{"id":183,"date":"2007-11-27T12:00:26","date_gmt":"2007-11-27T17:00:26","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/11\/27\/general-connectivity\/"},"modified":"2019-10-23T15:27:43","modified_gmt":"2019-10-23T19:27:43","slug":"general-connectivity","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/11\/27\/general-connectivity\/","title":{"rendered":"General connectivity"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>The notion of neighbor connectivity is discussed in most image processing textbooks.  Specifically, what is the set of neighbors\r\n      of a pixel?  For example, a commonly-used neighborhood connectivity is 4-connected, where each pixel has four neighbors. \r\n      The neighborhood looks like this:\r\n   <\/p><pre>   1\r\n 1 1 1\r\n   1<\/pre><p>Another common connectivity is 8-connected, where each pixel has eight neighbors.  The neighborhood looks like this:<\/p><pre> 1 1 1\r\n 1 1 1\r\n 1 1 1<\/pre><p>Many Image Processing Toolbox functions depend on a definition of connectivity.  Most of these functions allow you to specify\r\n      the desired connectivity in a very general, flexible way.\r\n   <\/p>\r\n   <p>Consider <tt>bwperim<\/tt>.  This function computes perimeter pixels by finding the foreground pixels that are connected to background pixels.  Some\r\n      definition of connectivity is therefore required.  Let's look at an example.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw = [ 0     0     0     0     0     0     0\r\n       0     0     1     1     1     0     0\r\n       0     1     1     1     1     1     0\r\n       0     1     1     1     1     1     0\r\n       0     1     1     1     1     1     0\r\n       0     0     1     1     1     0     0\r\n       0     0     0     0     0     0     0 ];<\/pre><p>Find the foreground pixels that are 4-connected to the background.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">perim4 = bwperim(bw, 4)<\/pre><pre style=\"font-style:oblique\">\r\nperim4 =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     0     1     1     1     0     0\r\n     0     1     0     0     0     1     0\r\n     0     1     0     0     0     1     0\r\n     0     1     0     0     0     1     0\r\n     0     0     1     1     1     0     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre><p>Now find the foreground pixels that are 8-connected to the background.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">perim8 = bwperim(bw, 8)<\/pre><pre style=\"font-style:oblique\">\r\nperim8 =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     0     1     1     1     0     0\r\n     0     1     1     0     1     1     0\r\n     0     1     0     0     0     1     0\r\n     0     1     1     0     1     1     0\r\n     0     0     1     1     1     0     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre><p>In addition to specifying connectivity as \"4\" or \"8\", you can also use a 3-by-3 matrix of 0s and 1s to specify other kinds\r\n      of connectivity.  The 3-by-3 connectivity matrix below says that a pixel has only two neighbors: The pixel above and the pixel\r\n      below.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">conn2 = [ 0 1 0\r\n          0 1 0\r\n          0 1 0 ];\r\n\r\nperim2 = bwperim(bw, conn2)<\/pre><pre style=\"font-style:oblique\">\r\nperim2 =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     0     1     1     1     0     0\r\n     0     1     0     0     0     1     0\r\n     0     0     0     0     0     0     0\r\n     0     1     0     0     0     1     0\r\n     0     0     1     1     1     0     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre><p>Note that the (4,2) and (4,6) pixels are not considered to be perimeter pixels with this connectivity.  That's because their\r\n      upper and lower neighbors are both part of the foreground, not the background.\r\n   <\/p>\r\n   <p>Sometimes it's useful to define 6-connectivity.  There are two different flavors, both of which can be expressed using the\r\n      3-by-3 matrix form:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">conn6a = [ 1 1 0\r\n           1 1 1\r\n           0 1 1 ];\r\n\r\nconn6b = [ 0 1 1\r\n           1 1 1\r\n           1 1 0 ];<\/pre><p>For processing three-dimensional arrays, you specify 6-connectivity (face-adjacent pixels), 18-connectivity (face- or edge-adjacent\r\n      pixels), or 26-connectivity (face-, edge-, or vertex-adjacent pixels).  But you can specify your own flavor of connectivity\r\n      by using a 3-by-3-by-3 matrix.  Here's an example.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw_3d = false(5,5,3);\r\nbw_3d(2:4,2:4,:) = true;\r\n\r\n<span style=\"color: #228B22\">% Label three-dimensional connected components.<\/span>\r\nL1 = bwlabeln(bw_3d)<\/pre><pre style=\"font-style:oblique\">\r\nL1(:,:,1) =\r\n\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n\r\n\r\nL1(:,:,2) =\r\n\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n\r\n\r\nL1(:,:,3) =\r\n\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n\r\n<\/pre><p>There's only one three-dimensional connected component.  But that's using the default connectivity.  Let's define a three-dimensional\r\n      connectivity such that each pixel has neighbors only in the same plane.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">conn_3d = cat(3, zeros(3,3), ones(3,3), zeros(3,3))<\/pre><pre style=\"font-style:oblique\">\r\nconn_3d(:,:,1) =\r\n\r\n     0     0     0\r\n     0     0     0\r\n     0     0     0\r\n\r\n\r\nconn_3d(:,:,2) =\r\n\r\n     1     1     1\r\n     1     1     1\r\n     1     1     1\r\n\r\n\r\nconn_3d(:,:,3) =\r\n\r\n     0     0     0\r\n     0     0     0\r\n     0     0     0\r\n\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">L2 = bwlabeln(bw_3d, conn_3d)<\/pre><pre style=\"font-style:oblique\">\r\nL2(:,:,1) =\r\n\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n\r\n\r\nL2(:,:,2) =\r\n\r\n     0     0     0     0     0\r\n     0     2     2     2     0\r\n     0     2     2     2     0\r\n     0     2     2     2     0\r\n     0     0     0     0     0\r\n\r\n\r\nL2(:,:,3) =\r\n\r\n     0     0     0     0     0\r\n     0     3     3     3     0\r\n     0     3     3     3     0\r\n     0     3     3     3     0\r\n     0     0     0     0     0\r\n\r\n<\/pre><p>Now there are three connected components, one in each plane of the array.<\/p>\r\n   <p>The Image Processing Toolbox functions <tt>bwlabel<\/tt>, <tt>bweuler<\/tt>, <tt>bwboundaries<\/tt>, and <tt>bwtraceboundary<\/tt> can accept either 4 or 8 connectivity.\r\n   <\/p>\r\n   <p>The toolbox functions <tt>bwareaopen<\/tt>, <tt>bwlabeln<\/tt>, <tt>bwperim<\/tt>, <tt>bwulterode<\/tt>, <tt>imclearborder<\/tt>, <tt>imextendedmax<\/tt>, <tt>imextendedmin<\/tt>, <tt>imhmax<\/tt>, <tt>imhmin<\/tt>, <tt>imimposemin<\/tt>, <tt>imreconstruct<\/tt>, <tt>imregionalmax<\/tt>, <tt>imregionalmin<\/tt>, and <tt>watershed<\/tt> can all accept general 3-by-3 (or higher dimensional) connectivity matrices.\r\n   <\/p>\r\n   <p>Have you used this general connectivity capability before?  If so, I'd like to hear about it.<\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_217519afd68b4a7db2d753ec3153187d() {\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='217519afd68b4a7db2d753ec3153187d ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 217519afd68b4a7db2d753ec3153187d';\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_217519afd68b4a7db2d753ec3153187d()\"><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.5<br><\/p>\r\n<\/div>\r\n<!--\r\n217519afd68b4a7db2d753ec3153187d ##### SOURCE BEGIN #####\r\n%%\r\n% The notion of neighbor connectivity is discussed in most image\r\n% processing textbooks.  Specifically, what is the set of\r\n% neighbors of a pixel?  For example, a commonly-used\r\n% neighborhood connectivity is 4-connected, where each pixel has\r\n% four neighbors.  The neighborhood looks like this:\r\n%\r\n%     1 \r\n%   1 1 1\r\n%     1 \r\n%\r\n% Another common connectivity is 8-connected, where each pixel\r\n% has eight neighbors.  The neighborhood looks like this:\r\n%\r\n%   1 1 1\r\n%   1 1 1\r\n%   1 1 1\r\n%\r\n% Many Image Processing Toolbox functions depend on a definition\r\n% of connectivity.  Most of these functions allow you to specify\r\n% the desired connectivity in a very general, flexible way.  \r\n%\r\n% Consider |bwperim|.  This function computes perimeter\r\n% pixels by finding the foreground pixels that are connected to\r\n% background pixels.  Some definition of connectivity is\r\n% therefore required.  Let's look at an example.\r\n\r\nbw = [ 0     0     0     0     0     0     0\r\n       0     0     1     1     1     0     0\r\n       0     1     1     1     1     1     0\r\n       0     1     1     1     1     1     0\r\n       0     1     1     1     1     1     0\r\n       0     0     1     1     1     0     0\r\n       0     0     0     0     0     0     0 ];\r\n\r\n%%\r\n% Find the foreground pixels that are 4-connected to the \r\n% background.\r\n\r\nperim4 = bwperim(bw, 4)\r\n\r\n%%\r\n% Now find the foreground pixels that are 8-connected to the\r\n% background.\r\n\r\nperim8 = bwperim(bw, 8)\r\n\r\n%%\r\n% In addition to specifying connectivity as \"4\" or \"8\", you can\r\n% also use a 3-by-3 matrix of 0s and 1s to specify other kinds of\r\n% connectivity.  The 3-by-3 connectivity matrix below says that a\r\n% pixel has only two neighbors: The pixel above and the pixel\r\n% below.\r\n\r\nconn2 = [ 0 1 0\r\n          0 1 0\r\n          0 1 0 ];\r\n\r\nperim2 = bwperim(bw, conn2)\r\n\r\n%%\r\n% Note that the (4,2) and (4,6) pixels are not considered to be\r\n% perimeter pixels with this connectivity.  That's because their\r\n% upper and lower neighbors are both part of the foreground, not\r\n% the background.\r\n%\r\n% Sometimes it's useful to define 6-connectivity.  There are two\r\n% different flavors, both of which can be expressed using the\r\n% 3-by-3 matrix form:\r\n\r\nconn6a = [ 1 1 0\r\n           1 1 1\r\n           0 1 1 ];\r\n       \r\nconn6b = [ 0 1 1\r\n           1 1 1\r\n           1 1 0 ];\r\n       \r\n%%\r\n% For processing three-dimensional arrays, you specify\r\n% 6-connectivity (face-adjacent pixels), 18-connectivity (face-\r\n% or edge-adjacent pixels), or 26-connectivity (face-, edge-, or\r\n% vertex-adjacent pixels).  But you can specify your own flavor\r\n% of connectivity by using a 3-by-3-by-3 matrix.  Here's an\r\n% example.\r\n\r\nbw_3d = false(5,5,3);\r\nbw_3d(2:4,2:4,:) = true;\r\n\r\n% Label three-dimensional connected components.\r\nL1 = bwlabeln(bw_3d)\r\n\r\n%%\r\n% There's only one three-dimensional connected component.  But\r\n% that's using the default connectivity.  Let's define a\r\n% three-dimensional connectivity such that each pixel has\r\n% neighbors only in the same plane.\r\n\r\nconn_3d = cat(3, zeros(3,3), ones(3,3), zeros(3,3))\r\n\r\n%%\r\n\r\nL2 = bwlabeln(bw_3d, conn_3d)\r\n\r\n%%\r\n% Now there are three connected components, one in each plane of\r\n% the array.\r\n%\r\n% The Image Processing Toolbox functions |bwlabel|, |bweuler|,\r\n% |bwboundaries|, and |bwtraceboundary| can accept either 4 or 8\r\n% connectivity.\r\n%\r\n% The toolbox functions |bwareaopen|, |bwlabeln|, |bwperim|,\r\n% |bwulterode|, |imclearborder|, |imextendedmax|,\r\n% |imextendedmin|, |imhmax|, |imhmin|, |imimposemin|,\r\n% |imreconstruct|, |imregionalmax|, |imregionalmin|, and\r\n% |watershed| can all accept general 3-by-3 (or higher\r\n% dimensional) connectivity matrices.\r\n%\r\n% Have you used this general connectivity capability before?  If\r\n% so, I'd like to hear about it.\r\n\r\n##### SOURCE END ##### 217519afd68b4a7db2d753ec3153187d\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   The notion of neighbor connectivity is discussed in most image processing textbooks.  Specifically, what is the set of neighbors\r\n      of a pixel?  For example, a commonly-used neighborhood... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2007\/11\/27\/general-connectivity\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[138,88,440,166,352,140,442,444,46,102,404,142,446,448,450,148,438,364,366,288,100,150,130],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/183"}],"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=183"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/183\/revisions"}],"predecessor-version":[{"id":3576,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/183\/revisions\/3576"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}