Thinning to truly 8-connected skeletons

[alosca]

I have been using -morphology Thinning:-1 Skeleton:2 to create one pixel wide skeleton lines from binary images. Works great! The results are *almost* 8-connected skeletons as T junctions still have the junction point turned on - we need them off to make truly 8-conn lines. I have also tried Thinning with Diagonals and Corners afterwards as explained in

http://www.imagemagick.org/Usage/morpho ... r_skeleton

but to no avail. It seems the only problem is with T junctions, all the rest conform to 8-conn topology.

Is there an alternative to get truly 8-connected skeletons?

An option is to detect the T junction points using hit or miss and then subtract (xor) them from the skeleton:2 result but I might just be missing something already built in that I can take advantage of.

Version: ImageMagick 6.7.1-0 2011-07-26 Q16 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2011 ImageMagick Studio LLC
Features: OpenMP OpenCL HDRI

Thanks in advance.
- Alex.

[anthony]

You can thin using the specific T-junction kernel (rotated in 90 degree increments)
'LineJunctions:3>'

http://www.imagemagick.org/Usage/morpho ... ejunctions


Note that Thinning is essentially Hit-n-Miss (HMT) matching removal, just as Thickening is HMT addition.

Warning Line Juntions contain no background matching pixels, as such it is really simply an erode, and as such can not be used directly for skeleton generation.

If you come up with a skeleton kernel set variation that you find interesting, please let me know!

[alosca]

Thanks for the tip. It couldn't be simpler!

I wonder why Skeleton:2 does not include this T junction kernel so thinning can produce a truly 8-connected skeleton, as it is suggested in

http://www.imagemagick.org/Usage/morpho ... g_skeleton

But maybe using -morphology Thinning 'LineJunctions:3>' after Skeleton:2 is cheaper than adding a 9th kernel to the skeleton:2 set of 8 kernels (?).

If not there yet, I think a combination of 3x3 kernels to add (Thicken) pixels would be beneficial.
I have in mind the following 12 kernels:

kernel2image.sh -20.2 -ml '' -mt x1 '3@: 0,0,0 1,0,1 0,0,0 ' gap1.gif
kernel2image.sh -20.2 -ml '' -mt x1 '3@: 0,1,0 0,0,0 0,0,1 ' gap2.gif

I would use these to fill one pixel gaps in my 8-connected skeletons.

[anthony]

But maybe using -morphology Thinning 'LineJunctions:3>' after Skeleton:2 is cheaper than adding a 9th kernel to the skeleton:2 set of 8 kernels (?).

It would be cheaper to run at the end, as it only needs to be done once.

Remember Every kernel in the skeleton set will be applied, and will continue to cycle until none of those kernels
make a match. Adding four more kernels means it will be 50% slower (12 kernels in stead of 8 per cycle).

If not there yet, I think a combination of 3x3 kernels to add (Thicken) pixels would be beneficial.
I have in mind the following 12 kernels:

kernel2image.sh -20.2 -ml '' -mt x1 '3@: 0,0,0 1,0,1 0,0,0 ' gap1.gif
kernel2image.sh -20.2 -ml '' -mt x1 '3@: 0,1,0 0,0,0 0,0,1 ' gap2.gif
I would use these to fill one pixel gaps in my 8-connected skeletons.

Seems like a very specific requirement, and you obviously got the hang of doing a DIY!


NOTE with a '@' (45 degree) rotation both your commands produce the same kernel set, just with a slightly different order. You can see this if you check the kernels using -define showkernel=1

However this will miss any missing 3 or 4 line junction!

Better idea. dilate the skeletion image slightly, then thin it!

NOTE; the only way a skeleton could get a gap like this using skeleton functions, is if the original shape had such a gap, in which case dilating the original shape before generating the skeleton would also so the job. You could also simplify the skeleton by opening/closing or smoothing the original shape before generating the skeleton.

[alosca]

I mistakenly thought was a 9th kernel, but as you said, another 4 kernels to the already 8 in skeleton:2, 50% more expensive. Indeed, it would be cheaper to run LineJunctions:3> at the end, as it only needs to be done once.

I think the kernels in gap1.gif and gap2.gif pictures are all distinct, no?

I will look into the missing 3 and 4 line junctions. I can't quite see right now which 3x3 kernels I am missing. Which ones you have in mind?

As far as I can tell, smoothing and dilating with small kernels do not actually work very well in my case as they start to make round corners where sharp corners existed. I want to keep those as sharp as possible. Also, 4 way junctions start to appear as in the plus sign +, something I want to avoid as much as possible because it is not representative of the true geometry I am trying to capture from the images.

[anthony]

I mistakenly thought was a 9th kernel, but as you said, another 4 kernels to the already 8 in skeleton:2, 50% more expensive. Indeed, it would be cheaper to run LineJunctions:3> at the end, as it only needs to be done once.

