{"id":141,"date":"2007-06-12T11:52:52","date_gmt":"2007-06-12T15:52:52","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/06\/12\/connected-component-labeling-part-7\/"},"modified":"2019-10-23T12:58:10","modified_gmt":"2019-10-23T16:58:10","slug":"connected-component-labeling-part-7","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/06\/12\/connected-component-labeling-part-7\/","title":{"rendered":"Connected component labeling &#8211; Part 7"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>I described in my <a href=\"https:\/\/blogs.mathworks.com\/steve\/2007\/05\/25\/connected-component-labeling-part-6\/\">previous connected component labeling post<\/a> the algorithm used by <tt>bwlabeln<\/tt>.  This time I'll talk about the variation used by <tt>bwlabel<\/tt>. This variation uses <i>run-length encoding<\/i> as the first step.\r\n   <\/p>\r\n   <p>Here's what I mean by run-length encoding.  Consider this small binary image matrix:<\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/141\/cclabel_part7_fig1.png\"> <\/p>\r\n   <p>Such a binary image can be represented as a collection of <i>runs<\/i>, or sequences of 1s.  Working columnwise, this image contains 9 runs:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/141\/cclabel_part7_fig2.png\"> <\/p>\r\n   <p>Each run can be represented by its starting pixel and by the number of pixels in the run, which is called the <i>run length<\/i>.  Hence the term <i>run-length encoding<\/i>.\r\n   <\/p>\r\n   <p>For a larger binary image containing larger objects, the number of runs can be much smaller than the number of foreground\r\n      pixels.  But the connectivity analysis can be completely determined based on the runs.  In our small example:\r\n   <\/p>\r\n   <div>\r\n      <ul>\r\n         <li>Run #3 is connected to run #1<\/li>\r\n         <li>Run #4 is connected to run #2<\/li>\r\n         <li>Run #6 is connected to run #4<\/li>\r\n         <li>Run #7 is connected to run #5<\/li>\r\n         <li>Run #8 is connected to run #6<\/li>\r\n         <li>Run #9 is connected to run #7<\/li>\r\n         <li>Run #9 is connected to run #8<\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>This set of connectivity pairs can be resolved into equivalence classes using the <a href=\"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/20\/connected-component-labeling-part-3\/\">technique I described earlier based on <tt>dmperm<\/tt><\/a>. In this example there are only two equivalence classes, corresponding to the two connected components.\r\n   <\/p>\r\n   <p>The function <tt>bwlabel<\/tt> calls computes a run-length encoding first.  As it finds each run, it also determines which runs on the previous column are\r\n      connected, if any.  Then it constructs a sparse adjacency matrix and calls <tt>dmperm<\/tt> to compute the equivalence classes.  Then it labels each run in the output label matrix according to the equivalence class\r\n      it belongs to.\r\n   <\/p>\r\n   <p>This is a very efficient method because it scans each pixel in the input image only once, and also because the adjacency matrix\r\n      is usually relatively small.  It is R-by-R, where R is the number of runs.\r\n   <\/p>\r\n   <p>You can find this method described in Haralick and Shapiro, <i>Computer and Robot Vision Volume 1<\/i>, Addison-Wesley, 1992, pp. 40-48.  (Note that the equivalence class resolution method used by <tt>bwlabel<\/tt> is different than the one described in the book.)\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_99a8e17f9736433688a6bbfa5c383995() {\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='99a8e17f9736433688a6bbfa5c383995 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 99a8e17f9736433688a6bbfa5c383995';\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 2007 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_99a8e17f9736433688a6bbfa5c383995()\"><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.4<br><\/p>\r\n<\/div>\r\n<!--\r\n99a8e17f9736433688a6bbfa5c383995 ##### SOURCE BEGIN #####\r\n%% \r\n% I described in my \r\n% <https:\/\/blogs.mathworks.com\/steve\/2007\/05\/25\/connected-component-labeling-part-6\/ \r\n% previous connected component labeling post> the \r\n% algorithm used by |bwlabeln|.  This time I'll talk about the variation\r\n% used by |bwlabel|. This variation uses _run-length encoding_ as the first\r\n% step.\r\n%\r\n% Here's what I mean by run-length encoding.  Consider this small binary\r\n% image matrix:\r\n%\r\n% <<cclabel_part7_fig1.png>>\r\n%\r\n% Such a binary image can be represented as a collection of _runs_, or\r\n% sequences of 1s.  Working columnwise, this image contains 9 runs:\r\n%\r\n% <<cclabel_part7_fig2.png>>\r\n%\r\n% Each run can be represented by its starting pixel and by the number of\r\n% pixels in the run, which is called the _run length_.  Hence the term\r\n% _run-length encoding_.\r\n%\r\n% For a larger binary image containing larger objects, the number of runs\r\n% can be much smaller than the number of foreground pixels.  But the\r\n% connectivity analysis can be completely determined based on the runs.  In\r\n% our small example:\r\n%\r\n% * Run #3 is connected to run #1\r\n% * Run #4 is connected to run #2\r\n% * Run #6 is connected to run #4\r\n% * Run #7 is connected to run #5\r\n% * Run #8 is connected to run #6\r\n% * Run #9 is connected to run #7\r\n% * Run #9 is connected to run #8\r\n%\r\n% This set of connectivity pairs can be resolved into equivalence classes\r\n% using the \r\n% <https:\/\/blogs.mathworks.com\/steve\/2007\/03\/20\/connected-component-labeling-part-3\/ \r\n% technique I described earlier based on |dmperm|>. In this example there\r\n% are only two equivalence classes, corresponding to the two connected\r\n% components.\r\n%\r\n% The function |bwlabel| calls computes a run-length encoding first.  As\r\n% it finds each run, it also determines which runs on the previous column\r\n% are connected, if any.  Then it constructs a sparse adjacency matrix and\r\n% calls |dmperm| to compute the equivalence classes.  Then it labels each\r\n% run in the output label matrix according to the equivalence class it\r\n% belongs to.\r\n%\r\n% This is a very efficient method because it scans each pixel in the input\r\n% image only once, and also because the adjacency matrix is usually\r\n% relatively small.  It is R-by-R, where R is the number of runs.\r\n%\r\n% You can find this method described in Haralick and Shapiro, _Computer and\r\n% Robot Vision Volume 1_, Addison-Wesley, 1992, pp. 40-48.  (Note that the\r\n% equivalence class resolution method used by |bwlabel| is different than\r\n% the one described in the book.)\r\n##### SOURCE END ##### 99a8e17f9736433688a6bbfa5c383995\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   I described in my previous connected component labeling post the algorithm used by bwlabeln.  This time I'll talk about the variation used by bwlabel. This variation uses run-length encoding as... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2007\/06\/12\/connected-component-labeling-part-7\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[16],"tags":[352],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/141"}],"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=141"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/141\/revisions"}],"predecessor-version":[{"id":3538,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/141\/revisions\/3538"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=141"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=141"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}