基于自适应特征分布更新的压缩跟踪算法

冷建伟,李 鹏

(1.天津市复杂系统控制理论及应用重点实验室,天津 300384; 2.天津理工大学 自动化学院,天津 300384)

0 概述

基于视频的目标跟踪是机器视觉应用的关键,也是计算机学科的一个重要分支[1]。近年来有较多研究成果,文献[2]结合MeanShift和目标颜色直方图实现了对目标的有效跟踪,但该算法对颜色变化敏感,当目标受到光照或者目标本身颜色发生变化时,容易丢失目标;文献[3]提出的CamShift算法,在目标颜色变化时仍可以有效跟踪目标,而且能够自适应调整跟踪区域,提高跟踪精度,当目标与背景颜色区别较大时具有良好的跟踪效果,但当目标与背景颜色相近时,容易发生跟踪漂移;基于Kalman滤波[4]的跟踪算法是一种最优化自回归数据处理算法,即在视频中寻找与目标最相近的物体,该算法可很好地预测线性系统中的目标,但如果模型是非线性的,跟踪将会失败;基于粒子滤波[5]的跟踪算法对非线性模型也有很好的跟踪效果,但容易受粒子退化现象影响。

目前,基于检测的跟踪技术由于其实时性好、跟踪准确性高且具有一定的抗遮挡能力而得到大量应用[6]。这类算法通过分类器在线判别视频中的目标类和背景类实现跟踪。文献[7]将压缩感知理论与朴素贝叶斯分类器相结合,提出实时压缩跟踪(Compressive Tracking,CT)算法,实现对目标的快速稳定跟踪,但该算法自身也存在一定的缺陷:压缩特征在正负类中的分布使用固定学习率进行更新,无法体现真实分布,影响跟踪准确性和抗遮挡能力;目标跟踪窗口无法随目标尺寸变化而调整,使跟踪窗口不能很好地包围目标物体,影响样本采集,降低跟踪鲁棒性。为提高CT算法性能,很多专家和学者提出了改进措施[8-12],但都没有解决特征分布更新问题。

针对原始CT算法的不足,本文提出一种自适应更新特征分布的CT算法。该算法使用相邻两帧特征分布重叠度代替固定学习率更新特征分布,使特征分布学习率可根据每帧内目标变化自动调节。同时,为了避免遮挡物被误认为是跟踪目标,在更新正类特征分布时设定更新阈值。在跟踪过程中,根据目标变化实时调整跟踪窗口,减少采样过程中的误差,使跟踪更准确、鲁棒性更强。

1 CT算法

1.1 基于压缩感知的特征提取

由压缩感知理论可知,CT算法通过使用满足RIP(Restricted Isometry Property)条件的随机测量矩阵[13]实现对稀疏图像的多尺度降维,降维过程如图1所示。

图1 稀疏图像多尺度降维过程

为了实现多尺度降维,将每个样本与一组多尺度矩形滤波器{h(1,1),h(1,2),…,h(w,h)}进行卷积运算,矩形滤波器的定义如下:

(1)

其中,1≤x≤w和1≤y≤h分别为矩形滤波器的宽度和高度。

满足RIP条件的测量矩阵较多,其中最常见的是随机高斯矩阵,很多跟踪算法使用这种测量矩阵降维,但是随机高斯矩阵比较密集,当维数较低时对跟踪实时性不会有影响,当维数较高时,计算时间会增加,不利于实时跟踪,所以,CT算法采用一种非常稀疏矩阵,其生成规则如下:

(2)

1.2 基于朴素贝叶斯分类器的目标检测

(3)

其中,y∈{0,1}为样本标记,y=1表示样本为目标,y=0表示样本为背景。

由文献[14]可知,经稀疏矩阵得到的压缩特征满足高斯分布,因此,假设H(v)中的条件概率P(vi|y=1)和P(vi|y=0)都服从高斯分布,即:

(4)

(5)

(6)

(7)

其中,λ>0为学习率。

2 自动调节特征分布学习率的CT算法

2.1 自适应特征分布更新

由1.2节可知压缩特征服从高斯分布,而朴素贝叶斯分类器利用正负类特征服从高斯分布的不同区分目标和背景。在一组样本集中,正负类样本特征分布差异越大,分类器就越容易判别目标和背景。本文采用巴氏(Bhattacharyya)系数[15]度量2个分布之间的差异,对于连续分布,其表达式为:

(8)

其中,p(x)和q(x)是2个样本,B∈[0,1]表示巴氏系数,巴氏系数可用来比较2个样本的相似度。

如图2所示,随着样本正负类分布差异逐渐增大,B值逐渐减小。

图2 B值与特征分布关系

