基于LK光流跟踪法的有效目标点增强跟踪*

蒋　菱，程　赓（四川大学 计算机学院（软件学院），四川 成都 610065）

基于LK光流跟踪法的有效目标点增强跟踪*

蒋菱，程赓
（四川大学 计算机学院（软件学院），四川 成都 610065）

为了提高基于几何形态的物体跟踪方法的准确率，详细分析了基于几何形态的物体跟踪方法下目标点的正确性，并根据分析的结果，在对目标物体采样时选取更容易被跟踪到的目标点，对于跟踪的结果，排除由于背景影响产生的无效目标点，从增强有效点和排除无效点这两方面入手，提出了基于LK光流法的有效点增强跟踪算法。实验证明，提出的算法能够更加有效地跟踪物体，尤其是当目标快速运动或者发生形变时，能够有效地减少跟踪目标的中心错误率。

目标跟踪；LK光流法；有效点增强

0　引言

基于几何形态的物体跟踪方法是计算机视觉领域一个被广泛研究的问题，其中普遍使用的方法是先用矩形或椭圆形的包围盒初始化需要被跟踪的物体，给出包围盒在t时刻的大小及位置，跟踪器跟踪物体运动并估计在t+1时刻包围盒的大小及位置。为了让跟踪算法适应被跟踪物体所在环境的变化和物体本身外观的改变，视频跟踪的方法也越来越复杂，但无论是基于生成模型的跟踪方法，还是基于辨别模型的跟踪方法，都会假设被跟踪的物体在t时刻的状态是已知的并且是正确的，而对于绝大多数现实世界的视频来说，这个假设成立的条件非常苛刻，导致跟踪器跟踪失败。

LK光流法自从1981年被提出后，就被广泛应用于计算机视觉的各个方面，如医学图像配准［1］、图像拼接［2］、视频追踪［3-4］等领域。对于给定的模板，LK光流法用梯度下降的方法求解图像中与模板误差最小的块。而在视频跟踪领域，流传最广的就是 Lucas-Kanade跟踪算法［5］以及它的金字塔应用［6］，两个算法依靠估计被跟踪块的平移量来确定物体的运动方向。在此基础上，Kanade-Lucas-Tomasi跟踪器［7］又将仿射变换和角点检测的方法引入了LK光流法之中，进一步增强了追踪的效果。由于LK光流法需要耗费大量运算重新估计Hessian方程，HAGERGD［4］提出了交换图像与模板的角色的方法，提高了追踪的效率。而后，上述文章中所提到的思想又被重新整合，形成了反向组合算法［8］。

为了降低失败率，本文在LK光流法的基础上分析了导致追踪失败的几个原因，并结合这些原因提出了一种新的跟踪算法。

1　追踪点的正确性分析

LK光流跟踪法作为一种基于模板的追踪算法，首先需要在包围盒中选取有效的跟踪点，然后在视频的每帧之间建立点到点的运动轨迹，最后根据跟踪到的有效点估计新的包围盒。这样的跟踪方式存在以下问题：首先，对于跟踪点，每次跟踪结果不可避免地会产生误差，由于误差的累积，便会导致跟踪窗口的偏移；其次，如果某些目标点所在部分在后续视频中突然产生形变，被遮挡或者消失，跟踪器将会丢失目标，导致跟踪失败［9-10］。为了降低跟踪器的失败率，首先引入了一套判断机制判断跟踪到的点是否有效；其次，由于使用包围盒初始化追踪器，目标物体不可避免地会带入背景信息，影响跟踪器的跟踪效果，为了提高正确率，本文从初始化目标点的选取和排除两方面进行分析并提出了新的增强有效跟踪点的方法。

1.1被跟踪点的失效检测

这里主要引入了Forward-Backward错误检测和SSD错误检测两种检测被跟踪点是否失效的方法。

SSD错误检测方法是最常用的跟踪错误检测方法之一。这种检测方法假设在跟踪过程中目标点所在环境的变化量在一定范围内。实现方法如下，在t时刻，用目标跟踪点周围的图像块R描述目标跟踪点。跟踪目标点至t+1时刻，并得到它在t+1时刻的描述R′，SSD错误检测算法的跟踪误差则表示为：

