基于有效特征點的運動目標(biāo)匹配跟蹤算法

鄭曉萌 ，張德海

（1.中國科學(xué)院國家空間科學(xué)中心，北京100190；2.中國科學(xué)院大學(xué)北京100049）

目標(biāo)跟蹤是計算機視覺領(lǐng)域的研究熱點，并得到了廣泛的應(yīng)用。目標(biāo)跟蹤算法可以分為產(chǎn)生式和判別式兩大類。產(chǎn)生式跟蹤方法如文獻[1-2]所示，首先采用生成模型來描述目標(biāo)的表觀特征，然后在后續(xù)的圖像中找到與該模型最為匹配的位置作為目標(biāo)的位置。然而由于采用包圍框的形式對目標(biāo)進行初始化，在對目標(biāo)建模的同時包含了一定的背景信息，當(dāng)目標(biāo)變化劇烈或者被遮擋時容易產(chǎn)生偏移。判別式跟蹤方法如文獻[3]所示采用訓(xùn)練過的分類器來區(qū)分前景目標(biāo)和背景信息。與產(chǎn)生式算法相比，判別式算法魯棒性更強，性能更優(yōu)[4-5]。但由于受到目標(biāo)姿態(tài)變化、尺度變化、目標(biāo)快速運動、被遮擋或者消失等因素的影響，判別式算法也會產(chǎn)生漂移。

為了解決漂移現(xiàn)象，Kalal等將目標(biāo)跟蹤與檢測相結(jié)合，并引入在線學(xué)習(xí)機制，提出了TLD（Tracking-Learning-Detection）視覺跟蹤算法，解決了傳統(tǒng)跟蹤算法中無法獲取丟失目標(biāo)，無法進行長時間跟蹤的問題。但TLD中存在一些明顯的不足，如跟蹤器穩(wěn)定性不高、檢測器中檢測窗口過多耗時長等。Supancic[6]等采用自組織學(xué)習(xí)的方法選擇訓(xùn)練樣本更新檢測器，將SVM目標(biāo)方程中得分較高的跟蹤結(jié)果替換樣本集中早期樣本，建立更有效的樣本集，降低了時間復(fù)雜度。但該算法在目標(biāo)發(fā)生劇烈形變時，跟蹤效果較差。Alahari[7]等采用離線的方式對目標(biāo)運動的軌跡進行學(xué)習(xí)，估計目標(biāo)的形變變化，但該算法無法有效處理目標(biāo)的尺度變化。

針對以上算法中出現(xiàn)的問題，文中提出了一種基于有效特征點的自適應(yīng)目標(biāo)跟蹤算法。首先采用有效特征點代表目標(biāo)物體，保證目標(biāo)能被可靠地跟蹤，抑制了因跟蹤背景中錯誤的特征點而導(dǎo)致跟蹤結(jié)果漂移的現(xiàn)象。其次，采用馬爾科夫方向預(yù)測器來預(yù)估目標(biāo)的檢測區(qū)域，在可靠檢測的前提下，可以有效的縮小檢測范圍并增強跟蹤器對相似目標(biāo)軌跡的判別能力。

1 ORB算法

基于特征的跟蹤采用一組特征集合來描述運動目標(biāo)，通過在連續(xù)幀中搜索相應(yīng)的特征集合來檢索運動目標(biāo)，實現(xiàn)跟蹤[8]。在實際應(yīng)用中，常選取一些具有不變性的局部特征進行目標(biāo)跟蹤，這類方法具有抗遮擋性和魯棒性強等優(yōu)點。SIFT和SURF是兩種著名的特征檢測算子，在圖像旋轉(zhuǎn)、尺度變化和視覺變化下都具有良好的不變性，但二者的運算較為復(fù)雜，實時性差，而FAST[9]（Features from accelerated segment test）特征點檢測算子，單幀處理速度可達微秒級別[10]。ORB（Oriented FAST and Rotated Brief）算法 將 BRIEF（Binary robust independent elementary features）描述子與FAST特征點進行改進與結(jié)合，使其具有旋轉(zhuǎn)不變性和噪聲抑制特性。

