一种基于协方差估计的均值偏移对象跟踪算法

肖进胜，张亚琪，单姗姗，彭红

(武汉大学 电子信息学院，湖北 武汉，430079)

摘要：针对现有运动目标跟踪算法对目标大小、形状变化的适应能力较差，且不能对目标的旋转进行跟踪的问题，提出一种改进的目标跟踪算法。该算法是均值偏移算法的进一步扩展和延伸，在估计目标位置的同时用协方差矩阵来描述目标形状，结合色彩直方图，处理对象的角度和形状、大小发生变化时的跟踪问题。实验结果表明：改进的算法在不同环境下跟踪目标的鲁棒性很好，极大地提高了跟踪精度，具有很强的实用性。

关键词：均值偏移；协方差矩阵；对象跟踪；颜色直方图

中图分类号：TP391                 文献标志码：A         文章编号：1672-7207(2013)03-1049-05

A mean shift object tracking algorithm based on covariance estimation

XIAO Jinsheng, ZHANG Yaqi, SHAN Shanshan, PENG Hong

(School of Electronic Information, Wuhan University, Wuhan 430079, China)

Abstract: Considering the problems that the current tracking algorithms always fail in the adaption of object’s changing in size and shape and cannot follow when the object rotating, an improved object tracking algorithm was proposed which was an extension of the mean shift procedure. The new algorithm utilizes a covariance matrix to describe the object’s shape while estimating its position, combines with the color histogram, and processes the tracking problem while the target object keeps changing in angle, size or shape. The experiment shows that algorithm can robustly work in different environment and greatly raise the tracking accuracy.

Key words: mean shift; covariance matrix; object tracking; color histogram

运动目标的检测与跟踪在许多领域有着广泛的应用，是计算机视觉研究领域的焦点之一。均值偏移算法由于其具有简单和鲁棒的特点，近几年受到广泛关注，并以其无需参数、快速模式匹配的优点被广泛应用到目标跟踪领域，该算法特别在非刚性物体跟踪中有很好的实时性。均值偏移算法可以很好地解决跟踪的可视化问题^[1-2]。利用给定的数据样本可以得到近似概率密度函数的核^[3]，而均值偏移算法即为一个搜索经验概率密度函数最大值的过程^[4]。本文在均值偏移算法基础上提出一种基于协方差估计的跟踪算法^[5]。跟踪的非刚性物体用一个椭圆形的形状标定，由目标模型的颜色直方图和来自图像序列新模型的候选椭圆区域的颜色直方图定义一个相似度函数。在均值偏移过程中寻找区域的新对象，该图像与目标模型相似度最大^[6-7]。但当跟踪对象的形状、大小发生变化时，如何调整椭圆形状来接近该对象的问题仍然没有解决^[8]。现有的解决方法是：在每个跟踪步骤后，通过将椭圆形放大10%和缩小10%，来选择最佳匹配^[6]；或在椭圆形的尺度范围内进行广泛搜索，直到找到最相近的一个为止^[9]，等等。显然，这些方法迭代次数多，并且还要进行多次搜索比较，计算复杂度较大。本文对均值偏移算法进行扩展。新算法不仅只估计目标的位置，还同时估计和描述目标的形状变化。由计算协方差矩阵来得到运动目标的旋转和尺度变化。提出一种自由度为5的基于颜色直方图的目标跟踪方法，不仅估计跟踪对象的位置，而且估计近似该对象的椭圆的形状。新算法可有效地解决椭圆适应性相关的问题。

1  均值偏移算法原理

先假设样本数据集合，概率密度函数为高斯分布，如下所示：

    (1)

平均向量和协方差矩阵V的最大似然估计即是使联合概率达到最大时的值。对于高斯分布p，不失一般性，其最大目标函数可以写成如下形式^[10]：

          (2)

当V固定时，式(2)可视为用高斯内核模拟的经验密度函数，矩阵V可以看作是基于内核密度估计中的带宽参数。均值偏移算法可用来获取经验密度函数模型参数的鲁棒估计^[11-13]。式(2)可用加权系数方法的表示如下：

          (3)

可以用EM迭代法^[14]求出使式(3)达到最大值的参数和V。假定当前估计参数值为和，新的EM算法步骤1和2循环描述如下，直到目标函数收敛为止。

步骤1：将和视为常数，求使以e为底的对数似然函数达到最大。由Jensen不等式^[10]，有：

     (4)

其中： ，。

将不等式右端分别对求偏导，并令其为0得：

；i=1, …, N   (5)

注意到，可得：

  (6)

