× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

How can I find endpoints of binary skeleton image in OpenCV?

Ray Phan
Feb 02, 2015
<p>Given your tags of your questions and answers in your profile, I'm going to assume you want a C++ implementation. When you skeletonize an object, the object should have a 1 pixel thickness. Therefore, one thing that I could suggest is find those pixels that are non-zero in your image, then search in an 8-connected neighbourhood surrounding this pixel and count those pixels that are non-zero. If the count is only 2, then that is a candidate for an skeleton endpoint. Note that I'm also going to ignore the border so we don't go out of bounds. If the count is 1, it's a noisy isolated pixel so we should ignore it. If it's 3 or more, then that means that you're examining part of the skeleton at either a point within the skeleton, or you're at a point where multiple lines are connected together, so this shouldn't be an endpoint either.</p> <p>I honestly can't think of any algorithm other than checking all of the skeleton pixels for this criteria.... so the complexity will be <code>O(mn)</code>, where <code>m</code> and <code>n</code> are the rows and columns of your image. For each pixel in your image, the 8 pixel neighbourhood check takes constant time and this will be the same for all skeleton pixels you check. However, this will certainly be sublinear as the majority of your pixels will be 0 in your image, so the 8 pixel neighbourhood checking won't happen most of the time.</p> <p>As such, this is something that I would try, assuming that your image is stored in a <code>cv::Mat</code> structure called <code>im</code>, it being a single channel (grayscale) image, and is of type <code>uchar</code>. I'm also going to store the co-ordinates of where the skeleton end points are in a <code>std::vector</code> type. Every time we detect a skeleton point, we will add two integers to the vector at a time - the row and column of where we detect the ending skeleton point.</p> <pre><code>// Declare variable to count neighbourhood pixels int count; // To store a pixel intensity uchar pix; // To store the ending co-ordinates std::vector&lt;int&gt; coords; // For each pixel in our image... for (int i = 1; i &lt; im.rows-1; i++) { for (int j = 1; j &lt; im.cols-1; j++) { // See what the pixel is at this location pix = im.at&lt;uchar&gt;(i,j); // If not a skeleton point, skip if (pix == 0) continue; // Reset counter count = 0; // For each pixel in the neighbourhood // centered at this skeleton location... for (int y = -1; y &lt;= 1; y++) { for (int x = -1; x &lt;= 1; x++) { // Get the pixel in the neighbourhood pix = im.at&lt;uchar&gt;(i+y,j+x); // Count if non-zero if (pix != 0) count++; } } // If count is exactly 2, add co-ordinates to vector if (count == 2) { coords.push_back(i); coords.push_back(j); } } } </code></pre> <p>If you want to show the co-ordinates when you're done, just check every pair of elements in this vector:</p> <pre><code>for (int i = 0; i &lt; coords.size() / 2; i++) cout &lt;&lt; "(" &lt;&lt; coords.at(2*i) &lt;&lt; "," coords.at(2*i+1) &lt;&lt; ")\n"; </code></pre> <hr> <p>To be complete, here's a Python implementation as well. I'm using some of <code>numpy</code>'s functions to make this easier for myself. Assuming that your image is stored in <code>img</code>, which is also a grayscale image, and importing the OpenCV library and <code>numpy</code> (i.e. <code>import cv2</code>, <code>import numpy as np</code>), this is the equivalent code:</p> <pre><code># Find row and column locations that are non-zero (rows,cols) = np.nonzero(img) # Initialize empty list of co-ordinates skel_coords = [] # For each non-zero pixel... for (r,c) in zip(rows,cols): # Extract an 8-connected neighbourhood (col_neigh,row_neigh) = np.meshgrid(np.array([c-1,c,c+1]), np.array([r-1,r,r+1]), dtype=int) # Convert into a single 1D array and check for non-zero locations pix_neighbourhood = img[row_neigh,col_neigh].ravel() != 0 # If the number of non-zero locations equals 2, add this to # our list of co-ordinates if np.sum(pix_neighbourhood) == 2: skel_coords.append((r,c)) </code></pre> <p>To show the co-ordinates of the end points, you can do:</p> <pre><code>print "".join(["(" + str(r) + "," + str(c) + ")\n" for (r,c) in skel_coords]) </code></pre> <hr> <p><strong>Minor note:</strong> This code is untested. I don't have C++ OpenCV installed on this machine so hopefully what I wrote will work. If it doesn't compile, you can certainly translate what I have done into the right syntax. Good luck!</p> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/26537313/How%20can%20I%20find%20endpoints%20of%20binary%20skeleton%20image%20in%20OpenCV?/26541105">Stack Overflow</a>.</p>
comments powered by Disqus