基于簇相似的多分類器目標跟蹤算法

李 康，何發(fā)智，潘一騰，孫 航

（武漢大學計算機學院，湖北武漢430072）

基于簇相似的多分類器目標跟蹤算法

李 康，何發(fā)智，潘一騰，孫 航

（武漢大學計算機學院，湖北武漢430072）

由于跟蹤過程中目標和背景的變化，傳統(tǒng)的單分類器跟蹤算法學習到大量的非目標信息而導致跟蹤精度降低.針對該問題，本文提出使用樹形結(jié)構(gòu)保存歷史分類器.在每一幀，根據(jù)樹中路徑距離選擇分類器集對測試樣本分類.提出了一種基于簇相似性比較的分類算法.通過建立以方差為尺度的特征空間，比較測試樣本到簇中心的距離計算相似度，快速計算出目標樣本.實驗表明本算法能夠在復雜條件下實現(xiàn)對目標的魯棒跟蹤.

目標跟蹤；多分類器；在線學習；類哈爾特征

1 引言

目標跟蹤是計算機視覺中最為活躍的領(lǐng)域之一，其研究成果被廣泛用于運動分析，實時監(jiān)控和人機交互等領(lǐng)域［1，2］.近年來有大量的目標跟蹤算法被開發(fā)出來，但是由于目標本身的變化，目標信息不足，以及光照變化和遮擋變化等外部因素的影響，開發(fā)出魯棒性的目標跟蹤算法仍舊是一個難題.

經(jīng)典的跟蹤系統(tǒng)由外觀模型，運動模型和搜索策略三部分組成.其中，外觀模型最為重要，它直接影響了整個跟蹤系統(tǒng)的算法和結(jié)構(gòu).與靜態(tài)外觀模型相比，自適應(yīng)外觀模型算法［3，4］在跟蹤過程中不斷進行更新，適應(yīng)目標新的變化，具有更好的魯棒性.

根據(jù)外觀模型的不同，自適應(yīng)模型跟蹤算法可以分為生成模型［5，6］和判別模型［7，8］兩類.基于分類的判別模型算法從目標和背景中采集正樣本和負樣本，對這些樣本提取特征后訓練分類器，最后使用分類器對目標可能存在區(qū)域的采樣樣本進行分類得到目標的位置.文獻［8］提出了一種在線Boosting算法，取得了良好的效果.但是由于Boosting算法在每一幀都必須迭代地對弱分類器進行選擇，極大的降低了跟蹤速度.近年來，壓縮感知理論被廣泛用于包括目標跟蹤等圖像處理的各個領(lǐng)域.文獻［7］根據(jù)信號的稀疏特性，使用隨機采樣的方式從圖像中快速提取目標的類哈爾特征，并用這些相互獨立的特征組合訓練貝葉斯分類器，然后使用滑動窗口在目標可能存在的區(qū)域采集測試樣本進行分類，得到目標位置.

在上述所有自適應(yīng)算法中，分類器隨著跟蹤的進行而實時更新，但是當目標本身或其周圍環(huán)境發(fā)生劇烈變化時，最新的分類器學習到了大量的非目標信息，這時若目標恢復原狀或遮擋物從目標移開，最新的分類器則不能對目標進行準確分類.本研究通過構(gòu)建分類器樹保存歷史分類器信息，并根據(jù)樹中路徑距離選擇出分類器集用于對測試樣本分類，有效地解決了這個問題.為了保證跟蹤速度，本研究提出了一種基于簇相似性比較確定目標樣本的方法.該方法具有計算速度快，分類能力強，分類器易于保存，更新速度快等優(yōu)點.

2 算法描述

2.1基于檢測的跟蹤流程

