利用二值描述符的实时目标跟踪算法

覃 兵,田 军,查宇飞,张立朝,黄宏图

(空军工程大学航空航天工程学院,陕西西安 710038)

利用二值描述符的实时目标跟踪算法

覃 兵,田 军,查宇飞,张立朝,黄宏图

(空军工程大学航空航天工程学院,陕西西安 710038)

针对目标跟踪过程中的速率低和存储量大的问题,提出了一种新的利用二值描述符特征的快速稳定的目标跟踪算法.该算法首先在保持目标结构信息的情况下,通过寻找最优正交矩阵对样本进行旋转聚类,将样本从欧式空间投影到汉明空间,生成二值描述符.然后在粒子滤波采样的框架下,通过计算目标与候选样本的汉明距离确定目标跟踪位置.实验结果表明,当发生光照、姿态变化和快速移动时,该算法跟踪速度较快,并且能够实现稳定跟踪.

目标跟踪;二值描述符;粒子滤波;汉明距离

如何利用特征描述符高效地建立目标的表示模型,是实现以目标检测、跟踪与识别为基础的视觉任务系统的关键问题[1-4].在特征描述符发展初期,研究人员注重提高描述符的区分度,为获得较高区分度的描述符,用一组实数向量对目标的各个关键点进行描述,称这种特征描述符为实值描述符.尺度不变特征转换(Scale Invariant Feature Transform,SIFT)特征[5]是实值描述符的典型代表,其对尺度、旋转以及一定视角和光照变化等图像的变化都具有不变性,并且SIFT具有很强的可区分性.但是,SIFT算法利用特征匹配的方法进行跟踪时,由于需要对整幅图片进行处理来提取特征,当图像尺寸较大时,处理速度比较慢,无法达到实时性要求.

为了提高描述符生成和匹配的速度以及减小描述符所占存储空间,产生了二值描述符[6].这类特征描述符用一组二值向量对目标进行描述,一般采用逻辑比较或者线性投影的方法生成,而匹配过程则用易于计算的汉明距离作为相似性度量.因此,这类特征描述符不仅所占存储空间小,而且匹配速度快.

文献[7]提出鲁棒且独立的二进制基本特征(Binary Robust Independent Elementary Features, BRIEF)二值描述符.它由128或256或512对比较组成,采样点是按照中心位于特征位置的等方差高斯分布随机选取的.BRIEF的计算量和存储量低,但不具有尺度不变性和旋转不变性.文献[8]提出定向二进制特征(ORiented Brief,ORB)描述符,它解决了BRIEF缺少旋转不变性的问题,并通过使用亮度质心ORB计算局部的方向.2013年,文献[9]提出关键点二进制特征(BinBoost),设计了一个比较大的局部区域的二值描述符,通过构造二值哈希代价函数,利用推进方法(Boosting)获得弱分类器集合及其权值,寻找最优的二值描述符.但是,上述算法都没有考虑目标的整体结构信息,从而不能保持原来特征描述符在欧式空间的结构性.

基于以上考虑,笔者运用一种新的二值描述符生成算法,通过迭代量化的方法寻找最优正交矩阵对目标进行旋转聚类,得到保持目标结构信息的哈希变换;将目标从欧式空间投影到汉明空间,且投影后的数据与欧式空间中的数据的相关性最大;降低了特征描述符的存储空间,实现了快速匹配,充分利用速度和存储优势扩大了探索空间,提高了精度.

1 二值描述符的生成

新的二值描述符生成算法借鉴了文献[10]的想法,通过迭代量化的方法寻找到最优的正交矩阵,将相似的样本聚为一类,从而生成相同的二值描述符.该方法称为迭代量化(ITerative Quantization,ITQ).

1.1 二值描述符的生成原理

