基于二階空間直方圖的雙核跟蹤

張燦龍 唐艷平 李志欣① 馬海菲① 蔡 冰①

1 引言

目標(biāo)跟蹤是完成視覺監(jiān)控、人機(jī)交互、車輛導(dǎo)航等諸多視頻場景分析和理解任務(wù)的基礎(chǔ)。已有大量的跟蹤方法被報(bào)道[1,2]，這些方法可分成四大類：隨機(jī)性方法[3,4]、確定性方法[5,6]、鑒別分類法[7,8]以及子空間方法[9,10]。隨機(jī)性方法將目標(biāo)狀態(tài)看成隨機(jī)事件，在貝葉斯框架下，通過濾波來實(shí)現(xiàn)目標(biāo)跟蹤， 典型的如粒子濾波跟蹤器[3]。而確定性方法通常會(huì)先建立一個(gè)描述模型匹配度的目標(biāo)函數(shù)，然后將跟蹤問題轉(zhuǎn)換為目標(biāo)函數(shù)的尋優(yōu)問題，典型的如基于核的跟蹤器（Kernel-Based Tracking, KBT[5]）。

KBT算法使用基于梯度下降的迭代搜索技術(shù)，從而簡單快速， 已廣泛應(yīng)用于實(shí)時(shí)性要求較高的目標(biāo)跟蹤場合。雖然，經(jīng)過十幾年的發(fā)展，核跟蹤方法已相對(duì)成熟，但是， 作為一種輕量級(jí)、易實(shí)現(xiàn)的算法，它仍廣受人們的關(guān)注和持續(xù)研究[11,12]。原始KBT方法存在空間信息丟失、背景作用弱化以及尺度自適應(yīng)等問題。針對(duì)這些問題， 人們提出了許多改進(jìn)的方法。文獻(xiàn)[13]提出了空間直方圖（spatiogram）概念?？臻g直方圖不僅統(tǒng)計(jì)每個(gè)特征區(qū)間內(nèi)的像素個(gè)數(shù)，還計(jì)算該區(qū)間內(nèi)所有像素點(diǎn)空間分布的均值和方差，從而保持了空間信息。文獻(xiàn)[14]指出聯(lián)合背景信息往往能取得更好的跟蹤效果。文獻(xiàn)[5]試圖通過背景加權(quán)直方圖的方法消除在目標(biāo)和背景中同時(shí)出現(xiàn)的那些特征的重要性，但這一做法被文獻(xiàn)[15]證明是無效的。文獻(xiàn)[7]把跟蹤問題轉(zhuǎn)變成目標(biāo)與背景之間的二分類問題， 通過最大化類間距來鑒別目標(biāo)。但為了獲得一個(gè)好的分類器，需要大量樣本和離線訓(xùn)練，這在實(shí)際操作中存在一定的困難。

本文利用空間直方圖能保持空間信息的優(yōu)點(diǎn)，提出了一種基于空間直方圖表示的雙核式跟蹤算法。對(duì)于給定的候選目標(biāo)，本文通過兩個(gè)指標(biāo)來判斷其是否為真實(shí)目標(biāo)， 指標(biāo)一是候選目標(biāo)與目標(biāo)模板之間的相似度，指標(biāo)二是候選目標(biāo)與其鄰近背景區(qū)域之間的對(duì)比度。而目標(biāo)函數(shù)則由這兩者的自適應(yīng)加權(quán)組合而成。本文的主要貢獻(xiàn)有：提出了目標(biāo)評(píng)判雙準(zhǔn)則，導(dǎo)出了空間直方圖表示下的雙核式位移公式，建立了權(quán)值的模糊自適應(yīng)調(diào)節(jié)機(jī)制。

2 二階距空間直方圖

空間直方圖[13]是一種帶高階矩信息的廣義直方圖。零階矩對(duì)應(yīng)傳統(tǒng)意義上的直方圖， 而二階矩直方圖則是附加了像素點(diǎn)空間分布的均值和方差信息的直方圖。為了行文方便， 以下簡稱二階矩空間直方圖為二階直方圖。

