基于高維SIFT改進隱馬爾可夫模型的多目標跟蹤

劉藝博， 奚崢皓， 陳健超

(上海工程技術大學 電子電氣工程學院, 上海 201620)

0 引 言

自然場景下的多目標跟蹤(Multi-object tracking, MOT)是計算機視覺的一個重要問題，其在自動駕駛、軍事安全等領域都有廣泛的應用。多目標跟蹤的目的是在一個視頻中根據初始幀一些標定了身份信息的目標，在后續幀中維持這些目標的身份，并形成有效的軌跡[1-2]。然而，在復雜的環境背景下，目標在運動過程中容易被環境障礙物遮擋，并且，當多個目標相互交錯時容易引起跟蹤目標身份的丟失和互換，導致無法從視頻中提取到完整的運動軌跡。

馬爾可夫模型在多目標跟蹤任務中有顯著的優點，為了解決MOT中的遮擋問題， Liu等[3]提出了一種軌跡耦合關聯的馬爾可夫隨機場模型，通過整合密集人群的位置和運動信息，對其中不完整和偏差的位置數據進行校正，提高了跟蹤器的精度；Xiang等[4]將MOT表述為馬爾可夫決策過程中的決策，以策略學習的方式加強不同幀目標之間的數據關聯；Wu等[5]將馬爾可夫決策過程與不同頻率的相關濾波器關聯，解決了跟蹤過程中因為遮擋和尺度變換造成的目標漂移問題；Vojir等[6]利用隱馬爾可夫模型 (Hidden Markov Model, HMM)建立了一種HMMTxD方法的跟蹤器，將檢測結果作為觀測值輸入到模型中，并輸出估計跟蹤的結果，對遮擋問題有較好的魯棒性，然而此時模型受觀測狀態的影響較大，狀態值的選取直接影響了跟蹤結果的好壞。

基于馬爾可夫在跟蹤任務中的優越性，針對HMM狀態選取的問題，本文以SIFT算子作為模型中的狀態，建立一種基于SIFT的隱馬爾可夫模型(SIFT-HMM)，并將其應用到多目標跟蹤任務中。針對狀態關聯問題，利用HMM設計一種匹配SIFT隱性、觀測兩種狀態的方法，從而實現對遮擋目標的狀態估計。針對馬爾可夫模型復雜度較高的問題，利用SIFT關鍵點設計了一種高維的觀測方法，從而增強模型的推理速度。實驗結果表明，本文的跟蹤器在MOT17，MOT20、KITTI公共數據集上實現較好的跟蹤性能，高維模型能提高算法的推理速度。

1 基于SIFT-HMM的多目標跟蹤器

通過HMM實現多目標跟蹤的過程被描述為根據當前幀的目標狀態，獲取下一幀目標發生概率最大的狀態。本文提出了一種以SIFT關鍵點為狀態，建立HMM跟蹤器模型，通過對狀態值進行實時預測實現對多目標的跟蹤，SIFT-HMM跟蹤器的工作流程如圖1所示。

圖1 基于SIFT-HMM的跟蹤器工作流程

1.1 基于SIFT算法的特征關鍵點提取

(1)

定義Ω,Ψ兩個集合如式(2)所示：

(2)

(3)

1.2 基于SIFT關鍵點建立的HMM

HMM由觀測狀態序列O、隱性狀態序列S和參數λ組成。觀測狀態是實時狀態可以觀測的，用SIFT提取的關鍵點集表示觀測狀態，可得在t幀時的SIFT關鍵點集合為ot，那么由T幀序列組成的視頻的觀測序列為O={o1,o2,o3,…,oT}。隱性狀態是不可被直接觀測的未知狀態，用t+1幀的估計SIFT關鍵點集表示t幀的隱性狀態，那么由T幀序列組成的視頻的隱性狀態序列為S={s1,s2,s3,…,sT}，HMM中模型單幀的狀態轉移結構，如圖2所示。

圖2 HMM中單幀狀態轉移的結構圖

此外，視頻首幀圖像的隱性狀態與觀測狀態都表現為檢測器檢測得到的初始化結果，此時s1不具有實際意義，在數值上s1取值與o1一致；而視頻在最后一幀的圖像是跟蹤器的終止幀，模型在最后一幀時的觀測狀態oT不具有實際意義，在數值上取值與sT一致，故模型實際輸入的兩個狀態序列為O={o1,o2,…,oT-1}和S={s2,s3,…,sT}。

跟蹤器工作時，當前幀的目標狀態是由上一幀的狀態決定的，即t幀目標的狀態st與t-1幀時的觀測狀態ot-1有關，當t∈[2,T]，用Ft表示第t幀時模型的狀態向量,如式(4)所示：

