Databases
StackOverflow2013
Postsdbo
POExtracting segments from a list of 8-connected pixels
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POExtracting segments from a list of 8-connected pixels
    primarykey
    data
    text
    <p><em>Current situation</em> : I'm trying to extract segments from an image. Thanks to openCV's <code>findContours()</code> method, I now have a list of 8-connected point for every contours. However, these lists are not directly usable, because they contain a lot of duplicates.</p> <p><em>The problem</em> : <strong>Given a list of 8-connected points, which can contain duplicates, extract segments from it.</strong> </p> <p>Possible solutions : </p> <ul> <li>At first, I used openCV's <code>approxPolyDP()</code> method. However, the results are pretty bad... Here is the zoomed contours : </li> </ul> <p><img src="https://i.stack.imgur.com/eLX8e.png" alt="enter image description here"></p> <p>Here is the result of <code>approxPolyDP()</code> : (9 segments! Some overlap)</p> <p><img src="https://i.stack.imgur.com/irdD9.png" alt="enter image description here"></p> <p>but what I want is more like : </p> <p><img src="https://i.stack.imgur.com/IkrNP.png" alt="enter image description here"></p> <p>It's bad because <code>approxPolyDP()</code> can convert something that "looks like several segments" in "several segments". However, what I have is a list of points that tend to iterate several times over themselves.</p> <p>For example, if my points are:</p> <pre><code>0 1 2 3 4 5 6 7 8 9 </code></pre> <p>Then, the list of point will be <code>0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9</code>... And if the number of points become large (>100) then the segments extracted by <code>approxPolyDP()</code> are unfortunately not duplicates (i.e : they overlap each other, but are not stricly equal, so I can't just say "remove duplicates", as opposed to pixels for example) </p> <ul> <li>Perhaps, I've got a solution, but it's pretty long (though interesting). First of all, for all 8-connected list, I <strong>create a sparse matrix</strong> (for efficiency) and set the matrix values to 1 if the pixel belongs to the list. Then, I create a <strong>graph</strong>, with nodes corresponding to pixels, and edges between neighbouring pixels. This also means that I <strong>add all the missing edges between pixels</strong> (complexity small, possible because of the sparse matrix). Then I <strong>remove all possible "squares"</strong> (4 neighouring nodes), and this is possible because I am already working on pretty thin contours. Then I can launch a <strong>minimal spanning tree</strong> algorithm. And finally, I can approximate every branch of the tree with openCV's <code>approxPolyDP()</code></li> </ul> <p><a href="http://img197.imageshack.us/img197/4488/segmentation.png" rel="noreferrer">segmentation http://img197.imageshack.us/img197/4488/segmentation.png</a> </p> <p>Here are fantastic pictures (thanks Paint!) of the original list, and the associated graph. Then, when I add edges between neighbours. And finally, when I remove edges and make a minimum spanning tree (not useful here)</p> <p>To sum up : I've got a tedious method, that I've not yet implemented as it seems error-prone. However, I ask <strong>you</strong>, people at StackOverflow : are there other existing methods, possibly with good implementations?</p> <hr> <p>Edit : To clarify, once I have a tree, I can extract "branches" (branches start at leaves or nodes linked to 3 or more other nodes) Then, the algorithm in openCV's <code>approxPolyDP()</code> is the <a href="http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm" rel="noreferrer">Ramer–Douglas–Peucker algorithm</a>, and here is the Wikipedia picture of what it does : </p> <p><img src="https://i.stack.imgur.com/OCaAo.png" alt="enter image description here"></p> <p>With this picture, it is easy to understand why it fails when points may be duplicates of each other</p> <hr> <p>Another edit : In my method, there is something that may be interesting to note. When you consider points located in a grid (like pixels), then generally, the minimal spanning tree algorithm is not useful because there are many possible minimal trees</p> <pre><code>X-X-X-X | X-X-X-X </code></pre> <p>is fundammentally very different from</p> <pre><code>X-X-X-X | | | | X X X X </code></pre> <p>but both are minimal spanning trees</p> <p>However, in my case, my nodes rarely form clusters because they are supposed to be contours, and there is already a thinning algorithm that runs beforehand in the <code>findContours()</code>.</p> <hr> <p>Answer to Tomalak's comment : </p> <p><img src="https://i.stack.imgur.com/iTMPT.png" alt="enter image description here"></p> <p>If DP algorithm returns 4 segments (the segment from the point <code>2</code> to the center being there twice) I would be happy! Of course, with good parameters, I can get to a state where "by chance" I have identical segments, and I can remove duplicates. However, clearly, the algorithm is not designed for it.</p> <p>Here is a real example with far too many segments : </p> <p><img src="https://i.stack.imgur.com/TCga8.png" alt="enter image description here"></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USFezvez
    1. USFezvez
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO`are unfortunately not duplicates (i.e : they overlap each other, but are not stricly equal, so I can't just say "remove duplicates", as opposed to pixels for example)` I don't understand this. Why not?
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. USLightness Races in Orbit
    2. COI answered by editing my post with another magnificent Paint picture =)
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. USFezvez
    3. COI'm looking at the picture you added in response to Tomalak, and I have a doubt: the result of the DP algorithm is actually a valid solution, if you accept that the observed points can be as far from the "true"! segment as the central point in the image is. Do you have a specific threshold for the point-line distance that the algorithm must respect?
      singulars
      1. POExtracting segments from a list of 8-connected pixels
      1. USCoffee on Mars
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload