圖像邊緣特征檢測(cè)實(shí)現(xiàn)多目標(biāo)跟蹤的有序匹配算法研究

王 琪

(江蘇聯(lián)合職業(yè)技術(shù)學(xué)院揚(yáng)州分院繼續(xù)教育部 江蘇揚(yáng)州 225003)

0 引言

在視頻車(chē)輛檢測(cè)方面，單一的特征計(jì)算相對(duì)簡(jiǎn)單高效，對(duì)高速公路這類簡(jiǎn)單環(huán)境情況下的目標(biāo)檢測(cè)具有較好效果。但其實(shí)用性不強(qiáng)，對(duì)噪聲干擾較為敏感，特別在有行道樹(shù)、云彩、行人天橋、建筑物等相似干擾目標(biāo)出現(xiàn)時(shí)，誤檢率迅速增加。對(duì)于解決城區(qū)復(fù)雜交通場(chǎng)景下的目標(biāo)檢測(cè)問(wèn)題，單靠某一種特征計(jì)算很難完成檢測(cè)任務(wù)，每種特征計(jì)算都有一定的適用范圍，多特征組合方法是當(dāng)前主流[1]。另外，基于先驗(yàn)知識(shí)的特征計(jì)算很容易受到環(huán)境噪聲干擾，適應(yīng)性差。區(qū)域統(tǒng)計(jì)特征計(jì)算由于具有相對(duì)穩(wěn)定、魯棒性強(qiáng)、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，已成為當(dāng)前目標(biāo)檢測(cè)的熱點(diǎn)。

1 特征提取

特征提取在圖像處理研究中具有重要的地位，眾多學(xué)者對(duì)特征提取的方法進(jìn)行了大量的研究。特征提取的種類不僅是對(duì)形狀特征的提取，還有對(duì)顏色特征、空間特征的提取。在目前的形狀特征提取研究中，有兩種表示方法：一種是以圖像輪廓或邊界進(jìn)行特征提取，另一種是對(duì)圖像所在區(qū)域進(jìn)行特征提取[2]。前者目標(biāo)是圖像的邊界，后者目標(biāo)是圖像的整個(gè)區(qū)域。以下是比較常見(jiàn)的特征提取方法：

1) 邊界描述特征法?；贖ough的邊界特征法的基本思想主要是通過(guò)對(duì)邊緣特征的描述獲取圖像的基本形狀參數(shù)。Hough是利用圖像的區(qū)域特性將邊緣組成一種封閉的區(qū)域邊界，其基本思想是將集中的點(diǎn)連成線。邊界直方圖的基本思想是求出圖像的邊緣，然后做出有關(guān)于邊緣方向的直方圖。

2) 幾何法。將形狀的表達(dá)方式變?yōu)閿?shù)學(xué)的幾何表達(dá)方式。每個(gè)圖像都有周長(zhǎng)和面積等幾何參數(shù)。

3) 區(qū)域參數(shù)法。每一個(gè)實(shí)物都有其區(qū)域，而這個(gè)方法就是將實(shí)物區(qū)域作為不變量來(lái)描述形狀。

為了更好地解決在城市復(fù)雜環(huán)境下的車(chē)載多目標(biāo)檢測(cè)問(wèn)題，本文通過(guò)對(duì)特征的選擇對(duì)比分析發(fā)現(xiàn)，統(tǒng)計(jì)特征以及組合特征均能在復(fù)雜環(huán)境下具有較好的魯棒性。本文選擇提取車(chē)輛外框以及人的頭肩等區(qū)域信息，這些區(qū)域均具有明顯的固定邊緣和線性特征，這也是本文檢測(cè)的目標(biāo)區(qū)別于其他目標(biāo)(如：橋梁、樹(shù)等非規(guī)則目標(biāo))較為顯著之處。在此基礎(chǔ)上，提出采用Harr與HOG組合特征的兩步目標(biāo)檢測(cè)算法。Harr特征能夠很好地表達(dá)目標(biāo)邊緣和線性，盡管該特征比較粗略，但通過(guò)AdaBoost級(jí)聯(lián)分類器，可以舍棄那些大量的且對(duì)檢測(cè)不起作用的特征，而保留少量的對(duì)目標(biāo)檢測(cè)起關(guān)鍵作用的特征，因此檢測(cè)效率很高[3]。

