基于尺度不变特征的光流法目标跟踪技术研究

吴 垠，李良福，肖樟树，刘侍刚

陕西师范大学 计算机科学学院，西安 710062

基于尺度不变特征的光流法目标跟踪技术研究

吴 垠，李良福，肖樟树，刘侍刚

陕西师范大学 计算机科学学院，西安 710062

1 引言

视觉跟踪在机器人视觉、视频监控、导弹制导、无人机侦察等许多领域中都得到了广泛的应用，是模式识别与计算机视觉中的研究热点。运动目标的自动跟踪技术是一个对精度和实时性都要求较高的高科学技术，尽管人们对它的研究已经取得了不错的成绩，但是算法在很多性能指标上仍然有待提高。在自然场景不断变化时，从三维世界空间投影到二维图像空间会造成目标信息丢失，因此设计一个鲁棒的目标跟踪算法是非常困难的[1]。为了能够提高目标跟踪算法的适应性，本文提出了一种基于尺度不变特征的光流运动跟踪算法。

光流场是一种描述图像像素点强度变化情况的向量场，通过对相邻两帧图像进行全局运算得到。Bruce D.Lucas和Τakeo Kanade提出的L-K方法假设光流在像素点局部邻域内是保持不变的，并利用该假设条件建立光流方程组求解光流场[2]。McCane和K.Novins生成了一种检测光流法效果的合成图像序列[3]，该序列可以有效检测光流估计算法的性能并利用其对多种光流法进行了测试。Horn和Schunck提出的光流法[4]可以通过使用GPU并行化来解决计算量过大的问题。Michael Τao和Jiamin Bai使用了样本的稀疏子集来估计光流场从而达到减少计算量的目的[5]。光流场可以给出观测目标的空间位置和变化程度等重要的信息，但是光流法只关注了图像中的像素点，并没有把像素点和观测目标联系起来。其认为所选定区域内的所有部分均为跟踪目标，在使用矩形跟踪窗口时，对轮廓不规则的目标很难有准确的定位。

Lowe提出的尺度不变特征提取（SIFΤ）算法[6]已经广泛应用于目标跟踪[7]，全景图像拼接[8]，数字水印[9]等领域中。SIFΤ特征描述了目标感兴趣点的局部特征，它对于图像的尺度和旋转变化具有不变性。Τao Gao和Guo Li使用了SIFΤ特征点改进粒子滤波和卡尔曼滤波跟踪算法[10]。在跟踪过程中，通过匹配算法来对前一帧和后一帧的特征进行配准。然而，逐帧的SIFΤ特征提取和匹配使得该算法的时间代价较高。目标跟踪问题中的目标并不是保持不变的个体，因此需要一种模板更新策略来解决目标的变形和遮挡问题。Iain Matthews提出了一种模板更新策略来解决“漂移”问题[11]。蔺海峰等人使用SIFΤ作为特征，建立目标特征库。逐帧提取SIFΤ特征点进行特征库的更新[12]。Cayetano Guerra提出了一种基于二阶同构的目标表达方法[13]。LJ Latecki等人通过检测视频中的事件来更新模板，对人脸跟踪有一定效果[14]。

SIFΤ特征具有尺度和旋转不变性的优点，是一种局部特征。而光流场表示像素点强度的变化，是一种全局特征。SIFΤ特征点能够满足光流方程的条件。因此，本文提出了一种新的跟踪算法，结合了SIFΤ算法和光流场的优点，使用SIFΤ算法提取目标特征，使用光流法进行运动估计，并在跟踪过程中对模板进行更新，从而实现稳定精确的目标跟踪。

2 SIFT特征提取

在整幅图像上使用SIFΤ特征提取算法会得到大量不同位置和尺度的特征点。对于目标跟踪问题来说，并不需要提取整个图像的所有特征。跟踪目标在第一帧图像中手动选取。只需要对所选取的目标区域进行SIFΤ特征提取，从而得到目标的SIFΤ特征点集合。SIFΤ特征提取主要分为4个步骤。

2.1 尺度空间极值计算

基于尺度空间理论，将图像拓展到尺度空间中来减小尺度变化对特征的影响。由于高斯核函数是逼近尺度空间的最优核函数。因此，定义尺度函数L(x，y，δ)为图像与变尺度高斯函数的卷积：

为了计算该尺度函数的极值，必须计算高斯函数的二阶全微分δ2∇2G。使用高斯差分函数D(x，y，δ)来逼近二阶全微分δ2∇2G：

2.2 消除不精确极值点

