Hi... As the title says i'm looking for a way to accuratelly extract edges from a noisy black and white image. Let me explain the situation. I have images which look like this one: I'm searching for a way to extract the edges of the pattern inside the image. I tried using some Photoshop techniques before start coding but i wasn't able to find something accurate. 1) I used regular edge detection filter but the black spots around the pattern didn't make it clear. 2) I tried to blur the image first, and despite it gave better results than 1, the resulted edges weren't accurate. Is there any way i can find the desired edges with one pixel accurancy? What i want to be able to do is after edge detection, to scan the image and store the edges' pixel positions in a sequential format. Say for example that the first pixel i find from the scanning is one of the shape's corners, i want to be able to form a loop by walking all the edge's pixels. Is this possible, or the image is too noisy to do it? Thanks in advance. If you need more info please ask. HellRaiZer

Exactly as AP said. Perform a morphological sieve to eliminate the noise, then use a standard canny edge detector or a Laplacian of Guassian.

For the sieve, I suggest you try using area morphology, which is essentially the combination of all possible structuring element shapes. Note that most sieves using an open-close operation, rather than just an open as the AP mentioned. In your case, since you just want to get rid of the small dark areas, an open operation would be sufficient.

There are loads of papers on this on the IEE(E) Image Processing Group database (IEExplore).

AP and python_regious thanks for the replies.

I thought of dillation too (not the erosion step), but i couldn't find a way to preserve the edge shapes and eliminate only the black spots.

Unfortunatelly i don't have access to IEEE papers (my university seems to have access to every electronic library except IEEE !!!). I'll try to browse their library in case to find relevant papers and then i'll try to see where i get them :) Maybe some of them are availiable through other libraries too.

And python_regious, i may not understand everything you described (my english don't help me here :)), but i have something to start searching. Thanks.

HellRaiZer

Quote:Original post by HellRaiZer
AP and python_regious thanks for the replies.

I thought of dillation too (not the erosion step), but i couldn't find a way to preserve the edge shapes and eliminate only the black spots.

Unfortunatelly i don't have access to IEEE papers (my university seems to have access to every electronic library except IEEE !!!). I'll try to browse their library in case to find relevant papers and then i'll try to see where i get them :) Maybe some of them are availiable through other libraries too.

And python_regious, i may not understand everything you described (my english don't help me here :)), but i have something to start searching. Thanks.

HellRaiZer

You need to perform an open operation (dilation followed by erosion) to preserve elements greater than the size of the structuring element, otherwise they will be reduced in size. Remember, you only want to remove features less than the size of the structuring element, and preserve the rest.

I did find some good papers on morphological operations, but I don't think they're suiting for what you want (this was when I was researching colour granulometries). If all else fails, google is your friend [smile]

As jff_f has shown however, getting a perfect rectangle is hard (although you can use a better edge detector to join up the edge segments, Canny for instance). If you perform a series of square sieves you will reduce the edges of the rectangles to be straight, you'll have to go up to a pretty large size though, so it all depends on your processing budget.

jff_f thanks for trying that. I must admit those edges are way better than mine (see photoshop tricks) :) The problem is that they aren't connected, and as i said in my first post i need the edges of a shape to form a loop so i can extract the shapes. Anyway this shows that it can be done. And as python_regious said, a better filter may do it. I'll have to check that tomorrow.

Quote:
There is no practical way to remove the noise around the rectangles unless you're only searching for rectangles or straight lines. If you want to keep this for general edges that's the best you can hope.

Unfortunatelly the shapes can be complex (see, concave polygons (not just quads))

Quote:
With this image and the edge detection you could define easily where the rectangles are if you only want rectangles... just create the biggest rectangle in the regions found with sobel edge detection and I think you would get a good accuracy (with correct edge detection... mine was a quick one).

The whole process must be automatic (for batch mode) so i don't know how practical this can be (defining the regions where shapes should exist).

python_regious:

Quote:
As jff_f has shown however, getting a perfect rectangle is hard (although you can use a better edge detector to join up the edge segments, Canny for instance). If you perform a series of square sieves you will reduce the edges of the rectangles to be straight, you'll have to go up to a pretty large size though, so it all depends on your processing budget.

Performance isn't an issue. Of course i want it to finish in finite time :) but i don't care if it takes 5 secs or 5 mins. The problem is that the edges of the squares must stay as is. I must extract the exact edges, and if i understood what you described correctly, the edges will become smoother. This isn't good for me.

One thought i had was this.
Instead of dilating the image in case to remove the black spots around the shapes, i can use dilation in a way to mimic photoshop's magic wand. I could place e.g. a red pixel inside each shape, and flood fill the shapes until the red pixels meet white. When no red pixel can be moved, then the dilation stops. If i replace all other-than-red pixels with a solid color, then edges can be extracted easily with any edge detection filter.
What do you think? Will this work?

I'll check it tommorow.

HellRaiZer

maybe check out SUSAN? I've implemented something similar (not exactly the same) for work and it's pretty effective.

Quote:Original post by HellRaiZer
python_regious:

Quote:
As jff_f has shown however, getting a perfect rectangle is hard (although you can use a better edge detector to join up the edge segments, Canny for instance). If you perform a series of square sieves you will reduce the edges of the rectangles to be straight, you'll have to go up to a pretty large size though, so it all depends on your processing budget.

Performance isn't an issue. Of course i want it to finish in finite time :) but i don't care if it takes 5 secs or 5 mins. The problem is that the edges of the squares must stay as is. I must extract the exact edges, and if i understood what you described correctly, the edges will become smoother. This isn't good for me.

One thought i had was this.
Instead of dilating the image in case to remove the black spots around the shapes, i can use dilation in a way to mimic photoshop's magic wand. I could place e.g. a red pixel inside each shape, and flood fill the shapes until the red pixels meet white. When no red pixel can be moved, then the dilation stops. If i replace all other-than-red pixels with a solid color, then edges can be extracted easily with any edge detection filter.
What do you think? Will this work?

You don't just dilate, that is a bad thing, as I said. Actually I was incorrect earlier, a close operatiosn would be more appropriate to what you want and is an erosion of a dilation. Sieving the image will in no way "smooth" the edges. Morphology is a non-linear operation, in as much as it doesn't introduce any new signals into the image (unlike linear operations such as the mean filter - which most certainly introduces new signals).

Your flood-fill algorithm could work, but is heavily dependant on there not being a thin route through the noise, and of course it needs human intervention [smile].

Just a bit of background incase you didn't know:

In greyscale, the dilation is simply a maximum operator, and an erosion a minimum filter. The open operation is defined as dilate( erode ) and the close is erode( dilate ). Closings are what you want to use here. You would want to use about a 7x7 structuring element to get rid of most of that noise. Larger structuring elements would straighten up the edges somewhat, though they may be shifted by a few pixels.

I could go into the definition, derivation and into more complicated morphological operations if you like, but I don't think it's necessary for what you want to do.

If you go into photoshop, filters->other->maximum - then do the minimum using the same size - that would perform a closing operation using a square structuring element of the size you input. As an example. here's the output of a (20x20 I think - "size 10" in PS anyway) close operation:



Just note that any colours or smooth edges you see is photoshop being shit.

[Edited by - python_regious on June 27, 2006 6:18:05 PM]