MeanShift算法在图像分割中的应用

韩俊，王保云

（1.云南师范大学信息学院，昆明 650500；2.云南师范大学数学学院，昆明 650500）

0 引言

近年来，大数据时代的到来促使计算机视觉技术飞速发展，图像分割是计算机视觉中的重要技术。图像分割就是把图像分成若干个特定的、具有独特性质的区域，提出感兴趣目标的技术和过程。图像分割被广泛应用于地理、军事、医学和人工智能中。

图像分割的方法众多，不同学者对分割方法的概括不同［1-2］。总的说来，图像分割可分为5类：基于阈值的分割、基于区域的分割、基于边缘的分割、基于特定理论的分割和基于神经网络的分割。MeanShift是密度类聚类算法的一种，用作图像分割时属于特定理论的分割方法。Mean-Shift于1975年由Fukunaga等［3］提出，他们使用了密度梯度对样本进行估计的方法，并用核函数对MeanShift中样本进行加权。Silverman B［4］提出的无参数核密度估计方法为MeanShift对样本的估计提供了系统的证明。Cheng Y等［5］介绍常用核函数原理并提出更多适用的核函数，为每个带宽内的样本分配权重，使得随着样本与被偏移点的距离不同，其偏移量对均值偏移向量的贡献也不同。文中对MeanShift算法应用于图像分割进行了实验，验证了算法良好的分割效果。

1 MeanShift算法理论基础

给定d维空间Rd中的n个样本点xi，i=1,…n，在x点的MeanShift向量为:

其中,Mh(x)称为MeanShift向量，图1中的宽箭头所示。Sh是一个半径为h的高维球区域，图1中实线大圈所示。xi表示在高维球区域内的样本点，图1中黑点所示。x表示初始聚类中心点，图1中的实线小圈中心位置。k表示在这n个样本点xi中,有k个点落入Sh区域中。

图1Sh区域内MeanShift示意图

式（1）是对高维球中的样本权重做均值计算，距离x点近的xi应该有更高的权重。引入核函数［3］和w(xi)［5］对MeanShift中样本进行加权的方法，将MeanShift算法扩展为如下形式：

其中，w(xi)≥0是一个赋给样本点xi的权重，G(x)是一个单位核函数，G(x)=g(‖x2‖)，h是核函数的带宽。在模式识别中，处理图像时经常用到的核函数如：Epanechnikov核、Uniform核和高斯核函数。

若不考虑权重w(xi)，通过式（2），计算某一次聚类中心与带宽内样本间的MeanShift向量为：

式（4）中mh(x)为x加上Mh(x)后新聚类中心的位置，图1中虚线小圈中心位置。

3 MeanShift图像分割

图像有分辨率和色彩等属性，用一种核函数或者固定的核带宽h并不能达到理想的处理结果。Comaniciu，Dorin等人［6］提出了空间域（分辨率）带宽hs和色域（色彩）带宽hr，并将空间域和色域统称为联合域。可以用核函数Khs,hr来估计图像中样本点x=(xs,xr)在联合域上的分布：

其中，p是色彩通道，C为一个归一化常数。当p=1表示一个灰度图像，p=3表示三通道的彩色图像，p＞3表示高维图像，比如卫星图像。

图像分割时，对聚为同一类的点取模态点（MeanShift迭代收敛的点）的色值，并选择性的对小于M个像素值的区域进行合并。下面是使用MeanShift在联合域上对彩色图像进行分割的步骤。

定义xi和zi，i=1,…,n,分别为滤波前的图像和滤波后的图像，Li为第i个像素对应的标签。给定收敛界限ε，将mh(x)替换成yj+1，并且带入hs和hr，则mh(x)变为如下的MeanShift形式：

（1）初始化j=1,yi,1=xi。

（2）根据式（5）计算yi,j+1，使得yi,j+1-yi,j收敛到ε，令zi=yi,c，yi,c为收敛后的位置。

（3）在联合域中，将距(hs,hr)窗口最近的模态点组成一类，用{Cp}p=1,…,m来表示。

（4）对于每一个i=1,…,n，赋值Li={p|zi∈Cp}，即：对于第i个像素，将符合p的包含在Cp中的zi赋值给标签Li。

（5）可选项：消除分割中总像素小于M的空间区域（M根据实际情况而定）。

将同属于标签Li区域中的像素色值更新为最后的模态点色值。迭代所有像素点，最终达到分割目的。下面是使用Uniform核对图像分割的效果。

图2 不同hs、hr和M对图像分割的影响

图2 不同hs、hr和M对图像分割的影响（续）

可以看出，色域带宽和最小合并像素控制着分割的区域数，分辨率带宽对分割结果的影响较小。

图3中，由于狗与草地在灰度图中灰度值相近，在hr大于2后，狗的轮廓已经不能保留，此时分割失败。彩色图中却能很好的分割。

图3 灰度图和彩色图分割对比

对图4中白框区域做灰度值分析如下。从图4中可以看出，分割后，聚为同一类的像素具有相同的色值，转化为灰度值图后更加平滑。

图4 白框内灰度值对比

对图像的分割方法众多，为了验证MeanShift算法在图像分割中的效果，表1是几个常用的机器学习分割方法和两个基于深度学习的分割方法deeplabv3、MaskRCNN的分割对比。选取了3类图像进行实验：第一类为背景、纹理和目标区域有较大差异，如表1中图①；第二类为单实例图像，背景和纹理与目标区域有较大差异，少噪点如表1中图②，多噪点如表1中图③；第三类为多实例图像，背景、纹理与目标区域难区分，难区分如图如表1中④，较难区分如表1中图⑤。除了边界分割和层次聚类分割，其他都是在RGB图像上实现分割。

从表1可以看出，第一类图像中，深度学习的两种方法未对实例进行训练，分割失败，其他分割效果良好；第二类图像中，每种方法都成功分割。阈值、SVM、MeanShift、深度学习对表1中图②分割效果优于其他几种。阈值、Mean-Shift、深度学习对表1中图③分割效果优于其他几种；第三类图像中，MeanShift、深度学习对表1中图④分割效果良好、其他分割效果较差。深度学习对表1中图⑤分割效果良好、其它分割效果较差。

表1 几种常见的图像分割方法分割效果对比

4 结语

在图像分割中，随着图像复杂程度的提升，MeanShift的聚类分割方法比其他传统的分割方法有更好的分割效果。基于深度学习的方法能带来更好的分割效果，但深度学习的方法仍然存在问题，如训练成本高、计算量大等。必须是预先训练过的实例，否则无法分割。MeanShift则具有不需要预训练、计算量小和易部署的特点。Mean-Shift是无参数的聚类方法，有着诸多优点，但算法中核函数的选择和核带宽的设定，对算法的收敛速度和计算量有着重要影响。核带宽h的选取关系着迭代速度和迭代后的效果，h过大存在过分割情况，h过小存在欠分割情况。

仍然有大批学者对MeanShift进行研究、探讨和改进，进一步提高算法的运算速度和结果准确性。赵胜男［7］提出了一种快速均值漂移的方法，李宏益等［8］提出并行运行算法的方法，他们提高了算法运行的速度。熊平等［9］使用区域相似性准则对分割不明显的区域进行合并。王晏等［10］在HSV色域中，定义了以高维球内样本点到基准点的颜色差值为核心的w(xi)计算函数，对图像分割取得了不错的效果。在大数据领域，MeanShift无参数的核密度聚类方法是一个很好的数据挖掘工具［11-13］。对MeanShift算法的改进和应用绝对不止文中所阐述的方向。如何降低算法复杂度，更有效的提升算法处理效果，需要广大学者做更进一步的研究。