基于Mean Shift聚类的多级阈值化方法

(1.周口师范学院机械与电气工程学院，河南周口 466001； 2.北京科技大学计算机与通信工程学院，北京 100083)

摘要： 为了解决多级阈值化技术中所选阈值的数量通常不能预先确定的问题，提出一种基于Mean Shift 聚类技术的新型多级阈值化方法.首先，通过使用Mean Shift技术探寻出潜在的模式中心，应用迭代的阈值选择方法来自动确定相邻模式中心的各个阈值；然后，采用多级阈值化对图像进行分割；最后，通过实验验证了基于Mean Shift聚类技术分割的图像相对于原始图像的对比度有了很大提高.该方法通过简单修改程序参数就能够灵活控制分割精度，可以广泛应用于单阈值分割、多级阈值分割和有损压缩等技术中.

关键词： 多级阈值化；图像分割；迭代阈值化；分割质量评估

0 引言

图像分割是进行图像理解和目标识别的一个必不可少的步骤，图像分割技术分为软分割和硬分割[1].聚类算法是软分割方法中最主要的图像分割算法，主要有两种：一种是K-means聚类[2]，其优点是易于实现但需要预先指定待分割图像中需要形成的群集的数量及中心; 另一种是模糊聚类[3]，当图像中不同物体之间没有明显的边界时，可以基于相似性准则采用模糊聚类的方法进行处理，但是它对噪声特别敏感，并且模糊关系的确定也非常繁琐.软分割计算起来相当费时；而硬分割是一种基于亮度信息的分割方法，它假设图像的直方图含有一个或多个峰值[4]，不需要图像的先验信息、计算简单，实时性高,但它忽略了图像的空间信息，阈值选择不当，经常会导致过分割或欠分割.实际上，该方法可以被认为是一个多级阈值化问题，其中所选取的多个阈值对应于相邻显著峰值的峰谷点.

多级阈值化技术将图像的直方图分为几个部分，当某一图像像素的特征值位于由某一对相邻阈值确定的范围时，该像素就被分到某一相应的部分.为了解决多阈值分割难题，近年来群智能技术被用来寻找最优阈值.Raja 等人[5]采用一个改进的粒子群(PSO)算法用于恶性肿瘤热图像的多阈值分割.Sarkar等[6]基于差分进化算法(DE)和最小交叉熵提出了一种新颖的多阈值彩色图像分割方法.

尽管上述方法可以确定出最优阈值，但是不能提供对应于图像直方图中潜在模式数量最优阈值数.因此，笔者提出了一种新型的最优多级阈值化方法，特别适用于具有多模态直方图的图像.首先使用Mean Shift程序确定出直方图的各个模态中心；然后使用一种迭代的阈值选取方法来确定相邻模态中心的各个阈值；最后利用已经确定的多个阈值对图像进行多阈值化分割.

1 算法部分

Mean Shift是一种非参数化的聚类方法[7]，其最大优点是它无须预先给出聚类的数量，且对聚类的形状也没有任何限制.作为一个迭代的模式探寻方法，Mean Shift程序利用核来计算观察窗口的特征加权平均，并可以准确地定位出聚类的中心并完成特征空间的划分.

对于d维空间Rd上的一个n点的数据集合{xi}i=1,…,n，点x处的多变量核密度估计为

式中：k(x)是侧面轮廓函数；h是窗口半径.令式(1)的梯度为0，得到密度函数的驻点为

式中:g(x)=-k′(x)是核函数G(x)的侧面轮廓函数.

连续迭代计算Mean Shift 矢量，并进行移位直到程序收敛，就能定位出局部模态.迭代的方程为

式中：y1为核窗口的初始位置中心；yj+1为yj处利用核G和窗口半径h计算出的加权平均.

对于Epanechnikov核为

式中：cd为单位d维球体的体积.

Mean Shift 的公式为

式中:Sh(yj)为中心位于yj；半径为h；包含nyj个数据点的超球体.

选择图像像素的灰度值作为特征空间，Mean Shift 程序可以探寻出其潜在的概率密度模态. 算法的步骤描述如下：

(1)将特征空间划分为n个非重合的同等大小部分.每一部分的大小为(Gmax-Gmin)/n，其中Gmax 和 Gmin分别为图像像素灰度值的最大值和最小值.为了避开低密度区域，要保证每一部分中像素的数量不少于一个阈值T1.

