Content deleted Content added
Link suggestions feature: 3 links added. |
|||
| (42 intermediate revisions by 29 users not shown) | |||
Line 1:
{{Short description|Algorithm used for points in euclidean space}}
In [[
Although the algorithm may be applied most directly to the [[Euclidean plane]], similar algorithms may also be applied to higher-dimensional spaces or to spaces with other [[Non-Euclidean geometry|non-Euclidean]] metrics. Lloyd's algorithm can be used to construct close approximations to [[centroidal Voronoi tessellation]]s of the input,<ref name="dfg99"/> which can be used for [[Quantization (signal processing)|quantization]], [[dithering]], and [[stippling]]. Other applications of Lloyd's algorithm include smoothing of [[triangle mesh]]es in the [[finite element method]].▼
{{multiple image
| align =
| direction =
| header = Example of Lloyd's algorithm.
| header_align =
| header_background =
| footer = In the last image, the
| footer_align =
| footer_background =
| width = 200
Line 12 ⟶ 17:
| image1 = LloydsMethod1.svg
| alt1 = Lloyd's method, iteration 1
| caption1 =
| image2 = LloydsMethod2.svg
| alt2 = Lloyd's method, iteration 2
| caption2 =
| image3 = LloydsMethod3.svg
| alt3 = Lloyd's method, iteration 3
| caption3 =
| image4 = LloydsMethod15.svg
| alt4 = Lloyd's method, iteration 15
| caption4 =
}}
{{clear}}
==History==
▲In [[computer science]] and [[electrical engineering]], '''Lloyd's algorithm''', also known as '''Voronoi iteration''' or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly-spaced sets of points in subsets of [[Euclidean space]]s, and partitions of these subsets into well-shaped and uniformly sized convex cells.<ref name="l82"/> Like the closely related [[k-means clustering|''k''-means clustering]] algorithm, it repeatedly finds the [[centroid]] of each set in the partition, and then re-partitions the input according to which of these centroids is closest. However, Lloyd's algorithm differs from ''k''-means clustering in that its input is a continuous geometric region rather than a discrete set of points. Thus, when re-partitioning the input, Lloyd's algorithm uses [[Voronoi diagram]]s rather than simply determining the nearest center to each of a finite set of points as the ''k''-means algorithm does.
The algorithm was first proposed by Stuart P. Lloyd of [[Bell Labs]] in 1957 as a technique for [[pulse-code modulation]]. Lloyd's work became widely circulated but remained unpublished until 1982.<ref name="l82"/> A similar algorithm was developed independently by Joel Max and published in 1960,<ref name="m60"/> which is why the algorithm is sometimes referred as the Lloyd-Max algorithm.
▲Although the algorithm may be applied most directly to the [[Euclidean plane]], similar algorithms may also be applied to higher-dimensional spaces or to spaces with other [[Non-Euclidean geometry|non-Euclidean]] metrics. Lloyd's algorithm can be used to construct close approximations to [[centroidal Voronoi tessellation]]s of the input,<ref name="dfg99"/> which can be used for [[Quantization (signal processing)|quantization]], [[dithering]], and [[stippling]]. Other applications of Lloyd's algorithm include smoothing of [[triangle mesh]]es in the [[finite element method]].
==Algorithm description==
Lloyd's algorithm starts by an initial placement of some number ''k'' of point sites in the input ___domain. In mesh
It then repeatedly executes the following relaxation step:
* The [[Voronoi diagram]] of the ''k'' sites is computed.
* Each cell of the Voronoi diagram is integrated, and the centroid is computed.
* Each site is then moved to the centroid of its Voronoi cell.
==Integration and centroid computation==
Because Voronoi diagram construction algorithms can be highly non-trivial, especially for inputs of dimension higher than two, the steps of calculating this diagram and finding the exact centroids of its cells may be replaced by an approximation.
===Approximation===
A common simplification is to employ a suitable discretization of space like a fine pixel-grid, e.g. the texture [[Z-buffering|buffer]] in graphics hardware. Cells are materialized as pixels, labeled with their corresponding site-ID. A cell's new center is approximated by averaging the positions of all pixels assigned with the same label.
Alternatively, [[Monte Carlo methods]] may be used, in which random sample points are generated according to some fixed underlying probability distribution, assigned to the closest site, and averaged to approximate the centroid for each site.
===Exact computation===
Although embedding in other spaces is also possible, this elaboration assumes [[Euclidean distance|Euclidean space]] using the [[Lp space|''L<sup>2</sup>'' norm]] and discusses the two most relevant scenarios, which are two, and respectively three dimensions.
Since a Voronoi cell is of convex shape and always encloses its site, there exist trivial decompositions into easy integratable simplices:
* In two dimensions, the edges of the polygonal cell are connected with its site, creating an umbrella-shaped set of triangles.
* In three dimensions, the cell is enclosed by several planar polygons which have to be triangulated first:
** Compute a center for the polygon face, e.g. the average of all its vertices.
** Connecting the vertices of a polygon face with its center gives a planar umbrella-shaped triangulation.
** Trivially, a set of [[Tetrahedron|tetrahedra]] is obtained by connecting triangles of the cell's hull with the cell's site.
Integration of a cell and computation of its [[centroid]] ([[center of mass]]) is now given as a weighted combination of its simplices' centroids (in the following called <math display="inline">\mathbf{c}_i</math>).
* Two dimensions:
** For a triangle the centroid can be easily computed, e.g. using [[Centroid#By geometric decomposition|cartesian coordinates]].
** Weighting computes as simplex-to-cell '''area''' ratios.
* Three dimensions:
** The [[Tetrahedron#Centroid|centroid of a tetrahedron]] is found as the intersection of three bisector planes and can be expressed as a matrix-vector product.
** Weighting computes as simplex-to-cell '''volume''' ratios.
For a 2D cell with {{math|''n''}} triangular simplices and an accumulated area <math display="inline">A_C = \sum_{i=0}^n a_i</math> (where <math display="inline">a_i</math> is the [[Triangle#Computing the area of a triangle|area of a triangle]] simplex), the new cell centroid computes as:
:<math>
C = \frac{1}{A_C}\sum_{i=0}^{n}\mathbf{c}_i a_i
</math>
Analogously, for a 3D cell with a volume of <math display="inline">V_C = \sum_{i=0}^n v_i</math> (where <math display="inline">v_i</math> is the [[Tetrahedron#Volume|volume of a tetrahedron]] simplex), the centroid computes as:
:<math>
C = \frac{1}{V_C}\sum_{i=0}^{n}\mathbf{c}_i v_i
</math>
==Convergence==
Line 47 ⟶ 83:
==Applications==
Lloyd's method was originally used for scalar quantization, but it is clear that the method extends for [[vector quantization]] as well. As such, it is extensively used in [[data compression]] techniques in [[information theory]]. 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]].<ref name="dhos00"/> In this application, the centroids can be weighted based on a reference image to produce stipple illustrations matching an input image.<ref name="s02"/>
In the [[finite element method]], an input ___domain with a [[complex geometry]] is partitioned into elements with simpler shapes; for instance, two-dimensional domains (either subsets of the Euclidean plane or surfaces in three dimensions) are often partitioned into triangles. It is important for the convergence of the finite element methods that these elements be well shaped; in the case of triangles, often elements that are nearly equilateral triangles are preferred. Lloyd's algorithm
can be used to smooth a mesh generated by some other algorithm, moving its vertices and changing the connection pattern among its elements in order to produce triangles that are more closely equilateral.<ref name="dg02"/> These applications typically use a smaller number of iterations of Lloyd's algorithm, stopping it to convergence, in order to preserve other features of the mesh such as differences in element size in different parts of the mesh. In contrast to a different smoothing method, [[Laplacian smoothing]] (in which mesh vertices are moved to the average of their neighbors' positions), Lloyd's algorithm can change the topology of the mesh, leading to more nearly
==Different distances==
Lloyd's algorithm is usually used in a [[Euclidean space]]. The Euclidean distance plays two roles in the algorithm: it is used to define the Voronoi cells, but it also corresponds to the choice of the centroid as the representative point of each cell, since the centroid is the point that minimizes the average squared Euclidean distance to the points in its cell. Alternative distances, and alternative central points than the centroid, may be used instead. For example, {{harvtxt|Hausner|2001}} used a variant of the [[Manhattan metric]] (with locally
== See also ==
* The [[Linde–Buzo–Gray algorithm]], a generalization of this algorithm for vector quantization
* [[Farthest-first traversal]], a different method for generating evenly
* [[Mean shift]], a related method for finding maxima of a density function
* [[K-means++]]
==References==
Line 74 ⟶ 111:
| title = Floating points: a method for computing stipple drawings
| volume = 19
| year = 2000
| citeseerx = 10.1.1.233.5810
}}.</ref>
<ref name="dew10">{{citation
| last1 = Dickerson | first1 = Matthew T. | author1-link = Matthew T. Dickerson
Line 84 ⟶ 123:
| pages = 13–22
| title = Proc. 7th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2010)
| year = 2010| isbn = 978-1-4244-7606-0 | s2cid = 15971504 }}.</ref>
<ref name="dej06">{{citation
| last1 = Du | first1 = Qiang | author1-link = Qiang Du
| last2 = Emelianenko | first2 = Maria | author2-link = Maria Emelianenko
| last3 = Ju | first3 = Lili
| doi = 10.1137/040617364
Line 94 ⟶ 133:
| title = Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations
| volume = 44
| year = 2006| citeseerx = 10.1.1.591.9903}}.</ref>
<ref name="dfg99">{{citation
| last1 = Du | first1 = Qiang | author1-link = Qiang Du
| last2 = Faber | first2 = Vance
| last3 = Gunzburger | first3 = Max
Line 105 ⟶ 144:
| title = Centroidal Voronoi tessellations: applications and algorithms
| volume = 41
| year = 1999| bibcode = 1999SIAMR..41..637D}}.</ref>
<ref name="dg02">{{citation
| last1 = Du | first1 = Qiang | author1-link = Qiang Du
| last2 = Gunzburger | first2 = Max
| doi = 10.1016/S0096-3003(01)00260-0
Line 115 ⟶ 154:
| title = Grid generation and optimization based on centroidal Voronoi tessellations
| volume = 133
| year = 2002
}}.</ref>
<ref name="ejr09">{{citation
| last1 = Emelianenko | first1 = Maria
Line 122 ⟶ 162:
| journal = SIAM Journal on Numerical Analysis
| pages = 1423–1441
| title = Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in
| volume = 46
| year = 2009 | doi=10.1137/070691334}}.</ref>
Line 133 ⟶ 173:
| title = Least squares quantization in PCM
| volume = 28
| year = 1982
}}.</ref>
<ref name="sg86">{{citation
| last1 = Sabin | first1 = M. J.
Line 151 ⟶ 192:
| publisher = [[ACM SIGGRAPH]]
| title = Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR)
| year = 2002
| s2cid = 12153589
}}.</ref>
<ref name="h01">{{citation
| last = Hausner| first = Alejo
Line 159 ⟶ 202:
| pages = 573–580
| contribution = Simulating decorative mosaics
| year = 2001
| s2cid = 7188986
}}.</ref>
<ref name="m60">{{citation
| last = Max| first = Joel
| doi = 10.1109/TIT.1960.1057548
| title = Quantizing for minimum distortion
| journal = [[IRE Transactions on Information Theory]]
| pages = 7–12
| volume = 6
| issue = 1
| year = 1960}}.</ref>
}}
==External links==
* [http://demogng.de/js/demogng.html?model=LBG&showAutoRestart&showVoronoi DemoGNG.js] Graphical Javascript simulator for LBG algorithm and other models, includes display of Voronoi regions
[[Category:Geometric algorithms]]
[[Category:
| |||