基于稀疏子空間選擇的在線目標跟蹤

黃丹丹　　孫怡

基于稀疏子空間選擇的在線目標跟蹤

黃丹丹1孫怡1

本文在粒子濾波框架下提出一種基于稀疏子空間選擇的兩步在線跟蹤方法.在跟蹤的第一步，利用稀疏子空間選擇算法篩選出與目標狀態相似性較高的候選區域，并將目標與背景間的過渡區域定義為單獨的類別以降低目標發生漂移的可能；第二步則通過構建有效的觀測模型計算候選區域與目標狀態間的相似性，其中相似性函數綜合考慮二者在整體和局部特征上的相似性，且將目標的原始狀態和當前狀態都作為參考，因此增強了觀測模型的可靠性；最后利用最大后驗概率估計目標狀態.此外，該算法通過對目標數據的更新來適應目標的表觀變化.實驗結果表明該算法能有效處理目標跟蹤中的遮擋、運動模糊、光流與尺度變化等問題，與當前流行的9種跟蹤方法在多個測試視頻上的對比結果驗證了該算法的有效性.

目標跟蹤，表觀變化，稀疏子空間選擇，粒子濾波

引用格式黃丹丹，孫怡.基于稀疏子空間選擇的在線目標跟蹤.自動化學報，2016，42（7）:1077-1089

目標跟蹤是對視頻序列中的目標進行狀態估計的過程，它是特征提取、目標檢測等底層視覺技術的輸出，同時為行為判定、語義理解等高級視覺分析提供輸入信息，在整個視覺處理流程中起到承上啟下的作用.盡管研究者們提出了大量的跟蹤算法［1-3］，但是由于形變、光照、遮擋等原因導致了目標表觀的復雜變化，使得目標跟蹤仍是計算機視覺領域的研究難點.

一般來說，一個跟蹤系統最重要的兩個組成部分是運動模型和觀測模型.其中運動模型對目標在當前情況下所有的可能狀態進行預測，常見的運動模型包括卡爾曼濾波［4］、粒子濾波［5］等.觀測模型則用于計算每個候選狀態與目標間的相似性，通常根據目標表觀建模的方式確定，例如基于稀疏表達的跟蹤方法常采用重建誤差作為度量標準［6-9］，而基于直方圖的建模方法則用直方圖相似進行計算［10-11］.由于觀測模型與目標表觀建模密切相關，因此對目標表觀進行精確而魯棒的描述是成功跟蹤的基礎.根據表觀建模的方式不同可將現有的跟蹤方法分為兩類，分別是生成式方法［12-15］和判別式方法［16-19］.

生成式跟蹤方法首先對目標表觀建模，然后在視頻序列中搜索與目標模型最相似的區域來跟蹤目標.增量視覺跟蹤（Incremental visual tracking，IVT）［12］基于低維子空間的方法對目標建模，并通過子空間的增量學習對模型進行自動更新以適應表觀變化.視覺跟蹤分解（Visual tracking decomposition，VTD）［13］將運動模型和觀測模型分為若干個小模型，通過這些小模型對目標的表觀進行更精確的描述，因此該方法在目標表觀發生變化時仍能比較準確地捕捉到目標的位置.此外，文獻［14］利用稀疏表示技術對目標區域進行稀疏編碼來表征目標，并通過均值漂移搜索具有最小重建誤差的區域作為跟蹤結果；而超像素跟蹤（Superpixel tracking，SPT）［15］則采用中等視覺線索— 超像素來描述目標表觀，并定義置信圖計算候選區域與目標模型間的相似性.生成式跟蹤方法不考慮目標與背景之間的區分性，因此當目標處于復雜背景時，很難保持穩定的跟蹤.判別式方法則將目標跟蹤建模為二類的分類問題，通過訓練目標表觀分類器來跟蹤目標.典型的判別式跟蹤方法如多樣例跟蹤（Multiple instance learning，MIL）［16］將目標附近的多個區域定義為正樣本包，以此來緩解跟蹤中的漂移問題.跟蹤學習檢測（Tracking learning detection，TLD）［17］則更關注目標的結構性，它將檢測與跟蹤相結合，并在訓練中根據樣本結構性限制不斷修正分類器從而得到更好的跟蹤結果.文獻［18］將圖像的稀疏編碼作為特征來表征樣本，并訓練一個線性支持向量機來區分目標與背景.判別式跟蹤方法雖然考慮了目標與背景之間的判別性，但是在跟蹤中常會由于累積誤差而導致模型的漂移.在以上兩種方法的基礎上，文獻［20］構建了一個基于稀疏表示的聯合模型，利用生成式方法和判別式方法聯合跟蹤目標，跟蹤的結果則由兩種方法共同決定.