如图1所示,图中每个点代表着一个样本,假设这些样本是通过主成分分析(Principal Component Analysis,PCA)降到二维后的显示结果.当对这些样本进行二值量化时,由图1(a)可知,相似的样本可能会量化到不同的二值描述符.如图1(b)所示,通过样本数据与一个随机正交矩阵相乘可以使样本发生一定的旋转.因此,存在最优的正交矩阵,使得相似的样本旋转聚为一类,得到同样的二值描述符,如图1(c)所示.为此,文中将根据此想法生成目标的二值描述符,并运用到目标跟踪中,充分发挥其准确性和有效性,将目标从欧式空间投影到汉明空间,保证投影后的数据与欧式空间中的数据的相关性最大.

图1 样本二值量化效果示意图

1.2 二值描述符的生成方法

设有n个图像样本,每个样本图像维度为a×b,将每个图像样本数据作为一行,得到n个样本对应的矩阵Xn×d,其中,n为样本个数,d为每个样本的维数,即d=a×b.要保证n个样本的均值为0,即通过量化得到样本的二值矩阵B∈{-1,1}n×k,其中,k为降维的维数.

首先,需要对上述n个样本减少特征数,避免过度拟合,并最终降低存储量.运用主成分分析(Principal Component Analysis,PCA)[11]的方法对样本数据进行降维,设降维后样本数据为Xn×k.

接下来,引入k×k维正交矩阵R,对Xn×k进行正交转换,使得降维数据量化后的误差最小,即

初始化随机正交矩阵R,采用类似k均值[12]迭代量化方法寻找最小误差.在每次迭代过程中,每个样本通过符号函数的方法赋予二值矩阵B,然后更新正交矩阵R,不断地使公式量化误差最小,交替进行的步骤如下:

(1)固定R,更新B.根据式(1),得到

(2)固定B,更新R[10].对k×k矩阵BTV进行奇异值分解,即

其中,SVD代表奇异值分解.接着,得到正交矩阵

交替地更新B和R,是为了寻找最优的正交矩阵,从而使得量化的误差越小.图2显示了随着迭代次数的增加,量化误差变化的过程.实验结果表明,只要迭代80次就可以使得量化误差趋于最小.

由以上步骤就能得到样本的二值描述符.相对于实值描述符,生成二值描述符的方法不仅存储量小,而且准确度高.

图2 不同的迭代次数得到的量化误差示意图

2 利用二值描述符的实时目标跟踪算法

基于上述新的二值描述符生成算法,文中的主要工作是将此新的方法运用到目标跟踪上,在粒子滤波采样框架下实现对目标的跟踪.粒子滤波算法[13]是由当前帧的跟踪结果在下一帧中得到对应的候选点,从而实现样本的概率分布随着时间的推移得到传递.

2.1 初始化

首先,在跟踪图像{Ii}i=1,2,…,N的第1帧I1中确定跟踪目标,并由上述新的二值描述符生成算法计算目标的二值描述符.文中采用的是矩形框表示目标,设目标的初始位置P1=[x,y,w,h,θ],其中,(x,y)为跟踪框的左上角坐标,(w,h)为跟踪框的宽度和高度,θ为跟踪框的旋转角度.由此,可得到初始帧的跟踪目标为

接着,生成目标的二值描述符.由上述新的二值描述符生成算法可知,单是由初始帧的跟踪目标是无法得到二值描述符的,因此,需要在目标初始位置P1附近高斯采样r个样本,其中,r值过大或过小都会导致采样的正负样本个数不均衡,会对计算最优正交矩阵R产生影响,从而使得正负样本无法映射得到不同的二值描述符,实验结果表明,取r=300时效果最佳.高斯采样参数Σ=[x′,y′,w′,h′,θ′],其中,(x′,y′)为跟踪框x方向和y方向的移动范围,(w′,h′)为跟踪框的宽度和高度的收缩范围,θ′为高斯采样的旋转角度.得到r个样本如下:

其中,ITQ代表利用节1.2的迭代量化方法求解,k为下降的维数,m为迭代量化时的循环次数.得到了新的矩阵的二值描述符B(1+r)×k,取其第1行,也就得到了初始目标的二值描述符,即

同时,也得到了对数据降维的特征向量U,以及迭代量化m次后得到的最优正交矩阵R.这两个参数将在接下来的跟踪过程中使用.

