News for hackers. Stuff that matters.
Re:K-Means Clustering by magicalhippo on Saturday January 13, 2024 @12:21AM (#38977554)
I implemented an algorithm which used k-means to reduce noise in a path tracer.

For each pixel instead of a single color value it generated k mean color values, using an online algorithm. These were then combined to produce the final pixel color.

The idea was that a pixel might have several distinct contributions (ie from different light sources for example), but due to the random sampling used in path tracing the variance of sample values is usually large.

The value k then was chosen based on scene complexity. There was also a memory trade-off of course, as memory usage was linear in k.

Re:K-Means Clustering by le-mark on Saturday January 13, 2024 @07:09AM (#38979257)
> For each pixel instead of a single color value it generated k mean color values, using an online algorithm.

What does online mean here?

Re:K-Means Clustering by magicalhippo on Saturday January 13, 2024 @02:29PM (#38983607)
Online means it processes the items as they come[1]. This means the algorithm can't consider all the items at once, and has to try to be clever on the spot.

In my case the algorithm uswd would use the first k samples as the initial means, and would then find which of the k means were closest to the current sample, and update that mean[2].

Given that in parh tracing one would typically use a fairly large number of samples per pixel relative to k, this approach did a reasonable job of approximating the k means.

[1]: https://en.wikipedia.org/wiki/Online_algorithm

[2]: https://yokolet.com/2017/05/29/online-algorithm.html