| Lloyd's Algorithm |
Article Index for Lloyd's |
Information AboutLloyd's Algorithm |
|
Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step:
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
|
|
|