图3 利用二值描述符的实时目标跟踪示意图

2.2 跟踪过程

算法流程如图3所示.传统的跟踪算法由于其算法复杂度的影响,在采样空间上范围较小,如图3第t+1帧采样所示,这就可能会因目标的突然快速移动或姿态变化大而丢失目标.文中算法可以充分利用速度和存储优势,扩大搜索空间,增加候选采样个数,进而能够提高跟踪精度.由上文得到了当前跟踪目标的二值描述符,在下一帧中,通过粒子滤波的方法去采样来得到候选样本.设候选样本个数为n,因此,可得到n个候选样本为

其中,sampling表示采样.Ii为第i帧跟踪图像;Pi-1为第i-1帧跟踪位置;Wi为粒子滤波采样权值,并且设W2=Σ,即在第2帧时是通过高斯采样得到候选样本的.

得到了n个候选样本后,通过新的二值描述符的生成算法计算出每个候选样本的二值描述符.在此过程中,需要运用求初始目标二值描述符时得到的特征向量U和正交矩阵R,具体计算如下:

由此可以看出,目标跟踪过程中候选样本的二值描述符仅仅通过两次乘法运算就可以得到,算法实现的速度较快,达到了目标跟踪的实时性.

目标跟踪中粒子的似然概率是通过计算粒子与目标模型之间的相似度或距离得到的,文中利用二值描述符和汉明距离度量方法来求取粒子的似然概率.由上述可知,目标的二值描述符为B0,n个候选样本的二值描述符为Bn×k,则目标与候选样本之间的汉明距离为

在文中,目标在下一帧的最终状态由权重最大的粒子决定.所以,由Dn找出权重最大的粒子为

其中,Lindex表示权重最大的粒子位置,find表示找到权重最大的粒子.

2.3 更 新

在上述跟踪过程中,最终得到了权值最大的候选样本,进而可以得到此候选样本对应的位置,作为跟踪目标的位置更新可表示为

粒子滤波的核心思想是,用一组具有权值的粒子来完全表示后验概率分布,即每个粒子的权重完全正比于其本身的似然概率.因此,得到上述n个候选样本的权值为

其中,σ是观测噪声的标准方差.

最后,对目标的二值描述符进行更新,即

3 实验结果及分析

文中所有实验是在3.06 GHz,6 GB内存的64位计算机环境下,通过MATLAB 2013a软件平台仿真实现的.根据实验跟踪过程中的精确度和实时性考虑,样本数据降维的维数k=64,候选样本的个数n=500,高斯采样参数Σ=[10,10,0.1,0.1,0.2],所有的3个测试视频的参数及其描述如表1所示.

表1 视频序列及其描述

3.1 实验结果

为验证文中算法,在对大量视频序列进行跟踪仿真实验的基础上,对基于领域分配法的目标跟踪(Distribution Fields for Tracking,Track DF)[14]、基于鲁棒且独立二进制基本特征的目标跟踪(Binary Robust Independent Elementary Features,BRIEF)以及文中算法(Proposed)的实验结果和跟踪性能进行分析,比较算法各自的复杂度.

图4第1行是“Sylvester”部分结果.视频中,背景比较相似、目标玩具姿态和移动速度不停变化.BRIEF的跟踪结果与真实目标存在一定的位置偏差,尤其是目标发生姿态变化时,偏差也越大,如第596帧. Track DF能够适应一定程度的姿态变化,但当姿态变化较大并且快速移动时,其跟踪精度也随之降低,如第996帧;而文中算法能够至始至终对目标进行跟踪.

图4 “Sylvester”、“David”和“Dollar”跟踪结果示意图

图4第2行是“David”部分结果.对其头部跟踪,主要有姿态、旋转以及光照等变化,BRIEF的跟踪结果在目标侧身和取下眼镜时存在较大的偏差,如第176帧和第346帧;Track DF在目标取下眼镜时,也就是目标姿态发生较大变化时,丢失目标,如第346帧;文中算法虽然在目标侧身过后存在一定的误差,如第246帧,但偏差较小,能够实现准确跟踪.

