在線機器學習跟蹤算法的研究進展

鐘必能，陳雁，沈映菊，陳鍛生，陳維斌

（華僑大學 計算機科學與技術學院，福建 廈門361021）

在計算機視覺領域，目標跟蹤有著廣泛的應用［1－3］.基于在線學習的目標跟蹤，把跟蹤看作分類問題，用在線機器學習算法來處理目標跟蹤.與傳統離線機器學習相比，在線機器學習算法應用更加廣泛和靈活，尤其是在跟蹤目標非特定，以及目標在跟蹤過程中變化大的情況.因此，隨著在線機器學習算法的迅速發展，基于在線學習的目標跟蹤算法成為近幾年的研究熱點之一.視頻是三維物體向二維平面的投影，復雜場景中噪聲、遮擋、背景干擾和目標表觀的變化等都給目標跟蹤帶來極大挑戰［4］.一個好的目標跟蹤算法，一般得滿足如下3點要求［5］：1）魯棒性，即在在復雜條件下，跟蹤算法也能很好地跟蹤目標；2）適應性，即跟蹤算法能夠自適應處理目標自身及其周圍背景的變化；3）實時性，即目標跟蹤需要實現對視頻流的實時處理.本文對基于在線機器學習的目標跟蹤算法的研究現狀進行比較和分析.

1 跟蹤器關鍵技術

目標描敘模型是跟蹤器中關鍵的一環，它和最終的跟蹤效果密切相關［5］.由于目標是被背景環繞的，除了考慮目標本身的模型外，還需要考慮目標周圍的背景給跟蹤器帶來的有用信息.考慮背景信息，可以使目標的描敘模型針對背景特征構建，從而獲得強的識別能力.Collins等［6］提出實時的，在候選特征空間中選擇最能區別目標和背景的特征來構建前景和背景模型，巧妙地把背景信息融入前景描敘模型建立的過程，獲得魯棒的跟蹤結果.如果背景中物體（特征塊）和跟蹤目標在運動上有一定關系，可以假設背景中的物體（特征塊）與目標的相對位置在短時間內不變，用背景物體（特征塊）和前景模型共同定位跟蹤目標的位置［7］.在目標跟蹤中，背景中有很多臨時但和跟蹤目標有很強關聯的非目標物體.

跟蹤器要有強的適應性，目標的描敘模型需要實時更新.建立自適應的模型后，用估計出來不精確的前景和背景區域來更新目標模型時，就會使目標模型的質量下降，最終發生目標漂移.在視覺領域，有很多研究者提出減少自適應模型漂移問題的方法，如在線學習過程中加入結構限制［8］，用多實例學習來更新分類器［9］，使用半監督范式更新Boosting分類器［10］，使用多分類器融合［11－13］，提出對野點魯棒的方法［14］，等等.這些方法都能在不同程度上減少自適應模型的漂移問題.但對于長時間的跟蹤，模型的更新仍然是一個非常具有挑戰性的問題.

如何有效在當前幀中搜索目標位置，是保證精確度下提高實時性的重要方向.由于跟蹤的特殊性，目標在當前幀的位置只可能出在前一幀目標位置的周圍.因此，可以使用粒子濾波［15］等隨機搜索策略來搜索目標.與窮盡搜索相比，隨機搜索策略主要優勢就是在跟蹤過程中減少采樣圖像塊數目.然而，粒子濾波也有自身的問題，即容易出現優秀粒子貧乏的問題.很多學者提出方法來解決這個問題，如LU等［16］采用RANSACK和粒子濾波的混合采樣策略來解決好粒子貧乏的問題.

2 基于在線Boosting的目標跟蹤算法

大多數Boosting方法都是離線學習，訓練和分類器預測是分開的.有研究者把隨機過程及優化方法與分類器更新結合起來，實現在線的機器學習.但不管是引入隨機過程還是優化方法，都需要解決兩個問題：1）在訓練樣本依次送給分類器時，如何更新分類器；2）如何高效地在所有候選弱分類器中挑選好的分類器來Boosting.

Avidan［17］提出使用AdaBoost方法來結合若干弱分類器，構成一個比較強的分類器，用獲得的強分類器對當前幀像素點進行二值分類，產生置信圖，使用MeanShift進行目標定位.即為了解決分類器對目標外觀變化的適應性，在每一幀跟蹤完成后，會在訓練一些新的弱分類器來替換在當前幀性能較差的弱分類器.算法最大亮點就是分類器在線更新以適應目標外觀變化.

