{"id":244,"date":"2008-12-31T18:41:28","date_gmt":"2008-12-31T23:41:28","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/12\/31\/dilation-with-linear-structuring-elements\/"},"modified":"2019-10-28T09:51:32","modified_gmt":"2019-10-28T13:51:32","slug":"dilation-with-linear-structuring-elements","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/12\/31\/dilation-with-linear-structuring-elements\/","title":{"rendered":"Dilation with linear structuring elements"},"content":{"rendered":"
\r\n

For my series on dilation algorithms<\/a>, I've followed my unfortunate custom of dragging a series out way too long. :-)\r\n <\/p>\r\n

So let's wrap it up with a mention of the last key algorithmic idea implemented in the Image Processing Toolbox morphology\r\n functions: grayscale dilation and erosion with horizontal and vertical structuring elements.\r\n <\/p>\r\n

Normally, the time required to perform dilation and erosion is proportional to the number of elements in the domain of the\r\n structuring element. But there are specialized algorithms that achieve better performance for certain classes of structuring\r\n elements. In particular, imdilate<\/tt> and imerode<\/tt> use the algorithm described in M. van Herk, \"A fast algorithm for local minimum and maximum filters on rectangular and octagonal\r\n kernels,\" Pattern Recognition Letters<\/i>, 13:517-521, 1992. There's a helpful description of this algorithm in P. Soille, Morphological Image Analysis: Principles and Applications<\/i>, 2nd ed., 2007, 89-90.\r\n <\/p>\r\n

This algorithm can perform flat grayscale dilation using horizontal and vertical linear structuring elements in time independent\r\n of the length of the strel.\r\n <\/p>\r\n

Let's test that. \r\n <\/p>

I = imread('rice.png'<\/span>);\r\nlengths = 5:2:31;\r\ntimes = zeros(size(lengths));\r\nfor<\/span> k = 1:numel(lengths)\r\n   se = strel(ones(1, lengths(k)));\r\n   times(k) = timeit(@() imdilate(I, se));\r\nend<\/span>\r\n\r\nplot(lengths, 1000*times)\r\nylim([0 max(1000*times)])\r\nxlabel('Linear structuring element length'<\/span>)\r\nylabel('Dilation time (milliseconds)'<\/span>)<\/pre> 
Here's a test for square structuring elements.<\/p>
lengths = 5:2:31;\r\ntimes = zeros(size(lengths));\r\nfor<\/span> k = 1:numel(lengths)\r\n   se = strel(ones(lengths(k), lengths(k)));\r\n   times(k) = timeit(@() imdilate(I, se));\r\nend<\/span>\r\n\r\nplot(lengths, 1000*times)\r\nylim([0 max(1000*times)])\r\nxlabel('Square structuring element width'<\/span>)\r\nylabel('Dilation time (milliseconds)'<\/span>)<\/pre> 
That's a nice result, especially since using rectangular structuring elements is fairly common.<\/p>\r\n   
To recap, the main dilation and erosion algorithm ideas exploited by Image Processing Toolbox morphology functions are:<\/p>\r\n   
\r\n      
For rectangular structuring elements, this algorithm interacts especially nicely with structuring element decomposition<\/a>. The functions imdilate<\/tt> and imerode<\/tt> automatically detect flat, rectangular structuring elements and decompose them into horizontal and vertical line structuring\r\n      elements. Therefore, grayscale dilation and erosion with flat, rectangular structuring elements can also be performed in time\r\n      independent of the structuring element size.\r\n   <\/p>\r\n