logo标签列表

如何在Matlab中找到二进制图像中的所有连通组件？

imagematlabimage-processingbinaryconnected-components
10

我一直在尝试使用8个邻域在二进制图像中找到所有连通分量，但不使用函数"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个相连的物体。

1个回答
18
这是图像处理中的一个常见问题。有许多变化，例如在图像中填充区域，或查找属于同一区域的像素。一种常见方法是使用深度优先搜索。思路是从左到右、从上到下遍历图像，在遇到等于1的任何像素时，将其添加到堆栈中。对于堆栈中的每个像素，您都要弹出堆栈，然后查看周围环绕此像素的相邻像素。任何等于1的像素都要添加到堆栈中。您需要保留一个额外的变量，其中包含您已经访问过的像素，不要将它们添加到堆栈中。当堆栈为空时，我们已经找到了整个区域的像素，因此用唯一的ID标记这些像素。然后重复此过程，直到图像中没有区域为止。
因此，假设矩阵存储在A中，这是基本算法：

  1. 初始化一个与 A 大小相同且为逻辑类型的数组。这将记录我们已经检查或访问过的像素。同时初始化一个输出数组 B，全部为零，用于获取您正在寻找的所有连通组件。最终值为零的任何位置都不属于任何连通组件。还要初始化一个 ID 计数器，以跟踪每个这些连接组件标签的连通组件。

  2. 对于矩阵中的每个位置：

    a. 如果该位置为 0，则将此位置标记为已访问并继续。

    b. 如果我们已经访问了此位置，则继续。

    c. 如果我们尚未访问此位置... 转到第 3 步。

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

    a. 只要此堆栈不为空...

    b. 弹出该位置的堆栈。

    c. 如果我们已经访问了此位置，则继续。

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

    e. 给定此位置，请查看 8 个相邻的像素。

    f. 删除此列表中已访问、不等于 1 或越界的像素。

    g. 剩下的位置，将这些添加到堆栈中。

  4. 一旦堆栈为空，请增加计数器，然后返回第 2 步。

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

不再拖延，这是代码。

%// 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的结果：
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连通区域中搜索，即仅在北、东、西和南方向上搜索，您需要查看以下部分：%// Look at the 8 neighbouring locations，即：

 %// 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个连接方式搜索，您只需修改此代码，仅提供那些基本方向即可：

 %// 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函数

如果您想要匹配 MATLAB 的 bwlabel 函数输出，bwlabel 按列主序或 FORTRAN 顺序搜索连接的组件。上面的代码按行主序或 C 顺序搜索。因此，您只需要首先沿着列而不是行搜索，这可以通过交换两个 for 循环的顺序来实现。

具体来说，替代执行以下操作：

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

你会做：

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

现在应该复制bwlabel的输出。

2
你的代码太棒了，它做了我真正想要的事情。虽然有点难以理解，但我懂了，你是一位优秀的程序员，再次感谢你。 - Pepe López
好代码。你能告诉我如何在数组中显示图形中的所有路径吗？例如：一个路径看起来像这样：path_1 =[3,2,6,7,4,8,5]; - kgk
@kgk，我不知道你在问什么。请使用我在上面回答中给出的示例，告诉我期望的输出结果。 - rayryeng
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接