From 8-connected to 4-connected lines

[anthony]

It is likely to only be a couple of kernels that need to be used.
As only a very specific condition (for the origins used in the 'thicken') would appear.

however the full example did not contain the thicken process you decided to use.

More than likely we can tweek the thicken to be more restrictive, so the number of overall passes through the image is less.

[alosca]

While preparing a final example I stumbled in the following apparently discrepancy, i.e., I ran exactly the same command on same images and obtain slightly different counts for "Changed", see asterisks below. Is this of concern?

bamboo [426] : convert 8conn.pgm -verbose -morphology thicken '3>:0,1,-,1,0,-,-,-,-' -morphology thinning skeleton:3 res.pgm
Thicken:1.0 #1 => Changed 6996 (re-iterate) *****
Thicken:1.1 #2 => Changed 5904 (re-iterate) *****
Thicken:1.2 #3 => Changed 0 (re-iterate)
Thicken:1.3 #4 => Changed 0 (done)
Thinning:1.0 #1 => Changed 111 (re-iterate)
Thinning:1.1 #2 => Changed 2 (re-iterate)
Thinning:1.2 #3 => Changed 19 (re-iterate)
Thinning:1.3 #4 => Changed 180 (re-iterate)
Thinning:1.4 #5 => Changed 14 (re-iterate)
Thinning:1.5 #6 => Changed 0 (re-iterate)
Thinning:1.6 #7 => Changed 1 (re-iterate)
Thinning:1.7 #8 => Changed 0 (re-iterate)
Thinning:1.8 #9 => Changed 0 (re-iterate)
Thinning:1.9 #10 => Changed 41 (re-iterate)
Thinning:1.10 #11 => Changed 0 (re-iterate)
Thinning:1.11 #12 => Changed 0 (done)
8conn.pgm=>res.pgm PGM 1959x996 1959x996+0+0 1-bit DirectClass 1.95MB 1.810u 0:00.289

bamboo [427] : convert 8conn.pgm -verbose -morphology thicken '3>:0,1,-,1,0,-,-,-,-' -morphology thinning skeleton:3 res.pgm
Thicken:1.0 #1 => Changed 7005 (re-iterate) *******
Thicken:1.1 #2 => Changed 5905 (re-iterate) ******
Thicken:1.2 #3 => Changed 0 (re-iterate)
Thicken:1.3 #4 => Changed 0 (done)
Thinning:1.0 #1 => Changed 111 (re-iterate)
Thinning:1.1 #2 => Changed 2 (re-iterate)
Thinning:1.2 #3 => Changed 19 (re-iterate)
Thinning:1.3 #4 => Changed 180 (re-iterate)
Thinning:1.4 #5 => Changed 14 (re-iterate)
Thinning:1.5 #6 => Changed 0 (re-iterate)
Thinning:1.6 #7 => Changed 1 (re-iterate)
Thinning:1.7 #8 => Changed 0 (re-iterate)
Thinning:1.8 #9 => Changed 0 (re-iterate)
Thinning:1.9 #10 => Changed 41 (re-iterate)
Thinning:1.10 #11 => Changed 0 (re-iterate)
Thinning:1.11 #12 => Changed 0 (done)
8conn.pgm=>res.pgm PGM 1959x996 1959x996+0+0 1-bit DirectClass 1.95MB 1.810u 0:00.299

[alosca]

Below is what I have found to work to obtain 4-connected lines from 8-connected lines:

Code: Select all

convert 8conn.png -verbose \
  -morphology thicken '3>:-,0,-,1,-,1,0,1,0' \  --- fill junction pixels by thickenning V's to get full T's
  -morphology thicken '3>:-,0,0,1,-,0,0,1,-' \  --- fill in diagonal pixels to obtain 4-connectivity
  -morphology thinning Skeleton:3 \   --- skeleton:3 to remove 2x2 filled blocks
  4conn.png

the output of this example is

Code: Select all

--- fill junction pixels by thickenning V's to get full T's
Thicken:1.0 #1 => Changed 4 (re-iterate)
Thicken:1.1 #2 => Changed 5 (re-iterate)
Thicken:1.2 #3 => Changed 5 (re-iterate)
Thicken:1.3 #4 => Changed 5 (done)
--- fill in diagonal pixels to obtain 4-connectivity
Thicken:1.0 #1 => Changed 375 (re-iterate)
Thicken:1.1 #2 => Changed 320 (re-iterate)
Thicken:1.2 #3 => Changed 0 (re-iterate)
Thicken:1.3 #4 => Changed 2 (done)
--- skeleton:3 to remove 2x2 filled blocks
Thinning:1.0 #1 => Changed 1 (re-iterate)
Thinning:1.1 #2 => Changed 0 (re-iterate)
Thinning:1.2 #3 => Changed 1 (re-iterate)
Thinning:1.3 #4 => Changed 0 (re-iterate)
Thinning:1.4 #5 => Changed 0 (re-iterate)
Thinning:1.5 #6 => Changed 0 (re-iterate)
Thinning:1.6 #7 => Changed 0 (re-iterate)
Thinning:1.7 #8 => Changed 0 (re-iterate)
Thinning:1.8 #9 => Changed 0 (re-iterate)
Thinning:1.9 #10 => Changed 0 (re-iterate)
Thinning:1.10 #11 => Changed 0 (re-iterate)
Thinning:1.11 #12 => Changed 0 (done)
8conn.png=>4conn.png PNG 224x215 224x215+0+0 8-bit PseudoClass 2c 0.060u 0:00.019

