一種基于特征點(diǎn)的快速跟蹤算法

劉雪琴，楊 媛，李 潔，宋煥生，b

(長安大學(xué)a.信息工程學(xué)院;b.陜西省道路交通智能檢測與裝備工程技術(shù)研究中心，陜西西安710064)

隨著監(jiān)控系統(tǒng)的逐漸應(yīng)用，視頻檢測技術(shù)迅速發(fā)展，交通事件檢測、交通參數(shù)檢測和交通狀況檢測等算法研究具有廣闊的研究背景。所以利用目標(biāo)跟蹤算法獲取車輛的準(zhǔn)確位置和運(yùn)動軌跡線，并為交通事件檢測、交通參數(shù)檢測和交通狀況檢測提供可靠的基礎(chǔ)數(shù)據(jù)成為國內(nèi)外專家研究的熱點(diǎn)。

目前常用的目標(biāo)跟蹤算法有基于區(qū)域的跟蹤、基于活動輪廓的跟蹤和基于特征的跟蹤等。基于區(qū)域的跟蹤［1］方法的主要思想是利用區(qū)域的時(shí)間相關(guān)性來實(shí)現(xiàn)目標(biāo)的跟蹤，就是在時(shí)域上檢測出的一個(gè)個(gè)像素連通塊，這些塊組成矩形模板，然后實(shí)現(xiàn)跟蹤。這種方法對于單目標(biāo)跟蹤效果很好，對于多目標(biāo)跟蹤，則相對復(fù)雜一些，而且需要消耗較多的時(shí)間?；诨顒虞喞母櫍?－4］是利用封閉的曲線輪廓來表達(dá)運(yùn)動目標(biāo)，并且在后續(xù)幀圖像中更新輪廓來達(dá)到目標(biāo)連續(xù)跟蹤的目的。相對于基于區(qū)域的跟蹤，此方法減少了算法復(fù)雜度，但是合理地區(qū)分多個(gè)運(yùn)動目標(biāo)并實(shí)現(xiàn)輪廓曲線的初始化是十分困難的?；谔卣鞯母櫡椒ǎ?］是利用相鄰幀中運(yùn)動目標(biāo)的個(gè)體特征的匹配來實(shí)現(xiàn)跟蹤。與基于區(qū)域的跟蹤方法的不同的是基于特征的跟蹤方法使用運(yùn)動目標(biāo)的某一個(gè)或者多個(gè)體特征作為相關(guān)時(shí)的對象。用于匹配的個(gè)體特征可以是全局特征，如運(yùn)動目標(biāo)的周長、面積、質(zhì)心等，也可以是線段、角點(diǎn)等局部特征?；谔卣鞯母櫡椒ū容^簡單，但計(jì)算量大，實(shí)時(shí)性差［6］。

本文提出了一種基于特征點(diǎn)的快速跟蹤算法，能夠快速地實(shí)現(xiàn)運(yùn)動初始化，準(zhǔn)確提取特征角點(diǎn)，快速匹配，實(shí)現(xiàn)穩(wěn)定跟蹤。

1 算法介紹

本算法是基于特征點(diǎn)的跟蹤算法，主要包括特征角點(diǎn)提取和特征匹配兩個(gè)過程。

1.1 運(yùn)動目標(biāo)檢測

通過運(yùn)動目標(biāo)檢測提取出圖像序列中的運(yùn)動信息，可以限定特征角點(diǎn)的提取范圍，減少計(jì)算量。本文選擇對光線等場景變化不太敏感的幀間差分法［7－8］來檢測運(yùn)動目標(biāo)。幀間差分法主要是利用當(dāng)前幀與之前相鄰幀的像素差值來確定運(yùn)動區(qū)域。有運(yùn)動目標(biāo)的區(qū)域，像素灰度變化較大，沒有運(yùn)動目標(biāo)的區(qū)域，像素灰度變化較小，以此來區(qū)分。

圖1是基于塊的幀差法檢測到的運(yùn)動目標(biāo)區(qū)域。

圖1 幀差法的運(yùn)動目標(biāo)檢測