Oza等［18］提出在訓練Boosting分類器時，把Possion過程與在線更新弱分類器權值相結合來更新分類器，徹底改變離線狀態下訓練樣本批量處理的方式.從理論上可以證明，當在線分類器獲得的樣本數達到一定數目后，其性能只稍遜離線訓練的分類器.

Grabner等［19］把在線Boosting算法引入計算機視覺領域，用于Boosting的弱分類器都是從對應的特征池挑選出來的當前最優弱分類器.在用于Boosting的分類器數目相同的情況下，Grabner的在線學習算法比Oza的適應能力更強，更能獲得當前樣本模式.

Liu等［20］用基于梯度尋優的算法來選擇最優的弱分類器.該方法比隨機方式效率更高地找到較優的分類器.Saffari等［21］首次將在線學習與多類Boosting結合，其認為二值分類和基于二值分類的多類別分類通常不能完全獲得特征空間中類別的結構和關系.Saffari把離線線性規劃Boosting拓展到在線學習領域［22］，并把在線多類別Boosting轉化為一個線性規劃領域的優化問題，通過原－對偶梯度下降策略來解決這個優化問題.該算法不需要事先指定類別數，能在線根據需要添加新類別.在目標跟蹤中，把快速變化、復雜和雜亂目標背景當做單一類別處理是不合理的，在線多類別Boosting能自適應調整背景對于類別數，使得跟蹤器更加魯棒.

Grabner等［10］為緩解跟蹤中的漂移問題，把半監督的Boosting引入到跟蹤領域［23］.Grabner提出的在線半監督Boosting和其在文獻［19］中提出的在線Boosting最大區別，就是能夠使用沒有標記的樣本來更新分類器模型.該算法對沒有標記的樣本有一個動態變化的偽標記，即可以用在線Boosting來組合弱分類器.在為更新分類器獲取訓練樣本時，可以在最有可能是目標的位置周圍隨機抽取圖像塊（無標記），使用這些圖像塊來更新分類器.

3 基于森林的目標跟蹤算法

隨機森林及由隨機森林衍生得到的霍夫森林主要有以下4個優點：1）算法簡單，訓練和分類速度很快；2）容易并行處理及在當前流行的多核、GPU框架中實現；3）隨機森林能很自然處理多類問題；4）相對于Boosting及其他組合弱分類器的方法，隨機森林對樣本錯誤標記更加魯棒.通常隨機森林是離線訓練，其具有和離線算法共通的內存消耗大、自適應弱、目標特定等缺陷.實現在線隨機森林主要有3個思路：1）在一定規則指導下，在線的生成樹的節點；2）樹結構不變，在線更新葉子節點統計信息；3）融合前兩種在線策略.

Saffar等［14］用在線Bagging和極度隨機樹來實現在線隨機森林.由于硬分裂規則，決策時的遞歸特性使得發生的誤差無法修正，進而使基于隨機森林的在線學習成為一個困難的問題.Saffar把在線Bagging［18］和特征隨機選擇的在線決策樹結合，使用算法時加權遺忘，并以新樹替換舊樹的方法來減小以前的樣本對當前森林的影響.

Schulter等［24］使用文獻［14］中的決策樹在線生成規則生成在線霍夫森林.文獻［25］用霍夫森林代替ISM中的碼本，用投票機制來檢測和跟蹤目標.霍夫森林是從訓練數據學習到的一些決策樹組成一顆森林，森林中每一顆樹可以把圖像或者視頻元素中的局部表觀對應到樹的葉子節點，每個葉子節點存有向霍夫空間投票的投票向量及其投票權重.該文中隨機森林結構是離線訓練的，在跟蹤過程中實時更新葉子節點的統計信息.利用跟蹤結果，向森林反饋那些投向目標的投票向量，對這些投票向量加大權重.利用這種反饋機制使跟蹤效果更加魯棒.

Godec等［26］提出一種在線霍夫森林算法及一種基于分割的精確目標表示.該算法用邊界框表示非剛性目標，即使目標定位準確，還是會在森林在線自學習過程中引入大量噪聲.基于分割的精確目標表示能夠很好地處理非剛性目標，是因為分割后的目標能夠減少很多錯誤標記的訓練樣本.Godec等把霍夫森林拓展到在線領域，把基于投票的檢測、反向投票，以及GrabCut分割聯合起來，很好地處理跟蹤問題.為了讓森林中的決策樹有強的泛化能力，把樹的分裂測試和閾值的選擇都隨機化.由于完全隨機化無法保證樹的表達能力，有些樹的大多數葉子節點會很稀疏.為了解決這個問題，該算法先生成很多樹，然后在這些樹中挑選表達能力強的一些樹來組成森林，即不僅保證森林的泛化能力，又具有一定表達能力.該算法采用在線更新葉子節點統計信息的方法來使森林適應目標變化，其分割過程采用反向投票機制獲得分割算法的前景種子，接著用Grabcut來進行粗略分割，并用分割得到的結果更新森林葉子節點的統計信息.

