How to find the endpoints of a binary skeleton in OpenCV?

Question

I have a skeleton in the form of binary pixels, for example:

I would like to find the coordinates of the endpoints of this skeleton (in this case there are four of them) using Open CV, if applicable.

Efficiency is important because I am analyzing several of them in real time from a video stream and have to do many other things at the same time.

(Note, I'm sorry that the screenshot above is the size of artifacts, but this is with the 8-linked skeleton I'm working with.)

Answer 1

Given your tags of your questions and answers in your profile, I'm going to assume that you want to implement C ++. When skeletonizing an object, the object must have a thickness of 1 pixel. Therefore, one thing I could suggest is to find those pixels that are not zero in your image, and then search in the 8-connected neighborhoods surrounding that pixel, and count those pixels that are not zero. If the counter is only 2, then this is a candidate for the end point of the skeleton. Notice that I will also ignore the border so that we do not go beyond. If the number is 1, it is a noisy isolated pixel, so we must ignore it. If it is 3 or more, it means that you are studying a part of the skeleton either at the point of the skeleton, or you are at the point where several lines are connected together, so this also should not be the end point.

I honestly can't think of any algorithm other than checking all the skeleton pixels for this criterion .... so the complexity will be O(mn) , where m and n are the rows and columns of your image. For each pixel in your image, checking the neighborhood of 8 pixels takes a constant time, and this will be the same for all the pixels of the skeleton that you are checking. However, this will certainly be sublinear, since most of your pixels will be 0 in your image, so checking for a neighborhood of 8 pixels will not occur most of the time.

So this is what I would like to try, assuming your image is stored in a cv::Mat structure called im , this is a single-channel (grayscale) image and is of type uchar . I am also going to save the coordinates where the end points of the skeleton are in type std::vector . Each time we find a skeleton point, we add two integers to it - a row and a column, where we find the end point of the skeleton.

 // 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); } } } 

If you want to show the coordinates when you're done, just check every pair of elements in this vector:

 for (int i = 0; i < coords.size() / 2; i++) cout << "(" << coords.at(2*i) << "," coords.at(2*i+1) << ")\n"; 

---

To be complete, a Python implementation is also implemented here. I use some of the numpy functions to make this easier for myself. Assuming your image is stored in img , which is also a grayscale image, and importing the OpenCV and numpy library (i.e. import cv2 , import numpy as np ), this is equivalent 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])) # Cast to int to index into image col_neigh = col_neigh.astype('int') row_neigh = row_neigh.astype('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)) 

To show the coordinates of the endpoints, you can do:

 print "".join(["(" + str(r) + "," + str(c) + ")\n" for (r,c) in skel_coords]) 

---

Minor note: This code is not verified. I do not have C ++ OpenCV installed on this computer, so hopefully what I wrote will work. If it does not compile, you can, of course, translate what I did into the correct syntax. Good luck

Answer 2

A little late, but it can be useful for people!

There you can do the same as @rayryeng, but with built-in openCV features! This makes it much smaller and probably faster (especially with Python, if you use it like me!) This is the same solution as this one .

Basically, we are trying to find non-zero pixels with one non-zero neighbor. So, we use openCV, built into the filter2D function, to drill the skeleton image with the custom kernel that we do. I just found out about convolution and kernels, and this page is really useful for explaining what these things mean.

So which kernel will work? What about

 [[1, 1,1], [1,10,1], [1, 1,1]]? 

Then, after applying this kernel, any pixel with a value of 11 is the one we want!

Here is what I use:

 def skeleton_endpoints(skel): # make out input nice, possibly necessary skel = skel.copy() skel[skel!=0] = 1 skel = np.uint8(skel) # apply the convolution kernel = np.uint8([[1, 1, 1], [1, 10, 1], [1, 1, 1]]) src_depth = -1 filtered = cv2.filter2D(skel,src_depth,kernel) # now look through to find the value of 11 # this returns a mask of the endpoints, but if you just want the coordinates, you could simply return np.where(filtered==11) out = np.zeros_like(skel) out[np.where(filtered==11)] = 1 return out 

Hope this helps!