From 8-connected to 4-connected lines

[alosca]

Hello,

Is there a quick way to convert 8-connected lines to 4-connected lines? I tried with Thicken, HMT, but to no avail. I have to transform a bunch of binary images containing 8-conn edges so I can use a program that only accepts 4-conn lines (connected components, not available yet on IM). An alternative is to thicken the 8-conn lines and then thin with Skeleton:1 or something similar to obtain the desired 4-conn lines. But if I can avoid this more expensive route, that would be much preferred. Any suggestions?

Thanks,
- Alex

[fmw42]

just a suggestion as I have not tested this, but depending upon your polarity try a 3x3 plus shape morphology open or close, e.g.

-morphology open (or close) plus:1

[alosca]

Many thanks for the suggestion. I tried plus and customised kernels but they didn't work. Here is a piece of an example image,

http://www.imagenoir.com/magick/result_2.png

I like to think that the right kernel + morphological operation will do it but I didn't come up with the right combination yet. I will need to take time to figured this out. Let me know if you have other suggestions. I will be happy to report here my findings.

[fmw42]

see diag at http://www.mathworks.com/help/toolbox/i ... morph.html, though it does not do what I thought, but perhaps is what you want. Perhaps it needs to be applied with all possible diagonals.

Search google and see if you can find anything else about 8-connected to 4-connected conversion.

http://www.dentistry.bham.ac.uk/landini ... tware.html. You could try these in ImageJ.

[anthony]

the problem with that page is that it does not actually list the HMT pattern kernels it uses to achieve the results described!


You probably need a 90-degree rotated variants (add a '>' flag).
'3>: 0,1,0 1,0,0 0,0,0'

Or even make it a rotated 2x2 kernel...

'2>:0,1 1,0'

You may like to add some don't care '-' elements to the array, for example for the 'other' corners of the search pattern.

Remember a Thicken kernel is just a HMT selection kernel that will add the difference between the lightest foreground and the darkest background pixels found. Typically HMT kernels use a don't care for the actual origin itself, so it can be used for 'thining' too.

You may like to try thickening using 'Corners' kernel instead -it uses a don't care for origin, so can be used for thickening too!
http://www.imagemagick.org/Usage/morphology/#corners
Ditto of the next set of 'Diagonals' Kernel.

And please report back what you find!

[fmw42]

Anthony,

What method are you suggesting for the diag variants? HMT or dilate/erode, or open/close or something else?

I guess there are two ways to look at this. One is to remove the offending 8-connected bits and the other is to add pixels to make the 8-connected be filled so as to be 4-connected. I originally tried the former with open (close gave me totally black results as it removed everything because of the nan, if I recall correctly). But I am thinking that the latter is better.

I think my test may have been wrong because I set it up using nan rather than 0. But I would agree that using all the 90-degree variants will likely be needed (via '>')

[anthony]

Pattern Kernels are only used for HMT, Thin and Thicken

Specially, these methods will... find matches (non-negative difference), add difference, subtract difference
where difference is "lowest forground value" - "biggest background value" which is found by the pattern kernel.

[alosca]

We are almost there! I have tried Thicken with the 2x2 rotated kernels, '2>:1,0,0,1' and the results are almost what we want except that it ended up adding 2x2 full blocks whenever we have a T (and its rotated versions) with a missing junction point, i.e. the pattern below (0 = black, X = white)

000X
XXX0
000X

ends up

00XX
XXXX
000X

which is not what we want but expected with these 2x2 kernels. I am trying now some Thinning to remove those undesired blocks (or maybe come up with some way to avoid them altogether). Will report results here. For the record, I also tried '2x2+1+0:1,0,0,1' but I suspect this is one of the rotated versions of '2>:0,1,1,0'.

[fmw42]

I went to http://www.dentistry.bham.ac.uk/landini ... tware.html and downloaded his folder of Morphology filters and installed in ImageJ. Then I used his BinaryThick_.class using the structuring kernel described in the file

Diagonal8to4.txt: Converts 8 connected white features to 4 connected ones by filling empty diagonal pixel spaces


// Diagonal8to4.txt
// converts 8 connected white features to 4 connected
// G. Landini at bham ac uk
run("BinaryThick ", "kernel_a=[0 1 2 1 0 2 2 2 2 ] rotations=[rotate 90] iterations=1 white");

where 2 is don't care

I then ran that filter after selecting BinaryThin in ImageJ. This brings up a simple 3x3 matrix window filled with zeros. Just click OK and further window will open that allows you to fill in the kernel as above and choose 90 rotate and foreground white.

It produced the following for your image.



Upon zooming, this appears to produce what I think you want.


I would then guess that a 3x3 IM morphology kernel of ( 0 1 2 1 0 2 2 2 2 ) or in matrix form

0 1 2
1 0 2
2 2 2

applied as a dilate or thicken and the applied again rotated 90 degrees should do what you want. You can I think specify '>" in IM to make it do the second rotated version. I have not tested it.

You can download ImageJ for any platform at http://rsbweb.nih.gov/ij/download.html and download his morphology filters and install them and try using ImageJ. If that works, then perhaps try the above suggestions in IM. I am curious to hear what you find. I just don't have the time right now to experiment.

Perhaps Anthony can clarify further as to whether it is a dilate or thicken, that would be required.

In IM, I suppose that it could be done with just

0 1
1 0

But Anthony can clarify further. I think this was what he was suggesting above. However, I was concerned that being an even dimension would shift the image some. But perhaps not. In any case you can use the 3x3 form described above with nan as don't care.

[alosca]