3 本文提出的算法

眾所周知，目標(biāo)與背景之間的反差越大，就越容易被辨認(rèn)出來，因此在設(shè)計(jì)跟蹤器的過程應(yīng)充分利用目標(biāo)與背景之間的反差特性。無論是早期的背景減跟蹤器，還是最近流行的二分類跟蹤器[7]，都利用了這一特性。而基于模板匹配的跟蹤器，如核跟蹤、濾波跟蹤和子空間跟蹤等，則是利用目標(biāo)與模板之間的相似度來完成跟蹤。研究發(fā)現(xiàn)，將目標(biāo)與模板之間的相似度以及目標(biāo)與背景之間的對(duì)比度進(jìn)行有機(jī)統(tǒng)一，是有益于改善跟蹤器性能。

3.1 目標(biāo)與背景的對(duì)比度

為了充分利用背景信息， 我們選擇緊繞候選目標(biāo)、大小為其3倍的環(huán)形區(qū)域作為有效的背景圖像。目標(biāo)與背景間的對(duì)比程度主要體現(xiàn)在顏色特征上，而不是空間結(jié)構(gòu)上，譬如，當(dāng)目標(biāo)與背景是顏色完全相同的色塊時(shí)，它們之間在視覺上應(yīng)該不存在反差，即對(duì)比度應(yīng)為0，但如果考慮空間結(jié)構(gòu)，則因?yàn)橐粋€(gè)是矩形，一個(gè)是環(huán)形，顯然對(duì)比度不為0，這是與事實(shí)不符的。因此，我們在度量目標(biāo)與背景間的對(duì)比度時(shí)，只考慮顏色特征。設(shè)背景圖像的顏色模型為

因?yàn)楸尘皥D像是環(huán)形的， 因此核函數(shù)僅在 x ∈[0.25,1]內(nèi)取非零值。

為了計(jì)算目標(biāo)與背景圖像的差異程度， 本文引入延森-香農(nóng)散度（Jensen-Shannon Divergence,JSD[17]），其定義為

3.2 雙核式位移公式推導(dǎo)

同時(shí)考慮相似度與對(duì)比度對(duì)目標(biāo)評(píng)判的影響，則可構(gòu)建新型目標(biāo)函數(shù)為

其中，0≤α, β≤1為權(quán)重系數(shù)，用于調(diào)節(jié)相似度與對(duì)比度在目標(biāo)函數(shù)中所占的比重，且有 α +β=1,0≤ ρ（z）≤1。

設(shè)目標(biāo)在前一幀中的位置為 z0。 將式（5）和式（9）代入式（10）中，并在pu（ z0）, ru（ z0） 和 μu（z0）處對(duì)目標(biāo)函數(shù)ρ（z）進(jìn)行泰勒展開，得到線性逼近形式為

其中

求式（11）中（）ρ z關(guān)于z的導(dǎo)數(shù)有

其中，gp（x ） = -kp′（x ）, gr（ x ） = -kr′（x ） 。式（14）表明目標(biāo)的位置是由目標(biāo)圖像與其背景圖像共同決定，因?yàn)槭街写嬖趦蓚€(gè)核函數(shù)，因此本文叫其為雙核式位移公式。在使用Epanechnikov核函數(shù)的情況下，式（14）可以進(jìn)一步簡化為

3.3 目標(biāo)與背景的對(duì)比度

可以合理認(rèn)為在相鄰幀之間相似度和對(duì)比度不會(huì)發(fā)生大的變化，因此本文根據(jù)前一幀的對(duì)比度和相似度值，使用模糊邏輯的方法來自適應(yīng)地決定當(dāng)前幀中的權(quán)值。模糊邏輯主要由模糊化、模糊規(guī)則、模糊推理和解模糊4部分組成[18]，本文采用了單點(diǎn)模糊化、乘積推理和重心解模糊。模糊規(guī)則定義為