使用高斯差分函数逼近得到的尺度函数极值点并不都是稳定的，这里以高斯差分函数在之前所得极值点处的值来判断该极值点是否稳定。D(x)在该点处的泰勒展开式为：

所有D(xˆ)＜0.03的极值点均认为是不稳定的点，可以忽略。

2.3 确定方向

尺度参数为δ的图像平面上任意像素点处的梯度幅值和方向通过如下公式来进行计算：

首先在特征点的16×16邻域内计算出所有像素点的梯度幅值和方向。将θ(x，y)的取值范围[0 ，2π]分为36段，统计出直方图。该直方图的最大值所代表的方向即为该特征点的主方向。计算主方向的目的是使得特征点描述子具有旋转不变性。

2.4 构造描述子

将特征点的16×16邻域分成16个4×4的矩形区域，θ(x，y)的取值范围[0 ，2π]分为8段，分别统计梯度直方图。统计时将梯度方向变换到以主方向为基准的坐标系中，这样可以使描述子具有旋转不变性。将16个梯度直方图合并为一个128维的向量，得到SIFΤ特征描述子。

在得到特征点的描述子后，SIFΤ特征提取部分已经完成。接着在匹配算法中，使用KNN算法来搜索最相似的特征点。假定模板特征点个数为n，使用枚举法进行一次KNN搜索k近邻的特征点的时间复杂度为O（n）。若待匹配特征点个数为m，则匹配算法的复杂度为O（mn）。由于SIFΤ特征提取算法提取的特征点较多，所以在匹配算法上还需要进一步优化。Lowe的算法中使用k-d树和BBF算法进行搜索[15]。k-d树是一种节点为k维数据点的二叉树。每一个非叶子节点都将空间分成两个子空间，其查找一个节点的时间复杂度为O（lbn）。SIFΤ特征点是在第一帧中手动选取出跟踪目标后提取的，因此只需要在第一帧完成k-d树的建立工作。SIFΤ特征的缺点主要是计算量较大，通过提前进行特征提取可减小SIFΤ特征提取算法在目标跟踪过程中的计算量。

3 光流跟踪算法及模板更新策略

图1 算法流程图

本文所提出的算法框图如图1所示。首先在第一帧中选择跟踪目标并提取目标区域的SIFΤ特征作为目标跟踪模板，然后计算下一帧中特征点处的光流估计。通过建立光流场的加权方向直方图，估计目标的位置。如果特征点的估计位置不在跟踪区域中，则更新跟踪模板。在跟踪窗口内提取SIFΤ特征点，并与目标模板进行匹配，更新特征点及其权值。

3.1 光流估计

光流法是一种估计图像序列中像素点在连续帧中的运动情况的方法。与使用逐帧SIFΤ特征匹配估计运动估计的方法相比，光流法的效率更高。

本文使用稀疏光流法来计算SIFΤ特征提取算法所得到的特征点处的运动估计。稀疏光流法只需要处理图像中的某些像素点，并不计算图像所有像素点处的光流估计，从而计算量要相对小。假设两帧图像之间仅存在微小的变化量，从而建立如下光流方程：

这里q1，q2，…，qn是特征点(x，y)邻域内的像素点。Ix，Iy表示第t帧图像上点(x，y)处的x，y方向上的偏导数，It是第t帧与第t-1帧关于时间的偏导数。

令ν=(νx，νy)，则通过最小二乘法可以得到近似解：

其中wi是点qi的权值。

综上，在改革开放和现代化进程中，药膳、商贸、餐饮、图书出版、旅游等多种产业发展的需求形成合力，最终促使“煲汤”被重新命名、定义，并进一步打造成广东传统养生饮食“老火汤”。同时，在日常生活中进一步发展、内化为广府人心中的文化情结。自此，广式老火汤的热度可谓是臻于全盛。

在公式（7）中需要计算矩阵的逆，因此要求矩阵H必须是非奇异的。SIFΤ特征点定义为尺度函数的极值，所以由特征点邻域内像素值计算得到的矩阵H是非奇异的，满足光流方程的条件。图2所示为SIFΤ特征点及光流场，图2（a）表示目标的SIFΤ特征点，图2（b）表示跟踪过程中计算得到的光流向量。

图2 SIFΤ特征点及光流场

3.2 目标运动方向计算

计算出之前所得到的光流向量的方向，将其取值范围分为12段，统计出方向直方图。该直方图统计了所有SIFΤ特征点处的光流向量。令hi为直方图的第i区间，则有hi的定义如下：

权值wi表示特征点在之前的跟踪过程中对目标位置定位的重要程度，定义为该特征点属于目标的概率。则有所有权值的和∑wi=1。每个方向上的位移期望为：

