基于局部优先的彩色图像分割算法

张　琦，陈金勇，帅　通

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)



基于局部优先的彩色图像分割算法

张琦，陈金勇，帅通

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

针对彩色图像分割聚类算法效果不理想以及计算复杂度较高的问题，提出了一种有效的彩色图像分割算法。该算法只对小区域进行处理操作，大大降低了计算复杂度，而且大大提高了图像分割的质量。与此同时，定义了名为局部优先级的变量，同时考虑了小区域的亮度和其他详细信息，减少由于只考虑像素点的亮度信息导致不恰当划分的可能性。实验结果表明，在真实彩色图像的分割结果中，该算法具有较好的图像分割效果。

彩色图像分割；均值漂移；通勤时间嵌入；局部优先

0　引言

图像分割是计算机视觉领域的一个重要话题，它是一个把图像划分为几个非相交区域的过程，使得每个区域均匀且相关[1-2]。彩色图像比灰度图像包含更多的信息，因此彩色图像分割逐渐成为研究的重点，并且涌现出一系列的图像分割算法。例如，K-Means算法[3]和层次算法[4]可以在图像像素是凸形簇时获得较好的结果。谱聚类算法[5-6]不对簇的结构做强的假设，图像分割效果优于K-Means算法和层次算法。然而，谱聚类算法在执行中需要对图的拉普拉斯矩阵进行特征值分解，使得算法的时间复杂度、空间复杂度高达O(n3) 和O(n2)[7-8]。

近来来，研究学者采用采样技术降低谱聚类算法特征值分解的计算复杂度。例如，文献[9]利用Nystrom方法获取随机采样样本的特征值，然后逼近原始数据的特征值。文献[10]使用谱聚类算法分析处理利用K-Means算法得到的小规模的原始数据中心点集合。文献[11]利用稀疏编码的思想，近似表达原始数据的相似度矩阵，从而可以高效地计算出特征值。然而，无论对原始数据进行任何的采样或者代表点选取，都不能准确捕获原始数据的结构。并且，一旦采样点或者代表点数据足够多时，特征值分解所消耗的时间也不可忽视。

为了解决这些问题，本文提出一种结合MeanShift算法与改进的通勤时间嵌入算法(以下简称为MSICTE算法)。MSICTE算法具有较低的计算复杂度，并且能够获得较好的图像分割结果。MSICTE算法首先使用MeanShift算法对彩色图像进行预分割，并用预分割得到的区域亮度和细节信息的均值代表该区域，并以此为基础构建一个图，然后利用基于局部优先的通勤时间嵌入算法对预分割形成的区域进行划分，得到最终的图像分割结果。在MSICTE算法中，MeanShift算法[12]不仅可以显著减少彩色图像的数据量，而且能保留原始图像的不连续性特性。并且，通勤时间基于Laplacian图、热核和图上随机游走等谱图理论，能够捕获数据的复杂空间结构[13]。实验结果表明，MSICTE算法能获得高质量的图像分割结果。

1　通勤时间

给定一个权图G=(V，E，W )，V表示图的顶点的集合，E⊆V×V是图的边的集合，W表示图的相似度矩阵。

定义1：首中时间H(i,j)。图上随机游走的首中时间H(i,j)为由i点出发首次到达j点的期望步长：

式中，wij是相似度；dii是图的度。

定义2：通勤时间Cij[14]可定义为由i点出发首次到达j点后第一次返回i点的期望步长。通勤时间与首中时间之间的关系可通过式(1)来描述：

Cij=Hij+ Hji。

(1)

通勤时间Cij可用拉普拉斯矩阵L和它的伪逆计算得到，如式(2)所示：

Cij=vol(ei-ej)TL†(ei-ej)。

(2)

2　MSICTE算法

2.1局部优先

彩色图像的视觉信息包括亮度和细节信息。亮度主要包含像素值，而细节信息是指像素值的变化程度。本文中，预分割区域的合并策略描述为：综合亮度信息、细节信息，并利用下文定义的局部优先概念合并这些区域。

对于给定的第l个局部区域记为Re(l)∈Rn×m×d，像素(i,j,d)的值记为re(i,j,d)，则该区域的亮度和细节信息分别记为lig(d，l)、det(d，l)，如式(3)和式(4)所示。

(3)

(4)

Re(l)的局部优先度f(d,l)表示为：

f(d,l)=λ(d,l)det(d,l)+(1-λ(d,l))lig(d,l)。

(5)

式中，λ(d,l)表示细节信息的加权优先度；(1-λ(d,l))表示亮度信息的加权优先度；λ(d,l)表示为：

(6)