由式(3)可以看出,所有特征在正负类中分布概率密度比值的对数相加构成了贝叶斯分类器,所以,贝叶斯分类器的更新对应特征在正负类中分布的更新[16]。而在CT算法中,特征分布更新存在2点不足:1)跟踪过程中始终使用固定学习率更新特征分布。由于目标所在环境或者目标本身的变化,同一特征在相邻两帧之间分布必然不同,如果此时仍使用固定学习率更新特征分布,将无法反映特征真实分布。2)对正类的所有特征分布都更新。CT算法考虑到了遮挡的影响,但只对小部分遮挡有效,当目标大部分或者完全被遮挡时,如果仍然更新正类特征分布,下一帧跟踪的目标往往会被误认为是遮挡物,跟踪窗口也会随着遮挡物移动而偏离真实目标。

为了克服以上不足,本文使用两帧之间特征分布重叠度Bi(第i帧与前一帧特征分布重叠度)代替固定学习率。为防止被污染的特征用于特征分布更新,对正类更新设定一个阈值K,只有当两帧目标具有一定相似度(Bi>K)时才更新正类特征分布,当Bi

(9)

(10)

通过使用两帧之间特征分布重叠度作为学习率更新特征分布,可有效利用对分类贡献大的特征,分类器参数更新更加准确。对正类更新设定阈值,可有效避免遮挡所导致的跟踪漂移和跟踪失败,当目标再次出现时,也可以重新定位目标。

2.2 跟踪窗口尺度更新

CT算法没有解决跟踪窗口尺寸问题,即目标窗口不会随目标尺度变化而做出相应的改变。如果跟踪过程中跟踪窗口始终保持初始状态,则当目标靠近摄像机时,目标在跟踪窗口中变大,影响负样本采集;当目标远离摄像机时,目标在跟踪窗口中变小,影响正样本采集。样本误差的积累会对分类器造成影响,使跟踪出现误差。为了避免采集样本带来的误差,本文利用相邻两帧目标改进的SIFT特征点之间的关系实时更新跟踪窗口,减少采集误差,提高跟踪准确性和鲁棒性。

2.2.1 改进的SIFT特征

与同类算子相比,SIFI算子具有良好的检测和匹配性能[17],因此,本文利用前后帧目标SIFT特征点对应的关系实现跟踪窗口尺度的更新,但传统的SIFT算法存在以下缺陷:1)传统SIFT算法使用关键点周围16像素×16像素矩形区域采样,使两幅图像对应区域发生旋转变化后,会有一部分区域不重叠,如图3中的灰色区域所示。因此,在实际提取SIFI特征时会采用比采样区域大一些的矩形区域进行旋转,取其落在采样区域的像素来构建描述符,这种改进虽然降低了传统SIFT算法的采样误差,但增加了旋转操作的像素,使运行时间变长,且在进行灰度插值和重采样时有可能带来更多的误差。2)传统的SIFT特征为了保证特征描述的旋转不变性,每个关键点都会生成128维特征向量,数据量大,不利于加快匹配速度。

图3 矩形区域描述符采样误差

因此,本文不使用传统矩形区域分割的SIFT特征描述符,而是采用一种扇形区域分割的SIFT特征描述符(所包含像素与原SIFT方法相同)[18],如图4所示。与矩形区域采样相比,扇形区域采样可保证对应区域旋转前后所覆盖像素的一致性,无论区域如何旋转,都不会出现不重叠区域,且每个关键点只会形成8×8维特征向量。

图4 扇形区域分割的特征描述符

本文利用目标变化前后匹配的SIFT特征点自适应调整跟踪窗口,在保证目标正确匹配的同时还要求匹配速度尽可能快,下面将在匹配成功率和匹配时间2个方面对矩形区域和扇形区域描述符进行比较,以选择合适的描述符构建特征点。匹配成功率为图像变化前后匹配的特征点个数与图像变化前特征点个数的比值,匹配时间为图像变化前后所有可匹配特征点完成匹配所用的时间。在测试过程中,采用5类具有代表性的图像进行实验,测试结果为20次实验的平均值,如表1所示(表中“性能提升”指扇形区域描述符相对矩形区域描述符的性能提升百分比)。由表1可知,在具有平移、模糊和亮度变化的图像进行匹配时,2种描述符的匹配成功率相当;在具有旋转或视角变化的图像进行匹配时,由于扇形区域描述符使用扇区分割圆形区域,消除了矩形区域旋转带来的误差,增强了描述符抗旋转能力,匹配的成功率明显高于矩形区域描述符。在匹配时间方面,构建扇形区域描述符时不需要对特征区域进行旋转操作,加快了运行速度,另外,扇形区域描述符把128维的特征向量降至64维,也加快了匹配速度,使匹配效率更高。

表1 特征描述符性能对比

综上所述,本文将使用抗旋转能力更强、运行速度更快的改进的SIFT特征构建特征点,以达到提高跟踪准确性和实时性的目的。

