摘 要： 由于實際場景復雜多變，目標在運動過程中往往會出現形變、遮擋等問題，增加了跟蹤的難度。為了解決上述問題，提出一種基于特征點匹配的自適應目標跟蹤算法。算法初始化時在選定的目標區域內提取特征點，跟蹤過程中通過對前后兩幀的特征點進行匹配，計算出目標的位置、尺度和旋轉變化，進而實現對目標的跟蹤。同時通過對特征點的不斷更新，可以使算法具有一定的抗遮擋能力。實驗表明，該方法在實際應用中效果很好。

0 引言

目標跟蹤算法作為視頻分析的基本內容之一，受到了廣泛的關注，近年來研究人員提出了很多具有針對性的方法，然而由于實際場景的復雜性，目標在運動過程中往往會發生劇烈的形變，部分或完全被遮擋，現有跟蹤算法很難完全克服這些問題，還需要進一步研究［1］。由于目標的局部特征在運動過程中比全局特征具有更好的穩定性，且在遮擋情況下仍有一部分局部特征存在，為此研究人員相繼提出了許多基于局部特征的目標跟蹤算法［2］，希望從這個角度出發解決較大形變或者被遮擋目標的跟蹤問題。

目前常用的局部特征包括HARRIS［3］、SIFT［4］、FAST［5］、BRISK［6］等。參考文獻［7-8］采用SURF特征點匹配的方法實現運動目標跟蹤，具有一定的抗形變和遮擋能力。參考文獻［9］對SIFT特征點進行了研究，提出一種基于改進SIFT特征點匹配的目標跟蹤算法。參考文獻［10］對MeanShift算法的跟蹤結果進行FAST-9特征點匹配，計算出目標的尺度變化，使得算法在原有高效率的基礎上具有了更好的抗尺度變化的能力。

鑒于特征點在運動目標發生尺度、旋轉變化或是被遮擋時仍能夠被檢測到，本文采用圖像特征點作為運動目標的描述特征，提出一種基于特征點匹配的自適應運動目標跟蹤算法，以達到在復雜環境下對目標進行穩定的跟蹤。算法根據輸入的初始目標矩形框，首先提取目標的特征點作為目標的初始特征。

獲取一幀新的圖像后，在搜索區域內提取特征點，然后與上一幀中的目標特征點進行匹配，根據匹配結果估計出目標的位置、尺度和旋轉變化，使用這些變化值更新上一幀目標的跟蹤結果，完成當前幀目標跟蹤任務。同時更新目標特征點，以使得算法具有一定的抗遮擋能力。

1 特征點匹配

圖像中的特征點通常是指與周圍像素值存在明顯差異，顏色值不連續的點，一般包括線段交點、重心點、高差異的點、局部曲率不連續點、曲線拐點、小波變換的局部極值點、角點以及興趣算子點等[11]。通常特征點都具有一定的旋轉、平移、尺度縮放不變性，對光照變化保持一定的不變性[12]。

考慮到跟蹤算法實時性的要求，選用FAST特征點來進行目標跟蹤。FAST特征點是由ROSTEN E和DRUMMOND T于2006年提出的一種簡單快速的特征點檢測算法，相比于其他的特征點檢測算法，它的計算速度有了很大程度的提高。FAST特征點是指在該像素點的周圍鄰域內，有足夠多的像素點與該點的顏色值相差較大，也就是說在圖像中FAST特征點與其周圍像素點顏色值不同，如圖1中的A、B兩點。那么根據式（1）可以判斷圖像中的某像素點是否為FAST特征點：

其中，p為要進行計算的像素點，x為p以為圓心、半徑為3的圓上的任意一點，I（x）和I（p）分別為x和p的顏色值，εd為顏色差值的閾值，當N大于一定的閾值N0且圓上的N個點中至少有N0個點是連續無中斷的，則認為p為FAST特征點。對于半徑為3的圓形鄰域模板，通常情況下N0取12。

為了提高FAST特征點的檢測效率，還可以采用附件的加速技巧，首先判斷候選點的圓周上被90°分割的4個頂點處的像素是否滿足條件，參見圖1中的1、5、9、13這4個點。若這4個點中至少有3個點滿足條件，即與候選點的像素值相差大于設定的閾值，則繼續判斷圓周上其他的點；否則就認為該候選點不是FAST特征點。

在算法的處理過程中，根據上一幀的跟蹤結果確定當前幀中目標的搜索區域，再根據以上描述的方法提取出搜索區域的FAST特征點，然后將當前搜索區域的FAST特征點與上一幀中目標的FAST特征點進行匹配。匹配方法如下：計算出要匹配的兩個FAST特征點集合中每一個特征點在另一個特征點集合中的最近鄰和次近鄰，若特征點和最近鄰之間的距離與其到次近鄰的距離之間的比值小于一定的閾值時，就認為此最近鄰是樣本的一個初始匹配。

為了提高特征點的近鄰計算速度，將FAST特征點集構造成BEIS J等人提出的一種改進K-d樹（K-dimension tree），然后使用BBF（Best Bin First）算法計算特征點的最近鄰和次近鄰[13]。獲得粗匹配結果之后，再使用RANSAC算法進一步剔除錯誤匹配，提高匹配正確率，最終得到精度較高的匹配結果。得到的高精度匹配結果可以更好地應用于后續的自適應目標跟蹤算法。

2 自適應目標跟蹤算法