圖1是用當(dāng)前幀(k幀)與之前相隔3幀(k－3幀)的圖像差分而得到的目標(biāo)區(qū)域，可以看到，由于車輛在k－3幀時(shí)的位置相對于k幀滯后，則k－3幀車尾處在當(dāng)前幀上已成路面，檢測到的運(yùn)動區(qū)域正好包含了這部分路面，如圖1b中方框所示。誤選的路面區(qū)域會對角點(diǎn)提取產(chǎn)生影響，有時(shí)選擇的角點(diǎn)就是在路面上。

為了盡量將檢測到的區(qū)域定位在車輛身上，為防止誤選，更準(zhǔn)確地分割出運(yùn)動車輛，將兩次幀差結(jié)果相與來判斷運(yùn)動目標(biāo)。具體表達(dá)式為

式中:fk(x，y)，fk－i(x，y)和fk+i(x，y)分別代表第k幀圖像、第k－i幀圖像和第k+i幀圖像;Dk(x，y)表示第k幀圖像與第k－i幀圖像幀差結(jié)果;Sk(x，y)表示第k幀圖像與第k+i幀圖像幀差結(jié)果。

式中:T是二值化設(shè)定的閾值。處理結(jié)果如圖2所示。

圖2 改進(jìn)后的幀差法效果圖

上述處理結(jié)果說明將兩次幀差結(jié)果相與，能夠消除誤選中的路面，更準(zhǔn)確地進(jìn)行運(yùn)動車輛檢測。

1.2 角點(diǎn)提取

得到運(yùn)動區(qū)域后，對其進(jìn)行角點(diǎn)提取。目前常用的角點(diǎn)提取算法有Sobel和Moravec等算法。

1)Sobel算法［9］

Sobel算法是一種快速的邊緣提取算法，包含橫向和縱向兩組的3×3模板，通過與圖像數(shù)據(jù)做平面卷積，得到橫向與縱向的灰度差值變化，來檢測邊緣變化情況。其橫向和縱向模板如圖3所示。

圖3 Sobel算法模板

Sobel算法抗噪性能差，容易選中偽角點(diǎn)，而且不能保證選中角點(diǎn)具有良好的可跟蹤性。圖4中只有一個(gè)角點(diǎn)，該角點(diǎn)位于車輛前端與道路的臨界處，對它進(jìn)行跟蹤，發(fā)現(xiàn)軌跡線并不光滑，說明這個(gè)角點(diǎn)不適合作為跟蹤初始點(diǎn)。

圖4 Sobel算法提取到的不穩(wěn)定跟蹤點(diǎn)

2)Moravec 算法［10］

Moravec是一種利用灰度方差提取角點(diǎn)的算法。主要思想為:以像素點(diǎn)(x，y)為中心確定大小為w×w的窗口(如5×5的窗口)，如圖5、圖6所示。

圖5 Moravec檢測窗

將圖6與圖4相比，Moravec算法沒有在車輛前端提取角點(diǎn)，而是在車身上提取了3個(gè)角點(diǎn)，這3個(gè)角點(diǎn)比So-bel算法提取的角點(diǎn)更加穩(wěn)定。所以本文選取Moravec算法進(jìn)行角點(diǎn)檢測。

圖6 Moravec算法提取角點(diǎn)及跟蹤效果

1.3 構(gòu)造模板

傳統(tǒng)的匹配模板使用以角點(diǎn)為中心的一整塊矩形區(qū)域的灰度數(shù)據(jù)來構(gòu)造，常常是將平滑區(qū)域與不平滑區(qū)域都包含了進(jìn)來。這種模板需要記錄的信息少，使用方便，但是會導(dǎo)致后續(xù)跟蹤計(jì)算量大。因此，本文使用一種改進(jìn)的模板。

改進(jìn)的模板在基本模板的基礎(chǔ)上，去掉平滑區(qū)域，只用不平滑區(qū)域來構(gòu)建模板。將整個(gè)模板分成5×5個(gè)小塊，采用分層處理，并使用外螺旋順序進(jìn)行標(biāo)記，以塊1為中心，塊2～塊9為內(nèi)層，塊10～塊25為外層，如圖7所示。

圖7 模板示意圖

