基于方向直方图的Mean shift目标跟踪新算法

秦 臻 ， 曹剑中

（1.中国科学院 西安光学精密机械研究所，陕西 西安710119；2.中国科学院研究生院 北京 100039）

目标的实时跟踪在计算机视觉跟踪领域有着非常重要的应用，近年来在目标跟踪领域提出了很多好的算法，然而很多算法由于计算复杂，都未能应用到对实时性要求较高的场合。Dorin Comaniciu将Mean shift算法引入到目标跟踪领域[1-2]，极大地减少了跟踪算法的计算量。Dorin Comaniciu提出的算法是以彩色直方图作为特征来实现目标的识别与定位，而灰度直方图所包含的图像信息单一，使得Mean shift算法很难应用于灰度图像，限制了Mean shift算法的适应环境。经典的Mean shift算法要求相邻两帧间目标模板区域必须重叠，在目标较快运动的情况下容易跟丢目标；在目标出现尺度变化的复杂条件下，其跟踪结果往往出现偏差，甚至跟踪失败。笔者提出了基于空间方向直方图的Mean shift跟踪算法，使用空间统计信息作为匹配信息，结合卡尔曼滤波预测目标位置。实验结果表明，该算法在目标运动较快，光照变化和尺度缩放等情况下可以对目标准确的跟踪，具有良好的鲁棒性和效率。

1 Mean shift算法概述

Mean shift算法是一种非参数概率密度估计算法[3]，可以通过迭代，快速地收敛于概率密度函数的局部极大值。算法的跟踪过程就是不断寻找概率密度局部最大值的过程，其步骤如下。

1.1 目标模型的描述

在首帧图像中确定被跟踪的目标区域，可通过手工选择矩形框的方式来确定目标区域。目标模型可以描述为在目标区域上的所有特征值的概率值，用目标模型的特征值估计的概率密度为：

其中，K（x）为核函数的轮廓函数；b（xi）是表示像素 xi属于哪类特征值；h 表示核函数的带宽[4]；δ[b（xi）-u]是用于判断目标区域中的任意像素xi的颜色值是否等于第u个特征值；C是一个标准化的常量系数。

1.2 候选模型的描述

类似式（1），计算当前帧中，搜索窗口的特征值的概率密度为：

1.3 相似性函数

相似性函数用于描述目标模型和候选模型的相似性度量，可使用Bhattacharyya[5]系数作为相似性函数，即

其值在0～1之间。ρΛ（y）的值越大，表示两个模型越相似。

1.4 目标定位

为使ρΛ（y0）最大，应当先将当前帧的目标中心定位为前一帧中目标中心的位置y0，在y0邻域内寻找局部最优目标位置 y1。 定位时，先在 ρΛ（y0）处对函数式（3）进行泰勒展开，相似性函数可近似为：

其中：

令

可以看出，求相似性函数最大就是要求式（6）最大，通过对相似性函数求最大值，即可计算Mean shift向量y1-y0。如式（7）所示：

其中 g（x）=-k′（x），这样目标区域即可由初始位置逐步移动到真实的目标位置。 根据式（4）可知，相似性函数ρΛ（y0）在处先进行泰勒展开，而泰勒展开要求是在邻域内展开，这就限制了起始点y0和y的距离不能太大。

2 基于方向直方图的跟踪

2.1 方向直方图

给定一组灰度图像I，定义像素的梯度方向角为

式中 ∂f/∂y和 ∂f/∂x分别是该像素处沿 y和 x方向的梯度，可以通过梯度算子来获得。梯度方向角θ的取值范围为0～2π。为了获得方向编码，需要对方向角进行量化。方向角量化的间距为Δθ，于是方向编码可按式（9）计算：

如果方向编码被量化成m个，则cij的取值为{0，1，2，…，m-1}。 对于小于阈值T的像素来说，定义其方向编码为m，由于此区域很难计算出稳定的梯度方向角，因而阈值T可根据经验来选择。如果采用的量化方向为16个，方向编码的间距Δθ取π/8。用Mean shift跟踪目标模型和候选模型时，在跟踪区域用方向编码来描述目标。方向编码示意图如图1所示。

2.2 跟踪算法流程

1）预测跟踪坐标 利用前一帧图像中目标的位置信息来预测在当前帧中目标的位置信息。先验估计计算公式[6]如下：

2）获得当前帧的跟踪坐标 以1）预测得到的跟踪坐标为起始搜索位置，应用基于方向直方图的Mean shift跟踪算法，得到当前帧目标实际的跟踪坐标 Zk（xK，yK）。

3）校正跟踪坐标 根据2）得到的实际测量值Zk，利用后验估计公式，计算得到新的后验估计坐标值，返回到1），进行下一帧参数的预测。

