Lloyd's algorithm: Difference between revisions

Revision as of 23:50, 6 March 2020

Latest revision as of 15:03, 29 April 2025

(12 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Algorithm used for points in euclidean space}}

In [[computerelectrical scienceengineering]] and [[electricalcomputer engineeringscience]], '''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. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in [[Voronoi diagram]]s.

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 = rightleft

| direction = verticalhorizontal

| header = Example of Lloyd's algorithm. The Voronoi diagram of the current pointssite positions (red) at each iteration is shown. The plusgray signscircles denote the centroids of the Voronoi cells.

| header_align = left

| header_background =

| footer = In the last image, the pointssites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.

| footer_align =

| footer_background =

Line 26 ⟶ 31:

| caption4 = Iteration 15

}}

{{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. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in [[Voronoi diagram]]s.

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==

Line 56 ⟶ 60:

** 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|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 and can be easily computed, e.g. using [[Centroid#By geometric decomposition|cartesian coordinates]].

** Weighting computes as simplex-to-cell '''area''' ratios.

* Three dimensions:

Line 79 ⟶ 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 equilateral elements as well as avoiding the problems with tangling that can arise with Laplacian smoothing. However, Laplacian smoothing can be applied more generally to meshes with non-triangular elements.

Line 107 ⟶ 111:

| title = Floating points: a method for computing stipple drawings

| volume = 19

| year = 2000}}.</ref>| s2cid = 142991

| citeseerx = 10.1.1.233.5810

}}.</ref>

<ref name="dew10">{{citation

| last1 = Dickerson | first1 = Matthew T. | author1-link = Matthew T. Dickerson

Line 117 ⟶ 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

Line 167 ⟶ 173:

| title = Least squares quantization in PCM

| volume = 28

| year = 1982| urls2cid = http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf10833328

}}.</ref>

<ref name="sg86">{{citation

Line 186 ⟶ 192:

| publisher = [[ACM SIGGRAPH]]

| title = Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR)

| year = 2002}}.</ref>| isbn = 1-58113-494-0

| s2cid = 12153589

}}.</ref>

<ref name="h01">{{citation

| last = Hausner| first = Alejo

Line 194 ⟶ 202:

| pages = 573–580

| contribution = Simulating decorative mosaics

| year = 2001}}.</ref>| isbn = 1-58113-374-X

| 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>

}}