基于MHT 的多物體跟蹤算法

邵 潔

(上海電力學院計算機與信息工程學院，上海 200090)

運動目標分析是計算機視覺研究領域中的一個富有挑戰(zhàn)性的課題.它涵蓋了移動目標物體的檢測、目標物體的跟蹤，以及跟蹤物體的行為識別等方面的內(nèi)容.這一課題在醫(yī)學檢測、軍事監(jiān)測、安全報警、智能居室、錄像檢索與回放等高科技領域具有廣泛的應用前景.

1 多物體跟蹤系統(tǒng)

目標跟蹤是指將收集在一定區(qū)域內(nèi)的一個或多個潛在目標的傳感信息進行判斷，區(qū)分出新目標和匹配原始跟蹤路徑的已有目標.更重要的是，一旦跟蹤確立，就可以進一步估計出目標物體的大量有用信息，例如運動速度、下一幀行進位置、目標分類特征等.一般而言，常見的監(jiān)控系統(tǒng)都是針對多物體場景設置的，因此多物體跟蹤(MTT)是最重要的跟蹤應用模式.圖1為典型的MTT系統(tǒng)的基本流程圖［1］.

圖1 MTT系統(tǒng)基本流程

當前，多目標跟蹤的難點主要來源于以下幾個方面:一是突發(fā)性物體運動;二是運動目標和運動場景同時變化;三是目標結構運動過程中的形變;四是目標間或目標與背景間產(chǎn)生遮擋;五是攝像機移動狀態(tài)下的運動跟蹤.

根據(jù) ALPER Yilmaz等人［2］的統(tǒng)計，能夠實現(xiàn)多物體跟蹤算法的主要有來自于 SETHI和JAIN的最近鄰法(GNN)、SHAFIQUE的多幀數(shù)據(jù)跟蹤法(MFT)、BAR-Shalom的聯(lián)合概率數(shù)據(jù)關聯(lián)算法(JPDAF)等.

與這些方法相比，多假設跟蹤算法(MHT)同時具有實現(xiàn)多目標場景下的物體進入、離開，以及被短暫遮擋等特殊情況下的跟蹤能力，同時易于實現(xiàn)程序優(yōu)化.目前，國外許多多物體跟蹤系統(tǒng)都廣泛采用MHT作為核心算法.

1978年，DONALD B Reid最先提出了用于跟蹤紅外成像目標的多假設跟蹤算法(MHT).MHT是一種在數(shù)據(jù)關聯(lián)發(fā)生沖突時形成多種假設以延遲做決定的邏輯.

但隨著假設數(shù)量的增加，計算量將成指數(shù)增長，因此本文選擇優(yōu)化后的基于軌跡的多假設跟蹤算法［3］，將其流程分為兩個步驟——數(shù)據(jù)關聯(lián)和航跡維護.實現(xiàn)步驟如圖2所示.

圖2 MHT基本實現(xiàn)流程

在實際應用中，本文采用卡爾曼濾波算法［4］實現(xiàn)跟蹤軌跡假設，采用LAP(Linear Assignment Problem)算法實現(xiàn)數(shù)據(jù)關聯(lián).

2 卡爾曼濾波算法

一個離散控制過程的系統(tǒng)可用一個線性隨機微分方程來描述:

同樣，對于系統(tǒng)在某一時刻的測量采樣值也可以用一個線性隨機微分方程來描述:

式中:X(k )——k時刻的系統(tǒng)狀態(tài);

U(k )——k時刻對系統(tǒng)的控制量;

A，B——系統(tǒng)參數(shù)，對于多模型系統(tǒng)，為矩陣;

Z(k )——k時刻的測量值;

H——測量系統(tǒng)的參數(shù)，對于多測量系統(tǒng)，為矩陣;

W(k)，V(k)——系統(tǒng)噪音和測量噪音，一般可以被假設成高斯白噪音，其協(xié)方差矩陣分別為Q和R(這里假設其不隨系統(tǒng)狀態(tài)變化而變化).

對于滿足以上條件的線性隨機系統(tǒng)，卡爾曼濾波器是最優(yōu)的信息處理器.利用卡爾曼濾波器，結合測量值和系統(tǒng)估計值的協(xié)方差，可以估算出系統(tǒng)的最優(yōu)化輸出.

假設當前狀態(tài)為x(k)，則可根據(jù)上一狀態(tài)的最優(yōu)預測X(k－1|k－1)，給出當前狀態(tài)的預測值:

更新相對應于預測值X(k|k－1)的協(xié)方差:

結合式(2)，計算當前狀態(tài)下的最優(yōu)預測值:

計算當前狀態(tài)的卡爾曼增益:

最后更新當前狀態(tài)下最優(yōu)預測值X(k|k)的協(xié)方差:

3 基于MHT的多物體跟蹤算法的實現(xiàn)

MHT實現(xiàn)多假設跟蹤的方式示例1如圖3所示.

