{"id":227,"date":"2008-09-17T13:19:12","date_gmt":"2008-09-17T17:19:12","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/17\/dilation-structuring-element-decomposition\/"},"modified":"2019-10-28T09:42:46","modified_gmt":"2019-10-28T13:42:46","slug":"dilation-structuring-element-decomposition","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/17\/dilation-structuring-element-decomposition\/","title":{"rendered":"Dilation algorithms&mdash;structuring element decomposition"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>This is the second post in my <a href=\"https:\/\/blogs.mathworks.com\/steve\/category\/dilation-algorithms\/\">series<\/a> on algorithm concepts behind the implementation of dilation and erosion in the Image Processing Toolbox. Today I want to\r\n      talk about <i>structuring element decomposition<\/i>.\r\n   <\/p>\r\n   <p>Some useful structuring elements can be represented as the dilation of two or more smaller structuring elements.  Dilation\r\n      implementations can exploit this decomposition of structuring elements into smaller structuring elements by taking advantage\r\n      of the associativity property of dilation.\r\n   <\/p>\r\n   <p>That is, suppose image <i>g<\/i> is the dilation of image <i>f<\/i> with structuring element <i>b<\/i>:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2008\/dilation_2_eq84341.png\"> <\/p>\r\n   <p>where the star operator means dilation. And further suppose that <i>b<\/i> is the dilation of two other structuring elements:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2008\/dilation_2_eq73605.png\"> <\/p>\r\n   <p>Then the original image dilation equation can be rewritten as:<\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2008\/dilation_2_eq69910.png\"> <\/p>\r\n   <p>In English, the equation above says we can dilate <i>f<\/i> with structuring element <i>b<\/i> by:\r\n   <\/p>\r\n   <p>1. Dilating <i>f<\/i> first with structuring element <i>b1<\/i>.\r\n   <\/p>\r\n   <p>2. Dilating the result of step 1 with structuring element <i>b2<\/i>.\r\n   <\/p>\r\n   <p>Let's see how this might help make dilation faster. One of the most commonly-used structuring element shapes is the square.\r\n       For example, here's a simple 5-by-5 array of 1s that can define a structuring element domain (or neighborhood):\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">b = ones(5, 5)<\/pre><pre style=\"font-style:oblique\">\r\nb =\r\n\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n\r\n<\/pre><p>It turns out that a square (or rectangular) structuring element can be decomposed into two structuring elements: a horizontal\r\n      line, and a vertical line.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">b1 = ones(1, 5)<\/pre><pre style=\"font-style:oblique\">\r\nb1 =\r\n\r\n     1     1     1     1     1\r\n\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">b2 = ones(5, 1)<\/pre><pre style=\"font-style:oblique\">\r\nb2 =\r\n\r\n     1\r\n     1\r\n     1\r\n     1\r\n     1\r\n\r\n<\/pre><p>You can check that the dilation of <tt>b1<\/tt> and <tt>b2<\/tt> equals <tt>b<\/tt> by using the <tt>'full'<\/tt> option of <tt>imdilate<\/tt>:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">imdilate(b1, b2, <span style=\"color: #A020F0\">'full'<\/span>)<\/pre><pre style=\"font-style:oblique\">\r\nans =\r\n\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n\r\n<\/pre><p>How does this help us?  Well, as I discussed <a href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/03\/dilation-algorithms-introduction\/\">last time<\/a>, computing dilation directly from its defining equation requires <i>Q<\/i> comparisons per pixel, where <i>Q<\/i> is the number of elements in the structuring element domain.  The 5-by-5 square structuring element has 25 elements in its\r\n      domain.  But structuring elements <tt>b1<\/tt> and <tt>b2<\/tt> have only five elements each.  So you could dilate by one and then again by the other and require only 40% of the comparisons.\r\n   <\/p>\r\n   <p>Let's look at how structuring element decompositions are computed and represented in the Image Processing Toolbox.  The function\r\n      <tt>strel<\/tt> makes a structuring element object.  You give <tt>strel<\/tt> the name of a shape, such as <tt>'rectangle'<\/tt>, plus any parameters required for the shape.  When you use <tt>strel<\/tt> to make a rectangular structuring element, the resulting object displays information about itself, including the decomposition:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">se = strel(<span style=\"color: #A020F0\">'rectangle'<\/span>, [5 5])<\/pre><pre style=\"font-style:oblique\"> \r\nse =\r\n \r\nFlat STREL object containing 25 neighbors.\r\nDecomposition: 2 STREL objects containing a total of 10 neighbors\r\n\r\nNeighborhood:\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n     1     1     1     1     1\r\n\r\n \r\n<\/pre><p>You can call the function <tt>getsequence<\/tt> (actually a method of the <tt>strel<\/tt> class) to get the structuring elements in the decomposition:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">decomp = getsequence(se)<\/pre><pre style=\"font-style:oblique\"> \r\ndecomp =\r\n \r\n2x1 array of STREL objects\r\n \r\n<\/pre><p>You use ordinary MATLAB array indexing to get each of the structuring elements from the decomposition:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">decomp(1)<\/pre><pre style=\"font-style:oblique\"> \r\nans =\r\n \r\nFlat STREL object containing 5 neighbors.\r\n\r\nNeighborhood:\r\n     1\r\n     1\r\n     1\r\n     1\r\n     1\r\n\r\n \r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">decomp(2)<\/pre><pre style=\"font-style:oblique\"> \r\nans =\r\n \r\nFlat STREL object containing 5 neighbors.\r\n\r\nNeighborhood:\r\n     1     1     1     1     1\r\n\r\n \r\n<\/pre><p>Ordinarily, of course, <tt>strel<\/tt> and <tt>imdilate<\/tt> together handle all of these details for you when you perform image dilation.\r\n   <\/p>\r\n   <p>Next time I plan to look at some of the other shapes offered by <tt>strel<\/tt> and see how they get decomposed.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_31dc98c952d54fd5b2e849aecd62008e() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='31dc98c952d54fd5b2e849aecd62008e ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 31dc98c952d54fd5b2e849aecd62008e';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Steve Eddins';\r\n        copyright = 'Copyright 2008 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_31dc98c952d54fd5b2e849aecd62008e()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.6<br><\/p>\r\n<\/div>\r\n<!--\r\n31dc98c952d54fd5b2e849aecd62008e ##### SOURCE BEGIN #####\r\n%%\r\n% This is the second post in my \r\n% <https:\/\/blogs.mathworks.com\/steve\/category\/dilation-algorithms\/ \r\n% series> on algorithm concepts behind the\r\n% implementation of dilation and erosion in the Image Processing Toolbox. Today\r\n% I want to talk about _structuring element decomposition_.\r\n%\r\n% Some useful structuring elements can be represented as the dilation of two or\r\n% more smaller structuring elements.  Dilation implementations can exploit this\r\n% decomposition of structuring elements into smaller structuring elements by\r\n% taking advantage of the associativity property of dilation.\r\n%\r\n% That is, suppose image _g_ is the dilation of image _f_ with structuring\r\n% element _b_:\r\n% \r\n% $$g = f \\star b$$\r\n% \r\n% where the star operator means dilation. And further suppose that _b_ is the\r\n% dilation of two other structuring elements:\r\n%\r\n% $$b = b_1 \\star b_2$$\r\n%\r\n% Then the original image dilation equation can be rewritten as:\r\n%\r\n% $$g = f \\star (b_1 \\star b_2) = (f \\star b_1) \\star b_2$$\r\n%\r\n% In English, the equation above says we can dilate _f_ with structuring element\r\n% _b_ by:\r\n%\r\n% 1. Dilating _f_ first with structuring element _b1_.\r\n%\r\n% 2. Dilating the result of step 1 with structuring element _b2_.\r\n%\r\n% Let's see how this might help make dilation faster. One of the most\r\n% commonly-used structuring element shapes is the square.  For example, here's a\r\n% simple 5-by-5 array of 1s that can define a structuring element domain (or\r\n% neighborhood):\r\n\r\nb = ones(5, 5)\r\n\r\n%%\r\n% It turns out that a square (or rectangular) structuring element can be\r\n% decomposed into two structuring elements: a horizontal line, and a vertical\r\n% line.\r\n\r\nb1 = ones(1, 5)\r\n\r\n%%\r\n\r\nb2 = ones(5, 1)\r\n\r\n%%\r\n% You can check that the dilation of |b1| and |b2| equals |b| by using the\r\n% |'full'| option of |imdilate|:\r\n\r\nimdilate(b1, b2, 'full')\r\n\r\n%%\r\n% How does this help us?  Well, as I discussed \r\n% <https:\/\/blogs.mathworks.com\/steve\/2008\/09\/03\/dilation-algorithms-introduction\/ \r\n% last time>, computing dilation\r\n% directly from its defining equation requires _Q_ comparisons per pixel, where\r\n% _Q_ is the number of elements in the structuring element domain.  The 5-by-5\r\n% square structuring element has 25 elements in its domain.  But structuring\r\n% elements |b1| and |b2| have only five elements each.  So you could dilate by\r\n% one and then again by the other and require only 40% of the comparisons.\r\n%\r\n% Let's look at how structuring element decompositions are computed and\r\n% represented in the Image Processing Toolbox.  The function |strel| makes a\r\n% structuring element object.  You give |strel| the name of a shape, such as\r\n% |'rectangle'|, plus any parameters required for the shape.  When you use\r\n% |strel| to make a rectangular structuring element, the resulting object\r\n% displays information about itself, including the decomposition:\r\n\r\nse = strel('rectangle', [5 5])\r\n\r\n%%\r\n% You can call the function |getsequence| (actually a method of the |strel|\r\n% class) to get the structuring elements in the decomposition:\r\n\r\ndecomp = getsequence(se)\r\n\r\n%%\r\n% You use ordinary MATLAB array indexing to get each of the structuring elements\r\n% from the decomposition:\r\n\r\ndecomp(1)\r\n\r\n%%\r\n\r\ndecomp(2)\r\n\r\n%%\r\n% Ordinarily, of course, |strel| and |imdilate| together handle all of these\r\n% details for you when you perform image dilation.\r\n%\r\n% Next time I plan to look at some of the other shapes offered by |strel| and\r\n% see how they get decomposed.\r\n##### SOURCE END ##### 31dc98c952d54fd5b2e849aecd62008e\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   This is the second post in my series on algorithm concepts behind the implementation of dilation and erosion in the Image Processing Toolbox. Today I want to\r\n      talk about structuring... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/17\/dilation-structuring-element-decomposition\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[18],"tags":[516,124,288,106],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/227"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=227"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/227\/revisions"}],"predecessor-version":[{"id":3608,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/227\/revisions\/3608"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}