基于特征点一致性约束的实时目标跟踪算法

朱安民，陈燕明

深圳大学计算机与软件学院，深圳518060

实时跟踪技术在军事安全、交通监管、智能机器人及游戏娱乐产业等领域有广泛应用. 实时跟踪包括目标检测和目标跟踪两部分，其中目标的跟踪部分占实时跟踪的大多数时间，因此对跟踪的实时性起着关键作用.

目前的跟踪算法主要有点跟踪［1］、核跟踪［2］和轮廓跟踪［3］. 其中，点跟踪方法是以目标的特征点来表征目标，从视频当前帧的特征点寻找下一帧的匹配特征点，由此获得被跟踪的目标. 实际上，随着目标的运动和其所处场景的变化，在跟踪过程中经常发生点的特征发生剧烈变化或消失而导致跟踪失败的情况. 因此，面对光照变化、目标形变、部分遮挡、高速运动、尺度缩放、旋转、图片噪音和模糊等因素，如何选取目标的特征点是首要解决的问题. Qiao 等［4］提出利用获得目标的相位奇异点进行跟踪的方法. 当被跟踪的目标有明显纹理时，相位奇异点健壮性佳，且对缩放及旋转不敏感. 但是，噪音干扰也易使其被误认为是奇异点，且在视觉模糊的情况下，奇异点易被丢失. Khan 等［5］通过建立前景特征点集和背景特征点集，由增强的各向异性mean shift 算法跟踪两个点集，并建立目标模板集合进行匹配，从而得到跟踪轨迹. 该算法虽能较好地处理部分遮挡问题和较大程度的目标变形问题，但由于两个特征点集的计算量较大，运算时间长，对于高速运动目标，跟踪的实时性不足.Sun 等［6］采用Lowe［7］的SIFT 特征作为特征点，并建立点匹配的动态模型，但因SIFT 特征的计算量较大，且在遇到部分遮挡和变形的情况下会出现点跟踪失败，需建立目标模板模型弥补失败情况，进行目标匹配，增加运行时间，所以同样对于高速运动目标的追踪效果有待提高. Pan 等［8］采用基于多层隐马尔可夫模型的粒子滤波跟踪. 该算法随着层数的增加，跟踪的准确性明显增强，但是同时计算复杂性也提高，运行时间变长.

在实时跟踪过程中，目标所处的运动场景的变化和映射在二维图像中目标的变化，都会使原本用来描述目标的特征点消失. 因此，为持续描述被跟踪目标，需不断更新描述目标的特征点. 即使场景变化或目标变化导致特征点消失，仍可通过获得新的特征点描述目标，实现继续跟踪目标. 为提高跟踪的鲁棒性和实时性，本研究提出特征点动态选择模型算法，即采用Lucase-Kanade 光流法［9-10］计算跟踪特征点，并对特征点集进行一致性约束，从而提高特征点的可靠性. 该算法能较好地处理目标和场景变化导致的特征点跟踪丢失问题，动态选择一段时间范围内能够描述目标的相对稳定的特征点.

1 光流法简介

光流是运动物体在观察成像平面上的像素运动的瞬时速度. 光流法则是利用图像序列中像素在时域上的变化及相邻帧之间的相关性找到上一帧跟当前帧之间的对应关系，从而计算出相邻帧之间物体的运动信息的一种方法. 本研究采用Lucase-Kanade光流法计算像素的运动变化.

光流法有3 个前提假设:①相邻帧之间的亮度I 恒定;②相邻帧之间物体的运动较小;③保持空间一致性，即同一区域的像素具有相同运动［11］.

由假设①和假设②可得出光流约束方程为

经一阶泰勒级数展开可得

若由③假设一个局部范围内(u，v)相同，则

式(3)可记为Aμ = b.