λ(d,l)和(1-λ(d,l))称为局部优先的敏感因子，可反映f(d,l)的局部信息敏感度。局部亮度的敏感因子的值越大，亮度信息的局部优先敏感度越大。

局部优先可以使簇内的数据对象更加紧密，也可以使簇与簇之间数据对象更加分散。从而为后续的图像分割算法提供更为适合的数据结构，并获得更高的图像分割质量。

2.2通勤时间嵌入算法

对于一个给定的数据集A，它包含n个数据点，每个数据点由p个属性进行描述，即A∈Rn×p，A=[a1,a2,…,an]T，可使用归一化拉普拉斯矩阵Ln推导通勤时间Cij。

根据式(2)，Cij也可以表示为：

(7)

A的奇异值分解可以表示为：

A=UΣVT。

(8)

式中，U与V正交；Σ=diag(σ1，…，σp)；UUT=I∈Rn×n；VVT=E∈Rp×p；Σ是奇异值方阵。

使用余弦函数计算相似度矩阵W：

W=AAT=UΣ2UT。

(9)

对于式(8)，两边同时右乘(ΣVT)RP，并应用右伪逆公式(X)RP=XT(XXT)-1，可以推导出

U=AVӆ

(10)

因此，矩阵ATD-1A的特征值分解可以表示为：

(11)

(12)

根据式(10)可以得到：

(13)

结合式(7)和式(12)，Cij可以变换为：

(14)

式(14)说明i和j两点间的通勤时间Cij等于矩阵S的第i列与第j列间的欧氏距离的平方，并且下式成立：

(15)

2.3MSICTE算法主要步骤

MSICTE算法步骤主要包括：首先使用Mean Shift算法把原始图像预分割为若干个小图像区域；然后利用本文定义的局部优先策略对预分割结果构建无向图；最后利用通勤时间嵌入算法处理，得到最终的图像分割结果。

MSICTE算法的详细步骤如下：

输入：待分割原始图像及分割的类别数目k；

步骤1：使用Mean Shift算法对原始图像进行预分割，得到若干个小区域；

步骤2：利用本文定义的局部优先策略对预分割后小区域计算，得到其代表点集合A。

步骤3：使用式(9)计算W。

步骤4：使用式(11)计算ATD-1A。

步骤6：使用式(15)计算矩阵S，然后调用k-means算法将S聚类为k个簇。

步骤7：使用边缘检测算法获取物体的轮廓。

输出：最终的图像分割结果。

3　实验设计及结果分析

本节对本文提出的MCISTE算法进行实验对比，测试图像3幅、图像大小421×381或381×421。实验硬件环境为：联想 Ideapad Y460，Intel(R) Core(TM) i3M 350 @ 2.27 GHz CPU、2 G 内存；软件环境为：Windows 7操作系统、Matlab2010a。

为验证本文算法的有效性，MSICTE算法与3种算法进行对比实验，对比算法分别为：Nyström方法的谱聚类算法(SCUNM算法)、结合Mean shift与模糊C均值的MSFCM算法、结合Mean Shift与Ncut算法的MSNcut算法。4种算法的分割结果如图1所示，运行时间如表1所示。图1(a)中为原始图像，且从上至下类别数分别为3、8、4；第2列SCUNM算法的图像分割结果；第3列为MSFCM算法的图像分割结果；第4列为MSNcut算法的图像分割结果；第5列为本文提出的MSICTE算法图像分割结果。

图1　4种算法图像分割结果对比

(单位：s)

从图1中可以得到如下结论：

① 使用均值漂移算法进行预分割的MSFCM、MSNcut和MSICTE算法能够获得比SCUNM算法更好的图像分割结果。SCUNM算法为了降低谱聚类算法的计算复杂度，采用了基于采样技术的Nyström方法，然而采样点不一定能精确的捕捉整个数据集的结构，会丢失一部分信息，导致无法从图1(b)图像分割结果中得到物体的轮廓，而其他3种算法不使用采样技术，因此保持了图像的显著特征。因此，可以从MSFCM、MSNcut和MSICTE算法的图像分割结果清晰的得到物体的轮廓；

② MSNcut的图像分割结果好于MSFCM。MSFCM算法容易陷入局部最优。如，针对图1(a)中的图像2和图像3从上至下，MSFCM算法把图像2中的“大海”与图像3中的“石头”分割为小块，没有保留图像的全局信息。反观MSNcut算法始终可以获得图像的全局信息，能够得到全局最优结果；

③MSICTE算法的图像分割质量最好。MSICTE算法首先使用MS算法保留原始图像的显著特征，随后利用通勤时间算法得到全局最优的图像分割结果。从图1中可以明显看出，MSICTE的图像分割结果清晰，可轻松识别图像中的物体，并且物体的轮廓清晰、完整、准确。

