基于GMS與FPME的視頻目標跟蹤方法

張海濤，秦鵬程

（遼寧工程技術大學軟件學院，遼寧葫蘆島125105）

0 概述

視頻目標跟蹤是當前計算機視覺領域的熱門研究課題，在民用和軍事的眾多場景中有著廣泛的應用［1-3］，而對目標特征點的提取和匹配是視頻跟蹤中的一項重要步驟［4-5］。視頻跟蹤中存在諸多影響因素，如尺寸變化、角度變化、光照變化、背景物雜亂、噪聲、遮擋干擾等，這增加了特征點錯誤匹配對準的概率，極大地影響了后續視頻跟蹤的效果。因此，如何快速有效地剔除誤匹配特征點以提高匹配精度，成為一項值得研究的問題。

當前對于誤匹配特征點的剔除方法研究在點云配準［6］、三維對象識別［7-8］等方面應用較為廣泛。文獻［9］利用基于迭代最近點（Iterative Closest Point，ICP）的精確配準技術對前期誤匹配結果進行后期校準，但是該算法過于依賴較為準確的初始姿態估計，且存在計算量大、耗時較長、收斂慢等問題。文獻［10］在尺度不變特征轉換（Scale Invariant Feature Transform，SIFT）算法的基礎上增加了區域重疊核加權Hu 矩，將相似度較小的匹配點剔除掉，然而SIFT算法［11］需要建立高維度復雜的描述子，占用了大量的內存，運行時間較長。文獻［12］采用隨機抽樣一致性（Random Sample Consensus，RANSAC）匹配點提純算法剔除錯誤的關鍵點匹配對，提高了識別的精度，然而該算法在抽樣時需要對所有的特征點進行迭代以得到最大化的局內點，導致效率較低，在一定程度上犧牲了算法的實時性。

針對特征點提取和匹配過程中速度慢、效率低的問題，文獻［13］提出一種加速魯棒特征（Speeded up Robust Feature，SURF）算法，對DoH 中的高斯二階微分進行近似簡化，加速了特征的提取和描述。然而，SURF 算法在計算主方向時過于依賴局部圖像的梯度方向，導致匹配成功率降低。文獻［14］提出一種二進制特征描述算法（ORB），有效地解決了計算和收斂速度慢的問題，提高了匹配的實時性，并且在圖像識別的精度上有了進一步提高［15-16］，然而ORB 在匹配過程中容易受到目標外未知因素的干擾，導致匹配結果中存在大量的誤匹配點。

文獻［17］在鄰域一致性約束的基礎上，提出一種融合ORB 與網格統計的視頻跟蹤方法GMS，通過在特征點鄰域范圍內選擇支持特征點集進行約束檢驗，以較小的時間代價增加了ORB 算法穩健匹配的數量。文獻［18］提出一種基于稀疏表示的跟蹤方法，但是該方法僅考慮整體而非局部外觀來區分目標和背景區域，因此，當目標和背景區域相差不明顯時，跟蹤效果較差。文獻［19］采用了深層卷積神經網絡模型，但是在應對簡易跟蹤環境時，其跟蹤速度很慢。文獻［20］方法利用基于相關濾波的跟蹤方法，在計算效率上有著優異的性能，然而該方法會因為匹配跟蹤誤差的累積而導致模型逐漸退化。

針對上述方法特征點匹配精度與匹配速度存在矛盾的問題，本文在視頻目標跟蹤方法GMS 的框架下，對ORB 特征匹配階段產生的錯誤匹配對進行“粗-精”兩階段剔除，提出一種新的視頻目標跟蹤方法ME-GMS（Mismatch Elimination GMS）。利用K-means算法快速粗略地剔除誤差較大的匹配關系，提高正確匹配對所占比例。在此基礎上，依據分裂法的思想，參考匹配點到聚類中心的偏離程度，根據誤差設定合適的閾值，從而對誤匹配對進行精確剔除。