2.2.2 尺度更新过程

本文利用相邻两帧目标的仿射变换参数更新跟踪窗口。前后两帧目标的仿射变换关系如式(11)所示。

It=H×It-1

(11)

其中,It表示当前帧目标图像,It-1表示前一帧目标图像,H为3×3仿射变换矩阵,H可以表示为如下形式:

(12)

其中,ρ是尺度因子,θ是旋转角度,(tx,ty)是平移向量。

从上述公式可知,未知参数有4个,所以,至少要存在4组匹配的特征点才能计算得出仿射参数,而改进的SIFI特征可以提供多组(大于4)匹配特征。

跟踪窗口更新的步骤如下:

1)提取初始帧目标改进的SIFT特征点。

2)随机筛选特征点,得到固定数目(大于4)的特征点作为特征点库。

3)从第二帧开始,提取当前帧目标改进的SIFT特征点并与特征点库中的特征点进行匹配,得到一定数量(大于4)的特征匹配组。

4)利用匹配的特征点之间的关系求解仿射变换参数,更新跟踪窗口。

5)根据当前帧目标,更新特征点库。

通过以上方式,获得前后两帧目标的仿射变换参数,实时调整跟踪窗口尺度,防止目标变化影响样本采集,使跟踪准确性和鲁棒性更高。

2.3 算法流程

算法自适应更新特征分布

输入t-1帧目标位置和尺度

输出当前帧目标位置,更新后的分类器参数和跟踪窗口

1)根据目标t-1帧位置和跟踪窗口尺度,分别采集正负样本图像集合Dα={z‖l(z)-lt-1‖<α}和Dζ,β={z|ζ<‖l(z)-lt-1‖<β},其中lt-1是上一帧(t-1帧)的跟踪位置,且α<ζ<β。

2)计算正负样本的多尺度特征,使用非常稀疏矩阵对特征投影得到压缩域特征。

3)计算各个压缩特征在正负类中的特征分布,根据式(8)～式(10)更新特征分布。

4)使用朴素贝叶斯分类器对每个特征向量v分类,找到目标跟踪位置lt。

5)根据目标变化,实时调整跟踪窗口大小和位置。

3 实验结果与分析

为了验证本文算法性能,将本文算法与CT和FCT(Fast Compressive Tracking)算法对4个包含快速移动、明暗变化、遮挡等干扰因素的标准测试序列进行对比。测试所用台式机配置为Windows 7 操作系统,Inter Core i5处理器,2.53 GHz主频,4 GB内存,所使用开放软件为VS2013,装载OpenCV2.4.9图像处理库。

3.1 实验参数设置

在实验过程中,阈值K和特征点库中特征点数目的设定会影响实验效果,因此,先分析这2个参数对跟踪精度的影响,然后取对跟踪精度影响最小的数据作为实验参数。阈值K(0.5～1.0)对跟踪精度影响结果为4个公共测试序列20次实验的平均值,如图5所示。

图5 阈值对跟踪精度的影响

由图5可知,当K<0.75时,相邻两帧目标特征分布重叠度较低,一些被污染的样本也会用于更新特征分布,容易导致跟踪漂移,中心位置误差较高;当0.750.9时,相邻两帧目标特征分布重叠度较高,导致新提取的特征无法用于更新特征分布,跟踪准确性下降,中心位置误差变高。通过实验可知,当0.8

为了保证算法实时性,特征点库中特征点数目不易过多,本文设定特征点库中特征点数目为20,并从匹配的特征点中选取6组用于求解目标仿射变换参数。

3.2 实验结果

如图6所示,在序列walking中,目标在移动过程中存在一定的姿态变化,但光照、背景和遮挡等因素影响较小,3种算法都能实现有效跟踪。当目标出现大幅度旋转时,如图中第254帧,CT和FCT算法跟踪准确性会降低,而本文算法能准确定位目标位置,提高了跟踪准确性。

如图7所示,在序列face中,目标光照变化明显,给跟踪带来了困难。由图中第673帧、第1 183帧、第1 265帧可以看出,当目标亮度发生明显变化时,CT和FCT算法由于使用固定学习率更新特征分布,导致跟踪发生漂移,而本文算法根据目标在相邻两帧之间的变化自适应调节特征分布,始终能对目标进行有效跟踪。

如图8所示,在序列car中目标存在尺度变化、光照变化和部分遮挡等干扰因素。由图中第15帧、第52帧、第76帧可以看出,随着目标尺度的不断减小,CT和FCT算法出现了不同程度的跟踪漂移,而本文算法始终对目标进行着准确跟踪。可以看出本文算法在目标尺度发生变化时,能自适应调整跟踪窗口,防止跟踪漂移,提高了跟踪鲁棒性。