上述方法從不同角度對目標表觀進行建模，針對跟蹤中的難點提出各自的解決方法，但是這些方法都需要對所有的候選區域構建表觀模型，然后從其中選擇與目標最接近的作為跟蹤結果.然而實際上，根據運動模型獲得的候選狀態中僅有少數與目標狀態接近，大部分候選狀態都與實際狀態具有較大的偏離，因此對所有候選狀態進行建模不僅造成大量的冗余計算，而且這些候選區域具有不同的表觀特性，這種表觀復雜性也加大了跟蹤中表觀建模和觀測建模的難度.針對這一問題，本文在粒子濾波框架下提出一種兩步的在線跟蹤方法.在跟蹤的第一步，該方法首先根據指定的目標區域構造目標數據；然后利用該數據張成的子空間對候選區域進行預處理，提取出少量與目標狀態最接近的候選狀態，這個預選的過程通過稀疏子空間選擇算法實現.在跟蹤的第二步，則對這些選出的候選狀態構建簡單有效的聯合觀測模型，最后根據最大后驗概率估計目標狀態.與現有的跟蹤方法不同，本文提出的方法對采樣得到的候選狀態進行預處理，在減少候選狀態個數的同時還提高了候選狀態的“質量”，即：保留的候選狀態比其他狀態更接近目標.這使得該算法不必為了區分多樣化的候選狀態而對目標的表觀進行復雜的建模，在避免了冗余計算的同時也使得模型的設計更簡約有效.在多個測試視頻上的跟蹤結果驗證了本文算法的有效性.

1　基于相異性的稀疏子空間選擇算法［21］

稀疏子空間選擇是指從大量的源數據中找到一個子空間，該子空間能夠保留所有目標數據的關鍵性質，構成子空間的元素也稱為“代表”或“樣例”.在視覺系統中，尤其是在視頻處理中，稀疏子空間選擇算法能夠將大量的圖像有針對性地進行聚類并獲得聚類中心［22］. 基于相異性的稀疏子空間選擇算法（Dissimilarity-based sparse subset selection，DS3）將該問題描述如下：已知源數據和目標數據利用某種度量標準計算X、Y中元素之間的相異性，根據二者的相異性矩陣計算X中數據對Y中元素的表達系數.首先介紹源數據X和目標數據Y之間的相異性矩陣D，該矩陣定義如下：

式中，‖·‖p表示lp范數；I（t）表示指示函數，當t=0時，函數值為0，否則值為1.式（3）中，目標函數的第1項用于約束表達Y所使用的元素個數，即尋找的子空間中所包含的元素個數，第2項約束的是X表達Y所需要的整體代價，第3項約束的是Y中奇異元素的個數，即Y中不能用X表達的元素的個數為平衡前兩項約束的參數，wj>0是懲罰因子，ej∈［0，1］表示是奇異元素的概率.式（3）可以通過乘數交替方向算法（Alternating direction method of multipliers，ADMM）［23］求解.系數矢量zzi中只有少量元素非0，所以式（3）也可視為信號的稀疏表示問題.由于子空間選擇算法的目的就是從源數據中找到能夠表達目標數據的子集合，因此在根據式（3）求得優化解Z?之后，可以通過數值的大小來確定子集合中的元素.如果X中的第i個元素對應的系數矢量zi滿足則為子集合中的元素，其中μ為約束系數，本文中取值為0.2.為后文表述方便起見，將子集合記為其中lc為元素 xxlc在源數據集合X中的索引，C為子集合中元素的個數.從子集合的選擇過程可知，C的值與源數據和目標數據有關，是根據式（3）的計算結果自動確定的.那么自然地，目標數據集合中的元素可以用子集合中的元素稀疏地表示，可以通過下式進行聚類，

從以上描述可知，已知源數據X和目標數據Y，通過DS3算法不僅可以找到X的一個低維子空間去描述Y，還能夠根據這種描述關系將源數據自動聚類，并為目標數據中的每個元素分配類別.本文將目標跟蹤中的候選區域作為源數據X，利用目標模板與背景模板構建目標數據Y，根據上述DS3算法將候選區域聚類，并為目標數據分配類別，選出與目標模板同類別的候選區域進行后續跟蹤處理，以減少冗余計算并降低觀測建模的復雜性.

圖1　源數據（樣本）示意圖（（a）采樣得到的候選區域；（b）歸一化的候選圖像）Fig.1　Sketch map of source data（samples）（（a）Candidates obtained by sampling；（b）Normalized candidates）

2　基于稀疏子空間選擇的兩步目標跟蹤方法

本節著重介紹提出的兩步跟蹤算法，首先給出源數據與目標數據的構造方法；然后介紹如何利用DS3算法對候選區域進行預處理；之后提出本文使用的相似性函數，最后給出目標數據的在線更新方法.

2.1源數據與目標數據的構造方法

