In my earlier posts aboutdilation and erosion algorithms, I wrote about exploiting structuring element decomposition for improving speed. Today I want to discuss a potential decompositiongotcha: If you don't implement decomposed dilation and erosion carefully, you can easily end up with wrong answers near the image boundaries.

Here's an example to illustrate what can go wrong, starting with a single binary image containing only one foreground pixel;

A = false(5,5); A(5,3) = true

A = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

Here's a structuring element:

b = [1 0 0; 1 1 0; 1 1 1; 0 1 1; 0 0 1]

b = 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1

Compute the dilation ofAbybusingimdilate:

A_b = imdilate(A, b)

A_b = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0

The structuring elementbcan be decomposed into two smaller structuring elements,b1andb2。

b1 = [1; 1; 1]

b1 = 1 1 1

b2 = [1 0 0; 0 1 0; 0 0 1]

b2 = 1 0 0 0 1 0 0 0 1

Morphology theory (actually, just the distributive property you learned back in high school) suggests that we should be able to dilateAbyb1, and then dilate the result byb2, to get the same result as dilatingAbyb。Let's try that.

A_b1_b2 = imdilate(imdilate(A, b1), b2)

A_b1_b2 = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0

Uh oh. CompareA_bandA_b1_b2carefully to see they are not the same. So where did we go wrong? Roughly speaking, we failed to take into consideration the effect of dilationoutside the image boundaries。如果你把整个解放军形象ne into account, dilation byb1affects pixels outside the original image boundaries. The out-of-bounds pixels can then affect in-bounds results when we dilate byb2。But in the callimdilate(imdilate(A, b1), b2)above, each call toimdilatereturns a result that's only the size of the input image; affected out-of-bounds pixels get cropped out.

So let's try that again, but this time we'll pre-pad the input image with 0s.

A_p = padarray(A, [1 1], 0,'both')

A_p = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

Now dilate withb1andb2in succession:

A_p_b1_b2 = imdilate(imdilate(A_p, b1), b2)

A_p_b1_b2 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0

And trim away the padded rows and columns:

A_p_b1_b2_cropped = A_p_b1_b2(2:end-1, 2:end-1)

A_p_b1_b2_cropped = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0

Success! That result equalsA_b。

That means we have a trade-off to make. We can get significant speed improvements using structural element decomposition, but we can guarantee correct results at the image boundaries only if we use extra memory to make a padded copy of the input image. That's whatimdilateandimerodedo.

I have two more brief topics in mind for this series on dilation and erosion algorithms. I'll try to wrap things up in December.

Get the MATLAB code

Published with MATLAB® 7.7