基于Struck的在線學習和相似度匹配的雙重更新跟蹤算法

3

(1.山東科技大學 電氣與自動化工程學院，山東 青島 266590； 2.山東省機器人與智能技術重點實驗室，山東 青島 266590；3.山東大學 控制科學與工程學院，山東 濟南 250061)

視覺目標跟蹤不僅是人工智能應用中不可或缺的技術手段，同時也是計算機視覺發展的重要一環。雖然廣泛應用于人工智能機器人、航空航天技術、智能視頻監控、醫學影像處理、智能交通系統和虛擬現實等多種技術平臺[1]，但研究人員依然面臨視頻序列中對圖像目標處理的局部或全部遮擋(occlusion，OCC)、照明變化(illumination variation，IV)、比例變化(scale variation，SV)、變形(deformation，DEF)、運動模糊(motion blur，MB)、快速運動(fast motion，FM)、平面內旋轉(in-plane rotation，IPR)、平面外旋轉(out-of-plane rotation，OPR)、背景雜波(background clutter，BC)、超出視野(out of view，OV)、低分辨率(low resolution，LR)等公認復雜場景的挑戰[2-3]。

目標跟蹤的方式通常是在圖像序列的初始幀以矩形框的形式對目標位置和大小進行人工標定，之后跟隨目標的運動而跟蹤目標，并記錄位置信息。近年來，解決視覺目標跟蹤的問題基本上有兩種思路：第一種思路是依賴于跟蹤目標的先驗知識，對目標進行建模，之后在測試的序列中找到相對應的目標，既可以使用單一特征，也可以采用多特征疊加，這其中包括目標的邊緣、形狀、色彩、輪廓、紋理和光線等視覺特征[4-5]，直方圖(如灰度、顏色等)和圖像矩的統計特征、代數空間特征(K-L變換)、尺度不變特征(scale invariant feature transform, SIFT)等[6]，也是當下主流的算法思想；第二種思路是不依賴于目標的先驗知識，直接對測試序列進行運動檢測，將目標從變換的背景圖像中識別出來，并檢測目標位置達到跟蹤的效果，參照被檢測物與攝像機之間的關系，可以分為靜態背景下的目標跟蹤和動態背景下的目標跟蹤。

Struck算法依賴目標的先驗知識對目標進行跟蹤[7-9]。示例觀察發現，Struck算法在遇到遮擋，特別是目標被完全遮擋時，學習者會將遮擋物的負樣本納入到學習框架中，從而失去對目標的有效判斷。示例觀察還發現，丟失目標后，矩形框位置將不再發生變化，當目標再次移動到矩形框所在位置時，根據學習者正樣本的累計訓練，跟蹤器方能繼續跟蹤目標，從而驗證了跟蹤器在丟失目標后不能主動進行目標檢測的問題。當相同或類似的遮擋物再一次出現在目標的矩形框中，可能是遮擋目標，也可能是作為背景被目標小范圍遮擋時，跟蹤器同樣會丟失跟蹤目標。這是因為遮擋物在遮擋目標的時候學習者將遮擋物作為正樣本學習了一部分，使得跟蹤器誤認為是目標，從而再次發生目標丟失問題。本研究引入相似度匹配更新策略，與Struck算法的在線學習更新策略相結合，得到基于Struck的在線學習和相似度匹配的雙重更新跟蹤算法(下文中簡稱雙重更新跟蹤算法)，以適應目標被完全遮擋的場景，在目標丟失后能夠依據相似度匹配的方式重新搜索到目標，并繼續完成跟蹤。

1 Struck算法的在線學習更新

Struck算法在圖像序列中使用Haar特征[10-12]提取目標特征，通過在線學習的方式不斷更新目標的特征數據，并使用結構化支持向量機[13-16]對數據樣本做出最優分類，能夠適應IV、MB、IPR、LR等場景，但對OCC、OV、SV、DEF場景的適應性不夠理想。其在線學習更新過程為：

1) 通過一個預測函數f:χ→γ對幀間轉換進行直接估計，對目標圖像塊做標簽(x,y)，其中x是樣本，y是目標期望的轉換。建立一個判別函數

F(x,y)=〈w,Φ(x,y)〉

(1)

用于評判目標與學習后正樣本的相似度，其中Φ(x,y)是聯合內核映射(輸入空間到特征空間的一種轉換)。預測目標的位置函數定義為：

(2)

其中，跟蹤目標的位置更新為pt=pt-1(yt)。

2) 在給定的目標集合中，尋找超平面的最優目標函數為：

(3)

3) 基于目標邊界框重疊度定義損失函數：

(4)

4) 設計存儲系數

(5)

5) 通過使用拉格朗日公式的對偶性以及參數化將公式(3)簡化為：