1.1 特征點提取

Drummond等人認(rèn)為在灰度圖像中，若某像素點的灰度值比其鄰域內(nèi)足夠多的點的灰度值大（或?。┯谝欢ㄩ撝担瑒t該點可能為圖像的角點。圖1為以像素點P為中心，以3為半徑的離散化Bresenham圓形鄰域模板，該圓的邊界上有16個像素值。若P點的灰度值比連續(xù)n個點的像素值大于或小于閾值T，則點P可能是一個角點。

n值可取12或9，實驗證明n取9的效果更好，因此本文采用FAST-9角點檢測算法。上述算法中，對于圖像中的每一個點，都需要遍歷其鄰域圓上的16個像素點，效率非常低。因此采用一種高效算法快速排除一大部分非特征的像素點。算法假設(shè)若某點為FAST角點，則其鄰域圓上將有超過34的候選點滿足判斷條件。首先檢測P點周圍1、9、5、13四個位置的像素點中是否有三個點滿足判斷條件，若不滿足，則該點不是特征點，若滿足，則繼續(xù)判斷該點的鄰域上16個點中是否有12個滿足判斷條件。

求出FAST角點后，利用Harris角點檢測算法，選出FAST角點中響應(yīng)值最大的N個點。由于FAST算法不能產(chǎn)生多尺度的特征點，因此采用空間金字塔模型，在金字塔的各層上采用Harris濾波生成多尺度下的FAST特征點。

圖1 FAST特征點檢測模板

1.2 特征點的方向

利用灰度質(zhì)心[11]算法，對目標(biāo)物體所在的目標(biāo)框提取其形心，與FAST特征點結(jié)合構(gòu)成OFAST[12]特征向量，將特征點和質(zhì)心之間的偏移向量作為該特征點的方向，解決了FAST特征點不具有旋轉(zhuǎn)不變性的問題。

Rosin定義鄰域矩為

從特征點O到質(zhì)心C間構(gòu)建OFAST特征向量OC，作為該特征點的方向，其方向角θ的大小為：

為了提高方法的旋轉(zhuǎn)不變性，需確保x和y在鄰域半徑為r的圓形區(qū)域內(nèi)，即x,y∈[-r,r]。

1.3 特征點描述子

ORB算法采用具有旋轉(zhuǎn)不變性的BRIEF[13]作為描述子。BRIEF描述子的實質(zhì)是在特征點附近隨機選取指定數(shù)量的像素點對，通過比較點對間的灰度值大小，組合編碼成一個長度為N（一般N=256）的二進制字符串。BRIEF描述子的構(gòu)建步驟如下：1）為了較少噪聲干擾，先對圖像進行平滑處理。

2）以特征點為中心，取S*S的鄰域窗口。在窗口內(nèi)選取一對（兩個）M*M的子窗口，比較子窗口的像素和（可由積分圖像求出），進行二進制賦值（一般S=31，M=5）。

其中p(x)，p(y)分別為兩個子窗口的像素和。

3）在S*S的鄰域窗口內(nèi)選取N對子窗口，使其相關(guān)性最低，重復(fù)步驟2）進行二進制賦值，求出一個長度為N的二進制碼串，這個碼串就是該特征點的描述子。

BRIEF描述子由特征點周圍的N對（2N個）子窗口生成，將這N對子窗口( )xi,yi，i=1,2,….,2n組成一個矩陣S:

為使BRIEF描述子具有旋轉(zhuǎn)不變性，使用圖像塊旋轉(zhuǎn)角度θ和相應(yīng)的旋轉(zhuǎn)矩陣Rθ，建立矩陣S的校正版本Sθ。

其中

θ為2.2中為特征點求得的主方向。

