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

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

1 引言

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

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

本文利用空間直方圖能保持空間信息的優點，提出了一種基于空間直方圖表示的雙核式跟蹤算法。對于給定的候選目標，本文通過兩個指標來判斷其是否為真實目標， 指標一是候選目標與目標模板之間的相似度，指標二是候選目標與其鄰近背景區域之間的對比度。而目標函數則由這兩者的自適應加權組合而成。本文的主要貢獻有：提出了目標評判雙準則，導出了空間直方圖表示下的雙核式位移公式，建立了權值的模糊自適應調節機制。

2 二階距空間直方圖

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

3 本文提出的算法

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

3.1 目標與背景的對比度

為了充分利用背景信息， 我們選擇緊繞候選目標、大小為其3倍的環形區域作為有效的背景圖像。目標與背景間的對比程度主要體現在顏色特征上，而不是空間結構上，譬如，當目標與背景是顏色完全相同的色塊時，它們之間在視覺上應該不存在反差，即對比度應為0，但如果考慮空間結構，則因為一個是矩形，一個是環形，顯然對比度不為0，這是與事實不符的。因此，我們在度量目標與背景間的對比度時，只考慮顏色特征。設背景圖像的顏色模型為

因為背景圖像是環形的， 因此核函數僅在 x ∈[0.25,1]內取非零值。

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

3.2 雙核式位移公式推導

同時考慮相似度與對比度對目標評判的影響，則可構建新型目標函數為

其中，0≤α, β≤1為權重系數，用于調節相似度與對比度在目標函數中所占的比重，且有 α +β=1,0≤ ρ（z）≤1。

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

其中

求式（11）中（）ρ z關于z的導數有

其中，gp（x ） = -kp′（x ）, gr（ x ） = -kr′（x ） 。式（14）表明目標的位置是由目標圖像與其背景圖像共同決定，因為式中存在兩個核函數，因此本文叫其為雙核式位移公式。在使用Epanechnikov核函數的情況下，式（14）可以進一步簡化為

3.3 目標與背景的對比度

可以合理認為在相鄰幀之間相似度和對比度不會發生大的變化，因此本文根據前一幀的對比度和相似度值，使用模糊邏輯的方法來自適應地決定當前幀中的權值。模糊邏輯主要由模糊化、模糊規則、模糊推理和解模糊4部分組成[18]，本文采用了單點模糊化、乘積推理和重心解模糊。模糊規則定義為

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

本文中模糊邏輯的輸入為上幀中對比度和相似度的可信度，輸出為當前幀中相似度的權值α，而對比度的權值β=1-α。記相似度的可信度分別為

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

表1 模糊規則基

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

4 實驗與分析

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

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

第1個實驗通過跟蹤視頻dollar來比較DKBT和DTBSS。該視頻有327幀，每幀大小為320×240，其跟蹤結果如圖1（a）所示。可以看到從第38幀開始最上面的那張美鈔被逐漸折疊，在第51幀中已被折疊，并且整疊鈔票在第131幀中被拆成兩疊。第134幀中左邊那張是被折疊后的原始美鈔，右邊那張是新露出的美鈔，雖然后者外觀與第1幀完全相同，但它們并不是同一張鈔票。此時，DTBSS并沒像DKBT那樣跟蹤到被折疊美鈔，而是跟蹤到了與初始美鈔外觀相似的新美鈔。從跟蹤結果來說DTBSS是失敗了，但從原理上來講DTBSS比DKBT要更準確，因為DTBSS的空間直方圖在描述目標對象時比DKBT的普通直方圖多了空間信息。圖1（b）和圖1（c）分別展示了第134幀中黑色矩形區域的DTBSS和DKBT目標函數值演化曲面，不難看出DTBSS只有一個比較突出的波峰，而DKBT出現了兩個幅度非常接近的波峰，這是因為后者所使用的普通直方圖沒有考慮目標的空間信息，致使美鈔折疊前后仍然相似，這與事實矛盾。

4.2 單核與雙核比較

第2個實驗通過跟蹤視頻walker來比較KBST和DTBSS。該視頻有252幀，每幀大小為640×480，其跟蹤結果如圖2（a）所示。可以看到第84幀以前兩個跟蹤器都能穩定地跟蹤到walker，但從第84幀開始KBST的跟蹤窗發生了漂移，并最終跟丟了目標，而DTBSS始終能穩定地跟蹤到運動目標。這主要是因為walker被樹干遮擋之后，候選目標與目標模型之間的相似度急劇下降，從而導致KBST搜索失敗，而DTBSS卻憑借候選目標與其背景之間的對比度，成功地鎖定了跟蹤對象。圖2（b）和圖2（c）分別展示了第84幀中黑色矩形區域的相似度與對比度演化曲面，不難看出相似度曲面沒有明顯的峰值，且對比度峰值遠大于相似度峰值，因此該幀中對比度主導了對目標對象的評估。圖2（d）中權值α的演化曲線

圖1 實驗1的測試結果

圖2 實驗2的測試結果

也反映了這一情況，例如，從第81～90幀α的值顯著較低，說明此時相似度的可信度要低于對比度的，因此文中的自適應權值調節方法能較好地抑制跟蹤過程中不可靠角色。

4.3 與最新跟蹤器比較

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

4.4 定量比較

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

5 結束語

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

表3 各跟蹤方法的定量測試結果

圖3 實驗3的測試結果（實線框代表DTBSS，虛線框代表IVT，點線框代表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].電子與信息學報, 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.