(6)

(7)

2 相似度匹配更新

選擇Haar特征為特征描述算子表示圖像，使用邊緣特征模板對灰度化的圖像進行處理，將模板中的白色矩形區域的像素和減去黑色矩形區域的像素和，計算得出目標圖像塊的特征值，并保存初始模型的特征值。定義一個基于Haar特征檢測目標區域與初始模型的相似函數

(8)

其中，T0是初始模型目標區域特征值，Tz為當前幀目標區域特征值。

在獲得目標的位置估計后，將目標位置所在的圖像塊根據相似函數計算得到的值，與初始模型的特征進行相似度判別，符合閾值要求的圖像塊作為正樣本，添加到在線學習對正樣本的學習過程中。由于樣本使用的是在線學習的方式，所以最初的正樣本僅僅是一個初始模板，隨著圖像序列一幀幀的跟進，每幀中符合閾值要求的圖像塊都被當作正樣本加入到學習過程中。因為圖像序列中連續幀之間的目標是緩慢變化的，在線學習的方式也具有漸進性，相鄰幀間的目標變化較小，特征的差異也不大，所以在學習過程中容易受到影響，從而易使正樣本的學習偏離原來的目標。這就是Struck算法在遇到遮擋后不能再次搜索到目標的原因，也是設立相似函數的目的。通過相似函數計算當前幀的目標相似度，可以避免跟蹤目標的特征在學習中與初始目標的特征出現較大差異，不至于因漸進的學習而造成負樣本的誤學習，保證了正樣本學習的穩定性，對目標的判斷始終保持一個高度相似的水平，進而能夠穩定跟蹤目標。

閾值的選取可自由設定，根據公開數據集的測試結果，選取80%作為設定的閾值可以取得最佳的效果。當η≥80%時，作為正樣本被學習者學習；當η<80%時，不作為學習者的正樣本更新。當連續5幀的目標都丟失后，在下一幀圖像中采用滑動窗口的形式，遍歷搜索目標圖像所在位置，以相似度判別為依據，在自設的搜索半徑內搜索相似度η≥50%的矩形框，選擇其中相似度最高的圖像塊作為目標繼續跟蹤。這里閾值選擇為50%是因為弱分類器在對目標進行判別時，概率一般選取為大于50%，為了更好地尋找目標位置，設置了相對較低的閾值，放寬對目標搜索的條件。經過大量的視頻序列測試，選擇相似度η≥50%的矩形框作為候選目標框的分類標準，便可以判斷目標所在位置。但同樣可能出現誤判的情況，比如在球場上對球員的跟蹤，球員身著統一的服裝，對整個球員跟蹤的話，相同隊內的成員之間特征值的差異比較小。但這并不影響對目標的跟蹤，因為在放寬條件的情況下找到目標后，依然如上述步驟與初始模板的特征進行比較。如果出現誤判，那么在接下來的5幀圖像中，正樣本不會被更新，將再次重新搜索目標，以達到對目標的循環搜索。如果搜索完成后沒有滿足相似度要求的圖像塊，視為沒有發現目標，對下一幀圖像繼續做遍歷搜索處理，直到找到目標或者到達圖像序列最后一幀圖像為止。雙重更新跟蹤算法的流程如圖1所示。

算法:雙重更新跟蹤算法輸入:圖像序列并在首幀標定目標位置根據判別函數F預測第t幀目標位置yt計算yt位置圖像塊的相似度ηif η≥80%then 對正樣本進行在線學習并輸出目標位置else 停止更新正樣本并輸出上一幀目標位置if 連續5幀不更新正樣本then 對下一幀圖片進行遍歷搜索目標end ifend if

圖1 雙重更新跟蹤算法流程

Fig.1 Process of dual update tracking algorithm

由于Struck算法的速度較慢，對其跟蹤框架進行整體優化。Struck算法的在線學習更新需要不斷學習正樣本來適應目標的特征變化，對支持向量的需求比較大，通常設為100。雖然Struck算法中限制了支持向量的無限增長，但仍然允許保持相當的數量，從而降低了算法的跟蹤速度。而本研究設計的相似函數和在線學習作為雙重更新策略，不需要很多的支持向量來維持在線學習中正樣本的有效性，減少了跟蹤框架中對支持向量的需求，支持向量個數設為50，為程序的運行釋放出更多的緩存空間。在對圖像進行遍歷搜索時，滑動窗口由1×1像素擴大為3×3像素，步長為1個像素，目的在于弱化邊緣像素點的特征，強化中心點的特征。滑動窗口只有1個，輸出的通道數為1。在對圖像的特征提取時，Haar特征首先對圖像進行灰度化處理，弱化顏色特征對目標辨識的影響，輸入的通道數由原來的RGB顏色空間的3通道減少為灰度圖像的1通道。通過設計相似函數改變參數設置，從而達到提高雙重更新跟蹤算法運行速度的目的。