將式（3）中求出的特征點質(zhì)心方向信息加入描述子中，加入方向后的特征描述子為：

2 有效目標(biāo)點選取

2.1 特征點追蹤

目標(biāo)物體具有整體性，當(dāng)其做平移運動時，目標(biāo)上各點的運動情況相同，當(dāng)目標(biāo)旋轉(zhuǎn)時，目標(biāo)車輛瞬時加速度較小，速度不會發(fā)生較大變化，且LK[14]光流法要求相鄰兩幀圖像間隔非常?。◣资撩雰?nèi)），在此時間間隔內(nèi)，可將旋轉(zhuǎn)運動近似成平移運動。所以，同一目標(biāo)上的特征點應(yīng)具有相同的位移矢量。利用這個特性，可選出包圍框內(nèi)穩(wěn)定的特征點。具體步驟如下：

1）對圖像進行灰度處理，確定待跟蹤物體的目標(biāo)框boundingbox，并利用質(zhì)心算法，求出第t幀中boundingbox的質(zhì)心位置O(t)。

2）以O(shè)(t)為中心，劃定一個矩形區(qū)域，令其為BoundingBox，其長寬比與boundingbox一致，大小是boundingbox覆蓋面積的4倍。

4）用LK光流金字塔算法求出上述特征點在第t+1幀中的位置。并求出上述點的幀間位移

5）求出幀間位移中值dmed，將距離dmed過遠(yuǎn)的一半點刪除，剩余點即穩(wěn)定特征點。

2.2 特征點匹配

通過特征點描述子間的漢明距離大小來表示特征點之間的相似度，當(dāng)距離大于某一閾值時，則認(rèn)為匹配成功。特征點匹配的步驟如下：

1）求出第t幀中BoundingBox內(nèi)的所有特征點的描述子，將它們作為database。

2）對第t幀中的BoundingBox進行檢測區(qū)域預(yù)估確定它在第t+1幀中的位置。檢測區(qū)域預(yù)估算法將在下一節(jié)中闡述。

3）求出第t+1幀中BoundingBox內(nèi)的所有特征點描述子，與database進行匹配，每個描述子在database內(nèi)尋找2個最佳匹配結(jié)果。其中穩(wěn)定特征點的選取標(biāo)準(zhǔn)如下：

①若與背景中的特征點相匹配，則刪除。

②若最佳匹配的匹配距離大于某一閾值，則刪除。

③若最佳的匹配距離與次佳的匹配距離之比大于某一閾值，則刪除該特征點。

2.3 特征點融合

由于噪聲等外界因素的影響，經(jīng)漢明距離匹配后可能存在偽匹配對造成誤差。而且采用包圍框?qū)ζ溥M行初始化，會不可避免的引入背景信息，背景中的特征點會使跟蹤逐漸產(chǎn)生偏移。但是，多數(shù)情況下，目標(biāo)物體與背景環(huán)境中的特征點的運動方向不一致。

因此本文將跟蹤和匹配后保留下的穩(wěn)定特征點進行融合，得出能有效代表目標(biāo)物體的目標(biāo)點，減少了因跟蹤背景中錯誤特征點而導(dǎo)致的跟蹤窗口漂移的現(xiàn)象。上述算法框圖如圖2所示。

圖2 有效特征點選取框圖

3 基于馬爾科夫模型的檢測區(qū)域預(yù)估

通常對全局圖像進行特征點檢測時，會因檢測區(qū)域過大引入一些消極目標(biāo)，導(dǎo)致檢測時間過長。此外，當(dāng)目標(biāo)區(qū)域中出現(xiàn)多個相似的目標(biāo)，且這些目標(biāo)在運動過程中發(fā)生重疊時，易出現(xiàn)跟蹤失敗的情況。因此，本文利用光流法預(yù)測出目標(biāo)框質(zhì)心位置，并加入馬爾科夫方向預(yù)測器[15]，根據(jù)前一幀中目標(biāo)物體的運動方向來預(yù)估當(dāng)前幀中目標(biāo)物體的運動方向，縮小特征點的檢測范圍。