4 在線協同訓練

協同訓練（co－training）是一種半監督學習技術［27］，需要同一數據的不同角度的特征.協同學習首先從每個特征角度用標記樣本學習一個分類器；然后，用這些相互獨立的分類器來對未標記的數據進行預測.每個分類器都會對樣本預測都有置信度.挑選置信度較高的作為有標記的訓練樣本來更新與之相對的分類器，增強分類器的能力.從協同學習的角度來看，前面介紹的兩種目標跟蹤算法都是自學習方式，即用自己的預測結果來更新自己.自學習方式無糾錯機制，容易倒置誤差積累，最終發生漂移.

Tang等［28］把在線支持向量機和協同訓練結合到一起，實現魯棒跟蹤.首先使用相互獨立的特征（顏色直方圖和HOG特征）訓練兩個獨立SVM分類器；然后，使用SVM遍歷下一幀視頻，得到兩張置信圖，把置信圖融合，定位目標位置；最后，使用協同訓練方式在線更新SVM分類器.

Liu等［29］提出在協同訓練框架下的Boosting誤差上界來指導跟蹤器的更新.該算法使用協同訓練框架下衍生來的Boosting誤差邊界［30］來指導協同訓練和Boosting的結合.多視角分類器之間的不一致率很大可能就是分類器誤差上界.每一輪Boosting從兩個獨立特征池中挑選出兩個視角獨立的弱分類器，最小化分類器誤差上界來協同挑選兩個視角的弱分類器.多輪挑選后，把從這些兩個視角得到的多個弱分類器加權組合成強分類器.

Leistner等［31］提出使用多視角的在線隨機森林來做跟蹤，使用多角度特征訓練不同隨機樹組成多視角森林.在線更新樹時，用Bagging方法從森林中隨機采樣一些樹（不能包括更新的樹）組成子森林對無標記樣本進行標記，然后用標記的樣本更新樹.這樣使得同一樣本更新不同樹時有可能出現不同標記，使森林更加魯棒.由于很難保證不同特征之間完全獨立性，因此也有可能造成模型更新時誤差累積.

5 多跟蹤器融合

單個分類器都有自身的缺陷，如果有好的方式把這些跟蹤器融合起來，肯定能夠增加跟蹤器的魯棒性.融合的關鍵在于選取用于融合的跟蹤器及融合的機制.

Stalder等［32］提出分類器系統的思想.該系統由三類分類器構成，即離線訓練得到的分類器（檢測器）；在線有監督分類器（識別器）；在線半監督分類器（跟蹤器）.離線分類器找到目標可能區域，該分類器的要求是泛化能力強，能夠應用到任何場景.在線有監督分類器是特定目標的識別器，識別器只需要能在特定場景中有效.在線半監督分類器作用是在下一幀跟蹤識別器識別到的目標.把跟蹤得到的目標樣本通過檢測器檢測后最終用來更新識別器.該算法有效解決了半監督學習［10］中先驗分類器固定不變對半監督學習效果的影響.

Santner等［12］提出把基于模板相似度的跟蹤算法（穩定）、基于光流的均值漂移算法（適應性強）及基于表觀的在線隨機森林（適應性適中）3個跟蹤算法用分層方式結合起來，通過并行處理實現實時跟蹤.此外，Stenger等［33］還提出使用多個跟蹤器來跟蹤目標，對每個跟蹤器單獨進行評估，用跟蹤器中結果最好的或者用所有結果的組合作為最終結果.算法首先離線訓練獲得置信度和跟蹤誤差之間的關系，然后利用學習到的對應關系來在線評估跟蹤器性能，根據當前幀各個跟蹤器性能來融合跟蹤器.文獻［33］提出兩種融合方式：1）并行啟用多跟蹤器，挑選最優或者加權組合跟蹤器結果；2）跟蹤器依次啟用，一旦有一個跟蹤器性能超過設定的性能閾值，該跟蹤器結果作為跟蹤結果（其他跟蹤器就不啟動）.

