自适应的均值漂移分割算法

马 瑜，梁慧琳，张艳宁，徐 爽

(1.西北工业大学计算机学院，陕西西安710129;2.宁夏大学研究生院，宁夏银川750021)

1 引言

均值漂移聚类是一个基于Parzen窗的非参数核密度估计理论，为寻找局部密度的最大处。在均值漂移过程中，任何数据点都可以作为初始点进行均值漂移。将收敛到同一个点的像素点进行聚类，漂移过程中，由图像自动决定每一类的像素数，和类的边界［1］。

Comaniciu和Ramesh基于可变的窗宽密度估计提出一种自适应的均值漂移［2］，并且应用于图像分割和聚类［3］。对自适应算法的提出主要是为下一步图像处理做基础。周芳芳、樊晓平采用自适应均值漂移聚类算法为三维数据场设计传递函数［4］。Lei Lin提出一种针对三维MR图像的自适应分割方法，其主要思想也是采用自适应的带宽设计，再加入 K-Means算法［5］。Xinhong Zhang为了图像处理时降低计算时间和计算维度，提出自适应分割算法，其主要思想是运用了对一幅图像的概率密度估计来计算进行带宽设计，再加入本地特征散列法进行图像分割 。袁胜智、谢晓方提出了一种基于Kalman-mean shift的自适应跟踪算法，在mean shift算法中加入了一个尺度更新项，通过尺度更新对运动目标，特别是目标尺寸变化的目标进行自适应跟踪［7］。

基于图像处理中对图像分割的高效、精确的要求，每一幅图像带宽范围不同，而且，一幅图像，有的部分需要精细地分割，有的部分又不需要。本文提出一种自适应的窗宽计算方法。由每个像素点与周围点的关系以及图像的直方图来计算每个像素点的窗宽，从而进行自适应的分割。

2 均值漂移算法简介

2.1 均值漂移向量

给定d维空间Rd中的S个样本点s。在x∈X处，改进的样本均值公式为［8］:

样本均值与像素点的偏移量m(x)－x称为均值漂移向量，记为Mh(x)。其中，K称为核函数。核函数可以控制因距离不同，对像素点X的均值漂移向量贡献的重要性不同。K为核函数的条件为:它存在一个剖面函数，即:

并满足:

(1)k是非负的;

(2)k为非增，如果 ka＜b，k(a)≥k(b);

一般常用的核函数有两种，单位均匀核函数与单位高斯核函数。

单位均匀核函数:

w(s)为权值，权值用来控制在核函数范围内，不同的样本点，重要性不同。它满足归一化条件:

均值漂移向量表示为:

2.2 均值漂移算法

均值漂移算法是寻找局部密度最大值的过程。

均值漂移迭代算法执行过程如下:

(1)计算样本均值m(x)。

(2)计算样本均值与像素点之间的偏移量m(x)－x。

(3)判断如果样本均值与像素点之间的偏移量小于一个给定的误差值，结束循环，样本均值为像素点收敛的模式点;否则把m(x)赋给x，执行(1)继续。

3 自适应窗宽

在聚类中，带宽h决定了核函数的影响范围，窗宽h对核密度函数估计过程以及最终的聚类结果都有很大影响。如果h取值很小，密度函数f(x)相当于n个数据对象为中心的函数的叠加，每个像素点周围的密度函数值很小，聚类结果会产生很多类。如果h无穷小，那么每个像素的密度等于1/n，并且自成一类;如果h取值很大，f(x)称为n个变化缓慢且宽度很大的基函数的叠加，每个像素周围的密度函数值比较大且近似相等，相距较近的聚类将被合并。如果h无穷大，所有像素的密度等于1且被聚合为一类。所以，尽可能准确的密度估计结果和聚类结果来自于窗宽h的选择。选择窗宽h时应尽可能的使密度函数f(x)体现原始数据的分布特性。确定窗宽h后，通过搜索密度函数的局部极大值点实现图像的分割［9］。

3.1 直方图