Ft=[ot-1,st,λ]

(4)

其中，模型的參數λ=(A,B,Π)，分別表示狀態轉移概率矩陣、觀測概率矩陣和狀態概率向量。

t幀狀態ot-1所能取到的觀測狀態數量是有限的，此時的狀態數量為N(N∈Z+)，由于ot-1與st存在矩陣變換關系，故隱性狀態st所能取到的狀態數量也是有限的，隱性狀態數量為M(M∈Z+)。用V={v1,v2,…,vN}表示所有的觀測狀態集合，Q={q1,q2,…,qM}表示所有的隱性狀態集合，則P(|ot-1|=vt)表示觀測狀態ot-1取到vt的概率，如式(5)所示，P(|st|=qt)表示t幀時隱性狀態st取到qt的概率，如式(6)所示：

P(|ot-1|=vt)=max{P(|ot-1|=v1),…,P(|ot-1|=vN)}

(5)

P(|st|=qt)=max{P(|st|=q1),…,P(|st|=qM)}

(6)

其中，vt∈V，qt∈Q。

狀態在相鄰幀之間的轉移是通過參數λ的變換關系來傳遞的，且參數包含3個子參數，即λ=(A,B,Π)分別表示狀態轉移概率矩陣，觀測概率矩陣，狀態概率向量，如式(7)～式(9)所示：

(7)

(8)

Π=[π1,π2,…,πM]1×M

(9)

其中，aij表示t-1幀的狀態qi轉移到t幀的狀態qj的概率，aij=P(|st|=qj||st-1|=qi)；bij表示t幀隱性狀態qi產生觀測值vj的概率，bij=P(|ot-1|=vj||st|=qi)；πi表示初始幀的狀態qi出現的概率；πi=P(|s1|=qi)，下角標i,j表示可能狀態的標號。

確定每一幀狀態的取值以及幀與幀之間傳遞關系后，HMM可以用O,S,λ之間的關系來表示，如式(10)所示：

P(O,S|λ)=P(F1,F2,…,FT)=P(F2,…,FT-1,oT,s1|λ)=P(o1,…,oT-1,s2,…,sT,oT,s1|λ)=πs1bs1o1as1s2bs2o2…ast-1stbstot

(10)

1.3 SIFT-HMM的高維觀測狀態

1.3.1 高維觀測狀態的描述

基于HMM建立的多目標跟蹤器一般對每個目標建立獨立的HMM，狀態表示為每個目標的全部關鍵點集，此時的觀測維度較低，將其定義為初始的低維狀態模型。

圖3 優化高維模型的原理圖

高維模型中，ot表示t幀K個目標的觀測狀態，包含目標數量、關鍵點數量、關鍵點維度3重信息。t幀時模型的狀態向量Ft包含K個目標和R個關鍵點，每個關鍵點在形式上表現為一個m×n的二維矩陣，那么ot在形式上表示為一個K×R×m×n的四維數組，將高維數組ot進行逐層分解，則有式(11)：

ot=[ot(1),ot(2),ot(3),…,ot(K)]

(11)

其中，ot(k)表示t幀時第k個目標的觀測值，表現為R×m×n的三維數組，如式(12)所示：

ot(k)=[ot(k)|1,ot(k)|2,ot(k)|3,…,ot(k)|R]T

(12)

其中，ot(k)|r表示t幀時第k個目標在第r個關鍵點的觀測值，表現為m×n的二維矩陣，如式(13)所示：

(13)

關鍵點由1×32的描述子向量表示，即m×n=1×32，故ot(k)|r可改寫為式(14)：

ot(k)|r=[x1(t),x2(t),…,x32(t)]

(14)

根據式(11)～式(14)，t幀時K×R×m×n的觀測狀態ot表示為K×R×n(n=32)的三維數組，如式(15)所示：

(15)

1.3.2 高維觀測狀態模型的復雜度

低維狀態模型和高維狀態模型表現在狀態維度的不同，而狀態維度決定了參數的計算量，從而影響跟蹤過程的推理速度。低維狀態模型中每幀的狀態模型針對一個目標，多個目標的場景需要多個模型同時運行，其參數總計算量等于每個模型對應參數的乘積，用μlow表示模型的復雜度，如式(16)所示：

(16)

其中，αk(t)表示第k個目標在t幀的復雜度。

高維狀態模型中，每幀的狀態模型針對其全部目標，多個目標的場景只需要一個模型運行，其參數計算量等于該模型的參數計算量，用μhigh表示此時模型的復雜度如式(17)所示：