图4第3行是“Dollar”部分结果.可以看出,3种算法基本都能对目标至始至终的跟踪.在目标产生折叠或者目标快速移动时,BRIEF产生的偏差相对于其他两个算法较大,如第96帧、第176帧和第296帧.

3.2 性能分析

文中对照实验所涉及的算法均按照原文献所介绍的思路编写,未进行任何形式的额外优化处理.下面对各算法的跟踪性能以及算法复杂度进行简要分析.

3.2.1 跟踪性能

中心位置误差[15]的计算表达式为

其中,O和Ot分别为算法得到的跟踪框中心位置和目标真实中心点,中心位置误差表示目标中心与真实目标中心的误差,其值越小,表明跟踪的精度越高.视频中每帧的中心位置误差如图5所示,其中横轴表示图像帧数,纵轴表示均方根误差.由图5可知,文中算法要比其他两种算法对目标有更准确的定位.

图5 3种算法跟踪结果的中心位置误差比较示意图

3.2.2 算法复杂度

Track DF算法首先对目标图像按照灰度值区间进行分层;然后,对分层后的图像分别进行空域和值域滤波,得到分布场特征;最后,用梯度下降法选取与目标图像分布场特征之间欧式距离最小的候选位置为目标的跟踪位置.因此,Track DF算法比BRIEF算法复杂,这里仅分析BRIEF算法与文中算法的复杂度.在BRIEF算法中,其构建二值描述符时,每个候选样本都要经过nd次逻辑比较以及nd次加减运算,因此,BRIEF算法处理每一帧的算法复杂度为O(Nnd2).文中算法的复杂度主要在于式(10),因此,文中算法处理每一帧的复杂度为O(Ndk).表2给出了各算法平均每帧的处理时间.综上可知,文中算法的处理速度最佳.

表2 3种算法的处理速度 s/帧

4 结束语

视觉跟踪中如何利用特征描述符高效地建立目标的表示模型,一直是研究的热点和难点.笔者通过对样本二值描述符生成算法的研究,将一种新的二值描述符生成算法与粒子滤波相结合,提出了利用二值描述符的实时目标跟踪算法.该算法通过迭代量化的方法寻找一个最优的正交矩阵,从而将样本的数据进行旋转聚类,使得相似的样本能够生成相似的二值描述符,寻找保持目标结构信息的哈希变换,使投影后的数据与欧式空间中的数据的相关性最大.并且文中充分利用速度和存储优势扩大探索空间,提高精度,因此新特征具有鲁棒性的特点.通过粒子滤波算法,运用异或运算计算汉明距离,得到下一帧目标的位置以及后验概率,提升了算法的速度和效率.将文中算法应用于视觉跟踪领域,在跟踪效果和跟踪速度上都比其他跟踪算法有所提高.

不足之处是,文中算法虽然在一定程度上解决了特征描述符表征特征的快速性和鲁棒性的问题,但是降维时的特征向量和量化时的正交矩阵未能实时更新,因此,对于复杂背景的目标跟踪效果仍不是十分理想.研究如何有效地在线更新特征向量以及正交矩阵,将大大增强文中算法的鲁棒性,这将是下一步的工作.

[1]Li Xi,Hu W M,Shen C H,et al.A Survey of Appearance Models in Visual Object Tracking[J].ACM Transactions on Intelligent Systems and Technology,2013,4(4):58-72.

[2]李远征,卢朝阳,李静.一种基于多特征融合的视频目标跟踪方法[J].西安电子科技大学学报,2012,39(4):1-6. Li Yuanzheng,Lu Zhaoyang,Li Jing.Robust Video Object Tracking Algorithm Based on Multi-feature Fusion[J]. Journal of Xidian University,2012,39(4):1-6.