3.1 馬爾科夫方向預(yù)測

在視頻序列中，可將目標(biāo)物體的運動分解為水平和豎直方向上運動。所以，采用馬爾科夫模型來分別預(yù)測目標(biāo)在水平和豎直方向上的運動趨勢。以豎直方向為例，令其狀態(tài)空間為{1為上，0為下}。馬爾科夫模型假設(shè)當(dāng)前幀中目標(biāo)的運動狀態(tài)僅與上一幀中目標(biāo)的狀態(tài)和狀態(tài)轉(zhuǎn)移矩陣有關(guān)。令t時刻的狀態(tài)轉(zhuǎn)移矩陣Pt如下：

其中，st表示目標(biāo)在t時刻的運動狀態(tài)，狀態(tài)矩陣Pt的每列之和為1。則由目標(biāo)在t時刻的運動方向狀態(tài)量及狀態(tài)轉(zhuǎn)移矩陣，可以預(yù)測目標(biāo)在t+1時刻的運動方向如下：

式中，p(st=1)（p(st=0)）分別為目標(biāo)在t時刻向上（下）的運動概率。若目標(biāo)在t時刻向下運動，則令p(st=0)=1，反之，令其為0；若目標(biāo)在t時刻上下方向上沒有運動，則令p(st=1)=0.5；等式左端為預(yù)測的目標(biāo)物體在t+1時刻向下或向上的運動概率，令概率大的那個方向為目標(biāo)在t+1時刻的運動方向。

根據(jù)目標(biāo)運動狀態(tài)的估計，可以求出其狀態(tài)轉(zhuǎn)移矩陣如下：

式中，n0，n1表示在0～t時間內(nèi)，視頻中目標(biāo)分別向下、上運動的幀數(shù)，n11（n00）表示在0～t時間內(nèi)，目標(biāo)在前一幀和當(dāng)前幀中都向上（下）運動的幀數(shù)，n01（n10）表示在0～t時間內(nèi)，目標(biāo)在上一幀中向下（上）運動但當(dāng)前幀中向上（下）運動的幀數(shù)。本文通過相鄰兩幀中目標(biāo)中心位置在豎直方向上的差值來判斷其向上（下）運動。

3.2 檢測區(qū)域預(yù)估算法

在對圖像進行特征點檢測前，需要根據(jù)目標(biāo)的運動狀態(tài)預(yù)測出目標(biāo)可能出現(xiàn)的位置范圍，檢測區(qū)域預(yù)估算法步驟如下：

1）利用灰度質(zhì)心算法，求出第t幀中Bounding?Box的質(zhì)心位置O（t），并利用LK光流法求出其在第t+1幀中的質(zhì)心位置O（t+1）。

2）利用馬爾科夫方向預(yù)測器，根據(jù)目標(biāo)在第t幀中的運動方向分別預(yù)測出目標(biāo)在第t+1幀中水平豎直方向的運動趨勢。確定目標(biāo)在第t+1幀中的大致范圍。

4 實驗結(jié)果及分析

4.1 實驗環(huán)境及測試數(shù)據(jù)說明

硬件實驗環(huán)境：Intel Core i5-4300U 1.90GHz CPU，NVIDIA GTX 950M顯卡。

軟件實驗環(huán)境：Windows 10.0，Visual Studio 2013，opencv2.4.9。

文中采用了4個典型的視頻序列對算法性能進行測試，并與TLD算法（參數(shù)為默認(rèn)值，具體參考相應(yīng)文獻）進行對比。表1列出了所選測試視頻的屬性，基本涵蓋了跟蹤過程中常遇到的一些場景變化。圖2為各視頻序列在測試過程中的一些截圖。本文將目標(biāo)超過50%以上的遮擋或者90°以上的空間旋轉(zhuǎn)視為“目標(biāo)不可見”。

