python_regious thanks for all the help, links and papers. :)

Quote:
OOohh, I see. You want to keep the irregularity of the edges. Sorry, I thought that you wanted to essentially get nice neat rectangles out of it .

Yes i want the irregularities. That's what i'm trying to say from the beginning, but (once again) my english don't help. I have to do something for this :) (to self : learn english)

The page and the part of your report on granulometry, made the whole thing more clear (i think). When i'm going from one structurin element to the next (= bigger one), should those two differ only in size or they must differ in shape too? E.g. two different 3x3 masks can be:

Mask 1:

1 0 01 1 00 1 1

Mask 2:

1 1 01 1 11 0 0

Should i apply both of them, or a simple 3x3 mask with all elements 1 will be enough. I think you mentioned in a previous post that i should try a star mask or something like that, so i guess they must differ in shape too. But then the possible combinations for an 7x7 maks are endless (i think 49! (this is factorial))

I'll give it a shot and i'll post back later.

Taharez:

Quote:
How about using ACMs? If you can identify some points inside the shapes, you could then grow a contour from inside the shape, thus building the boundary. It's not an area I've studied a lot (did my projects on Hough transforms), but it seems it could be a could candidate in your application. There's a demo applet of ACMs here, but there's loads of info available, just search for "active contour model", or "snakes", but I'm guessing the former will give you more relevant hits ;)

I think what you describe is the same thing i posted previously (the flood filling thing, but without flooding the shape). I keep that on the back of my mind for now, because i'm trying to find a way to do the same thing without knowing anything about the image. And, as python_regious pointed out, this can lead to artifacts. I don't know for sure, but i think he is right. I guess the only way to find out is by implementing it :) Anyway, thanks for the suggestion.

HellRaiZer

Quote:Original post by Taharez
How about using ACMs? If you can identify some points inside the shapes, you could then grow a contour from inside the shape, thus building the boundary. It's not an area I've studied a lot (did my projects on Hough transforms), but it seems it could be a could candidate in your application. There's a demo applet of ACMs here, but there's loads of info available, just search for "active contour model", or "snakes", but I'm guessing the former will give you more relevant hits ;)

That sounds extremely similar to Hellraisers flood fill algorithm. The problem that I can see is deciding where to start. You could construct a "blob" detection algorithm, such that it detects areas of black over a certain size, then find the geometric centre and start from there. I did write a "blob" detection algorithm about 4 years ago, but it's since been lost. It's not too hard though, as it's recursive in nature.

It also all depends on how much of the noise he wants to retain at the edges, and it would still suffer from routes through the noise, although these could be eliminated using a "only count the mass which is 95% from the CoM" type algorithm. However this would start to fail once you have two connected blobs.

Quote:Original post by HellRaiZer
python_regious thanks for all the help, links and papers. :)

Quote:
OOohh, I see. You want to keep the irregularity of the edges. Sorry, I thought that you wanted to essentially get nice neat rectangles out of it .

Yes i want the irregularities. That's what i'm trying to say from the beginning, but (once again) my english don't help. I have to do something for this :) (to self : learn english)

The page and the part of your report on granulometry, made the whole thing more clear (i think). When i'm going from one structurin element to the next (= bigger one), should those two differ only in size or they must differ in shape too? E.g. two different 3x3 masks can be:

Mask 1:

1 0 01 1 00 1 1

Mask 2:

1 1 01 1 11 0 0

Should i apply both of them, or a simple 3x3 mask with all elements 1 will be enough. I think you mentioned in a previous post that i should try a star mask or something like that, so i guess they must differ in shape too. But then the possible combinations for an 7x7 maks are endless (i think 49! (this is factorial))

I'll give it a shot and i'll post back later.

Taharez:

Quote:
How about using ACMs? If you can identify some points inside the shapes, you could then grow a contour from inside the shape, thus building the boundary. It's not an area I've studied a lot (did my projects on Hough transforms), but it seems it could be a could candidate in your application. There's a demo applet of ACMs here, but there's loads of info available, just search for "active contour model", or "snakes", but I'm guessing the former will give you more relevant hits ;)

I think what you describe is the same thing i posted previously (the flood filling thing, but without flooding the shape). I keep that on the back of my mind for now, because i'm trying to find a way to do the same thing without knowing anything about the image. And, as python_regious pointed out, this can lead to artifacts. I don't know for sure, but i think he is right. I guess the only way to find out is by implementing it :) Anyway, thanks for the suggestion.

HellRaiZer

Oh, you keep the same shape. When I talk about a 3x3 mask, I really mean:

1 1 11 1 11 1 1

If you want to use all possible permutations of a certain structuring element size, you want to use area morphology.

Tessellator:
Where should i clear the shape_list? The way i think the above pseudocode will work, is by either leaving the noise as is in the image, or by marking shapes as noise.