Zhong等［13］把跟蹤問題視為弱監督學習問題來解決.把多個跟蹤器看做多個標記源，使用弱監督學習來得到目標位置，以及在線評估每個跟蹤器的性能.與文獻［33］相比，該算法不需要離線獲得跟蹤器性能與某個可觀測變量之間關系，而是通過EM算法迭代獲得最優的標記結果和各跟蹤器的精度.

6 算法性能比較與分析

目前，跟蹤算法的評價主要有定性評價和定量評價兩種方法.定量評價與定性評價相互補充，使得評價效果更為完善和充分.通過在公共的視頻數據庫上，使用視頻跟蹤算法來跟蹤同一目標，跟蹤器得到的目標位置與真實的目標位置的偏差來評估算法的跟蹤精度.

總的來說有3種主要計算方法：1）跟蹤到目標的幀數占全部視頻幀的比例；2）從視頻每一幀跟蹤器得到的目標位置和實際位置偏差所獲得的目標位置偏差圖；3）計算跟蹤器得到的目標框與真實目標框之間的重疊面積占所有面積的比例.

為了對目前系統有一個直觀的認識，對一些典型算法的實驗結果和所采用方法的特點進行比較，結果如表1所示.從表1可以看出：使用基于在線機器學習的方法，越來越優秀的機器學習算法、更加有效地在線學習策略、以及跟蹤算法與分割算法的協調或跟蹤算法與檢測算法的協同等，可以極大地改進的跟蹤算法的精度.但是由于每一種跟蹤算法都有其自身的優點和缺點，因此通常情況下只能處理某一些特定類型的變化，很難確保某一特定類型的跟蹤算法能夠處理復雜跟蹤場景中的所有不確定因素.

表1 典型跟蹤算法的比較Tab.1 Comparison of the typical tracking algorithms

7 總結與展望

基于自學習的方法使用自身對樣本的標記來更新模型，容易引入錯誤標記的樣本，并且容易產生誤差積累，最終發生目標漂移.為了解決自學習的漂移，有些研究者提出不對新樣本進行確切的標記，而用半監督的方式來處理這些樣本，減少漂移.雖然半監督學習能夠解決一些漂移問題，但當實際目標跟蹤發生很大變化時，先驗分類器無法對當前目標的預測給予很大置信度，就弱化了半監督過程，也容易發生漂移.目前，有研究者提出多先驗（先驗更新）的半監督學習［32］來解決單純半監督的問題.

此外，一些研究者提出使用協同訓練的方式來解決目標漂移過程，同一樣本提取獨立的兩類特征，訓練兩個獨立的分類器，使用協同方式來在線更新分類器.由于很難保證特征之間的獨立性，因此可能會造成模型更新時誤差累積.由于單一跟蹤器總是有其不足之處，有一部分研究者從多跟蹤器融合的角度來處理漂移問題.

從總的思路來看，本文認為可以從3個方面入手來解決漂移問題.1）提出新的魯棒在線學習算法，使其能夠有魯棒跟蹤結果；2）對在線分類器獲得的目標位置使用其他方法進行修正，如使用分割算法修正目標位置；3）使用多跟蹤器的融合，實現魯棒跟蹤.

［1］韓崇昭，侯志強.視覺跟蹤技術綜述［J］.自動化學報，2006，32（4）：603－617.

［2］譚鐵牛，王亮，胡衛明.人運動的視覺分析綜述［J］.計算機學報，2002，25（3）：225－237.

［3］章毓晉，賈慧星.車輛輔助駕駛系統中基于計算機視覺的行人檢測研究綜述［J］.自動化學，2007，33（1）：84－90.

［4］YILMAZ A，JAVED O，SHAH M.Object tracking：A survey［J］.ACM Computing Surveys，2006，38（4）：13－20.

［5］YANG Han－xuan，SHAO Ling，ZHENG Feng，et al.Recent advances and trends in visual tracking：A review［J］.Neurocomputing，2011，74（18）：3823－3831.

［6］COLLINS R T，LIU Yan－xi，LEORDEANU M.Online selection of discriminative tracking features［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1631－1643.

［7］GRABNER H，MATAS J，VAN G L.Tracking the invisible：Learning where the object might be［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：1285－1292.

［8］KALAL Z，MATAS J，MIKOLAJCZYK K.PN learning：Bootstrapping binary classifiers by structural constraints［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：49－56.

［9］BABENKO B，YANG M H，BELONGIE S.Visual tracking with online multiple instance learning［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.Colorado：IEEE Press，2009：983－990.

