title: Extracting segments from a list of 8-connected pixels
body: <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 strictly 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 neighbouring 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>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 Stack Overflow: 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="https://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm" rel="nofollow 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 fundamentally 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>