From 8-connected to 4-connected lines

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-24T17:24:27-07:00

fmw42 wrote:Have tried comparing the output when using the kernel then its rotated version vs using the rotated kernel first and then the unrotated
the results WILL be different, as it will determine WHICH pixel is added. Remember multiple kernels are normally handles as if two separate operations.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
fmw42
Posts: 25656
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: From 8-connected to 4-connected lines

Post by fmw42 » 2012-06-24T17:24:54-07:00

To check if the 2x2 blocks are gone I use -morphology hmt '2x2:1,1,1,1' and make sure there is no white pixels in the result (obs: HMT reports some boundary pixels as a hit - due to mirror padding?).
I am not positive, but -morphology may be sensitive to the -virtual-pixel setting which defaults to edge (repeat what is on the border) not mirror. But you can set it to black or white as desired or any of the other options. Anthony should be able to comment of the use of -virtual-pixel with -morphology.

see
convert -list virtual-pixel

or

http://www.imagemagick.org/script/comma ... tual-pixel

User avatar
fmw42
Posts: 25656
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: From 8-connected to 4-connected lines

Post by fmw42 » 2012-06-24T17:27:38-07:00

anthony wrote:
fmw42 wrote:Have tried comparing the output when using the kernel then its rotated version vs using the rotated kernel first and then the unrotated
the results WILL be different, as it will determine WHICH pixel is added. Remember multiple kernels are normally handles as if two separate operations.

My quote was Have you tried ...

I was suspecting just what Anthony confirmed.

I edited my earlier post to correct the question.

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-24T17:30:34-07:00

fmw42 wrote:
I am not positive, but -morphology may be sensitive to the -virtual-pixel setting which defaults to edge (repeat what is on the border) not mirror. But you can set it to black or white as desired or any of the other options. Anthony should be able to comment of the use of -virtual-pixel with -morphology.
Yes it is. I'd probably use -virtual-pixel white. to surround the image with virtual white pixels. That should make the lines always join edges by single pixel connections (never two pixels at edge).
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

alosca
Posts: 52
Joined: 2010-03-04T17:54:57-07:00
Authentication code: 8675308
Location: Pasadena, California

Re: From 8-connected to 4-connected lines

Post by alosca » 2012-06-25T12:11:17-07:00

Even after filling the V to get full T there are situations where a 2x2 block is still present as it is shown in the example below (crop from the 8to4 image above posted by Fred). So, I think there is more to it than closing the V. When I run in a large image there are lots of these blocks.
Any suggestions? Would you be willing to post a full command line where the conversion works as expected, in case you already know how to do it?

Edited: the far right image below shows the pixel (black circle) I believe should be removed. Is this necessary to claim we have a 4-connected skeleton line?

Image Image Image
Last edited by alosca on 2012-06-25T16:26:23-07:00, edited 1 time in total.

User avatar
fmw42
Posts: 25656
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: From 8-connected to 4-connected lines

Post by fmw42 » 2012-06-25T13:20:17-07:00

The edge effects can probably be fixed with the correct choice of -virtual-pixel. I don't see why the rest is not correct. Please show us what you think is the correct result (by editing your example above, if necessary).

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-25T16:30:41-07:00

alosca wrote:Even after filling the V to get full T there are situations where a 2x2 block is still present as it is shown in the example below (crop from the 8to4 image above posted by Fred). So, I think there is more to it than closing the V. When I run in a large image there are lots of these blocks.
yes I see, but that is an artefact of using 2x2 diagonal detection. No matter how you arrange the origin between the 2, 90 degree rotated kernels you will get this problem at some orientation.

So don't use 2x2 kernels.

Look for V's first,

Code: Select all

 '3>: -,0,-   
      1,-,1
      0,1,0'
but then look for diagonals

Code: Select all

 '3>: -,0,0   
      1,-,0
      0,1,-'
The top right corner, may also need to be a don't care ('-')

That should do the task.

Did you try the built-in 'diagonal kernels'? It should be equivalent to the last but using 8 kernels (2 X rotated kernels) instead of 4.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

alosca
Posts: 52
Joined: 2010-03-04T17:54:57-07:00
Authentication code: 8675308
Location: Pasadena, California

Re: From 8-connected to 4-connected lines

Post by alosca » 2012-06-25T16:35:40-07:00

Thanks for the info on virtual-pixel. I will experiment with it. By the way, it is not that the boundaries are not properly 4-connected but HMT was reporting these 2x2 blocks on the boundaries when in fact none where shown on the processed image.

I edited my previous post. Please check it. You asked me the right question: do the 2x2 blocks I have been mentioning disqualify the results as truly 4-conn lines? Maybe not! But if I could I certainly would opt to have results without these extra pixels (again, marked with a black disk above). It seems they are not necessary at all to define the line 4-connectivity.

alosca
Posts: 52
Joined: 2010-03-04T17:54:57-07:00
Authentication code: 8675308
Location: Pasadena, California

Re: From 8-connected to 4-connected lines

Post by alosca » 2012-06-25T16:46:32-07:00

