Voronoi graph from set of polygons in Emgu CV (or OpenCV)

Question

Using Emgu CV I have extracted a set of closed polygons from the contours in an image of a road network. The polygons represent road outlines. The result is shown below, plotted over an OpenStreetMaps map (the polygons in 'pixel' form from Emgu CV have been converted to latitude/longitude form to be plotted).

Set of polygons representing road outlines:

I would now like to compute the Voronoi diagram of this set of polygons, which will help me find the centerline of the road. But in Emgu CV I can only find a way to get the Voronoi diagram of a set of points. This is done by finding the Delaunay triangulation of the set of points (using the Subdiv2D class) and then computing the voronoi facets with GetVoronoiFacets.

I have tried computing the Voronoi diagram of the points defined by all the polygons in the set (each polygon is a list of points), but this gives me an extremely complicated Voronoi diagram, as one might expect:

Voronoi diagram of set of points:

This image shows a smaller portion of the first picture (for clarity, since it is so convoluted). Indeed some of the lines in the diagram seem to represent the road centerline, but there are so many other lines, it will be tough to find a criterion to extract the "good" lines.

Another potential problem that I am facing is that, as you should be able to tell from the first picture, some polygons are in the interior of others, so we are not in the standard situation of a set of disjoint closed polygons. That is, sometimes the road is between the outer boundary of one polygon and the inner boundary of another.

I'm looking for suggestions as to how to compute the Voronoi graph of the set of polygons using Emgu CV (or Open CV), hopefully overcoming this second problem I've outlined as well. I'm also open to other suggestions for how to acheive this without using Emgu CV.

Hexarchy

So, you need to compute the "center" of the streets starting from 1) an image, using pixel form (easy) or 2) using point coordinates lat, lng? For 1) you can draw the filled polygons, and use distance transform. The center of the streets will have the maximum distance value. Non-maxima suppression will give you the result – Carlenacarlene

From an image is what I need. Using a distance transform is a great idea, thanks. In fact I can apply the distance transform to my original binary image, which is where I originally computed the polygons from by finding the contours! This is great because then I don't need to deal with the problem of polygons containing other polygons. Can you help me with non-maxima suppression - how would I achieve this in Emgu CV? The closest I can find by searching is Harris edge detection. – Hexarchy

That said, the end result that I need is a graph of lat/longs which represent the road centerline... which I can find from the centerline pixels in principle, but perhaps that's not the best approach. Perhaps Voronoi graph is still a better approach. – Hexarchy

@Carlenacarlene please can you give me some help as to how to achieve non-maxima suppression? – Hexarchy

Hey Chris, sorry about this because its not really an answer, but how did you manage to get the roads in the map using Emgu CV. It's exactly what I've been trying to do. Yours is the closest thing I've found. Cheers and thanks. – Rummage

I've just used the Voronoi graph of the set of points, and taken those edges which fall in the region of interest (inside the big outer polygon, and outside the inner ones). This gives you a graph with "hairy" appearance (like a caterpillar with hairs, and its body is the road centerline). The "hairs" can be removed be removing nodes in the graph with only one neighbor (I've written my own graph data structure to represent the road). You may need to do this multiple times. – Hexarchy

Answer 1

If you already have polygons, you can try computing the Straight Skeleton.

I haven't tried it, but CGAL has an implementation. Note that this particular function license is GPL.

A possible issue may be:

The current version of this CGAL package can only construct the straight skeleton in the interior of a simple polygon with holes, that is it doesn't handle general polygonal figures in the plane.

Probably there are workarounds for that. For example you can include all polygons in a bigger rectangle (this way the original polygons will be holes of the new rectangle). This may not work well if the original polygons have holes. To solve that, you could execute the algorithm for each polygon with holes and then put all polygons in a rectangle, removing all holes and execute the algorithm again.

Emlynn