從上節可知，DS3算法從源數據張成的空間中尋找一個低維子空間來表達目標數據.本文將候選區域作為源數據，具體做法為：首先利用粒子濾波算法對目標狀態進行采樣，然后將采樣得到的候選區域進行歸一化，再對歸一化后的圖像進行列向量化就得到源數據其中是第個候選區域經過列向量化后得到的向量，d為的維數，m 為候選區域的個數.構造源數據的過程如圖1所示，圖1（a）中矩形框內的圖像為采樣得到的候選區域，圖1（b）是經過歸一化的候選圖像.

目標數據是待表達的數據，本文根據指定的目標區域和背景區域進行目標數據的構造.從現有的跟蹤方法可知，在目標建模時加入判別信息后會得到更好的跟蹤結果［17-18］.大部分方法中，判別信息指的是目標和背景之間的差別信息，例如在基于稀疏表示的方法中，判別信息一般體現為利用目標模板和背景模板構造字典［18-19］.但是在實際中，目標區域與背景區域之間還存在過渡區域，如圖2（a）中右側上數第2個示意圖所示.由于目標建模的方法不同，對過渡區域的處理也各不相同.在MIL跟蹤中，將這部分區域作為正樣本來包容跟蹤中產生的模型漂移，而在文獻［20］中則將其作為負模板以減少狀態估計的誤差.在本文提出的跟蹤方法中，將過渡區域作為獨立的一類，因此目標數據由三部分構成，分別是目標模板P=｛ pppi|i=1，···，n1｝、過渡模板H= ｛ hhhi|i=1，···，n2｝和背景模板G=｛ gggi|i=1，···，n3｝.這三類模板的位置分布分別如圖2（a）中右側三個示意圖所示，具體的模板圖像由左側的矩形框表示.其中目標模板由目標區域向各個方向分別平移得到，背景模板從背景區域采樣得到，過渡模板則在二者之間由采樣得到，這三類模板在圖2（a）中分別用實線、虛線和點劃線的矩形框表示.對這些模板進行歸一化和列向量化處理，即可得到由三類模板構成的目標數據其中n=n1+n2+n3為模板個數的總和，經過歸一化的模板如圖2（b）所示.

圖2 目標數據（模板）示意圖（（a）模板分布示意圖；（b）歸一化的模板圖像）Fig.2　Sketch map of target data（templates）（（a）Sketch map of template distributions；（b）Normalized templates）

2.2基于DS3的候選區域預處理

按照上節的方法將源數據X和目標數據Y構建完成后，根據歐氏距離計算二者之間的相異性矩陣D，即通過求解式（3）可找到X的一個低維子空間用于描述Y，同時源數據X可根據表達系數矩陣Z自動聚類，目標數據Y可根據式（4）進行分類，圖3給出了這一過程的示意圖.圖3（a）為樣本圖像，也即源數據X；圖3（c）則是X的聚類結果，其中每個橢圓代表一類，不同線型的橢圓代表不同的類別.圖3（b）表示的是目標數據Y，圖像的外接矩形框給出Y中每個模板在圖3（c）中所屬的類別，例如目標模板 pp1的外接矩形為實線，那么 pp1與圖3（c）中實線橢圓內的候選區域屬于同一類別，其他模板的類別以此類推.從圖3可知，經過DS3算法后，目標數據的每個元素都會在候選區域的聚類結果中找到對應的類別.由于目標數據由目標模板、過渡模板和背景模板構成，因此，根據圖3所示的分類結果，可以得到與目標模板處于同一類別的候選區域，如圖4所示.其中圖4（a）為目標數據中的目標模板，它代表了目標在不同時刻的表觀；圖4（b）為圖3（c）中與目標模板處于同一類別的候選區域，也就是經過預處理后保留下來的候選區域.

經過上述過程，候選狀態中與目標狀態接近的部分被篩選出來并根據觀測模型進行最終的狀態估計，而其余的則被拋棄.通過對候選區域的預處理，不僅減少了冗余計算，而且保留下來的候選區域的表觀更趨于單一化，更有利于目標的狀態估計.本文能成功地對候選區域進行預處理，主要有以下三個原因：一是根據稀疏表示系數篩選候選區域能夠有效地適應目標的表觀變化，由于大量基于稀疏表示的跟蹤方法已經證明了稀疏模型能夠處理局部遮擋、局部形變以及光流、尺度和位姿變化對目標表觀的影響，而本文提出的粒子預判方法又是基于源數據對目標數據的稀疏表示系數，因此繼承了基于稀疏表示的模型對目標表觀變化的適應能力，從而使粒子預判的結果更加準確.二是采用DS3算法對候選區域進行聚類不需要預先規定類別個數，而是完全根據數據本身的特點自動聚類，避免了由于硬性規定聚類個數而導致的聚類誤差，并使得同一類別內的候選區域具有更強的相似性.三是將過渡模板加入到目標數據中，使得偏離真實狀態較小的候選區域也能被分離出來，降低了這部分候選區域被保留的可能性，這也保證了選出的候選區域更接近真實的目標狀態.