Anyway, thanks for participating. I think the dilation/erosion procedure works for now. I thought of an alternative solution if some images are too noisy for this algorithm. I could dilate the image using a big mask (say 9x9), eliminating any noise around the shapes. Then i can extract those edges (which will be smooth/straight), mark them with a color which isn't present in the image (e.g. red) and move them pixels in the opposite direction (the flood filling thing, or Active Contour Model as Taharez pointed out) until they touch a pixel other than black. This way I can get exact edges, without worrying about noise.

Movement in the opposite direction (something like expanding the edges) can be done on the original image as is or on the original image with a 3x3 dilation/erosion mask applied to it. This way any paths that might lead to very complex edges will be eliminated and the result will be more accurate.

For the moment a simple closing with a big mask seems to give good results, so i have sometime to think about the above procedure in detail.

One problem i'm trying to solve right now (and i briefly mentioned in the original post) is how i can extract a closed loop for every shape. I.e. starting from a random edge pixel, how can i walk all edge pixels and finish one the starting one. I have code a simple function which tries to do that, but a major problem is that it assumes that every pixel has only one neighbor. E.g. here is a problematic situation.

  0 1 2 3 4 5 6 *-------------0|0 0 0 0 0 0 01|1 0 0 1 0 1 02|1 0 1 0 1 1 03|0 1 0 0 0 0 14|0 0 0 0 0 0 0

If you start at the upper left corner and start scanning for 1s, then the first one you will find is at position (0,1). The next pixel is the only neighbor that is 1, this is (0,2) and so on, until you reach pixel (4,2) where it has two neighbors. Selecting either one (the other will be selected in the next step) will result in an error in the loop. Either the loop will terninate (and as a result it isn't a loop), or on pixel will be skipped.

Does anybody has an idea how i can solve this? How can i decide where to move next?
Maybe a better/bigger edge detector may do the trick. I have to check that.

Anyway, thank you all for posting and especially python_regious.

HellRaiZer

Quote:Original post by HellRaiZer
One problem i'm trying to solve right now (and i briefly mentioned in the original post) is how i can extract a closed loop for every shape. I.e. starting from a random edge pixel, how can i walk all edge pixels and finish one the starting one. I have code a simple function which tries to do that, but a major problem is that it assumes that every pixel has only one neighbor. E.g. here is a problematic situation.

  0 1 2 3 4 5 6 *-------------0|0 0 0 0 0 0 01|1 0 0 1 0 1 02|1 0 1 0 1 1 03|0 1 0 0 0 0 14|0 0 0 0 0 0 0

If you start at the upper left corner and start scanning for 1s, then the first one you will find is at position (0,1). The next pixel is the only neighbor that is 1, this is (0,2) and so on, until you reach pixel (4,2) where it has two neighbors. Selecting either one (the other will be selected in the next step) will result in an error in the loop. Either the loop will terninate (and as a result it isn't a loop), or on pixel will be skipped.

Does anybody has an idea how i can solve this? How can i decide where to move next?
Maybe a better/bigger edge detector may do the trick. I have to check that.

Read up on the Canny edge detector.

Essentially you perform the following steps:

1. Gaussian filter
2. Sobel filter ( or other edge detection filter that provides direction information - so that'd be first order filters )
3. Derive edge directions
4. Quantise edge directions
5. Perform non-maximal suppression
6. Hysteresis based thresholding

That should provide you with a complete, single pixel wide edge.

The first hit on google seemed pretty good.

Other than Canny, there's the Laplacian of Gaussian edge detector, which is pretty good. The basic sobel filter is pretty shit really, and the basic laplacian performs horribly with noise (and of course needs a zero-crossing detection filter).

Quote:
Anyway, thank you all for posting and especially python_regious.

Not a problem, I'm quite interested in this area, if you haddn't have guessed [smile].

I just finish integrating this Canny Edge Detector in my little app. Now i can say for sure that the problem isn't in the edge detector. Below are two images from the two algorithms.

1. Simple edge detection kernel
2. Canny edge detector

The problem isn't that the lines are more than one pixel wide. The problem is that every single pixel must have two and only two neighbors. With both algorithms this isn't true at some corners. I'll leave it as is for now, and make a note of it, if something doesn't work in the future.

Tessellator:
I've tried a similar algorithm a while back in case to make a free volume (or more correctly "free space") distribution of the image (free space == black pixels). Other than the fact that it could select all white pixels as one shape, it can easily result in a stack overflow (i suspect your FindAdjacentMatchingPixelsAndAddToArray() function is recursive). So it isn't as easy as it sounds, even if it got the job done.

Quote:
Sorry for the guff!

No problem :)

HellRaiZer

Quote:Original post by HellRaiZer
I just finish integrating this Canny Edge Detector in my little app. Now i can say for sure that the problem isn't in the edge detector. Below are two images from the two algorithms.

1. Simple edge detection kernel
2. Canny edge detector

The problem isn't that the lines are more than one pixel wide. The problem is that every single pixel must have two and only two neighbors. With both algorithms this isn't true at some corners. I'll leave it as is for now, and make a note of it, if something doesn't work in the future.

HellRaiZer

Well, the non-maximal suppression stage of the Canny should make it such that there are only two neighbours (at least along the direction of the edge).