如图9所示,在序列fist中,目标出现了大面积遮挡现象,对跟踪造成了很大干扰。从图中可以看出,当目标出现大面积遮挡时,如第54帧,这时3种算法都无法定位目标;当目标持续移动,遮挡物随之消失时,如第125帧、第1 134帧,CT和FCT算法将遮挡物误认为目标,导致跟踪失败,而本文算法能重新定位目标,并持续跟踪。由此可知,本文算法所采用的特征分布更新策略克服了大面积遮挡的影响,使跟踪获得较好效果。

图6 序列walking实验结果

图7 序列face实验结果

图8 序列car实验结果

图9 序列fist实验结果

各算法处理时间如表2所示,因为本文算法采用改进的SIFT特征来调整跟踪窗口,所以在实时性上比FCT算法要差,但与CT算法相差不多,可实现实时跟踪。

表2 算法处理时间 (ms·frame-1)

4 结束语

本文提出一种自适应更新特征分布的CT算法。针对特征分布更新问题,使用相邻两帧特征分布的重叠度代替固定学习率更新特征分布,并对正类特征分布的更新设定阈值。对于跟踪过程中跟踪窗口无法实时更新的问题,提取相邻两帧目标改进的SIFT特征点进行匹配,根据匹配的特征点之间的关系得到目标的仿射变换参数,最后由仿射变换参数更新跟踪窗口。实验结果表明,本文算法对跟踪过程中的光线突变、尺度变化、大面积遮挡等因素具有较好的抗干扰能力,跟踪窗口可随目标变化实时改变,跟踪准确性高、鲁棒性好,能够实现实时跟踪。但由于本文算法使用改进的SIFT特征来解决跟踪窗口更新问题,使算法处理速度有所下降,因此下一步将重点研究如何加快处理速度。

[1] 闫庆森,李临生,徐晓峰,等.视频跟踪算法研究综述[J].计算机科学,2013,40(6A):204-209.

[2] COMANICIU D,RAMESH V,MEER P.Kernel-based Objects Tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(5):564-577.

[3] BRADSKI G R.Real Time Face and Object Tracking as a Component of a Perceptual User interface[C]//Proceedings of the 4th IEEE Workshop on Applications of Computer Vision.Washington D.C.,USA:IEEE Press,1998:214-219.

[4] HUANG S L,HONG J X.Moving Object Tracking System Based on Camshift and Kalman Filter[C]//Proceedings of the 2011 International Conference on Consumer Electronics,Communications and Networks.Washington D.C.,USA:IEEE Press,2011:1423-1426.

[5] VADAKKEPAT P,LIU J.Improved Particle Filter in Eensor Fusion for Tracking Randomly Moving Object[J].IEEE Transactions on Instrumentation and Measurement,2006,55(5):1823-1832.

[6] AVIDAN S.Support Vector Tracking[J].IEEE Tran-sactions on Pattern Analysis and Machine Intelligence,2004,26(8):1064-1072.

[7] ZHANG K H,ZHANG L,YANG M H.Real-time Compressive Tracking[C]//Proceedings of 2012 European Conference on Computer Vision.New York,USA:ACM Press,2012:864-877.

[8] 王 权,刘侍刚,彭亚丽,等.基于SIFT的压缩跟踪算法[J].现代电子技术,2014(15):62-64.

[9] 钟 权,周 进,崔雄文.融合SIFT特征的压缩跟踪算法[J].光电工程,2015,42(2):66-72.

[10] 朱周元,张 超,吴小培,等.尺度自适应的压缩跟踪算法[J].计算机工程与应用,2013,52(14):180-185.

[11] 李庆斌,朱国庆,周 妍,等.基于特征在线选择的目标压缩跟踪算法[J].自动化学报,2015,41(11):1961-1970.

[12] 景 静,徐光柱,雷帮军,等.一种基于压缩域的实时跟踪改进算法[J].计算机工程,2014,40(4):170-174.

[13] ACHLIOPTAS D.Database-friendly Random Projections:Johnson-linden Stratus with Binary Coins[J].Journal of Computer and System Sciences,2003,66(4):671-687.

[14] DIACONIS P,FREEDMAN D.Asymptotics of Graphical Projection Pursuit[J].Annals of Statistics,1984,12(3):793-815.

[15] COMANICIU D,RAMESH V,MEER P.Real-time Tracking of Non-rigid Objects Using Mean Shift[C]//Proceedings of 2000 IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2000:142-149.

[16] 耿 磊,王学斌,肖志涛,等.结合特征筛选与二次定位的快速压缩跟踪算法[J].自动化学报,2016,42(9):1421-1431.

[17] 王永明,王贵锦.图像局部不变性特征与描述[M].北京:国防工业出版社,2010.

[18] 曾 峦,顾大龙.一种基于扇形区域分割的SIFT特征描述符[J].自动化学报,2012,38(9):1513-1519.