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:

Average color on the left, median on the right.

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:

Better, but boring.

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:

The scaled Laplacian image, the resulting points, and the colored Voronoi diagram.

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:

Original, result, triangle outlines

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.