2 中国科学院 长春光学精密机械与物理研究所 快速捕获与实时图像处理研究室, 吉林 长春 130033
2 Department of Fast Capture and Real-Time Image Processing, Changchun Institute of Optics, Fine Mechanics and Physics, The Chinese Academy of Sciences, Changchun 130033, China
低对比度低信噪比目标跟踪,是视频跟踪领域的一个难题.随着军事战场中对复杂光学环境下武器装备的战技性能要求越来越高,低对比度以及目标旋转、缩放、被遮挡等非理想状态严重制约了跟踪性能的提高.
多年来,国内外学者针对复杂背景中目标跟踪的鲁棒算法[1]进行了大量研究,但许多算法由于计算复杂未能应用到对实时性要求较高的场合.直到2003年,Comaniciu[2]将Mean Shift算法引入到目标跟踪领域,由于其运算速度快、跟踪鲁棒性好,至今仍受到很多学者的关注,提出的改进方法主要集中在以下几个方面:
· 在目标模型表达方面:改进的目标模型中引入更多的联合特征,例如混合模型[3]、SIFT特征[4]、LBP模型[5]、纹理信息[6]、自适应特征融合[7]、区域特征[8]等,描述能力有所增强,但在线调整特征权重的能力较弱,缺少鉴别性更强的相似性度量函数;
· 在尺度和方向估计方面:改进的方法[9, 10, 11]扩展了原始算法,在离散或者连续参数空间对尺度和方向进行优化计算,但对剧烈变化的尺度与方向估计效果不佳;
· 在抗遮挡跟踪方面:文献[12]引入Kalman滤波器、粒子滤波等算法预测目标位置,能够处理短时全局遮挡情况;文献[13, 14, 15, 16]将空间信息融入目标模型中,各个部分对整体贡献不同,对局部遮挡时定位较准确,但无法跟踪短时全局遮挡的目标;
· 在快速目标跟踪处理方面:改进方法[17,18]使用图像金字塔、全局概率密度搜索提高目标定位能力,但较易受相似目标干扰.
经过近10年的发展,Mean Shift跟踪研究已经相对成熟,当前限制其进一步发展的因素主要是算法固有的局限性,如Bhattacharyya相似系数对于非稀疏的直方图特征的鉴别性较差.
该局限性限制了其在低对比度目标跟踪中的应用.本文将研究重点放在建立鉴别性更高的参数模型和匹配度量上,提出一种基于似然相似度函数的低对比度目标跟踪方法.利用棱锥面方程的单峰特性,突出模型中的目标灰度信息.同时,从统计中的极大似然估计方法得到启发,构造一种新的似然相似度函数,与传统的相似度量相比,度量值的可区分性更高.实验结果表明:利用棱锥面参数模型和似然相似度函数可以从本质上解决以往Mean Shift跟踪方法对于低对比度目标的鉴别性不好的缺点,有效跟踪复杂背景条件下的低对比度目标.本文的研究意义就在于:它将增加我们对相似性度量函数的认识,为探索相似性度量函数的构造规律奠定基础.同时,注重该方法的可延展性,也就是说,利用似然相似度函数对于相似度的鉴别性更强的性质,可以把似然相似度函数推广到应用相似性度量的图像匹配领域,例如景像匹配.
1 参数模型的构造从数学角度描述目标跟踪过程是对目标建立合理的模板参数模型,然后在跟踪序列中目标可能出现的区域建立跟踪参数模型,匹配跟踪模型和模板模型达到目标检测或跟踪的目的.因此,参数模型的构造是跟踪是否有效的基础,要求建立的参数模型能够尽可能完备地反映目标信息,并很好地区分目标和背景.传统Mean Shift
算法使用核密度估计方法[7]建立初始模板的加权灰度直方图为
(1)
其中,u=1,…,m,i=1,…,n,m表示灰度级数,n表示初始模板包含的像素个数;Xi=(xi,yi)表示初始模板中第i个像素的坐标;H为初始模板的带宽向量;K(Xi,H)为核函数,C是标准化常数;d是Kronecker delta函数.即有:
其中,b(Xi)表示Xi点的灰度值.
传统的直方图仅仅统计每个灰度值出现的概率,与灰度值所处的位置无关.核密度估计方法使用核函数对各个像素点的灰度值加权后再统计直方图,其中,核函数的值与该像素点距中心像素点的距离成反比.此方法不仅统计每个灰度值的出现概率,同时引入像素点的空间位置信息,距离中心越远的像素点对应的核函数权值越小,对该灰度的直方图统计值贡献也越小;反之越大.这与实际情况相符合,模板中越远离中心的点受到背景图像的影响越大,对模板直方图的贡献越小;反之越大.因此,核函数的选取关系到直方图的加权值.传统Mean Shift算法使用Epanechnikov核函数:
(2)
其中,为归一化参数,H=(hx,hy)为带宽向量.本文使用棱锥面方程构造新的核函数计算模板参数模型,新的核函数公式如下:
K(Xi,H)=hx-|xi|+hy-|yi| (3)
图 1对比了使用两种核函数对于低对比度目标建立的参数模型图.图 1(a)为Epanechnikov核函数的图示,图 1(b)为我们构造的棱锥面核函数的图示.可以看出:本文使用棱锥面方程构造的核函数,在不改变函数单调递减性质的同时,使得密度大的信息更加突出.图 1(c)为航拍的低对比度飞机目标,图 1(d)为使用Epanechnikov核函数对图 1(c)所示黑色方框内的飞机目标进行密度估计得到的密度函数曲面,图 1(e)为使用棱锥面核函数得到的密度函数曲面.可以看出:本文构造的核函数得到的曲面有更明显的峰值和梯度变化,更能突出窗口中目标的灰度信息.
同理,跟踪模板灰度直方图为
(4)
其中,u=1,…,m,i=1,…,n¢,m表示灰度级数,n¢为跟踪模板包含的像素个数;Y为跟踪模板中心像素的坐标;H¢为跟踪模板的带宽向量;C¢是标准化常数.
2 参数模型的匹配模板匹配过程即求两个模型相似度的过程.传统Mean Shift算法使用Bhattacharyya系数度量估计值与的相似性:
(5)
其中,u=1,…,m,m表示灰度级数;为初始模板灰度直方图;为跟踪模板灰度直方图.
本文从统计学常用的极大似然估计理论获得启发,极大似然估计的原理是,建立似然函数L(q)来度量待估计的未知参数q将以多大可能产生已知样本.因此,使L(q)达到最大值时,未知参数的估计值即为极大似然估计值.求L(q)的极大值常常转化为求lnL(q)的极大值,因为ln(x)为x的增函数,lnL(q)和L(q)在q的同一值处达到它们的极值点.本文研究所建立的似然相似度量函数如下:
(6)
其中,u=1,…,m,m表示灰度级数;为初始模板灰度直方图;为跟踪模板灰度直方图.
对公式(5)和公式(6)分别求导数,绘制似然相似度函数与Bhattacharyya相似系数的斜率对比图,如图 2所示.
可见:新的似然相似函数斜率变化更大,使得跟踪过程中相似度的可区分性更强.
3 目标跟踪过程至此,目标跟踪过程就转化成似然函数为似然相似函数、参数为Y(目标跟踪位置)的极大似然估计过程.
将公式(6)在(为第k-1帧目标的位置)处泰勒展开,假设相邻帧灰度直方图变化不大,认为 很小,则只取泰勒一阶近似,可得:
(7)
将公式(5)代入公式(7),可得:
(8)
其中,
(9)
为了推导方便,假设当H=h2I时,有:
(10)
对公式(10)求导,建立似然方程:,得:
(11)
令g(x)=-k¢(x),将g(x)代入公式(11)得:
(12)
由于Epanechnikov核函数的轮廓函数为,可以求得g(x)=-k¢(x)=1,代入公式(12)得:
.
传统Mean Shift算法的跟踪权值wi为
(13)
其中,为初始模板灰度直方图,为跟踪模板灰度直方图,为第k-1帧目标的位置.
通过公式(9)、公式(13),可以推导出本研究权值与传统权值的关系式为分析迭代权值在跟踪算法中的实际意义(如图 3所示).图示黑色方框为5x5模板区域,中心在C位置,假设左图为初始状态,右图为下一帧状态,灰色区域为目标,白色区域为背景.
右图与左图相比,黑色方框内白色区域密度值变大.根据公式(8)可知:对应的wi变小,灰色区域密度值变小,对应的wi变大.新的目标中心向灰色区域偏移,即,新的跟踪窗将向右方移动.
对于某一个固定的灰度值u,当时,也就是说,初始模板中灰度值u出现的概率较大时,灰度为u的像素是模板中的主要信息,此时wi>1,,说明对于初始模板中主要信息被赋予的权值,通过似然相似函数推导得到的权值比传统权值要大;对于某一个固定的u¢,当时,初始模板中灰度u¢出现的 概率较小,说明灰度为u¢的像素是模板中的次要信息,此时wi<1,,说明对于初始模板中次要信息被赋的权值,通过似然相似函数推导得到的权值比传统权值要小.
综上所述,通过似然相似函数推导得到的权值使主要信息和次要信息对比更加鲜明,处理目标与背景相近时很有效.
4 实验结果图 4给出了航拍序列图像中,跟踪飞机目标的示意图.其中,图 4(a)~图 4(c)为传统算法跟踪图,图 4(d)~图 4(f)为本文算法跟踪图.
由图 4可以看出:传统Mean Shift算法中,目标和背景对应的权值比较接近,会导致跟踪与飞机灰度非常接近的山脉(如图 4(c)中白色线框所示).本研究对目标和背景赋予的权值可区分性更强,最终使得跟踪窗口向目标方向移动(如图 4(f)中黑色线框所示).
图 5、图 6给出了监视序列图像中,跟踪汽车目标的示意图.其中,图 5(a)~图 5(d)为传统算法跟踪图,图 5(e)~图 5(h)为本文算法跟踪图.
图 6显示了跟踪60帧浓雾中汽车的权值变化对比图,其中,左图为传统方法权值变化,右图为本文方法权值变化.
由图 5可以看出:传统Mean Shift算法在第39帧时,由于浓雾干扰,目标和背景对应的权值比较接近,会导致跟踪框停留在背景上.本研究对目标和背景赋予的权值可区分性更强,最终使得跟踪窗口向目标方向移动.图 7显示了第39帧传统方法和本文方法计算的每个灰度级对应的权值对比情况.
由图 8(b)、图 8(c)可以看出:当汽车被对面来的车辆和路边的电线杆遮挡时,算法仍能保持持续稳定的跟踪.针对图 8(c)中的遮挡情况,下面来分析本文权值的意义.
由图 8(a)可以看出:由于初始模板中没有电线杆的灰度信息,因此,中电线杆的灰度对应的直方图值非常小,从而得到的值非常小,甚至趋近于0.因此,图 8(c)所示电线杆部分像素点坐标对应的权值非常小,对最终跟踪位置的计算结果基本没有贡献.而电线杆的左右两侧都有车的像素点没有被全部遮挡,对应的权值很大,对最终跟踪位置起着决定性作用.因此,只要目标没有被全部遮挡,有颜色信息外露,则最终跟踪位置会向着外露的像素点处移动,实现不受部分遮挡影响的连续跟踪.
5 性能分析 5.1 适应性分析我们使用局部信号干扰比LSCR[8]来度量图像的对比度,公式如下:
LSCR=(ut-ub)/scl,
其中,ut表示目标灰度均值,ub表示背景灰度均值,scl表示目标周围邻域的灰度标准差.对图 4中的飞机目标计算LSCR值为4.9.
对105个低对比度图像序列进行实验,定义跟踪成功率=成功跟踪帧数/图像序列总帧数.本文算法与传统算法跟踪成功率对比情况如图 9所示.
通过对大量复杂场景图片实验跟踪性能可以得出:本文算法对于LSCR>3的图像具有稳定的跟踪性能.
5.2 复杂度分析假设各种运算的时间表示如下:一次加(减)法为Ta,一次乘法为Tm,一次除法运算为Td,一次开方运算为Ts.目标位置收敛时的平均迭代次数为N,初始模板的像素数为n,灰度级数为m.
比较本文与传统算法的复杂度,见表 1.
因为加法的运算时间与乘法相比可以忽略,由表 1得出本文算法复杂度为
(2Nn+m)Tm+(Nm+N+m)Td (14)
传统算法复杂度为
(2Nn+2Nm+m)Tm+(N+Nm+n)Td+mTs (15)
公式(15)减公式(14)得:2NmTm+(n-m)Td+mTs为本文简化的计算量.
5.3 时间性能分析表 2给出在32bit定点、1GHz时钟的TMS320C6416定点数字信号处理器环境条件下,本文算法与传统算法对于图 4所示序列图像的计算时间对比情况.
由表 2可以看出:与传统算法相比,第1帧计算模板直方图的时间减少了约12倍.在背景复杂的低对比度情况下跟踪,本文的算法最多约用2.5ms,比传统算法约减少了10倍;并且随着选取模板逐渐变大,简化效果会更加明显.在工程应用中,对于每秒50帧的采样速率,要求在20ms内完成目标跟踪任务及其他图像处理过程.可见:本文算法占用时间资源很少,为嵌入更多的图像处理算法奠定了基础.
6 结束语本文提出一种基于似然相似度函数的低对比度目标跟踪方法.在建立模型阶段,利用棱锥面方程的单峰特性,突出模型中的目标灰度信息,使目标与背景灰度信息的可区分性更高;在模型匹配阶段,从统计学中的极大似然估计方法得到启发,构造一种新的似然相似度函数,与传统的相似度量相比,度量值的可区分性更高,大大提高了匹配区域的无重复模式;最后,将目标跟踪过程转化为对目标跟踪位置的极大似然估计过程.与传统算法相比,本文算法运算时间减少了约10倍,目前已经成功嵌入TMS320C6416硬件平台,可以满足实时跟踪要求.通过对大量低对比度外场实际图片实验的结果表明,本文算法所能探测的目标对比度LSCR最低限度约为3.作为实例,给出复杂背景下低对比度(LSCR=4.9)空中飞机的实验结果.
致谢 在此,我们向对本文的工作给予支持和建议的同行,尤其是长春光机所的贾平研究员和王延杰研究员表示衷心的感谢.[1] | Ning JF, Zhang L, Zhang D, Wu C. Scale and orientation adaptive mean shift tracking. IET Computer Vision, 2012,6(1):52-61 . |
[2] | Comaniciu D, Ramesh V, Meer P. Kernel-Based object tracking. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2003, 25(2):564-577 . |
[3] | Zhang K, Kwork JT. Simplifying mixture models through function approximation. IEEE Trans. on Neural Networks, 2010,21(4): 644-658 . |
[4] | Zhou HY, Yuan Y, Shi CHM. Object tracking using SIFT features and mean shift. Computer Vision and Image Understanding, 2009,113(3):345-352 . |
[5] | Zhang J, Ning JF, Yan YF, Yu W. Target tracking based LBP model. Journal of Image and Graphics, 2012,17(11):1418-1424 (in Chinese with English abstract). |
[6] | Sivic J, Zisserman A. Efficient visual search of videos cast as text retrieval. IEEE Trans. on Pattern Analysis on Machine Intelligence, 2009,31(4):591-606 . |
[7] | Wang SHK, Guo JJ, Wang JZH. Mean shift tracking based on adaptive feature fusion. Journal of Beijing Institute of Technology (Natural Science Edition), 2011,31(7):803-809 (in Chinese with English abstract). |
[8] | Mahadevan V, Vasconcelos N. Biologically inspired object tracking using center-surround saliency mechanisms. IEEE Trans. on Pattern Analysis on Machine Intelligence, 2013,35(3):541-554 . |
[9] | Khan ZH, Gu YH, Backhouse AG. Robust visual object tracking using multi-mode anisotropic mean shift and particle filters. IEEE Trans. on Circuits and Systems for Video Technology, 2011,21(1):74-87 . |
[10] | Zivkovic Z, Cegil AT, Krose B. Approximate Bayesian methods for kernel-based object tracking. Computer Vision and Image Understanding, 2009,113(6):743-749 . |
[11] | Leichter I. Mean shift trackers with cross-bin metrics. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2012,34(4): 695-706 . |
[12] | Li XH, Zhang TY, Shen XD, Sun JCH. Object tracking using an adaptive Kalman filter combined with mean shift. SPIE Journal of Optical Engineering, 2010,49(2):020503 . |
[13] | Wang FL, Yu SHY, Yang J. Robust and efficient fragments-based tracking using mean shift. AEU—Int’l Journal of Electronics and Communication, 2010,64(7):614-623 . |
[14] | Fang JX, Yang J, Liu HX. Efficient and robust fragments-based multiple kernels tracking. AEU—Int’l Journal of Electronics and Communication, 2011,65(11):915-923 . |
[15] | Maggio E, Cavallaro A. Accurate appearance-based Bayesian tracking for maneuvering targets. Computer Vision and Image Understanding, 2009,113(4):544-555 . |
[16] | Vezzani R, Grana C, Cucchiara R. Probabilistic people tracking with appearance models and occlusion. Pattern Recognition Letters, 2011,32(6):867-877 . |
[17] | Li SHX, Chang HX, Zhu CHF. Adaptive pyramid mean shift for global real-time visual tracking. Image and Vision Computing, 2010,28(3):424-437 . |
[18] | Li LF, Fu ZR, Chen WD, Ji M. A coarse-to fine kernel matching approach for mean-shift based visual tracking. Opto-Electronics Review, 2009,17(1):65-71 . |
[5] | 张炯,宁纪锋,颜永丰,于伟.对立色LBP模型的目标跟踪. 中国图像图形学报,2012,17(11):1418-1424. |
[7] | 汪首坤,郭俊杰,王军政.基于自适应特征融合的均值迁移目标跟踪. 北京理工大学学报(自然科学版),2011,31(7):803-809. |