(17)

低維模型的復雜度μlow表現為多個目標復雜度的積，高維模型復雜度μhigh表現為多個目標復雜度的和，則μhigh≤μlow，表明高維狀態模型能一定程度的降低模型的復雜度。

1.4 SIFT-HMM的參數訓練和求解

Baum-Welch方法是HMM參數學習的通用方法之一，使用該方法對SIFT-HMM的參數訓練[8]。若視頻序列中一共存在K個目標，初始幀圖像中有k1個目標，對這k1個目標建立高維觀測狀態模型。該模型單獨訓練，得到高維模型的參數。而對于在后續幀中出現的K-k1個目標，初始化每個目標并建立低維觀測狀態模型，得到獨立的K-k1個模型并進行訓練。綜合上述，1個高維模型和K-k1個低維模型，最終能夠得到整個SIFT-HMM的K-k1+1個收斂的參數。對于第θ個模型，θ∈[1,K-k1+1]，該模型收斂的參數λη(θ)可由式(18)得到：

maxAη(θ)=

(18)

其中，Aη(θ),Bη(θ),Πη(θ)表示收斂的3個參數；maxAη(θ),maxBη(θ),maxΠη(θ)表示3個參數的極大值；η表示模型的最大迭代次數。

將式(18)得到的3個參數以及輸入觀測序列O代入到式(10)的計算關系式中可以得到隱性狀態st的最大概率狀態值如式(19)所示：

(19)

該概率最大的狀態即是t幀時st的狀態，逐幀計算全部T幀的狀態，從而得到整個視頻的狀態序列S，將這些估計的狀態(SIFT關鍵點集)用一個可視的回歸框框選出來，形成關于時序t的跟蹤軌跡，即得到SIFT-HMM的跟蹤可視化結果。

2 基于檢測器的初始化預處理方法

SIFT-HMM跟蹤算法是根據初始幀選定的目標框，實現對后續幀中目標的跟蹤。在建立跟蹤器之前，需要對圖片序列進行預處理，得到初始化結果。本文的預處理即建立一個檢測器，得到圖片序列的初始化目標框。選用MOT Challenge的DPM公共檢測器作為檢測框架，在輸入到跟蹤器模型前用該檢測器進行目標的初始化定位，DPM檢測器在MOT17-10-DPM序列的首幀檢測結果如圖4所示。檢測器利用回歸框來框選檢測到的目標，而在得到待測目標的同時，圖4(a)中出現了許多錯檢的回歸框，這些錯檢的回歸框在驗證跟蹤器效果時不具有實際意義，因此將第一幀圖像中錯檢的回歸框剔除，剔除異常后的檢測結果如圖4(b)所示，優化后的檢測結果將作為跟蹤器首幀的輸入。

(a) DPM檢測器檢測結果 (b) 剔除異常后的檢測結果

3 實驗結果分析與算法評估

在MOT17、MOT20和KITTI公共數據集上對SIFT-HMM的性能進行評估，并與其他先進的跟蹤算法進行比較分析。實驗環境為一臺具有Intel Corei5-9600KF CPU處理器和16 GB內存的個人電腦，算法是通過python3.8在64位Windows10操作系統上實現的。

3.1 數據集和評價指標

3.1.1 數據集

選取了3個數據集中具有各自特點的視頻序列來檢驗跟蹤器的有效性。MOT17數據集是攝像機在室外環境下拍攝到的行人視頻，選取MOT17-08-DPM視頻序列用于檢驗在擁擠、遮擋環境下的跟蹤性能；選取MOT17-10-DPM視頻序列用于檢驗在動態場景下的跟蹤性能；MOT20數據集中目標數量較多，選取MOT20-01、MOT20-02數據集用于檢驗高維模型的優越性；KITTI數據集是針對自動駕駛的數據集，選取KITTI-0006用于檢驗以剛體為目標的跟蹤性能。

3.1.2 評價指標

為了量化跟蹤器結果，并且統一與其他對比算法的評價標準，采用IDS、MOTA、MOTP3個指標來量化多目標跟蹤器的性能。其中，IDS表示在一條跟蹤軌跡跟蹤的過程中，目標身份發生交換的次數；MOTA表示多目標跟蹤的準確率，如式(20)所示；MOTP表示多目標跟蹤的精度，反應了預測結果與標準框的匹配度，如式(21)所示：

(20)

(21)

其中，FN、FP、GT表示跟蹤中漏檢的目標數、錯檢的目標數、全部目標的實際總數；dt,i表示第t幀中第i個目標對的距離；ct表示t幀中預測軌跡與GT匹配上的數目。

