淺析特征點(diǎn)匹配的自適應(yīng)目標(biāo)跟蹤算法

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

0 引言

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

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

鑒于特征點(diǎn)在運(yùn)動目標(biāo)發(fā)生尺度、旋轉(zhuǎn)變化或是被遮擋時仍能夠被檢測到，本文采用圖像特征點(diǎn)作為運(yùn)動目標(biāo)的描述特征，提出一種基于特征點(diǎn)匹配的自適應(yīng)運(yùn)動目標(biāo)跟蹤算法，以達(dá)到在復(fù)雜環(huán)境下對目標(biāo)進(jìn)行穩(wěn)定的跟蹤。算法根據(jù)輸入的初始目標(biāo)矩形框，首先提取目標(biāo)的特征點(diǎn)作為目標(biāo)的初始特征。

獲取一幀新的圖像后，在搜索區(qū)域內(nèi)提取特征點(diǎn)，然后與上一幀中的目標(biāo)特征點(diǎn)進(jìn)行匹配，根據(jù)匹配結(jié)果估計出目標(biāo)的位置、尺度和旋轉(zhuǎn)變化，使用這些變化值更新上一幀目標(biāo)的跟蹤結(jié)果，完成當(dāng)前幀目標(biāo)跟蹤任務(wù)。同時更新目標(biāo)特征點(diǎn)，以使得算法具有一定的抗遮擋能力。

1 特征點(diǎn)匹配

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

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

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

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

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

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

2 自適應(yīng)目標(biāo)跟蹤算法

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

其中，Pi-1和Pi分別為Mi-1和Mi的重心。目標(biāo)在運(yùn)動過程中也時常會出現(xiàn)尺度和旋轉(zhuǎn)變化，可以根據(jù)以下兩個公式計算出目標(biāo)在Ii-1與Ii幀之間的尺度和旋轉(zhuǎn)變化：

其中，ai、aj為Mi中任意兩個點(diǎn)，bi、bj為Mi-1中分別與ai、aj對應(yīng)的兩個點(diǎn)，s為估計出的目標(biāo)尺度縮放因子，

為目標(biāo)從第i-1到i幀發(fā)生旋轉(zhuǎn)的旋轉(zhuǎn)角度，R為旋轉(zhuǎn)矩陣。

的計算方法如下：

估計出目標(biāo)的位移、尺度和旋轉(zhuǎn)變化之后，就可以計算出第Ii+1中的目標(biāo)。

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

算法1

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

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

具體步驟為：

（1）獲取一幀圖像Ii；

（2）若i=1，則在R1范圍內(nèi)提取FAST特征點(diǎn)，獲得O1，轉(zhuǎn)到1；

（3）將Ri-1適當(dāng)擴(kuò)大得到目標(biāo)搜索區(qū)域，在該區(qū)域內(nèi)計算O，O與Oi-1進(jìn)行匹配獲得匹配點(diǎn)對集合Mi、Mi-1；

（4）根據(jù)式（2）~（4）計算出目標(biāo)的位移

尺度變化因子s和旋轉(zhuǎn)矩陣R；

（5）根據(jù)式（6）計算出目標(biāo)新的外接矩形框Ri，并更新目標(biāo)特征點(diǎn)集合，獲得Oi；

（6）處理完成則算法結(jié)束，否則轉(zhuǎn)到步驟（1）。

3 實(shí)驗(yàn)與結(jié)果分析

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

4 結(jié)論

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

參考文獻(xiàn)

［1］ 高韜，劉正光，張軍，等?；谔卣鼽c(diǎn)的多運(yùn)動目標(biāo)跟蹤［J］。電子與信息學(xué)報，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的目標(biāo)跟蹤算法［J］。江南大學(xué)學(xué)報（自然科學(xué)版），2012，11（5）：515-518.

［8］ 梅振順，戰(zhàn)蔭偉，鐘左峰?；赟URF特征的目標(biāo)跟蹤［J］。中國體視學(xué)與圖像分析，2011，16（1）：28-32.

［9］ 李明?；赟IFT特征點(diǎn)匹配的目標(biāo)跟蹤算法研究［D］。合肥：合肥工業(yè)大學(xué)，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］ 趙登科。立體視覺測量中的點(diǎn)特征提取與匹配算法［D］。沈陽：沈陽理工大學(xué)，2013.

［12］ 劉潔。基于特征點(diǎn)的目標(biāo)檢測與跟蹤方法研究［D］。成都：電子科技大學(xué)，2008.

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

編輯：jq