基于近邻传播和区域融合的彩色图像分割算法

王 磊

（商洛学院 现代教育技术中心，陕西商洛 726000）

2007年Frey&Dueck在Science提出了一种新的聚类算法：近邻传播聚类（Affinity Propagation，简称AP），其主要优势体现在无须事先确定聚类数（与k-means不同），而是根据数据自身的特性自动聚类到合适的数目。AP算法已经被实验证明效果要优于K均值算法[1]。例如，对数千个手写的邮政编码的图片，AP算法只花很短的时间就可以聚类到少量代表各种笔迹类型的手写图片，而K-means算法要达到同样精度要耗费500万年[2]。该算法已在医学图像处理[3]、路线搜索和选址[4]、基因外显子发现、图像搜索[5]等方面得到了应用。但是传统AP算法在实际应用中仍然存在一些问题，如：该算法的空间复杂度和时间复杂度严重受制于样本个数，因此导致传统AP算法无法处理大规模数据，特别是大规模图像分割问题[6]。由此，本文提出了一种基于近邻传播聚类的彩色图像分割算法。包括三部分：图像预处理过程，将RGB颜色空间彩色图像变换到CIE L*u*v*颜色空间彩色图像，目的是采用更符合人类视觉感受颜色空间，并进一步解除R、G、B三分量的相关性；基于给定数目的近邻传播聚类（APGNC）的图像分割，目的是获得整幅图像的分割结果；图像后处理过程，利用区域合并方法修正图像的分割结果，目的是保证最终分割目标的整体性，去除目标区域内的错分或者误分的部分。

1 彩色图像预处理过程

目前表达彩色的颜色空间已经有很多种不同的形式（即：颜色空间）：RGB、HSL、HSV、CIE L*u*v*以及CIE L*a*b*。现在应用最为广泛的颜色空间是RGB，这种颜色空间虽然简单不需要转换，但R、G、B三分量之间有很高的相关性，这对于图像分割是不利的。CIE L*u*v*颜色空间是根据人眼视觉系统构造的，L*分量表示亮度，u*v*共同表示某种颜色，它可以表示所有人眼可以看见的颜色，同时也包括一些物理世界不能再现的颜色。另外，它对应的饱和度线和色调线近似于线性变换，可以很好地改善了视觉非正规的问题。因此，在图像分割前需要将以RGB形式描述的彩色图像转换为CIE L*u*v*颜色系统中的彩色图像，进而进行分析和处理。转换过程如公式(1)-(3)所示。

RGB颜色空间先转换到XYZ颜色空间

CIE L*u*v*的计算公式[7]

其中

Y0为XYZ空间中白色对应的颜色分量，Y0、u0、v0为 CIE L*u*v*中白色对应的三个颜色分量[8]。

2 基于A P的图像分割

在利用AP算法进行图像分割时，想要降低算法的时间复杂度和空间复杂度通常有两种方法：一种是采用稀疏相似性传播聚类[9]；另一种是将图像划分成互不重叠的子图，并将子图作为数据点进行聚类[10]。这两种方法虽然都能够一定程度上降低算法的空间和时间复杂度，但是算法本身复杂度较高、不易实现[6]，且不能从根本上加快聚类的速度。

现有实验已经证明在普通PC下（matlab环境），AP算法中样本个数一般被限制在3000以内[11]，显然这在实际应用中有很大弊端；而本文通过选取适当的采样率，可以大大扩展AP算法在图像分割中的应用。

本文对经过预处理的彩色图像，进行初始近邻传播聚类。包括三个步骤：首先，对彩色图像进行数据采样（包括自动均匀采样和手工标定采样）；然后，对采样数据进行给定聚类数目的近邻传播聚类（APGNC），获得相应的聚类中心；最后，根据最大相似度规则，计算其余未采样数据点的类标签。

2.1 对彩色图像进行数据采样

2.1.1 自动均匀采样

利用均匀采样方法对整幅图像进行数据采样，设置采样率rate，其范围为[0,1]，具体做法是每间隔1/rate个点采样一次。显然，采样率越高，采样数据就越少，图像分割的时间就越短，聚类效果也就越差；反之亦然。因此，综合考虑算法的效果和效率，通过改变采样率rate，把采样数据控制在300-2000为宜，以保证聚类过程的高效。