(2)运行Mean Shift 程序n次以得到n个收敛点，Mean Shift程序和核半径为h=(Gmax-Gmin)/n.

(3)将距离小于一个预设阈值T2的相邻收敛点合并为一点，求出m(mlt;n) 个潜在的概率密度模态中心.

为了将图像灰度分为m个类，比如0～255，考虑到图像灰度范围的上下限已确定，需要再确定K个阈值，满足K=m-1.在下文中采用一种迭代阈值选取方法来确定K个阈值.

为了使分割方法更具鲁棒性，阈值应该能够自动地被确定出来.因此，自动阈值选择是图像分割的一个关键步骤.Ridler and Calvard [8]提出了一种迭代的阈值选择方法，该方法描述如下.

给定一幅图像，假定I(i,j)是(i,j)处像素的灰度值，其中1≤i≤M and 1≤j≤N,0≤I(i,j)≤L-1，L为图像的灰度级别.首先计算出图像的灰度直方图，假定希望能找到一个阈值T并利用该阈值将图像分割为一个二进制图像.在二进制图像中，所有灰度值低于T的像素，其灰度值都被A所取代；所有灰度值高于T的像素，其灰度值都被B所取代.将误差函数定义为二进制图像和原始图像相应像数灰度值差的平方和.使用积分以方便表达，则误差函数可以表示为：

e2=

(k-A)2h(k)dk+

(k-B)2h(k)dk,

式中,k为像素的灰度值；h(k)为灰度值在直方图中出现的次数.分别令e2对T、 A 和 B的偏导数为0可以得到：

实际上，A 和 B分别为直方图被阈值T分成的两部分的均值.

注意到阈值T仅由两部分的均值A和B确定，而这两部分的均值A和B又只有当T确定了以后才能被计算出来.所以需要使用迭代算法：首先选定初始阈值做为起始点；然后利用此阈值将直方图分为两个部分，分别计算出两部分的均值，并将阈值更新为两部分均值的和的一半，该过程反复执行直到阈值收敛；最后利用多阈值化方法图像的灰度范围将被K个阈值分割为K+1个部分.

给定原始图像I(i,j)，利用Mean Shift程序确定阈值的数量K，令Tmin=0及Tmax=L-1，利用迭代阈值选取方法计算出K个阈值{T(i)|i=1,2,…,K}，其中T(i)lt;T(i+1).K个阈值将图像直方图分割为m个互不重叠的区域：

其中,J为分割图像.

2 分割质量评估

图像分割质量的评估没有一个标准的方法，最常用的是主观评估，这种方法主观性太强，而非监督性评估方法由于可以克服上述缺点，受到越来越多的关注.Haralick等[9]给出了高质量图像分割结果的四条准则：①分割出的各个区域内部像素的特性要尽量一致；②相邻区域之间像素特性的差异要大；③区域内部没有孔洞；④区域边界在空间位置上要精确，并且不能支离破碎.

前两条被用于审查图像中目标的特性，被称为特性准则；后两条被称为语义准则，被用来衡量人如何将一个区域识别为一个目标[10].

Zhang[11]引入期望区域熵作为区域内一致性的度量.假定原始图像被分割成N个区域，采用Rj来表示区域j(1≤j≤N)中的像素集合；Sj表示区域j的面积，Sjm表示对应于区域j的原始图像中具有灰度值m (0≤m≤L-1)的像素个数，那么区域j的熵定义为

而分割的期望区域熵为

式中：SI是图像I的面积，表示图像内部具有更高的相似度.

Biswas等[12]提出了用IQI(image quality index)来度量区域间的差异.对于一个行数和列数分别为M和N的图像I，令I(i,j)表示(i,j)处像素的灰度值.则IQI被定义为

IQI反映的是沿着区域间边界图像像素性质的平均对比度，值越大表明图像的平均对比度越大.

3 实验结果