在表1中可以看出，在所有的4种彩色图像分割算法中，TMSNcut

总之，MSICTE算法能够得到较好的图像分割质量，且运行效率较高。

4　结束语

本文提出了一种结合均值漂移算法与改进的通勤时间嵌入的彩色图像分割算法，实验表明本文提出的算法较其他常用的方法具有更高的有效性和鲁棒性。本文算法的长处在于综合利用了均值漂移和通勤时间嵌入算法的优点。预分割阶段的均值漂移算法能够较好的保持原始图像不连续特征，而基于局部优先策略构建的区域邻接图与通勤时间算法对预分割后的小区域进行处理，大大增强了图像分割算法的性能。除此之外，MSICTE算法具有较低的时间复杂度。

[1]BAI X D，CAO Z G，YU Z H，et al.Color Image Segmentation Using Watershed and NyströmMethod Based Spectral Clustering[C]∥Proceedings of SPIE—The International Society for Optical Engineering，2011:1-8.

[2]邢旭东，周旭，米健.基于改进的人工蚁群的图像分割算法[J].无线电工程，2013，39(6):71-73，81.

[3]GUI Y，BAI X，LI Z，et al.Color Image Segmentation UsingMean Shift and Improved Spectral Clustering，Control Automation Robotics &Vision[C]∥Proceedings of 2012 12th International Conference,2012:1 386-1 391.

[4]GUPTA P，SAXENA S，SINGH S，et al.Color Image Segmentation:A State of the Art Survey[J].International Journal of Computational Intelligence Research，2012，8(1):17-25.

[5]VON L U.A Tutorial on Spectral Clustering[J].Statistics and Computing,2007，17(4):395-416.

[6]NG A Y，JORDANM I，WEISS Y.On Spectral Clustering:Analysis and an Algorithm[C]∥Proceedings of Advances in Neural Information Processing Systems.Cambri-dge，MA:MIT Press，2001(14):849-856.

[7]SHI J，MALIK J.Normalized Cuts and Image Segmentation[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2000，22(8):888-905.

[8]CHEN W Y，SONG Y Q，BAI H J.Parallel Spectral Clustering in Distributed Systems[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2011，33(3):568-586.

[9]FOWLKES C，BELONGIE S，CHUNG F.Spectral Grouping Using the NyströmMethod[J].Pattern Analysis andMachine Intelligence，IEEE Transactions on，2004，26(2):214-225.

[10]YAN D H，HUANG L，JORDANM I.Fast Approximate Spectral Clustering[C]∥Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM，2009:907-916.

[11]CHEN X L，CAI D.Large Scale Spectral Clustering with Landmark-Based Representation[C]∥Proceeding of 2011 AAAI.

[12]COMANICIU D，MEER P.Mean Shift:A Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2002，24(5):603-619.

[13]FOUSS F，PIROTTE A，RENDERS JM，et al.Random-Walk Computation of Similarities Between Nodes of a Graph with Application to Collaborative Recommendation[J].IEEE Transactions on Knowledge and Data Engineering，2007，19(3):355-369.

[14]QIU H J，HANCOCK E R，Clustering and Embedding Using Commute Times[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2007，29(11):1 873-1 890.

张琦男，(1987—)，博士。主要研究方向：航天地面应用、信息处理和图像分割。

陈金勇男，(1970—)，研究员。主要研究方向：系统工程、航天地面应用。

AColorImageSegmentationAlgorithmBasedonLocalPriority

ZHANGQi，CHENJin-yong，SHUAITong

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

Inviewofunfavorableclusteringeffectandhighcomputationalcomplexityforcolorimagesegmentation，anovelalgorithmwhichcansupplyeffectivecolorimagesegmentationisproposedinthispaper.Thealgorithmisonlyusedforprocessingandoperationofsmallregions，thussignificantlyimprovingthecomputationalcomplexityandthequalityofimagesegmentation.Meanwhile，thelocalpriorityisdefined，consideringthelightnessandotherdetailedinformationofsmallregionsinordertoreducetheprobabilityofgeneratingsomeinappropriatepartitioningwhenconstructingthegraphbyusingonlythelightnessinformationofpixels.Theexperimentalresultsshowthatthisalgorithmhasbetterimagesegmentationeffect.

colorimagesegmentation；meanshift；commutetimeembedding；localpriority

10.3969/j.issn.1003-3106.2016.08.07

2016-05-05

中国博士后科学基金资助项目(2015M580217)；河北省博士后科学基金资助项目(B2015005003)。

TP391A

1003-3106(2016)08-0027-04

引用格式：张琦，陈金勇，帅通.基于局部优先的彩色图像分割算法[J].无线电工程,2016,46(8):27-30.