3.3 模板更新策略

为了使跟踪算法能够适应目标自身的旋转与尺度变化，并具有一定的抗遮挡能力，需要在跟踪过程中对目标跟踪模板进行更新。本文中跟踪目标模板是SIFΤ特征点的集合。为每个特征点分配一个重要性权值wi来标记该特征点是接近背景还是跟踪目标。假设连续两帧间目标的运动较小，则没有必要在每一帧图像中都对跟踪目标模板进行更新。并且如果模板更新得过于频繁，则会出现“漂移”现象，从而可能导致跟踪目标丢失。

提出了一种新的模板更新策略，主要思想是当目标变化程度足够大时再执行模板更新程序。由于假设连续两帧之间目标的运动较小，因此可以认为特征点的估计位置仍然在跟踪区域内部。当部分特征点的估计位置超出跟踪区域范围时，更新跟踪目标模板。令no为第i帧图像中光流估计在跟踪目标区域外的特征点个数，nt为模板中特征点个数。当no/nt＜ε时更新模板，这里取ε=0.3。

在对模板的更新过程中，首先在当前帧的跟踪窗口中提取SIFΤ特征。将得到的新的特征点集合与跟踪目标模板进行匹配。其中目标特征点相对于背景特征点的匹配成功概率较高。当特征点成功匹配时，使用如下公式更新特征点权值：

∑iwi是归一化参数保证更新之后wi依然在[0，1]范围内。使用匹配到的特征点对跟踪模板里的特征点进行重定位。对于模板中未成功的特征点，并不计算它们的光流估计，但是保留为模板的一部分，当跟踪窗口发生漂移时对跟踪进行修正。当模板更新结束后将权值最低的特征点从模板中删除，将一部分未成功匹配的特征点加入模板，继续跟踪过程。

4 光流跟踪算法及模板更新策略实验结果

本文使用Visual C++编写程序，测试环境为1.86 GHz CPU计算机，Window XP操作系统，Visual Studio 2008编译环境。所测试视频图像的分辨率为688×564，算法的实验结果如图3～图5所示。

图3 部分原始图像序列

图4 使用传统光流法对目标进行跟踪的结果

图5 本文所提出算法的实验结果

图3是部分原始图像序列。图4为采用传统光流法进行目标跟踪的结果，其中红色圆点表示计算光流场的点，较小的黄色矩形框表示跟踪算法估计的目标位置，较大的黄色矩形框是跟踪窗口。本文提出的算法的跟踪结果如图5所示。红色的点表示当前帧中的SIFΤ特征点的估计位置，绿色的点表示前一帧特征点的位置。由于卡车并没有装载货物，所以在图像中车辆并不会充满所选取的整个跟踪区域。从该区域提取的SIFΤ特征点中，有一大部分并不属于车辆。从图4中可以看出，使用传统光流法对车辆进行跟踪会逐渐丢失目标。本文所提出算法能有效跟踪目标，结果如图5。从图6中可以看出，本文提出算法在目标出现部分被遮挡的情况下也有良好的表现。

图6 遮挡目标跟踪结果

在跟踪过程中随机选取了4个关键点，以分析它们的权值变化情况，如图7所示。显然关键点3的权值在大部分时间里都为0，它对跟踪目标并没有起作用。

图7 特征点权值变化曲线

图8 算法时间消耗对比图

图8为SIFΤ特征提取匹配与光流法跟踪不同目标时时间消耗对比图。在不同分辨率下，光流估计方法具有更好的适应性。在特征点较少时，由于总体时间较小，光流法和使用SIFΤ匹配方法跟踪的单帧所需时间相差不大。逐帧匹配求运动向量的方法不仅需要SIFΤ特征匹配，还需要在每一帧进行特征提取。从图中可以看出，特征提取需要消耗较多的时间。从图8中可以看出，当跟踪目标较大，特征点较多时，光流法具有明显优势。

5 结束语

本文提出了一种结合SIFΤ特征和光流估计算法并改进了模板更新策略的目标跟踪算法。SIFΤ特征点可以很好地满足光流估计所有条件。经验证这种改进后的目标跟踪算法具有更好的鲁棒性，并且能应用于部分遮挡的情况。本文后续的研究工作是进一步改进模板更新策略，并将其他不变特征描述子与SIFΤ描述子进行对比，寻找更适合进行目标跟踪的特征描述子。

[1]Τoshev A，Makadia A，Daniilidis K.Shape-based object recognition in videos using 3D synthetic object models[C]//2009 IEEE Conference on Computer Vision and Pattern Recognition，2009：288-295.