對于新建的結(jié)構(gòu)化模板，選取6個(gè)小塊構(gòu)建新的模板。對于這25個(gè)小塊。理論上認(rèn)為越靠近中心塊的小塊，對跟蹤影響越大，因此盡可能選取靠近中心的小塊。新的模板保留中心塊塊1，在內(nèi)層8個(gè)塊中選取3個(gè)，外層16個(gè)塊中選取2個(gè)。

除中心塊外，其他5個(gè)塊的選擇采用改進(jìn)的角點(diǎn)選擇算法，也就是對其他24個(gè)塊運(yùn)用公式計(jì)算每個(gè)塊的角點(diǎn)度量值，然后分別對內(nèi)層和外層的各個(gè)塊進(jìn)行比較，分別留下角點(diǎn)度量值最大的3個(gè)和2個(gè)塊。

改進(jìn)的模板表示方法相對于基本的模板表示方法來說，減少了跟蹤匹配計(jì)算至少19/25的時(shí)間消耗。為車輛的實(shí)時(shí)跟蹤提供了必要的條件。

1.4 匹配搜索

本文使用塊匹配跟蹤算法，塊匹配跟蹤算法對運(yùn)動模板跟蹤的思想［11］是:對于第N－1幀圖像中的角點(diǎn)(x1，y1)，在其周圍一定區(qū)域內(nèi)構(gòu)造一個(gè)匹配模板template1，在當(dāng)前幀(第N幀)圖像上的一定范圍(成為匹配窗)內(nèi)按照一定的匹配準(zhǔn)則搜索和該模板最接近的模板template2(稱為預(yù)測模板)，那么就認(rèn)為該模板的中心位置(x2，y2)為前一時(shí)刻的模板移動后現(xiàn)在的新位置。如圖8所示。

圖8 塊匹配跟蹤算法示意圖

搜索策略使用全搜索法。全搜索法，即對搜索范圍內(nèi)的所有位置依次進(jìn)行計(jì)算，選擇與模板最相似的小塊作為匹配塊，該方法計(jì)算量大，但是精確度最高。

待匹配小塊與目標(biāo)模板的相似性由匹配準(zhǔn)則得到。匹配準(zhǔn)則選取了運(yùn)算次數(shù)小且運(yùn)算復(fù)雜度低的SAD算法。表達(dá)如下

式中:f(i，j)表示待匹配塊中(i，j)位置處像素的灰度值;g(i，j)為模板中(i，j)位置處像素的灰度值。

起始搜索位置為角點(diǎn)的當(dāng)前位置，搜索范圍為以角點(diǎn)為中心的一個(gè)一定寬度的正方形區(qū)域。如果跟蹤目標(biāo)進(jìn)行頻繁的不規(guī)則運(yùn)動，這樣的搜索窗設(shè)置是恰當(dāng)?shù)?。但是本文跟蹤的運(yùn)動目標(biāo)是道路上行駛的車輛，其運(yùn)動路線和方向都是有一定規(guī)律的。這樣，再選擇這樣的設(shè)置，就會在非目標(biāo)區(qū)域做了很多的無用工作，所以考慮利用過去時(shí)刻角點(diǎn)的位置和運(yùn)動矢量，來對當(dāng)前時(shí)刻匹配角點(diǎn)的大概位置進(jìn)行預(yù)測，以預(yù)測結(jié)果來設(shè)置初始搜索位置和搜索窗，這樣至少可以將搜索窗縮小到原來的1/4，相應(yīng)地至少可以減少3/4的時(shí)間消耗，提高實(shí)時(shí)性。

當(dāng)穩(wěn)定跟蹤得到一定數(shù)量的匹配點(diǎn)后，可以對目標(biāo)進(jìn)行預(yù)測。根據(jù)最近幾幀的n個(gè)匹配點(diǎn)之間的距離預(yù)測下一幀的匹配點(diǎn)，公式如下

式中:dis_x和dis_y為最近幾幀的n個(gè)匹配點(diǎn)之間的橫向距離和縱向距離;block［k］.position［count］為第k條軌跡的第count個(gè)匹配點(diǎn)的位置信息;predictx和predicty為x和y方向預(yù)測值。

預(yù)測結(jié)果顯示了新匹配點(diǎn)最可能出現(xiàn)的位置，則搜索范圍可以相應(yīng)地縮小到包含預(yù)測點(diǎn)的小范圍區(qū)域中，減少了計(jì)算量和時(shí)間消耗。如圖9所示。