Rj：如果 e1屬于，并且 e2屬于,…，并且 el屬于，則v屬于。其中，Rj為第j條模糊規(guī)則，L為總的規(guī)則數(shù)， {e1, e2,… ,el}和v分別為模糊邏輯的輸入和輸出。

本文中模糊邏輯的輸入為上幀中對(duì)比度和相似度的可信度，輸出為當(dāng)前幀中相似度的權(quán)值α，而對(duì)比度的權(quán)值β=1-α。記相似度的可信度分別為

給定目標(biāo)的模型 h'和它在上一幀中的位置 z0，從位置 z0開始， 根據(jù)式（15）遞歸地搜索目標(biāo)在當(dāng)前幀中的最優(yōu)位置。表2總結(jié)了基于二階空間直方圖的雙核跟蹤（Dual-kernel Tracking Based on Second-order Spatiogram, DTBSS）流程。采用Matlab和MEX混合方式對(duì)其進(jìn)行了編程。

表1 模糊規(guī)則基

表2 基于二階空間直方圖的雙核跟蹤算法

4 實(shí)驗(yàn)與分析

本文采用了4段視頻來測試DTBSS的性能， 并將它與基于雙核的直方圖跟蹤（Dual-Kernel Based Tracking, DKBT[19]）、基于單核的空間直方圖跟蹤（Kernel Based Spatiogram Tracking, KBST[16]），增量學(xué)習(xí)跟蹤（Incremental Visual Tracker, IVT[9]）和l1跟蹤（l1Tracker, L1T[10]）做了比較和分析。初始目標(biāo)均由手工標(biāo)出。初始化。DTBSS, DKBT,KBST算法中的尺度處理采用文獻(xiàn)[5]中的方法。實(shí)驗(yàn)環(huán)境為主頻2×3.2 GHz、內(nèi)存4G的PC機(jī)。

4.1 直方圖與空間直方圖比較

第1個(gè)實(shí)驗(yàn)通過跟蹤視頻dollar來比較DKBT和DTBSS。該視頻有327幀，每幀大小為320×240，其跟蹤結(jié)果如圖1（a）所示?？梢钥吹綇牡?8幀開始最上面的那張美鈔被逐漸折疊，在第51幀中已被折疊，并且整疊鈔票在第131幀中被拆成兩疊。第134幀中左邊那張是被折疊后的原始美鈔，右邊那張是新露出的美鈔，雖然后者外觀與第1幀完全相同，但它們并不是同一張鈔票。此時(shí)，DTBSS并沒像DKBT那樣跟蹤到被折疊美鈔，而是跟蹤到了與初始美鈔外觀相似的新美鈔。從跟蹤結(jié)果來說DTBSS是失敗了，但從原理上來講DTBSS比DKBT要更準(zhǔn)確，因?yàn)镈TBSS的空間直方圖在描述目標(biāo)對(duì)象時(shí)比DKBT的普通直方圖多了空間信息。圖1（b）和圖1（c）分別展示了第134幀中黑色矩形區(qū)域的DTBSS和DKBT目標(biāo)函數(shù)值演化曲面，不難看出DTBSS只有一個(gè)比較突出的波峰，而DKBT出現(xiàn)了兩個(gè)幅度非常接近的波峰，這是因?yàn)楹笳咚褂玫钠胀ㄖ狈綀D沒有考慮目標(biāo)的空間信息，致使美鈔折疊前后仍然相似，這與事實(shí)矛盾。

4.2 單核與雙核比較