SSD值用来衡量两个图像块的相似程度，SSD值越高，表示两个图像块之间越不相似，SSD值高于某个阈值时，则跟踪错误。这种误差描述方法的缺陷如图1（a）所示，位于车胎前轮的点②因为被遮挡而在第二张图中消失，但由于图片中存在与点②极其相似的点③，跟踪器跟踪点②到点③，SSD错误检测方法无法排除被错误跟踪的点③这种点漂移的情况。为了解决这种错误跟踪的情况，引入了Forward-Backward错误检测方法。

Forward-Backward错误检测方法是基于正向追踪与反向追踪的一致性假设产生的方法，认为被正确追踪到的点应该独立于时间轴，即正向追踪和反向追踪生成的轨迹差别不大。具体实现方法如图1（b）所示。用S=（It，It+1，…，It+k）表示一段视频中的一系列帧，Pt为其中一个被跟踪点在t时刻的位置，首先，追踪器追踪点 Pt，经过正向追踪k步后生成点Pt的轨迹=（Pt，Pt+1，…，Pt+k）。然后，令=Pt+k，反向追踪点，同样生成追踪 k步后的轨迹=（，，…，）。最后，比较两条轨迹，如果它们相差太远，则跟踪错误。为了简化运算，本文使用点Pt与之间的欧式距离表示两条轨迹之间的差距，则

图1　SSD错误检测方法的缺陷及Forward-Backward错误检测方法原理

如果正向跟踪目标物体的轨迹与反向跟踪目标物体轨迹之间的差距小于一定的阈值，则认为目标点已被正确地跟踪到。

图 1中，Forward-Backward错误检测方法可以排除正向追踪轨迹与反向追踪轨迹差别太大的点。点①在两张图中均可见，跟踪器正向追踪与反向追踪的结果一致；点②因为被遮挡而在第二张图中消失，导致正向追踪轨迹与反向追踪轨迹差别较大。

1.2跟踪点初始化

跟踪器在跟踪过程中的表现对跟踪点的初始化方法非常敏感，因此，如何初始化跟踪点也就显得至关重要。初始化跟踪点通常有两种方法：静态初始化方法和适应性初始化方法。静态初始化方法采用第一帧包围盒中的点初始化跟踪器，对于目标点的选择，一种方法是随机选择包围盒中的点作为目标点；另一种方法则是用第一帧中的特征点初始化跟踪器［5，7］。但问题是，由于静态模板不足以表达被追踪物体的所有形态，即使是包围盒中的特征点，也有可能在后续视频中被遮挡、消失或者发生形态的改变而导致跟踪失败。适应性初始化方法在追踪过程中逐渐更新目标模型，这种方法的好处是可以适应物体外表、光照或者周围环境的变化。但是由于每步更新产生的误差的累积，包围盒会逐渐发生漂移。

为了辨别什么样的目标点更容易被跟踪到，本文分别使用LK光流法跟踪视频第一帧中所有像素点和第一帧中的特征点，并使用Forward-Backward错误检测方法和SSD错误检测方法排除跟踪错误的点，结果如图2所示，可以发现：（1）如果目标点周围没有任何特征点存在，那么目标点一定不能被追踪到；（2）并不是所有特征点在追踪过程中都能被追踪到；（3）特征点周围的点比其他目标点更容易被追踪到。

结合上述特点，特征点及其周围的点被跟踪到的概率更高，在连续两帧图像中，尤其如此。但是，如果每帧都计算特征点，需要耗费大量的运算，从而降低了跟踪效率。为此，本文提出一种新的目标点选取方法来权衡静态初始化和适应性初始化方法：（1）首先用包围盒中的随机点初始化视频的第一帧；（2）用LK光流法跟踪这些目标点，分别计算这些点的SSD误差和Forward-Backward误差；（3）保留误差最低的20％的目标点；（4）在初始化下一帧时，在保留下来的目标点周围再随机选取目标点。

图2　错误检测与排除

1.3基于运动域的错误点检测

