Get notified about new tutorials
RECEIVE NEW TUTORIALS

First 15 Minutes Free

289 sessions given

since Jul 09, 2014

since Jul 09, 2014

Likelihood of Reply:
80%

Response Time:
within an hour

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<int> coords;
// For each pixel in our image...
for (int i = 1; i < im.rows-1; i++) {
for (int j = 1; j < im.cols-1; j++) {
// See what the pixel is at this location
pix = im.at<uchar>(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 <= 1; y++) {
for (int x = -1; x <= 1; x++) {
// Get the pixel in the neighbourhood
pix = im.at<uchar>(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 < coords.size() / 2; i++)
cout << "(" << coords.at(2*i) << "," coords.at(2*i+1) << ")\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>

Get New Tutorials Delivered to Your Inbox

New tutorials will be sent to your Inbox once a week.