Not to mention that as a 'erode' rather than a true hit-n-miss, a line junction kernel would result in a eroded skeleton! Basically on the first run, it would remove just about every internal pixel in the original shape, before any skeleton is even produced!

I think the kernels in gap1.gif and gap2.gif pictures are all distinct, no?

Opps, yes you are right. They are.

Hmmm also note that your kernel (to find knight-move gaps)

Code: Select all

   '3@: 0,1,0  0,0,0  0,0,1 '

would actually match two pixels in the gap between the two on pixels, making a 4-connected skeleton. As such a extra thinning step may be needed to remove one of those pixels to re-form the 8-connected skeleton. however reducing this to just 90-degree rotates will remove that second match...

Code: Select all

   '3>: 0,1,0  0,0,0  0,0,1 '

I will look into the missing 3 and 4 line junctions. I can't quite see right now which 3x3 kernels I am missing. Which ones you have in mind?

I would look at adding some 'does not matter' entries to the kernels, so that 3 and 4 line junctions are also found.
For example...

Code: Select all

   '3@: 0,-,0  1,0,1  0,0,0 '

will find all T-junctions (orthogonal and diagonal) as well as direct line gaps. But then the rotations will exand to 8 kernels instead of 4 kernels.
Alternative making the kernal symmetrical again

Code: Select all

  '3@: 0,-,0 1,0,1 0,-,0 '

will find t-junctions as well as X and + junctions.
For finding 'knight-move' gaps and Y junctions try...

Code: Select all

 '3>: 0,1,0 -,0,0 -,0,1 ' 

I have not actually tried these, but they should work.

As far as I can tell, smoothing and dilating with small kernels do not actually work very well in my case as they start to make round corners where sharp corners existed. I want to keep those as sharp as possible. Also, 4 way junctions start to appear as in the plus sign +, something I want to avoid as much as possible because it is not representative of the true geometry I am trying to capture from the images.

How would you replace a + junction in that case. As a once pixel loop? or slightly larger --'|,-- type arrangement?
Similarly you may need to consider replacing X junctions in some way too.

I am very interested in this discussion, and may make a good addition to thinning skeletons in IM Examples.

May I ask what the skeletons are for?

[alosca]

Very very nice! Thanks for the suggestions.

Hmmm also note that your kernel (to find knight-move gaps)

Code: Select all

'3@: 0,1,0  0,0,0  0,0,1 '

would actually match two pixels in the gap between the two on pixels, making a 4-connected skeleton.

I am not sure I got this, I think I might be missing some understanding on how IM runs each kernel in a set. In my understanding, only the central pixel in the 45o degree set above would be turned on by a Thicken. What am I missing?

The kernels

Code: Select all

'3@: 0,-,0 1,0,1 0,-,0 '
'3>: 0,1,0 -,0,0 -,0,1 ' 

are excellent generalizations to detect one pixel gaps although I don't want to turn on the junction on the T's - I could probably run these more general kernels and then remove the T junctions as explained earlier in a last pass. If indeed we are not missing some of the kernels present in '3@: 0,1,0 0,0,0 0,0,1 ' then these should be sufficient to turn on one pixel gaps.

I currently do not replace + junctions if they are unavoidable but I try not to create unreal ones when using the morphological transformations. You got it right: I want to space the junctions a few pixels apart, so instead of + we want to have

___|__
|

My application is in biology, more specifically, in segmentation of plant cells whose walls are marked by proteins and visible in one channel on a possibly multichannel image. If interested, I can post an example picture.

[anthony]

Hmmm also note that your kernel (to find knight-move gaps)

Code: Select all

'3@: 0,1,0  0,0,0  0,0,1 '

would actually match two pixels in the gap between the two on pixels, making a 4-connected skeleton.

I am not sure I got this, I think I might be missing some understanding on how IM runs each kernel in a set. In my understanding, only the central pixel in the 45o degree set above would be turned on by a Thicken. What am I missing?

One kernel will match in one position, turning on one pixel, a different rotated kernel will match in another position, turning on a different pixel. Remember you have 8 kernels. So say you have a gap like __ ---- one kernel will add a pixel at the upper position a different kernel will add on at the lower position.

Hmmm hold. I was wrong. Hit and Miss will match two pixels (one from two different kernels), but as Thinning/Thickening uses kernels in a iterative manner, that is the next kernel will be applied to image modified by the previous kernel. As such as soon as one kernel finds one pixel, the other position will no longer be a HMT match.

To get both HMT pixels to appear, I would have to modify the kernel composition so as to do 'union' addition of all matches by all kernels against the original image. EG I would need to add -define morphology:compose=Lighten to turn on a union of HMT thickening. EG: Apply Thickening of each kernel against only the original image, then 'lighten' all the results together.
http://www.imagemagick.org/Usage/morpho ... el_compose

This is a method that I have not explained very well in IM examples (no actual examples either). I did not even think of using 'union' (lighten compose) for thicking, only 'intersection' (compose darken) for thinning.
http://www.imagemagick.org/Usage/morpho ... ing_darken

