MeanShift算法相关应用

    廖礼

    摘 要 MeanShift算法是一种无参数概率密度估计的算法。通过概率密度函数和有限次的迭代，能快速找到数据分布的模式。具有原理简单、参数少，无需预处理等诸多优点，被广泛应用于图像平滑、边缘检测、目标跟踪等领域。本文简要介绍了MeanShift算法的几种应用。

    关键词 MeanShift 图像平滑 边缘检测 目标跟踪

    中图分类号：TP391.41 文献标识码：A

    0引言

    MeanShift （均值漂移）是一种非参数概率密度估计的方法，一种最优的寻找概率密度极大值的梯度上升法，在解决计算机视觉底层过程中表现出了良好的鲁棒性和较高的处理速度。MeanShift最早于1975 年由Fukunaga等人在关于概率密度梯度函数的估计一文中提出。MeanShift 算法一般指的是一个迭代的步骤，即先算出当前点的漂移均值，移动该点到其漂移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。随着时间的推移，MeanShift也由最基本的形式得到了完善和发展。首先，Yizong Cheng定义了一族核函数，使得随着样本与被漂移点的不同，其漂移量对均值漂移向量的贡献也不同；其次又设定了一个权重系数，使得不同样本点的重要性不一样。因此MeanShift 的适用范围得到了扩大。接着Comaniciu 等人将MeanShift 算法运用到了特征空间的分析之中，对图像进行平滑和分割处理，并把非刚体的跟踪问题近似为一个MeanShift 最优化问题，使得跟踪可以实时地进行。由于MeanShift 算法完全依靠特征空间中的样本点进行分析，不需要任何先验知识，收敛速度快，近年来在图像平滑、边缘检测以及目标跟踪等许多计算机视觉研究领域开始得到广泛的关注和应用。

    1 MeanShift算法的相关应用

    1.1基于MeanShift的图像平滑

    一幅图像可以表示成一个二维网格点上p维向量，每一个网格点代表一个像素，p=1表示这是一个灰度图，p=3表示彩色图，p>3表示一个多谱图，网格点的坐标表示图像的空间信息。统一考虑图像的空间信息和色彩（或灰度等）信息（这里选择L*U*V彩色空间），组成一个p+2维的向量x=（xs，xr），其中xs表示网格点的坐标，表示该网格点上p维向量特征。所谓p+2维空间指的是图像二维坐标空间和p维值域空间。用核函数K来估计x的分布，K具有如下形式：

    其中hs，hr控制着平滑的解析度，C是一个归一化常数。分别用xi和zi，i=1，…，n表示原始和平滑后的图像。用MeanShift算法进行图像平滑的具体步骤如下：

    对每一个像素点：

    （1）初始化j=1，并且使yi，1=xi；

    （2）运用MeanShift算法计算yi，j+1，直到收敛。记收敛后的值为yi，c；

    （3）赋值zi=（x，y）。

    1.2基于MeanShift的边缘检测

    基于MeanShift的边缘检测同样是在p+2维空间中，选用YCbCr彩色空间作为算法的彩色度量空间，以像素的MeanShift偏移向量为重要特征，并考虑像素点相互空间关系的边缘检测算法。首先通过MeanShift算法计算出图像中各个像素的MeanShift最终偏移量，然后根据MeanShift理论以及该偏移量性质，同时引入MeanShift向量的方向和长度进行边缘检测。

    算法步骤：

    （1）根据zi=（x'iMS）=（x'i，y'y'）取得图像中每一个像素点的MeanShift偏移量MSvector；

    （2）如果像素点对应的MSvector向量同时满足如下条件，则该点为边缘轮廓点： |MSvector|MST； 该点的领域点中，至少有一个点的MSvector矢量方向和该点的MSvector矢量方向的夹角介于160度到200度之间。

    其中，xi和zi（i=1，2，…，n），分别为d维空间中的输入图像像素和输出图像像素。

    MeanShift偏移量表示为MSvector（xi，yi），其中（xi，yi）为图像中像素坐标值，i=1，2，…，n，这样越靠近边缘的点，其离图像聚类中心点就越远，相应的|MSvector|值越大。

    1.3基于MeanShift的目标跟踪

    基于Meanshift 的目标跟踪算法是一种半自动跟踪算法，在起始帧需要对跟踪目标进行初始化，首先通过鼠标选定要跟踪的目标区域，这个目标区域也是核函数作用的区域，区域的大小等于跟踪窗口半径h （或称核函数带宽）。对在目标区域内的像素点，计算特征空间中每个特征值的概率，即为目标模型的描述。在后续的每帧中可能存在目标候选区域，对其特征空间每个特征值的计算称为候选模板的描述。利用Bhattacharyya相似函数（简称BH系数）度量初始帧目标模型和当前帧候选模型的相似性，通过求相似函数最大得到关于目标的MeanShift 向量，这个向量即是目标从初始位置向正确位置移动的向量，由MeanShift 算法的收敛性，不断迭代计算MeanShift 向量，在当前帧中，最终目标会收敛到目（下转第276页）（上接第274页）标的真实位置，从而达到跟踪的目的。

    算法步骤：

    （1）选中物体，记录输入的方框和物体；

    （2）求出视频中有关物体的反向投影图；

    （3）根据反向投影图和输入方框进行MeanShift迭代，由于它是重心移动，即向反向投影图中概率大的地方移动，所以始终会移动到目标上；

    （4）下一帧图像时用上一帧输出地方框来迭代即可。

    2总结

    本文简要介绍了MeanShift的一些典型应用，显示出了MeanShift的强大功能。当然Meanshift算法的应用不仅仅局限于此。随着Meanshift算法的不断改进，其应用领域也不断扩展，应用前景也会越来越好。

    参考文献

    [1] 宋新，沈振康，王平，王鲁平.Mean shift 在目标跟踪中的应用[J].系統工程与电子技术，2007（29）.

    [2] Fukunaga，K.&L.D.Hostetler.The Estimation of the Gradient of a Density Function[J].IEEE Trans. Information Theory， 1975（21）： 32-40.

    [3] Cheng，Y.Z. MeanShift， Mode seeking， and Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1995，17（08）： 790-799

    [4] Dorin Comaniciu. Mean Shift：A Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002.

    [5] 田莘.基于MeanShift算法的目标跟踪问题研究[D].西安：西安科技大学，2011.

    [6] 何恒攀，赵敏，孙棣华.基于meanshift算法的图像边缘检测[J].重庆工学院学报（自然科学版），2009，23（08）.

    [7] 丁大弸，黄欢，刘辉罗山.基于Mean Shift算法的实时运动目标跟踪[J].山西电子技术，2008（05）.