图1 为光流法点跟踪示意图，根据光流法计算像素点P 在下一帧的对应点. 根据假设②，设点P为圆心，以r 为半径的圆是P 点的可能移动范围.在圆内搜索亮度值相同的点，如左图IP= Ia= Ib，根据假设③，若以P 点为中心3 ×3 的像素区域和分别以a 点和b 点为中心3 ×3 的像素区域亮度值一一对应相等，则点a 和点b 为P 点在下一帧的可能对应点. 比较点a 和点b 的μ 值，以μ 值最小的点作为P 点在下一帧的对应点.

图1 光流法点的跟踪示意图Fig.1 Point tracking diagram of optical flow method

2 运动目标的跟踪算法

运动目标跟踪算法模型如图2，虚线框中的动态选择模型包括目标模型(ⅰ)、随机采样模型(ⅱ)及一致性约束条件(ⅲ). 其中，目标模型为描述目标的特征点的集合，这些特征点决定了跟踪的目标所在的区域;随机采样模型为目标区域随机采样获得的点，这些点将作为候选的描述目标的特征点;一致性约束为运动目标区域内各点所具有的空间相关性，运动中目标区域的点具有速度和方向上的一致性，如线性运动的各点具有等速同向规律，旋转运动的各点具有等速异向规律等. 因此，可通过一致性约束来判断在场景变化或目标变化中不一致的特征点.

图2 运动目标跟踪算法模型Fig.2 Algorithm model of moving target tracking

本研究利用动态选择模型进行目标跟踪. 首先，模块ⅰ计算当前帧特征点在下一帧的对应点，模块ⅲ在当前帧目标区域随机采样特征点并计算其在下一帧的对应点;然后，模块ⅱ对模块ⅰ获得的对应点进行一致性约束评估，获得一致性约束条件;其次，模块ⅰ和ⅲ中符合一致性约束条件的对应点选为特征点;最后，将模块ⅲ中的特征点加入到模块ⅰ中.

2.1 动态选择模型

在相邻两帧之间，若目标区域的某点的特征具有唯一性，则说明该点稳定性好，可作为描述目标的特征点. 目标模型主要用于选择目标的特征点以保持特征的稳定性. 假设初始化目标方框，目标模型在目标方框内初始一组特征点集N，N(t)为随时间t 变化的特征点数. 利用中值法［14］预测下一帧目标方框区域.

中值法预测目标方框的计算过程如下:假设当前帧的特征点集为B = {b1，b2，…，bn}，对应的前一帧的特征点集为A = {a1，a2，…，an}，则:①计算各特征点坐标的水平偏移量为{dx1，dx2，…，dxn}，垂直偏移量为{dy1，dy2，…，dyn}，分别取数列{dx1，dx2，…，dxn}和{dy1，dy2，…，dyn}的中值可得目标方框的位移. ②计算A 中各点两两之间的欧式距离{da1，da2，…，dan}和B 中各点两两之间的欧式距离{db1，db2，…，dbm}，然后取数列{db1/da1，db2/da2，…，dbm/dam}的中值可得目标方框的缩放比例. 经上述两次中值法可预测下一帧的目标方框.

图3 是一个人影很明显的行人实例(predestrian2)，其特征点数量N(t)随时间t 的变化明显衰减:第1 帧初始化100 个特征点，刚开始在第2 帧保持100 个特征点，到第6 帧时许多不稳定点被丢失，在第36 帧发生遮挡后特征点数剩13 个，至第64 帧特征点数只剩6 个，最后随着目标的运动变化特征点全部丢失，跟踪失败.

图3 实例(pedestrian2)特征点的衰减情况Fig.3 The attenuation of feature points in the pedestrian2 video sequence

图4 给出了5 个跟踪实例［13］的特征点数N(t)随时间t 的变化情况. 由图4 可见，在时间范围Δt内，N(t)值变化很小. 此时的特征点可描述运动目标的特征. 我们称在Δt 时间内的特征点集具有稳定性. 但当t ＞Δt 时，N(t)值逐步减少，此时特征点集作为描述运动目标特征的可靠性降低，易致跟踪失败.

