【导读】这是一篇方法总结，做了简单的实验，内容较为浅显。

   图像分割是计算机视觉中的重要技术。图像分割就是把图像分成若干个特定的、具有独特性质的区域，提出感兴趣目标的技术和过程。图像分割被广泛应用于地理、军事、医学和人工智能中。图像分割的方法众多，总的说来，图像分割可分为5类：基于阈值的分割、基于区域的分割、基于边缘的分割、基于特定理论的分割和基于神经网络的分割。MeanShift是密度类聚类算法的一种，用作图像分割时属于特定理论的分割方法。MeanShift于1975年由Fukunaga等提出，他们使用了密度梯度对样本进行估计的方法，并用核函数对MeanShift中样本进行加权。Silverman B提出的无参数核密度估计方法为MeanShift对样本的估计提供了系统的证明。Cheng Y等介绍常用核函数原理并提出更多适用的核函数，为每个带宽内的样本分配权重，使得随着样本与被偏移点的距离不同，其偏移量对均值偏移向量的贡献也不同。下文是MeanShift算法在图像分割中的实验及效果。

1、MeanShift算法理论

给定$d$维空间$R^d$中的$n$个样本点$x_i,i=1,2,...,n$在$x$点的MeanShift向量为:

\[M_h(x)=\frac{1}{k}\sum_{x_i\in S_k}(x_i-x)\]  (1)

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

图1 $S_h$ 区域内MeanShift示意图

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

\[M_h(x)=\frac{\sum_{i-1}^n G(\frac{x_i-x}{h})w(x_i)(x_i-x)}{\sum_{i=1}^nG(\frac{x_i-x}{h})w(x_i)} \]  (2)

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

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

\[M_h(x)=\frac{\sum_{i=1}^nG(\frac{x_i-x}{h})x_i}{\sum_{i=1}^nG(\frac{x_i-x}{h})}-x\] (3)

令

\[m_h(x)= \frac{\sum_{i=1}^nG(\frac{x_i-x}{h})x_i}{\sum_{i=1}^nG(\frac{x_i-x}{h})}\]

则式（3）可写为：

\[m_h(x)=x+M_h(x)\]

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

2、MeanShift图像分割

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

\[K_{h_r,h_s}=\frac{C}{h_s^2h_r^p}k \left( \|\frac{x^s}{h_s}\|^2 \right) k \left( \|\frac{x^r}{h_r}\|^2 \right)\]

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

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

定义$x_i$和$z_i,i=1,...,n$，分别为滤波前的图像和滤波后的图像，$L-i$为第$i$个像素对应的标签。给定收敛界限$\epsilon$，将$m_h(x)$替换成$y_{j+1}$，并且带入$h_s$和$h_r$，则$m_h(x)$变为如下的MeanShift形式：

（1） 初始化$j=1,y_{i,1}=x_i$。

（2） 根据式（5）计算$y_{i,j+1}$，使得$y_{i,j+1}-y_{i,j}$收敛到$\epsilon$，令$z_i=y_{i,c}$。$y_{i,c}$为收敛后的位置

（3） 在联合域中，将距$(h_s,h_r)$窗口最近的模态点组成一类，用$\{C_p\}_{p=1,...,m}$来表示。

（4） 对于每一个$i=1,...,n$，赋值$L_i=\{p|z_i\in C_p\}$，即：对于第$i$个像素，将符合$p$的包含在$C_p$中的$z_i$赋值给标签$L_i$。

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

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

图2，不同$h_s$、$h_r$和$M$对图像分割的影响

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

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

上图中，由于狗与草地在灰度图中灰度值相近，在$h_r$大于2后，狗的轮廓已经不能保留，此时分割失败。彩色图中却能很好的分割。对图5中白框区域做灰度值分析如下：

图4，白框内灰度值对比    (a)白框内灰色值（b）彩色图分割后转灰度值

从上图中可以看出，分割后，聚为同一类的像素具有相同的色值，转化为灰度值图后更加平滑。

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

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

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

3、讨论

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

参考文献

[1]杨晖,曲秀杰图像分割方法综述[J]电脑开发与应用,2005(03):21-23

[2]林开颜,吴军辉,徐立鸿彩色图像分割方法综述[J]中国图象图形学报,2005(01):1-10

[3]Fukunaga K, Hostetler L The estimation of the gradient of a density function, with applications in pattern recognition[J] IEEE Transactions on information theory, 1975, 21(1): 32-40

[4]Dehnad K Density estimation for statistics and data analysis[J] 1987

[5]Cheng Y Mean shift, mode seeking, and clustering[J] IEEE transactions on pattern analysis and machine intelligence, 1995, 17(8): 790-799

[6]Comaniciu D, Meer P Mean shift: A robust approach toward feature space analysis[J] IEEE Transactions on pattern analysis and machine intelligence, 2002, 24(5): 603-619

[7]赵胜男 Mean Shift图像分割算法的改进[D]山西大学,2016

[8]李宏益,吴素萍Mean Shift图像分割算法的并行化[J]中国图象图形学报,2013,18(12):1610-1619

[9]熊平,白云鹏带宽自适应Mean Shift图像分割算法[J]计算机工程与应用,2013,49(23):174-176+234

[10]王晏,孙怡自适应Mean Shift算法的彩色图像平滑与分割算法[J]自动化学报,2010,36(12):1637-1644

[11]沈辉,李世银基于WiFi与PDR融合的井下定位方法[J]煤矿机械,2020,41(10):202-204

[12]李华昌,揭东帅,徐敏电力市场化改革下的电价敏感性研究[J]中北大学学报(自然科学版),2020,41(05):431-436

[13]邓浩伟, 杨书新, 裴嘉琪,等 基于矩阵分解和Meanshift聚类的协同过滤推荐算法[J] 计算机科学与应用, 2020, 010(004):P649-658

作者：韩俊 排版：wangbaoyun  审核：wangbaoyun