{"id":241,"date":"2008-12-19T19:17:39","date_gmt":"2008-12-20T00:17:39","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/12\/19\/packed-dilation-and-erosion\/"},"modified":"2019-10-28T09:49:00","modified_gmt":"2019-10-28T13:49:00","slug":"packed-dilation-and-erosion","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/12\/19\/packed-dilation-and-erosion\/","title":{"rendered":"Packed dilation and erosion"},"content":{"rendered":"
\r\n

This post is another in my series on morphological dilation and erosion algorithms<\/a>.<\/i><\/p>\r\n

One of the algorithm techniques used by imdilate<\/tt> and imerode<\/tt> is binary image bit packing. In bit packing, groups of 32 binary image pixels are stored as bits in unsigned 32-bit integers.\r\n <\/p>\r\n

The Image Processing Toolbox functions bwpack<\/tt> and bwunpack<\/tt> do the packing and unpacking. Let's look at a simple example, starting with reading in text.png and then extracting a 32-by-4\r\n subimage.\r\n <\/p>

bw = imread('text.png'<\/span>);\r\nimshow(bw)<\/pre> 
bw_sub = bw(12:41, 30:33)<\/pre>
\r\nbw_sub =\r\n\r\n     0     0     0     0\r\n     0     0     1     1\r\n     0     0     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     0     1     1\r\n     0     0     1     1\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     1     0     0     0\r\n     1     0     0     0\r\n     0     0     0     0\r\n     0     0     0     0\r\n     0     0     1     1\r\n     0     0     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n     0     1     1     1\r\n\r\n<\/pre>
Now pass the subimage to bwpack<\/tt>.\r\n   <\/p>
bw_sub_packed = bwpack(bw_sub)\r\nwhos<\/pre>
\r\nbw_sub_packed =\r\n\r\n     1572864  1040187640  1065354238  1065354238\r\n\r\n  Name                 Size             Bytes  Class      Attributes\r\n\r\n  bw                 256x256            65536  logical              \r\n  bw_sub              30x4                120  logical              \r\n  bw_sub_packed        1x4                 16  uint32               \r\n\r\n<\/pre>
bw_sub_packed<\/tt> is just a 1-by-4 uint32<\/tt> matrix, but those 4 values contain all the values in the original 32-by-4 subimage. You can see the correspondence by using\r\n      the dec2bin<\/tt> function, which converts a decimal number to binary form (represented as a string).\r\n   <\/p>
% Convert the bw_sub_packed(1,2) to binary form.<\/span>\r\ndec2bin(bw_sub_packed(1, 2))<\/pre>
\r\nans =\r\n\r\n111110000000000000000011111000\r\n\r\n<\/pre>
You can see that these are the 0 and 1 values from the second column of bw_sub<\/tt>.\r\n   <\/p>\r\n   
So what does this have to do with dilation and erosion? Binary image dilation and erosion can be expressed in terms of translations,\r\n      logical ANDs, and logical ORs of pixel values.  The C and C++ operators >><\/tt>, <<<\/tt>, &<\/tt>, and |<\/tt> operate on unsigned integer values in bitwise fashion.  Therefore, by packing binary image pixel values into the bits of\r\n      unsigned 32-bit integers, we can write C or C++ code that dilates and erodes faster, because it is essentially operating on\r\n      multiple pixel values at a time.\r\n   <\/p>\r\n   
Let's try dilating text.png by packing it, passing the packed image to imdilate<\/tt>, and then unpacking the result.  (Note that imdilate<\/tt> supports 32-bit integer images, so we have to explicitly tell imdilate<\/tt> to treat the input as packed.)  We'll use a diagonal cross structuring element.\r\n   <\/p>
bw_packed = bwpack(bw);\r\nse = strel(eye(9) | rot90(eye(9)));\r\nbw_packed_dilated = imdilate(bw_packed, se, 'ispacked'<\/span>);\r\nbw_dilated = bwunpack(bw_packed_dilated);\r\nimshow(bw_dilated)<\/pre> 
Let's time packed dilation and compare it to the ordinary version, using a 2k-by-2k image. \r\n   <\/p>
bw = repmat(bw, 8, 8);\r\nbw_packed = bwpack(bw);\r\npacked_dilation_time = timeit(@() imdilate(bw_packed, se, 'ispacked'<\/span>))<\/pre>
\r\npacked_dilation_time =\r\n\r\n    0.0127\r\n\r\n<\/pre>
ordinary_dilation_time = timeit(@() imdilate(bw, se))<\/pre>
\r\nordinary_dilation_time =\r\n\r\n    0.0396\r\n\r\n<\/pre>
speedup = ordinary_dilation_time \/ packed_dilation_time<\/pre>
\r\nspeedup =\r\n\r\n    3.1251\r\n\r\n<\/pre>
The measured speedup is good, but much less than a factor of 32, which we might have expected.  There are two reasons for\r\n      the smaller speedup factor:\r\n   <\/p>\r\n   
\r\n      
    \r\n         
  • Input argument parsing and other overhead in imdilate.m<\/li>\r\n         
  • The C++ code used by the toolbox for ordinary dilation uses a method that does better when there are relatively few white\r\n            input pixels, and this method can't be used as effectively for the packed version.\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   
    Here's a design question for you to consider: Should imdilate<\/tt> always use the packed form?  In other words, if you pass it a logical<\/tt> input, should imdilate<\/tt> pack it, performed packed dilation, and then unpack it?\r\n   <\/p>\r\n   
    Well, the packing and unpacking steps take time. For example:<\/p>
    timeit(@() bwpack(bw))<\/pre>
    \r\nans =\r\n\r\n    0.0198\r\n\r\n<\/pre>
    So it's conceivable that packing, packed dilation, and unpacking could together take longer than the ordinary dilation implementation.<\/p>\r\n   
    We decided that imdilate<\/tt> (and imerode<\/tt>) should automatically do bit packing only if the structuring element is decomposed into at least two structuring elements.\r\n       That way, the cost of packing and unpacking is amortized across the cost of at least two packed dilation operations.\r\n   <\/p>\r\n   
    Lately, we've been taking a fresh look at various aspects of our morphology operations, and we're optimistic that we can make\r\n      them go faster in future releases of the Image Processing Toolbox.\r\n   <\/p>