融合Kalman滤波的自适应带宽Mean Shift算法

傅荟璇，王宇超，孙枫

(哈尔滨工程大学 自动化学院，黑龙江 哈尔滨，150001)

摘要：针对Mean Shift算法在复杂背景中存在颜色干扰问题和核函数带宽固定的缺陷，提出一种融合Kalman滤波的自适应带宽Mean Shift跟踪算法。将Mean Shift算法得到的目标位置作为Kalman滤波的测量值，利用Kalman滤波预测出下一帧目标的位置，以预测值作为Mean Shift算法迭代运算的初始值，并以仿射变换来描述目标尺寸变化，利用连续两帧中匹配窗口的最大相关系数确定最优匹配窗口搜索目标。跟踪试验结果表明：算法在背景与目标颜色相近和目标尺寸变化等复杂情况下都能对目标进行准确跟踪，具有较强的抗干扰能力。

关键词：目标跟踪；Mean Shift算法；Kalman滤波

中图分类号：TP391.4          文献标志码：A         文章编号：1672-7207(2011)S1-0784-05

Tracking algorithm based on Kalman and Mean Shift with adaptive bandwidth

FU Hui-xuan, WANG Yu-chao, SUN Feng

(College of Automation, Harbin Engineering University, Harbin 150001, China)

Abstract: According to the defects that Mean Shift algorithm exists color interference in a complex background and kernel function bandwidth of Mean Shift was not changeable, integrated Kalman filter to adaptive bandwidth Mean Shift Tracking algorithm was proposed. Taking object position obtained from Mean Shift as Kalman filter measure value, Kalman filter is used to get the predicted starting position of Mean Shift in every frame. The object size change by the affine transformation is described, and the window is matched using continuous two frames in the maximum correlation coefficient to determine the optimal matching window search object. The tracking experiment shows that the algorithm in the complex situation, such as background and the object having similar color and the object size changing, can carry on the accurate tracking to the object, showing a good anti-interference ability.

Key words: object tracking; Mean Shift algorithm; Kalman filter

目标跟踪是计算机视觉的一个重要分支。在视频监控、物体识别等应用领域中，往往需要在各种复杂的环境下对运动物体进行有效跟踪。跟踪系统不但要求能够实时适应目标因各种运动导致的外观变化，而且要求对场景中存在的复杂背景、目标尺寸变化等因素的影响不敏感。Mean Shift是一种基于密度梯度的无参数估计方法，于1975年由Fukunaga等^[1]提出，1995年Cheng^[2] 将它引入到计算机视觉领域，但直到近几年才引起国内外学者的广泛关注。近年来，Mean Shift算法^[3-4]以其无需参数、快速模式匹配的优点被广泛应用到目标跟踪领域^[5-8]。Mean Shift跟踪算法在简单背景环境中能够取得较好的跟踪效果，但是在复杂背景中，由于该算法对运动物体不做任何预测，不能解决大面积背景颜色干扰问题，容易导致跟踪失败，所以需引入估计器预测目标运动参数。卡尔曼滤波方法是美国著名学者Kalman和Bucy于1960年提出的一种最优递推滤波方法，具有计算量小、可实时计算的特点。因此，将Mean Shift算法与Kalman滤波结合来预测目标位置，增强跟踪算法的抗干扰能力。Mean Shift迭代依赖于带宽，却没有能力自适应调整带宽，即跟踪窗口的大小。通常核窗宽由初始跟踪窗口的尺寸决定。当目标尺寸不断缩小时，跟踪窗口内存在大量的背景，背景噪声会影响目标的跟踪点、当目标尺寸逐渐增大以至超出核窗宽范围的时候，固定不变的核窗宽常常会导致目标的丢失。

本文作者在分析传统Mean Shift算法局限性的基础上，结合Kalman滤波，提出一种融合Kalman滤波的自适应带宽Mean Shift算法。利用Mean Shift算法计算跟踪窗口的位置和大小，并把窗口的中心位置作为Kalman滤波的测量值，校正目标的中心位置；然后，以比例参数计算本帧目标的尺寸， 通过计算相关系数确定最优匹配窗口，计算出新的核函数带宽。Kalman滤波器的预测结果用于设置下一帧图像搜索窗口的中心位置。试验结果表明，该算法可以有效解决背景颜色干扰及目标准确定位问题，具有良好的鲁棒性。

1  Mean Shift跟踪算法

Mean Shift是一种非参数的密度估计算法，在起始帧内为被跟踪目标建立直方图分布，用同样的方法计算第N帧对应的直方图分布，以2个分布的相似性最大为原则。

1.1  目标区域距离加权建模

假设模板中各个像素点为，模板中心是。定义函数，将处像素值与2维实数坐标向量相对应。模板的半径是；