通過手動選擇或者采用運動目標檢測算法選中要跟蹤的目標之后，可以獲得該目標的外接矩形框R1，采用上面敘述的方法提取目標的FAST特征點集合O1，通過上述兩步，完成算法初始化工作。在對目標進行跟蹤的過程中，假設當前獲取的視頻圖像為Ii幀，第Ii-1幀圖像中算法獲得的目標外接矩形框為Ri-1，目標的FAST特征點集合為Oi-1，由于兩幀之間的時間間隔有限，目標的移動范圍也是小距離的，對Ri-1進行適當放大可以獲得Ii幀中的目標搜索區域，在搜索區域中提取FAST特征點集合O，O與Oi-1進行匹配，獲得匹配點集合對Mi-1、Mi。第Ii-1與Ii幀之間目標的位移可以通過下式估計出：

其中，Pi-1和Pi分別為Mi-1和Mi的重心。目標在運動過程中也時常會出現尺度和旋轉變化，可以根據以下兩個公式計算出目標在Ii-1與Ii幀之間的尺度和旋轉變化：

其中，ai、aj為Mi中任意兩個點，bi、bj為Mi-1中分別與ai、aj對應的兩個點，s為估計出的目標尺度縮放因子，

為目標從第i-1到i幀發生旋轉的旋轉角度，R為旋轉矩陣。

的計算方法如下：

估計出目標的位移、尺度和旋轉變化之后，就可以計算出第Ii+1中的目標。

式（6）中Vi-1為Ri-1的頂點，根據Vi可以獲得第Ii幀中目標的外接矩形框Ri。當Mi中特征點個數小于一定閾值時，選取O中位于Ri中的特征點添加到Mi中，獲得Ii幀中的目標特征點集合Oi。算法1中描述了該自適應目標跟蹤算法。

算法1

輸入：視頻幀序列I1，I2，…，Ii，…，In和初始目標的外接矩形框R1。

輸出：每幀圖像中的跟蹤目標外接矩形框R2，…，Ri，…，Rn。

具體步驟為：

（1）獲取一幀圖像Ii；

（2）若i=1，則在R1范圍內提取FAST特征點，獲得O1，轉到1；

（3）將Ri-1適當擴大得到目標搜索區域，在該區域內計算O，O與Oi-1進行匹配獲得匹配點對集合Mi、Mi-1；

（4）根據式（2）~（4）計算出目標的位移

尺度變化因子s和旋轉矩陣R；

（5）根據式（6）計算出目標新的外接矩形框Ri，并更新目標特征點集合，獲得Oi；

（6）處理完成則算法結束，否則轉到步驟（1）。

3 實驗與結果分析

為了驗證算法的有效性，選取了多種場景下的運動目標，對算法進行了多組實驗，實驗結果如圖2所示。實驗使用的硬件環境為：CPU為Pentium（R）Dual-CoreE6700（主頻為3.2 GHz），內存2 GB，軟件平臺為：操作系統Windows 7（32位），使用C++語言在Microsoft Visual Studio 2010進行編程，調用OpenCV圖像處理庫，所提出的方法對非剛體的行人、剛體的汽車以及旋轉角度很大的物體都能有較好的跟蹤效果。

4 結論

針對跟蹤目標在運動過程中會發生尺度和旋轉變化導致跟蹤失敗的問題提出一種采用局部特征點匹配的運動目標跟蹤算法，通過實驗可以發現該算法能夠很好地適應目標的縮放和旋轉變化，對目標一直保持穩定的跟蹤，且通過對跟蹤過程中目標特征點的更新，使得該方法具有一定的抗遮擋能力，具有較好的實用性。不過未來還需要對算法進行更多的實驗和改進，以進一步提高算法的魯棒性和實時性。

參考文獻

［1］ 高韜，劉正光，張軍，等。基于特征點的多運動目標跟蹤［J］。電子與信息學報，2010.5，32（5）：1111-1115.

［2］ NEBEHAY G， PFLUGFELDER R. Consensus-based matching and tracking of keypoints for object tracking［C］。 Winter Conference on Applications of Computer Vision， 2014： 862-869.

［3］ HARRIS C， STEPHENS M. A combined comer and edge detector［A］。 Proceedings of the 4th Alvey Vision Conference［C］。 Manchester， UK， 1988：147-151.

［4］ LOWE D G. Distinctive image features from scale-invariant keypoints［J］。 International Journal of Computer Vision， 2004，60（2）：91-110.

［5］ ROSTEN E， DRUMMOND T. Machine learning for high-speed corner detection［C］。 European Conference on Computer Vision， 2006：430-443.

［6］ LEUTENEGGER S， CHLI M， SIEGWART R. Brisk： binary robust invariant scalable keypoints［C］.Computer Vision-ICCV，2011： 2548-2555.

［7］ 王露露，張洪，高忠國。基于SURF的目標跟蹤算法［J］。江南大學學報（自然科學版），2012，11（5）：515-518.

［8］ 梅振順，戰蔭偉，鐘左峰。基于SURF特征的目標跟蹤［J］。中國體視學與圖像分析，2011，16（1）：28-32.

［9］ 李明。基于SIFT特征點匹配的目標跟蹤算法研究［D］。合肥：合肥工業大學，2011.

［10］ Song Yi， Li Shuxiao， Chang Hongxing. Scale adaptive mean shift tracking based on feature point matching［C］.2013 Second IAPR Asian Conference on Pattern Recognition， 2013：220-224.

［11］ 趙登科。立體視覺測量中的點特征提取與匹配算法［D］。沈陽：沈陽理工大學，2013.

［12］ 劉潔。基于特征點的目標檢測與跟蹤方法研究［D］。成都：電子科技大學，2008.

［13］ 王永明，王貴錦。圖像局部不變性特征與描述［M］。北京：國防工業出版社，2010.

編輯：jq