选择两组复杂度不同的图像来验证该多阈值图像分割方法的有效性.第一组图像是一幅合成图像“Gray8”；第二组图像包含从Berkeley Segmentation Dataset[13]选出来的自然图像35 010、126 007、241 004、113 016、385 039、368 016.笔者提出的多阈值分割方法包括3个参数：核半径h控制着分割的敏感度；阈值T1暗示了特征空间中最小可以接受的概率密度；阈值T2对应于相邻两个收敛点的最小距离.实验选取h=T2=(Gmax-Gmin)/10，其中，Gmax和Gmin分别为图像像素灰度值的最大值和最小值；T1=0.001×(M×N)，其中M和N分别为图像的行列数.

图1和图2给出了两组图像的分割结果.中间图像显示了直方图分割的过程示意图，矩形表示整个灰度直方图中被划分成的几个互不重叠的部分，每个矩形的中心是其Mean Shift程序核窗口的起始点，每一个五角星代表了相应Mean Shift程序的收敛点，如果相邻收敛点的距离小于核窗口的半径则将此相邻收敛点合并以得到模态中心，各模态中心用黑色三角形表示，相邻模态中间的阈值由迭代阈值选取方法选定并由短划线表示其位置.

图1所示的8个离散的灰度值被成功地检测出来(图1(b))，并给出了比较精确的分割结果(图1(c)).对于图2中的2幅自然图像，也给出了令人满意的分割结果，并且相对于原始图像，分割图像的对比度提高了许多.

采用本文方法得到的图像的分割结果如图3所示，从左到右分别为“Lena”“Cameraman”和“Baboon”;其中第一行显示了原始图像，第二行为笔者所提多阈值分割方法得到的图像分割结果，其中合理选择分割半径后得到K=6个分割阈值.

将本文分割方法与典型的多阈值分割方法PSO及DE算法进行了比较.分割图像的性能参数选择前文所述的期望区域熵Hr和图像质量指标IQI，比较结果见表1.可以看出，对于对比度比较明显的自然图像，选择同样数量的阈值数是时，

本文方法的性能优于PSO和DE算法.但是对于纹理较丰富的图像如Baboon，本文方法稍逊于PSO和DE算法.

本文分割算法在Berkeley Segmentation Dataset测试数据上获得了良好的分割效果.为了展示本文分割方法的性能，如图3所示，选取其中的几幅典型图像35 010、126 007、241 004、113 016、385 039、368 016，实验选取分割阈值个数为 K=6.

与各群智能算法一样，本文方法也具有随机性.表1和表2为几种方法的最优结果.分割算法对每幅图像重复运行50次后，分别计算目标函数的均值和方差，结果如表2，3所示，可以看出本文的图像分割算法具有良好的稳定性.

对于K=6，将本文方法的计算时间与PSO和DE方法进行了比较，结果如表4所示.结果显示，大部分情况下本文算法运行时间最少.

笔者采用的多阈值化方法用到了3个参数：核半径h、阈值T1和阈值T2.T1和T2对分割结果的影响要远小于h.一般来说，若选取较大的T1值，则Mean Shift程序只能探测出最重要的模

态，这通常会造成欠分割；而若选取较小的T1值，则Mean Shift程序还能探测出次要的模态，这通常会造成过分割.实际上，T1选取为整个图像大小的1%就可以得到较好的自然图像分割结果. 而T2对分割结果影响较小，通常令T2等于核窗口的半径,因此我们主要讨论h的影响.

作为一种非参数化的密度估计方法，Mean Shift程序的估计精度会受到核半径h的影响;通常较小的核半径值会使程序得到太多模态；而较大的核半径值会生成平滑的密度和较少数量的模态.最常用的方法是选择不同的核半径，将算法运行多次直到分割性能达到最优. Comaniciu[14]用比较复杂的方式解决了核半径的选择问题，实验显示，当核半径选为(Gmax-Gmin)/10时，就可以得到较好的分割结果，分割图像的对比度提高了许多.可以看到，随着核半径的增加，Hr越来越小，表明随着图像被划分的区域数目的增多，各个区域内像素特性的差异越来越小；IQI也越来越小，表明区域间像素特性的差异越来越小，尽管如此，任何一个分割结果的IQI都要比原始图像的IQI大.因此，从图像压缩的角度来看，本文方法也具有一定的参考价值.

4 结论

