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

例如，我的输入矩阵是：

For example, my input matrix is:

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 to 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

有此图像中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 是逻辑相同。这将记录哪些像素我们检查或视察。同时初始化输出数组 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. If we have already visited this location, then continue.

℃。如果我们没有访问过这个位置......转到步骤＃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...

乙。弹出这个位置离堆

℃。如果我们参观了这个位置，然后再继续。

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

Ð。否则，纪念这一位置访问并标记与所连接的组件ID这个位置。

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

即鉴于此位置，看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. 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.

事不宜迟，这里的code。

Without further ado, here's the code.

%// Step #1
visited = false(size(A));
[rows,cols] = size(A);
B = zeros(rows,cols);
ID_counter = 1;

%// For each location in your matrix...
for row = 1 : rows
    for col = 1 : cols
        %// If this location is not 1, mark as visited and continue
        if A(row,col) == 0
            visited(row,col) = true;

        %// If we have visited, then continue
        elseif visited(row,col)
            continue;

        %// Else...
        else
            %// Initialize your stack with this location
            stack = [row col];

            %// While your stack isn't empty...
            while ~isempty(stack)
                %// Pop off the stack
                loc = stack(1,:);
                stack(1,:) = [];

                %// If we have visited this location, continue
                if visited(loc(1),loc(2))
                    continue;
                end

                %// 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;

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

                %// 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) = [];

                %// 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) = [];

                %// Add remaining locations to the stack
                stack = [stack; [locs_x locs_y]];
            end

            %// Increment counter once complete region has been examined
            ID_counter = ID_counter + 1;
        end
    end
 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

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