图4 5 个特征点集实例随时间衰减情况Fig.4 The attenuation of feature points in 5 video sequences

为解决特征点集衰减问题，本研究增加了随机采样模型. 首先在目标区域内随机选择100 个像素点，这些像素点与目标模型特征点不重复，根据光流法可计算这100 个像素点在下一帧的对应点，并把这些对应点作为随机采样模型获取的目标特征点. 当目标特征点数量N(t)值逐步减少至临界值时，从随机特征点集中选取新的特征点放入模型，并增大N(t)值以保持特征点集的稳定性. 图5 显示了单独的目标模型和本研究提出的联合了随机采样模型的目标模型，在目标跟踪中特征点集的变化情况. 从第28 帧开始，在只采用单独的目标模型的情况下，运动目标遇到部分遮挡，特征点数量急剧下降，第40 帧以后部分遮挡的情况消失，而采用本研究提出的联合了随机采用模型的目标模型后，由于不断获得新的特征点，继续保持跟踪目标的稳定性.

图6 给出一个室内明暗变化环境下跟踪行人时特征点集变化的对比实例. 其中，上2 组为单个目标模型特征点;下2 组为目标模型联合随机采样模型的特征点. 通过采样添加新的特征点，目标模型特征点的分布将逐步趋于脸部的轮廓、眼睛、鼻子和嘴巴等边缘，呈现与目标特征相关的规律，此时模型动态选择的特征点趋于更稳定.

2.2 特征点的一致性约束

一致性约束作为动态选择模型的一部分，有必要对其进一步说明:实时跟踪的目标运动形式可能是刚体运动、局部非刚体运动、高速运动、变速运动或兼有各种情况的体操运动［12］. 因此，分析目标的运动速度和运动方向有利于实现跟踪的鲁棒性，特别是当目标出现部分遮挡或者高速运动的情况时.

图5 实例car 特征点数量变化比较Fig.5 Comparison of feature points in car video sequence

图6 暗场景脸部跟踪中特征点的稳定性对比Fig.6 The stability of the feature points in low light

对同一个运动目标，假设视频跟踪的相邻两帧之间的时间是连续的，即目标的运动变化很小，则运动具有空间一致性，目标各特征点间具有位移和方向的一致性. 如图7 的变速情况，为运动目标分别沿x 轴和y 轴的位移. 从图7 可见，实例car 的运动变化较小，实例motocross 的运动变化剧烈. 由空间一致性可知，运动目标的速度即帧间的位移大小也具有一致性. 具体步骤为:①由欧式距离计算下一帧目标模型点的位移大小并统计概率;②分析概率分布的特征得出位移大小的临界值;③根据空间一致性约束筛选下一帧目标模型中的特征点和随机采样的新特征点.

图7 x 轴与y 轴方向上两个目标的运动轨迹Fig.7 The trajectory of two objects in the x-axis and y-axis

如图8，模型特征点集位移大小的概率分析为:设目标模型特征点数量为n，{x1，x2，…，xn}为各特征点的位移统计量，统计位移概率P(xk)，(0 ≤xk＜+ ∞，k = 1，2，…，n)，则概率分布函数为

其中，E = 3 为位移偏差;p(xi)为最大概率值. 当F(x)≥0.5 时，xi为模型特征点的位移临界值.

图8 柱形特征点位移的概率分析Fig.8 Probability analysis in displacement of feature points

图9 为视频car，目标小汽车经过遮挡物的情况. 当遮挡物与目标运动产生相对运动时，即产生运动方向的不一致性. 本研究采用运动方向的一致性约束，能及时剔除目标模型中偏离稳定性的特征点，并约束新添加的采样特征点. 其算法步骤与位移一致性类似:①计算下一帧的目标模型各个特征点相对于当前帧的目标模型特征点所在的方向(正东、东南、正南、西南、正西、西北、正北和东北)，然后统计这8 个方向上各方向的概率;②分析概率分布的特征得出下一帧的运动方向;③根据方向一致性约束筛选下一帧目标模型中的特征点和随机采用的新特征点.