2 有序匹配算法

現(xiàn)有特征匹配的圖像檢測(cè)方法中，一般都是特征間的一對(duì)一匹配，一組匹配特征間是獨(dú)立匹配的，不考慮所選取的目標(biāo)圖像描述特征間的邏輯關(guān)系與結(jié)構(gòu)等，這就使得匹配結(jié)果通常表現(xiàn)出局部性，難以從全局上實(shí)現(xiàn)目標(biāo)圖像的準(zhǔn)確檢測(cè)[4]。因此，本文提出一種基于圖同構(gòu)理論的特征匹配方法，綜合編輯距離、層次關(guān)系等特征，計(jì)算目標(biāo)特征的結(jié)構(gòu)級(jí)相似性，對(duì)目標(biāo)圖像特征的表示有向圖中以點(diǎn)、邊有序交替匹配的方式來(lái)判斷目標(biāo)的有向圖近似同構(gòu)，從而實(shí)現(xiàn)基于子圖同構(gòu)判定的目標(biāo)圖像檢測(cè)。

以上特征匹配思想的基礎(chǔ)是圖匹配問(wèn)題，其本質(zhì)上是一個(gè)NP完全問(wèn)題，這類問(wèn)題的常用解決方案是通過(guò)計(jì)算和匹配結(jié)構(gòu)的相似性實(shí)現(xiàn)，其指導(dǎo)思想是：基于相鄰元素相似性倒推元素自身相似度，即，若節(jié)點(diǎn)的鄰居節(jié)點(diǎn)相似，則節(jié)點(diǎn)本身也相似，其核心是相似度傳播算法。最典型的兩個(gè)基于結(jié)構(gòu)的本體匹配算法SF和GMO，其核心思想都是：擁有相似父/子概念的概念可能相似，擁有相似屬性的概念可能相似。

基于子圖近似同構(gòu)的特征匹配方法(Charactore Matching based Subgraph Isomorphism, SICM)框架如圖1所示。由圖1可知，SICM是一個(gè)順序匹配器，主要包括4個(gè)主要功能模型：錨點(diǎn)與子圖提取、結(jié)構(gòu)相似度量、子圖近似同構(gòu)判定、基于子圖同構(gòu)的目標(biāo)匹配。

所謂錨點(diǎn)，是指待目標(biāo)中第一對(duì)確定為相似的屬性特征，表現(xiàn)在有向標(biāo)記圖中就是第一對(duì)確定匹配的節(jié)點(diǎn)，其形式化定義如下：

2.1 定義1

對(duì)于待匹配目標(biāo)的特征雙重編碼A和B，計(jì)算其對(duì)應(yīng)的有向圖G(A)和G(B)的相似度需要完成如下計(jì)算：① 特征編輯距離相似度；② 特征層次關(guān)系相似度；③ 特征其他關(guān)系相似度；④ 結(jié)構(gòu)相似度。具體解釋如下：

圖1 特征雙重編碼有序匹配算法框架

(1)

則x與y間編輯距離相似度計(jì)算如式(2)：

(2)

其中，α、β為權(quán)重調(diào)整參數(shù)，且0<α，β≤1∧α+β=1。

2) 特征層次關(guān)系相似度：設(shè)x在G(A)中入度集為xin={xi∈V(A)|?xiHcx}，出度集為xout={xj∈V(A)|?xHcxj}，類似y在G(B)中入(出)度集分別為yin、yout，則x與y層次關(guān)系相似性計(jì)算如式(3)：

(3)

xin?yin={x|x∈xin,y∈yin:Se(x,y)∈OM(x,y)}表示x、y父節(jié)點(diǎn)中可匹配的節(jié)點(diǎn)集；