Just an example where things can go wrong. In some situations, "-morphology thicken '2>:0,1,1,0'" turns pixels on when they shouldn't. For example, in the left case below we have more pixels turned on than necessary, filling the 3x2 block shown on the middle picture:



The way I was able to fix this problem was with "-morphology thicken '2:0,1,1,0' -morphology thicken '2x2+0+1:1,0,0,1'". This gives the picture on the far right above. But I probably need to consider all rotated cases as well to make sure it covers all possible situations - I am not sure the problem is really solved now.

Is there a way to get morphology results composed with the input image before the next rotated kernel is applied in the sequence? I have seen in the documentation that one can use things like -define morphology compose:lighten but this doesn't work for me (I suspect this would answer my question),

%> convert 8conn.pgm -define morphology compose:lighten -morphology thicken '2>:0,1,1,0' nada.pgm
convert: unable to open image `lighten': No such file or directory @ error/blob.c/OpenBlob/2617.
convert: no decode delegate for this image format `lighten' @ error/constitute.c/ReadImage/544.

Version: ImageMagick 6.7.7-2 2012-05-30 Q16 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2012 ImageMagick Studio LLC
Features: OpenMP OpenCL

[alosca]

Many thanks Fred for going the extra mile on this!

It worked well on that example and, after a close inspection, the result is indeed a (almost) 4-connected line. It seems this is the right kernel when used with Thicken (or almost, see below). I tried -morphology thicken '3>:0,1,-,1,0,-,-,-,-' and obtained similar result. The problem we still have is with the T junctions I mentioned in my previous post. Here is an example when thickening with this 3x3 kernel:



The 2x2 solid block is still a problem. It seems to me that, after considering your findings, the way to fix the problem is to fill in the black T junction pixel and then use -morphology thicken '3>:0,1,-,1,0,-,-,-,-' as it was shown in your post that the result is correct (coincidentally, we didn't have this problem with the image you tested - which at the end was beneficial to pinpoint the culprit).

What makes me scratch my head now is why the 2x2 kernels I have been testing so far didn't give the right results. They have the same 0,1,1,0 entries as in this 3x3 kernel (the '-' are just the don't care entries)?! Maybe there is something under the hood that I am missing (?). Maybe the 2x2 kernel origins we were using had to be modified?

Also, as you pointed out, we don't need all rotations, just one of 90 degrees clockwise:

bamboo [1173] : convert 8conn.pgm -verbose -morphology thicken '3>:0,1,-,1,0,-,-,-,-' nada.pgm
Thicken:1.0 #1 => Changed 339 (re-iterate)
Thicken:1.1 #2 => Changed 383 (re-iterate)
Thicken:1.2 #3 => Changed 0 (re-iterate)
Thicken:1.3 #4 => Changed 0 (done)

So using '3>:..." is not efficient in this case.

I would like to use IM to get this accomplished thus the reason I didn't bother with ImageJ. But I would certainly have learned the solution have I followed your initial suggestion!

---

Edited: After using kernel2image I confirmed that the 3x3 kernel is the same as the 2x2 kernel I have been using and that the results achieved by both kernels (and their rotated versions) are the same. So we are only left to fix the T junction case.

[alosca]

Here is what works so far for me (Edited: well, not really found some cases it fails)

convert 8conn.pgm -verbose -morphology thicken '3>:0,1,-,1,0,-,-,-,-' -morphology thinning '3>:1,0,0,1,1,0,1,1,1' 4conn.pgm

Thicken:1.0 #1 => Changed 339 (re-iterate)
Thicken:1.1 #2 => Changed 381 (re-iterate)
Thicken:1.2 #3 => Changed 0 (re-iterate)
Thicken:1.3 #4 => Changed 0 (done)
Thinning:1.0 #1 => Changed 2 (re-iterate)
Thinning:1.1 #2 => Changed 5 (re-iterate)
Thinning:1.2 #3 => Changed 0 (re-iterate)
Thinning:1.3 #4 => Changed 0 (done)
8conn.pgm=>4conn.pgm PGM 224x215 224x215+0+0 8-bit DirectClass 32.8KB 0.030u 0:00.009


left = 8conn, right = 4conn

Thickening uses the 3x3 kernel suggested by Fred while Thinning fix the generated, undesired 2x2 white blocks. I still can't figure out why the '2>:0,1,1,0' kernels are not sufficient. Maybe just a coincidence with this particular example and the order in which the kernels are applied differ between the 3x3 and 2x2 kernsls (?).

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?).

[fmw42]

Have you tried comparing the output when using the kernel then its rotated version vs using the rotated kernel first and then the unrotated

1 0
0 1

followed by

0 1
1 0


vs


0 1
1 0

followed by

1 0
0 1

Curious if the result are different or not.

[alosca]

I have already tried that order and others and it shouldn't make any difference at all as we can always have rotated versions of the pattern in the image thus any order is equally possible and plausible.

[anthony]

Just an example where things can go wrong. In some situations, "-morphology thicken '2>:0,1,1,0'" turns pixels on when they shouldn't. For example, in the left case below we have more pixels turned on than necessary, filling the 3x2 block shown on the middle picture:

You need to first find and fill in 'V' arrangements, to convert them to 'T', Once 'T' intersections are filled (four passes), THEN you can THEN look for the diagonal joins. Be specific about the order of thicken, as it will determine the preference about which pixel is to be filled in the diagonal.

NOTE: HMT will find all locations, always using the original image. Thicken and thin, will modify the image using one kernel, before trying the next kernel. This is standard practice, though IM does has expert settings (morphology:compose) to allow it to always add pixels while only looking at the original image (for that iteration).