（来点有⽤的）MATLAB⼆值图连通域快速标记算法
by HPC_ZY
由于⼯程需要，⽤C++实现三维⼆值图像的连通域标记。像往常⼀样拿起冈萨雷斯《数字图像处理（第三版）》，按照算法原理先实现⼆维再改成三维。⽤（256,256,256）数据测试，根本停不下来（尴尬）。因此明⽩⼀个道理，在⼀定程度上 “经典” = “效率低” = “不考虑时间复杂度和空间复杂度”…… 故上⽹查阅资料，学习快速算法，并记录在此分享给⼤家。
基本原理
连通域标记的本质就是把所有块出来，并设置不同的编号。
主要步骤：
1）遍历图像到种⼦点
2）区域⽣长到区域Ni
3）记录，并在原图中删去区域Ni
4）重复1~3直⾄原图没有值为1的像素
参考⽂献《⼀种⼆值图像连通区域标记的简单快速算法》-葛春平
算法实现
0. 变量解释
[M,N]=size(bw);%⼆值图像与尺⼨
label =zeros(M,N);%标记结果
class =0;%类别
stopflag =0;%停⽌标记
sp =1;%遍历起始点
stack =zeros(M*N,2,'uint32');%缓存栈
stackidx =0;%栈索引
neib =[-1,0;0,-1;1,0;0,1];%邻域偏移坐标
1.种⼦点搜索
1. 不好的索引⽅式（不使⽤）
两重循环，且需要利⽤flag才能退出外层循环
%%%%%%%%%%%%%%%%%%%%不使⽤以下代码%%%%%%%%%%%%%%%%%%%
flag =0;
for i =1:M
for j =1:N
if bw(i,j)
x = i;
y = j;水性润滑剂
flag =1;
圣贞德女子学院
break
end
end
if flag
break
end
end
2. 好的索引⽅式，不好的搜索⽅式（不使⽤）
利⽤单层循环，通过计算获得⼆维坐标。反复测试可提速2~4倍。
%%%%%%%%%%%%%%%%%%%%不使⽤以下代码%%%%%%%%%%%%%%%%%%%
for k =1:M*N
if bw(k)
y =ceil(k/M);
x = k-(y-1)*M;
break
end
end
3. 好的搜索⽅式
显⽽易见，已经搜索过的地⽅不可能再出现种⼦点。
连通域越多，重复次数就越多，如果每次都从（1,1）开始搜索则浪费时间。
因此我们每次迭代都从上⼀种⼦点之后开始搜索，时间复杂度为O(n)。
sp =1;
for k = sp:M*N
if bw(k)
y2 =ceil(k/M);
笛卡尔我思故我在
x2 = k-(y2-1)*M;
sp = k+1;
break
end
end
2 区域⽣长
⽅法很多，这⾥不做对⽐。我们⽤空间换时间，牺牲内存消耗来减少时间开销。
⽅法如下：
1）建⽴⼀个⼤⼩为NUM2数组stack 来保存等待⽣长的点的坐标（NUM的值有图像⼤⼩决定，我取的M N），并设置⼀个索引记录当前缓存点的个数stackidx；
2）到种⼦点，放在数组第⼀⾏，并令stackidx加1；
3）对stack中第stackidx⾏的点进⾏四领域⽣长，在stack中删去stackidx⾏的点，同时stackidx减1；然后将新得到的点加⼊stack，同时stackidx加1。
注意：每次到⽬标点都要在原图中置0，并在结果图中标号。
neib =[-1,0;0,-1;1,0;0,1]; stackidx =0；
while stackidx
x =stack(stackidx,1);
y =stack(stackidx,2);
stackidx = stackidx-1;
for n =1:4
dx = x+neib(n,1);
dy = y+neib(n,2);
if bw(dx,dy)
stackidx = stackidx+1;
stack(stackidx,:)=[dx,dy];
bw(dx,dy)=0;
label(dx,dy)= class;
end
end
end
完整代码
function label =label2d(bw)
[M,N]=size(bw);
label =zeros(M,N);%分类结果
class =0;%类别
stopflag =0;%停⽌标记
sp =1;%遍历起始点
stack =zeros(M*N,2,'uint32');%缓存栈stackidx =0;%栈索引
neib =[-1,0;0,-1;1,0;0,1];%邻域偏移坐标
while1
%寻种⼦点
for k = sp:M*N
if bw(k)
y =ceil(k/M);
x = k-(y-1)*M;
stackidx = stackidx+1;
stack(stackidx,:)=[x,y];
class = class+1;
label(x,y)= class;
bw(x,y)=0;
sp = k+1;
break
end
if k == M*N %达到图像末端
stopflag =1;
end
end
%结束
if stopflag
break
end
%连通域
while stackidx
x =stack(stackidx,1);
y =stack(stackidx,2);
stackidx = stackidx-1;
for n =1:4
dx = x+neib(n,1);
dy = y+neib(n,2);
if bw(dx,dy)
stackidx = stackidx+1;
stack(stackidx,:)=[dx,dy];
grid service
bw(dx,dy)=0;
label(dx,dy)= class;
end内蒙古民族高等专科学校
end
end
end
end
实验
对于连通域标记，MATLAB有库函数
% CC输出，BW⼆值图，CONN连通⽅式CC =BWCONNCOMP(BW,CONN)；
其输出为⼀结构体，内容分别为：连通⽅式，图像尺⼨，连通域数量，像素索引列表。要获得标记图像还需进⾏操作，在下⾯测试中演⽰：load bw2
%库函数
tic
label1tmp =bwconncomp(bw2,4);
label1 =zeros(size(bw2));
for k =1:label1tmp.NumObjects
label1(label1tmp.PixelIdxList{k})= k;
end
t1 = toc;
%⾃函数
tic
label2 =label2d(bw2);
t2 = toc;
figure
subplot(131),imagesc(bw2),title('原图')
subplot(132),imagesc(label1),title('库函数'),xlabel(t1)
subplot(133),imagesc(label2),title('⾃函数'),xlabel(t2)
colormap jet
通过实验结果可以看出，两者输出完全⼀致，库函数在速度上还是更胜⼀筹。但相⽐于教材上的经典算法，⾃函数速度已经提升百倍以上，尤其是在三维数据上（不做测试）。
其他
1. 在种⼦点搜索和四邻域判断中，都使⽤了单层循环代替双层循环，以提⾼了计算速度。（对于三维图像效果更明显）
2. 三维连通域标记只是从⼆维数组变为三维数组，⽐较简单，⼤家可在上述代码基础上加⼊第三维（z）即可。
3. 由于C语⾔与MATLAB在数组存储上⾏列相反，所以改写为C语⾔时种⼦点搜索中坐标x,y要互换。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议