1 GMS 特征匹配方法

1.1 特征點提取

GMS 算法在特征匹配階段采用ORB 算法進行特征點的檢測與匹配。ORB 是一種基于FAST 特征點檢測和Brief 描述子改良而成的圖像特征匹配算法，其在應用于視頻跟蹤時具有極為優異的速度表現力，并具有尺度不變性和旋轉不變性。ORB 算法主要通過以下步驟來完成特征點的檢測：

1）采用FAST 算法粗提取大量的特征點。當以候選點p為圓心、r為半徑的鄰域范圍內存在M個連續大于或小于候選點p處灰度值的點，則認為候選點p為FAST 特征點。

2）為消除圖像邊緣處存在的較強響應，利用Harris 算法的響應函數對步驟1）中提取的FAST 特征點執行排序，并保留前N個點。

3）為對提取的特征點賦予尺度信息，采用多尺度圖像金字塔對圖像分層提取FAST 特征點。

4）為對提取的特征點賦予方向信息，采用灰度質心法來計算FAST 特征點的主方向。當特征點鄰域范圍內的質心位置不與中心重合時，可通過質心與中心的位置坐標計算特征點的主方向。

特征點鄰域范圍內的質心可定義為：

特征點的鄰域矩可定義為：

其中，I(x,y)表示(x,y)點處的灰度值。

特征點的主方向為：

1.2 特征點描述與匹配

ORB 算法采用Brief 描述子對每個特征點進行特征描述。Brief 描述子通過比較特征點鄰域范圍內像素點對的灰度差值，形成一個二進制碼串，并采用漢明距離作為特征點匹配的相似性度量準則。ORB算法主要通過以下步驟來完成特征點的匹配：

1）在特征點p的鄰域范圍內選擇n個像素點對，根據式（4）中的二元測試函數τ對這n個像素點對進行二值判決，得到一個包含n個二進制值的碼串：

τ(p；ai,bi)表示特征點p鄰域范圍內的描述子分段函數，其定義如下：

其中，I(a)表示在特征點p鄰域范圍內a點處的灰度值。

2）為使Brief 算法生成的特征描述子具有旋轉不變性，將式（3）得到的特征點主方向θ增加至描述子。

首先在特征點鄰域范圍內選擇n對點集構建一個2×n維的矩陣，如式（6）所示；然后利用θ對應的旋轉矩陣Rθ構造特征點對校正矩陣RθQ，得到具有旋轉不變性的特征描述子，如式（7）所示。

3）利用貪婪搜索的方法找出相關系數小于設定閾值的鄰域點對，構建包含256 個向量的最終特征描述子。

4）利用漢明距離計算特征描述子間的相似度進行特征匹配。假設步驟3）中的描述子K=b0b1…b255，則相似度D(K1,K2)可定義為：

2 特征點誤匹配剔除方法

在進行前后兩幀圖像的特征點匹配時，得到的匹配關系中均含有一定數量的誤匹配對，這會對視頻跟蹤產生一定程度的干擾，經累計會降低視頻跟蹤的準確性。為剔除這些誤匹配對，本文采用由粗到精的方法，逐步對誤匹配對進行剔除。首先利用K-means 算法的思想對匹配關系進行聚類劃分，僅保留匹配對數量最多的那一類，從而剔除掉大部分誤匹配對；然后在獲得較多正確匹配對的基礎上，以標準差和歐氏距離為準則，利用分裂法進一步剔除誤匹配對。

2.1 基于K-means 的誤匹配粗剔除方法

因此，對于集合C中的每一對匹配關系，利用2 個相對應的支持特征點集和，可計算從pi到qc(i)的旋轉矩陣Ri和平移向量ti：

在此基礎上，將旋轉矩陣Ri和平移向量ti中的元素按順序排列，得到1 個6 維向量。將集合C中的每1 對匹配關系都轉化為1 個6 維向量v，全部匹配關系轉換完成后，得到新的集合。