LK光流法使用跟踪到的有效点估计下一帧的目标包围盒，为了包围所有的有效点，在估计的包围盒中会逐渐带入背景信息。使用LK光流跟踪法跟踪目标物体，并使用Forward-Backward错误检测方法和SSD错误检测方法排除被错误跟踪的点，其中连续两帧的检测结果如图3所示。图3（a）中的点为t时刻在目标跟踪物中选取的被跟踪的点，图3（b）为使用LK光流法跟踪目标点至t+1时刻并且使用 Forward-Backward错误检测方法和SSD错误检测方法后保留下来的目标点，部分目标点位于被跟踪的物体上，而部分则在背景环境中，对于目标点的跟踪，这些保留下来的目标点都是可靠的，但对于目标物体的跟踪，位于背景环境中的点则会让跟踪窗口逐渐产生漂移。但是在大部分情况下，被跟踪物体上目标点的运动方向与背景环境中目标点的运动方向并不一致，图3（c）记录了所有可靠的目标点从t时刻到 t+1时刻的运动方向，图3（d）为对运动方向统计的结果，高度较高的方块统计位于跟踪物体上的目标点的运动方向，高度较矮的方块统计位于背景环境中的目标点的运动方向，可以发现，目标物体的运动方向与背景的运动方向发生了明显的分离。

图3　连续两帧的检测结果

利用这个特性，可以降低背景环境的点对跟踪结果的影响，具体方法如图4所示。

图4　降低背景环境的点对跟踪结果的影响

然后，对运动方向向量进行分类。笔者认为，如果存在目标物体的运动方向和背景的运动方向发生分离，那么将所有运动方向向量投射到单位圆后，运动方向向量会呈现出明显的区域化特征，如果对所有单位化后的运动方向向量按照逆时针0～360°方向进行编号，其中某些相邻运动方向向量之间的夹角会明显大于其他的相邻运动方向向量之间的夹角。基于这个假设，需要先对运动方向单位化：

而后对单位化后的运动方向向量按照逆时针方向进行编号，对于两个编号相邻的运动方向，计算它们之间的夹角：

如图5所示，由于余弦函数在0～2π的范围内并不是单调递减函数，因此需要排除余弦值大于t，但是角度却大于预设值的运动方向向量夹角。这里通过判断运动方向向量所在象限进行排除，如果相邻运动方向向量夹角的余弦值大于t，对于和，通过其坐标，确定所在的象限ψm+1和ψm，如果两个象限不连续，则同样记录下夹角的编号。然后，从记录下来的编号处分开，将运动方向分为Nm类。

图5　运动方向向量夹角

最后，在分类的基础上确定主运动方向，统计每类中运动方向向量的数量：

如果其中一类中运动方向向量的数量明显大于其他类，则确定这类为目标物体的运动方向，保留拥有这类运动方向向量的目标点。

2　基于LK光流法的有效点增强方法

前面分析了目标点的正确性，结合上述分析，提出了鲁棒性更强并且效果更好的基于LK光流法的有效点增强跟踪方法。除视频第一帧外，追踪器接收相邻两帧图片 It和 It+1以及在 t-1时刻到 t时刻追踪到的所有目标点Pt，输出从t时刻到t+1时刻追踪到的所有目标点Pt+1，再根据 Pt+1估计 t-1时刻包围盒的位置。算法流程如图6所示。

图6　算法流程

（1）随机初始化第一帧的包围盒。

（2）追踪目标点，其中，依靠 LK光流追踪器生成从时刻到t+1时刻目标点的运动轨迹。

（3）按照式（1）和式（2）对追踪到的目标点进行 SSD错误检测和FB错误检测。

（4）按照1.3节提出的方法分离背景与目标物体，进一步去除在背景中的目标点。

（5）在剩下的点中保留20％误差最小的目标点，并根据它们重新估计包围盒。对于包围盒的估计，首先假设物体可以表示为方形的图像块，找到目标点中最小行数 rmin、最大行数 rmax、最小的列数 cmin、最大列数 cmax，并设置一个范围值 △，则新的包围盒可表示为［cmin-△，rmin-△，cmax+△，rmax+△］。

（6）在以保留下来的目标点为中心，R为半径的区域内重新选择追踪目标点，并在下一次追踪中重复步骤（2）到步骤（6），直到整个视频完结。

3　实验结果与分析