第2個(gè)實(shí)驗(yàn)通過跟蹤視頻walker來比較KBST和DTBSS。該視頻有252幀，每幀大小為640×480，其跟蹤結(jié)果如圖2（a）所示?？梢钥吹降?4幀以前兩個(gè)跟蹤器都能穩(wěn)定地跟蹤到walker，但從第84幀開始KBST的跟蹤窗發(fā)生了漂移，并最終跟丟了目標(biāo)，而DTBSS始終能穩(wěn)定地跟蹤到運(yùn)動(dòng)目標(biāo)。這主要是因?yàn)閣alker被樹干遮擋之后，候選目標(biāo)與目標(biāo)模型之間的相似度急劇下降，從而導(dǎo)致KBST搜索失敗，而DTBSS卻憑借候選目標(biāo)與其背景之間的對(duì)比度，成功地鎖定了跟蹤對(duì)象。圖2（b）和圖2（c）分別展示了第84幀中黑色矩形區(qū)域的相似度與對(duì)比度演化曲面，不難看出相似度曲面沒有明顯的峰值，且對(duì)比度峰值遠(yuǎn)大于相似度峰值，因此該幀中對(duì)比度主導(dǎo)了對(duì)目標(biāo)對(duì)象的評(píng)估。圖2（d）中權(quán)值α的演化曲線

圖1 實(shí)驗(yàn)1的測試結(jié)果

圖2 實(shí)驗(yàn)2的測試結(jié)果

也反映了這一情況，例如，從第81～90幀α的值顯著較低，說明此時(shí)相似度的可信度要低于對(duì)比度的，因此文中的自適應(yīng)權(quán)值調(diào)節(jié)方法能較好地抑制跟蹤過程中不可靠角色。

4.3 與最新跟蹤器比較

第3個(gè)實(shí)驗(yàn)通過跟蹤視頻doll和panda來比較DTBSS和最新算法IVT, L1T，實(shí)驗(yàn)結(jié)果如圖3所示。可以看到在被跟蹤對(duì)象未發(fā)生旋轉(zhuǎn)和形變時(shí)，如圖3（a）, DTBSS, IVT和L1T都能準(zhǔn)確地鎖定目標(biāo)。但在目標(biāo)發(fā)生較大的旋轉(zhuǎn)和遮擋時(shí)，如圖3（b）, IVT,L1T分別從第159, 7幀開始跟丟目標(biāo)。由于在均值漂移（mean-shift）框架下DTBSS是無法解決目標(biāo)旋轉(zhuǎn)的，而基于粒子濾波框架的IVT卻能很容易地處理目標(biāo)的仿射運(yùn)動(dòng)，因此，正如圖4（d）所示，盡管DTBSS始終跟上了panda，但其整體準(zhǔn)確率要比IVT低。L1T是基于稀疏表示的跟蹤算法，雖然也是在粒子濾波框架下實(shí)現(xiàn)的，但該文作者提供的源程序并不能處理旋轉(zhuǎn)問題，因此對(duì)panda的跟蹤效果很不理想。此外，IVT和L1T都引入了在線學(xué)習(xí)機(jī)制，這對(duì)處理目標(biāo)表觀變化是有好處的，但同時(shí)也帶來更新誤差的累積問題，隨著累積誤差越大，它們的跟蹤性能也會(huì)下降。

4.4 定量比較

表3列舉了定量比較結(jié)果， 圖4展示了逐幀重疊率。不難發(fā)現(xiàn)， 與其他跟蹤方法相比， 本文所提出的跟蹤方法在平均重疊率、平均計(jì)算時(shí)間和成功率指標(biāo)上獲得了較好的綜合性能。

5 結(jié)束語

本文將對(duì)比度準(zhǔn)則引入核跟蹤算法中， 并通過綜合空間直方圖、Jensen-Shannon散度和模糊邏輯等理論， 構(gòu)建了基于空間直方圖的雙核跟蹤。算法在空間結(jié)構(gòu)保持、背景信息利用和實(shí)時(shí)性方面實(shí)現(xiàn)了有機(jī)統(tǒng)一， 是對(duì)傳統(tǒng)核跟蹤算法的有效拓展。對(duì)卷入遮擋、旋轉(zhuǎn)、縮放、模糊以及偽目標(biāo)干擾等變化下的多組目標(biāo)的跟蹤實(shí)驗(yàn)驗(yàn)證了本文的結(jié)論。未來可研究將雙準(zhǔn)則目標(biāo)函數(shù)嵌入粒子濾波算法中，以期突破核跟蹤框架對(duì)縮放、旋轉(zhuǎn)和形變等的約束。