[3]孙浩,王程,王润生.局部不变特征综述[J].中国图象图形学报,2011,16(2):141-151. Sun Hao,Wang Cheng,Wang Runsheng.A Review of Local Invariant Features[J].Journal of Image and Graphics, 2011,16(2):141-151.

[4]高晶,毕笃彦,赵晓林.融合边缘片断与水平集分割的目标跟踪算法[J].西安电子科技大学学报,2011,38(6):146-151. Gao Jing,Bi Duyan,Zhao Xiaolin.Non-rigid Object Tracking Based on the Boundary Fragment Feature and Level Set Segmentation[J].Journal of Xidian University,2011,38(6):146-151.

[5]Lowe D G.Object Recognition from Local Scale-invariant Features[C]//Proceedings of the Seventh IEEE International Conference on Computer Vision.Piscataway:IEEE,1999:1150-1157.

[6]Heinly J,Dunn E,Frahm J M.Comparative Evaluation of Binary Features[C]//Proceedings of the 12th European Conference on Computer Vision.Berlin:Springer,2012:759-773.

[7]Calonder M,Lepetit V,Strecha C,et al.BRIEF:Binary Robust Independent Elementary Features[C]//Lecture Notes in Computer Science:6314.Heidelberg:Springer Verlag,2010:778-792.

[8]Rublee E,Rabaud V,Konolige K,et al.ORB:an Efficient Alternative to SIFT or SURF[C]//Proceedings of the IEEE International Conference on Computer Vision.Piscataway:IEEE,2011:2564-2571.

[9]Trzcinski T,Christoudias M,Lepetit V,et al.Boosting Binary Keypoint Descriptors[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society,2013:2874-2881.

[10]Gong Y C,Lazebnik S.Iterative Quantization:a Procrustean Approach to Learning Binary Codes[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway:IEEE,2011:817-824.

[11]Lauro N C,Verde R,Irpino A.Principal Component Analysis[J].Business Research Methods,2005,23(2):41-64.

[12]Huang Z.Extensions to the K-means Algorithm for Clustering Large Data Sets with Categorical Values[J].Data Mining and Knowledge Discovery,1998,2(3):283-304.

[13]张俊根,姬红兵.采用粒子滤波和模糊聚类法的非线性多目标跟踪[J].西安电子科技大学学报,2010,37(4):636-641. Zhang Jungen,Ji Hongbing.Passive Multi-target Tracking Based on Independent Particle Filtering and Fuzzy Clustering [J].Journal of Xidian University,2010,37(4):636-641.

[14]Sevilla-Lara L,Learned-Miller E G.Distribution Fields for Tracking[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society,2012:1910-1917.

[15]Everingham M,Van Gool L,Williams C K,et al.The Pascal Visual Object Classes(VOC)Challenge[J].Interational Journal of Computer Vision,2010,88(2):303-338.

(编辑:齐淑娟)

Real-time visual object tracking based on binary descriptors

QIN Bing,TIAN Jun,ZH A Yufei,ZHANG Lichao,HUANG Hongtu
(Inst.of Aeronautics and Astronautics Eng.,Air Force Eng.Univ.,Xi’an 710038,China)

Object tracking often has the problems of low rate and high storage.Therefore,a tracking algorithm based on binary descriptors is proposed.The algorithm retains the original construction information on the samples and projects the samples from Euclidean space to Hamming space in order to generate binary descriptors by searching the optimal orthogonal matrix for rotating cluster.Then under the frame of particle filtering,it is necessary to determine the tracking position by computing the hamming distance.Analysis and experiment show that the proposed tracking algorithm performs rapidly and favorably when the target objects undergo large illumination,pose changes and fast movement.

object tracking;binary descriptors;particle filtering;hamming distance

TP391

A

1001-2400(2015)05-0168-07

2014-05-08< class="emphasis_bold">网络出版时间:

时间:2014-12-23

国家自然科学基金资助项目(61472442);航空科学基金资助项目(20131996013)

覃 兵(1991-),男,空军工程大学硕士研究生,E-mail:qinbingzaixian@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.028.html

10.3969/j.issn.1001-2400.2015.05.028