[不完全�K�-means聚类与分类优化结合的图像分割算法]K-means聚类

　　 文章编号:1001-9081(2012)01-0248-04 doi:10.3724/SP.J.1087.2012.00248 　　 　　摘 要:为提升�K�均值聚类的效率及图像分割效果，提出了一种不完全�K�均值聚类与分类优化结合的图像分割(IKCO)算法。首先，采用简单的方法来进行数据精简及初始中心的确定；然后，根据给出的不完全聚类准则对图像进行聚类分割；最后，对分割结果进行分类优化以提升分割效果。实验结果表明，相对于传统的�K�均值聚类方法，IKCO算法在进行图像分割时具有很好的分割效率，且分割效果与人类视觉感知具有更高的一致性。
　　
　　�关键词:图像分割；不完全�K�均值聚类；分类优化
　　�中图分类号: TP391.413 文献标志码:A
　　 �
　　Abstract: To improve the clustering efficiency and image segmentation effect, the paper proposed an Incomplete �K�-means and Category Optimization (IKCO) method. First of all, the algorithm used simple approach to finish data subsampling and initial centers determining. Then, according to the clustering rules, the proposed algorithm finished image�s segmentation. Finally, the algorithm used category optimization method to improve segmentation results. The experimental results show that, compared with the traditional �K�-means clustering method, the proposed algorithm has better segmentation efficiency, and the segmentation result has a higher consistency with human visual perception.
　　
　　 Key words: image segmentation; incomplete �K�-means clustering; category optimization
　　�
　　0 引言�
　　图像分割是将图像分成各具特性的区域并提取出感兴趣的目标的技术和过程。它是图像处理到图像分析的重要环节。目前基于彩色图像的分割方法［1］大致有基于阈值的方法、基于模板匹配的方法、基于区域生长的方法以及基于边缘检测和基于聚类的方法等。�
　　�而在图像分割的众多方法中，K均值聚类由于其简单性与高效性而被广泛应用于图像分割。K均值聚类的主要思想是通过聚类使得类内差异渐小、类间差异渐大从而得到一个好的聚类,进而实现图像在某种意义上的分割。K均值聚类虽然有着简单、高效等优点，但由于其对初始聚类中心较为依赖且用K均值聚类实现图像分割时很少利用到图像的空间信息，使得在用K均值聚类实现图像分割时，往往会出现聚类效果不稳定、过分割等问题。�
　　为提升传统K均值聚类的聚类效率及分割效果，本文对传统的K均值聚类算法进行改进，�并结合分类优化方法提出一种不完全�K�均值聚类与分类优化(Incomplete �K�-means and Category Optimization, IKCO)算法来处理彩色图像的分割问题。本文的IKCO算法首先采用简单的方法来进行数据精简及初始中心确定；然后对精简后的样本进行不完全�K�均值聚类；最后再利用设计的分类优化方法对分类结果进行优化。�
　　
　　1 传统�K�均值聚类算法�
　　�K均值聚类算法是一种需要事先确定其聚类数目K的无监督聚类算法，在理论上具有高可靠性，同时应用起来收敛速度快，局部搜索能力强。因此，K均值聚类算法是图像分割中应用较多的一种算法。K均值聚类算法的主要思想是尝试将n个样本划分到K个类中，且尽可能使这K个类具有较小的类内差异和较大的类间差异。若设其准则函数如式(1)所示：�
　　J=∑ki=1J�i=∑ki=1∑x=x�ix－�x�i��2(1)�
　　其中�x�i�表示第i个类的中心。则其主要步骤可如下所示。�
　　步骤1 从n个数据样本中通过某种策略选出k个样本作为初始聚类中心。�
　　步骤2 计算各个样本与每个聚类中心的差异，根据某种原则将其划分到合适的聚类中。�
　　步骤3 重新计算各个聚类中心，并根据式(1)计算出新的J值，记为J���t+1�。�
　　步骤4 若‖J����t+1�－J��t‖≤ε则迭代停止，ε为迭代停止条件；否则转到步骤2继续迭代。��
　　
　　2 IKCO算法�
　　本文提出的IKCO算法对传统的�K�均值聚类算法提出以下几方面的改进：首先，采用样本空间精简的方法来减少单次迭代的耗时;其次，采用一种简单的方法来确定初始聚类中心;另提出一种不完全聚类方法来进一步改进聚类的效率;最后，给出一种分类优化方法来对聚类结果进行优化，以剔除聚类结果中的一些小区域。算法的具体流程如图1所示。�
　　
　　�在本文算法开始前，还需要对图像进行特征提取工作。由于主要只采用图像的色彩信息，因此对每个像素x�i其特征向量为其在�HSV�色彩空间中的各分量构成：V��x�i�={h��x�i�,s��x�i�,v��x�i�}。�
　　设待聚类的特征向量集合为{V�1,V�2,…,V�N}，其中N为像素总数，聚类数为K。�
　　本文所采用的距离度量方式是在欧氏距离的基础上对各分量进行了加权，如式(2)所示：�
　　d(V�i,V�j)=�k�1•‖h�i－h�j‖�2+k�2•‖s�i－s�j‖�2+k�3•‖v�i－v�j‖�2（2）�
　　其中k�1,k�2,k�3为对特征向量中各分量的加权值。��
　　
　　2.1 缩小样本空间�
　　目前主要的样本精简策略有两种：一种是基于图像像素［2］的，即对图像进行分块，用块的均值或中值来作为新的样本。若分块大小为2×2，则分块的样本空间大小将变为原来的1/4。另一种是基于图像特征［3］的，即将具有相同特征的样本（像素）归为一类。本文的样本精简策略是在第二种方法基础上改进得来，即先对特征空间进行分块，再将像素基于其特征划分到分块后单元格中,并用单元格的值来体现具有此类特征的像素的个数。相对于传统�K�均值聚类过程中对所有样本进行处理，此算法能较大地提高聚类效率，算法描述如算法1所示。�
　　算法1 样本空间精简。
　　
　　程序前
　　�
　　�输入 S��M×N�=�{�s��i, j�|1≤i≤M,1≤j≤N�}�为M×N大小的图像像素集合�；�
　　分块大小q×q×q�;� q为已确定常数。�
　　输出 Z��H�n×S�n×V�n�=�{�z��h,s,v�|0≤h≤H�n,0≤s≤S�n,0≤v≤V�n�}��；�H�n,S�n,V�n为各特征的个数，Z��H�n×S�n×V�n�为分块后的特征空间。�
　　�Begin��
　　�for� 对�z��h,s,v�∈Z��H�n×S�n×V�n�，V��h,s,v�表示该单元格的值�
　　V��h,s,v�←0�;��
　　�for� 对�x��i, j�∈S��M×N�，H�x,S�x,V�x为其特征 �do��
　　h=H�x/q�;�s=S�x/q�;�v=V�x/q�;��
　　z��h,s,v�←x��i, j��;��
　　V��h,s,v�++�;���
　　end�
　　�返回Z��H�n×S�n×V�n��;���
　　end
　　
　　程序后
　　�
　　2.2 聚类中心确定�
　　�在目前的研究成果中针对K均值聚类中心选择的优化的方法有很多，�且这些方法在处理某些图像分割问题时取得了较好的效果。这些方法主要有基于分裂式的方法（LINDE-BUZO-GRAY, LBG）［4］、基于最大最小距离（Minmax, MMX）［5］、基于密度的方法（Density-based, DEN）［6］、基于子集最远优先（Subset Farthest First, SFF）［7］等。�本文给出的确定初始中心的方法在之前的样本精简基础上对最大最小距离方法引入密度来作为度量，最初的k个聚类中心选择样本密度最高的k个特征样本，然后迭代确定初始聚类中心，具体算法描述如算法2所示。��
　　算法2 初始中心确定。
　　
　　程序前
　　�
　　
　　输入 �Z��H�n×S�n×V�n��为精简后的样本空间，最大迭代次数�I�。�
　　�输出 C=�{�c�1,c�2,…,c�k�}�,k个聚类中心。这个逗号分隔得是否正确，请明确。��
　　begin�
　　�V�v表示Z��H�n×S�n×V�n�中样本v的值�;��
　　选取Z��H�n×S�n×V�n�中k个V�v较大的样本作为k个初始中心赋予集合C中�;��
　　r←0�
　　�while� r≤I或者前一次迭代k个中心均无变化 �do��
　　�for��(�i=0�;�i�max� En�
　　swap�(�v,c�i�);��
　　�max� En←En�;���
　　end�
　　end�
　　�r←r+1�;���
　　end;�
　　�返回C=�{�c�1,c�2,…,c�k�};���
　　end;
　　程序后
　　�
　　
　　2.3 不完全聚类�
　　�传统的K均值聚类方法在聚类过程中总是会计算样本与每个聚类中心的距离。而对于大多数样本其归属是极为明显的，可以通过一种方法来快速得到它的所属类，从而避免计算其与每个聚类中心的距离，进而缩小聚类时间。本文提出的算法给出了一种方法来将聚类中心附近的样本快速归于此聚类中。其主要思想是从聚类中心出发，将聚类中心的R邻域本文中的“领域”，是否应该为“邻域”？请明确。内的样本归于其所属类中，而对于未出现在任何聚类中心邻域内的样本和同时出现在多个聚类中心邻域内的样本将其设为待定，待迭代至聚类中心不再变化时，再将其归于最近的类中。�
　　在给出具体算法描述前，先给出以下定义。�
　　定义1 （（q,R）-邻域）假定q为m维空间Z={z�1,z�2,…,z�m}中某个点，S为一个m维方体，V为一个多维区域，若满足以下条件:�
　　1)q为S的中心；�
　　2)R为一正整数；�
　　3)S在第i维属性上的取值区域为［q［i］－R,q［i］+R］；�
　　4)V为S中不包含q的非空单元格。�
　　则称V为q的（q,R）-邻域，用T(q,R)表示。�
　　这样对于样本x若其位于聚类中心c�i的R邻域内，即x∈T(c�i,R)，则将其归于以c�i为中心的类中。邻域大小R值的确定将成为影响聚类效果的重要因素。理想的R值应使尽可能多的样本能够划分到聚类中，而尽可能少的样本被标记为待定。而理想的邻域半径的R值的确定计算是非常复杂的,因此本文提出了3种近似方法来确定邻域大小R。若设第i次聚类时，其聚类中心为Φ�i={φ�i�1,φ�i�2,…,φ�i�k}，第j个聚类中心的聚类半径为R��i, j�，则3种方法R��i, j�值的计算公式如下。�
　　1）邻接最小距离：�
　　R��i, j�=12•�min�(‖φ�i�m－φ�i�j‖�2); 1≤m, j≤k,m≠j（3）�
　　2）邻接均值：�
　　R��i, j�=12•(k－1)∑k－11≤m, j≤k, m≠j‖φ�i�m－φ�i�j‖�2(4)�
　　3）全局均值：�
　　R��i, j�=12•C�2�k ∑C���2��k1≤m, j≤k, m≠j‖φ�i�m－φ�i�j‖�2(5)�
　　以上3种确定邻域半径R的方法不同的情况下有不同的效果，而本文中经过对多个图像进行多次实验采用了式（4）的方法来得到R值。��
　　
　　不完全聚类的具体算法描述如算法3。�
　　
　　算法3 不完全聚类。
　　程序前
　　�
　　�输入 C�0=�{�c�1,c�2,…,c�k�}�，k个初始聚类中心,Z��H�n×S�n×V�n�为精简后的样本空间。�
　　输出 S=�{�s�1,s�2,…,s�k�}�,k个分类结果。��
　　begin�
　　�j←0��
　　Repeat�
　　�对Z中的所有非空单元格初始化为待定状态0�;��
　　根据式�（�4�）�计算R��i, j�的值�;��
　　�For� c�i∈C��(j)� �do��
　　v表示属于Z中的非空样本�;��
　　�if� v∈T�(�c�i,R��i, j��)�且v位于待定状态0�
　　//将v归于以c�i为中心的类中�
　　s�i←v�
　　�else if� v∈T�(�c�i,R��i, j��)�且v不位于任何待定状态�
　　将v从之前划分到的类中剔除出来归于待定状态1�;��
　　�end;��
　　j←j+1�;��
　　//根据前面的分类重新计算聚类中心�
　　�for� z∈�［�1,k�］� �do��
　　c��j�z=∑v∈s�zn�v•v∑v∈s�zn�v�
　　�until� 所有k个类不再变化�;��
　　对�v∈Z且v位于任何一种待定状态�
　　//将v归于距离最近的类中�
　　z←Π�k这个是累积符号吗？还是一个变量，请明确。�{���arg min��k∈�{�1,2,…,k�}�‖v－c�k‖�2�}��
　　s�z←v�
　　返回k个聚类�{�s�1,s�2,…,s�k�}���
　　end
　　程序后
　　�
　　
　　2.4 聚类优化�
　　�利用以上不完全K均值聚类方法进行图像分割，由于并没有利用位于几个聚类交界处及位于整个样本空间边缘的一些样本，且聚类过程是基于特征的，完全忽略了图像的空间信息，使得聚类结果中出现了很多小区域。因此本文提出了一种对分类结果进行优化的方法，这种方法一定程度结合了区域信息，对聚类分割所产生的小区域进行了剔除，有较好的处理效果。其主要思想是用哈希的方法统计样本x的R×R邻域内属于各类的样本个数如图2所示，再将属于x所属类的样本个数与一个阈值比较，若大于则不做任何操作；否则将样本x归于邻域类样本所属类最多的类中，其算法描述如算法4所示。��
　　
　　算法4 聚类优化。
　　程序前
　　�
　　
　　�输入 S��M×N�=�{�s��i, j�|1≤i≤M,1≤j≤N�}�，表示M×N大小的图像像素集合；
　　L��H�n×S�n×V�n�=�{�l��h,s,v�|0≤h≤H�n,0≤s≤S�n,0≤v≤V�n�}�不完全聚类后的分类结果�；�
　　l��h,s,v�的值表示具有特征h,s,v的样本所属的类�；�
　　分块大小q×q×q�;� q为已确定常数。�
　　输出 U��M×N�=�{�u��i, j�|1≤i≤M,1≤j≤N�}�，表示M×N大小图像各个像素所属类的标记。�
　　�Begin�//先用L��H�n×S�n×V�n�对U��M×N�进行初始标记�
　　�for� 对�x��i, j�∈S��M×N�，H�x,S�x,V�x为其特征 �do��
　　h=H�x/q�;�s=S�x/q�;�v=V�x/q�;��
　　u��i, j�←l��h,s,v��
　　�end��
　　//统计x的R×R邻域内属于各类的像素个数,Γ�(�x,R�)�表示x�//的R×R邻域�
　　�for� 对�x��i, j�∈S��M×N� �do��
　　�for� x��t,k�∈Γ�(�x��i, j�,R�)� �do��
　　m�［�u��t,k��］�++�;��
　　�end;��
　　//若邻域内像素属于x所属类的个数小于阈值T,则将�//u��i, j�标记为邻域类像素属于最多的类中�
　　�if� m�［�u��i, j��］�［8］中的图像进行了实验,作为比较同时列出了传统�K�均值聚类,�K�均值聚类与区域合并结合(K-Means and Region Merging, KMRM)算法的处理结果，以及本文的IKCO算法过程中部分阶段的得到的结果及最终结果。实验环境为AMD 64，CPU 2.64�GHz,1�GB内存。以下给出3组实验结果。�
　　在图4~6所示的图像分割结果中，图4(a)、图5(a)、图6(a)为原图，图4(b)、图5(b)、图6(b)为传统的�k�均值聚类的分割结果，图4(c)、图5(c)、图6(c)为本文IKCO算法的不完全聚类部分的结果，图4(d)、图5(d)、图6(d)为KMRM算法的处理结果，图4(e)、图5(e)、图6(e)为本文IKCO算法所得到的处理结果。从图4(b)、图5(b)、图6(b)中可以看出传统�K�均值聚类所得到的图像分割结果效果极差，而图4(c)、图5(c)、图6(c)表明本文给出的不完全聚类方法在加权的距离度量方法下得到的处理结果已经很好，只是存在一些孤立的小区域，而本文IKCO所得到的图像分割结果即图4(e)、图5(e)、图6(e)已经与人眼分割结果极
　　
　　����
　　
　　为接近。而从图4(d)、图5(d)、图6(d)与图4(e)、图5(e)、图6(e)的对比可知，本文方法与KMRM算法分割效果较为相似，都与人类视觉感知很接近，但从图片1,2的结果对比可更为明显看出一些情况下本文IKCO算法优于KMRM算法。表1给出了图4~6分割时所采用的相关参数和分类数，�其中：k�1,k�2,k�3分别为距离度量时各色彩分量的加权因子,hs,hr为�KMRM�算法中的两带宽参数。�另本文IKCO算法所采用的迭代停止条件取10��－5�。�
　　
　　3.2 定量分析�
　　为了定量地评价本文所给出的方法，采用了大多数文献所采用的分割评价准则，即分割准确度（Segmentation Accuracy, SA）（如式（6）），来对算法的处理效果及性能进行衡量。表2中的数据即为本文IKCO算法与快速FCM［9］、Jseg［10］GrabCut［11］和N-Cut［12］几种算法在图4~6中的三组图像的处理效果和性能上统计的平均值。从表2分析可以得出本文IKCO算法在分割结果上处理效果居中，比不上Jseg及GrabCut算法，但也相差不大，但运行时间上相对于这两种方法有较大降低。另从表2可看出，本文IKCO算法相对于快速FCM和N-Cut方法运行时间及处理效果都有较好的改善。�
　　�SA=N���Correct��/N���Total��（6）��
　　
　　
　　另为进一步验证本文IKCO算法所做的工作，即对传统�K�均值聚类的改进和聚类优化的价值，本文通过与KMRM算法在聚类时间和聚类优化时间上分别进行比较，来突出本文IKCO算法的可利用性。表3给出了KMRM算法与本文算法在图4~6中各自的聚类时间，及对聚类结果优化处理的耗时。从表3中两算法的“聚类时间”一列可以看出，本文所给出的IKCO算法在聚类时间上相对于KMRM算法有大幅度的降低。另由于KMRM算法中的区域合并实质上也是对聚类结果的优化，因此从表3中的（KMRM）的“区域合并时间”一列与本文的IKCO算法的“分类优化时间此列与表3中的那一列名称不一致，请统一用同一个名称。”一列的对比可看出本文算法所设计的聚类优化方法在性能上相对于区域合并的聚类优化方法有着很大的优势。综合以上情况可知本文IKCO算法在一些情况下在聚类时间及聚类优化时间上均优于�K�均值聚类与区域合并结合的算法，存在一定的价值。�
　　
　　4 结语�
　　实验结果表明，本文提出的基于不完全�K�-means聚类与分类优化结合的方法(IKCO)，在处理大部分图像分割的问题时能得到较好的分割效率及处理效果。且通过对本文IKCO算法与其他几种常见的图像分割算法在处理效果和分割效率上进行比较，表明本文方法是存在较大的价值。当然本文提出的方法在一定程度上存在局限性，在不完全聚类过程中，由于只利用了部分样本进行聚类迭代，若整个样本空间中样本非常分散，则聚类效果将变得不理想。本文给出的分类优化方法在对进行分类优化时若图像中存在较小或较细的对象，则会将其完全覆盖。这两个问题的解决将成为下一步的研究重点。
　　
　　
　　�参考文献:�
　　[1]
　　林开颜，吴军辉，徐立鸿.彩色图像分割方法综述［J］.中国图象图形学报,2005,10(1):1-10.
　　�[2]
　　GOLDBERG N. Colour image quantization for high resolution graphics display ［J］. Image and Vision Computing, 1991, 9(5): 303-312.
　　�[3]
　　MIGNOTTE M. Segmentation by fusion of histogram-based �k�-means clusters in different color spaces ［J］. IEEE Transactions on Image Processing, 2008, 17(5): 780-787.
　　�[4]
　　LINDE Y, BUZO A, GRAY R. An algorithm for vector quantizer design ［J］. IEEE Transactions on Communications, 1980, 28(1): 84-95.
　　�[5]
　　GONZALEZ T F. Clustering to minimize the maximum intercluster distance ［J］. Theoretical Computer Science, 1985, 38(2/3): 293-306.
　　�[6]
　　�AL-DAOUD� �M,� ROBERTS �S.� New methods for the initialisation of clusters ［J］. Pattern Recognition Letters, 1996, 17(5): 451-455.
　　�[7]
　　TURNBULL D, ELKAN C. Fast recognition of musical genres using RBF networks ［J］. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(4): 580-584.
　　�[8]
　　MARTIN �D,� FOWLKES �C,� TAL �D,� �et al.� A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics ［C］// Proceedings of 2001 International Conference on Computer Vision. Washington, DC: IEEE Computer Society, 2001: 416-423.
　　�[9]
　　孙艺峰,王向阳,王春花.一种新的快速模糊C均值聚类图像分割算法［J］.小型微型计算机系统.2008, 29(2): 320-323.
　　�[10]
　　DENG Y, MANJUNATH B S. Unsupervised segmentation of color-texture regions in image and video ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(8): 800-810.
　　�[11]
　　ROTHER �C,� KOLMOGORO �V,� BLAKE �A.� �Grabcut-interactive� foreground extraction using iterated graph cuts ［J］. ACM Transactions on Graphics, 2004, 23(3/4): 309-314.
　　�[12]
　　SHI �J,� MALIK �J.� Normalized cuts and image �segmentation ［J］.� IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
　　
　　收稿日期:2011-07-06;修回日期:2011-08-23。
　　
　　 基金项目:
　　国家863计划项目(2006AA12A104)这个基金项目是否已经结题，请明确。未结题。
　　
　　 作者简介:
　　杨明川(1987-),男,四川南充人,硕士研究生,主要研究方向:图形图像处理； 吕学斌(1976-),男,湖北武汉人,讲师,博士,主要研究方向:目标跟踪、信息融合； 周群彪(1966-),男,江苏溧阳人,副教授,硕士,主要研究方向：计算机通信。

推荐访问:不完全 算法 分割 不完全�K�-means聚类与分类优化结合的图像分割算法 kmeans聚类算法图片分类 kmeans聚类算法例题