一种尺度和旋转自适应的目标跟踪算法

赵钦君¹，张勇¹，赵东标²

(1. 济南大学 自动化与电气工程学院，山东 济南，250022；

2. 南京航空航天大学 机电学院，江苏 南京，210016)

摘 要：

踪中的尺度和旋转问题，提出一种基于尺度不变特征变换(SIFT)和均值漂移的目标跟踪算法。该算法首先检测模板区域和目标区域在尺度空间中的极值点，然后通过拟合三维二次函数精确定位特征点的位置和尺度，接着对目标区域和模板区域的特征点进行匹配，并根据相邻帧之间尺度和角度的连续性，去除误匹配，最后利用正确匹配的特征点中的尺度和角度信息，计算被跟踪目标的尺度和旋转角度。研究结果表明：当被跟踪目标的角度和尺度发生变化时，该算法皆具有较好的跟踪效果。

关键词：

目标跟踪；尺度不变特征变换(SIFT)；均值漂移算法；尺度空间；

中图分类号：TP391          文献标志码：A         文章编号：1672-7207(2013)06-2354-07

A scale and rotation adaptive algorithm for object tracking

ZHAO Qinjun¹, ZHANG Yong¹, ZHAO Dongbiao²

(1. School of Electrical Engineering, University of Jinan, Jinan 250022, China;

2. College of Mechanical and Electrical Engineering,Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Abstract: In order to solve the problem of scale and rotation in image object tracking, a novel object tracking algorithm based on Scale Invariant Feature Transform (SIFT) and Mean Shift was proposed. Firstly, scale-space extrema in the model area and object area are detected and accurate positions and scales of the feature points were located by fitting 3D quadratic functions. Secondly, feature points in model area and object area were matched and the mismatched points were eliminated according to continuity of scale and angle between adjacent frames. Lastly, the scale and rotation angle of the object being tracked were calculated by using the scale and angle information which was provided by the feature points correctly matched. Experimental results show that the proposed algorithm has good tracking effect no matter whether the scale or the angle of the object changes.

Key words: object tracking; Scale Invariant Feature Transform (SIFT); Mean Shift algorithm; scale space

视频图像序列中的运动目标跟踪^[1-2]是计算机视觉领域的研究热点之一。它利用计算机视觉技术和视频分析方法，对视频输入装置得到的图像序列进行自动分析，对其中的运动目标进行检测、提取、识别和跟踪，获取目标的状态参数，以实现对运动目标的行为理解，完成更高一级的任务。它在视频监控、智能交通、人机交互、军事领域以及机器人视觉导航等领域都有着广阔的应用空间。因此，研究视频目标跟踪相关技术具有重要的学术意义和实用价值。但目前目标跟踪在实际应用中仍面临很多困难，例如，跟踪过程中由于镜头变焦，或者目标沿着镜头轴线方向的运动，图像中的目标大小都会发生明显变化；由于目标自身的旋转或者相机绕镜头轴线的旋转运动，图像中目标的角度都会发生明显变化。鲁棒的跟踪算法需要能正确跟踪目标的这些尺度和旋转变化。Mean Shift算法^[3-6]在目标跟踪领域中获得了成功应用，它具有计算量小、实时性好的优点，但该算法不能跟踪目标的旋转变化。对于目标的尺度变化，Comaniciu等^{[3, 7]}提出了±10%的增量分别对核窗口宽度进行修正的方法。该方法首先在当前帧中用3个不同大小的核进行3次独立的Mean Shift跟踪计算，然后选择较大的Bhattacharyya系数所对应的窗口宽度作为当前目标的核窗口宽度。当目标逐渐缩小时，该方法可以得到较好的效果，但是当目标逐渐增大时，核窗口宽度很难扩大，反而逐渐变小。这是因为基于Bhattacharyya系数的相似性度量经常会在较小的跟踪窗口中达到局部最大。Liu等^[8]虽然可以较好地适应目标尺度的变化，但是不能根据目标的角度变化对跟踪窗口做出适当的调整。王长军等^[9-10]以目标区域的梯度方向分布(直方图)为特征，有效解决了目标跟踪中的旋转问题，但不适用于目标尺度发生变化的情况。SIFT算法^[11]是Lowe在总结和完善了现有的基于不变量技术的特征检测方法的基础上，于2004年正式提出的图像局部特征描述算法。该算法是一种基于尺度空间的、对图像缩放、旋转甚至仿射变换均具有不变性的图像局部特征描述算法。Mikolajczyk等^[12]通过对包括SIFT算子在内的10种局部描述算子所做的不变性对比实验，阐述了SIFT及其扩展算法在同类描述算子中具有最强的健壮性。牛长锋等^[13]提出了一种基于SIFT特征和粒子滤波的目标跟踪方法，较好地解决了目标跟踪中的尺度和遮挡问题，Zhou等^[14]将SIFT算法和Mean Shift算法结合起来跟踪目标，但这2种方法也都没有给出目标运动过程中的角度信息。为了同时解决目标跟踪中的尺度问题和旋转问题，受图像匹配中常用的SIFT算法的启发，本文作者提出了一种新的基于尺度不变特征变换和均值漂移的目标跟踪算法。该算法利用改进的SIFT算法提取的特征点中的尺度和角度信息，计算被跟踪目标的尺度和旋转角度，有效解决了目标跟踪中的尺度和旋转问题，具有较好的鲁棒性。

1  Mean Shift跟踪算法及分析

1.1  目标模型的描述

Mean Shift算法首先要对目标进行初始化，在包含目标的起始帧定义一个包含所有目标特征的最小矩形区域，即被跟踪目标的目标区域。设目标区域的中心坐标为x₀，核函数的轮廓函数为k(x)，其带宽为h，那么，对目标区域内的所有像素点，i=1，2，…，n，可以计算特征空间中每个特征值的概率。对应每一个特征u=1，2，…，m的目标概率模型可以表示为：

其中：C为标准化常量系数；函数b和δ的作用是判断x_i处的颜色值是否属于特征值u。

1.2  候选模型的描述

候选目标区域是指在第二帧及以后的每帧中可能包含目标的区域。设候选目标区域内的所有像素点为{x_i}，i=1，2，…，n_h，候选目标区域的中心为y，核函数的轮廓函数为k(x)，其带宽为h，则对应每一个特征u=1，2，…，m的候选目标概率模型可以表示为：

1.3  相似性度量函数

设目标模型的特征的概率密度分布为q，当前帧中以y为中心的候选目标模型的概率密度分布为p(y)，相似性度量函数用来描述目标模型和候选模型之间的相似程度，本文选用Bhattacharyya系数作为相似性度量函数，其定义为：

1.4  目标定位

为使式中最大，将候选目标区域的中心先定位为前一帧中目标的中心位置y₀，从这一点开始寻找与目标模型最相似的目标区域。假设在当前帧中目标的真实位置为y，先要计算在当前帧的y₀处候选目标的特征概率，u=1，2，…，m。在处对式进行泰勒展开，可得：

式中第1项与目标的真实位置为y无关，因此，这里只分析第2项，令

式就是在有权值w_i时的核密度估计，通过迭代计算式的均值漂移向量，可得目标中心从起始点y₀向真实位置点y移动的向量。均值漂移算法的中心点在连续迭代中的位置可表示为：

其中：g(x)=-k′(x)。按照式反复迭代，最后即可得到目标在当前帧中的最优位置y。

1.5  算法分析

Mean Shift算法是一种高效的模式匹配算法，其应用于目标跟踪有几个优势：首先，算法计算量不大，由于Mean Shift本质上是最陡下降法，其寻优过程收敛速度快，在目标区域已知情况下完全可以做到实时跟踪，因此已成功应用于对跟踪实时性要求较高的场合；其次，该算法是一种以目标区域像素值的概率分布为特征的跟踪算法，由于采用了统计特征，因此对跟踪过程中的边缘遮挡、目标变形和背景运动不敏感，具有较好的鲁棒性；另外，作为一种无参数密度估计算法，很容易作为一个模块和别的算法集成。因而该方法受到很多研究者的喜爱，已经成功应用于目标跟踪领域中。但Mean Shift算法也有不足之处，主要有：首先，Mean Shift跟踪算法中核函数窗口宽度起着非常重要的作用，因为它不但决定了参与Mean Shift迭代的样本数量，而且也反映了跟踪窗口的大小。一般情况下核函数的窗口宽度由初始跟踪窗口的尺寸决定，并且在整个跟踪过程中不再发生改变。然而，当目标存在明显尺度变化时，尤其是当目标尺寸逐渐增大以至超过核函数的窗口宽度范围时，固定不变的核函数窗口宽度常常会导致目标跟踪失败。其次，由于采用像素值分布为特征，丢失了目标的几何信息，因此该算法只能跟踪目标的平移，无法跟踪目标的旋转。

2  尺度和旋转自适应的跟踪算法

2.1  尺度问题的解决

一幅二维图像，在不同尺度下的尺度空间表示可由图像与高斯核卷积得到：

式中：(x，y)为空间坐标；σ为尺度坐标。G(x，y，σ)为尺度可变高斯函数：

为了有效地在尺度空间检测到稳定的特征点，本文作者在高斯差分尺度空间(DOG scale-space)中对图像进行卷积操作。DOG算子计算简单，是尺度归一化的LOG算子的近似。利用不同尺度的高斯差分核与图像卷积生成：

通过式(8)和式(9)的计算，可以建立图像高斯金字塔和差分高斯金字塔。图像金字塔共分为O组，每组又包含S层，式(9)^[11]中k=2_1/S，σ₀=1.6k，S=3。

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图1所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，如果该像素在这26个邻域像素中皆为极值，则作为候选的极值点。

图1  DOG尺度空间极值点检测

Fig. 1  Extreme point detection in DOG scale space

接下来通过拟和三维二次函数以精确确定特征点的位置和尺度，同时去除低对比度的特征点和不稳定的边缘响应点(因为DOG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。

利用DOG函数的二阶Taylor展开式D(X)插值得到特征点位置和尺度坐标的精确值(亚像素精度)：

式中：向量，表示采样点和特征点之间的位置、尺度偏移。令式的一阶导数为0，可得特征点精确位置的偏移向量为：

将加到原粗特征点的坐标X，即得到特征点的亚像素精确插值估计。将式代入式可得：

当|D(X)|小于某阈值时，这个特征点可以舍去，通常，这种特征点对噪声敏感故而不稳定。

总之，本文作者先在尺度空间中粗略定位出特征点所在的位置和尺度，再通过对三维矢量X=( x，y，σ)进行插值运算精确定位出特征点所在的尺度。这样，所检测出的每个特征点都有一个较精确的尺度，因此，即可利用正确匹配的特征点的尺度信息计算出目标的尺度变化情况。

设匹配成功的特征点个数为n，其中对应模板区域的特征点为，i=1，2，…，n，其所在的尺度为，i=1，2，…，n；对应当前帧中目标区域的特征点为，i=1，2，…，n，其所在的尺度为，i=1，2，…，n。另设模板目标的尺度为s₀，则当前帧中目标的尺度s₂可表示为：

对匹配成功的特征点，其中可能存在误匹配，而误匹配特征点尺度变化的比例与其他正确匹配的特征点相比，往往相差会比较大，其对计算当前帧中目标的尺度影响也会比较大，因此，需要去除少数发生误匹配的特征点带来的影响。由于当前帧中目标的尺度与上一帧中目标的尺度相差不会很大，因此可根据这一点来去除误匹配，设上一帧图像中目标的尺度为s₁，并设s′=s₁/s₀，则当

时，则认为该匹配点为误匹配。其中：s_T为尺度比例的阈值，其取值与相邻两帧图像间目标尺度变化的程度有关。s_T取值过大，则达不到去除误匹配点的目的；s_T取值过小，则可能会将正确匹配的特征点作为误匹配点去除掉，本文中s_T取0.3。

2.2  旋转问题的解决

为了实现图像匹配中的旋转不变性，需要对每个特征点指定方向参数。具体方法就是在以特征点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。特征点(x，y)邻域像素的梯度m(x，y)和方向θ(x，y)的计算公式如下：

在以特征点为中心的一定邻域范围内，根据样本点的梯度方向生成一个梯度方向直方图，梯度方向直方图的范围为0°~360°，直方图每10°作为一个柱，共有36个柱。然后将邻域内的每个采样点按梯度方向θ归入适当的柱，以梯度模m作为贡献的权重。最后选择直方图的主峰值作为特征点的主方向，选取量值达到主峰值80%以上的局部峰值作为辅助方向。这样一个特征点可能会被指定具有多个方向，可以增强匹配的鲁棒性。

为了确保旋转不变性，在生成特征描述子的时候首先将坐标轴旋转到特征点的主方向，因此主方向的精确定位十分关键，如果主方向的定位不够精确，将直接影响描述子的特征向量，进而影响特征匹配的效果。文献[11]中，主方向直方图分成36个柱，每10°作为一个柱，本文给出了一个更精确的特征点主方向：

其中：b_m为最初的主方向；为更精确的主方向；h[c]为指向最初主方向的柱值；h[l]和h[r]分别为h[c]左边和右边的柱值。

文献[11]中，在生成描述子的时候对以特征点为中心的8×8窗口内的像素值进行了高斯加权运算(越靠近特征点的像素其梯度值对描述子的贡献越大)，这主要是为了降低特征点的主方向定位不准确时，离特征点较远的点对特征点描述子的影响。当特征点的主方向定位比较准确时，这种做法不但降低了描述子对特征点的描述能力，而且增加了计算量，因此本文不再对特征点周围的像素值做高斯加权运算。

在视频图像序列运动目标跟踪过程中，为了解决旋转问题，在当前帧中的目标区域提取SIFT特征点，并与目标模板区域的SIFT特征点进行匹配。如果目标存在旋转，则正确匹配的特征点的主方向也将发生旋转，并且和目标旋转的角度一致，因此，可利用特征点主方向的变化来表示目标的旋转变化。设匹配正确的特征点个数为n，其中对应模板区域的特征点为，i=1，2，…，n，其主方向为，i=1，2，…，n；对应当前帧中目标区域的特征点为，i=1，2，…，n，其主方向为，i=1，2，…，n。另设模板目标的角度为θ₀，则当前帧中目标的角度θ₂可表示为：

对匹配成功的特征点，其中可能存在误匹配，而误匹配特征点主方向的变化与其他正确匹配的特征点相比，往往相差会比较大，其对当前帧中目标的角度影响也会比较大，因此，需要去除少数发生误匹配的特征点带来的影响。由于当前帧中目标的角度与上一帧中目标的角度相差不会很大，因此可根据这一点来去除误匹配，设上一帧图像中目标的角度为θ₁，并设，则当

时，则认为该匹配点为误匹配。其中，θ_T为角度差的阈值，本文中取30°。

2.3  算法步骤

为了提高算法的实时性，本文只在含有目标的最小区域内检测尺度空间极值点，从而降低了整个算法的计算量，提高了算法的实时性。综上所述，本文提出的算法的具体步骤如下：

(1) 读取第一帧图像I₀，根据Mean Shift算法统计图像中给定目标的颜色特征作为目标模板，并记录目标的角度θ₀和尺度s₀。

(2) 在目标区域检测SIFT特征点并生成SIFT特征向量，j=1，2，…。

(3) 读取下一帧图像I_i，i=1，2，…，假设上一帧图像中目标的角度和尺度分别为θ₁和s₁(对于第二帧图像，θ₁=θ₀，s₁=s₀)，若图像不存在则退出。

(4) 将图像I_i旋转角度θ₁，得到目标角度为零的图像。

(5) 对图像中的以s₁为尺度的目标进行均值漂移运算，得到目标的中心并计算其在图像I_i中的坐标。

(6) 在图像I_i中以目标中心为中心，截取包含目标的最小正矩形图像，并在该图像中检测SIFT特征点，生成SIFT特征向量，j=1，2，…。

(7) 将，j=1，2，…与，j=1，2，…进行匹配并去除误匹配。

(8) 根据匹配的特征点的尺度和角度变化计算当前帧中目标的尺度s₂和角度θ₂，并令θ₁=θ₂，s₁=s₂转到步骤(3)。

3  实验结果及分析

为了验证本文提出的跟踪算法的有效性，用实际拍摄的视频图像序列进行试验，将新算法与传统的均值漂移算法进行比较。本文算法的开发环境为VC++6.0，机器配置为Pentium 4 2.8 GHz，1 G内存，实际拍摄的图像采集速度为15帧/s。

图2所示为改进的均值漂移算法^[8]对存在尺度变化目标的跟踪实验结果，该算法是在上一帧核函数窗口宽度的基础上分别增加和减少10%的办法来探测当前帧核函数窗口的实际宽度。由于Bhattacharyya系数往往很容易在较小的核函数窗口内取得局部最大值，因此在目标逐渐增大的过程中，核窗口宽度不但难以被扩大，反而会逐渐变小。图3所示为当目标存在尺度变化时本文算法的跟踪实验结果。由图3可见：与改进的均值漂移算法相比，本文算法能较好的跟踪目标的尺度变化。图4所示为当目标存在旋转变化时改进的均值漂移算法^[15]的跟踪实验结果，图5所示为本文算法的跟踪实验结果。由图4和图5(特别是图5(e)和5(f))可见：当背景较复杂时，与本文算法相比，改进的均值漂移算法跟踪目标旋转角度的精确度难以保证。因此，与改进的均值漂移算法相比，本文算法能较好地跟踪目标的旋转变化。

图2  改进的均值漂移算法目标尺度跟踪实验

Fig. 2  Object scale tracking experiment of improved Mean Shift algorithm

图3  本文算法目标尺度跟踪实验

Fig. 3  Object scale tracking experiment of proposed algorithm

图4  改进的均值漂移算法目标旋转跟踪实验

Fig. 4  Object rotation tracking experiment of improved Mean Shift algorithm

图6所示为当目标存在旋转变化时改进的均值漂移算法与本文算法的计算量对比图。由图6可见：与改进的均值漂移算法相比，本文算法在有效解决目标跟踪中的尺度和旋转问题的同时，计算量有所增加，在实际应用中可以通过硬件加速(如GPU)等办法解决。

由于本文算法中目标的尺度和角度是根据正确匹配的SIFT特征点计算出来的，因此，对颜色或灰度信息较丰富的目标可提取出较多的特征点，具有较好的跟踪效果。而当目标区域过小或匹配的特征点过少时，算法跟踪效果将会受到影响。对此，本文的解决办法是当正确匹配的特征点数量少于3个时，目标的尺度和角度不再变化，即取上一帧的尺度和角度。另外，当目标过大或特征点数量过多时，算法的实时性将会受到影响，这也是本文算法的不足之处。对此，可设置一定的阈值，当目标区域大于一定的阈值并且匹配成功的特征点大于一定的数量时，将目标缩小一半后提取目标区域的特征点，最后计算目标的尺度时再扩大一倍，这样可降低算法的计算量，提高算法的实时性。

图5  本文算法目标旋转跟踪实验

Fig. 5  Object rotation tracking experiment of proposed algorithm

图6  算法计算量对比

Fig. 6  Computational complexity comparison of algorithms

除此之外，本文算法中的目标匹配是后续图像序列中的目标与第一帧的模板目标进行匹配的，其优点是在跟踪过程中，目标的尺度和旋转变化不受上一帧跟踪结果的影响，跟踪误差也不会累积，缺点是跟踪过程中模板没有更新。

4  结论

(1) 为了解决目标跟踪中的尺度和旋转问题，提出了基于尺度不变特征变换(SIFT)的均值漂移(Mean Shift)跟踪算法。

(2) 该算法首先利用SIFT算法提取目标区域的特征点并进行匹配，然后根据相邻帧之间尺度和角度的连续性，去除误匹配，最后利用正确匹配的特征点中的尺度和角度信息，计算被跟踪目标的尺度和旋转角度。当被跟踪目标的角度和尺度发生变化时，该算法皆具有较好的跟踪效果。该算法的不足之处是当被跟踪目标的特征点较少时，跟踪效果会受到一定程度的影响。

参考文献：

[1] Abramson H, Avidan S. Tracking through scattered occlusion[C]//2011 Conference on Computer Vision and Pattern Recognition. Colorado: IEEE Computer Society, 2011: 1-8.

[2] Han Z, Ye Q, Jiao J. Combined feature evaluation for adaptive visual object tracking[J]. Computer Vision and Image Understanding, 2011, 115(1): 69-80.

[3] Comaniciu D, Ramesh V, Meer P. Real-Time Tracking of Non-Rigid Objects Using Mean Shift[C]//Proceeding of IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island: IEEE Computer Society, 2000: 142-149.

[4] Chia Y S, Kow W Y, Khong W L, et al. Kernel-based object tracking via particle filter and mean shift algorithm[C]//2011 11th International Conference on Hybrid Intelligent Systems (HIS). Malacca: IEEE Computer Society, 2011: 522-527.

[5] Li P. An adaptive binning color model for mean shift tracking[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(9): 1293-1299.

[6] Khan Z H, Gu I Y, Backhouse A G. Robust visual object tracking using multi-mode anisotropic mean shift and particle filters[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2011, 21(1): 74-87.

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

[8] Liu C Y, Yung N. Scale-adaptive spatial appearance feature density approximation for object tracking[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1): 284-290.

[9] 王长军, 朱善安. 基于Mean Shift的目标平移与旋转跟踪[J]. 中国图象图形学报, 2007, 12(8): 1367-1371.

WANG Changjun, ZHU Shanan. Mean Shift based targets' rotation and translation tracking[J]. Journal of Image and Graphics, 2007, 12(8): 1367-1371.

[10] Draréni J, Roy S. A Simple oriented Mean-Shift algorithm for tracking[J]. Image Analysis and Recognition, 2007, 18(4): 558-568.

[11] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[12] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[13] 牛长锋, 陈登峰, 刘玉树. 基于 SIFT 特征和粒子滤波的目标跟踪方法[J]. 机器人, 2010, 32(2): 241-247.

NIU Changfeng, CHEN Dengfeng, LIU Yushu. Tracking object based on SIFT features and particle filter[J]. Robot, 2010, 32(2): 241-247.

[14] Zhou H, Yuan Y, Shi C. Object tracking using SIFT features and Mean Shift[J]. Computer vision and image understanding, 2009, 113(3): 345-352.

[15] 贾静平, 柴艳妹, 赵荣椿. 一种健壮的目标多自由度 Mean Shift 序列图像跟踪算法[J]. 中国图象图形学报, 2006, 11(5): 707-713.

JIA Jingping, CHAI Yanmei, ZHAO Rongchun. Robust tracking of objects in image sequences using multiple degrees of freedom Mean Shift algorithm[J]. Journal of Image and Graphics, 2006, 11(5): 707-713.

(编辑  杨幼平)

收稿日期：2012-06-11；修回日期：2012-09-26

基金项目：国家自然科学基金资助项目(61203375，61203083，51175261)；济南大学博士基金资助项目(XBS1241)

通信作者：赵钦君(1981-)，男，山东临沂人，博士，从事机器视觉等研究；电话：15215315698；E-mail：cse_zhaoqj@ujn.edu.cn

摘要：为了解决目标跟踪中的尺度和旋转问题，提出一种基于尺度不变特征变换(SIFT)和均值漂移的目标跟踪算法。该算法首先检测模板区域和目标区域在尺度空间中的极值点，然后通过拟合三维二次函数精确定位特征点的位置和尺度，接着对目标区域和模板区域的特征点进行匹配，并根据相邻帧之间尺度和角度的连续性，去除误匹配，最后利用正确匹配的特征点中的尺度和角度信息，计算被跟踪目标的尺度和旋转角度。研究结果表明：当被跟踪目标的角度和尺度发生变化时，该算法皆具有较好的跟踪效果。