{"id":153,"date":"2007-07-17T10:02:52","date_gmt":"2007-07-17T14:02:52","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/07\/17\/bwlabeln-design-decision\/"},"modified":"2019-10-23T13:41:48","modified_gmt":"2019-10-23T17:41:48","slug":"bwlabeln-design-decision","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/07\/17\/bwlabeln-design-decision\/","title":{"rendered":"bwlabeln – design decision"},"content":{"rendered":"

\r\nIn a comment on my \"Connected component labeling - Part 6\"<\/a> post, Martin Isenburg asked \"what is the rationale behind the design decision to have bwlabeln<\/tt> work on individual pixels rather than on runs of pixels?\"\r\n<\/p>\r\n\r\n

\r\nExcellent question. I'm happy to answer \"why did they do it that way\" algorithm questions—when I know the answer, that is!\r\n<\/p>\r\n\r\n

\r\nTo summarize the issue: bwlabel<\/tt> performs two-dimensional connected component labeling by analyzing the adjacency relationships of runs of pixels. bwlabeln<\/tt>, on the other hand, analyzes the adjacency relationships of individual pixels. \r\n<\/p>\r\n\r\n

\r\nBackground: Late in the development cycle when Image Processing Toolbox version 3, we decided based on a rising tide of user feedback to add multidimensional support to the toolbox. This was a lot work, and we only had a few months to do it. Component labeling was on the list. 2-D labeling existed in the toolbox, but we needed to add support for arbitrary dimension labeling.\r\n<\/p>\r\n\r\n

\r\nSeveral toolbox functions, including connected-component labeling, depended upon some definition of pixel connectivity. 2-D functions that already existed accepted 4 or 8 as connectivity definitions. For 3-D, we could add 6, 18, and 26 to the list, but what should we do for arbitrary dimensions? We decided to add to support a very broad notion of defining connectivity. Specifically, to define the desired multidimensional connectivity, you could provide a connectivity array, called CONN<\/tt> in the documentation. CONN<\/tt> is a 3-by-3-by- ... -by-3 logical array, symmetric about its center element. This gives the user the ability to define whatever connectivity they desire.\r\n<\/p>\r\n\r\n

\r\nAs part of the overall multidimensional development effort, we had already created code for doing arbitrary-dimensional neighborhood iterating (see toolbox\/images\/images\/private\/neighborhood.cpp for the details). By combining that code with the union-find technique, it was possible to implement arbitrary-dimension arbitrary-connectivity labeling quickly and robustly, without much code. \r\n<\/p>\r\n\r\n

\r\nI thought about carrying over the run-length encoding idea to multiple dimensions, but I suspected the code needed to perform arbitrary-dimension arbitrary-connectivity adjacency analysis on runs would be complicated and error-prone. I was also pretty sure that there would be cases, depending on the dimensionality, the connectivity definition, and the specific image characteristics, where doing a run-length encoding pass would be counterproductive. \r\n<\/p>\r\n\r\n

\r\nSo it all came down to a judgment call. Based on available time and resources, the long list of functions that needed multidimensional implementations, and the possibility that the run-length technique might be inefficient in some cases, we decided to go for the pixel-wise union-find implementation.\r\n<\/p>\r\n","protected":false},"excerpt":{"rendered":"

\r\nIn a comment on my \"Connected component labeling - Part 6\" post, Martin Isenburg asked \"what is the rationale behind the design decision to have bwlabeln work on individual pixels rather than on... 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\/153"}],"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=153"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/153\/revisions"}],"predecessor-version":[{"id":3548,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/153\/revisions\/3548"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=153"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=153"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=153"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}