0
$\begingroup$

What will be the output of skeletonization of a circle? In my class my instructor said that it will be a single dot in the center but what I found on the Internet was a cross. I discussed with a friend of mine, and he said that the reason it will be a dot is that a smaller circle can not fit a larger circle in such a way that it touches more than one point and is not out of the boundary of the original signal. Although I beg to differ because of the equation of finding the length of the arc. Can anyone confirm the output of skeletonization of a circle with proper reasoning?

$\endgroup$
1
$\begingroup$

The question here is: "The output of which skeletonisation"? The topological or the morphological?

It seems from what you mention on your discussion with your friend that you are referring to the morphological skeleton.

In the case of the topological skeleton, the answer is trivial. Given that the topological skeleton is the set of all foreground pixels that are at maximal distances from the boundaries of the image and the definition of the disk (all points in space that are at most at distance $R$ from the centre of the disk), the skeleton of a disk (a circle that is filled*) is the single pixel at its centre.

The morphological skeleton works slightly differently. It is based on the morphological operations of erosion followed by opening, both of which are using a structuring element.

Roughly speaking, you can think of erosion followed by opening as progressively "pealing off" boundaries from a region, until there is nothing left to peal off. (This is not entirely accurate and I will return to it further below).

Here for example is some random disc I placed on a dark background...

enter image description here

...and here are a few of the first iterations of morphological skeletonisation:

enter image description here

enter image description here

Where it is clear that the disc is shrinking and this looks like going towards our previous thinking regarding the topological skeleton, where eventually, all that is left is going to be a single pixel at the centre.

However, we can already see that this shape does not look so much like a circle now, it's kind of pointy and also, if we continue this process, something odd starts happening (in my case after about iteration 12 or 13):

enter image description here

enter image description here

Ultimately, what is left behind is a cross.

Where is this cross coming from?

This is a byproduct of two things:

  1. The fact that the structuring element is discrete and its curvature at different iteration levels does not match exactly the curvature of the given disc. To understand this better, consider this extreme example that could well be showing a "disc" or a "diamond" or a square rotated 45 degrees:

$$\begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 0\\ \end{matrix}$$

(In other words, the disc is not exactly a disc and it is not strictly enforcing that rule of "all pixels at distance $R$" strictly to all of its pixels. It is more like, pixels less than that distance in which case, its discrete boundary "plays" in and out of the actual continuous boundary.)

  1. The way that the "pealing off" takes place. In fact, the morphological skeleton is the union of $n$ partial skeletons. Each partial skeleton of some image $I$ via a structuring element $B$ is obtained via:

$$ S_n(I) = (I \ominus nB) - (I \ominus nB) \circ B $$

Where $I$ is the image (here, our bigger disc), $n$ is the iteration level, $B$ is the structuring element, $\ominus$ represents erosion, $\circ$ represents dilation and $nB$ is interpreted as "$n$ applications of erosion". Also notice here that the $-$ operator has the lowest precedence. So you don't evaluate it until you have evaluated both the left-hand and right-hand expressions.

The "pealing off" is achieved by that $-$ operator in the middle but there is a little bit more into it. A partial skeleton is the difference (as in set difference) between the "eroded" $I$mage by $B$ and the "dilation of that eroded $I$mage" by $B$. Which is basically like the difference between a shrunk image and the shrunk image enlarged. This difference is $\emptyset$ for the first few iterations but as the disc gets smaller and smaller and now the differences in the boundary start becoming more pronounced, the shrunk and shrunk-enlarged images start differing by 1 pixel (exactly at the peaks as you can see from the matrix example above). Since the skeleton is the union of the partial skeletons and each partial skeleton will have 4 pixels difference to its previous one, what "survives" throughout the iteration levels is that cross.

To understand better why I am referring to erosion and dilation as shrinking and enlarging and their difference as some "boundary", you need to understand the effect of those particular operations in detail. To do this, in addition to the excellent wikipedia articles, you can have a look at Gonzalez & Wood's "Digital Image Processing". In my second edition, chapter 9 is devoted to morphological image processing (and is totally worth a complete thorough reading) and the morphological skeletons are presented in pages 543-545.

Hope this helps.

*: The topological skeleton of a circle is a circle.

$\endgroup$
  • $\begingroup$ Great answer! There are lots of different skeletonization algorithms, they all produce something different for a circle, and few of them will yield a single dot as expected in the continuous domain. $\endgroup$ – Cris Luengo Dec 29 '18 at 23:49
  • $\begingroup$ @CrisLuengo Thank you. My personal default is the one based on distance but yes, there are definitely different views on skeletonisation and they produce slightly different results, the devil is in the detail. All the best. $\endgroup$ – A_A Jan 7 at 8:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.