步骤2：把视为常数，选择使目标函数最大化。由式(4)只需计算的极大值。注意到高斯分布的定义，将其对求偏导，并令其为0得：

            (7)

考虑式(6)，可得迭代式：

  (8)

由式(8)可知：对位置进行估计得到的更新等式与高斯内核均值偏移的更新式相等。

2  改进的均值偏移算法及分析

2.1  基于颜色分布直方图的跟踪

初始时，目标由手动或用其他算法标记为椭圆O，用x_i表示椭圆O中所有像素点的位置，用表示初始时椭圆目标中心在图像中的位置，用二阶矩近似确定目标的形状：

          (9)

颜色分布直方图用于目标外观的建模。设颜色分布直方图有M个区间，其函数: R²→1, …, M确定当前点x_i处的颜色值。第M个直方图的值可以由下式计算得到：

      (10)

其中：为克罗内克函数。用高斯核函数N增大目标中间部分点的权重，使目标边沿点的权重降低，减少对椭圆边界像素点的依赖。并且只取核周围有限领域中距离核心不超过的个像素点。

在图片中定义1个椭圆区域，用表示它的位置，协方差矩阵V表示它的形状。用颜色直方图来描述该区域的外形，并且第m个向量计算公式如下：

      (11)

将该区域与物体的相似度定义为它们直方图的相似度。如同文献[1]中提到，用巴氏系数来度量两者直方图的相似度：

        (12)

在当前估计量附近的一级泰勒近似值定义如下：

     (13)

其中：c₁和c₂为常量因子。

       (14)

因为式(13)中的末项和式(2)中的一样，所以，可用新的EM 算法寻找相似度函数的局部最优解。

2.2  基于协方差矩阵更新的跟踪算法

一般的均值偏移算法，没有考虑协方差矩阵V的更新，而协方差矩阵V代表着尺度和方位的变化^[15].如果是样本数据初始的分布，那么，式(2)的期望值为：

        (15)

同样，考虑高斯分布定义，求协方差矩阵V使达到最大。令其对V的偏导数为0可得：

       (16)

所以，V的迭代更新方程如下：

       (17)

由上面的分析可知：假设输入物体模型o，它的初始(k=0)位置，形状，计算初始目标区域颜色直方图。整个算法步骤如下：

(1) 计算当前帧中区域的颜色直方图的值；

(2) 计算权重和q_i；

(3) 计算新的预测位置；

(4) 计算新的方差；

(5) 当用新的椭圆区域没有变化时，停止迭代；否则，设置k←k+1且转至第1步，重新计算。

该过程每1帧循环1次。在最简单的情况下，直接用前一帧中椭圆区域的位置和形状的值来作为新的帧的椭圆区域的初始值。

3  实验结果及分析

为测试本文提出算法的有效性，选取具有代表性的标准测试视频进行物体跟踪实验，并与经典均值偏移算法得出的运行速度与跟踪效果进行对比。在实验过程中，使用的软件环境为MATLAB 7.12.0.635，操作系统为Windows XP，硬件平台为：Inter(R) Core(TM)i5-2300 CPU@2.80 GHz，2.79 GHz，4.00 GB内存。

针对标准序列进行跟踪实验，本文算法与经典均值偏移算法所得运行效率对比结果见表1。测试采用多次运行取平均时间的方法。

由表1可知：即使加入协方差矩阵的更新计算，本文提出的算法仍然比传统的均值偏移算法具有更高的时间运行效率，处理速度平均是传统算法的2倍。

图1所示为本文算法与经典均值偏移算法的跟踪效果对比。跟踪物体的位置和形状用虚的椭圆线框表示。

图1中“Intelligentroom_raw”序列是一段由监控摄像机所拍摄的较长、质量低的视频。图1给出视频中具有典型性的2帧，目标向摄像机运动，目标大小变化较大，方向也发生变化。图2中“PetsD2TeC2”标准数据序列来自www.visualsurveillance.org。由于车辆也改变了方向和大小，可以看出：标准的均值偏移跟踪法并不适用于目标大小的改变，已经跟丢；而本文提出的算法可以适应目标尺寸和方向的改变。

表1  算法跟踪效率对比

Table 1  Comparison of processing speeds of two algorithms

图1  序列Intelligentroom_raw的跟踪效果对比

Fig.1  Comparison of tracking effect on Intelligentroom_raw sequence

图2  序列PetsD2TeC2的跟踪效果对比(第300帧和380帧)

Fig.2  Comparison of tracking effect on PetsD2TeC2 sequence