圖3　目標數據（模板）和源數據（樣本）聚類示意圖（（a）樣本示意圖；（b）模板以及聚類結果；（c）樣本聚類結果）Fig.3　Sketch map of target data（templates）clustering and source data（samples）clustering（（a）Sketch map of samples；（b）Templates and clustering results；（c）Samples clustering results）

圖4　粒子預判示意圖（（a）目標模板示意圖；（b）與目標模板屬于同一類別的樣本示意圖）Fig.4　Sketch map of particles pre-filter（（a）Sketch map of target templates；（b）Sketch map of samples that has the same classes with target templates）

2.3相似性函數

在目標跟蹤中，觀測模型用于計算候選狀態與目標區域之間的相似性，該相似性反映了候選狀態是參考目標的概率.為了更準確地估計當前的目標狀態，本文構建了一個聯合相似性函數，從整體和局部兩個方面綜合衡量候選區域與目標之間的相似性.令表示經過預處理后保留下來的候選區域為第個候選區域，T為目標模板，那么與T之間的相似性可通過下式計算：

2.4目標數據在線更新

目標的表觀在跟蹤中會由于光流、視角以及本身形變等原因而改變.隨著時間的推移，根據首幀信息構造的目標模型不能完全適應這些變化，從而導致跟蹤失敗.因此有效的模型更新是跟蹤算法能否長期穩定跟蹤的一個重要因素，本文對目標數據進行在線更新以適應目標的表觀變化.由于目標數據是由目標模板、過渡模板和背景模板三部分組成，因此需要分別進行更新.為了使更新方法更加高效，本文每5幀進行一次判斷，如果目標模板能夠很好地描述目標當前的表觀，則不需要更新.如果目標模板不能適應目標當前的表觀，則用當前的跟蹤結果取代目標模板中權重最小的模板，權重的計算方法與文獻［6］相同.同時在目標區域與背景區域之間進行重新采樣以更新過渡模板，并在背景區域采樣更新背景模板.在目標模板更新時，保留首幀中由指定的目標區域構成的目標模板以減輕跟蹤過程中的漂移.實驗結果證明該更新方法與本文提出的兩步跟蹤方法相結合，能夠準確地捕捉目標在跟蹤過程中的表觀變化，獲得更穩定的跟蹤結果.

3　兩步跟蹤算法的實現

本文提出的兩步跟蹤方法基于粒子濾波框架，粒子濾波中包含兩個重要的模型，分別是觀測模型和運動模型.令表示目標在第t幀的觀測表示目標在第t幀的狀態，本文將觀測模型定義為：

此外，運動模型建模為具有6個獨立參數的高斯分布，即：

在上述框架下，本文跟蹤方法的第1步包括根據粒子濾波方法對當前狀態進行采樣、利用DS3算法對候選狀態進行預處理.而第2步則包括對保留下來的候選區域構建觀測模型，根據最大后驗概率估計目標狀態.為了將本文算法表述的更加清楚，本節總結了該算法的各個步驟，并概括如算法1所示.

算法1.兩步跟蹤算法流程

初始化階段t=1:

在指定目標區域周圍提取目標模板，在背景區域采樣得

到背景模板，在目標區域與背景區域之間采樣得到過渡

模板，利用三類模板構造目標數據Y；

跟蹤階段:

Fort=2:FrameNum

第1步:

1）根據第t-1幀的目標狀態，利用式（9）進行狀態預測，并用候選區域構造源數據X；

2）利用DS3算法對源數據聚類，并根據式（4）對

目標數據中的每個模板進行分類；

3）選出與目標模板屬于同一類別的候選區域，進

行第2）步的處理；

第2步:

1）根據式（5）～（7）計算保留下來的候選區

取200 g飛灰，放入不銹鋼容器內，量取20%（w/w）去離子水，將穩定化藥劑溶解于水中并將水溶液均勻灑在飛灰樣品表面，充分攪拌后，自然養護7 d，將養護結束后的樣品破碎用于重金屬浸出毒性檢測。

域與目標模板間的相似性；

2）根據式（8）和式（10）估計當前目標狀態；

更新:

Ift是5的整數倍

根據第2.4節方法更新目標數據Y；

End

End