xout?yout={x|x∈xout,y∈yout:Se(x,y)∈OM(x,y)}表示x、y子節(jié)點(diǎn)中可匹配的節(jié)點(diǎn)集。

3) 節(jié)點(diǎn)間其他關(guān)系相似性：記與x、y存有R關(guān)系的節(jié)點(diǎn)集合分別為xR={x′∈V(A)|r∈RA:?(x′rx)∨(xrx′)}和yR={y′∈V(B)|r∈RB:?(y′ry)∨(yry′)}，若?r1∈RA,r2∈RB，有式(4)成立：

(4)

則記節(jié)點(diǎn)集為xR?yR，以加權(quán)后得到節(jié)點(diǎn)間其他關(guān)系相似度計(jì)算如式(5)：

(5)

4) 結(jié)構(gòu)相似性：設(shè)為A、B的一對(duì)錨點(diǎn)，x、y的導(dǎo)出子圖G(x)、G(y)與G(A)、G(B)間結(jié)構(gòu)相似度計(jì)算如式(6)：

S(G(x),G(y))=η·Se(x,y)+φ·SHc(x,y)+ξ·SR(x,y)

(6)

η+φ+ξ=1為權(quán)重參數(shù)。

若兩個(gè)有向圖G、G′點(diǎn)、邊間保持一一對(duì)應(yīng)關(guān)系，且對(duì)應(yīng)點(diǎn)(邊)間保持相同關(guān)聯(lián)關(guān)系，則G和G′同構(gòu)，記為G?G′。

由于圖像檢測(cè)中只需關(guān)鍵特征的相似度滿足閾值要求即可判定為匹配，因此本文提出了圖的近似同構(gòu)概念。

2.2 定義2

設(shè)給定目標(biāo)A和B，其有向圖分別為G(A)和G(B)，若根節(jié)點(diǎn)a∈G(A)，在G(B)中存在一點(diǎn)b，有為A、B的一對(duì)錨點(diǎn)；對(duì)于G(A)和b的導(dǎo)出子圖G(Bb)，有V(A)?V(Bb),E(A)?E(Bb)，?x∈V(A):?y∈V(Bb):OM(x,y)，?e∈E(A):?e′∈E(Bb):OM(e,e′)，滿足S(G(A),G(Bb))≥θ，θ為匹配閾值，則稱A與B是圖近似同構(gòu)的，記為G(A)≈G(B)。

基于圖近似同構(gòu)，SICM算法思想是：按廣度優(yōu)先遍歷法，在確定匹配錨點(diǎn)后，基于節(jié)點(diǎn)出入度進(jìn)行節(jié)點(diǎn)與邊的有序交替匹配，直至在G(B)中找到一個(gè)與G(A)近似同構(gòu)的子圖。算法的主要步驟是：①在G(B)中找到根節(jié)點(diǎn)a∈G(A)的錨點(diǎn)b；②生成錨點(diǎn)導(dǎo)出有向圖G(Bb)；③判定G(A)與G(Bb)是否滿足圖近似同構(gòu)。若滿足則認(rèn)為其是可匹配的，否則，迭代上述過(guò)程直至收斂。

3 圖像邊緣特征檢測(cè)

所謂邊緣特征檢測(cè)，就是計(jì)算圖像中像素亮度變化差別很大的點(diǎn)的導(dǎo)數(shù)，應(yīng)用求導(dǎo)方法檢測(cè)數(shù)字圖像的灰度值不連續(xù)的現(xiàn)象[5]。如圖2所示。

圖2 圖像邊緣及相應(yīng)導(dǎo)數(shù)

3.1 梯度算子

梯度和一階導(dǎo)數(shù)相對(duì)應(yīng)，相應(yīng)梯度算子就對(duì)應(yīng)相應(yīng)的一階導(dǎo)數(shù)算子，等式是一個(gè)連續(xù)函數(shù)f(x,y)在(x,y)處的梯度計(jì)算：

(7)

梯度是一個(gè)矢量，存在幅值和相位，相位和幅值分別如下：

