The notion of neighbor connectivity is discussed in most image processing textbooks. Specifically, what is the set of neighbors of a pixel? For example, a commonly-used neighborhood connectivity is 4-connected, where each pixel has four neighbors. The neighborhood looks like this:
1 1 1 1 1
Another common connectivity is 8-connected, where each pixel has eight neighbors. The neighborhood looks like this:
1 1 1 1 1 1 1 1 1
Many Image Processing Toolbox functions depend on a definition of connectivity. Most of these functions allow you to specify the desired connectivity in a very general, flexible way.
Consider bwperim. This function computes perimeter pixels by finding the foreground pixels that are connected to background pixels. Some definition of connectivity is therefore required. Let's look at an example.
bw = [ 0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0 ];Find the foreground pixels that are 4-connected to the background.
perim4 = bwperim(bw, 4)
perim4 =
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 0
0 1 0 0 0 1 0
0 1 0 0 0 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
Now find the foreground pixels that are 8-connected to the background.
perim8 = bwperim(bw, 8)
perim8 =
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 1 0 1 1 0
0 1 0 0 0 1 0
0 1 1 0 1 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
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 of connectivity. The 3-by-3 connectivity matrix below says that a pixel has only two neighbors: The pixel above and the pixel below.
conn2 = [ 0 1 0
0 1 0
0 1 0 ];
perim2 = bwperim(bw, conn2)
perim2 =
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0
0 1 0 0 0 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
Note that the (4,2) and (4,6) pixels are not considered to be perimeter pixels with this connectivity. That's because their upper and lower neighbors are both part of the foreground, not the background.
Sometimes it's useful to define 6-connectivity. There are two different flavors, both of which can be expressed using the 3-by-3 matrix form:
conn6a = [ 1 1 0
1 1 1
0 1 1 ];
conn6b = [ 0 1 1
1 1 1
1 1 0 ];For processing three-dimensional arrays, you specify 6-connectivity (face-adjacent pixels), 18-connectivity (face- or edge-adjacent pixels), or 26-connectivity (face-, edge-, or vertex-adjacent pixels). But you can specify your own flavor of connectivity by using a 3-by-3-by-3 matrix. Here's an example.
bw_3d = false(5,5,3);
bw_3d(2:4,2:4,:) = true;
% Label three-dimensional connected components.
L1 = bwlabeln(bw_3d)
L1(:,:,1) =
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
L1(:,:,2) =
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
L1(:,:,3) =
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
There's only one three-dimensional connected component. But that's using the default connectivity. Let's define a three-dimensional connectivity such that each pixel has neighbors only in the same plane.
conn_3d = cat(3, zeros(3,3), ones(3,3), zeros(3,3))
conn_3d(:,:,1) =
0 0 0
0 0 0
0 0 0
conn_3d(:,:,2) =
1 1 1
1 1 1
1 1 1
conn_3d(:,:,3) =
0 0 0
0 0 0
0 0 0
L2 = bwlabeln(bw_3d, conn_3d)
L2(:,:,1) =
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
L2(:,:,2) =
0 0 0 0 0
0 2 2 2 0
0 2 2 2 0
0 2 2 2 0
0 0 0 0 0
L2(:,:,3) =
0 0 0 0 0
0 3 3 3 0
0 3 3 3 0
0 3 3 3 0
0 0 0 0 0
Now there are three connected components, one in each plane of the array.
The Image Processing Toolbox functions bwlabel, bweuler, bwboundaries, and bwtraceboundary can accept either 4 or 8 connectivity.
The toolbox functions bwareaopen, bwlabeln, bwperim, bwulterode, imclearborder, imextendedmax, imextendedmin, imhmax, imhmin, imimposemin, imreconstruct, imregionalmax, imregionalmin, and watershed can all accept general 3-by-3 (or higher dimensional) connectivity matrices.
Have you used this general connectivity capability before? If so, I'd like to hear about it.
Get
the MATLAB code
Published with MATLAB® 7.5
Hi Steve,
Thanks for the great blog, and hope you keep this up. I have a question about the bwperim - connectivity example here. When I try this simple code:
conn1 = 4
A = [0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0]
B = bwperim(A,conn1)
I get the resulting perim matrix B:
B =
0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Ideally A(1,4), A(1,5) and A(1,6) shouldn’t be perimeter pixels. Is there some way to get the right perimeter? Thanks in advance!
Harun—There is an implicit assumption in bwperim that pixels “outside” the image are background pixels. That’s why A(1,4:6) are identified as perimeter pixels. You could get your desired result by prepadding the boundary with ones using padarray.
Tried it and works like a charm. But there’s the additional hassle of removing the pads once bwperim does its work, hope this can be addressed in future versions. Thanks a lot Steve!
hey Steve,
thanks for your great blog. i had a question extending the general connectivity (perhaps we could call it specific connectivity?:)
can you think of a way to extend bwperim (or any function or set of functions) to connect open objects, such as the incomplete perimeters of circles? for example, let’s say i have the following matrix, and i want to complete the circle… perhaps by recursively checking for 8-pixel connectivity. any ideas?
circperim = bwperim(fspecial(’disk’,8)>0);
circperim(1:5,1:5) = zeros(5);
imshow(circperim);
0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
thanks!
dave
Dave—I think you’re pushing the idea of pixel connectivity way past where it was meant to go. :-) You might try using a Hough circle detection algorithm. Some of these do a good job detecting partial circles. Once you have the center and radius, you can fill in the perimeter pixels.