此外，值得指出的是，本文在粒子濾波框架下實現目標的跟蹤，主要是因為粒子濾波是一種比較有效的搜索策略，它采用多個隨機的采樣粒子來逼近目標真實的密度分布，可以不受狀態矢量非線性和非高斯的限制.由于粒子濾波的限制條件少，并且能夠提供目標所有可能的狀態，因此與本文提出的粒子預判方法相結合后，能夠使保留下來的粒子更加接近目標的真實狀態，從而提高跟蹤的準確程度.實際上，本文提出的粒子預判方法和目標表觀模型也可以和其他的搜索方法相結合實現目標跟蹤，如Kalman濾波和窮盡搜索等.但是Kalman濾波要求目標的運動模型和觀測模型均為線性，并且要求系統噪聲滿足高斯分布，因此當目標不滿足上述條件時容易導致跟蹤失敗.而窮盡搜索雖然能夠提供有效的采樣粒子，但是計算量太大，無法應用于自然場景下的目標跟蹤.

圖5　粒子預判算法對多余粒子的濾除性能Fig.5　Performance of the particles pre-filter algorithm for filtering the redundant particles

4　實驗結果及分析

4.1粒子預判算法的有效性分析

本節選取四個測試視頻進行粒子預判算法的有效性分析，分別是Faceocc、Singer1、Dollar和Owl序列.本節的實驗包括兩部分，一是分析算法對多余粒子的濾除情況，二是分析算法對跟蹤性能的增強情況.圖5是測試視頻在粒子預判算法對多余粒子的濾除性能，其中橫軸為初始的粒子數目，縱軸為經過粒子預判后保留下來的粒子數目，該數據是測試視頻在所有幀的平均值.從圖中可知，經過粒子預判后，保留的粒子數目有了大幅度的減少，證明了粒子預判的有效性.表1是測試視頻在粒子預判前后的平均跟蹤結果，包括中心位置誤差和重合面積參數，中心位置誤差PosErr定義為當前跟蹤結果的中心位置坐標與參考值之間的均方根，面積重合參數定義為其中Rg和Rt分別表示目標區域面積的參考值和實際跟蹤結果.表1中的數據是在初始粒子數目為300的條件下得到跟蹤結果.無預判是沒有經過粒子預判，直接對所有粒子都進行觀測.建模的跟蹤結果；有預判則是本文提出的兩步跟蹤算法的跟蹤結果.從表中可知，經過粒子預判算法后，跟蹤結果的準確性都得到了不同程度的提高，這是因為本文提出的粒子預判算法利用稀疏表示來建模目標和樣本之間的結構關系，因此繼承了稀疏表示模型對目標表觀變化的適應能力，能夠有效地去除距離目標真實位置較遠的粒子，從而提高了算法的跟蹤性能.

4.2定性分析

本節給出本文算法以及其他9種對比算法在測試視頻上的跟蹤結果，并從四個角度對這些算法的性能進行測試與比較.為了使圖片中的結果更清晰，本文只給出效果最好的5種方法的跟蹤結果并只對這5種方法的性能進行討論與分析.

表1　有無粒子預判處理的跟蹤結果對比Table 1　Tracking results comparing between the method with particle pre-filter and the method without particle pre-filter

圖6　目標存在遮擋時的跟蹤結果Fig.6　Tracking results when targets are occluded

測試1.目標存在遮擋時本文算法的跟蹤性能. 圖6（a）所示的Race序列中，目標不僅經歷嚴重的遮擋而且目標的尺度和外觀都發生了巨大的變化，從結果圖像中可知，只有本文的算法能夠在整個序列中保持穩定準確的跟蹤.在150幀，當目標幾乎被完全遮擋時，其他算法都不能對目標進行準確定位.而在576幀，盡管除了IVT外的方法都捕捉到目標的位置，但是只有本文算法能夠對目標的尺度進行正確的估計.隨著時間推移，到了719幀，除本文算法外的其余算法都已經丟失了目標，跟蹤失敗. 圖6（b）所示的Faceocc序列中，人臉圖像被頻繁地遮擋，盡管圖中所示的5種方法都能成功跟蹤目標，但是本文的算法在尺度以及定位精度上要優于其他方法，具體數值如表3所示.圖6（c）的Dollar序列中，目標紙幣經過折疊后，從目標呈現的表觀來看相當于該紙幣被部分遮擋.IVT、MIL和DSSM在紙幣被折起時，就產生了漂移，并且除MIL外其他方法并沒有在后續圖像中恢復正確的跟蹤.而本文的算法在根據稀疏子空間選擇算法對候選區域進行預處理時，將目標區域與背景區域間的過渡區域單獨定義為一類，因此減少了這部分區域被保留下來參與最終狀態估計的可能性，避免了漂移的發生.