［10］GRABNER H，LEISTNER C，BISCHOF H.Semi－supervised on－line boosting for robust tracking［C］∥Proceedings of the Europe Conference on Computer Vision.Marseille：Springer Press，2008：234－247.

［11］KIM T K，WOODLEY T，STENGER B，et al.Online multiple classifier boosting for object tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition Workshops.San Francisco：IEEE Press，2010：1－6.

［12］SANTNER J，LEISTNER C，SAFFARI A，et al.Prost：Parallel robust online simple tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：723－730.

［13］ZHONG Bi－neng，YAO Hong－xun，CHEN Sheng，et al.Visual tracking via weakly supervised learning from multiple imperfect oracles［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：1323－1330.

［14］SAFFARI A，LEISTNER C，SANTNER J，et al.On－line random forests［C］∥Proceedings of the International Conference on Computer Vision Workshops（ICCV Workshops）.Kyoto：IEEE Press，2009：1393－1400.

［15］ISARD M，BLAKE A.Condensation：Conditional density propagation for visual tracking［J］.International Journal of Computer Vision，1998，29（1）：5－28.

［16］LU L，DAI X T，HAGER G.A particle filter without dynamics for robust 3dface tracking［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition Workshop.Washington：IEEE Press，2004：70.

［17］AVIDAN S.Ensemble tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（2）：261－271.

［18］OZA N C，RUSSELL S.Online bagging and boosting［C］∥Proceedings of the International Conference on Artificial Intelligence and Statistics.Florida：IEEE Press，2001：2340－2345.

［19］GRABNER H，BISCHOF H.On－line boosting and vision［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.New York：IEEE Press，2006：260－267.

［20］LIU Xiao－ming，YU Ting.Gradient feature selection for online boosting［C］∥Proceedings of the International Conference on Computer Vision.Rio de Janeiro：IEEE Press，2007：1－8.

［21］SAFFARI A，GODEC M，POCK T，et al.Online multi－class lpboost［C］∥Proceedings of the International Conference of Computer Vision and Pattern Recognition.San Francisco：IEEE Press，2010：3570－3577.

［22］DEMIRIZ A，BENNETT K P，SHAWE T J.Linear programming boosting via column generation［J］.Machine Learning，2002，46（1）：225－254.

［23］LEISTNER C，GRABNER H，BISCHOF H.Semi－supervised boosting using visual similarity learning［C］∥Proceedings of the International Conference of Computer Vision and Pattern Recognition.Alaska：IEEE Press，2008：1－8.

［24］SCHULTER S，LEISTNER C，ROTH P M，et al.Online hough forests［C］∥Proceedings of British Machine Vision Conference.Dundee：Springer Press，2011：1－11.

［25］GALL J，YAO A，RAZAVI N，et al.Hough forests for object detection，tracking，and action recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（11）：2188－2202.

［26］GODEC M，ROTH P M，BISCHOF H.Hough－based tracking of non－rigid objects［C］∥Proceedings of International Conference of Computer Vision.Barcelona：IEEE Press，2011：81－88.

［27］BLUM A，MITCHELL T.Combining labeled and unlabeled data with co－training［C］∥Proceedings of the eleventh Annual Conference on Computational Learning Theory.Madison：ACM Press，1998：92－100.

［28］TANG Feng，BRENNAN S，ZHAO Qi.Co－tracking using semi－supervised support vector machines［C］∥Proceedings of the International Conference of Computer Vision.Rio de Janeiro：IEEE Press，2007：1－8.

［29］LIU Rong，CHENG Jian，LU Han－qing.A robust boosting tracker with minimum error bound in a co－training framework［C］∥Proceedings of the International Conference on Computer Vision.Kyoto：IEEE Press，2009：1459－1466.

［30］DASGUPTA S，LITTMAN M L，MCALLESTER D.Pac generalization bounds for co－training［C］∥Proceedings of the Advances in Neural Information Processing Systems.Whistler：MIT Press，2002：375－382.

［31］LEISTNER C，GODEC M，SAFFARI A，et al.Online multi－view forests for tracking［J］.Pattern Recognition，2010，6327（10）：493－502.

［32］STALDER S，GRABNER H，VAN G L.Beyond semi－supervised tracking：Tracking should be as simple as detection，but not simpler than recognition［C］∥Proceedings of the International Conference on Computer Vision Workshops.Kyoto：IEEE Press，2009：1409－1416.

［33］STENGER B，WOODLEY T，CIPOLLA R.Learning to track with multiple observers［C］∥Proceedings of the International Conference on Computer Vision and Pattern Recognition.Florida：IEEE Press，2009：2647－2654.