假設(shè)已知t時刻圖像Ft中的目標為x*t，其位置為.首先從目標周圍半徑rp內(nèi)提取目標簇其次在目標周圍半徑rin和ron之間采集背景簇目標簇和背景簇中的樣本用于訓練跟蹤系統(tǒng)維持的分類器.當?shù)趖+1幀到來時，使用滑動窗口在第t+1幀目標周圍采集測試樣本集最后使用t時刻訓練得到的分類器對測試樣本集進行分類，得到t+1時刻的目標

2.2特征提取

本實驗中使用隨機生成的均值類哈爾特征模板提取樣本的特征.樣本x的第i個特征可以表示為：

2.3分類器的構(gòu)建

本文根據(jù)樣本到樣本簇之間的距離來定義它們之間的相似度.定義第i維特征空間中樣本x與簇之間的距離關(guān)系為：

樣本與簇之間的相似度定義為與它們之間的距離成反比：

樣本與簇越相似，則S（x，χ）越大.定義目標函數(shù)J（x）描述樣本是目標的相對可能性，即若J（x（1））＞J（x（2）），則樣本x（1）更有可能是目標.由于目標應(yīng)該與目標簇相似，而要與背景簇不相似，因此目標函數(shù) J（x）定義為與樣本到目標簇之間的相似度成正比，與樣本到背景簇之間的相似度成反比：

2.4測試樣本分類

2.5節(jié)描述.則目標在t+1時刻的狀態(tài)以及所使用的分類器可以通過式（7）得出：

2.5分類器的更新與選擇

圖1描述了多分類器的選擇與更新策略.在t時刻，系統(tǒng)維持了一個樹形數(shù)據(jù)結(jié)構(gòu)表示分類器之間的派生關(guān)系.在t+1幀，從分類器集合At選擇出一個子集對t+1幀的測試樣本進行分類，其中dis（c，at）≤k表示距離at路徑長度小于或等于k.圖1中虛線框內(nèi)節(jié)點為距離at路徑長度小于2的節(jié)點.通過式（7）對t+1幀測試樣本分類后，得出和 c*.由于在跟蹤過程中目標形變，光照，遮擋等因素的影響，目標簇和背景簇的參數(shù)會發(fā)生相應(yīng)的變化，為了保證跟蹤的魯棒性和準確性，需要對這些參數(shù)進行在線更新.本文參考文獻［8］中參數(shù)更新的方法，在求出第t+1幀目標的位置后，采集第t+1幀的目標簇和背景簇并計算出它們的統(tǒng)計特征參數(shù)則t+1時刻的分類器at+1=可以表示為：

其中λ是學習率.最后將at+1作為c*的葉子節(jié)點加入到分類器樹中.

2.6跟蹤算法步驟

本文跟蹤算法的基本步驟如下：

如果第t+1幀不是最后一幀，則進入循環(huán)：

步驟5：將at+1作為c*的葉子節(jié)點加入到分類器樹中.

輸出：第t+1幀的目標位置x*t+1；更新后的分類器集合At+1以及新的分類器樹.

3 實驗結(jié)果與分析

實驗與當前主流的3種算法在3個視頻序列上進行對比.參與對比的算法有：CT［7］，DFT［10］，TLD［11］，本文算法簡稱MCCS.視頻序列包括了實時跟蹤中常遇到的光照變化，形變，遮擋，復雜背景，運動模糊等影響因素.對比視頻序列包含了人工標定的目標位置.視頻序列數(shù)據(jù)以及其它算法的實驗數(shù)據(jù)可以從文獻［12］得到.

3.1參數(shù)設(shè)置

本實驗中使用矩形框標記跟蹤結(jié)果，目標在第1幀中的位置通過人工標定.試驗參數(shù)設(shè)置如下：目標簇采集半徑為rp=4個像素，背景簇采集內(nèi)半徑為rin=6個像素，外半徑ron=15個像素，負樣本采集數(shù)量為50個.測試樣本采集半徑為rs=25個像素.類哈爾特征數(shù)nf= 50個.類哈爾特征中圖像塊的個數(shù)nh為1到4之間的隨機整數(shù).多分類器選擇中的節(jié)點距離參數(shù)k=10.學習率λ=0.9.實驗環(huán)境為：Intel（R）Core（TM）i3-2120 CPU 3.30GHz，8 GB RAM，64位Windows操作系統(tǒng)，算法平均速度為35幀/秒.