4.2 跟蹤精度及運算速度

本文采用目標(biāo)重疊率[16]overlap、綜合評價指標(biāo)F、平均誤差衡量算法的跟蹤精度。采用視頻序列的總幀數(shù)與跟蹤所用時間的比值即算法每秒處理的幀數(shù)fps衡量算法的運算速度。計算公式如下：

表1 視頻序列信息

圖3 視頻序列測試截圖

其中：RT表示跟蹤得到的窗口，RG表示目標(biāo)實際所在窗口，area為窗口面積。當(dāng)重疊率大于0.5時

其中：P（precision）為準(zhǔn)確率，是算法正確跟蹤的樣本數(shù)與總樣本數(shù)之間的比值。R（recall）為召回率，是算法正確跟蹤的樣本數(shù)與總的正確樣本數(shù)之間的比值，用來衡量算法的查全度。P和R的計算公式如下：

其中，Nall為含有目標(biāo)的幀數(shù)，Ntrack為算法跟蹤得到的幀數(shù)為正確跟蹤的幀數(shù)。

平均誤差為算法估測出的目標(biāo)框與實際目標(biāo)框之間的中心距離。實驗結(jié)果如表2所示。

上述視頻序列均存在目標(biāo)的部分遮擋或完全遮擋，因此無法獲得目標(biāo)的連續(xù)軌跡。本文采用LK金字塔光流法對目標(biāo)框質(zhì)心的位置進行預(yù)測，并加入馬爾科夫方向預(yù)測器，對目標(biāo)物體的運動方向進行預(yù)測，縮小了檢測區(qū)域的范圍，較TLD算法的全局檢測，具有更快的處理速度。同時，此方法可排除圖像中相似目標(biāo)的干擾，提高追蹤器對相似目標(biāo)的辨識能力，實驗效果如圖4所示。

表2 兩種算法實驗結(jié)果對比

TLD算法的跟蹤模塊在目標(biāo)上均勻地選取點進行跟蹤，這些點并不能有效的代表包圍內(nèi)的目標(biāo)物體，而且采用包圍框的方式進行初始化會不可避免的引入背景信息，導(dǎo)致目標(biāo)中心誤差越來越大[17]。本文將特征點跟蹤和特征點匹配相結(jié)合，求出能有效代表目標(biāo)物體的穩(wěn)定目標(biāo)點。抑制了因跟蹤均勻選取的目標(biāo)點和背景中錯誤的目標(biāo)點而造成的跟蹤結(jié)果偏移現(xiàn)象，尤其當(dāng)目標(biāo)快速運動或發(fā)生形變時，本算法較TLD算法具有更低的中心錯誤率。實驗效果如圖5所示。通過對上述實驗結(jié)果的定量分析，本文算法在目標(biāo)物體快速運動、遮擋或者消失、視野中存在相似目標(biāo)、光照變化、目標(biāo)大小和外觀發(fā)生變化等情況都具有較高的跟蹤精度和跟蹤速度。

圖4 CarChase跟蹤效果圖（左側(cè)為TLD算法，右側(cè)為本文算法）

圖5 motocross跟蹤效果圖

5 結(jié)論

TLD算法和本文所提出的算法在長時間的視頻序列跟蹤中都具有良好的跟蹤效果。本文將特征點跟蹤和特征點匹配相結(jié)合[18]，得出能代表目標(biāo)物體的有效特征點，并在多個視頻序列上對TLD算法和本文算法進行了測試，實驗結(jié)果顯示，基于有效點的匹配跟蹤算法具有更高的跟蹤精度、處理速度和魯棒性，尤其當(dāng)目標(biāo)快速運動或發(fā)生形變時，中心錯誤率明顯降低，且具更強的對相似目標(biāo)的辨識能力。在今后的工作中將對本算法做進一步改進，并將之運用在更多的數(shù)據(jù)集上進行測試，以實現(xiàn)對多目標(biāo)物體的追蹤。