測試2.目標由于快速運動而產生運動模糊時本文算法的跟蹤性能.Jumping序列中的目標由于快速跳躍而產生模糊，而背景區域的復雜性也增加了跟蹤的難度.IVT和Frag在構建目標模型時不考慮目標與背景間的區別信息，同時根據模糊目標圖像構建的表觀模型又不能準確地描述目標，從而導致跟蹤失敗.DSSM算法雖然利用了判別信息，但是對過渡區域所屬類別的定義并不明確，因此當目標區域存在模糊時，極易導致模型的漂移.如圖7（a）所示，DSSM的跟蹤結果總是在實際位置周圍，這說明該方法構建的目標模型雖然能在一定程度上區分目標與背景，但是模型已經產生漂移以至于不能準確地定位目標.此外SCM算法則由于其采用的聯合模型而使得跟蹤比較準確.相對于以上幾種方法，本文算法在跟蹤的第1步利用了目標與背景間的判別信息，而且將過渡區域明確規定為一個獨立的類別，在減少漂移的同時也保證了篩選出的候選區域更接近目標的真實狀態；此外，算法第2步建立的觀測模型不僅從整體與局部兩個方面綜合衡量候選狀態與目標之間的相似性，而且采用原始目標狀態和經過表觀變化的目標狀態作為相似性函數的參考標準，因此本文的觀測模型在存在模糊時仍能對目標當前的狀態進行準確地估計.圖7（b）所示的Owl序列中，目標區域的準確輪廓在快速的運動下幾乎不能用肉眼分辨.從結果圖像可見，除本文算法外，其余幾種方法都有不同程度的漂移，這說明本文算法能夠有效地處理跟蹤中由于快速運動而產生的模糊現象.

圖7　目標快速運動產生模糊時的跟蹤結果Fig.7　Tracking results when targets appearance is blurry because of quick movement

圖8　光流發生變化時的跟蹤結果Fig.8　Tracking results when targets undergo illumination changes

圖9　目標發生形變（（a），（b））以及場景中存在相似區域（（b），（c））時的跟蹤結果Fig.9　Tracking results when targets occur deforms（（a）and（b））and results when there are similar regions in scenes（（b）and（c））

測試3.光流變化時本文算法的跟蹤性能.圖8（a）所示的Singer1序列中，場景的光流與目標的尺度都發生巨大的變化.L1和LSK不考慮目標與背景間的判別信息，因此不能很好地應對光流和尺度的變化.VTD、SCM和本文算法都能在整個序列中成功地跟蹤目標，但是本文算法采用兩步跟蹤，不僅能夠減少漂移，而且由于觀測模型的有效性而使跟蹤的結果更加準確.在Car11序列中，目標車輛在低照度情況下行駛，并且在運動中伴隨著光流的變化以及由于相機抖動引起的輕微模糊.由于目標的表觀在整個序列中只發生了剛性變化，因此大多數方法都能很好地跟蹤目標.只有TLD方法從跟蹤開始不久就產生漂移，并且隨著時間推移，這種漂移越來越嚴重，如圖8（b）所示.

測試4.目標表觀發生變化或場景中存在與目標相似區域時本文算法的跟蹤性能.在圖9（a）所示的Sylv序列中，目標在不同光照下由于位姿變化而導致目標表觀的變化.雖然這幾種方法都成功地對目標進行了跟蹤，但是DSSM和TLD算法在355幀到542幀之間發生了輕微的漂移，而SCM在613幀也偏離了目標的真實位置，本文算法一直保持著穩定的跟蹤，并且取得了最好的跟蹤結果，如表2和表3所示.圖9（b）所示的Football序列中，目標經歷快速運動并且場景中存在與目標相似的區域.從結果圖像可見，IVT與Frag在181幀開始產生偏移，在309幀，VTD與DSSM也產生漂移，只有本文算法在整個序列中都能正確地估計目標的狀態，從而保持著準確的跟蹤結果.在Stone序列的背景中存在大量與目標類似的區域，這些區域增大了發生錯誤跟蹤的可能性.在387幀，當目標被部分遮擋時，VTD將遮擋物誤認為是目標，并在后續跟蹤中無法恢復.而IVT、TLD與SCM在跟蹤中不能很好地處理目標的尺度變化，對比而言，本文算法的跟蹤結果取得了較小的定位誤差，同時與參考目標具有最大的重合面積.

表2　跟蹤結果的平均中心位置誤差（像素）Table 2　Average center location errors of tracking results（pixel）

表3　跟蹤結果的平均面積重合誤差（像素）Table 3　Average overlap scores of tracking results（pixel）

4.3定量分析

本節采用中心位置誤差PosErr和面積重合參數SC對所有跟蹤算法的性能進行定量分析.表2、表3分別給出包括本文算法在內的10種跟蹤方法在10個測試視頻上的跟蹤結果，分別為跟蹤結果的平均中心位置誤差和平均面積重合參數，其中最優以及次優的跟蹤結果分別用粗體和斜體表示，“—”表示跟蹤出現中斷.從表2可知，本文提出的兩步跟蹤算法在這些測試視頻上均取得最優或次優的結果，而在表3所示的重合面積參數中，本文算法在跟蹤的準確性上優于其他所有的跟蹤方法.