(8)

(9)

3.2 Laplacian算子

Laplacian算子是一種應(yīng)用于二階導(dǎo)數(shù)的算子，一個(gè)連續(xù)函數(shù)f(x,y)在(x,y)處定義如下：

(10)

Laplacian算子在圖像處理中也需要利用模板實(shí)現(xiàn)，且模板有兩個(gè)特別之處；第一是在模板的中心處該系數(shù)必須為正數(shù)；第二是模板內(nèi)的所有系數(shù)之和為零。

(11)

(12)

拉普拉斯算子檢測(cè)圖像的邊緣，經(jīng)常會(huì)產(chǎn)生有雙像素的邊界，此外對(duì)噪聲也比較敏感，所以一般不會(huì)使用這種方法對(duì)圖像邊緣檢測(cè)。

4 有序匹配算法的圖像邊緣特征檢測(cè)

4.1 Prewitt算子

Prewitt算子是一種對(duì)像素點(diǎn)在該領(lǐng)域內(nèi)各個(gè)方向上的像素差，并且在圖像的像素邊緣出現(xiàn)的極大值或極小值判斷邊緣，從而確定邊緣，消除不確定的邊緣，平滑噪聲的效果明顯。檢測(cè)的具體方向模塊各自檢測(cè)相應(yīng)的對(duì)象，一個(gè)檢測(cè)水平方向邊緣，另外一個(gè)則是檢測(cè)垂直方向的邊緣，方向模塊如表1所示。

表1 Prewitt算子方向模塊

一個(gè)連續(xù)的函數(shù)f(x,y)，應(yīng)用Prewitt算子算法，得到以下數(shù)學(xué)公式：

Gx=|[f(x-1,y-1)+f(x-1,y)+f(x-1,y+1)]-

[f(x+1,y-1)+f(x+1,y)+f(x+1,y+1)]|

Gy=|[f(x-1,y+1)+f(x,y+1)+f(x+1,y+1)]-

[f(x-1,y-1)+f(x,y-1)+f(x+1,y-1)]|

(13)

則p(x,y)=Gx+Gy

(14)

若P(x,y)大于或等于閾值T，則(x,y)表示邊緣處的像素點(diǎn)，P(x,y)則表示為邊緣圖像，但是，應(yīng)用這種方法檢測(cè)圖像邊緣，會(huì)存在一個(gè)問(wèn)題，錯(cuò)誤判斷圖像的邊緣，因?yàn)橛行┰肼朁c(diǎn)的灰度值很高，或者本來(lái)應(yīng)該有的邊緣點(diǎn)因?yàn)槠浠叶戎当容^低，在檢測(cè)邊緣時(shí)沒(méi)能正確檢測(cè)出來(lái)，導(dǎo)致出現(xiàn)多余的邊緣或者丟失了圖像的某些邊緣。

對(duì)于灰度值較低的圖像邊緣，使其灰度值增加，可以對(duì)圖像進(jìn)行銳化，然后再Prewitt算子邊緣檢測(cè)，圖像銳化的效果就是使圖像灰度的反差增強(qiáng)，把模糊的圖像變得更加清楚，增加其對(duì)比性，這里選擇拉普拉斯算子的方法具有很好的銳化效果，能夠增強(qiáng)圖像灰度突變區(qū)。這種方法既能保留原圖像的灰度值，還能突出圖像的細(xì)節(jié)信息。拉普拉斯銳化方程如式(15)：

(15)

應(yīng)用Prewitt算子圖像邊緣檢測(cè)源程序如下：

I = imread(檢測(cè)圖像)；

J1= edge(I，′prewitt′，0.04)；0.04%為梯度閾值

Figure，imshow(I)；

Figure，imshow(J1)；

4.2 Log算子

Log算子是一種結(jié)合高斯濾波和拉普拉斯算子兩種算子的方法對(duì)圖像進(jìn)行邊緣檢測(cè)，Log算子邊緣檢測(cè)方程式如下：

?2g(x,y)=?2[h(x,y)×f(x,y)]=

