Image Stained Glass using Voronoi DiagramsMichael [email protected] geometrical concept of the Voronoidiagram was used to create an imagefilter providing a “stained glass” or mo-saic effect on an image. The Voronoidiagram was calculated by exploitingits dual relationship with the Delaunaytriangulation, which was in turn calcu-lated using a randomized incrementalalgorithm and stored in a DCEL. Var-ious methods were tried for selec tingthe points, including sampling from adistribution built using edge detection.Sampling using edge detection distri-butions was shown to provide resultssignificantly better than uniform ran-dom sampling.1 IntroductionVoronoi diagrams, when calculated on someset of N points in the 2d plane, s egme nt thespace into regions surrounding every point. Thepolygonal regions are such that, within a regionsurrounding some point p0, the point p0is closerto any point p in that region than any other ofthe N points included in the Voronoi diagram.The mapping between points in the plane andsurrounding regions is one to one.This information has many uses, but one ofthe most obvious is processing an image for anartistic effect. The representation created byshading a Voronoi diagram on N points in theimage plane with colors from each sample pointcreates a “stained glass” or mosaic version of theimage. One of the key problems here is effectiveselection of the point set P for the Voronoi dia-gram.2 Theory2.1 Voronoi DiagramsFirst, it is appropriate to examine the algo-rithms involved in the efficient calculation of aVoronoi diagram on a set of N points. The goalis a polygonal map of the plane consisting of aset of polygons surrounding the N points. Thepolygon surrounding a point p covers the areafor which p is the close st of the N points.Given two points p and p0, we can create aVoronoi diagram by drawing a line perpendic-ular to the line pp0, intersecting pp0at its mid-point. A Voronoi diagram with more points in-cludes many such lines, meaning that each poly-gon has straight edges consisting of line seg-ments which are sections of such perpendiculars.Voronoi diagrams can be calculated directly,using for example the beach line algorithm fromthe work (Fortune, 1986). It is often simpler,however, to take advantage of the close rela-tionship that exists between the structure of theVoronoi diagram, and that of the Delaunay tri-angulation. (Guibas et al., 1990)2.2 Delaunay TriangulationA triangulation of some point set P is a planarsubdivision such that every polygon is a triangle(except for the unbounded face), and the ver-tices are points in P . A triangulation exists forevery point set P , as any bounded face can besplit up into triangles, and the unbounded faceis simply the complement of the convex hull forP . There are, of course, many different trian-gulations on any one set of points P . Giventwo triangles bordered by a common edge, it isalways possible to “flip” this edge such that itconnects the remaining two points, assuming thequadrilateral in question is convex. (Berg, 2000)In a triangulation, it is undesirable to havesmall (sharp) angles. There is one triangula-tion, called the Delaunay triangulation, whichmaximizes the minimum angle and therefore isthe “best” triangulation. One simple way to findthis triangulation is to take an arbitrary trian-gulation and flip all illegal edges. Here, an il-legal edge is defined as an edge for which flip-ping will improve the triangulation: the orderedset of angles after flipping will be lexicographi-cally greater than the set before flipping. (Berg,2000) Of course, an edge can only b e flipped inthe case of a convex quadralateral. An exampleof such an edge flip is shown on fig. 1.It is not necessary to calculate all the anglesto determine the legality of an edge. Considertwo triangles abc and dbc that share an edge cb.Let C be the circle defined by abc. The edge ijis illegal if an only if the point d lines inside C.A proof can be found in (Berg, 2000).Figure 1: An edge flip during the process ofcreating a Delaunay triangulation.http://www.cescg.org/CESCG-2004/web/Domiter-Vid/A Delaunay triangulation can be constructedusing an incremental algorithm based on theabove. (Berg, 2000) Randomizing the point setP , add the points sequentially to the triangula-tion. Each time a point is added, start by trian-gulating the face containing the new point, andthen legalize edges recursively until all edges inthe triangulation are legal. Thus, the algorithmmaintains a correct Delaunay triangulation ofthe currently included points as an invariant.2.3 Dual TransformationThe last step in constructing a Voronoi diagramon P is to convert the Delaunay triangulationon P into a Voronoi diagram. The structuresare related through duality.A face in the Delaunay triangulation corre-sponds to a vertex of the Voronoi diagram, suchthat the location of the Voronoi vertex is thecenter of circumcircle for the (triangular) De-launay face. A vertex in the Delaunay trian-gulation corresponds to a face in the Voronoidiagram. This Voronoi face surrounds the De-launay vertex and represents the Voronoi cell forthis vertex. An edge in the Delaunay triangula-tion corresponds to a p e rpendicular edge in theVoronoi diagram. Two Voronoi vertices are con-nected if an only if the corresponding Delaunayfaces are adjacent. Figure 2 shows a Delaunaytriangulation and the corresp onding Voronoi di-agram.2.4 Point SamplingOne of the primary difficulties in using Voronoidiagrams to create stained glass effects is theselection of the point set P on which to buildthe diagram. Badly chosen points create a re-sult that captures none of the features in theoriginal image. In this project, the implemen-tation of fully automated, intelligent point se-lection was a key goal. Point selection can bedone, or adjusted, manually, however the needfor such intervention limits to applicability ofthe processing, and so was not studied here.2.4.1 Naive ApproachesThe simplest method for point selection usesa random sample of N points, distributed uni-formly within the boundaries of the image. Sucha method is of course very simple to implement,and also has an advantage that follows from itsuniformity. Because the distribution is uniform,the sizes of all the Voronoi cells will be relativelysmall, and thus a badly-colored Voronoi cell canhave only a limited size. The obvious issue withsuch a method is that it fails to account for theglobal features of an