表示模板上各个像素点到模中心的归一化距

离。k(x)为核函数。δ[x]是离散冲击函数，当 x=0时，其值为1；否则，其值为0。由此可以得到如下计算模板直方图的公式(以直方图中像素值为u的项为例，其中为的归一化系数，使概率之和为1)：

    (1)

式中：

，

。

1.2  候选区域距离加权建模

同理，假设匹配对象中各个像素点为{x_i}_{i-1, …, m}，对象的中心是y，对象的半径是h，则计算对象直方图的公式为(以直方图中像素值为u的项为例，其中C为p_u(y)的归一化系数，使概率之和为1)：

      (2)

式中：

，

。

1.3  目标与候选区域的相似度

相似度采用Bhattacharyya系数表征，定义为：

      (3)

可见，与分布越接近，ρ(y)越大。由于归一化，当与分布完全相同时，ρ(y)取得最大值1；否则，ρ(y)将介于0与1之间。

1.4  目标位置搜索

为使ρ(y)达到最大，在当前帧中，以目标在上一帧中的位置y₀ (目标区域的中心位置)作为目标在当前帧中的初始位置，然后在y₀邻域内寻找最优目标位置y₁，使得ρ(y₁)最大。对式(3)在p(y₀)处进行泰勒展开，略去高阶项后相似性函数可近似为：

(4)

式中：。

由于式(4)中的第1项与y无关，为了使迭代得出的中心接近实际的目标中心，式(4)中的第2项必须要取最大值。通过Mean Shift迭代可以使该项最大，即找到了最佳中心。中心迭代公式如下：

         (5)

由于目标模型是建立在颜色直方图的基础上，而直方图是一种比较弱的对目标特征的描述，当背景和目标的颜色分布较相似时或在目标周围出现与目标颜色相近的其他物体时，算法易丢失目标。核窗宽由初始跟踪窗口的尺寸决定，当目标存在明显尺度变化时，固定不变的核窗宽常会导致目标的丢失且目标定位不准确。

2  融合Kalman滤波的自适应带宽Mean Shift算法

2.1  融入Kalman的Mean Shift跟踪算法

将Kalman滤波预测技术融入到Mean Shift算法中，提高跟踪方法的抗干扰能力。在跟踪过程中，由于相邻2帧图像时间间隔较短，目标运动状态变化较小，可近似认为目标在2帧图像的时间间隔内做匀速运动，所以，采用等速度运动模型，用Kalman滤波器预测目标中心位置。

设一个离散时间线性系统的状态方程和观测模型分别为：

          (6)

             (7)

式中：X_k为k时刻的状态矢量；A为从k-1时刻到k时刻的状态转移矩阵；Z_k为k时刻的测量值；H是测量矩阵；W_k与V_k分别表示过程和测量的噪声。

定义状态向量，观测状态向量，预测状态向量。其中：分别表示目标中心在x轴和y轴上的位置和速度；分别表示Kalman滤波器预测的目标中心位置和速度。根据式(6)和(7)得状态转移矩阵A和观测矩阵H：

，    (8)

式中：T是时刻t_k与时刻t_k-1的时间间隔。

Kalman滤波分为预测和校正2个阶段：首先，初始化过程噪声方差矩阵Q、测量噪声方差矩阵R、初始状态向量X₀和初始误差方差矩阵P₀，然后用预测状态向量X'_k中的x'_k，y'_k分量设定Mean Shift算法搜索窗口的中心位置，并把Mean Shift算法输出的质心位置作为测量值Z_k来校正预测状态向量X'_k，得到Kalman滤波器的预测结果X'_k+1，用于设置下一帧图像搜索窗口的中心位置。

2.2  自适应带宽Mean Shift算法

在一帧图像中，用N个像素点表示目标(x₁，x₂，…，x_n)，在下一帧中对应像素点坐标为(x′₁，x′₂，…，x′_n)，则2帧中目标区域像素的坐标满足仿射变换关系^[9]：

,

1＜i＜n               (9)

式中：k，θ和b分别表示目标的比例缩放、旋转和平移参数。

连续2帧中目标的比例变化一般并不大，相对前一帧，设本帧中目标尺寸可能的缩放范围k为(-1.5,1.5)，令，k₀=0.05，i=0，1，…，10。计算关于每个k_i的匹配窗口，计算这些匹配窗口和初始帧中目标窗口的相关系数，相关系数最大的为本帧最优的k′。

2.3  算法流程

具体算法描述如下：

(1) 初始选定跟踪目标，Kalman参数初始化，根据式(1)计算目标的量化直方图q_u；

(2) 读取下一帧图像，预测当前帧方差P_k/k-1，目标状态X_k/k-1，其中预测位置为y₀；

