Extract segments from a list of 8-linked pixels

Question

Current situation: I am trying to extract segments from an image. Thanks to the openCV method findContours findContours() , I now have a list of points with 8 links for each path. However, these lists cannot be used directly, because they contain many duplicates.

Problem: Given a list of 8-connected points that may contain duplicates, extract segments from it.

Possible solutions:

• At first I used the openCV method approxPolyDP() . However, the results are pretty bad ... Here are the large-scale contours:

Here is the result of approxPolyDP() : (9 segments! Some overlap)

but I want more:

This is bad because approxPolyDP() can convert something that "looks like multiple segments" to "multiple segments". However, I have a list of points that tend to repeat several times above themselves.

For example, if my points are:

 0 1 2 3 4 5 6 7 8 9 

Then the list of points will be 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9 ... And if the number of points becomes large (> 100), then the segments extracted by approxPolyDP() , unfortunately, are not duplicated (then is: they overlap, but are not strictly equal, so I can’t just say “remove duplicates”, unlike pixels, for example)

• Maybe I have a solution, but it is quite long (albeit interesting). First of all, for all 8-linked lists, I create a sparse matrix (for efficiency) and set the matrix values ​​to 1 if the pixel belongs to the list. Then I create a graph , with nodes corresponding to pixels, and edges between adjacent pixels. It also means that I add all the missing edges between the pixels (the complexity is small, possible due to the sparse matrix). Then I delete all possible “squares” (4 neighboring nodes), and this is possible because I am already working on rather thin contours. Then I can run the minimal spanning tree algorithm. And finally, I can approximate each tree branch with openCV approxPolyDP()

segmentation http://img197.imageshack.us/img197/4488/segmentation.png

Here are some fantastic snapshots (thanks to Paint!) Of the source list and a related graph. Then when I add edges between neighbors. And finally, when I remove the edges and create a minimal spanning tree (not useful here)

To summarize: I have a tedious method that I haven't implemented yet, as it seems to be error prone. However, I ask you folks from StackOverflow: are there other existing methods, perhaps with good implementations?

---

Edit: To clarify, as soon as I have a tree, I can extract the “branches” (the branches begin at the leaves or nodes associated with 3 or more other nodes). Then the algorithm in openCV approxPolyDP() is the Ramer-Douglas-Puker algorithm , and here is a Wikipedia photo of what it does:

With this picture, it's easy to see why it fails when the dots can be duplicates.

---

Other editing: There is something interesting to note in my method. When you consider points located in a grid (for example, pixels), then, as a rule, the minimal spanning tree algorithm is not useful, since there are many possible minimal trees

 XXXX | XXXX 

fundamentally different from

 XXXX | | | | XXXX 

but both are minimal spanning trees

However, in my case, my nodes rarely form clusters, because they must be contours, and the thinning algorithm already exists, which is executed in advance in findContours() .

---

Reply to Tomalak's comment:

If the DP algorithm returns 4 segments (the segment from point 2 to the center, which will be there twice), I would be happy! Of course, with good parameters, I can get to a state where, by chance, I have the same segments, and I can remove duplicates. However, obviously, the algorithm is not intended for him.

Here is a real example with too many segments:

Answer 1

Using Mathematica 8, I created a morphological graph from a list of white pixels in the image. It works great on your first image:

Create a morphological graph:

 graph = MorphologicalGraph[binaryimage]; 

Then you can request the properties of the chart that interest you.

This gives the names of the vertices in the graph:

 vertex = VertexList[graph] 

Rib List:

 EdgeList[graph] 

And this gives the top position:

 pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex 

Here are the results for the first image:

 In[21]:= vertex = VertexList[graph] Out[21]= {1, 3, 2, 4, 5, 6, 7, 9, 8, 10} In[22]:= EdgeList[graph] Out[22]= {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6, 6 \[UndirectedEdge] 7, 6 \[UndirectedEdge] 9, 8 \[UndirectedEdge] 9, 9 \[UndirectedEdge] 10} In[26]:= pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex Out[26]= {{54.5, 191.5}, {98.5, 149.5}, {42.5, 185.5}, {91.5, 138.5}, {132.5, 119.5}, {157.5, 72.5}, {168.5, 65.5}, {125.5, 52.5}, {114.5, 53.5}, {120.5, 29.5}} 

Given the documentation at http://reference.wolfram.com/mathematica/ref/MorphologicalGraph.html , the MorphologicalGraph team first calculates the skeleton by morphological thinning:

 skeleton = Thinning[binaryimage, Method -> "Morphological"] 

Then the peak is discovered; these are branch points and end points:

 verteximage = ImageAdd[ MorphologicalTransform[skeleton, "SkeletonEndPoints"], MorphologicalTransform[skeleton, "SkeletonBranchPoints"]] 

And then the top is connected after analyzing their connectivity.

For example, you can start by breaking up the structure around the vertex, and then search for related components by displaying the edges of the graph:

 comp = MorphologicalComponents[ ImageSubtract[ skeleton, Dilation[vertices, CrossMatrix[1]]]]; Colorize[comp] 

The devil is in the details, but it seems like a solid starting point if you want to develop your own implementation.

Answer 2

Try mathematical morphology. First you need to dilate or close your image to fill the holes.

 cvDilate(pimg, pimg, NULL, 3); cvErode(pimg, pimg, NULL); 

I got this image

The next step should be to apply the thinning algorithm. Unfortunately, it is not implemented in OpenCV (MATLAB has bwmorph with argument thin ). For example, with MATLAB, I refined the image for this:

However, OpenCV has all the necessary basic morphological operations to implement thinning ( cvMorphologyEx , cvCreateStructuringElementEx , etc.).

Another idea.

Remote conversion is said to be very useful in such tasks. May be so. Consider the cvDistTransform function. He creates the following image:

Then using something like cvAdaptiveThreshold :

This skeleton. I think you can iterate over all related white pixels, find curves and filter out small segments.

Answer 3

I implemented a similar algorithm before, and I did it as an incremental least squares method. It worked well enough. The pseudocode is somewhat reminiscent of:

 L = empty set of line segments for each white pixel p line = new line containing only p C = empty set of points P = set of all neighboring pixels of p while P is not empty n = first point in P add n to C remove n from P line' = line with n added to it perform a least squares fit of line' if MSE(line) < max_mse and d(line, n) < max_distance line = line' add all neighbors of n that are not in C to P if size(line) > min_num_points add line to L 

where MSE (row) is the standard error of the row (summation over all points of the squared line of the distance to the best fitting line), and d (row, n) is the distance from point n to the line. Good max_distance values ​​seem like pixels or so, and max_mse seems to be much smaller and will depend on the average size of the line segments in your image. 0.1 or 0.2 pixels worked on fairly large images for me.

I used this on real images pre-processed using the Canny operator, so the only results I have are this. Here is the result of the above algorithm in the image:

It is also possible to make the algorithm fast. My C ++ implementation (a closed source forced to do my work, sorry, otherwise I would give it to you) processed the above image after about 20 milliseconds. This includes using the Canny operator to detect the edge, so in your case it should be even faster.