3.2評價方法

本實驗中采用文獻［12］中提出的重合度成功率為評判方法.定義為重合度，其中R表示算法跟蹤的結(jié)果區(qū)域，G表示人工標定的目標區(qū)域，∩和∪表示兩種區(qū)域的交集和并集，函數(shù)area表示區(qū)域中像素的個數(shù).若S大于某個閾值，則認為該幀的跟蹤是成功的.

3.3實驗結(jié)果分析

圖2顯示了在各種不同重合率閾值的情況下各種算法跟蹤成功率.其中橫軸表示重合率閾值，縱軸表示在該閾值下跟蹤成功的幀數(shù)占視頻總幀數(shù)的比例，算法后面的數(shù)字為AUC值（Area Under Curve，即曲線與坐標軸圍成區(qū)域的面積）.從各個測試視頻的AUC值中可以看出，本文的算法跟蹤準確度更高.部分實例跟蹤結(jié)果如圖3所示.下面針對各個測試視頻序列進行結(jié)果分析：

（1）Basketball：該視頻序列中存在的大量與目標相似的背景以及目標本身的跑動產(chǎn)生的形變都會干擾跟蹤的結(jié)果.在第389，485幀目標發(fā)生了形變和遮擋，CT，TLD，DFT算法跟蹤到了非目標隊員上.第650幀時發(fā)生了強烈的光照變化，只有MCCS跟蹤準確.說明本算法能夠應(yīng)對跟蹤中遇到的遮擋，形變以及光照變化等情況.

（2）Jumping：在該視頻序列中，目標由于自身跳動以及相機的抖動產(chǎn)生了大量的模糊圖片.在第59幀中，DFT和CT就丟失了目標.從圖2的統(tǒng)計數(shù)據(jù)中可以看出，本算法處理運動模糊的效果優(yōu)于其他算法.

（3）Shaking：本視頻序列主要用于測試算法應(yīng)對燈光變化的能力.如圖3所示，在第60幀，舞臺燈光突然增強，除本算法之外的所有算法都產(chǎn)生了不同程度的漂移.在燈光強度減弱后，CT和TLD由于學習到了大量的燈光信息而不能對目標進行準確定位.在第266幀，由于光照強度變化，CT和TLD發(fā)生了漂移，本算法仍能夠準確地跟蹤目標位置.從圖2的數(shù)據(jù)中可以看出，本算法在應(yīng)對光照變化情況時能夠保證跟蹤精度.

4 結(jié)束語

在自適應(yīng)目標跟蹤算法中，由于目標被遮擋或背景的劇烈變化而使得分類器學習到了非目標信息，從而減低了跟蹤算法的性能.本文針對該問題提出了一種多分類器的跟蹤策略，通過建立樹形結(jié)構(gòu)的分類器集合，在每幀挑選出多個分類器對測試樣本進行分類，并挑選分類結(jié)果最好的分類器進行更新，避免了因分類器學習過快而產(chǎn)生的跟蹤漂移問題.為了能夠達到實時跟蹤，提出了一種基于簇相似性比較的快速分類算法，通過在以方差為尺度的特征空間中比較樣本與簇之間的相似性確定目標樣本.在與當前流行的跟蹤算法的比較中體現(xiàn)了本方法的優(yōu)越性.

［1］Yang H，Shao L，Zheng F，et al.Recent advances and trends in visual tracking：A review［J］.Neurocomputing，2011，74（18）：3823-3831.

［2］Yilmaz A，Javed O，Shah M.Object tracking：A survey ［J］.ACM Computing Surveys，2006，38（4）：13.