圖9 改進(jìn)的搜索范圍示意圖

2 實(shí)驗(yàn)結(jié)果

本文給出了幾種不同的場景(見圖10)對本文的算法進(jìn)行驗(yàn)證。第1種場景攝于下午，圖像較為清晰;第2種場景攝于傍晚，且為陰天天氣，圖像較暗，對比度不高;第3種場景攝于隧道內(nèi)，圖像比較清晰;第4種場景攝于雨霧天氣，圖像清晰度低，噪聲干擾較大。

圖10 不同場景下跟蹤結(jié)果

由4種場景中的跟蹤軌跡可見，運(yùn)動本文的算法能夠在不同場景下實(shí)現(xiàn)運(yùn)動目標(biāo)的實(shí)時(shí)有效跟蹤，跟蹤效果準(zhǔn)確度高，本算法對噪聲、夜晚環(huán)境、霧雪等環(huán)境具有良好的魯棒性。

3 總結(jié)

常用的跟蹤算法時(shí)間復(fù)雜度大、實(shí)時(shí)性差，本文提出的一種基于特征點(diǎn)的快速跟蹤算法，有效解決了這個(gè)問題。本文在基礎(chǔ)算法上，采用兩次幀差結(jié)果相與來進(jìn)行運(yùn)動檢測，為更準(zhǔn)確地提取角點(diǎn)提供有了有利條件;為提高跟蹤的準(zhǔn)確性和實(shí)時(shí)性，利用不平滑區(qū)域來構(gòu)造模板;最后針對該方法的計(jì)算量大、實(shí)時(shí)性差的缺點(diǎn)，使用了目標(biāo)匹配點(diǎn)預(yù)測算法，并根據(jù)預(yù)測點(diǎn)縮小搜索范圍，減少運(yùn)算量，提高搜索效率和實(shí)時(shí)性。實(shí)驗(yàn)表明，該算法能夠克服計(jì)算量大、實(shí)時(shí)性差等缺點(diǎn)，并能得到較好的跟蹤效果，為后續(xù)處理提供可靠的數(shù)據(jù)。

［1］ GU C，LEEM.Semiautomatic segmentation and tracking of semantic video objects［J］.IEEE Trans.Circuits and Systems for Video Technology，1998，8(5):572－584.

［2］ PARAGIOSN，DERICHE R.Geodesic a tive contours and levelsets for the detection and Tracking of moving objects［J］.IEEE Trans.Patern A-nalysis and Machine Intelligence，2000，22(3):266－280.

［3］ BERTALMIO M，SAPIROO G，RANDLL G.Morphing active contours［J］.IEEE Trans.Patern Analysis and Machine Intelligence，2000，22(7):733－737.

［4］ PETERFREUND N.Robust tracking of position and velocity with Kalmans nakes［J］.IEEE Trans.Patern Analysis and Machine Intelligence，2000，22(6):564－569.

［5］ ZHOU H，YUAN Y，SHI C.Object tracking using SIFT features and meanshift［J］.Computer Vision and Image Understanding，2009，113(3):345－352.

［6］丁艷，金偉其，薛雪.基于加權(quán)相關(guān)的圖像匹配跟蹤算法研究［J］.彈箭與制導(dǎo)學(xué)報(bào)，2009，29(4):58－62.

［7］ WANG J，WANG D.Particle swarm optimization with a leader and followers［J］.Progress in Natural Science，2008，18(11):1437－1443.

［8］ LONGW，YANG Y.Stationary background generation:an alternative to the difference of two images［J］.Pattern Recognition，1990，23(12):1351－1359 .

［9］江雯，陳更生，楊帆，等.基于Sobel算子的自適應(yīng)圖像縮放算法［J］.計(jì)算機(jī)工程，2010，36(7):214－216.

［10］盧瑜，郝興文，王永俊.Moravec和Harris角點(diǎn)檢測方法比較研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(6):95－100.

［11］劉海華，雷奕，謝長生.基于塊匹配的運(yùn)動估計(jì)搜索算法研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用，2006，26(6):1354－1364.