OpenCV - Morphological Skeleton

Skeleton

In many computer vision applications we often have to deal with huge amounts of data: processing can therefore be slow and requires a lot of memory.
In order to achieve faster processing and a smaller memory footprint, we sometimes use a more compact representation called a skeleton.
A skeleton must preserve the structure of the shape but all redundant pixels should be removed.
Here is a skeleton of the letter "B":

In this article we will present how to compute a morphological skeleton with the library OpenCV.
The skeleton obtained is far from perfect but it is a really simple method compared to other existing algorithms.

Pseudocode

As described on Wikipedia, a morphological skeleton can be computed using only the two basic morphological operations: dilate and erode.
In pseudo code, the algorithm works as follow:

img = ...;
while (not_empty(img))
{
    skel = skel | (img & !open(img));
    img = erosion(img);
}

At each iteration the image is eroded again and the skeleton is refined by computing the union of the current erosion less the opening of this erosion. An opening is simply an erosion followed by a dilation.

Implementation

It's really straightforward, first load the image to process in grayscale and transform it to a binary image using thresholding:

cv::Mat img = cv::imread("O.png", 0);
cv::threshold(img, img, 127, 255, cv::THRESH_BINARY);

We now need an image to store the skeleton and also a temporary image in order to store intermediate computations in the loop. The skeleton image is filled with black at the beginning.

cv::Mat skel(img.size(), CV_8UC1, cv::Scalar(0));
cv::Mat temp(img.size(), CV_8UC1);

We have to declare the structuring element we will use for our morphological operations, here we use a 3x3 cross-shaped structure element (i.e. we use 4-connexity).

cv::Mat element = cv::getStructuringElement(cv::MORPH_CROSS, cv::Size(3, 3));

And now the core of the algorithm, the main loop. We need a boolean variable in order to check if there is at least one pixel remaining. Operations are done in-place when possible.

bool done;
do
{
  cv::morphologyEx(img, temp, cv::MORPH_OPEN, element);
  cv::bitwise_not(temp, temp);
  cv::bitwise_and(img, temp, temp);
  cv::bitwise_or(skel, temp, skel);
  cv::erode(img, img, element);
 
  double max;
  cv::minMaxLoc(img, 0, &max);
  done = (max == 0);
} while (!done);

The use of the minMaxLoc function deserves an explanation. We want to check if there is still at least one pixel in the image, unfortunately I have not found a function for this task in OpenCV, therefore I just check if the maximum value is 0. minMaxLoc stores the minimum value in the second parameter (ignored if NULL pointer) and the maximum in the third parameter. A short-circuit OR function would be nice for this task.

The loop is over, we have our skeleton, let's display it!

cv::imshow("Skeleton", skel);
cv::waitKey(0);

Results

On a big "O":

On the word "OpenCV":

Optimization

As discussed with Arthur Kalverboer in the comments below, it is possible to optimize the computation in several ways.

First of all we can notice we perform the open operation and just after we perform an erosion on the same image, but an opening is just an erosion followed by a dilation, so we can perform the erosion and save it to a new image eroded, and at the end of the loop we copy eroded to img.

The second optimization concerns the use of cv::minMaxLoc in order to check if an image still has white pixels, computing the norm (cv::norm) of the image is faster.
EDIT2: Abid Rahman told me the function 'cv::countNonZero' is even faster, I didn't know this function existed, thanks!

Finally the last optimization is to replace the and and not operations by a simple set difference operation (cv::subtract). This works because we only manipulate binary images.

Here is the updated code:

cv::threshold(img, img, 127, 255, cv::THRESH_BINARY); 
cv::Mat skel(img.size(), CV_8UC1, cv::Scalar(0));
cv::Mat temp;
cv::Mat eroded;
 
cv::Mat element = cv::getStructuringElement(cv::MORPH_CROSS, cv::Size(3, 3));
 
bool done;		
do
{
  cv::erode(img, eroded, element);
  cv::dilate(eroded, temp, element); // temp = open(img)
  cv::subtract(img, temp, temp);
  cv::bitwise_or(skel, temp, skel);
  eroded.copyTo(img);
 
  done = (cv::countNonZero(img) == 0);
} while (!done);

