Free space aware Voronoi diagram

Quick intro

In this article, you will find a method to extract an extended Voronoi Diagram from an image. This method takes in account the topology of the free space to post-process the Voronoi Diagram. The Voronoi diagram is extensively used in all sort of situation: skeletonization, matching, you name it… 😉

The Voronoi diagram is simply all the points that are at equal distance from 2 or more “stuff”. If you have an image where black pixels represent free space and the other ones are “stuff” (let’s call then occupied pixel), then the Voronoi diagram is every black point at equal distance of 2 or more occupied pixels.

The method presented here was published in this paper, that you can also find directly on my webpage. If you use this in academic work, please cite this paper.

The code is available here

Why this and no others

There is other tools to extract the Voronoi diagrams and I’m especially thinking of EVG-thin. While it’s very efficient and robust, it was too robust for my own application. I am working on drawings, while EVG-thin is used for place detection and paths creation in SLAM-maps (maps build by robots during exploration and localisation). Thus the robustness of EVG-thin meant that, either some detail of my maps would be suppressed or too many branches of the Voronoi diagram would be kept.

I needed a Voronoi Diagram that kept details that seemed important but removed noise in the drawing.


Case in example, let’s take this image :

Screenshot from 2017-03-10 14-07-33
One beautiful map

To construct the Voronoi diagram, we calculate the Euclidean distance image of the map. This function is available in OpenCV and here are the parameters I used :

cv::distanceTransform(img, img_out, labels, CV_DIST_L2, CV_DIST_MASK_PRECISE, CV_DIST_LABEL_CCOMP);

This is the image we obtain.

Screenshot from 2017-03-10 14-07-44
One beautiful distance image. The whiter the further away from an occupied pixel.

From this image, we are going to extract local maxima (place where a pixel is surrounded by pixels of lower value) of the image using a Laplacian filter. Here is the Laplacian filter:

\left[ \begin{matrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{matrix} \right]

The Laplacian filter is a tool to extract edges from the image. Since we work on the distance image, the Laplacian filter give a high negative value to all local maxima. So now we indeed have a complete Voronoi Diagram, where the pixel with the lowest values after the Laplacian filter was used, are on the branches of the Voronoi Diagram. See the next image.

Screenshot from 2017-03-10 14-07-55
We can see the contour of the occupied pixels and the voronoi diagram is the white and gray lines. Quite a lot of clutter

However, this image is pretty messy and we still haven’t extracted a proper Voronoi Diagram. What we have is a cluttered distance image where pixels value drop significantly when at equal distance from 2 or more occupied pixels. Note that, due to the nature of the Laplacian operator, the local maxima are now minima. We invert the image so that minima become maxima again.

So now comes the magic trimming of noisy points. Here is the logic of the trimming step:

“Drawings have a lot of details that are insignificant: wavy lines, small details that are not influencing the drawing much. While other details are really important: big empty zones, small passages between zones and smaller but really detailed structures.

Also, important structures are usually drawn bigger than insignificant ones to catch the eye.

The goal: penalize the first but give a boost to the later.”

Now we have a certain number of local maxima pixels from the Laplacian filter. The biggest the distance between the closest occupied pixel and the Voronoi point, the highest is the minima value of the Voronoi pixel. Thus, we have a measurement of the strength of the minima. We find the highest maxima of the image and trim the Voronoi points by keeping all points more than a certain percentage of the highest max. For example, if the highest max is 100 and I consider 10%, I will keep every point over 10.

Experimentally, I found that keeping all pixels whose value is more than 30% of the image’s strongest minimum’s value, lead to clear Voronoi graphs. Depending on your application, this percentage could vary, so be careful ;). Here is the resulting image after the trimming.

Screenshot from 2017-03-10 14-08-02
We only kept the strongest part of the Voronoi diagram. Yay for image processing.

The good thing about it is that it is not a branch based trimming but pixel based. So partial branch can be kept. The trimming is less binary than EVG-thin and can keep more details while removing the noise.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s