My application is in biology, more specifically, in segmentation of plant cells whose walls are marked by proteins and visible in one channel on a possibly multichannel image. If interested, I can post an example picture.

I see. a small example image would be good, though it is not necessary. I just wondered what your application was.

[alosca]

I am confused: isn't the pixel under the origin of the kernel the only pixel that gets changed after a morphological operation? The origin travels over all pixels in the image and perform convolution only where there is an absolute match with the kernel? If so, why the need for union addition as you explained?

I am not sure but I think you don' always want to match all kernels against the original image. In our case of filling one pixel gaps, for example, all kernels are ORed, i.e., as soon as a match is found there is no more need to test the remaining kernels on the set. This is because the kernels are mutually exclusive, no two kernels can happen at the same image location. If one kernel matches no other kernel in the set will match. You could reduce computation by halting as soon as one match occurs. Does it make sense?

Said that, I don't know if the same applies to all other possible morphological operations. Maybe only when applying mutually exclusive kernels ?! To be checked...

[alosca]

I confirmed: we need 45 degrees rotations, not only 90, to generate all kernels necessary to detect the gaps we are interested:

For knight-move gaps: 3@: 0,1,0 -,0,0 -,0,1;
For X,Y,-,T and their rotation variants: 3@: 0,-,0 1,0,1 0,-,0

A total of 12 kernels will do it:

kernel2image.sh -40.4 -ml '%[number]' -bc white -kc black,gray80 -mt x1 '3@: 0,1,0 -,0,0 -,0,1; 3@: 0,-,0 1,0,1 0,-,0 ' gap-kernels.gif

[anthony]

I am confused: isn't the pixel under the origin of the kernel the only pixel that gets changed after a morphological operation? The origin travels over all pixels in the image and perform convolution only where there is an absolute match with the kernel? If so, why the need for union addition as you explained?

If you ran a Hit and Miss, on a small 'knights move gap' then for one kernel you will get a match with one pixel (at the center) and for another kernel you will get a match at a different pixel.. For example.

Code: Select all

   .  .  .  .  .
   .  .  x  o  o
   o  o  x  .  .
   .  .  .  .  .

the . is background o an existing pixel. one of the 8 rotations will match when it is centered on one 'x' while a different kernel of those 8 rotations will match the other 'x'.

For a HMT transform the result will be just the two 'x's

But with a Thicken operation, one of the X's will match, and then the other X will not get matched because it is no longer a 'gap'. It was filled by a previous iteration of a different kernel.

However if you enable a 'lighten' composite or 'union' of all the images you would get by only applying each kernel only to the original image, then each kernel will not see the 'filled in pixels' so both pixels will gte matched, and merged together in the output.

I am not sure but I think you don' always want to match all kernels against the original image.

Fair enough. That the default is iterative in any case, so the first kernel that matches will prevent the other kernels from matching.

In our case of filling one pixel gaps, for example, all kernels are ORed, i.e., as soon as a match is found there is no more need to test the remaining kernels on the set. This is because the kernels are mutually exclusive, no two kernels can happen at the same image location. If one kernel matches no other kernel in the set will match. You could reduce computation by halting as soon as one match occurs. Does it make sense?

Well IM will still apply all kernels to every location. and repeat according to the number of times you request it to repeat (infinite times = -1) In the infinite case it will stop when no kernel made any change anywhere on the image.

Said that, I don't know if the same applies to all other possible morphological operations. Maybe only when applying mutually exclusive kernels ?! To be checked...

It doesn't in thinning for example you may get a whole series of matches due to iterations, however each match will be only by a different kernel. each kernel only applys to the 'current iteration' of the image as a whole, it does not see for example any change that it added to the previous row.

[alosca]

Got it! I don't know why but what I had in mind was that for every pixel in the image you apply all the kernels in the given set before moving to the next pixel. But in fact, you apply a kernel to the entire image and then repeat for every kernel in the sequence using either the original (non iterative mode) or the modified image from the previous iteration (iterative mode). I can see why these will give different results. And why the latter can be potentially more expensive than the former in certain cases. But all is working pretty well!

Many thanks for taking the time to explain and for the informative illustration.

[anthony]

The 'verbose' output of morphology was designed to be informative of exactly what steps morphology was applying. Which kernel, weather it is saved and results composited separately, or the result is just 'iterated to the next kernel.

It may actually be faster to apply each kernel image once at each location, which would have the same effect as the appropriate compositing operation, but that would only work when all kernels are actually the same size (due to pixels fetch and caching from the pixel buffers). However kernel sizes is not guaranteed and is not actually the case if you are doing two linear blurs in an iterative manor to mimic the action of a much larger 2-dimensional Gaussian blur.

This is why thinning to skeletons are so slow. Their is a lot of wasted processing, (which you can see if you watch the verbose output of the number of pixels that are actually modified!, particularly toward the end of the skeleton process.