How to find all connected components in a binary image in Matlab?

Question

I am trying to find all connected components using 8 neighbors in a binary image, without using the "bwlabel" function.

For example, my input matrix:

a = 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 

I would have something like this:

 a = 1 1 0 0 0 0 0 1 1 0 0 2 2 0 1 1 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 

There are 3 related objects in this image.

Answer 1

This is a common problem when processing images. There are many options, such as a flood filling a region in an image, or finding which pixels belong to the same region. One general approach is to use the depth of the first search . The idea is that you move the image from left to right and from top to bottom, and for any encountered pixels equal to 1, you add them to the stack. For each pixel in your stack, you delete the stack, and then look at the neighboring pixels surrounding that pixel. Any pixels you add to the stack. You need to save an additional variable, where all the pixels that you have already visited , you do not add them to the stack. When the stack is empty, we found those pixels that are the whole region, so you mark them with a unique identifier. Then repeat this procedure until regions are highlighted in your image.

Thus, given that your matrix is ​​stored in A , this is the main algorithm:

• Initialize an array whose size is A logical . This will record which pixels we examined or visited. Also initialize the output array B to all zeros, which gives you all the connected components you are looking for. Any locations that are ultimately zero do not belong to any related components. Also, initialize an ID counter that keeps track of which related component label each of them has.

• For each location that is in our matrix:

  a. If location 0 , mark this location as visited and continue.

  b. If we have already visited this place, continue.

  with. If we have not visited this place ... go to step 3.

• Add this invisible space to the stack.

  a. Although this stack is not empty ...

  b. Put this location from the stack.

  with. If we visited this place, we will continue.

  d. Else, mark this location as visited and mark this location with the identifier of the connected components.

  e. Given this location, look at 8 adjacent pixels.

  f. Delete those pixels in this list that were visited, but not equal to 1 or outside the borders of the matrix

  d. Regardless of location, add them to the stack.

• Once the stack is empty, increase the counter, and then return to step # 2.

• Continue driving until we visit all locations in our array.

Without further ado, here is the code.

---

 %// Step #1 visited = false(size(A)); [rows,cols] = size(A); B = zeros(rows,cols); ID_counter = 1; %// Step 2 %// For each location in your matrix... for row = 1 : rows for col = 1 : cols %// Step 2a %// If this location is not 1, mark as visited and continue if A(row,col) == 0 visited(row,col) = true; %// Step 2b %// If we have visited, then continue elseif visited(row,col) continue; %// Step 2c %// Else... else %// Step 3 %// Initialize your stack with this location stack = [row col]; %// Step 3a %// While your stack isn't empty... while ~isempty(stack) %// Step 3b %// Pop off the stack loc = stack(1,:); stack(1,:) = []; %// Step 3c %// If we have visited this location, continue if visited(loc(1),loc(2)) continue; end %// Step 3d %// Mark location as true and mark this location to be %// its unique ID visited(loc(1),loc(2)) = true; B(loc(1),loc(2)) = ID_counter; %// Step 3e %// Look at the 8 neighbouring locations [locs_y, locs_x] = meshgrid(loc(2)-1:loc(2)+1, loc(1)-1:loc(1)+1); locs_y = locs_y(:); locs_x = locs_x(:); %%%% USE BELOW IF YOU WANT 4-CONNECTEDNESS % See bottom of answer for explanation %// Look at the 4 neighbouring locations % locs_y = [loc(2)-1; loc(2)+1; loc(2); loc(2)]; % locs_x = [loc(1); loc(1); loc(1)-1; loc(1)+1]; %// Get rid of those locations out of bounds out_of_bounds = locs_x < 1 | locs_x > rows | locs_y < 1 | locs_y > cols; locs_y(out_of_bounds) = []; locs_x(out_of_bounds) = []; %// Step 3f %// Get rid of those locations already visited is_visited = visited(sub2ind([rows cols], locs_x, locs_y)); locs_y(is_visited) = []; locs_x(is_visited) = []; %// Get rid of those locations that are zero. is_1 = A(sub2ind([rows cols], locs_x, locs_y)); locs_y(~is_1) = []; locs_x(~is_1) = []; %// Step 3g %// Add remaining locations to the stack stack = [stack; [locs_x locs_y]]; end %// Step 4 %// Increment counter once complete region has been examined ID_counter = ID_counter + 1; end end %// Step 5 end 

With your sample matrix, this is what I get for B :

 B = 1 1 0 0 0 0 0 1 1 0 0 2 2 0 1 1 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 

---

To search in a 4-connected neighborhood

To change the code for searching in a four-connected region, that is, only North, East, West and South, the section where you see %// Look at the 8 neighbouring locations , that is:

  %// Look at the 8 neighbouring locations [locs_y, locs_x] = meshgrid(loc(2)-1:loc(2)+1, loc(1)-1:loc(1)+1); locs_y = locs_y(:); locs_x = locs_x(:); 

To search for 4-related mods, you just need to change this code to give only those main directions:

  %// Look at the 4 neighbouring locations locs_y = [loc(2)-1; loc(2)+1; loc(2); loc(2)]; locs_x = [loc(1); loc(1); loc(1)-1; loc(1)+1]; 

The rest of the code remains untouched.

To match MATLAB bwlabel function

If you want to combine the output of the MATLAB function bwlabel , bwlabel searches for connected components in the main or FORTRAN column. The above code searches in line by line or in order. So you just need to search the columns first, not the rows, as what the above code does, and you do this by replacing the order of the two for loops.

In particular, instead of executing:

 for row = 1 : rows for col = 1 : cols .... .... 

You would do:

 for col = 1 : cols for row = 1 : rows .... .... 

Now this should repeat the output of bwlabel .