Image Triangulation: Voronoi Method

Voronoi diagrams are great, so let’s use them to stylize images. First, let’s just throw a bunch of points on an image, and compute the Voronoi diagram. Then for each cell, we fill it with the average or median color within:

Hmm. That’s not great. It doesn’t pay attention to the edges at all, and the pieces are all different sizes without regard to the image. Also, when we use the median color, it looks sharper and prettier. Lessons learned: pick points better, use median color.

What’s a better distribution of points? To get the classic stained-glass look, we can use Lloyd’s algorithm to distribute the points evenly:

That’s better than before, but it still neglects the image. We want there to be more points near edges, and fewer points in unchanging areas. Lloyd’s algorithm is good for clustering points, so let’s apply it to a version of the image that shows its variation. For example, let’s use the magnitude of the spatial Laplacian:

Getting better, but still not right! The points are at edges of the image, as desired, but that means that the Voronoi cells straddle the edges. We want the edges of the filled-in shapes to follow the edges of the image. For that, let’s divide the image into triangles with a Delaunay triangulation, and fill in the triangles instead:

It works! And it doesn’t need a crazy number of points, either. Check out this animation of refinement, where the number of steps doubles per frame:

This is a quick way to make a triangularized image, but it lacks the error bounds of the subdivision method. Of course, the two could be combined: use this method for a rough approximation, then use the subdivision to refine it.