為了更直觀地表現所有對比方法的跟蹤結果，圖10給出了上述兩個對比結果的曲線圖，點劃線為本文算法的跟蹤結果.圖10（a）中的中心誤差越小越好，而圖10（b）中的重合參數越大越好.圖中橫軸測試視頻的序號代表的視頻序列分別為：1.Car11；2.Faceocc；3.Sylv；4.Dollar；5.Football；6.Jumping；7.Owl；8.Stone；9.Race；10.Singer1.從圖10中可知本文算法的跟蹤性能優于其他方法.

除了上述平均跟蹤結果，本文還給出了Benchmark［2］中用于衡量算法整體跟蹤性能的曲線：OPE（One-pass evaluation）的曲線下面積（Area under curve，AUC），如圖11所示.其中圖11（a）為精確度曲線，圖11（b）為跟蹤成功率曲線.從圖11可知，當誤差閾值設為20個像素時，本文算法的跟蹤精確度達到90.25%，而當成功跟蹤的閾值設為重合面積之比為0.6時，本文算法的成功跟蹤率達到75.38%，這充分說明本文算法在整個跟蹤過程中均能夠保持比較準確而穩定的跟蹤.

4.4算法的運行時間分析

本節對本文算法的運行時間進行分析.由于LSK方法要求運行環境為64位的處理器，無法與其他跟蹤方法在同一實驗平臺上實現，因此本節只對包括本文算法在內的9種跟蹤方法在相同實驗平臺上的運行時間進行對比.表4給出了這些跟蹤方法的運行時間，從表中的數據可知，本文提出的兩步跟蹤算法雖然未能達到實時的跟蹤，但是其運行時間在表中的跟蹤方法中仍然處于中上水平.此外，本文算法采用文獻［21］的作者提供的代碼進行粒子預判的計算，該代碼并沒有經過優化或并行處理，是本文算法中最耗時的部分.在測試過程中，大概有3/4的運行時間耗費在粒子預判階段，因此本文算法的計算效率仍有提升的空間.

圖10　所有跟蹤方法在全部測試視頻上的跟蹤性能（（a）平均中心誤差曲線；（b）平均重合面積參數曲線）Fig.10　Performance of all the tracking methods in test sequences（（a）Average center error curve；（b）Average overlap area parametric curve）

圖11　OPE曲線（（a）跟蹤精度的統計曲線；（b）跟蹤成功率的統計曲線）Fig.11　One-pass evaluation curve（（a）Precision plot of OPE；（b）Success plots of OPE）

表4　本文跟蹤算法與對比跟蹤算法的平均運行時間比較Table 4　Average running times comparing between the proposed method and other methods

5　總結

本文在粒子濾波框架下提出一種基于稀疏子空間選擇的兩步跟蹤算法.該算法對采樣粒子進行預處理，減少候選區域個數的同時提高了剩余候選狀態與目標真實狀態間的近似程度，從而減少冗余計算并降低了目標建模的復雜度.定義的相似性函數綜合考慮候選區域與目標狀態在整體與局部特征上的相似性，并且將目標的原始狀態和經過表觀變化后的狀態同時作為參考，因此能夠提供更為準確的觀測模型，提高目標估計的準確性.此外，該算法采用的更新策略也增強了其對目標表觀變化的適應能力.與其他跟蹤方法的對比實驗結果證明本文算法的有效性.

References

1 Yilmaz A，Javed O，Shah M.Object tracking：a survey. ACM Computing Surveys（CSUR），2006，38（4）：1-45

2 Wu Y，Lim J，Yang M H.Online object tracking：a benchmark.In：Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，USA：IEEE，2013.2411-2418

3 Smeulders A W M，Chu D M，Cucchiara R，Calderara S，Dehghan A，Shah M.Visual tracking：an experimental survey.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（7）：1442-1468

4 Kalman R E.A new approach to linear filtering and prediction problems.Transactions of the ASME，Journal of Basic Engineering，1960，82：35-45

5 Doucet A，Freitas N，Gordon N.Sequential Monte Carlo Methods in Practice.New York：Springer-Verlag，2001.

6 Mei X，Ling H B.Robust visual tracking using L1minimization.In：Proceedings of the 2009 International Conference on Computer Vision.Kyoto，Japan：IEEE，2009.1436-1443

7 Zhang T Z，Ghanem B，Liu S，Ahuja N.Robust visual tracking via multi-task sparse learning.In：Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2012.2042-2049

8 Hong Z B，Mei X，Prokhorov D，Tao D C.Tracking via robust multi-task multi-view joint sparse representation.In： Proceedings of the 2013 International Conference on Computer Vision.Sydney，NSW：IEEE，2013.649-656