4  结论

(1) 提出一种新的基于颜色直方图的目标跟踪算法。这个算法最大的优点是适用于目标的形状和大小同时改变的情况，通过建立目标颜色直方图的核密度函数模型，运用新的EM算法，求出目标的位置和描述目标形状的协方差矩阵V。

(2) 此算法能够满足实时工作的需要，只是计算量比目前在目标形状和尺寸变化后有跟踪困难的算法时要大。新的基于颜色直方图的目标跟踪过程是基于均值偏移算法的拓展和更新，而均值偏移算法对其他机器视觉问题也很有适用性。

参考文献：

[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] Jarabo-Amores P, Rosa-Zurera M, de la Mata-Moya D, et al. Spatial-range mean-shift filtering and segmentation applied to SAR images[J]. IEEE Transactions on Instrumentation and Measurement, 2011, 60(2): 584-597.

[3] NG Heungsun, WU Taipang, TANG Chikeung. Surface- from-gradients without discrete integrability enforcement: A Gaussian kernel approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(11): 2085-2099.

[4] 王永忠, 梁彦, 赵春晖, 等．基于多特征自适应融合的核跟踪方法[J]. 自动化学报, 2008, 34(4): 393-399.

WANG Yongzhong, LIANG Yan, ZHAO Chunhui, et al. Kernel-based tracking based on adaptive fusion of multiple cues[J]. Acta Automatica Sinica, 2008, 34(4): 393-399.

[5] 胡铟, 杨静宇. 基于分块颜色直方图的MeanShift 跟踪算法[J]. 系统仿真学报, 2009, 21(10): 2936-2939.

HU Yin, YANG Jingyu. Tracking algorithm based on block color histogram and Mean Shift[J]. Journal of System Simulation, 2009, 21(10): 2936-2939.

[6] Bradski G R. Real time face and object tracking as a component of perceptual user interface[C]//Proc IEEE Workshop on Applications of Computer Vision. New Jersey, USA: IEEE Press, 1998: 214-219.

[7] Comaniciu D, Ramesh V, Meer P. Real-time tracking of non-rigid objects using mean shift[C]//Proc IEEE Conf on Computer Vision and Pattern Recognition. South Carolina, USA: IEEE Press, 2000, 2: 142-149.

[8] Ning J, Zhang L, Zhang D, et al. Robust object tracking using joint color-texture histogram[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2009, 23(7): 1245-1263.

[9] Collins R. Mean-shift blob tracking through scale space[C]//Proc IEEE Conf on Computer Vision and Pattern Recognition. Wisconsin, USA: IEEE Press, 2003: 234-240.

[10] Zivkovic Z, Krose B. An EM-like algorithm for color-histogram- based object tracking[C]//IEEE Conference on Computer Vision and Pattern Recognition. Washington D C, USA: IEEE Press, 2004: 798-803.

[11] 李冠彬, 吴贺丰. 基于颜色纹理直方图的带权分块均值漂移目标跟踪算法[J]. 计算机辅助设计与图形学学报, 2011, 23(12): 2059-2066.

LI Guanbin, WU Hefeng. Weighted fragments-based Meanshift tracking using color-texture histogram[J]. Journal of Computer- Aided Design & Computer Graphics, 2011, 23(12): 2059-2066.

[12] SHEN Chunhua, Kim J, WANG Hanzi. Generalized kernel- based visual tracking[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(1): 119-130.

[13] Leichter I, Lindenbaum M, Rivlin E. Mean Shift tracking with multiple reference color histograms[J]. Computer Vision and Image Understanding, 2010, 114(3): 400-408.

[14] 朱峰, 宋余庆, 陈健美. 基于椭球等高分布混合模型的聚类方法[J]. 江苏大学学报: 自然科学版, 2011, 32(6): 701-705.

ZHU Feng, SONG Yuqing, CHEN Jianmei. Clustering method based on elliptical contoured mixture model[J]. Journal of Jiangsu University: Natural Science Edition, 2011, 32(6): 701-705.

[15] Takeda H, Farsiu S, Milanfar P. Deblurring using regularized locally adaptive kernel regression[J]. IEEE Transactions on Image Processing, 2008, 17(4): 550-563.

(邓履翔)

收稿日期：2012-02-13；修回日期：2012-05-03

基金项目：国家自然科学基金资助项目(91120002，41001306)

通信作者：肖进胜(1975-)，男，湖北武汉人，博士，副教授，从事视音频信号处理和通信研究；电话：027-68753538；E-mail: js_xiao@tom.com