Here are the images used above

8-connectivity 4-connectivity

There should be a way to reduce the number of operations above but that pipeline seems to be sufficient to get the desired 4-connected lines.

[anthony]

A 'cut-n-paste' version of the commented command...

Code: Select all

convert 8-connectivity.png -verbose -virtual-pixel white \
  -print "Fill 'v' junctions to 't' junstions\n" \
  -morphology thicken '3>:-,0,-,1,-,1,0,1,0' \
  -print "Fill in diagonal pixels to obtain 4-connectivity\n" \
  -morphology thicken '3>:-,0,0,1,-,0,0,1,-' \
  -print "Use skeleton:3 to 'thin' 2x2 filled blocks\n" \
  -morphology thinning Skeleton:3 \
  4conn.png

But thank you for the example. Note I added the VP white, though it is not needed for this example.

We currently have a total of 4+4+12 kernel passes.
The skeleton kernel may possibly be reduced but we would need to examine the 2x2 blocks that were generated.
According to the verbose output there was 2 such 'thinnings' performed.

Were these at 'v' -> 't' junctions?

Also the second thicken (fill diagonal), should not need the 3rd and 4th kernel to thicken diagonal lines! And yet the the 4th kernel produces 2 such thickens. We will need to example those cases to determine why.

Perhaps it was these thickens that produces the 2 sets of 2x2 blocks that was later removed by the skeletion thin?

In any case total added pixels is... 716, followed by 2 removals.


Hmmm... My version on your image produced different results!

Fill 'v' junctions to 't' junstions
Thicken:1.0 #1 => Changed 4 (re-iterate)
Thicken:1.1 #2 => Changed 5 (re-iterate)
Thicken:1.2 #3 => Changed 5 (re-iterate)
Thicken:1.3 #4 => Changed 5 (done)
Fill in diagonal pixels to obtain 4-connectivity
Thicken:1.0 #1 => Changed 372 (re-iterate)
Thicken:1.1 #2 => Changed 319 (re-iterate)
Thicken:1.2 #3 => Changed 1 (re-iterate)
Thicken:1.3 #4 => Changed 3 (done)
Use skeleton:3 to 'thin' 2x2 filled blocks
Thinning:1.0 #1 => Changed 0 (re-iterate)
Thinning:1.1 #2 => Changed 0 (re-iterate)
Thinning:1.2 #3 => Changed 0 (re-iterate)
Thinning:1.3 #4 => Changed 0 (re-iterate)
Thinning:1.4 #5 => Changed 0 (re-iterate)
Thinning:1.5 #6 => Changed 0 (re-iterate)
Thinning:1.6 #7 => Changed 0 (re-iterate)
Thinning:1.7 #8 => Changed 0 (re-iterate)
Thinning:1.8 #9 => Changed 0 (re-iterate)
Thinning:1.9 #10 => Changed 1 (re-iterate)
Thinning:1.10 #11 => Changed 0 (re-iterate)
Thinning:1.11 #12 => Changed 0 (done)
8-connectivity.png=>4conn.png PNG 224x215 224x215+0+0 8-bit PseudoClass 2c 0.050u 0:00.030

Oh. A 'flicker_cmp' (Script download from http://www.imagemagick.org/Usage/scripts/flicker_cmp )
of the two images show 3 different 'edge effects' between your version and mine. Adding VP distorted the image less in two spots, though it removed a single isolated edge pixel on the bottom edge for the third 'edge effect'.

NOTE a flicker-cmp of the 8 image to the results show a distinct 1/2 pixel move of diagonal lines in a easterly direction. This is to be expected as part of the thicken process. If you also implement the reverse, I would ensure that that has the opposite preference.

I'll add these kernels as named kernels into IM (both IMv6 and IMv7) next time I get a chance to do some programming.

[alosca]

Were these at 'v' -> 't' junctions?

Perhaps it was these thickens that produces the 2 sets of 2x2 blocks that was later removed by the skeletion thin?

I can't tell without further analysis. And I suspect doing analysis based on a single example might not be conclusive to cover all possible cases. Maybe there is an algorithm out there that can do the conversion without having to resort to many kernel operations. I would need to investigate.

Would you have an idea why the 3x3 kernel Fred investigated was able to produce the 4-connected lines in ImageJ but not in IM? Maybe that can be a helpful hint.

I am still puzzled why running the same operations on the same input image produces different changes (as I reported earlier). Unless there is some random numbers involved, it doesn't make much sense to get different results. Do you get the exact same results as mine when you don't use a white VP?

Thanks for considering programming named kernels for this conversion.

[anthony]

The different checks depend on 'edge effect' (my enabling of Virtual pixels)
and on kernel order (which side of a diagonal pixels are added).

However I think most of the thining kernels are overkill, and 2 of the diagonal kernels should not be needed.
Why they were actually used... that is the question.

One test not done is the case of four lines coming together at a point, either as a 'plus' with the center missing' or as a cross. The later may actually produce a 3x3 block, if we are not careful.