3.2 實驗結果分析

3.2.1 可視化結果分析

SIFT-HMM在部分數據集的可視化結果如圖5 所示。可視化結果表明，在3種不同的場景下，SIFT-HMM跟蹤器都能對目標實現有效的跟蹤。

圖5 SIFT-HMM在部分數據集的可視化結果

3.2.2 優化的高維狀態模型結果分析

SIFT-HMM在MOT20-02第25幀的跟蹤可視化結果如圖6所示，該圖中目標較多，對初始幀每個目標建立獨立的HMM會導致此時的跟蹤器復雜度較高。

圖6 MOT20-02第25幀的跟蹤可視化結果

為了驗證本文提出的優化高維模型的優越性，控制兩個變量來設置消融實驗，進而比較優化前的初始低維模型和優化后的高維觀測模型的復雜度。在同一序列下截取一段視頻，比較在相同視頻下兩個模型的運行時間，量化運行時間的指標為HZ，表示跟蹤器在一秒中處理幀數的速度；保持其他條件不變的情況下，增加截取視頻的幀數，比較在增加幀數之后運行時間的變化。

共選取了3個視頻，分別從每個視頻初始幀截取30幀的視頻段和120幀的視頻段做兩次測試，測試的結果見表1。實驗結果表明，基于高維模型的SIFT-HMM跟蹤器在6個測試的HZ上都表現最優。在MOT20-01數據集的兩次測試中，基于高維模型的跟蹤器分別比初始模型在運行速度上提升94.11%和68.75%；在MOT20-02數據集的兩次測試中，基于高維模型的跟蹤器分別比初始模型在運行速度上提升183.33%和126.92%；在MOT17-08-DPM數據集的兩次測試中，基于高維模型的跟蹤器分別比初始模型在運行速度上提升19.28%和4.51%。這些結果表明，高維優化模型能夠有效的降低跟蹤器的復雜度，提升跟蹤器的推理速度。

表1 SIFT-HMM高維模型與初始低維模型的消融實驗

3.3 與其他跟蹤算法的對比分析

為了驗證SIFT-HMM跟蹤器的優越性，本文選擇與MOT-MDP[4]，MDP-OF[9]，HMOT[10]，JDMOT[11]跟蹤算法進行對比分析，對比結果見表2。實驗結果表明，對于IDS指標，本文在這3個視頻序列上都取得最好的性能，比第二好的跟蹤器在MOT數據集上高出33.3%～70.5%；在KITTI數據集上高出6.7%。這是由于本算法為每個目標建立的HMM，使每個目標的轉移通過獨立的馬爾可夫鏈來傳遞，具有較好的獨立性。

表2 與其他跟蹤算法的對比結果

MOTA受FN、FP、IDS3個指標影響。HMOT算法在個體關聯上引入了細化運動模式的方法，減少了算法的誤陽性數據，在FN指標上有較好的效果，但在目標軌跡交叉時容易產生誤差，IDS指標較差。本文的IDS指標在MOT數據集上平均比HMOT高7倍，在KITTI數據集上平均比HMOT高出42.7%。因此，本文在MOT17的兩個序列上取得最好的性能，而在KITTI-0006序列上取得第二好的性能，比最好的HMOT算法低出4.6%。

本文的MOTP指標在MOT17-08-DPM取得第二好的性能，而在KITII數據集上取得第四的性能，這是因為以SIFT關鍵點建立HMM時，模型容易受背景特征點的干擾，導致框選目標時多框選了背景的特征點造成目標框與GT的不匹配。

4 結束語

本文提出了一種SIFT-HMM的多目標跟蹤算法，該算法能夠有效解決多目標跟蹤過程的遮擋，以及目標身份互換的問題，在MOT20數據集上通過實驗檢驗高維SIFT觀測狀態優越性，實驗結果表明在視頻序列首幀圖像采用高維觀測狀態建立的SIFT-HMM，能夠降低模型的復雜度。在MOT17和KITTI數據集上與其他跟蹤算法進行了對比分析，對比結果表明，本文算法的IDS指標在兩個數據集上表現最優，比第二優的算法高出34.3%和76.2%，表明本文的算法對目標身份互換問題有較好的魯棒性；MOTA指標在2個數據集上分別取到56.84%和86.7%的性能，在MOT17數據集上比第二優的算法高出4.7%，表明本文的算法具有較好的跟蹤準確度，并對遮擋問題有較好的魯棒性。然而，本文在MOTP指標上未能表現最優，因此約束SIFT關鍵點來提高跟蹤的精度會是未來研究的方向。