{"id":224,"date":"2008-09-03T14:16:08","date_gmt":"2008-09-03T18:16:08","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/03\/dilation-algorithmsintroduction\/"},"modified":"2019-10-28T09:40:35","modified_gmt":"2019-10-28T13:40:35","slug":"dilation-algorithms-introduction","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/03\/dilation-algorithms-introduction\/","title":{"rendered":"Dilation algorithms—Introduction"},"content":{"rendered":"
\r\n

Post updated on September 4 based on feedback from Cris Luengo's comment.<\/em><\/p>\r\n\r\n

Today I'm starting a new series covering some of the concepts underlying algorithms for performing morphological dilation\r\n (and erosion, which is very similar). Most of the time, when people talk about image dilation, they mean the form of dilation\r\n that is a local maximum operation on the neighbors of each pixel. For example, here's how to compute the local maximum, for\r\n each image pixel, with that pixel and its eight neighbors:\r\n <\/p>

A = magic(5)<\/pre>
\r\nA =\r\n\r\n    17    24     1     8    15\r\n    23     5     7    14    16\r\n     4     6    13    20    22\r\n    10    12    19    21     3\r\n    11    18    25     2     9\r\n\r\n<\/pre>
se = ones(3,3)<\/pre>
\r\nse =\r\n\r\n     1     1     1\r\n     1     1     1\r\n     1     1     1\r\n\r\n<\/pre>
B = imdilate(A, se)<\/pre>
\r\nB =\r\n\r\n    24    24    24    16    16\r\n    24    24    24    22    22\r\n    23    23    21    22    22\r\n    18    25    25    25    22\r\n    18    25    25    25    21\r\n\r\n<\/pre>
The set of neighborhood pixels involved in the max operator forms a shape called the structuring element<\/i>. The structuring element doesn't have to be square, as above.  Here is dilation with a short, 3-pixel line:\r\n   <\/p>
se = [1 1 1];\r\nB2 = imdilate(A, se)<\/pre>
\r\nB2 =\r\n\r\n    24    24    24    15    15\r\n    23    23    14    16    16\r\n     6    13    20    22    22\r\n    12    19    21    21    21\r\n    18    25    25    25     9\r\n\r\n<\/pre>
Let's consider how long it should take to compute dilation. Suppose an image has P pixels, and the structuring element contains\r\n      Q neighbors.  Computing the output for a particular pixel involves both Q memory reads and Q comparisons.  Therefore we might\r\n      expect the computation time to be proportional to Q.\r\n   <\/p>\r\n   
We can try to verify that behavior using square structuring elements of varying sizes.  \r\n   <\/p>
% Read in a small sample image and replicate it to make a 1k-by-1k<\/span>\r\n% test image.<\/span>\r\nI = repmat(imread('rice.png'<\/span>), 4, 4);\r\n\r\n% Measure dilation times using a set of square structuring elements<\/span>\r\n% ranging in size from 5-by-5 to 97-by-97.<\/span>\r\nw = 5:4:97;\r\n\r\n% The number of neighbors, Q, in each structuring element will be<\/span>\r\n% w^2.  We are guessing that the running time will be proportional<\/span>\r\n% to Q.<\/span>\r\nQ = w.^2;\r\n\r\n% Initialize vector containing recorded times.<\/span>\r\ntimes = [];\r\n\r\nfor<\/span> wk = w\r\n    % Not that many MATLAB users are familiar with the for-loop<\/span>\r\n    % construct above.  I'll send a MATLAB t-shirt to the first<\/span>\r\n    % person who adds a comment to this post with a brief, clear,<\/span>\r\n    % and correct explanation.<\/span>\r\n\r\n    se = strel(ones(wk, wk));\r\n    f = @() imdilate(I, se);\r\n    times(end+1) = timeit(f);\r\nend<\/span>\r\n\r\nplot(Q, times)\r\nylim([0 1.5*max(times)])<\/pre> 
That plot looks almost constant, with maybe just a hint of an increase with Q.<\/p>\r\n   
So is imdilate<\/tt> somehow computing dilation faster than expected?\r\n   <\/p>\r\n   
That's the subject of this series.  We'll start digging in deeper next time.<\/p>