2.1.2 手工标定采样

由于在自动均匀采样中当rate较小时，采样数据之间的间隔（即1/rate）就很大，这样对于一些小目标就存在采样不充分或者直接跳过的情况，因此本文设定当rate小于某个值（默认为1%）时，应当结合人工标定，添加一些感兴趣的区域或小目标点。

2.2 给定聚类数目的APGNC算法

传统AP算法不能像K-means那样在聚类前预知最终聚类数目，即AP算法不能得到指定聚类数目的结果。但是从文献[12]的思想出发，可以通过基于二分法的判断，实现上述目标。

算法： APGNC（Affinity Propagation with Given Number of Cluster）

步骤：

1)初始化AP：人工指定最终聚类数目为DK，偏向参数P为median（S），上界P_high=0,下界P_low=2*P。

2)运行一次经典AP算法：得到聚类数K。

3)进行判断：若K＜DK，说明聚类数目少，应增大P值：P_low=P，得到新的偏向参数P=1/2*(P_low+P_high)，转入 2）；若 K＞DK，说明聚类数目多，应减小P值：P_high=P和P_low=2*P_low，得到新的偏向参数P=1/2*(P_low+P_high)，转入2）；若K=DK，说明达到给定的聚类数目，转入 4）。

4)输出聚类结果，算法结束。

2.3 判断未采样数据的类标签

采样数据经过APGNC聚类后获得了相应的类归属，而其余的未采样数据仍然没有类归属。因此，要将采样数据聚类的结果扩展到其他未采样数据，具体做法如下：

计算未采样数据与各聚类中心点之间的相似度，然后按照最大相似度原则，为它们赋予相应的类标签Cx：

其中，Ci表示经APGNC聚类得到的第i个聚类中心，i=1,2，…，DK。

3 图像分割的后处理

由于只在彩色图像的颜色特征上聚类，没有考虑像素点的空间信息，因此彩色图像经过AP算法初始分割后，较容易产生了面积较小的独立区域或孤立点。区域合并就是将两个在空间上相邻，且在颜色上最相近的区域合并为一个区域，用以消除图像分割中琐碎的区域和噪声点的干扰，让分割图像更趋于整体，使分割结果更符合人类的视觉效果。

本文主要利用区域邻接图（RAG），并采用区域的面积和颜色特征来进行区域合并的[13]。这样做主要有两个目的：首先通过区域面积准则，筛选小而孤立的区域或孤立点，作为区域合并的对象区域；接着计算对象区域和与它相邻近的各区域之间的颜色距离，颜色最接近的区域作为将要进行合并的目标区域。最后，通过修改对象区域中数据的类标签，完成区域合并。

区域合并的具体算法步骤：

1)初始化。n 为初始分割区域数，R={r1，r2，…，rn}，且R'=φ。R为合并前的区域集合，R'为合并后的区域集合。rm是第m个区域,m=1,2,…,n。

2)如果ri的面积小于T，那么ri就是对象区域，R=R-ri,i=1,2,…,n.

3)rj=argmin(Dis(ri，rj)|1≤j≤n，rj∈R)，那么 rj就是对象区域。其中：

|ri|，|rj|分别代表第i和第j区域中包含的像素个数（面积）代表两个区域的颜色均值，在本文即为L,u,v三分量的区域均值表示三维欧氏距离[14]；

4)将ri的类标签修改为rj的类标签,and r'=ri∪rj，R=R-rj，R'=R'+r'；

5)重复2)-4)，直到R为空。

4 实验结果及分析

4.1 实验数据

从Berkeley图像库中选取三副实验图像（图1）。对于每幅实验图像，APGNC算法中相似度取负的欧氏距离，偏向参数P初始为median（S），指定的目标聚类数目DK设置为表1中图片相应的分割数目，阻尼系数设置为0.7，自动采样率rate设置为2‰，区域合并的面积阈值T取200。（硬件环境：CPU：Intel Core(TM)2，1.86GHz With 1G memory），实验软件：MATLAB 7.8.0(R2009a)。

