一种基于稀疏表达和光流的目标跟踪方法

牛一捷

(大连交通大学 软件学院，辽宁 大连 116028)*

0 引言

随着计算机技术的高速发展，计算机视觉研究领域受到了越来越多研究者的关注.目标跟踪是其中备受关注的前沿方向，在人机交互、安全监控、虚拟现实、医学、体育等方面都有广泛应用.虽然已经取得了一些进展，但到目前为止还没有一个通用算法适用于所有问题.这是因为目标跟踪问题受到多种因素影响，如:内在因素包括目标物体位置、形状和尺度的变化等;外在因素包括光照变化，摄像机运动及视角转换，遮挡、复杂背景等.

传统的经典目标跟踪方法有:光流法［1］、meanshift、kalman、粒子滤波.这些算法的准确率较低，表现为跟踪目标易发生漂移并很快中断跟踪任务.近年来，随着模式识别技术的发展，研究人员开始将跟踪问题看成目标检测、目标识别等模式识别问题，提出了很多算法，其中最具有代表性的有:Online Adaboost［2］，BeSemiT［3］，TLD［4］等.这类方法在实际应用中跟踪的准确率较高，但是需要提前学习并且在新的一帧到来时需要进行大量的识别操作，对于对实时性要求比较高的跟踪问题来说是一个瓶颈问题.

本文鉴于上面两类算法的优缺点，提出一种光流算法和稀疏表达技术相结合的新算法(SROF).不仅能够较好的避免发生漂移和跟踪任务突然中断问题，而且算法的准确性也得到了很大的提高.

1 传统光流算法

光流的概念是Gibson在1950年首先提出来的.后来将光流法应用于跟踪问题，即利用图像像素点在时间域上的变化以及相邻帧之间的相关性来进而推断出跟踪目标在新一帧速度及方向的方法.根据选取像素点的数量，分为稠密光流和稀疏光流.稠密光流是图像中的每个像素点均参与运算，计算开销较大.稀疏光流仅由一组选定的像素点参与运算，因此在实际应用中较多地使用稀疏光流法.目前应用广泛的是 Bruce D.Lucas和Takeo Kanade在1981年提出的 Lucas-Kanade(LK)算法［1］，本文也基于这个算法.本算法基于三点假设.

(1)亮度恒定，像素在帧间运动时，像素值保持不变:

(2)图像的变化相对于时间的变化微小，对图像约束方程使用泰勒公式展开，可以得到:

这个方程中，Ix，Iy是二维图像的偏导数，It是图像随时间的导数，u和v是所要求的速度在x，y方向分量，但目前对于单个像素，无解，于是有了第三个假设.

2 稀疏表达技术

稀疏表达技术是用比香农定律更低的采样率来表示和压缩信号.Mei，X.and H.Ling等将其引入到视频目标跟踪这一领域中［9-11］.

稀疏表达的核心理论可以理解为在一组过完备基A∈Rd×n(使用n维传感器经d次观测得到的某个信号的观测值)下，重构某个信号y.稀疏表达要求对信号y∈Rd的重构系数向量x∈Rn尽可能地稀疏，转化为如下最小化问题:

但上述I0－范数最小化问题是NP-hard问题，计算率极低.Tao等人在式(5)基础上证明了:在满足约束等距性(restricted isometry property，RIP)条件下，如下的I1－范数最小化问题是式(5)的I0－范数最小化问题的最紧表示［10］:

这是一个凸优化问题，其求解效率要比式(5)高得多.再引入观测噪声，上述最优化问题可以松弛化表示为:

对于上述最优化问题，有许多方法能够有效地求解，包括贪婪算法、L1最小化、LASSO，本文利用LASSO算法.

3 仿射变换区域的生成

4 SROF算法

SROF算法的基本思路是:将目标跟踪任务分为两阶段:粗略定位和精确定位.第一阶段粗略定位，主体思想为光流算法.第二阶段精确定位，主体思想为模式识别思想.具体的算法流程如下:

(1)初始化

(a)在视频的第一帧中初始化跟踪目标，并提取正负样本;

(b)用颜色特征表示正负样本，利用稀疏表达技术提取原始目标关键特征.

(2)实时追踪

for T=2，3，… ，t(t为视频序列总帧数)

①粗略定位:

(a)联合 Harris和FAST算法检测出的特征点和等间距像素点组成光流算法像素点集O.

(b)采用后向跟踪－形心配准的方法，为跟踪目标在新一帧中计算粗略定位区域.

②准确定位:

(a)对粗略定位区域根据仿射变换法建立一组目标候选区域.

(b)用颜色特征表示每个候选区域，利用稀疏表达技术计算每个候选区域与初始目标的正负样本的相似度比率，最终确定目标的准确位置.