图9 实例(car)特征点方向分析Fig.9 Direction analysis in feature points of car video sequence

模型特征点运动方向的概率分析如下:设目标模型特征点数量为n，{y1，y2，…，yn}为各特征点的方向统计量，统计方向概率P(yk)，(yk= 1，2，…，8，k = 1，2，…，n)，则概率分布函数为

其中，E = 1 为方向偏差;p(yi)为最大概率值. 当F(y)≥0.5 时，yi为模型特征点的运动方向，目标做线性运动;否则，目标做非线性运动.

一致性约束能使描述目标的特征点随目标的改变而变化，从而保持目标模型的稳定性.

3 实验结果及分析

本研究的实验数据均出自文献［13］，包括多种不同情况的实例视频，并按15 帧/秒的速率转化为320 ×240 的灰度图像序列处理. 本研究提出的动态选择模型跟踪算法通过学习特征点的稳定性进行运动目标的实时跟踪. 本实验中，首先用随机采样模型初始化目标模型. 在第1 帧中随机采样，选取目标区域中的100 个像素，利用Lucase-Kanade 光流法得到第2 帧的对应点，再根据一致性约束条件获得符合要求的对应点作为特征点(位移的临界值范围采用E = ±3)，此时这些特征点作为目标的特征描述用来初始化目标模型. 然后随机采样模型继续采样100 个像素，并行计算随机采样点和目标模型特征点在下一帧的对应点. 从目标模型特征点在下一帧的对应点中得到一致性约束条件，通过这些一致性约束条件剔除目标模型在下一帧中不稳定的特征点，同时用此一致性约束条件筛选随机采样点在下一帧中的对应点. 当目标模型中稳定的特征点的数量减少时，筛选过的随机采样点作为目标特征点加入目标模型，维持目标模型特征点的数量在一个峰值上. 如图10，实例motocross 跟踪过程有效特征点数N 最大达92，这也是本实验初始设置采样点为100 的原因. 另外，如实例motocross 和pedestrian2，N 最小为8，当N ＜8 时，特征点不足以描述目标，因此目标跟踪失败.

图10 目标模型特征点数峰值分析Fig.10 Peak analysis in object model

采用本研究提出的算法(model)和具有代表性的3 种算法［14］，包括FB (forward-backward)、NCC (normalized cross correlation)、FB + NCC 分别进行跟踪实验，并进行对比，结果如表1. 其中，7个实例分别为①低速行驶穿过部分遮挡物的汽车(car);②室内亮度变化的行人(david);③剧烈晃动的跳绳运动(jumping)，④身体有遮挡的并行路人(predestrian1);⑤人影很明显的行人(predestrian2);⑥背景和衣色纹理相似的行人(predestrian3);⑦高速运动中的越野摩托(motocross).

表1 FB，NCC，FB+NCC 算法与本研究算法在有效跟踪上的帧数对比Table 1 Comparison with approaches (FB，NCC，FB+NCC)in terms of the numbers of correctly tracked frames

由表1 可见，在大部分低速运动的实例(car、david 和pedestrian2)中，几种算法都能获得较多的连续跟踪，对部分遮挡情况都有很好的适应性，但当遮挡面积占目标比例变大时，如实例car 中，FB+NCC 算法最早跟踪失败. 其次，如实例motocross这种高速变速运动，FB、NCC 和FB +NCC 等算法因无法快速适应变化的特征点，导致跟踪失败. 本研究提出的模型算法能较好地适应该情况，获得良好的跟踪效果. 最后，图11 给出本算法在时间效率上的情况，图中可知本算法的平均耗时优于FB+NCC 算法，有较高的实时性.