anthony wrote:
alosca wrote:Even after filling the V to get full T there are situations where a 2x2 block is still present as it is shown in the example below (crop from the 8to4 image above posted by Fred). So, I think there is more to it than closing the V. When I run in a large image there are lots of these blocks.
yes I see, but that is an artefact of using 2x2 diagonal detection. No matter how you arrange the origin between the 2, 90 degree rotated kernels you will get this problem at some orientation.
The result above is after the 3x3 kernel that Fred showed on his post after investigating how it was done in ImageJ, not the 2x2 that I was advocating for. I agree, the problem will persist no matter how I place the origin.

I have tried the diagonals at the beginning and if I recall correctly they were not helpful. I think the steps to take are:

1 - Fill the V's tp get full T's
2 - Use the 3x3 rotated kernels Fred posted or you posted (they are the same, I think)
3 - Somehow remove these 2x2 blocks if *really necessary* - I might be asking too much but it seems to me they have no place in 4-connectivity.

I will do another round of tests and report back.

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-25T17:18:02-07:00

alosca wrote:Thanks for the info on virtual-pixel. I will experiment with it. By the way, it is not that the boundaries are not properly 4-connected but HMT was reporting these 2x2 blocks on the boundaries when in fact none where shown on the processed image.
Not their are two styles of handling multi-kernel HMT, Thining, and Thickening.
HMT will return, Any pixel that will match any of the kernels. That is you will get a 'merger' of all the kernel results.
However by default thining and thickening, will apply each of the kernels to the image in sequence. that is the next kernel will be applied to the results of the previous kernel.

The result is that multiple pixels may be added or removed by thicken, thin, where HMT only shows one set of pixels.

Typically this is faster and desirable, so that is what IM does. You can however set a morphology 'compose' method, that if set will get IM to collect all the matches first, then thicken/thin, as appropriate.

I am not certain if this is -define morphology:compose darken or if it is lighten. Though I did try to describe it in...
Thinning Style - Sequential or Simultaneous
http://www.imagemagick.org/Usage/morpho ... ning_style
I only just edited this, to try and better describe the effects, so it make take a while to appear.
Old link (before edits) is
http://www.imagemagick.org/Usage/morpho ... ing_darken
You asked me the right question: do the 2x2 blocks I have been mentioning disqualify the results as truly 4-conn lines? Maybe not! But if I could I certainly would opt to have results without these extra pixels (again, marked with a black disk above). It seems they are not necessary at all to define the line 4-connectivity.
Actually they don't. ANY solid shape is 4-connected. And a general thicken will ensure 4-connectedness.
What you want in minimal 4-connectedness.

NOTE there is situations where 2x2 blocks are sometimes desirable in a minimal 4-connected lines,
For example...

Code: Select all

    o
    o
 oooo
   oooo
   o
   o
This will likely not be a problem, as the original thinning probably converted that situation to another equivalent form, of branching connections.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-25T17:23:52-07:00

What do you get if you use a 4-connected skeleton kernel set on the 2x2 blocks?
http://www.imagemagick.org/Usage/morphology/#skeleton
Specifically, skeleton:3 kernel set which I regard as the best. (though is not the default in IM as it was found later)

Does it thin those blocks?
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

alosca
Posts: 52
Joined: 2010-03-04T17:54:57-07:00
Authentication code: 8675308
Location: Pasadena, California

Re: From 8-connected to 4-connected lines

Post by alosca » 2012-06-26T01:41:45-07:00

anthony wrote:What do you get if you use a 4-connected skeleton kernel set on the 2x2 blocks?
http://www.imagemagick.org/Usage/morphology/#skeleton
Specifically, skeleton:3 kernel set which I regard as the best. (though is not the default in IM as it was found later)
Does it thin those blocks?
Yes, the 2x2 blocks are gone after thinning with Skeleton:3,

Code: Select all

convert result_2_8to4.pgm -morphology thinning skeleton:3 sk3.pgm
lines in sk3.pgm have minimal 4-connectivity.

User avatar
fmw42
Posts: 25656
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: From 8-connected to 4-connected lines

Post by fmw42 » 2012-06-26T10:01:48-07:00

If this is resolved, please post the full command line to go from 8-connected outline to 4-connected outline. Anthony, may want to add this to his examples page on morphology. If not, I am still interested in the full solution.

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: From 8-connected to 4-connected lines

Post by anthony » 2012-06-26T16:29:15-07:00

Ditto, the final full example it is a good thing to add.

Though as mentioned skeleton 3 is a very heavy 12 kernel set. But it probably only need applying once.

The final thing that would need to be watched is lines migrating across the display when switching back and forth between 4 and 8 connectedness.

ASIDE: the skeleton kernels that are defined can not only be used for thinning but also for thickening to generate SKIZ (skeletons of the background), EG: expanding objects into zones of influence, which seems to be what your examples show (inverted).
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

alosca
Posts: 52
Joined: 2010-03-04T17:54:57-07:00
Authentication code: 8675308
Location: Pasadena, California

Re: From 8-connected to 4-connected lines

Post by alosca » 2012-06-26T21:04:59-07:00

I will put a final example shortly with as few operations as possible. I was hoping to use something less expensive than Skeleton:3 as it seems only a few iterations are necessary to get the desired result (I am not sure if only because this is a small example).

convert result_2_8to4.pgm -verbose -morphology thinning skeleton:3 nada.pgm
Thinning:1.0 #1 => Changed 2 (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)

Post Reply