{"id":229,"date":"2008-09-29T14:36:07","date_gmt":"2008-09-29T18:36:07","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/29\/dilation-algorithms-decomposing-more-shapes\/"},"modified":"2019-10-28T09:43:43","modified_gmt":"2019-10-28T13:43:43","slug":"dilation-algorithms-decomposing-more-shapes","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/09\/29\/dilation-algorithms-decomposing-more-shapes\/","title":{"rendered":"Dilation algorithms—decomposing more shapes"},"content":{"rendered":"
\r\n

In my previous post on dilation algorithms<\/a> I discussed structuring element decomposition. We looked at the decomposition of structuring elements with rectangular domains.\r\n Today I want to follow up on the idea by looking at decompositions of other structuring element shapes.\r\n <\/p>\r\n

The strel<\/tt> function offers a variety of flat structuring element shapes:\r\n <\/p>\r\n

\r\n
    \r\n
  • diamond<\/li>\r\n
  • disk<\/li>\r\n
  • line<\/li>\r\n
  • octagon<\/li>\r\n
  • pair<\/li>\r\n
  • periodicline<\/li>\r\n
  • rectangle<\/li>\r\n
  • square<\/li>\r\n <\/ul>\r\n <\/div>\r\n

    (The strel<\/tt> function also offers nonflat shapes, and shapes with arbitrary domains.)\r\n <\/p>\r\n

    Let's look at the 'diamond'<\/tt> shape. The doc says SE = strel('diamond', R)<\/tt> creates a flat, diamond-shaped structuring element, where R<\/tt> specifies the distance from the structuring element origin to the points of the diamond.\" For example:\r\n <\/p>

    se1 = strel('diamond'<\/span>, 5)<\/pre>
     \r\nse1 =\r\n \r\nFlat STREL object containing 61 neighbors.\r\nDecomposition: 4 STREL objects containing a total of 17 neighbors\r\n\r\nNeighborhood:\r\n     0     0     0     0     0     1     0     0     0     0     0\r\n     0     0     0     0     1     1     1     0     0     0     0\r\n     0     0     0     1     1     1     1     1     0     0     0\r\n     0     0     1     1     1     1     1     1     1     0     0\r\n     0     1     1     1     1     1     1     1     1     1     0\r\n     1     1     1     1     1     1     1     1     1     1     1\r\n     0     1     1     1     1     1     1     1     1     1     0\r\n     0     0     1     1     1     1     1     1     1     0     0\r\n     0     0     0     1     1     1     1     1     0     0     0\r\n     0     0     0     0     1     1     1     0     0     0     0\r\n     0     0     0     0     0     1     0     0     0     0     0\r\n\r\n \r\n<\/pre>
    The display says the structuring element has 61 neighbors in its domain, but the four decomposed structuring elements have\r\n      a total of only 17 neighbors.\r\n   <\/p>\r\n   
    What shapes makes up the decomposition?  We can use getsequence<\/tt> and getnhood<\/tt> to find out.\r\n   <\/p>
    se1_seq = getsequence(se1);\r\nfor<\/span> k = 1:numel(se1_seq)<\/pre>
        getnhood(se1_seq(k))<\/pre>
    \r\nans =\r\n\r\n     0     1     0\r\n     1     1     1\r\n     0     1     0\r\n\r\n<\/pre>
    \r\nans =\r\n\r\n     0     1     0\r\n     1     0     1\r\n     0     1     0\r\n\r\n<\/pre>
    \r\nans =\r\n\r\n     0     0     1     0     0\r\n     0     0     0     0     0\r\n     1     0     0     0     1\r\n     0     0     0     0     0\r\n     0     0     1     0     0\r\n\r\n<\/pre>
    \r\nans =\r\n\r\n     0     1     0\r\n     1     0     1\r\n     0     1     0\r\n\r\n<\/pre>
    end<\/span><\/pre>
    This decomposition comes from Rein van den Boomgard and Richard van Balen, \"Methods for Fast Morphological Image Transforms\r\n      Using Bitmapped Binary Images,\" Computer Vision, Graphics, and Image Processing: Models and Image Processing<\/i>, vol. 54, no. 3, May 1992, pp. 252-254.  (That journal name sure is a mouthful!)\r\n   <\/p>\r\n   
    Now let's look at the 'disk'<\/tt> structuring element.  By default, strel('disk',R)<\/tt> actually gives you an approximation<\/i> to a disk shape, where the approximation is based on a technique called radial decomposition using periodic lines<\/i>.  The reference sources are:\r\n   <\/p>\r\n   
    \r\n      
      \r\n         
    • Rolf Adams, \"Radial Decomposition of Discs and Spheres,\" Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing<\/i>, vol. 55, no. 5, September 1993, pp. 325-332.\r\n         <\/li>\r\n         
    • Ronald Jones and Pierre Soille, \"Periodic lines: Definition, cascades, and application to granulometries,\" Pattern Recognition Letters<\/i>, vol. 17, 1996, 1057-1063.\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>
      se2 = strel('disk'<\/span>, 5)<\/pre>
       \r\nse2 =\r\n \r\nFlat STREL object containing 69 neighbors.\r\nDecomposition: 6 STREL objects containing a total of 18 neighbors\r\n\r\nNeighborhood:\r\n     0     0     1     1     1     1     1     0     0\r\n     0     1     1     1     1     1     1     1     0\r\n     1     1     1     1     1     1     1     1     1\r\n     1     1     1     1     1     1     1     1     1\r\n     1     1     1     1     1     1     1     1     1\r\n     1     1     1     1     1     1     1     1     1\r\n     1     1     1     1     1     1     1     1     1\r\n     0     1     1     1     1     1     1     1     0\r\n     0     0     1     1     1     1     1     0     0\r\n\r\n \r\n<\/pre>
      Similar to the 'diamond'<\/tt> shape above, the 'disk'<\/tt> shape is decomposed into a sequence of smaller structuring elements:\r\n   <\/p>
      se2_seq = getsequence(se2);\r\nfor<\/span> k = 1:numel(se2_seq)<\/pre>
          getnhood(se2_seq(k))<\/pre>
      \r\nans =\r\n\r\n     1\r\n     1\r\n     1\r\n\r\n<\/pre>
      \r\nans =\r\n\r\n     1     0     0\r\n     0     1     0\r\n     0     0     1\r\n\r\n<\/pre>
      \r\nans =\r\n\r\n     1     1     1\r\n\r\n<\/pre>
      \r\nans =\r\n\r\n     0     0     1\r\n     0     1     0\r\n     1     0     0\r\n\r\n<\/pre>
      \r\nans =\r\n\r\n     1     1     1\r\n\r\n<\/pre>
      \r\nans =\r\n\r\n     1\r\n     1\r\n     1\r\n\r\n<\/pre>
      end<\/span><\/pre>
      I mentioned above that strel('disk',R)<\/tt> gives you an approximation to a disk. Let's see what that approximation looks like with a larger radius:\r\n   <\/p>
      se3 = strel('disk'<\/span>, 21);\r\nimshow(getnhood(se3), 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
      Well, that's definitely an approximation.  It looks a lot more like an octagon than a circle.  The syntax strel('disk',R,N)<\/tt> gives you more control over the approximation.  N<\/tt> can be 0, 4, 6, or 8.  The values 4, 6, and 8 indicate different levels of approximation.  The default value is 4.  With\r\n      N<\/tt> equal to 8, the result looks closer to a circle, but dilation is a little slower because the decomposition isn't as efficient.\r\n   <\/p>
      se4 = strel('disk'<\/span>, 21, 8);\r\nimshow(getnhood(se4), 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
      Setting N = 0<\/tt> asks strel<\/tt> to construct a disk shape with no decomposition approximation.\r\n   <\/p>
      se5 = strel('disk'<\/span>, 21, 0);\r\nimshow(getnhood(se5), 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
      Using getsequence<\/tt> we can see that there is no decomposition for se5<\/tt>:\r\n   <\/p>
      numel(getsequence(se5))<\/pre>
      \r\nans =\r\n\r\n     1\r\n\r\n<\/pre>
      Next time we'll do some timing experiments with the decomposed structuring elements.<\/p>