{"id":239,"date":"2008-11-26T20:34:52","date_gmt":"2008-11-27T01:34:52","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/11\/26\/a-structuring-element-decomposition-gotcha\/"},"modified":"2019-10-28T09:47:46","modified_gmt":"2019-10-28T13:47:46","slug":"a-structuring-element-decomposition-gotcha","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/11\/26\/a-structuring-element-decomposition-gotcha\/","title":{"rendered":"A structuring element decomposition “gotcha”"},"content":{"rendered":"
\r\n

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

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

A = false(5,5);\r\nA(5,3) = true<\/pre>
\r\nA =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     0     1     0     0\r\n\r\n<\/pre>
Here's a structuring element:<\/p>
b = [1 0 0; 1 1 0; 1 1 1; 0 1 1; 0 0 1]<\/pre>
\r\nb =\r\n\r\n     1     0     0\r\n     1     1     0\r\n     1     1     1\r\n     0     1     1\r\n     0     0     1\r\n\r\n<\/pre>
Compute the dilation of A<\/tt> by b<\/tt> using imdilate<\/tt>:\r\n   <\/p>
A_b = imdilate(A, b)<\/pre>
\r\nA_b =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     1     0     0     0\r\n     0     1     1     0     0\r\n     0     1     1     1     0\r\n\r\n<\/pre>
The structuring element b<\/tt> can be decomposed into two smaller structuring elements, b1<\/tt> and b2<\/tt>.\r\n   <\/p>
b1 = [1; 1; 1]<\/pre>
\r\nb1 =\r\n\r\n     1\r\n     1\r\n     1\r\n\r\n<\/pre>
b2 = [1 0 0; 0 1 0; 0 0 1]<\/pre>
\r\nb2 =\r\n\r\n     1     0     0\r\n     0     1     0\r\n     0     0     1\r\n\r\n<\/pre>
Morphology theory (actually, just the distributive property you learned back in high school) suggests that we should be able\r\n      to dilate A<\/tt> by b1<\/tt>, and then dilate the result by b2<\/tt>, to get the same result as dilating A<\/tt> by b<\/tt>. Let's try that.\r\n   <\/p>
A_b1_b2 = imdilate(imdilate(A, b1), b2)<\/pre>
\r\nA_b1_b2 =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     1     0     0     0\r\n     0     1     1     0     0\r\n     0     0     1     1     0\r\n\r\n<\/pre>
Uh oh.  Compare A_b<\/tt> and A_b1_b2<\/tt> carefully to see they are not the same. So where did we go wrong?  Roughly speaking, we failed to take into consideration\r\n      the effect of dilation outside the image boundaries<\/i>.  If you take the entire image plane into account, dilation by b1<\/tt> affects pixels outside the original image boundaries.  The out-of-bounds pixels can then affect in-bounds results when we\r\n      dilate by b2<\/tt>.  But in the call imdilate(imdilate(A, b1), b2)<\/tt> above, each call to imdilate<\/tt> returns a result that's only the size of the input image; affected out-of-bounds pixels get cropped out.\r\n   <\/p>\r\n   
So let's try that again, but this time we'll pre-pad the input image with 0s.<\/p>
A_p = padarray(A, [1 1], 0, 'both'<\/span>)<\/pre>
\r\nA_p =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     0     1     0     0     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre>
Now dilate with b1<\/tt> and b2<\/tt> in succession:\r\n   <\/p>
A_p_b1_b2 = imdilate(imdilate(A_p, b1), b2)<\/pre>
\r\nA_p_b1_b2 =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0\r\n     0     0     1     0     0     0     0\r\n     0     0     1     1     0     0     0\r\n     0     0     1     1     1     0     0\r\n     0     0     0     1     1     0     0\r\n\r\n<\/pre>
And trim away the padded rows and columns:<\/p>
A_p_b1_b2_cropped = A_p_b1_b2(2:end-1, 2:end-1)<\/pre>
\r\nA_p_b1_b2_cropped =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     1     0     0     0\r\n     0     1     1     0     0\r\n     0     1     1     1     0\r\n\r\n<\/pre>
Success! That result equals A_b<\/tt>.\r\n   <\/p>\r\n   
That means we have a trade-off to make.  We can get significant speed improvements using structural element decomposition,\r\n      but we can guarantee correct results at the image boundaries only if we use extra memory to make a padded copy of the input\r\n      image. That's what imdilate<\/tt> and imerode<\/tt> do.\r\n   <\/p>\r\n   
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.<\/p>