9 Zhang S P，Yao H X，Zhou H Y，Sun X，Liu S H.Robust visual tracking based on online learning sparse representation. Neurocomputing，2013，100：31-40

10 Adam A，Rivlin E，Shimshoni I.Robust fragments-based tracking using the integral histogram.In：Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition.New York，USA：IEEE，2006.798-805

11 He S F，Yang Q X，Lau R W H，Wang J，Yang M H.Visual tracking via locality sensitive histograms.In：Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，USA：IEEE，2013.2427-2434

12 Ross D A，Lim J，Lin R S，Yang M-H.Incremental learning for robust visual tracking.International Journal of Computer Vision，2008，77（1）：125-141

13 Kwon J，Lee K M.Visual tracking decomposition.In：Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE，2010. 1269-1276

14 Liu B Y，Huang J Z，Yang L，Kulikowsk C.Robust tracking using local sparse appearance model and k-selection. In：Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2011.1313-1320

15 Yang F，Lu H C，Yang M H.Robust superpixel tracking.IEEE Transactions on Image Processing，2014，23（4）：1639-1651

16 Babenko B，Yang M H，Belongie S.Visual tracking with online multiple instance learning.In：Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami FL，USA：IEEE，2009.983-990

17 Kalal Z，Matas J，Mikolajczyk K.P-N learning：bootstrapping binary classifiers by structural constraints.In：Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE，2010. 49-56

18 Xie Y，Zhang W S，Li C H，Lin S Y，Qu Y Y，Zhang Y H.Discriminative object tracking via sparse representation and online dictionary learning.IEEE Transactions on Cybernetics，2014，44（4）：539-553

19 Zhuang B H，Lu H C，Xiao Z Y，Wang D.Visual tracking via discriminative sparse similarity map.IEEE Transactions on Image Processing，2014，23（4）：1872-1881

20 Zhong W，Lu H C，Yang M H.Robust object tracking via sparsity-based collaborative model.In：Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2012.1838-1845

21 ElhamifarE，SapiroG，SastryS.Dissimilarity-based sparsesubsetselection.IEEETransactionsonPatternAnalysisandMachineIntelligence， 2014.DOI：10.1109/TPAMI.2015.2511748

22 Elhamifar E，Vidal R.Sparse subspace clustering： algorithm，theory，and application.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781

23 Boyd S，Parikh N，Chu E，Peleato B，Eckstein J.Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends in Machine Learning，2010，3（1）：1-122

黃丹丹大連理工大學信息與通信工程學院博士研究生.2007年獲得長春理工大學電子信息工程學院電子信息科學與技術系學士學位.主要研究方向為視頻序列中的目標檢測與目標跟蹤.

E-mail:dluthuang@163.com

（HUANG Dan-DanPh.D.candidate at the School of Information and Communication Engineering，Dalian University of Technology.She received her bachelor degree from Changchun University of Science and Technology in 2007.Her research interest covers object detection and object tracking.）

孫怡大連理工大學信息與通信工程學院教授.1986年獲得大連理工大學電子系學士學位.主要研究方向為圖像處理，模式識別與無線通信.本文通信作者.E-mail:lslwf@dlut.edu.cn

（SUN YiProfessor at Dalian University of Technology.She received her bachelor degree from Dalian University of Technology in 1986.Her research interest covers image processing，pattern recognition，and wireless communication.Corresponding author of this paper.）

Online Object Tracking via Sparse Subspace Selection

HUANG Dan-Dan1SUN Yi1

This paper proposes a two-stage online tracking method based on sparse subspace selection in the particle filter framework.At the first stage of the tracking，those candidates that highly similar to the target state are selected using the sparse subspace selection algorithm.The transition region between target and background region is defined as a separate category to alleviate the drifting.And at the second stage，a simple but effective observation model is built to calculate the similarities between the candidates and the target.The similarity measuring function not only considers the integral and local similarities comprehensively but also uses both the original target state and the state after appearance changes as references to enhance the reliability of the measurement model.Finally，the state of target is estimated according to the maximum posterior probability.Furthermore，the target appearance changes are captured by update strategy.The experimental results show that the proposed method can effectively handle the occlusion，motion blur，as well as illumination and scale changes in tracking.Comparative results on challenging benchmark image sequences show that this method performs favorable against the 9 other state-of-the-art algorithms.

Object tracking，appearance changes，sparse subspace selection，particle filter

10.16383/j.aas.2016.c150493

Huang Dan-Dan，Sun Yi.Online object tracking via sparse subspace selection.Acta Automatica Sinica，2016，42（7）:1077-1089

2015-07-30錄用日期2016-01-23
Manuscript received July 30，2015；accepted January 23，2016本文責任編委劉躍虎
Recommended by Associate Editor LIU Yue-Hu
1.大連理工大學信息與通信工程學院大連116024
1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116024