这是图像处理中的一个常见问题。有许多变化,例如在图像中填充区域,或查找属于同一区域的像素。一种常见方法是使用
深度优先搜索。思路是从左到右、从上到下遍历图像,在遇到等于1的任何像素时,将其添加到堆栈中。对于堆栈中的每个像素,您都要弹出堆栈,然后查看周围环绕此像素的相邻像素。任何等于1的像素都要添加到堆栈中。您需要保留一个额外的变量,其中包含您已经访问过的像素,不要将它们添加到堆栈中。当堆栈为空时,我们已经找到了整个区域的像素,因此用唯一的ID标记这些像素。然后重复此过程,直到图像中没有区域为止。
因此,假设矩阵存储在
A
中,这是基本算法:
初始化一个与 A
大小相同且为逻辑类型的数组。这将记录我们已经检查或访问过的像素。同时初始化一个输出数组 B
,全部为零,用于获取您正在寻找的所有连通组件。最终值为零的任何位置都不属于任何连通组件。还要初始化一个 ID 计数器,以跟踪每个这些连接组件标签的连通组件。
对于矩阵中的每个位置:
a. 如果该位置为 0
,则将此位置标记为已访问并继续。
b. 如果我们已经访问了此位置,则继续。
c. 如果我们尚未访问此位置... 转到第 3 步。
将此未访问的位置添加到堆栈中。
a. 只要此堆栈不为空...
b. 弹出该位置的堆栈。
c. 如果我们已经访问了此位置,则继续。
d. 否则,将此位置标记为已访问,并使用连接组件 ID 标记此位置。
e. 给定此位置,请查看 8 个相邻的像素。
f. 删除此列表中已访问、不等于 1 或越界的像素。
g. 剩下的位置,将这些添加到堆栈中。
一旦堆栈为空,请增加计数器,然后返回第 2 步。
继续进行,直到我们访问了数组中的所有位置。
不再拖延,这是代码。
visited = false(size(A));
[rows,cols] = size(A);
B = zeros(rows,cols);
ID_counter = 1;
for row = 1 : rows
for col = 1 : cols
if A(row,col) == 0
visited(row,col) = true;
elseif visited(row,col)
continue;
else
stack = [row col];
while ~isempty(stack)
loc = stack(1,:);
stack(1,:) = [];
if visited(loc(1),loc(2))
continue;
end
visited(loc(1),loc(2)) = true;
B(loc(1),loc(2)) = ID_counter;
[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(:);
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) = [];
is_visited = visited(sub2ind([rows cols], locs_x, locs_y));
locs_y(is_visited) = [];
locs_x(is_visited) = [];
is_1 = A(sub2ind([rows cols], locs_x, locs_y));
locs_y(~is_1) = [];
locs_x(~is_1) = [];
stack = [stack; [locs_x locs_y]];
end
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
在4连通邻域中搜索
要修改代码以在4连通区域中搜索,即仅在北、东、西和南方向上搜索,您需要查看以下部分:%// 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个连接方式搜索,您只需修改此代码,仅提供那些基本方向即可:
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
的输出。