本节分别在三个数据集上实验了基于LK光流法的有效点增强跟踪算法，并与中值跟踪算法进行对比，采用中心错误率来衡量试验结果的准确性，实验结果图7所示。首先，对于快速运动、正常运动或者在运动过程中产生了形变的目标，中值跟踪算法和基于LK光流法的有效点跟踪算法的中心错误率在总体上均呈现出逐步上升的趋势，这是由于每步更新均会产生误差，误差逐步地累积导致中心错误率逐步上升，但是无论在哪种情况下，基于LK光流法的有效点增强跟踪算法的中心错误率总是低于中值跟踪的中心错误率。

但是，当目标物体为快速运动状态或者当目标物体发生形变时，本文提出的方法的中心错误率会明显低于中值跟踪算法，这是因为在这两种状态下目标物体的包围盒中更加容易带入背景信息，这些背景信息则导致目标中心误差越来越大，而本文的方法减少了背景信息的影响，所以中心错误率会维持在能够接受的范围内。

图7　实验结果

4　结论

本文详细分析了在基于几何形态的物体跟踪中被追踪的目标点的正确性，并根据分析的结果，提出了基于LK光流法的有效点增强跟踪算法，经过优化后的算法能够更加有效地跟踪物体，尤其是当目标快速运动或者发生形变时，采用本文方法能有效地将中心错误率控制在一定的可以接受的范围之内。但是由于增加了对跟踪到的点的处理步骤，产生了额外的计算，因此效率方面稍稍低于原来的方法。以后的工作会着重提高效率，改进有效点的选取策略，并且将之运用在更多的数据集上进行测试，同时利用测试结果进一步改进策略。

［1］CHRISTENSEN G E，JOHNSON H J.Image consistent registration［J］.IEEE Transactions on Medical Imaging，2004，20 （7）：568-582.

［2］SHUM H Y，SZELISKI R.Construction of panoramic image mosaics withglobal and local alignment［J］.International Journal of Computer Vision，2000，16（1）：63-84.

［3］BLACK M，JEPSON A.Eigen-tracking：robust matching and tracking of articulated objects using a view-based representation［J］.International Journal of Computer Vision，1998，36（2）：101-130.

［4］HAGER G D，BELHUMEUR P N.Efficient region tracking with parametric models of geometry and illumination［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（10）：1025-1039.

［5］LUCAS B D，KANADE T.An iterative image registration technique with an application to stereo vision［J］.International Joint Conference on Artificial Intelligence，1981（81）：674-679.

［6］BOUGUETJ Y.Pyramidal implementationof thelucas kanadefeaturetracker descriptionof thealgorithm［M］.Technical Report，Intel MicroprocessorResearchLabs，2000.

［7］SHI J，TOMASI C.Good features to track［C］.Conference on Computer Vision and Pattern Recognition，1994：593-600.

［8］BAKER S，MATTHEWS I.Lucas-kanade 20 years on：a unifying framework［J］.International Journal of Computer Vision，2006，56（3）：221-255.

［9］ROSTEN E，DRUMMOND T.Machine learning for highspeed corner detection［C］.ECCV 2006，2006，3951：430-443.［10］MCCANE B，NOVINS K.On benchmarking optical flow［J］.Computer Vision and Image Understanding，2003，84（1）：126-143.

Valid points reinforced tracking based on LK optical flow algorithm

Jiang Ling，Cheng Geng
（College of Computer Science，Sichuan University，Chengdu 610065，China）

To improve the accuracy of object tracking method based on the geometric shape，this paper analyzes the correctness of the target points in geometric-based tracking method in detail.In accordance with the result of analysis，for the sampling of the target object，selecting the points which can be tracked more easily；for tracking results，excluding the invalid points coused by background.From the aspects of enhancing the valid points and excluding the invalid points，this paper proposes a valid points reinforced tracking method based on LK optical flow algorithm.Experiments show that proposed method performs better，and can effectively reduce the center error rate of the object especially when the targetmoves fast or deformation occurs.

object tracking；LK optical flow algorithm；valid points reinforced

TP391.9

A

1674-7720（2015）06-0045-05

2014-11-21）

蒋菱（1989-），女，硕士，主要研究方向：图像处理，视频追踪。

国家自然科学基金（ 60903118 ， 61103137 ） ；国家科技支撑计划（ 2012AA011801 ）

程赓（1989－），男，硕士，主要研究方向：计算机图形学，虚拟现实。