如何在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.

事不宜迟，代码如下.

%// 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-connected 的方式搜索，您只需修改此代码以仅给出这些基本方向:

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 按列主要或 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.

具体来说，不要做:

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屋！