如何在 Matlab 中找到二进制图像中的所有连通分量? [英] How to find all connected components in a binary image in Matlab?

问题描述

我一直在尝试使用二进制图像中的 8 个邻居来查找所有连接的组件，而不使用函数bwlabel".

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

比如我的输入矩阵是:

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

我想要这样的东西:

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

此图像中有 3 个连接的对象.

There are 3 connected objects in this image.

推荐答案

这是图像处理中的常见问题.有许多变化，例如填充图像中的区域，或者查找哪些像素属于同一区域.一种常见的方法是使用深度优先搜索.这个想法是你从左到右和从上到下遍历你的图像，对于遇到的任何等于 1 的像素，你将它们添加到堆栈中.对于堆栈中的每个像素，从堆栈中弹出，然后查看围绕该像素的相邻像素.您添加到堆栈中的任何 1 像素.您需要在您已经访问过的任何像素处保留一个附加变量，不要将它们添加到堆栈中.当堆栈为空时，我们已经找到了整个区域的那些像素，因此您使用唯一 ID 标记这些像素.然后重复此过程，直到图像中的区域用完为止.

This is a common problem in image processing. There are many variations, such as flood filling a region in an image, or finding what pixels belong to the same region. One common approach is to use depth first search. The idea is that you traverse your image from left to right and top to bottom and for any pixels encountered that are equal to 1, you add them to a stack. For each pixel in your stack, you pop off the stack, then look at the neighbouring pixels that are surrounding this pixel. Any pixels that are 1 you add to the stack. You need to keep an additional variable where any pixels you have already visited, you don't add these to the stack. When the stack is empty, we have found those pixels that are an entire region, so you mark these with a unique ID. You then repeat this procedure until you run out of regions in your image.

因此，鉴于您的矩阵存储在 A 中，这是基本算法:

As such, given that your matrix is stored in A, this is the basic algorithm:

1. 初始化一个与 A 大小相同的数组，即 logical.这将记录我们检查或访问过的像素.还将输出数组 B 初始化为全零，为您提供您正在寻找的所有连接组件.任何最终为零的位置都不属于任何连通分量.还要初始化一个 ID 计数器，用于跟踪每个连接组件的标签.

1. Initialize an array that's the same size as A that is logical. This will record which pixels we have examined or visited. Also initialize an output array B to all zeroes that gives you all of the connected components that you are seeking. Any locations that are zero in the end don't belong to any connected components. Also initialize an ID counter that keeps track of what connected component label each of these will have.

对于我们矩阵中的每个位置:

For each location that's in our matrix:

一个.如果位置是 0，则将此位置标记为已访问并继续.

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

b.如果我们已经访问过这个位置，那么继续.

b. If we have already visited this location, then continue.

c.如果我们还没有访问过这个位置...转到第 3 步.

c. If we have not visited this location... go to Step #3.

将此未访问的位置添加到堆栈中.

Add this unvisited location to a stack.

一个.虽然这个堆栈不是空的......

a. While this stack is not empty...

b.从堆栈中弹出这个位置

b. Pop this location off of the stack

c.如果我们访问过此位置，请继续.

c. If we have visited this location, then continue.

d.否则，将此位置标记为已访问并使用连接组件 ID 标记此位置.

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

e.给定这个位置，查看 8 个相邻像素.

e. Given this location, look at the 8 neighbouring pixels.

f.移除这个列表中那些被访问过的像素，不等于1或者超出矩阵的范围

f. Remove those pixels in this list that have been visited, not equal to 1 or out of bounds of the matrix

g.无论剩下什么位置，都将它们添加到堆栈中.

g. Whatever locations are remaining, add these to the stack.

一旦堆栈为空，递增计数器，然后返回步骤#2.

Once the stack is empty, increment the counter, then go back to Step #2.

继续前进，直到我们访问了数组中的所有位置.

Keep going until we have visited all of the locations in our array.

废话不多说，代码如下.

Without further ado, here's 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   

使用您的示例矩阵，这就是我为 B 得到的:

With your example 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

<小时>

在 4 连接的社区中搜索

修改代码以在4个连通区域中搜索，即只有北、东、西、南，看到%//查看8个相邻位置的部分，即是:

 %// 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(:);

要以 4 连接方式进行搜索，您只需修改此代码以仅给出这些基本方向:

To search in a 4-connected fashion, you simply have to modify this code to only give those cardinal 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];

其余代码保持不变.

如果你想匹配 MATLAB 的 bwlabel 函数，bwlabel 以列major 或FORTRAN 顺序搜索连通分量.上面的代码按行主要或 C 顺序搜索.因此，您只需首先搜索列而不是行，就像上面的代码所做的那样，您可以通过交换两个 for 循环的顺序来做到这一点.

If you want to match the output of MATLAB's bwlabel function, bwlabel searches for connected components in column major or FORTRAN order. The above code searches in row major or C order. Therefore you simply have to search along columns first rather than rows as what the above code is doing and you do this by swapping the order of the two for loops.

具体来说，而不是这样做:

Specifically, instead of doing:

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

你会这样做:

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

现在应该会复制 bwlabel 的输出.

This should now replicate the output of bwlabel.

这篇关于如何在 Matlab 中找到二进制图像中的所有连通分量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！