表3 各跟蹤方法的定量測試結(jié)果

圖3 實(shí)驗(yàn)3的測試結(jié)果（實(shí)線框代表DTBSS，虛線框代表IVT，點(diǎn)線框代表L1T）

圖4 逐幀重疊率

[1] Zhang S, Yao H, Sun X, et al.. Sparse coding based visual tracking: review and experimental comparison[J]. Pattern Recognition, 2013, 46（7）: 1772-1788.

[2] Wu Y, Lim J, and Yang M. Online object tracking: a benchmark[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Oregon, Portland,USA, 2013: 2411-2418.

[3] Isard M and Black A. Condensation-conditional density propagation for visual tracking[J]. International Journal on Computer Vision, 1998, 29（1）: 5-28.

[4] 程旭, 李擬珺, 周同池, 等. 稀疏表示的超像素在線跟蹤[J].電子與信息學(xué)報(bào), 2014, 36（10）: 2393-2399.Cheng Xu, Li Ni-jun, Zhou Tong-chi, et al.. Online tracking via superpixel and sparse representation[J]. Journal of Electronics & Information Technology, 2014, 36（10）:2393-2399.

[5] Comaniciu D, Ramesh V, and Meer P. Kernel-based object tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25（5）: 564-577.

[6] Leichter I. Mean shift trackers with cross-bin metrics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34（4）: 695-706.

[7] Avidan S. Support vector tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26（8）:1064-1072.

[8] Zhang K and Song H. Real-time visual tracking via online weighted multiple instance learning[J]. Pattern Recognition,2013, 46（1）: 397-411.

[9] Ross D, Lim J, Lin R, et al.. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision,2008, 77（3）: 125-141.

[10] Mei X and Ling H. Robust visual tracking using l1minimization[C]. Proceedings of the International Conference on Computer Vision, Kyoto, Japan, 2009: 1436-1443.

[11] Fouad B, Lynda D, and Hichem S. Improved mean shift integrating texture and color features for robust real time object tracking[J]. The Visual Computer, 2013, 29（3）:155-170.

[12] Tomas V, Jana N, and Jiri M. Robust scale-adaptive meanshift for tracking[J]. Lecture Notes in Computer Science, 2013（7944）: 652-663.

[13] Birchfield S and Rangarajan S. Spatiograms versus histograms for region-based tracking[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, SanDiego, California, USA, 2005: 1158-1163.

[14] Collins R, Liu Y, and Leordeanum M. Online selection of discriminative tracking features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27（10）:1631-1643.

[15] Ning J, Zhang L, Zhang D, et al.. Robust mean shift tracking with corrected background-weighted histogram[J]. IET Computer Vision, 2012, 6（1）: 62-69.

[16] Conaire C, O'Connor N, and Smeaton A. An improved spatiogram similarity measure for robust object localization[C]. Proceedings of International Conference on Acoustics,Speech, and Signal Processing, Hawaii, USA, 2007:1069-1072.

[17] Lin J. Divergence measures based on the shannon entropy[J].IEEE Transactions on Information Theory, 1991, 37（1）:145-151.

[18] Liu Y, Tong S, and Chen C. Adaptive fuzzy control via observer design for uncertain nonlinear systems with unmodeled dynamics[J]. IEEE Transactions on Fuzzy Systems, 2013, 21（2）: 275-288.

[19] Zhang C, Jing Z, and Jin B. A dual-kernel-based tracking approach for visual target[J]. SCIENCE CHINA: Information Sciences, 2012, 55（3）: 566-576.