Lloyd's algorithm
In computer graphics and electrical engineering, also known as Voronoi iteration or relaxation, a method for evenly distributing samples or objects, usually points.
Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step:
- The Voronoi diagram of all the points is computed.
- Each cell of the Voronoi diagram is integrated and the centroid is computed.
- Each point is then moved to the centroid of its voronoi cell.
Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move further apart, and widely spaced points move closer together. In one dimension, this algorithm has been shown to converge to a centroidal Voronoi diagram (Du, 1999). In two dimensions, it is theorized to converge but no proof yet exists.
Since the algorithm converges slowly, and, due to limitations in numerical precision the algorithm will often not converge, real-world applications of Lloyd's algorithm stop once the distribution is "good enough." One common termination criteria is when the maximum distance a point moves in one iteration is below some set limit.
Lloyd's method is used in computer graphics because the resulting distribution has blue noise characteristics (see also Colors of noise), meaning there are few low-frequency components that could be interpreted as artifacts. It is particularly well-suited to picking sample positions for dithering.
Lloyd's algorithm is also used to generate dot drawings in the style of stippling (Deussen, 2002). In this application, the centroids can be weighted based on a reference image (Secord, 2002) to produce stipple illustrations matching an input image.
References
- Oliver Deussen, Stefan Hiller, Cornelius van Overveld, and Thomas Strothotte. Floating Points: A Method for Computing Stipple Drawings. Computer Graphics Forum, vol. 19, no. 3, (Proceedings of Eurographics), pp. 41-51, 2000.
- Q. Du, V. Faber, and M. Gunzburger. Centroidal Voronoi Tesselations. Siam review, vol. 41, no. 4, pp. 637-676, 1999.
- S. Lloyd. Least Square Quantization in PCM. IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129-137, 1982.
- Adrian Secord. Weighted Voronoi Stippling. Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR), pp. 37-43, 2002.