(3) 在预测目标位置y₀处，利用Mean Shift算法得到的目标窗口的中心位置作为Kalman滤波的测量值Z_k；

(4) 利用Kalman更新目标状态X_k/k及方差阵P_k/k，X_k/k即为当前帧目标窗口中心位置；

(5) 设本帧中目标尺寸可能的缩放范围k为(-1.5，1.5)，令，k=0.05，i=0，1，…，10。计算关于每个k_i的匹配窗口，计算这些匹配窗口和初始帧中目标窗口的相关系数，相关系数最大的为本帧最优的k′；

(6) 根据k′计算新的目标匹配窗口核函数带宽，返回步骤(2)开始下一帧的计算。

算法的结构如图1所示。

3  试验结果

试验中，采集图像分辨率为768×576的彩色图像。试验场景图像共550帧，对坦克跟踪，分别选取53帧、76帧、115帧、121帧、334帧、408帧、436帧、442帧的跟踪效果。图2所示为采用Mean Shift跟踪算法所得到的跟踪结果。

由图2可看出，背景中有与目标颜色相近的干扰时，算法收敛到与目标物体颜色相近的背景上，无法正确跟踪目标。当目标尺寸发生变化时，窗口无法随着目标尺寸而变化，不能准确定位目标。

图3所示为采用融合Kalman滤波的自适应带宽Mean Shift算法对同一视频序列所得到的跟踪结果。

由图3可看出，当坦克运动到桌子附近时，由于坦克与背景中的桌子颜色概率分布相近，所以Mean Shift容易收敛到桌子上，而加入Kalman 滤波器的Mean Shift算法可预测到下一时刻的目标位置，可以有效避免背景颜色的干扰问题，成功实现了目标跟踪。当第53帧、第76帧、第115帧、第121帧目标发生尺寸变小，第334帧、第408帧、第436帧、第442帧中目标尺寸变大时，跟踪窗口都能随着目标尺寸的变化而准确定位目标。

图1  算法结构图

Fig.1  Algorithm structure

图2  Mean Shift算法的跟踪结果

Fig.2  Tracking results by Mean Shift algorithm

图3  融合Kalman滤波的自适应带宽Mean Shift算法的跟踪结果

Fig.3  Tracking results by Kalman and Mean Shift with adaptive bandwidth algorithm

4  结论

针对Mean Shift算法在复杂背景中容易丢失目标的问题和核函数带宽固定的缺陷，将Kalman滤波预测融入到Mean Shift跟踪算法中。首先，确定初始化搜索窗口的位置和大小，并确定图像序列的状态模型和测量模型；然后，根据Kalman滤波预测出下一帧目标的位置，以预测值作为Mean Shift算法中迭代运算的初始值，提高了跟踪方法的抗干扰能力和速度。并以仿射变换来描述目标尺寸的变化，利用连续两帧中匹配窗口的最大相关系数确定最优匹配窗口搜索目标。跟踪试验表明：算法在背景与目标颜色相近和尺度缩放等复杂情况下都能对目标进行准确跟踪，具有较强的抗干扰能力。

参考文献：

[1] Fukunaga K, Hostetler L. The estimation of the gradient of a density function with application in pattern recognition[J]. IEEE Trans Information Theory, 1975, 21(1): 32-40.

[2] Cheng Y. Mean Shift, mode seeking, and clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(8): 790-799.

[3] Comaniciu D, Ramesh C. Mean Shift and optima1 prediction for efficient object tracking[C]//International Conference on Image Processing. Vancouver: ICIP, 2000, 3: 70-73.

[4] Comaniciu D, Ramesh V, Meer P. Real-time tracking of non-rigid objects using Mean Shift[C]//IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island: CVPR, 2000: 142-149.

[5] Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-575.

[6] Comaniciu D, Meer P. Mean Shift: A robust application toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[7] Yilmaz A, Shafique K, Shah M. Target tracking in airborne forward looking infrared imagery[J]. Image and Vision Computing, 2003, 21(7): 623-635.

[8] Collins R T. Mean Shift blob tracking through scale space[C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Madison: CVPR, 2003: 234-240.

[9] 朱胜利, 朱善安. 核函数带宽自适应的Mean shift目标跟踪算法[J]. 光电工程, 2006, 33(8): 11-16.
ZHU Sheng-li, ZHU Shan-an. Algorithm of target tracking based on Mean Shift with adaptive bandwidth of kernel function[J]. Opto-Electronic Engineering, 2006, 33(8): 11-16.

(编辑 杨华)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(60704004)；中央高校基本科研专项项目(HEUCFR1009)

通信作者：傅荟璇(1981-)，女，黑龙江牡丹江人，博士，讲师，从事机器视觉检测技术、模式识别的研究；电话：0451-82588958；E-mail：fuhuixuan@hrbeu.edu.cn