Also, don't forget to crop your images before processing. The two images I gave as examples are not cropped, cropping them (manually or using OpenCV) also improves execution time.

  • Arthur Kalverboer

    I have implemented the morphological skeleton with OpenCV and Python.
    It's a bit slow when applied to many images.
    I replaced the minMaxLoc with the Norm function using norm_type CV_C (max norm).

    • Arthur Kalverboer

      With the norm function it's about 20% faster. Nevertheless it takes about 0.2 sec CPU for one image.
      Also a mask (mask = img) for the And and Or functions will make it a little faster. I am looking further to make it faster.
      I am satisfied about the resulting skeletons. The results are better than the skeletons I got with an alternative method (using the functions DistTransform and AdaptiveThreshold).

      • Arthur Kalverboer

        Felix, thank for hint.
        I have implemented your suggestion to split the open-operation in erosion and dilation. As expected the program runs faster.
        Another hint to make the program runs faster is to replace the Not and And by one function Sub (subtract). In fact the temp-image is the difference between the img-image before and after the open operation. Because the images are boolean, this can be implemented by subtraction.
        The program now runs twice as fast as the original code.

        • Anonymous

          Indeed, thank you !
          I added the updated code in my article.

          I tried using masks, but my program was in fact slower :(.

          • Arthur Kalverboer

            Indeed the mask makes the program slower so I had removed the mask.
            I also tried the OpenCV function MorphologyEx with CV_MOP_TOPHAT. Tophat is the difference between the source before and after the open-operation. Just what we need. However this makes the program slower!!
            I read the updated code in your article and agree with that.

          • Andyvebby

            how to create morphological skeleton with IplImage?
            thank you

          • Phuong Hoang

            How can I know a line in an image continuous or decrete? To be specific, in an image I have handwritten character L. How can I know the L is continous line (actually 2 lines but i consider 1) or decrete? Thanks so much.

  • Abidrahman2

    Hi, thanks for the post.

    I implemented it in python. I tried your original code and optimized code. It doesn't make any difference in performance.

    But i changed minMaxLoc function with following method (which gave me 2-3X improvement in performance):

    size = number of pixels in img (ie rows*cols). (this need to be done at initial stage)

    # following lines instead of minMaxLoc
    zeros = size - cv::countNonZero(img)
    if zeros == size : # ie all pixels are zero
    done = True

    • Abidrahman2
    • Félix

      Thank you! I didn't know this function existed :).

    • Rubbic

      Hi,

      I implemented using Scala(similar to Java) there is a solution in python to remove small branches from the final image using : skimage.morphology.skeletonize(image) do you have any solution how can I implement it? how can I remove those branches to get the longest line remaining in my image?

      Thanks!

  • George Profenza

    This is very cool ! Nicely explained, thanks !

  • Pingback: OpenCV | Pearltrees()

  • harsh deshpande

    I am getting a blank image as the result.
    What's going wrong?

    • FelixAbecassis

      Hi, I just noticed that in the latest version of OpenCV I installed, a thresholding operation is necessary after loading in grayscale. I added the thresholding to the code, you should try again now.

      If it doesn't work, can you please tell me which image you used?

      • harsh deshpande

        Nope still doesn't work...
        I am using OpenCV 2.4.1 built using CMake.

        I used the opencv.png from your blog. If I use my own photo, the code simply hangs..

        • FelixAbecassis

          I've just tested my code on OpenCV 2.4.0 (release version) built with CMake, and it worked fine.
          So right now I don't know how to help you further, maybe you should try to save the image in a file instead of displaying it and check if it is still blank...

          • harsh deshpande

            OK thanks anyways for your help!

          • harsh deshpande

            Oops! my mistake! was displaying the wrong image..
            sorry about that... works perfectly fine!

  • Ed Burton

    Splendid blog post, very clear, very helpful, thank you.

    I'm trying to extract the topology of photographed line drawings. I'm getting lots of gaps appearing in the skeletons produced by this algorithm. Does it look like I've implemented it correctly and that the gaps are an inevitable feature of this method? If so then any advice how to extract a skeleton that preserves the exact topology of the input gratefully received (I've also implemented http://jeff.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html but it's rather slow)

  • François Pinard

    Bonjour Félix !

    J'aimerais faire fonctionner votre code, cependant j'obtiens systématiquement le message d'erreur "XXXXX (threshold, erode, morphologyEx, etc. !) n'appartient pas au groupe 'cv' " ... Je me trompe peut-être dans les include.

    Sauriez-vous d'où cela peut provenir ?
    Merci par avance.
    F. Pinard

    • François Pinard

      PS : J'utilise OpenCV 2.3.5 et Visual Studio 2008.

      • FelixAbecassis

        Bonjour, oui cela ressemble à un problème d'include des headers d'OpenCV.
        #include devrait suffire.

  • Totally_Novice

    I got a strange image after run the program.
    What's going wrong?

    • Totally_Novice

      PS : I use VC++6.0 with opencv1.0

  • Prasanna S

    Hey Felix,

    I need a bit of clarification. You did a simple threshold before you began skeletonising. I just wanted to know that whether other thresholding methods(adaptive threshold,Otsu's method) can play a role on the output we get.

    Thanks,

    Regards,
    Prasanna S

  • Pingback: cnblogs: OpenCV学习(19) 细化算法(7) – 迈克老狼2012 易站工作室 | 易站工作室()

  • Niaz Mohammad

    wondering could it be done with continuous video feed images? if so, please describe in short how to do so. Thanks

  • Eshan Gray

    Can i ask how would you change the code to allow for 8-connectivity instead?

  • Rubbic

    Nice! I have a question, how can I remove small branches after this? There is a solution in scikit-image for python but I am doing Java! Would you please help me on that?

  • Pingback: OpenCV: Problem at creating a Skeleton of Lines - DL-UAT()

  • Malik Faiq

    Throws exception on bitwise_or C:buildsmaster_PackSlave-win32-vc12-staticopencvmodulescoresrcarithm.cpp:1573: error: (-209) The operation is neither 'array op array' (where arrays have the same size and type), nor 'array op scalar', nor 'scalar op array' in function cv::binary_op

  • Microzak

    Hello, I'm trying to implement this algorithm in java but I'm not able to convert the with minMaxLoc, can anybody help me?

  • Arnold Tai

    Thank you!!!
    The pseudocode is really helpful.

  • Howard X. Zang

    (img & !open(img))
    for this step, we can use the TOPHAT operation.
    cv::morphologyEx(img, temp, cv::MORPH_TOPHAT, element);

  • Pingback: Skeletonization using OpenCV-Python - Desktop Background HD()