［3］權(quán)偉，陳錦雄，余南陽.在線學習多重檢測的可視對象跟蹤方法［J］.電子學報，2014，42（5）：875-882. QUAN Wei，CHEN Jin-xiong，YU Nan-yang.Online learning of multiple detectors for visual object tracking［J］.Acta Electronica Sinica，2014，42（5）：875-882.（in Chinese）

［4］姜明新，王洪玉，王潔，王彪.基于ML和L2范數(shù)的視頻目標跟蹤算法［J］.電子學報，2013，41（11）：2307 -2313. JIANG Ming-xin，WANG Hong-yu，WANG Jie，WANG Biao.Visual object tracking algorithm based on ML and L2-norm［J］.Acta Electronica Sinica，2013，41（11）：2307 -2313.（in Chinese）

［5］Ross D A，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77（1-3）：125-141.

［6］Mei X，Ling H.Robust visual tracking using l1 minimization［A］.IEEE 12th International Conference on Computer Vision［C］.Kyoto，Japan：IEEE，2009.1436-1443.

［7］Zhang K，Zhang L，Yang M H.Real-time compressive tracking［A］.Computer Vision-ECCV 2012［C］.Berlin Heidelberg：Springer，2012.864-877.

［8］Babenko B，Yang M H，Belongie S.Visual tracking with online multiple instance learning［A］.IEEE Conference on Computer Vision and Pattern Recognition［C］.Florida，USA：IEEE，2009.983-990.

［9］Mahalanobis P C.On the generalized distance in statistics ［J］.Proceedings of the National Institute of Sciences （Calcutta），1936，2：49-55.

［10］Sevilla-Lara L，Learned-Miller E.Distribution fields for tracking［A］.IEEE Conference on Computer Vision and Pattern Recognition［C］.Rhode Island：IEEE，2012.1910 -1917.

［11］Kalal Z，Matas J，Mikolajczyk K.Pn learning：Bootstrapping binary classifiers by structural constraints［A］.IEEE Conference on Computer Vision and Pattern Recognition ［C］.San Francisco：IEEE，2010.49-56.

［12］Wu Y，Lim J，Yang M H.Online object tracking：A benchmark［A］.IEEE Conference on Computer Vision and Pattern Recognition［C］.Portland，Oregon：IEEE，2013.2411-2418.

李 康 男，1986年9月出生，安徽亳州人.武漢大學在讀博士研究生，主要研究方向：圖像處理、目標跟蹤.

E-mail：likang@whu.edu.cn

何發(fā)智（通訊作者） 男，1968年11月出生，湖北武漢人.武漢大學教授、博士生導師.主要研究方向：圖像處理、計算機協(xié)同、計算機圖形.

E-mail：fzhe@whu.edu.cn

Multi-Classifier Object Tracking Based on Cluster Similarity

LI Kang，HE Fa-zhi，PAN Yi-teng，SUN Hang

（School of Computer Science，Wuhan University，Wuhan，Hubei 430072，China）

Due to the changes of target and background during tracking，traditional single classifier tracking algorithms learn a lot of non-target information which result in the decrease of tracking accuracy.In this paper，we propose to use tree structure to save former classifiers as a set.In each frame，a subset of classifiers are chosen according to the path in the tree to classify test samples.We propose a classification algorithm based on cluster similarity comparison.A normalized feature space is established according to the variance of the cluster.The target in a new frame could be got by computing the distance between test samples and the center of the cluster.Experiments show that our algorithm could achieve the goal of robust tracking under complicated conditions.

object tracking；multiple classifiers；online learning；Haar-like feature

TP391.41

A

0372-2112（2016）04-0821-05

電子學報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.010

2014-11-15；

2015-07-31；責任編輯：李勇鋒

國家自然科學基金（No.61472289）；湖北省自然科學基金（No.2015CFB254）