该算法关键技术分析:

(1)光流算法特征点选定

在稀疏光流算法中像素点的选取很重要，通常的算法是选取跟踪目标区域内的等间隔像素点集.这样选取的像素点不能代表跟踪目标的特点.本文在等间隔选取像素点的基础上添加上角点.角点是图像亮度发生剧烈变化或图像边缘曲线上曲率最大值的点.常用的角点检测方法有:Moravec、Harris［5］，SUSAN，FAST［6］，SIFT 等.

本文选择经典的Harris和FAST来共同完成光流特征点的选定.FAST角点检测算法是目前为止速度最快的角点选取算法.FAST算法原理:检测候选特征点周围一圈的像素值，如果候选点周围领域内有足够多的像素点与该候选点的灰度值差别够大，则认为该候选点为一个特征点.Harris角点检测算法是 Moravec角点检测算子的扩展.它的基本原理:当一个窗口在图像上移动，在平滑区域，窗口在各个方向上没有变化.窗口在边缘的方向上没有变化.但在角点处，窗口在各个方向上具有变化.Harris角点检测正是利用了这个直观的物理现象，通过窗口在各个方向上的变化程度，决定是否为角点.

(2)粗略定位

传统光流法的前提假设条件过多不适于实际的目标跟踪算法.具体的表现就是跟踪的准确性不高，在跟踪目标的过程中很快就会出现目标丢失的现象，而且无法重新找回跟踪目标，整个跟踪过程失败.因此，为了提高算法的准确性，采用后向跟踪－形心配准的方法［7］.具体算法:用(1)中产生的联合特征点集O应用到光流算法，之后得到在下一帧中对应的一组像素点集M.采用相同的光流方法，前后两帧对调，在上一帧中找到点集M对应的点集Q.计算O点集和Q点集对应点的欧式距离，把距离大于点集M，Q中所有对应两点之间平均距离的点舍弃.利用剩余点前后帧之间的位置偏移来计算跟踪目标的所在位置.

(3)原始跟踪目标关键特征提取

第一阶段已经得到了跟踪目标的粗略位置，接下来要应用模式识别的思想，对跟踪目标进行精确定位.首先要根据原始跟踪目标选取正负样本.为了考虑到跟踪目标可能的变化，对初始跟踪目标区域(图1(a)中间方框)，根据3中仿射变换方法建立正样本Np.选取跟踪目标区域外围有部分重叠的部分(图1(b)沿着大方框边缘，移动红色方框一圈，且红色方框和中间的目标方框相同大小)建立负样本.正负样本Nn记录了初始跟踪目标特征.负样本记录了背景特征.

图1 正负样本选取示意图

正负样本都用颜色直方图表示.颜色特征是一种全局特征，即以整个图像为单位提取的特征，如:颜色、纹理等.本文使用颜色直方图，它是不同色彩在整幅图像中所占的比例.对于RGB图像在每个通道上，共有256个取值，那么一副图像就共有256×3个取值.一个样本表示为一个列向量，列向量为768×1.但是这些取值中存在大量的冗余信息，这些冗余信息会干扰到目标的正确识别.通常可以采用降维的方法进行处理，如PCA或稀疏表达.本文采用稀疏表达方法来提取关键特征维.

根据2的理论分析，将稀疏表示问题可描述为如下LASSO最小化问题:

(4)精确定位

对粗略定位区域利用3中的仿射变换技术建立一组候选区域，由于候选区域越多算法准确率越高，但算法效率将受到影响.本文的策略是当上一帧置信度比较小时，本次仿射候选区域成倍增加，以便获得更好的跟踪区域，提高算法准确率.再次利用稀疏表达方法，完成精确定位.对于每一个候选区域同样用768维的颜色直方图表示，所有候选区域组成矩阵P.用(3)得到的x，对P进行简化，y=Px.接着对(3)中A矩阵简化，即A=Ax.将简化后的y，A代入式(9).利用 LASSO计算新的，此处的表示每个候选样本可以由A中正负样本中的哪些关键样本表示.

最后根据x'，计算每个候选样本的关键样本表示中正负样本所在比例来最终确定哪个候选样本为最终跟踪目标.具体计算公式为式(10)～(12)这里的Ap，An分别表示A中对应正负样本子集，x'p，x'n，分别表示对应正负样本子集的那部分元素子集.recP，recN表示计算每一个候选区域如果只用正样本和负样本表示的误差，最后用式(12)计算出每个候选样本和正负样本之间的误差比率，选取值最大的那个候选区域为最终跟踪目标区域，r的经验值取0.4.

5 实验结果

本文实验环境为:CPU:Intel(R)Core(TM)i3-2350M 2.30GHz，内存:2GB，显存 512MB，操作系统为win7，仿真软件为Matlab(R2012b).

