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

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

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

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

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

1 算法介紹

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

1.1 運(yùn)動(dòng)目標(biāo)檢測(cè)

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

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

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

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

為了盡量將檢測(cè)到的區(qū)域定位在車(chē)輛身上，為防止誤選，更準(zhǔn)確地分割出運(yùn)動(dòng)車(chē)輛，將兩次幀差結(jié)果相與來(lái)判斷運(yùn)動(dòng)目標(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é)果說(shuō)明將兩次幀差結(jié)果相與，能夠消除誤選中的路面，更準(zhǔn)確地進(jìn)行運(yùn)動(dòng)車(chē)輛檢測(cè)。

1.2 角點(diǎn)提取

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

1)Sobel算法［9］

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

圖3 Sobel算法模板

Sobel算法抗噪性能差，容易選中偽角點(diǎn)，而且不能保證選中角點(diǎn)具有良好的可跟蹤性。圖4中只有一個(gè)角點(diǎn)，該角點(diǎn)位于車(chē)輛前端與道路的臨界處，對(duì)它進(jìn)行跟蹤，發(fā)現(xiàn)軌跡線并不光滑，說(shuō)明這個(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檢測(cè)窗

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

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

1.3 構(gòu)造模板

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

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

圖7 模板示意圖

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

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

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

1.4 匹配搜索

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

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

搜索策略使用全搜索法。全搜索法，即對(duì)搜索范圍內(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)動(dòng)，這樣的搜索窗設(shè)置是恰當(dāng)?shù)?。但是本文跟蹤的運(yùn)動(dòng)目標(biāo)是道路上行駛的車(chē)輛，其運(yùn)動(dòng)路線和方向都是有一定規(guī)律的。這樣，再選擇這樣的設(shè)置，就會(huì)在非目標(biāo)區(qū)域做了很多的無(wú)用工作，所以考慮利用過(guò)去時(shí)刻角點(diǎn)的位置和運(yùn)動(dòng)矢量，來(lái)對(duì)當(dāng)前時(shí)刻匹配角點(diǎn)的大概位置進(jìn)行預(yù)測(cè)，以預(yù)測(cè)結(jié)果來(lái)設(shè)置初始搜索位置和搜索窗，這樣至少可以將搜索窗縮小到原來(lái)的1/4，相應(yīng)地至少可以減少3/4的時(shí)間消耗，提高實(shí)時(shí)性。

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

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

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

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

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

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

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

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

3 總結(jié)

常用的跟蹤算法時(shí)間復(fù)雜度大、實(shí)時(shí)性差，本文提出的一種基于特征點(diǎn)的快速跟蹤算法，有效解決了這個(gè)問(wèn)題。本文在基礎(chǔ)算法上，采用兩次幀差結(jié)果相與來(lái)進(jìn)行運(yùn)動(dòng)檢測(cè)，為更準(zhǔn)確地提取角點(diǎn)提供有了有利條件;為提高跟蹤的準(zhǔn)確性和實(shí)時(shí)性，利用不平滑區(qū)域來(lái)構(gòu)造模板;最后針對(duì)該方法的計(jì)算量大、實(shí)時(shí)性差的缺點(diǎn)，使用了目標(biāo)匹配點(diǎn)預(yù)測(cè)算法，并根據(jù)預(yù)測(cè)點(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)檢測(cè)方法比較研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(6):95－100.

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