后验估计计算公式[7]如下：

R为观测噪声协方差矩阵；Kk为卡尔曼增益；H表示状态变量xk对测量变量Zk的增益矩阵。

3 实验结果与分析

本文利用灰度图像序列来验证新算法的跟踪效果[8-9]。图2为图像跟踪区域的灰度直方图和方向统计直方图。图3是汽车图像序列的跟踪结果。

3.1 直方图的对比

方向直方图简化了目标的表述方式，减少了Mean shift匹配时的bins的个数，因而降低了跟踪过程中的匹配复杂度，有利于提高跟踪速度，并且利用了目标运动的方向特性，跟踪时对目标方向变化不敏感。

图1 运动方向编码示意图Fig.1 Coding schemes of movement direction

图2 汽车运动区域直方图Fig.2 Histogram of motor movement region

3.2 序列图像跟踪结果

图3 跟踪汽车图像序列Fig.3 Image sequence of tracking car

在图 3 中，图（a）、（b）、（c）为原算法的跟踪结果；图（d）、（e）、（f）为新算法的跟踪结果。原跟踪算法中，在汽车运动较快的情况下，跟踪过程中目标存在部分出框的问题；而新算法在目标运动速度过快和目标尺度变化的情况下仍然可以稳定的跟踪到目标。

表1 Mean shift和改进算法的对比Tab.1 Contrast between Mean shift and improved algorithm

图4 两组算法跟踪效率对比Fig.4 Tracking performance comparison of two groups algorithm

表1和图4是Mean shift算法和新算法的跟踪效率对比分析。图（a）是两组算法迭代次数对比。图（b）是两组算法跟踪耗时对比。

可以看出，由于卡尔曼滤波算法的计算量很小，卡尔曼滤波器平稳运行后，新的算法能够减少每帧内Mean shift的迭代次数，而且每帧的计算时间相对减少，表明新算法有效地提高了跟踪的效率。

4 结 论

本文提出了一种基于空间方向直方图的Mean shift跟踪新算法。该算法利用卡尔曼滤波器预测当前帧目标的可能位置，利用空间直方图来描述目标，能够在一定复杂条件下对目标进行准确、有效、实时的跟踪。实验结果表明，该算法可以较好的适应光线变化，目标尺度缩放或色彩质量很差等图像序列中的目标跟踪，改善了传统基于色彩方向直方图的局限性，提高了跟踪算法的效率。

[1]Comaniciu D， Ramesh V， Meer P.Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

[2]ComaniciuD，RameshV，MeerP.Real-timetrackingofnon-rigid objects using Mean shift[C]//Proc IEEE Coference on Computer Vision and Pattern Recognition，2000：142-149.

[3]CHENG Yi-zong.Mean shift， mode seeking， and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17（8）：790-799.

[4]Comaniciu D，Ramesh V，Meer P.The variable bandwith Mean shift and data-driven scale selection[J].Eighth IEEE International Conference on Computer Vision，2001：438-445.[5]PENG Ning-song， YANG Jie， LIU Zhi.Mean shift blob tracking with kernel histogram filtrering and hypothesis testing[J].Pattern Recognition Letters， 2005，26（5）：605-614.

[6]田纲，胡瑞敏，王中元.一种基于运动矢量分析的Mean shift目标跟踪算法[J].中国图象图形学报.2010，15（1）：85-90.TIAN Gang， HU Rui-min， WANG Zhong-yuan.A Mean shift target tracking algorithm based on motion vector analysis[J].Journal of Image and Graphics， 2010，15（1）：85-90.

[7]詹建平，黄席樾，沈志熙，等.基于均值漂移和卡尔曼滤波的目标跟踪方法[J].重庆理工大学学报：自然科学，2010，24（3）：76-80.ZHAN Jian-ping， HUANG Xi-yue， SHEN Zhi-xi， et al.Target tracking based on Mean-shift and kalman filter[J].JournalofChongqing University ofTechnology：Natural Science， 2010， 24（3）：76-80.

[8]王宝荣，杨华，王一程，等.基于卡尔曼滤波与均值漂移算法的目标跟踪[J].激光与红外，2009， 39（11）：1233-1236.WANG Bao-rong， YANG Hua， WANG Yi-cheng，et al.Targettrackingalgorithm based on Kalman filterand meanshift[J].Laser and Infrared， 2009， 39（11）：1233-1236.

[9]刘惟锦，章毓晋.基于Kalman滤波和边缘直方图的实时目标跟踪[J].清华大学学报：自然科学版，2008 ，48（7）：1104-1107.LIU Wei-jin，ZHANG Shu-jin.Edge-color-histogram and Kalman filter-based real-time object tracking[J].Journal of Tsinghua University：Science and Technology， 2008 ，48（7）：1104-1107.