{"id":125,"date":"2007-03-23T07:00:24","date_gmt":"2007-03-23T11:00:24","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/23\/pad-values-in-dilation-and-erosion\/"},"modified":"2019-10-23T08:47:52","modified_gmt":"2019-10-23T12:47:52","slug":"pad-values-in-dilation-and-erosion","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/23\/pad-values-in-dilation-and-erosion\/","title":{"rendered":"Pad values in dilation and erosion"},"content":{"rendered":"
\r\n

Blog reader DKS asked recently<\/a> why values outside the image are assumed to be -Inf<\/tt> when computing dilation. I thought this issue was worth exploring further because it has practical implications for certain\r\n computations.\r\n <\/p>\r\n

Suppose we start with a simple 4-by-4 matrix:<\/p>

f = [22 23 15 16; 24 25 14 15; 20 18 17 23; 19 16 15 20]<\/pre>
\r\nf =\r\n\r\n    22    23    15    16\r\n    24    25    14    15\r\n    20    18    17    23\r\n    19    16    15    20\r\n\r\n<\/pre>
Now think about computing the erosion with a 3-by-3 flat structuring element.  What's the output at the upper left corner?\r\n      It's the minimum of these 9 values:\r\n   <\/p>
?? ?? ??\r\n?? 22 23\r\n?? 24 25<\/pre>
So what do we use for the unknown values outside the image boundary? Suppose we zero pad:<\/p>
 0  0  0\r\n 0 22 23\r\n 0 24 25<\/pre>
Then the (1,1) output value is 0. In fact, if the image pixels are nonnegative, which is common, there will be a zero-valued\r\n      one-pixel-wide border all the way around the edge of the output image. This is called a boundary artifact<\/i> and is undesirable.  We could avoid this problem by simply excluding external values in our computation of the minimum. A\r\n      mathematical equivalent for erosion is to assume external values all equal some constant that is guaranteed to be greater than or equal\r\n      to all image pixels - like Inf:\r\n   <\/p>
Inf Inf Inf\r\nInf  22  23\r\nInf  24  25<\/pre>
To avoid boundary artifacts when performing dilation, pad with -Inf<\/tt>:\r\n   <\/p>
-Inf -Inf -Inf\r\n-Inf   22   23\r\n-Inf   24   25<\/pre>
Most of the time you don't need to explicitly use the Inf<\/tt> values.  One type of exception occurs when the structuring element doesn't include the center element.  Then sometimes the\r\n      Inf<\/tt> values can appear in the output.\r\n   <\/p>
imdilate(f, [1 0 0])<\/pre>
\r\nans =\r\n\r\n    23    15    16  -Inf\r\n    25    14    15  -Inf\r\n    18    17    23  -Inf\r\n    16    15    20  -Inf\r\n\r\n<\/pre>
Similarly, most of the time you don't actually need to explicitly pad the image.  The exception is when you are computing\r\n      a sequence of dilations (or erosions).  In the Image Processing Toolbox this frequently occurs because imdilate<\/tt> and imerode<\/tt> exploit ''structuring element decomposition.''   That is, a large structuring element is decomposed into two or more smaller\r\n      structuring elements that are mathematically equivalent to the original.\r\n   <\/p>\r\n   
Here's a contrived example to demonstrate why you need to pad explicitly to make the mathematical equivalence work out.<\/p>\r\n   
Structuring element 1 translates an image to the left by 2 pixels.<\/p>
se1 = [1 0 0 0 0];<\/pre>
Structuring element 2 translates an image to the right by 1 pixel.<\/p>
se2 = [0 0 1];<\/pre>
You'd expect the composition of dilation with these two structuring elements to be equivalent to a single dilation with a\r\n      structuring element that translates an image left by 1 pixel:\r\n   <\/p>
se3 = [1 0 0];<\/pre>
Let's try that sequence with no padding:<\/p>
f1 = imdilate(f, se1)<\/pre>
\r\nf1 =\r\n\r\n    15    16  -Inf  -Inf\r\n    14    15  -Inf  -Inf\r\n    17    23  -Inf  -Inf\r\n    15    20  -Inf  -Inf\r\n\r\n<\/pre>
f2 = imdilate(f1, se2)<\/pre>
\r\nf2 =\r\n\r\n  -Inf    15    16  -Inf\r\n  -Inf    14    15  -Inf\r\n  -Inf    17    23  -Inf\r\n  -Inf    15    20  -Inf\r\n\r\n<\/pre>
Now dilate the original image with se3 and compare:<\/p>
f3 = imdilate(f, se3)<\/pre>
\r\nf3 =\r\n\r\n    23    15    16  -Inf\r\n    25    14    15  -Inf\r\n    18    17    23  -Inf\r\n    16    15    20  -Inf\r\n\r\n<\/pre>
They aren't the same.  To make the results equivalent, you have to pad the original image, perform the dilation sequence,\r\n      and the crop the result.\r\n   <\/p>
fp = padarray(f, [2 2], -Inf)<\/pre>
\r\nfp =\r\n\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf    22    23    15    16  -Inf  -Inf\r\n  -Inf  -Inf    24    25    14    15  -Inf  -Inf\r\n  -Inf  -Inf    20    18    17    23  -Inf  -Inf\r\n  -Inf  -Inf    19    16    15    20  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n\r\n<\/pre>
fp1 = imdilate(fp, se1)<\/pre>
\r\nfp1 =\r\n\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n    22    23    15    16  -Inf  -Inf  -Inf  -Inf\r\n    24    25    14    15  -Inf  -Inf  -Inf  -Inf\r\n    20    18    17    23  -Inf  -Inf  -Inf  -Inf\r\n    19    16    15    20  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n\r\n<\/pre>
fp2 = imdilate(fp1, se2)<\/pre>
\r\nfp2 =\r\n\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf    22    23    15    16  -Inf  -Inf  -Inf\r\n  -Inf    24    25    14    15  -Inf  -Inf  -Inf\r\n  -Inf    20    18    17    23  -Inf  -Inf  -Inf\r\n  -Inf    19    16    15    20  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf  -Inf\r\n\r\n<\/pre>
fp2_cropped = fp2(3:end-2, 3:end-2)<\/pre>
\r\nfp2_cropped =\r\n\r\n    23    15    16  -Inf\r\n    25    14    15  -Inf\r\n    18    17    23  -Inf\r\n    16    15    20  -Inf\r\n\r\n<\/pre>
isequal(f3, fp2_cropped)<\/pre>
\r\nans =\r\n\r\n     1\r\n\r\n<\/pre>
Whenever imdilate<\/tt> or imerode<\/tt> is called with a decomposed structuring element, the functions compute the minimum padding necessary to avoid boundary artifacts\r\n      and pad with either -Inf<\/tt> or Inf<\/tt>, respectively.\r\n   <\/p>\r\n   
It's a classic speed vs. memory tradeoff.  Exploiting structuring element decomposition is faster, but storing the intermediate\r\n      padded arrays takes more memory.\r\n   <\/p>