圖3 視頻跟蹤場景示例1

假設當前視頻第k－1幀已有2個跟蹤目標，分別為 T1，T2，圖 3 中的 P1，P2分別為 T1，T2在第k幀根據(jù)式(3)和式(4)求得的假設位置.O1，O2，O3為k幀觀測到的3個物體，這里提取觀測物體可以采用多種背景提取方法，如幀差法、高斯混合模型(GMMs)等，本文采用GMMs提取前景圖像.根據(jù)當前情況，可能出現(xiàn)的匹配假設有10個［5］，分別為H1－H10.定義Tn(P1，O1)表示跟蹤軌跡Tn來自于P1和O1應用式(5)至式(7)關聯(lián)得到的最優(yōu)估計.Tn(O3)表示根據(jù)觀察新產(chǎn)生的跟蹤路徑T3.Tn(P1)表示無觀察物體與之匹配，以假設值延續(xù)跟蹤路徑Tn.

3.1 數(shù)據(jù)關聯(lián)

假設視頻第k－1幀圖像已有跟蹤軌跡數(shù)目為Nk－1，第k幀觀測到物體數(shù)目為mk，則其相關性矩陣Ω(Hk)由式(9)確定:

式中:j——行標號，對應當前幀的測量向量zkj;

i——列標號，對應已有跟蹤軌跡Ti;

采用 LAP算法化簡矩陣 Ω(Hk)，得到 Ω′(Hk)，實現(xiàn):

按圖3所示情況，可以得到:

3.2 跟蹤軌跡的形成與修剪

相關性化簡矩陣Ω′(Hk)的結果在某些情況下需要修正.MHT實現(xiàn)多假設跟蹤的方式示例2如圖4所示.

按圖4所示情況將會得到:

圖4 視頻跟蹤場景示例2

事實上，在這種情況下，P2所對應的物體往往已離開視頻畫面或在k幀未被檢測到，而O2是剛進入視頻或在k幀剛被檢測到的物體.因此，需要加入檢驗條件:

式中:traj_length——跟蹤軌跡Ti累計無觀測物體更新的幀的次數(shù);

Piw，Pih——已有軌跡斑塊Pi的寬和高;

Pi——軌跡Ti在當前幀的估計值;

Oj——當前幀觀測到的物體;

Ti(Pi，Oj)——Pi和Oj在同一物體軌跡上.

這一修正，即式(11)的成立條件為:

(1)假設視頻中所有物體不會在瞬間突然提速或降速;

(2)物體每秒行進距離小于每秒幀數(shù)與其自身長度的乘積的50%，即假設視頻為15 fps，4 m長的車輛速度小于30 m/s.

將數(shù)據(jù)關聯(lián)結果代入式(5)，可求得k幀最優(yōu)軌跡估計作為跟蹤結果顯示.同時，需要對卡爾曼增益和k幀最優(yōu)估值方差進行更新.

4 實驗結果與分析

為了驗證本方法實際場景應用的有效性，可針對多個不同場景視頻序列進行跟蹤實驗.實驗中，對每個跟蹤物體均標明跟蹤號，以此確定跟蹤結果的正確性.

圖5為車輛視頻的跟蹤結果.圖5a和圖5c中的黑色矩形框標識出跟蹤到的物體，其右上角數(shù)字為跟蹤物體號.圖5b和圖5d中白色斑塊顯示背景檢測算法提取到的前景物體.

實驗環(huán)境:雙核2.66 GHzCPU，3 GB內(nèi)存，幀圖像大小為352×288像素，每幀視頻MHT算法處理時間小于1 ms，GMMs+MHT處理時間為47 ms.

圖5 連續(xù)兩幀視頻圖像車輛跟蹤效果

5 結束語

本文經(jīng)過對多例實際場景視頻的跟蹤實驗，均獲得良好的跟蹤效果，尤其對具有良好背景分割效果的視頻得到了準確的跟蹤結果.實驗表明，該算法具有良好的魯棒性.但缺陷是對背景提取算法的過分依賴.錯誤的跟蹤主要來自于前景的錯誤提取，這也是今后系統(tǒng)改進的重點之一.

［1］SAMUEL S B，RAYTHEON.Multiple hypothesis tracking for multiple target tracking［J］.Aerospace and Electronic Systems Magazine，IEEE，2004，19(1):5-18.

［2］ALPER Yilmaz，OMAR Javed，MUBARAK Shah.Object tracking:a survey［J］.ACM Computing Surveys，2006，38(4):13.

［3］MASAMICHI Kojima，HIROSHI Kameda.A study of target tracking using track-oriented multiple hypothesis tracking［J］.SICE ’98，1998:933-938.

［4］DAVID A Forsyth，JEAN Ponce.Computer vision:a modern approach［M］.Pearson Education，2002:534-549.

［5］REID D B.An algorithm for tracking multiple targets［J］.IEEE Transactions on Automatic Control，1979，24(6):843-854.