图11 本算法和FB+NCC 算法目标跟踪效率比较Fig.11 Comparison with FB+NCC on the time efficiency

结 语

为能实时平稳跟踪动态目标，提出一种基于光流法的目标跟踪算法. 该算法通过实时学习目标的特征点，而这些特征点在一定时间范围内具有稳定描述目标特征的特性，即在面临光照变化、目标形变、部分遮挡、变速运动、尺度缩放、旋转、图片噪音和模糊等因素的情况下仍能有效表达目标特征，从而找出具备一致性约束的特征点进行跟踪并获得目标的运动轨迹. 较之现有流行目标跟踪算法，该算法具有目标跟踪的稳定性，即不易跟丢目标，同时该算法耗时相对较少，实时性较高. 不过，和其他算法类似，该算法在实时跟踪的目标消失或完全遮挡情况下，需重新检测目标，才能继续跟踪. 下一步，我们将结合目标检测的算法，处理目标消失和完全遮挡后继续跟踪的情况.

/ References:

［1］HuuGiao Nguyen，Fablet R，Ehrhold A，et al. Keypoint-based analysis of sonar images:application to seabed recognition ［J］. IEEE Transactions on Geoscience and Remote Sensing，2012，50(4):1171-1184.

［2］Ren C X，Dai D Q，Yan H. Coupled kernel embedding for low-resolution face image recognition ［J］. IEEE Transactions on Image Processing，2012，21(8):3770-3783.

［3］Yilmaz A，Javed O，Shah M. Object tracking:a survey［J］. ACM Computer Surveys，2006，38(4):1-45.

［4］Qiao Y，Wang W，Minematsu N，et al. A theory of phase singularities for image representation and its applications to object tracking and image matching ［J］. IEEE Transactions on Image Processing，2009，18(10):2153-2166.

［5］Khan Z H，Gu I Y H. Joint feature correspondences and appearance similarity for robust visual object tracking［J］. IEEE Transactions on Information Forensics and Security，2010，5(3):591-606.

［6］Sun L，Liu G Z. Visual object tracking based on combination of local description and global representation ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2011，21(4):408-420.

［7］Lowe D G. Distinctive image features from scale-invariant key points ［J］. International Journal Computer Vision，2004，60(2):91-110.

［8］Pan P，Schonfeld D. Video tracking based on sequential particle filtering on graphs ［J］. IEEE Transactions on Image Processing，2011，20(6):1641-1651.

［9］Fernando W S P，Udawatta L，Pathirana P N. Identification of moving obstacles with Pyramidal Lucas Kanade optical flow and k means clustering ［C］// Proceedings of 3rd International Conference on Information and Automation for Sustainability. Melbourne (Australia): IEEE Press，2007:111-117.

［10］Siong L Y，Mokri S S，Hussain A，et al. Motion detection using Lucas Kanade algorithm and application enhancement ［C］// International Conference on Electrical Engineering and Informatics. Bangi (Malaysia):IEEE Press，2009，2:537-542.

［11］Pyda B，Brindha R. A novel high speed L-K based optical flow computation ［C］// International Conference on Communication and Computational Intelligence.Erode(India):IEEE Press，2010，2:104-108.

［12］Kovashka A，Grauman K. Learning a hierarchy of discriminative space-time neighborhood features for human action recognition ［C］// Conference on Computer Vision and Pattern Recognition. San Francisco (USA):IEEE Press，2010，2:2046-2053.

［13］Yu Q，Dinh T，Medioni G. Online tracking and reacquisition using co-trained generative and discriminative trackers ［J］. Lecture Notes in Computer Science，2008:678-691.

［14］ Kalal Z，Mikolajczyk K，Matas J. Forward-backward error:automatic detection of tracking failures ［C］// The 20th International Conference on Pattern Recognition.Istanbul (Turkey ): Springers Press，2010:2756-2759.