浅议基于模糊连接度近邻传播聚类图像分割方法

论文导读：学者们提出了一些策略。如Li等提出使用局部图像模型将磁共振图像分成多个上下文，在每个上下文中使用AP对灰度级进行聚类的策略。该策略上下文均是矩形框，在最后整合分割结果时不方便，而且灰度级聚类的策略只适用于灰度图像。许晓丽等提出先用Mean-Shift算法将图像过分割成小区域，再进行AP聚类的MSAP（Mean-ShiftAffinityPro
摘要：针对现有近邻传播聚类图像分割策略分割精度低的理由，提出一种基于模糊连接度的邻近传播聚类（FCAP）图像分割算法。针对传统模糊连接度算法不能得出任意点对间模糊连接度的不足，结合最大生成树提出了全模糊连接度算法。FCAP算法先使用Normalized Cut超像素技术进行超像素分割，这些超像素可以看作数据点以及它们之间的模糊连接度；然后使用所提出的全模糊连接度算法计算超像素间的模糊连接度，根据模糊连接度和空间信息计算超像素的相似度；最后使用近邻传播（AP）聚类算法完成分割。实验结果表明，FCAP算法明显优于超像素处理后直接使用AP聚类算法进行分割的策略，并且优于无监督图像分割策略。
关键词：图像分割；模糊连接度；近邻传播聚类；超像素；最大生成树
：A
0引言
随着聚类技术的不断进步，基于聚类技术的图像分割策略成为研究热点。模糊聚类、谱聚类等聚类策略在图像分割中都有应用。近邻传播（Affinity Propagation， AP）聚类[1]相对于传统的聚类策略有不需要假定初始聚类中心和聚类数目，聚类精度高等优点。已有学者对AP聚类图像分割策略进行了研究[2-6]。这些研究主要分为两个方向：一是减小数据量，提高时空效率。图像像素数量庞大，AP聚类的时空复杂度都为n2，直接聚类消耗很大。针对这个理由，学者们提出了一些策略。如Li等[2]提出使用局部图像模型将磁共振图像分成多个上下文，在每个上下文中使用AP对灰度级进行聚类的策略。该策略上下文均是矩形框，在最后整合分割结果时不方便，而且灰度级聚类的策略只适用于灰度图像。许晓丽等[3]提出先用Mean-Shift算法将图像过分割成小区域，再进行AP聚类的MSAP（Mean-Shift Affinity Propagation）算法用于分割自然图像。MSAP算法大大减少了用于聚类的数据点的数目，提高了时空效率，但是Mean-Shift算法中的参数不易确定，也没有考虑空间信息。Huang等[4]提出先用改善的AP聚类算法得到许多粗分割的类和类中心，再对类中心使用Normalized Cut算法进行分类的策略。该策略以像素为数据点，只能分割很小的图片。还有其他学者使用采样或者分水岭过分割的策略减小数据量。二是提出新的相似度计算的策略。AP聚类和谱聚类一样，都是依据数据点间的相似性进行聚类的，所以相似度的计算策略直接决定聚类结果的好坏。Yang等[5]提出FS-AP（Fuzzy Statistical based Affinity Propagation）算法，用FSS（Fuzzy Statistical Similarity）作为相似度计算策略，使用AP聚类对多光谱图像进行分割。FS-AP算法同样是直接对像素进行聚类，时空效率很低。Zhang[6]根据人眼视觉特性提出了两种新的基于灰度级的相似度计算策略。该策略时空效率低并且只适用于灰度图像，直接使用效果不理想。总体上讲，使用AP聚类进行图像分割的研究还比较少，现有策略时空效率低，分割效果也不很理想，尤其对复杂的自然图像，很难得出满意的结果。
1996年Udupa等[7]提出了模糊连接度理论框架，如今模糊连接度已经成为比较成熟的图像分割策略。其中经典的算法有阈值模糊连接度算法、相对模糊连接度算法[8]等。模糊连接度策略分割效果好、运转速度快，在医学图像分割中占有重要地位。但是模糊连接度策略大都是交互式分割，而且对复杂的自然图像分割往往得不到很好的效果。
本文旨在提出一种新的图像分割策略，弥补AP聚类时空效率的不足，并大大提高分割精度。本文首先提出了一种全模糊连接度（Whole Fuzzy Connectedness， WFC）算法，该算法可以得到连通图中任意两点间的模糊连接度；然后将WFC算法与AP聚类结合提出基于模糊连接度的近邻传播聚类图像分割策略（Fuzzy Connectedness based Affinity Propagation clustering， FCAP）用于自然图像分割。
1AP聚类算法
AP聚类算法是根据数据点间的相似度进行聚类的。它先将所有数据点视为潜在的聚类中心，在数据点间迭代地传递信息直到聚类结果收敛。
2FCAP算法

2.1WFC算法

2.

1.1算法背景

2.

1.2算法原理

最大生成树中的任何一条边都是连接其两侧子图的边中权重最大的，其两侧的节点之间的模糊连接度不可能大于该边的权重，进而可知两个节点的模糊连接度要小于等于最大生成树中连接它们的路径中的每一条边的权重，根据模糊连接度的定义就可以得出上面的结论。故只需得出连通图的一棵最大生成树，并获得树中任意两点的路径和该路径的连接度，就可以得到所有节点间的模糊连接度。
2.

1.3算法描述

WFC算法是一种贪心算法，算法输入连通图G=（V，E），输出n*n模糊连接度矩阵M，算法中需要辅助队列Q和长度为n的数组key和parent。算法初始化时将M置为单位矩阵，所有节点的key置为无穷小， parent设为nil，然后随机选择根节点r，将其key置为1， parent置为自身，开始循环。每次循环从Q中取出key值最大的节点u，此时可通过parent找出u与v

2.

1.4算法伪代码

2FCAP算法 FCAP算法将WFC算法和AP聚类结合用于图像的自动分割。算法流程如下：
Step1用Normalized Cut超像素技术[9]对图像进行超像素分割。超像素是图像中由一系列位置邻近、颜色、纹理等特征相似的像素组成的小区域。算法中有一个参数N，用于指导超像素数目。
Step2对每个超像素，计算其质心作为其位置坐标，并提取特征。超像素是由许多像素组成的小区域，所以可提取的特征有很多，可以根据颜色（或灰度）、纹理等进行提取。 全文地址：www.7ctime.com/ylxlw/lw44626.html上一论文：关于的网络传播时代区域形象塑造