使用faceocc2数据集，这个数据集中包含了严重遮挡、目标物体位置、形状和尺度的变化等在实际目标跟踪过程中常遇到的难题.数据集中图像大小为320×240，共819帧.

为了比较，在faceocc2数据集上除了运行本文算法SROF外，还运行了三个目前最具代表性的算法:BoostT、BeSemiT和TLD.

测试参数的选定:算法初始化时，选取正样本Np为50个，负样本Nn为200个.精确定位中，仿射候选样本的选定，本文选定置信度大于0.9，选取100个候选区域，0.9～0.8之间，选定 200个候选区域，其他选定300个候选区域.式(9)用于生成原始跟踪目标关键特征时，λ=0.001.式(9)用于精确定位时，λ=0.01.本文具体数值的选定皆是经验值.

图2是BoosterT、BeSemiT、SROF四个算法的跟踪结果对比图.图3是中心位置误差对比图，通过计算每一帧手工标定的实际目标中心点坐标和四个算法在每一帧的跟踪结果中心点坐标之间的欧式距离得到该图.

图2 跟踪结果对比图

根据图2，对实验结果分析如下:

当目标发生部分遮挡时，如165帧，当目标位置发生变化时，如399帧，除了BeSemiT发生了严重偏移，其余三个算法都定位出目标.当目标的形状和尺度的变化时，如588帧，BeSemiT和TLD都跟丢，BoostT的跟踪结果都发生了严重偏移，当跟踪目标被完全遮挡时，如709帧，BeSemiT和TLD都跟丢，BoostT发生了严重偏移.本文算法在整个跟踪过程中都能较准确的跟踪目标，尤是当目标完全遮挡的情下还能较为准确的标定目标位置，如709帧，但是对于复杂运动，如429帧，当目标连续出现偏移之后又发生遮挡的情况，本文的算法也出现了偏移，需要进行改进，另外，在429帧，只有BoostT取得了较好的跟踪效果.根据图3，可以发现本文SROF算法在整个跟踪过程中稳定地保持着较高的准确性.

图3 中心位置误差对比图

6 结论

本文实现了一个新的目标跟踪算法.在整个算法框架上，本文将传统光流跟踪算法和模式识别思想相结合，采用两阶段跟踪目标定位的思路，最终确定出准确的目标跟踪区域.在目标区域的表示上，本文用到了全局颜色特征和局部角点特征，从不同角度描述目标，提高了算法的准确率.最重要的是将近年来较为流行的稀疏表达技术应用到了算法中，不仅用以清除目标表示的冗余信息，而且用于最终在一组候选样本中识别出最为准确的目标跟踪区域.虽然经实验证明本算法和目前较为流行的算法性能相当，甚至在有些情况下优于这些算法.但本文在一些环境条件下，准确率较低，还需要针对这些情况，提高算法的适应性和准确性.

［1］Lucas B D，Kanade T.An iterative image registration technique with an application to stereo vision［C］//IJCAI，1981，81:674-679.

［2］Grabner H，Bischof H.On-line boosting and vision［C］//Computer Vision and Pattern Recognition，2006 IEEE Computer Society Conference on IEEE，2006，1:260-267.

［3］Stalder S，Grabner H，Van Gool L.Beyond semi-supervised tracking:Tracking should be as simple as detection，but not simpler than recognition［C］//Computer Vision Workshops(ICCV Workshops)，2009 IEEE 12th International Conference on IEEE，2009:1409-1416.

［4］Kalal Z，Mikolajczyk K，Matas J.Forward-backward error:Automatic detection of tracking failures［C］//Pattern Recognition(ICPR)，2010 20th International Conference on IEEE，2010:2756-2759.

［5］Harris C，Stephens M.A combined corner and edge detector［C］//Alvey vision conference，1988，15:50.

［6］Rosten E，Drummond T.Machine learning for highspeed corner detection［C］//Computer Vision– ECCV 2006.Springer Berlin Heidelberg，2006:430-443.

［7］彭宁嵩.Mean—shift可视跟踪中的稳健性研究［D］.上海:上海交通大学，2005.

［8］Ross D A，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77(1-3):125-141.

［9］Mei X，Ling H.Robust visual tracking using minimization［C］//Computer Vision，2009 IEEE 12th International Conference on IEEE，2009:1436-1443.

［10］Candès E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.Information Theory，IEEE Transactions on，2006，52(2):489-509.

［11］Zhong W，Lu H，Yang M H.Robust object tracking via sparsity-based collaborative model［C］//Computer Vision and Pattern Recognition(CVPR)，2012 IEEE Conference on IEEE，2012:1838-1845.