本文使用直方图对图像的像素点的特征进行统计。直方图是一种统计图，对于一幅图像来说，通过统计图像中各个像素点的数量，从而对图像的像素分布有一个直观了解。通常，通过直方图可以对图像进行直方图归一化，直方图拉伸，直方图匹配。

一幅数字图像在范围［0，G］内共有L个灰度级，其直方图定义为离散函数h(rk)=nk，其中rk是区间［0，G］内的第K级亮度，nk是灰度级为rk的图像中的像素数。

其中，δ是 Kronecher符号［10］。

3.2 图像的直方图获取

对于一幅图像来说，如果它是灰度图像，则为单通道图像，如果它为彩色图像，应该包含三个通道:R(Red)，G(Green)，B(Blue)。彩色图像和灰度图像的直方图获取步骤是相同的，对于彩色图像，计算其二维直方图。

对于RGB图像，由于其处理时计算量较大。先将其转化到HSV空间(色调、饱和度、数值)。该颜色系统比RGB系统更接近于人们的经验和对颜色的感知。彩色图像提取其H、V颜色通道的，统计每种颜色分量的像素数占图像总像素数的比例，从而得到图像各种颜色分量的比例分布。

灰度图像直接计算其灰度像素值的直方图，并将其归一化，进行保存。

3.3 自适应窗宽h的计算

目前带宽的计算主要有两类，一类是固定带宽，一类是自适应带宽。固定带宽在迭代过程中，带宽h保持不变，因此需要计算相对于全局的最优带宽，在图像分割过程中，效率低，分割效果不好。而且，不同的图像，最优带宽并不在一个范围内，图像分割中参数的确定是一个很大的工程。因此，图像分割中，采用自适应带宽，理论上会获得比较好的分割效果。根据图像像素点的局部特征，自适应的设计迭代带宽，对密度大的区域采用小带宽，对密度小的区域则采用大带宽。

由以上的说法，令固定带宽h=h(xi)，即每个像素点的带宽均不一样。一幅图像，如果从它的直方图来统计看，这个统计思想非常地符合在核函数中窗宽的选择思想，即对密度大的区域采用小带宽，对密度小的区域则采用大带宽。像素分布于带宽成反比关系。所以，使用二维直方图对核函数的窗宽进行计算，是有用的。根据直方图的定义，直方图也可以看作一个归一化的概率密度函数f(xi)［11］。将每个样本点的密度估计用作选择h(xi)的特征，取f(xi)倒数的平方根:

式中，h0是一个初始的固定带宽，λ是常数。

为获得一个自适应的带宽，f(xi)，λ必须首先计算。自适应窗宽的均值漂移算法步骤为:

(1)找到一个对图像所有像素点都满足的估计f(xi)，在这，f(xi)为我们所取图像的二维直方图。

(2)窗宽因子λ的定义为:

(3)对于每个像素点 xi计算其自适应的窗宽h(xi):

则自适应的均值漂移向量可表示为:

将计算后的每个点的窗宽在分割中带入，便可得到自适应的分割结果。

4 实验结果及分析

本实验使用 Intel Core2，2.10 GHz，2G内存的HP笔记本，软件使用Matlab 2008版本。与原均值漂移分割算法［7］从分割结果进行对比。hr为均值漂移算法的值域带宽，hs值漂移算法的为空域带宽。分割后图像聚类区域像素点最小数量为500。算法中最大迭代次数为100，误差系数ε=0.01。本文采用图像大小为256×256或120×90。

图1 灰度图像的分割

取一幅灰度图像，如图1(a)所示图1(a)的灰度图像相对较为复杂。图1(b)为使用本文自适应算法进行图像分割的结果。图1(d)、(e)、(f)分别为使用固定带宽的均值漂移算法分割后的结果。对于固定带宽参数的选择，值域带宽选定16。进行频域带宽的单变量参数变化。由图可以看出，在图1(f)中带宽选择小了，分割结果太过精细，无法很好的将背景和前景分开，这就是过分割问题，对于一些不存在的细节也会分割。图1(d)和图1(e)进行对比，图1(e)能相对较好地将人的轮廓分割出来，但是，图像分割得结果不完整。而自适应的均值漂移算法，不仅很好地将人完整地分割，而且，在相机的脚架以及相机部分，都很清晰地分割出来。我们从图1(b)中可以看到一幅很完整的图像，包括图像的前景、背景以及一些细节。