利用K-means 算法對Vtrans進行聚類，將其劃分成η類（η取值范圍通常為3～5）的步驟如下：

1）創建η個聚類集合和η個聚類中心，每個聚類中心都是一個6 維向量。

2）將Vtrans中的N個向量隨機分配至η個聚類集合中。

3）更新每一類的聚類中心：

4）遍歷Vtrans中每個向量vj，計算出與vj距離最近的聚類中心，并將vj劃分至相應的中。

5）循環執行步驟3）和步驟4），當Vtrans中的所有向量在每一類中都不再變化時，聚類劃分過程結束。

2.2 基于分裂法的誤匹配精剔除方法

1）將標準差的閾值設置為Tthresh，將剔除系數設置為λ。

4）循環執行步驟2）和步驟3），直到滿足這2 個步驟中任意一個停止條件，結束剔除。

經過上述過程，可以得到視頻序列前后兩幀圖像特征點集間的正確匹配關系，消除視頻跟蹤中因誤匹配對而造成的累計誤差，進而利用這些正確的匹配關系進行快速穩健的視頻跟蹤。

3 實驗仿真

為驗證本文提出的ME-GMS 方法在處理特征點錯誤匹配時的有效性和高效性，下文分兩部分進行配準跟蹤實驗。第一部分選擇OTB-100［21］數據集中Rubik、Dog 和Skater 視頻序列進行特征點的跨幀匹配實驗，并將SIFT［11］、SURF［13］、ORB［14］和GMS［17］作為對比算法；第二部分選擇OTB-100、VGG［22］和Strecha［23］數據集進行視頻序列的連續跟蹤實驗，并選擇主流的跟蹤算法GMS、ASLA［18］、HDT［19］和DCFCA［20］作為對比算法。本文算法均利用Python代碼實現，并運行在配置為Core i7-7700k 和16 GB RAM 的PC 機上。

3.1 視頻序列的跨幀匹配實驗

選擇OTB-100 數據集中的Rubik、Dog 和Skater 視頻序列進行特征點的跨幀匹配實驗，統計SIFT［11］、SURF［13］、ORB［14］、GMS［17］和ME-GMS 算法的正確匹配數量和錯誤匹配數量，以計算匹配精度，同時比較各算法的運行速度，實驗結果如圖1 和表1所示。

圖1 不同算法對Rubik、Dog 和Skater 視頻序列的跨幀匹配結果Fig.1 Cross-frame matching results of different algorithms for Rubik，Dog and Skater video sequences

表1 不同算法對Rubik、Dog 和Skater 視頻序列的跨幀匹配性能Table 1 Cross-frame matching performance of different algorithms for Rubik，Dog and Skater video sequences

從圖1 和表1 可以明顯看出：SIFT 算法與SURF算法的匹配精度較差，匹配結果中存在大量的錯誤匹配；ORB 算法的匹配精度略高于SIFT 算法和SURF 算法，但是仍有一定數量的錯誤匹配，并且容易出現匹配對簇集于一點的情況；相比于ORB 算法，GMS 算法錯誤匹配的數量有所減少，匹配精度進一步提高；而ME-GMS 算法借助ORB 算法高效的匹配效率，匹配速度僅僅稍低于ORB 算法，但大量地剔除了錯誤的匹配點，保留下正確的部分，因此匹配精度得以提高，且即使在處理難度較大的跨幀匹配時，也沒有出現錯誤匹配現象。對比實驗結果證明了ME-GMS 算法在視頻序列的跨幀匹配時仍具有較好的匹配效果。

由表1 還可以看出，ORB 算法的平均匹配精度為73.88%，ME-GMS 算法的平均匹配精度為98.15%，匹配精度提高了約33 個百分點，并且高于GMS 算法的平均匹配精度94.20%，這證明ME-GMS算法在進行視頻序列的跨幀匹配時比傳統的特征點匹配算法適應能力更強，匹配效果更好。

