{"id":121,"date":"2007-03-13T07:00:32","date_gmt":"2007-03-13T11:00:32","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/13\/connected-component-labeling-part-2\/"},"modified":"2019-10-23T08:45:27","modified_gmt":"2019-10-23T12:45:27","slug":"connected-component-labeling-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/13\/connected-component-labeling-part-2\/","title":{"rendered":"Connected component labeling &#8211; Part 2"},"content":{"rendered":"<div class=\"content\">\n<p>In this series I'm discussing different ways to compute the connected components of a binary image. Before I get into specific<br \/>\nalgorithms, though, I need to touch briefly on the notion of <i>connectivity<\/i>.<\/p>\n<p>For a given pixel <i>p<\/i>, what is the set of neighbors of <i>p<\/i>? In other words, what is <i>p<\/i>'s neighborhood? There's no single answer that works best for all applications. One definition is that the neighbors of <i>p<\/i> are the pixels that share an edge with <i>p<\/i>. There are four such neighbors:<\/p>\n<pre>  1\r\n4 p 2\r\n  3<\/pre>\n<p>This is called a <i>four-connected neighborhood<\/i>.<\/p>\n<p>Another common neighborhood definition is the set of pixels that share an edge or a corner with <i>p<\/i>. There are eight:<\/p>\n<pre>8 1 2\r\n7 p 3\r\n6 5 4<\/pre>\n<p>Here's a binary image that demonstrates the practical difference between these neighborhood definitions:<\/p>\n<pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid #c8c8c8;\">bw = logical([ <span style=\"color: #0000ff;\">...<\/span>\r\n    0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 0 0 0 0 ]);\r\n\r\nshowPixelValues(bw)<\/pre>\n<p>&nbsp;<\/p>\n<p>If we use a four-connected neighborhood definition, then the image above has two connected components: an upper-left 2-by-2<br \/>\ncomponent, and a lower-right 2-by-3 component. With an eight-connected neighborhood definition, there's just one connected<br \/>\ncomponent.<\/p>\n<p>Many Image Processing Toolbox functions support other kinds of neighborhood definitions as well, via an optional input argument<br \/>\ncalled <tt>CONN<\/tt> (for connectivity). For two-dimensional processing, <tt>CONN<\/tt> is a 3-by-3 matrix of 0s and 1s. The matrix has to be symmetric about its central element. The 1s define the neighbors.<br \/>\nFor example, here are the <tt>CONN<\/tt> matrices for four-connected and eight-connected neighborhoods:<\/p>\n<pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid #c8c8c8;\">conn4 = [0 1 0; 1 1 1; 0 1 0]<\/pre>\n<pre style=\"font-style: oblique;\">conn4 =\r\n\r\n     0     1     0\r\n     1     1     1\r\n     0     1     0\r\n\r\n<\/pre>\n<pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid #c8c8c8;\">conn8 = [1 1 1; 1 1 1; 1 1 1]<\/pre>\n<pre style=\"font-style: oblique;\">conn8 =\r\n\r\n     1     1     1\r\n     1     1     1\r\n     1     1     1\r\n\r\n<\/pre>\n<p>In my next post in this series, I'll talk about representing the collection of neighbor relationships among foreground pixels<br \/>\nas a graph.<\/p>\n<p><script>\/\/ <![CDATA[\nfunction grabCode_705bd0fb589d4852ab9387b8fdfb180f() {\n        \/\/ Remember the title so we can use it in the new page\n        title = document.title;\n\n        \/\/ Break up these strings so that their presence\n        \/\/ in the Javascript doesn't mess up the search for\n        \/\/ the MATLAB code.\n        t1='705bd0fb589d4852ab9387b8fdfb180f ' + '##### ' + 'SOURCE BEGIN' + ' #####';\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 705bd0fb589d4852ab9387b8fdfb180f';\n    \n        b=document.getElementsByTagName('body')[0];\n        i1=b.innerHTML.indexOf(t1)+t1.length;\n        i2=b.innerHTML.indexOf(t2);\n \n        code_string = b.innerHTML.substring(i1, i2);\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\n\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \n        \/\/ in the XML parser.\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\n        \/\/ doesn't go ahead and substitute the less-than character. \n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\n\n        author = 'Steve Eddins';\n        copyright = 'Copyright 2007 The MathWorks, Inc.';\n\n        w = window.open();\n        d = w.document;\n        d.write('\n\n\n\n<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\n\n\n\n\\n');\n      \n      d.title = title + ' (MATLAB code)';\n      d.close();\n      }\n\/\/ ]]><\/script><\/p>\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\">\n<a><span style=\"font-size: x-small; font-style: italic;\">Get<br \/>\nthe MATLAB code<br \/>\n<noscript>(requires JavaScript)<\/noscript><\/span><\/a><\/p>\n<p>Published with MATLAB\u00ae 7.4<\/p>\n<\/div>\n<p><!-- 705bd0fb589d4852ab9387b8fdfb180f ##### SOURCE BEGIN ##### %% Connected Component Labeling - Part 2 % In this series I'm discussing different ways to compute the connected % components of a binary image. Before I get into specific algorithms, % though, I need to touch briefly on the notion of _connectivity_. % % For a given pixel _p_, what is the set of neighbors of _p_? In other words, % what is _p_'s neighborhood? There's no single answer that works best % for all applications. One definition is that the neighbors of _p_ are the % pixels that share an edge with _p_. There are four such neighbors: % % 1 % 4 p 2 % 3 % % This is called a _four-connected neighborhood_. % % Another common neighborhood definition is the set of pixels that share an % edge or a corner with _p_. There are eight: % % 8 1 2 % 7 p 3 % 6 5 4 % % Here's a binary image that demonstrates the practical difference between % these neighborhood definitions: bw = logical([ ... 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 ]); showPixelValues(bw) %% % If we use a four-connected neighborhood definition, then the image above % has two connected components: an upper-left 2-by-2 component, and a % lower-right 2-by-3 component. With an eight-connected neighborhood % definition, there's just one connected component. % % Many Image Processing Toolbox functions support other kinds of % neighborhood definitions as well, via an optional input argument called % |CONN| (for connectivity). For two-dimensional processing, |CONN| is a % 3-by-3 matrix of 0s and 1s. The matrix has to be symmetric about its % central element. The 1s define the neighbors. For example, here are the % |CONN| matrices for four-connected and eight-connected neighborhoods: conn4 = [0 1 0; 1 1 1; 0 1 0] %% conn8 = [1 1 1; 1 1 1; 1 1 1] %% % In my next post in this series, I'll talk about representing the % collection of neighbor relationships among foreground pixels as a graph. ##### SOURCE END ##### 705bd0fb589d4852ab9387b8fdfb180f --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\nIn this series I'm discussing different ways to compute the connected components of a binary image. Before I get into specific<br \/>\nalgorithms, though, I need to touch briefly on the notion of... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/13\/connected-component-labeling-part-2\/\">read more >><\/a><\/p>\n","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[16],"tags":[330],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/121"}],"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=121"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/121\/revisions"}],"predecessor-version":[{"id":2323,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/121\/revisions\/2323"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}