3 測試和實驗分析

3.1 測試環境

測試的硬件環境為64位Intel CORE i7 3.4 GHz處理器和16 GB內存的計算機，調試實驗的軟件平臺為Visual Studio 2013，程序用C++語言編寫。測試結果所用的Girl視頻圖像序列來源于OTB100的公開數據集，Cup視頻圖像序列是以課題組實驗室為背景自行拍攝的數據集。

3.2 定性分析

為了直觀地展示兩種算法的跟蹤表現，將實驗序列的跟蹤表現進行對比，其結果如圖2所示，代表雙重更新跟蹤算法，灰色代表Struck算法。

由圖2可以看出，在室外場景中，Girl視頻(640×480)存在SV、OCC、BC、DEF、LR等復雜場景，目標小女孩在被成年人完全遮擋時，目標在視頻中消失，雙重更新跟蹤算法在目標特征明顯出現時，可以再次捕捉到目標位置并繼續跟蹤。而Struck算法目標被遮擋時已經丟失目標，其正樣本的在線學習過程中引入了負樣本的誤學習。在室內場景中，Cup視頻(1 280×720)存在SV、OCC、LR、MB等復雜場景，目標杯子在運動的過程中，遇到障礙物對其完全遮擋，消失于圖像范圍之內，當目標具有的明顯特征再次出現時，雙重更新跟蹤算法能夠重新捕捉到目標，并繼續跟蹤。而Struck算法在遮擋時丟失目標，當目標再次出現時不能自動尋找到目標，只有在目標重新出現在丟失位置時，才能繼續跟蹤，對于實際跟蹤的場景中具有很大的局限性。

3.3 定量分析

為了更直觀地對比兩種算法的跟蹤性能，對視頻序列進行了成功率、跟蹤速度和中心位置誤差的對比。此處，成功率是指成功跟蹤到目標的幀數與圖像序列總幀數的比值。

從表1可以看出，雙重更新跟蹤算法的跟蹤成功率均比Struck算法要高，在全部遮擋的Girl視頻序列中，比Struck算法高出41.5%。在長時間遮擋的Cup視頻序列中，雖然雙重更新跟蹤算法成功率只有81%，但在總共100幀的序列中目標杯子有13幀被完全遮擋，沒有杯子的明顯特征，不能跟蹤目標。從表1中可以看出，雙重更新跟蹤算法比Struck算法在Girl視頻序列中快7.7 FPS，在Cup視頻序列中快8.3 FPS，通常人的視覺感官對于視頻的播放速率要求在15 FPS以上，雙重更新跟蹤算法可以滿足實時性的要求。

圖2 視頻序列的測試結果

目標跟蹤算法跟蹤成功率/%Girl序列Cup序列跟蹤速度/FPSGirl序列Cup序列Struck算法54.536.019.418.2雙重更新跟蹤算法95.081.027.126.5

跟蹤過程中的目標偏移程度如圖3所示。Girl視頻序列中，Struck算法在120幀處,由于遮擋的原因已經跟蹤失敗，當目標被完全遮擋再次出現在視野中時，不能恢復對原目標的跟蹤；雙重更新跟蹤算法利用雙重更新策略，可以繼續跟蹤目標。Cup視頻序列中，從第26幀到48幀目標被完全遮擋，消失在視野中，兩種算法均無法捕獲目標特征，在第54幀目標再次出現并具有明顯特征時，雙重更新跟蹤算法可以再次獲取目標位置，繼續跟蹤目標；而Struck算法僅在第90幀目標重新運動到被完全遮擋前的位置時，才可以繼續跟蹤目標。

圖3 雙重更新跟蹤算法與Struck算法視頻序列中心位置誤差對比

4 結論

本研究的雙重更新策略目標跟蹤算法是對結構化內核框架跟蹤算法的改進，通過增加初始模型特征值相似度匹配與樣本的在線學習作為雙重更新策略，降低了非目標物對正樣本學習的影響，增強了正樣本模板學習的有效性。通過對公開數據集和實際拍攝數據集的測試結果表明，雙重更新跟蹤算法可以有效的處理MB、SV、OCC、BC、OV、LR等跟蹤方面的復雜場景，并在該類場景下具有較小的跟蹤誤差，特別是對于目標被嚴重遮擋的場景，能夠重新搜索到目標位置并繼續跟蹤。雖然雙重更新跟蹤算法取得了良好的效果，但在DEF等場景中仍需進一步改進，而且跟蹤速度有所降低的問題也需要解決，這是下一步研究的方向。