?2h(x,y)×f(x,y)

(16)

σ等于2的Log算子檢測(cè)圖像的邊緣，檢測(cè)結(jié)果如圖3，其源程序如下：

I = imread(檢測(cè)圖像);

BW1 = edge(I，′log′，0.003)； % σ=2

imshow(BW1)；title(′σ=2′)

圖3 Log算子圖像邊緣檢測(cè)

4.3 Canny算子

Canny算子是使用雙閾值法檢測(cè)邊緣，這兩個(gè)閾值有不同的用法，其優(yōu)勢(shì)在于不易受噪聲影響，能檢測(cè)出圖像真正的弱邊緣，提升邊緣敏感度，檢測(cè)性能較好。邊緣檢測(cè)源程序如下：

I = imread(檢測(cè)圖像)；

imshow(I)；

BW1 = edge(I，′canny′，0.2)；

Figure，imshow(BW1)；

Canny算子檢測(cè)效果如圖4。

圖4 Canny算子檢結(jié)果圖

5 有序匹配算法的多目標(biāo)跟蹤

5.1 道路背景提取

在系統(tǒng)調(diào)試測(cè)試過(guò)程中，道路背景提取是其基礎(chǔ)，以下說(shuō)明這個(gè)測(cè)試過(guò)程中遇到的幾個(gè)典型問(wèn)題及其解決辦法：① 車(chē)輛在沒(méi)有停車(chē)標(biāo)志的路段進(jìn)行倒庫(kù)處理。用串口給上位機(jī)發(fā)送此處的圖像，將圖像和識(shí)別停車(chē)標(biāo)志P的程序進(jìn)行比對(duì)，發(fā)現(xiàn)該處算法存在漏洞，經(jīng)多次改進(jìn)后讓車(chē)輛實(shí)現(xiàn)只在有停車(chē)標(biāo)志的路段進(jìn)行停車(chē)處理。② 程序沒(méi)有改動(dòng)但車(chē)輛行駛行為識(shí)別效果完全不一樣。經(jīng)調(diào)研分析后發(fā)現(xiàn)，電池供電不足會(huì)導(dǎo)致這種現(xiàn)象。③ 無(wú)端客戶端出現(xiàn)系統(tǒng)安裝包突然無(wú)法下載現(xiàn)象。查閱K60的相關(guān)資料后可知，是由于插拔下載器不當(dāng)導(dǎo)致K60進(jìn)行自鎖保護(hù)，對(duì)其進(jìn)行解鎖即可繼續(xù)使用。

5.2 常規(guī)道路檢測(cè)

圖5是車(chē)輛行駛在雙車(chē)道的左車(chē)道時(shí)的情況，其中有幾行的中心線略偏右，從圖5中可以看出中心線略偏右的那幾行沒(méi)有右邊界，這種情況下程序中先預(yù)估右邊界值，然后中心值取左右邊界值之和的一半，由圖5可看出調(diào)試結(jié)果和程序設(shè)定的一致，擬合出的中心線近似一條直線且在圖像的中間。

圖5 雙車(chē)道路段

圖6是車(chē)輛行駛在單車(chē)道時(shí)的情況。圖6和圖7雖然都是車(chē)輛在直道處的情況，但在程序上是分別處理的。因?yàn)閱诬?chē)道的情況是所有路況中最容易判別的，雙車(chē)道的情況容易和過(guò)彎混淆。由圖7可以看出單車(chē)道路段處程序擬合出的中心線在圖像的中間位置且近似直線，所以本文針對(duì)此類路段設(shè)計(jì)的算法是正確的。

圖6 單車(chē)道路段

圖7是車(chē)輛行駛到有行駛方向指示路口時(shí)的情況，在這種情況下，中心線的擬合要稍作調(diào)整，否則容易出現(xiàn)箭頭所在行的中心值偏右的情況，這是因?yàn)榧^處也有黑白跳變的明顯特征，從而導(dǎo)致查找道路左邊界時(shí)發(fā)生誤判。由圖7可知，中心線擬合正確，沒(méi)有出現(xiàn)各行中心值差別很大的情況。