3.2 視頻序列的連續跟蹤實驗

選擇OTB-100，VGG 和Strecha 數據集進行視頻序列的連續跟蹤實驗。采用中心位置誤差（Center Location Error，CLE）、距離精度（Distance Precision，DP）和重疊精度（Overlap Precision，OP）［21］作為評價指標，中心位置誤差閾值設置為10 像素，重疊率閾值設置為0.7。本文算法與當前主流跟蹤算法GMS［17］、ASLA［18］、HDT［19］和DCFCA［20］的性能對比如表2所示。

表2 ME-GMS 算法與當前主流跟蹤算法的性能對比Table 2 Comparison of performance between ME-GMS and current mainstream tracking algorithms

從表2 可以看出，ME-GMS 算法在3 個視頻數據集上的平均跟蹤結果均優于其他4 種主流跟蹤算法，其中：平均CLE 達到4.13 像素，相比于其他4 種跟蹤算法平均提高了18%；平均DP 達到92.1%，相比于其他4 種跟蹤算法平均提高了9%；平均OP 達到90.1%，相比于其他4 種跟蹤算法平均提高了8%。ASLA 算法在目標與背景相似的情況下，出現了較多的誤匹配；HDL 算法由于其復雜結構，導致處理速度最低；DCFCA 算法的計算效率極高，但是隨著誤差的積累導致其他指標效果較差。實驗結果表明，ME-GMS 算法通過引入由粗到精的誤匹配對剔除策略，可以大幅減少不必要特征點的生成與匹配工作，對視頻序列實現更加穩定的跟蹤效果。在平均運行速度上，ME-GMS 算法排第二，略微低于DCFCA 算法，這也反映了ME-GMS 算法以較小的時間代價換取了跟蹤性能的較大提升。

圖2 是ME-GMS 算法與其他4 種主流跟蹤算法在3 個視頻數據集上測試的距離精度曲線對比。可以看出，ME-GMS 算法的距離精度曲線位置最高，說明該算法的跟蹤定位能力最強。圖3是ME-GMS算法與其他4 種主流跟蹤算法在3 個視頻數據集上測試的重疊精度曲線對比。重疊精度曲線可有效反映目標跟蹤算法的跟蹤精度，它與坐標軸圍成區域的面積越大，說明對應目標跟蹤算法的跟蹤性能越好。

綜合圖2 和圖3 可知，與其他4 種對比算法相比，ME-GMS 算法的距離精度曲線和重疊精度曲線位置都最高，說明ME-GMS 算法的跟蹤性能優于所對比的其他跟蹤算法，進一步驗證了基于K-means的誤匹配粗剔除方法和基于分裂法的誤匹配精剔除方法的有效性。

圖2 ME-GMS 算法與主流跟蹤算法的距離精度曲線對比Fig.2 Comparison of distance accuracy curves between ME-GMS and mainstream tracking algorithms

圖3 ME-GMS 算法與主流跟蹤算法的重疊精度曲線對比Fig.3 Comparison of overlapping accuracy curves between ME-GMS and mainstream tracking algorithm

4 結束語

本文提出一種新的視頻目標跟蹤方法ME-GMS。在GMS 方法框架下，對ORB 算法特征匹配階段產生的錯誤匹配對進行“粗-精”兩階段剔除，借助ORB算法高效的計算速度，在保證視頻序列跟蹤時效性的同時提高匹配精度。視頻序列的跨幀匹配和連續跟蹤實驗驗證了本文方法穩健高效的匹配性能。但是該方法在進行特征點誤匹配剔除時易受特征點提取質量的影響，即視頻目標在復雜環境下，如受到光照、遮擋等因素的干擾，會導致特征點本身提取效果較差，從而影響剔除的效果，使視頻跟蹤的整體性能下降。下一步將優化特征點提取方法，以實現更好的跟蹤效果。