Page 1 of 1

thinning, skeleton:1 (bug ?)

Posted: 2010-12-03T02:40:06-07:00
by alosca
I have found differences in results when performing the following thinning operations on a B&W image:

convert img.pgm -morphology Thinning:-1 'Skeleton:1;Corners' thin.pgm
convert thin.pgm -morphology Thinning:-1 'LineEnds:-1;Peaks:1.5' -depth 1 result_1.pgm

and combining both thinnings in a single call

convert img.pgm -morphology Thinning:-1 'Skeleton:1;Corners;LineEnds:-1;Peaks:1.5' -depth 1 result_2.pgm

result_1 (wrong) has a dangling line not present in result_2 (what i think it is the right solution) but both were constructed using the same operations.
Would this be a bug ? I only use two calls of convert because I need to save both thin.pgm and result_1.pgm as shown above (any way I can save both files within a single call of convert?).

here are the images (in png format), from left to right, img.pgm, result_1, result_2:

Image Image Image

if I use Skeleton:2 instead all works well. is there a reason to prefer 'Skeleton:1;Corners' over 'Skeleton:2' ?
At the end I want 8-connected lines, no corners, no 2x2 blocks.

Version: ImageMagick 6.6.3-8 2010-08-21 Q16 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2010 ImageMagick Studio LLC
Features: OpenMP

- alex

Re: thinning, skeleton:1 (bug ?)

Posted: 2010-12-05T23:50:49-07:00
by anthony
When thinning down to a skeleton I have mentioned quite a number of times that the operations is 'fragile' which means if you re-order the kernels you get different results. Many research articles and morphology tutorials mention this fact!

Basically generating skeletons by thinning will get you connected skeleton, that will be close to the center lines of the ridges, But it may not be the exact centerline.

If you really want perfect center-lines or 'top of ridge' what you need is a morphological skeleton. A couple of methods has only been touched on the very last section of the morphology page, and is closely related to using 'distance gradients' Some kernels have been provided for this purpose, in the form of Ridges and Ridges:2. I am trying to find out other methods of morphological skeleton generation (and "medial axis transform" or MAT). As well as methods of shape to MAT and its inverse Mat to shape.

Using "Skeleton:2" is perfectly fine if the results are what you want. As mentioned it will automatically thin diagonals done to an 8-connected line, where the original traditional "Skeleton" kernel set only reduces to a 4-connected zig-zag diagonal lines.

The ONLY reason for doing a Skeleton of Skeleton:2 is that the resulting 4 connected lines, can be 'fast pruned' using the technique I have outlines but not completed in
http://www.imagemagick.org/Usage/morpho ... prune_fast
The only reason I have not completed is I have not found a nice way to flood fill from the set of discoved end points.

Remember punning lines is more costly, as it has to follow the lines removing them a few pixels at a time while processing the whole image each time. But skeleton thining can do a more direct removal of edges. The fast removal method would try to avoid whole image processing, and concentrate on the pruning using just specific neighbourhood of points last changed (a type of specialised flood fill). It may eventually become an alternative morphology operation.
is there a reason to prefer 'Skeleton:1;Corners' over 'Skeleton:2' ?
Corners are slightly more agressive version of the corner kernels in "Skeleton". If that agressivness (generating a 8 connected skeleton instead of a 4 connected one) is what you want, then just use "Skeleton:2" which includes those kernels in it already.

Result wise you may get a slightly different skeleton, but overall it will more than likely be slower with more wasted - no change steps being applied.

You may also like to try a "Edges;Corners" kernel set which is equivalent to "Skeleton:2" just with the kernels given a different order. I guarantee the result will again be very slightly different.

As I said skeletization by thinning is fragile! Different kernel orders generate very slight differences in results.
combining both thinnings in a single call
I do not recommend that at all!!! Doing both skeleton and line end pruning as a single kernel set does work, but again may result in IM applying more primitive iterations (most of them wasted), than when doing them separately. The only thing going for it is it is less options on the command line. But less options does not mean faster or better processing, just more convenient.

Remember a single primitive iteration is one kernel being applied once to the image. Having a set of 8 kernels in a set means ALL 8 kernels will be applied (8 primitives), at every iteration.
If ANY one kernel changed the image, then ALL 8 kernels will be applied again in the next cycle, in case that change allows other kernels to make more changes.

That means if you combine skeleton and pruning into one kernel set, then even when the skeleton aspect is finished its kernels will continue to be applied (and not do anything) while the pruning process continues (pruning usually takes longer).

Try a few runs with the debugging verbose enabled on on a small image and you will get an idea what is going on when multiple kernels are involved.

It is better to perform separate stages as separate steps.

The only reason skeleton uses 8 kernels as a single set is because they work together. Removing edges will generate corners, removing corners can generate more edges. One kernel may halt and not do anything for a few cycles, then start modifying the image again in later cycles.

Also see the 'half skeleton' results you get if the edges are applied as a separate step to the corners. See examples in
http://www.imagemagick.org/Usage/morphology/#edges
http://www.imagemagick.org/Usage/morphology/#corners
Basically doing a
-morphology Thinning:-1 Corners -morphology Thinning:-1 Edges
or even
-morphology Thinning:-1 Edges -morphology Thinning:-1 Corners
will generate other very different looking skeleton (possibly incomplete), though with the results less liking to be near the actual center-lines of the shapes; but the result will still equally valid as a thinned skeleton.


Note the Peaks:1.5 method probably, only requires one iteration to perform it task of removeing all single pixels. Once single pixels are removed there is no more need to repeat it. It does not need to iterate. Also single pixels do not effect either skeleton or pruning, though pruning may have a chance of removing the final pixel of a isolated line. As such it is probably better to apply it as a single once-off operation (without iteration) as a final step in the thinning process. Otherwise the kernel is being constantly applied without any chance of it doing anything!

ASIDE: It is good to know people are trying out the morphology routines. :-)

Re: thinning, skeleton:1 (bug ?)

Posted: 2010-12-06T14:24:14-07:00
by alosca
Thanks for the detailed answer and information. I now know that using multiple kernels in a single call to thinning is detrimental to speed. I will make changes accordingly. I will try the debugging you suggested to see what is happing under the hood.

I am satisfied with Skeleton:2 and will continue using it. Needless to say perfect center lines are always welcome and I will try and adopt them once they become available. I am also looking forward to adopt the fast pruning you mentioned. I suppose I can start with 4-connected lines via Skeleton:1, prune them, and then transform to 8-connected lines if this whole pipeline proves to be more robust and/or faster than Skeleton:2.

I am sure I am not the only one using your morphology suite. It does make a difference, specially when combined with all the other IM features.