为了解决多级阈值化图像分割方法中阈值的数量不能预先确定这一难题，提出了一种新型的基于聚类技术的多级阈值化方法.首先使用Mean Shift技术搜索到潜在的模式中心点；然后应用迭代的阈值选择方法来确定相邻模式中心的各个阈值；最后采用多级阈值化方法对图像进行分割，并通过大量实验得到了验证.此外，还应用期望区域熵Hr和图像质量指标IQI对分割结果进行了评估，显示了本文方法的有效性.本文方法可以通过简单地修改程序参数来控制分割的精度，并且无须预先确定直方图中潜在的模态数量，因此，本文方法可应用于单阈值分割、多级阈值分割和有损压缩等技术中.

[1] TOKAS N, KARKRA S, PANDEY M K. Comparison of digital image segmentation techniques a research review [J]. International journal of computer science and mobile computing, 2016(5):215-220.

[2] DHANACHANDRA N, MANGLAM K, CHANU Y J. Image segmentation using K-means clustering algorithm and subtractive clustering algorithm[J]. Procedia comouter science, 2015,54: 764-77.

D, Y

ez J, GAUDA C.Fuzzy image segmentation based upon hierarchical clustering[J]. Knowledge based system,2015, 87(c):26-37.

[4] OTSU N. A threshold selection method from grey-level histograms[J]. IEEE transaction on systems man amp; cyberntics,2014,9(1):62-66.

[5] RAJA N S M, SUKANYA S A, NIKITA Y.Improved PSO based multi-level thresholding for cancer infected breast thermal images using otsu[J].Procedia computer science, 2015,48:524-529.

[6] SARKAR S, DAS S,CHAUDHURI S S.Amultilevel color image thresholding scheme based on minimum cross entropy and differential evolution[J].Pattern recognition letters,2015,54:27-35.

[7] CHENG Y.Mean shift, mode seeking, and clustering[J].IEEE transactions on pattern analysis and machine intelligence,2012,17(7):790-799.

[8] RIDLER T W,CALAARD S.Picture thresholding using an iterative selection method[J].IEEE transactions on systems man amp; cybernetics,2010,8(8):630-632.

[9] HARALICK R,SHAPIRO L.Survey: image segmentation techniques[J].Computer vision, graphics and image processsing,2013(29):100-132.

[10] 余金煌，陶同赞.小子域滤波在高密度电法图像处理中的应用[J].水电技术，2015(1)：5-10.

[11] ZHANG H,FRITTS J E,GOLDMAN S A.A region entropy-based objective evaluation method for image segmentation[C]∥2009 IEEE Instrumentation and Measuren Technology conference. Singapore:IEEE 2014: 38-49.

[12] BISWAS S,LOVELL B C.Bezier and splines in image processing and machine vision[M].London: Sprin-ger,2009.

[13] Berkeley segmentation dataset[EB/OL]. [2017-03-01].http://www.cs.berkeley.edu/projects/vision/bsds. 2012.

[14] COMANICIU D.An algorithm for data-driven bandwidth selection[J].IEEE transactions on pattern analysis and machine intelligence,2013,25(2):281-288.

Based on the Mean Shift Clustering Multilevel Threshold Method

(1.Mechanical and Electrical Engineering，Zhoukou Normal University，Zhoukou 466001，China; 2.School of Computer amp; Communication Engineering， Beijing University of Sclence amp; Technology， Beijing 100083,China)

Abstract: In order to solve the problem that the number of selected thresholds in multilevel thresholds cannot be usually predetermined, a novel multi-level thresholding method based on Mean Shift Clustering technique was proposed. Using Mean Shift technology to explore the potential mode center, the various thresholds of adjacent to the mode center was automatically determined by using of iterative threshold selection method, and then the method of multi-level threshold was used for image segmentation.The experimental results showed that, relative to the original image, contrast of the image split with Mean Shift clustering technique was greatly improved.This method could control the segmentation precision flexibly by simply modifying parameters of the program,and could be widely used in the technology of single threshold segmentation, multi-level threshold segmentation and detrimental compression and other technologies.

Key words: multilevel thresholding; image segmentation; iterative threshold selection; segmentation evaluation

基金项目：国家自然科学基金资助项目(61401526)；河南省自然科学基金资助项目(152300410134)

作者简介：程全(1978— )，男，河南沈丘人，周口师范学院副教授，主要从事智能控制研究，E-mail:quan8888@126.com.