Lloyd's algorithm

Lloyd's algorithm

In computer graphics and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is 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, also named a centroidal Voronoi tessellation (Du, 2006). In higher dimensions, some weaker convergence results are known (Sabin, 1986).

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 criterion 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, 2000). In this application, the centroids can be weighted based on a reference image (Secord, 2002) to produce stipple illustrations matching an input image.

See also

* The Linde-Buzo-Gray algorithm, which is a generalization of this algorithm.

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.
* Qiang Du, Maria Emelianenko, and Lili Ju. "Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations." SIAM Journal of Numerical Analysis, vol. 44, pp. 102-119, 2006.
* Qiang Du, Vance Faber, and Max Gunzburger. "Centroidal Voronoi Tessellations: Applications and Algorithms." Siam Review, vol. 41, no. 4, pp. 637-676, 1999.
* Stuart P. Lloyd. "Least Squares Quantization in PCM." IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129-137, 1982.
* J. Sabin and R. Gray. "Global Convergence and Empirical Consistency of the Generalized Lloyd Algorithm." IEEE Transactions on Information Theory , vol. 32, no. 2, pp. 148-155, 1986.
* Adrian Secord. "Weighted Voronoi Stippling." Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR), pp. 37-43, 2002.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Lloyd R. Welch — Lloyd Richard Welch is a noted American information theorist, and co inventor of the Baum Welch algorithm.Welch received his B.S. in mathematics from the University of Illinois, 1951, and Ph.D. in mathematics from the California Institute of… …   Wikipedia

  • Lloyd Shapley — Infobox Scientist name = Lloyd S. Shapley |300px image width = caption = Lloyd S. Shapley in 2002, Los Angeles birth date = Birth date and age|1923|6|2|mf=y birth place = Cambridge, Massachusetts death date = death place = residence = nationality …   Wikipedia

  • K-means algorithm — The k means algorithm is an algorithm to cluster n objects based on attributes into k partitions, k < n. It is similar to the expectation maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural… …   Wikipedia

  • Linde-Buzo-Gray algorithm — The Linde Buzo Gray algorithm is a vector quantization algorithm to derive a good codebook.It is similar to the k means method in data clustering.The algorithm At each iteration, each vector is split into two new vectors.*A initial state:… …   Wikipedia

  • Shor's algorithm — Shor s algorithm, first introduced by mathematician Peter Shor, is a quantum algorithm for integer factorization. On a quantum computer, to factor an integer N, Shor s algorithm takes polynomial time in log{N}, specifically O((log{N})^3),… …   Wikipedia

  • Hirschberg's algorithm — Hirschberg s algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sumof… …   Wikipedia

  • Baum-Welch algorithm — In computer science, statistical computing and bioinformatics, the Baum Welch algorithm is used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the forward backward algorithm and is named for Leonard E. Baum and… …   Wikipedia

  • k-means clustering — In statistics and data mining, k means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. This results into a partitioning of… …   Wikipedia

  • Cluster analysis — The result of a cluster analysis shown as the coloring of the squares into three clusters. Cluster analysis or clustering is the task of assigning a set of objects into groups (called clusters) so that the objects in the same cluster are more… …   Wikipedia

  • David Mount — Not to be confused with David W. Mount, Professor Emeritus of Molecular and Cellular Biology at the University of Arizona. David Mount is currently a Professor at The University of Maryland (College Park Campus) whose research is in Computational …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”