我几乎完全就是照着WIKI百科上的算法实现的，不过是用Matlab而已。使用了两步法进行标记，一步法我还没怎么看。两步法中第二步是比较麻烦的，其中用到了不相交集合的一些理论，尤其是不相交集合森林，我这里的find_set函数就是参考《算法导论》311页的算法写的。如果用c++写，也许需要自己构造数据结构。
好吧，下面是我理解的算法过程：
1.首先要确定是标记8邻域连通还是4邻域连通，如果是8邻域连通，就用的模板，如果是4邻域连通，就用的模板。我这里用了是8连通。
2.用模板变量图像，类似卷积，不过不计算，只比较。比较当前像素和邻域4个或2个像素，如果都不相等，那么标记号加一，并且把这个标记号赋值给另一个标记空间中相同位置的像素，因为不能破坏当前图像的像素。如果有一个相等，那么就把这4个或2个像素中非背景像素中的最小值赋给另一个标记空间相同位置的像素，并且把这4个或2个像素同有相同当前位置像素值的集合取并集（ps:这个真的好难解释--!!）。遍历完会得到标记图像和有标记号那么多个的标记集合。
3.遍历标记图像，按标记图像的像素值索引标记集合，找到标记集合中代表当前集合最小的值赋值给原图像当前位置的像素（ps:这里最好看《算法导论》或这里）。
还是看代码吧，运行一下更好：
main.m
1 clear all;
2 close all;
3 clc;
4
5 img=imread(\'liantong.bmp\');
6 imgn=img>128;
7 s=uint8(1-imgn);
8
9 %{
10 s=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
11 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0; %这个矩阵是维基百科中的矩阵
12 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0;
13 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0;
14 0 0 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0;
15 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0;
16 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0;
17 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0;
18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
19 %}
20 imshow(mat2gray(s));
21 [m n]=size(s);
22 tmp=zeros(m,n);
23 label=1; %第一遍遍历时标记的标签数量
24 for i=2:m
25 for j=2:n-1
26 up_left=s(i-1,j-1); %原图像当前像素周围四个像素
27 up=s(i-1,j);
28 up_right=s(i-1,j+1);
29 left=s(i,j-1);
30 cur=s(i,j);
31
32 if cur==1
33 if cur~=up_left && cur~=up &&cur~=up_right &&cur~=left %当前和四周的都不一样，加新标签
34 tmp(i,j)=label;
35 link{label}=[];
36 label=label+1;
37 else
38 t=sort([tmp(i,j-1) tmp(i-1,j-1) tmp(i-1,j) tmp(i-1,j+1)]); %标签图像当前像素周围四个像素并排序
39 for k=1:4 %寻找周围四个像素非零的最小值赋值给标签图像
40 if t(k)~=0
41 tmp(i,j)=t(k);
42 for w=k:4
43 link{t(w)}=union(t(k:4),link{t(w)}); %设置不相交集合
44 end
45 break;
46 end
47 end
48 end
49 end
50
51 end
52 end
53
54 for i=1:m
55 for j=1:n
56 if s(i,j) ~=0
57 s(i,j)=find_set(link,tmp(i,j));
58 end
59 end
60 end
61 figure,imshow(mat2gray(s))
find_set.m
1 function re=find_set(p,i) %不相交集合寻找代表当前集合的最小值，详见《算法导论》第21章
2 if min(p{i}) ~= i
3 i=find_set(p,min(p{i}));
4 end
5 re=i;
6 end
下面是运行的结果：
原图
结果图
效果还不错吧。
