Content deleted Content added
m Use vector images |
computing voronoi cells and the centroid |
||
Line 40:
* 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.
Obtaining the Voronoi cells and computing its centroid is not a trivial task, and [[Monte Carlo methods]] is typically used for this purpose. In this method, random sample points are generated according to some fixed probability distribution. Each random point is declared to belong to the Voronoi cell corresponding to the nearest seed point. After a large number of random samples have been generated, the average of random samples collected in each Voronoi cell gives the new centroids of 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]] {{harv|Du|Emelianenko|Ju|2006}}. In higher dimensions, some slightly weaker convergence results are known {{harv|Sabin|1986}}, {{harv|Emelianenko|Ju|Rand|2009}}.
Line 45 ⟶ 47:
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.
The Lloyd's method was originally used for scalar quantization, but it is clear that the method extends for vector quantization as well. 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]] {{harv|Deussen|Hiller|van Overveld|Strothotte|2000}}. In this application, the centroids can be weighted based on a reference image {{harv|Secord|2002}} to produce stipple illustrations matching an input image.
| |||