圖7 有行駛方向指示的路口

圖8和圖9是車(chē)輛進(jìn)彎道前和進(jìn)彎道后的情況(以左拐為例)。車(chē)輛進(jìn)入彎道前，可以采集到道路兩邊邊界值，通過(guò)計(jì)算左右邊界值的平均值即可得到中心線。車(chē)輛進(jìn)入彎道后，左側(cè)邊界值無(wú)法找到，這種情況下每行的中心值是按如下方法計(jì)算得到。現(xiàn)設(shè)A為任一行的中心值，B為該行右邊界的邊界值，C為該行的上一行的中心值，D為上一行的右邊界值，則A=C+(D-B)，由圖10所示，擬合出的中心線和右邊界變化趨勢(shì)一致，所以擬合出的中心線正確。

圖8 進(jìn)入彎道前的中心擬合線

圖9 進(jìn)入彎道后的中心擬合線

5.3 有交通燈路口處的車(chē)輛識(shí)別

圖10是車(chē)輛在十字路口判別到有交通燈情況下的識(shí)別圖，由圖10右邊的標(biāo)志位turn_left=1可以看出，程序在處理這幅圖像時(shí)識(shí)別到了左轉(zhuǎn)的箭頭，所以本文設(shè)計(jì)的交通燈識(shí)別算法可行。

圖10 交通燈路段

5.4 特殊交通標(biāo)志檢測(cè)識(shí)別

圖11為車(chē)輛到達(dá)可停車(chē)路段時(shí)的情況，由圖11右邊的標(biāo)志位Find_p=1(最后一行)可以看出，圖像經(jīng)過(guò)識(shí)別處理后找到了停車(chē)標(biāo)志P，所以本文設(shè)計(jì)的停車(chē)標(biāo)志識(shí)別算法可行。

圖11 可停車(chē)路段

圖12是車(chē)輛遇到障礙時(shí)的情況。由圖12可看出中心線較平滑，沒(méi)有分成明顯的兩段式，這說(shuō)明小車(chē)在此處識(shí)別到障礙，中心線得到了平滑處理，所以可以得出障礙識(shí)別算法正確。平滑的中心線會(huì)讓小車(chē)在進(jìn)障礙和出障礙時(shí)行駛得較流暢，不會(huì)產(chǎn)生遲鈍現(xiàn)象。

圖12 障礙路段

由于設(shè)置的道路情況較多，識(shí)別的工作量大，導(dǎo)致難度也很大，調(diào)試的過(guò)程經(jīng)常出現(xiàn)誤判，程序進(jìn)行了多次的BUG修改，經(jīng)過(guò)多次調(diào)試最終得到了以上這些效果圖。

6 結(jié)束語(yǔ)

基于特征匹配的方法提取目標(biāo)幾何特征，將特征輸入預(yù)測(cè)模型，通過(guò)預(yù)測(cè)模型求解出下一幀中目標(biāo)可能出現(xiàn)的位置或運(yùn)動(dòng)狀態(tài)，構(gòu)造不同的特征相似性度量函數(shù)，使相鄰幀間的目標(biāo)可以匹配，實(shí)現(xiàn)多目標(biāo)跟蹤[6]。Prewitt算子、Log算子、Canny算子是實(shí)現(xiàn)多目標(biāo)跟蹤的典型算法，多層級(jí)聯(lián)檢測(cè)有助于提高復(fù)雜環(huán)境下多目標(biāo)檢測(cè)的準(zhǔn)確度，通過(guò)對(duì)直方圖距離函數(shù)最小化來(lái)追蹤目標(biāo)，發(fā)揮計(jì)算量小、適應(yīng)性強(qiáng)的優(yōu)點(diǎn)。未來(lái)，可進(jìn)一步獲得距離、方位、速度等參數(shù)，更好地檢測(cè)圖像邊緣特征，實(shí)現(xiàn)多目標(biāo)跟蹤。