图1 实验用图（鸟、飞机、教堂）

4.2 实验结果

为了验证本文所提方法的高效性和准确性，特意选择了基于K-means的RGB彩色图像分割算法作对比验证实验，其聚类数目设置见表1。

表1 图像信息

在图2中，基于K均值的彩色图像分割中存在大量孤立点和小区域，严重影响了分割结果的精度。很显然，与K均值的分割结果相比，本文方法减少了分割结果中的孤立小区域，提高了分割的精度，使结果更加趋于整体一致性，更加符合人类整体视觉感观的特点；另外，可以通过调整自动采样率rate的值，使该算法用于更大尺寸图像的分割处理，这是传统AP算法所不具备的。

在图3中，对比本文方法、k-means与人工分割结果，不难发现本文方法的分割结果是比较符合理想的人工分割结果，这是与事实相一致的；特别是由于采用了区域合并策略，对AP初始分割进行了一定的修正，消除了背景区域中的孤立区域的影响，使最终的分割结果更倾向于整体一致。

表2对本文方法与K-means方法在运行时间（s）上进行了对比，结果表明,本文方法拥有较快的执行时间，并能够达到较满意的分割效果。

图2 聚类结果

表2 对比试验

5 结论

本文针对近邻传播聚类在图像分割方面存在的问题，提出了利用数据采样和区域合并的基于近邻传播聚类的彩色图像分割方法。经仿真试验证明，本文所提的图像分割方法进一步改善了图像分割质量，具有较满意的分割结果和较快的处理速度，更符合人类的整体视觉感观。但该方法仍然存在不足之处，即只利用了图像中的颜色信息，而忽视了纹理等有用的空间信息。因此，如何将这些丰富的空间信息整合应用到该图像分割算法中还需要进一步探讨。

图3 分割结果

[1]FreyBJ,DueckD.Clustering bypassingmessages between data points[J].Sincence,2007,315(5814):972-976.

[2]Kelly K.Affinity propagation slashes computing times[OL/DB].available:http://www.news.utoronto.ca/bin6/070215-2952.asp,October 25,2007.

[3]Li G,Guo L,Liu T M.Grouping of brain MR images via affinity propagation[C].IEEE International Symposium on Circuits and Systems,Taipei,Taiwan,2009:2425-2428.

[4]唐东明,朱清新,杨 凡，等.基于仿射传播聚类的大规模选址布局问题求解[J].计算机应用研究,2010,27(3):841-844.

[5]万 洁.基于affinity propagation聚类方法的图像检索技术在数字图书馆中的应用[J].计算机与现代化,2008(8):116-119.

[6]张仁彦,赵洪亮.基于相似性传播聚类的灰度图像分割[J].海军工程大学学报,2009,21(3):33-37.

[7]Cheng H D,Jiang X H,Sun Y,et al.Color image segmentation: advanees and prospects. Pattern Recognition[J].December,2001,34(l2):225-2281.

[8]SHARMA C,TRUSSELL H.Digital color image[J].IEEE Transaction on Image Processing,1997,6(7):901-932.

[9]Xiao J X,Wang J D,Tan P,et al.Joint affinity propagation for multiple view segmentation[C].Proceedings of 2007 IEEE 11th internationa conference on computer vision. piscataway,NJ0885521331,United States:Institute of Electrical and Electronics Engineers Inc,2007:1-7.

[10]FREY B J,DUECK D.Mixture modeling by affinity propagation [J].Neural Information Processing Systems,2006,18:379-386.

[11]谷瑞军,汪加才.面向大规模数据集的近邻传播聚类[J].计算机工程,2010,36(23):22-24.

[12]王 磊,汪西莉.一种结合半监督的改进自适应亲和传播聚类[J].计算机应用研究，2010:27(12):4436-4442.

[13]CHENG H D,JIANG X H,WANG J.Color image segmentation based on homogram thresholding and region merging[J].Pattern Recognition,2002,35(2):373-393.

[14]ERLANDSSON F,LINNMAN C,EKHOLM S,et al.A detailed analysis of cyclin a accumulation at the G1/S border in normaland transformed cells[J].Experimental Cell Research,2000,259:86-95.