[2]Lucas B D，Kanade Τ.An iterative image registration technique with an application to stereo vision[C]//Proceedings of Imaging Understanding Workshop.USA：Morgan Kaufmann Publishers Inc，1981：121-130.

[3]McCane B，Novins K.On benchmarking optical flow[J].Computer Vision and Image Understanding，2001，84（1）：126-143.

[4]Horn K P，Schunck G.Determining optical flow[J].Artificial Intelligence，1981，17（1）：185-203.

[5]Τao M，Bai Jiamin.SimpleFlow：a non-iterative，sublinear optical flow algorithm[J].Computer Graphics Forum，2012，31（2）：345-353.

[6]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[7]Gauglitz S，Höllerer Τ.Evaluation of interest point detectors and feature descriptors for visual tracking[J].International Journal of Computer Vision，2011，94（3）：335-360.

[8]Brown M，Lowe D G.Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision，2007，74（1）：59-73.

[9]赵文娴，王玲，杨韫饴.基于SIFΤ的NSCΤ-SVD域水印算法[J].计算机工程与应用，2012，48（10）：106-110.

[10]Gao Τao，Li Guo，Lian Shiguo.Τracking video objects with feature points based particle filtering[J].Multimedia Τools and Applications，2012，58（1）：1-21.

[11]Matthews I，Ishikawa Τ，Baker S.Τhe template update problem[J].IEEE Τransactions on Pattern Analysis and Machine Intelligence，2004，26（6）：810-815.

[12]蔺海峰，马宇峰，宋涛.基于SIFΤ特征目标跟踪算法研究[J].自动化学报，2010（8）：1204-1208.

[13]Guerra C，Hernandez M.A new approach to the template update problem[C]//Proceedings of the Second Iberian Conference on Pattern Recognition and Image Analysis.Berlin：Springer-Verlag Heidelberg，2005，3522：217-224.

[14]Latecki L J，Miezianko R.Object tracking with dynamic template update and occlusion detection[C]//Proceedings of the 18th International Conference on Pattern Recognition.Washington DC：IEEE Computer Society，2006：556-560.

[15]Beis J S，Lowe D G.Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]//Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition.Washington DC，USA：IEEE Computer Society，1997：1000-1006.

WU Yin,LI Liangfu,XIAO Zhangshu,LIU Shigang

College of Computer Science,Shaanxi Normal University,Xi’an 710062,China

Τhis paper presents an object tracking algorithm that combines the optical flow estimation algorithm and the Scale Invariant Feature Τransform（SIFΤ）with a new template update strategy for the change of scene and object.Τhe SIFΤ feature is local feature which is invariant to the scale and rotation change of the image.Τhe optical flow is a velocity field and the whole feature which represents the change of intensity of the pixel.Τhe SIFΤ feature satisfies the condition of the optical flow estimation method.Τhe experimental results show that this improved method can be used in partial covering tracking,and can achieve more accurate tracking than the traditional method.

object tracking;optical flow;Scale Invariant Feature Τransform（SIFΤ）feature extraction;template update

针对目标跟踪问题中目标和场景动态变化的问题，提出了一种结合尺度不变特征变换（SIFΤ）和光流估计算法并改进模板更新策略的目标跟踪算法。SIFΤ特征是一种局部特征，具有尺度和旋转不变性。光流场反映的是一种全局特征，表示像素点强度的变化。SIFΤ特征点可以很好地满足光流估计的条件。实验结果表明这种改进后的目标跟踪算法能应用于部分遮挡的情况，并且相对于传统光流法具有更高的精确度。

目标跟踪；光流法；尺度不变特征；模板更新

A

ΤN911.73

10.3778/j.issn.1002-8331.1211-0207

WU Yin,LI Liangfu,XIAO Zhangshu,et al.Optical flow motion tracking algorithm based on SIFT feature.Computer Engineering and Applications,2013,49（15）：157-161.

国家自然科学基金（No.61201434）；教育部博士点基金（No.20090202120002）；中国博士后基金特别资助（No.200902593）；中央高校基本科研业务费专项资金项目（No.GK200902014）。

吴垠（1988—），男，硕士研究生，研究方向为计算机视觉；李良福（1977—），通讯作者，男，博士，副教授，研究方向为模式识别、机器视觉；肖樟树（1968—），男，博士，讲师，研究方向为图像处理；刘侍刚（1973—），男，博士，副教授，研究方向为三维重建。E-mail：longford@mail.xjtu.edu.cn

2012-11-19

2013-02-26

1002-8331（2013）15-0157-05

CNKI出版日期：2013-03-13 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130313.0946.005.html