图2(a)为一幅复杂的彩色图像。图2(b)为使用本文自适应算法进行图像分割的结果。图2(d)、(e)、(f)分别为使用固定带宽的均值漂移算法分割后的结果。对于固定带宽参数的选择，值域带宽选定16。进行频域带宽的单变量参数变化。图2(d)中，树叶部分好多细节没有分割出，前景和背景很模糊。图2(f)较好的分割出了树叶的部分，但是相比图2(e)，在蓝天部分，地面部分又存在过分割的问题。图2(b)图使用自适应的分割算法。不仅很好地分割出树叶，而且对于地面和蓝天，分割精度又不至于太细导致过分割。

图2 彩色图像的分割

5 结论

本文根据在图像处理中对图像分割前期准备工作高效、准确的要求，结合图像的直方图，提出一种自适应的均值漂移分割算法。算法首先利用图像的直方图估计出图像的概率密度。对每个像素点根据其周围特征以及概率分布计算它的带宽值。使得在均值漂移滤波时可以达到自适应的效果。如果没有自适应带宽，那么在确定参数时需要大量的实验。实验结果表明，改进算法很好的解决了固定带宽均值漂移算法在确定带宽时效率低，分割效果差的问题。自适应的均值漂移分割算法可以有很好的分割结果。

［1］ Zhang Xinhong，Cui Yanbin．An adaptive mean shift clustering algorithm based on locality-sensitive hashing［J］．Optik，2012，123(20):1891 －1894．

［2］ D Comaniciu，V M P Ramesh．The variable bandwidths mean shift and data-driven scale selection［J］．IEEE Int．Conf．Comput．Vis，2001，(1):438 －445．

［3］ H B Helbig，M O Ernst．Optimal integration of shape information from vision and touch［J］．Exp．Brain Res．2007，4(179):595 －606．

［4］ Zhou Fangfang，Fan Xiaoping．Designing transfer function based on adaptive bandwidth mean shift clustering algorithm［J］．Information and Control，2007，36(5):585 －591．(in Chinese)周芳芳，樊晓平．基于自适应带宽均值漂移聚类算法设计传递函数［J］．信息与控制，2007，36(5):585－591．

［5］ Lei Lin．Adaptive pixon represented segmentation(APRS)for 3D MR brain images based on mean shift and Markov random fields［J］．Pattern Recognition Letters．2011:1036－1043

［6］ Zhang Xinhong．An adaptive mean shift clustering algorithm based on locality-sensitive hashing［J］．Optik．2012:1891－1894．

［7］ Yuan Shengzhi，Xie Xiaofang．Bandwidth-adaptive tracking algorithm based on Kalman-mean shift method［J］．Laser＆ Infraded，2009，39(5):558 －561．(in Chinese)袁胜智，谢晓方．一种基于Kalman-mean shift的自适应跟踪算法［J］．激光与红外，2009，39(5):558 －561．

［8］ Y Cheng，Mean shift，mode seeking，and clustering［J］．IEEE Trans．Pattern Anal．Machine Intell，1995，17:790－799．

［9］ Gan Wenyan，Li Deyi．Hierarchical clustering based on kernel density estimation［J］．Journal of System Simulation，2004，16(2):302 －307．(in Chinese)淦文燕，李德毅．基于核密度估计的层次聚类算法［J］．系统仿真学报，2004，16(2):302 －307．

［10］ Hong MingJian．Study on the Adaptive Histogram Modification ForImage Enhancement［D］．Chongqing:Chongqing University，2002，4．(in Chinese)洪明坚．图像增强的自适应直方图修正算法研究及其应用［D］．重庆:重庆大学，2002，4．