周 強(qiáng)，周 虎，徐利軍，劉 濤，游 政，羅賓鴻

(1.東華大學(xué)機(jī)械工程學(xué)院，上海 201620；2.上海航天動力技術(shù)研究所，上海 201108)

0 引言

圖像定位算法一般分為基于灰度信息和基于特征信息的算法?；诨叶刃畔⒌乃惴ㄟ\(yùn)算量小但不穩(wěn)定[1]；基于特征信息的算法則魯棒性更強(qiáng)，效果更好，定位結(jié)果主要由特征提取和特征匹配兩部分決定[2]。

特征匹配算法中SIFT算法具有較強(qiáng)的魯棒性，能夠保持很好的匹配穩(wěn)定性。但是該算法生成的特征點(diǎn)數(shù)量多，消耗的匹配時間較長，且誤匹配較多[3]。針對上述問題，Bay等人[4]提出改進(jìn)后的SURF算法，該算法利用積分圖像進(jìn)行計(jì)算，由Hessian檢測子來獲取特征點(diǎn)。通過計(jì)算每個特征點(diǎn)的Harr小波變換確定特征點(diǎn)的主方向，進(jìn)而確定特征點(diǎn)描述符，再根據(jù)特征描述向量之間的歐氏距離完成匹配[5]。SURF在理念上與SIFT類似，注重圖像在不同尺度空間上的梯度信息，并在特征檢測和描述向量的生成中充分利用積分圖像和方框?yàn)V波器，減少了描述向量的維數(shù)，提高了特征匹配的速度[6]。但是當(dāng)圖像存在較大視角和噪聲變化時，SURF算法提取的特征點(diǎn)比較不穩(wěn)定[7]。因此，國內(nèi)外一些學(xué)者基于SURF算法提出了一些改進(jìn)：廉藺[8]等人針對SURF算法中Harr描述符未能充分利用特征點(diǎn)的周圍信息，提出加窗灰度直方圖算法，實(shí)現(xiàn)特征點(diǎn)外圍區(qū)域灰度差信息的利用；羅楠[9]等人通過在SURF描述符上增加領(lǐng)域采樣點(diǎn)經(jīng)過局部歸一化后的灰度統(tǒng)計(jì)信息和二階梯度值細(xì)節(jié)信息，得到擴(kuò)展SURF描述符，同樣實(shí)現(xiàn)特征點(diǎn)外圍區(qū)域灰度差信息的利用；翟優(yōu)[10]等人分析了在不同局部領(lǐng)域劃分情況下SURF的性能，他們將SURF描述符的局部領(lǐng)域由原來的柵格狀更改為三角形和扇形進(jìn)行研究，發(fā)現(xiàn)分別采用柵格、三角形和扇形對SURF描述符的局部領(lǐng)域進(jìn)行劃分時，SURF算法的性能依次改善。

為了增加圖像定位識別的效率，本文提出在使用SURF算法之前先通過雙樹復(fù)小波變換對圖像進(jìn)行分解，將圖像分為高頻和低頻兩部分，只將其中的低頻部分作為SURF算法的輸入圖像得到特征描述子，再由SLSH算法實(shí)現(xiàn)特征降維得到最終的特征描述子；然后通過歐氏距離和最近鄰次近鄰比值法剔除部分錯誤匹配點(diǎn)對，完成粗匹配，再利用RANSAC算法構(gòu)造仿射變換模型進(jìn)一步剔除錯誤匹配點(diǎn)對，實(shí)現(xiàn)精確匹配，從而實(shí)現(xiàn)圖像的精確定位。利用汽車線束上的接插件進(jìn)行定位實(shí)驗(yàn)，給出實(shí)驗(yàn)結(jié)果，并與SURF算法、SIFT算法進(jìn)行比較分析。

1 結(jié)合雙樹復(fù)小波變換和SURF算法生成特征描述子

1.1 雙樹復(fù)小波變換分解圖像

為了提高SURF算法的運(yùn)算速度和匹配精度，分別將目標(biāo)圖像與基準(zhǔn)圖像通過雙樹復(fù)小波變換分解成低頻和高頻兩部分。其中，低頻部分保留了原始圖像的大部分信息，高頻部分則攜帶有許多噪聲。因此選擇圖像分解后的低頻部分作為SURF的輸入圖像不僅能夠減少運(yùn)算量，還能提高圖像配準(zhǔn)精度[11]。雙樹復(fù)小波φ(t)用公式表示為

φ(t)=φh(t)+jφg(t)

(1)

式中φh、φg(t)為實(shí)數(shù)小波。

如圖1所示，雙樹復(fù)小波包含樹A和樹B兩個平行分解樹，分別由兩對不同的共軛正交濾波器構(gòu)成，即h0(n)、h1(n)和g0(n)、g1(n)。輸入信號A(j,1)經(jīng)過雙樹復(fù)小波變換后將得到低頻部分和高頻部分，其中低頻部分由A(j+1,1)和A(j+1,2)組成，依次代表了實(shí)部和虛部；高頻部分則由6個高頻子帶D(j+1,n)，n=1,2,…,6組成。

圖1 雙樹復(fù)小波變換的分解結(jié)構(gòu)圖

1.2 特征點(diǎn)檢測

特征點(diǎn)是圖像精確配準(zhǔn)的關(guān)鍵[11]，SURF算法利用積分圖像和方框?yàn)V波器來加快運(yùn)算速度[6]，并采用快速Hessian矩陣算法對特征點(diǎn)進(jìn)行檢測。積分圖像的設(shè)定為[12]：設(shè)I=(x,y)表示圖像I(x)的某一個像素，則點(diǎn)(x,y)的積分值可表示灰度區(qū)域，如圖2所示。對I(x)進(jìn)行積分，得到I(x)左上角到任意點(diǎn)(x,y)的灰度值總和，即

(2)

圖2 積分圖像

選取圖像I(x)中的任意一點(diǎn)X=(x,y)，該點(diǎn)在σ尺度上的Hessian矩陣定義為

(3)

(4)

實(shí)際應(yīng)用是通過箱式濾波器代替二階高斯濾波來提高速度?；驹韀3]為：使用箱式濾波器模板與輸入圖像的卷積Dxx、Dxy和Dyy來代替式(3)中的Lxx(X,σ)、Lxy(X,σ)、Lyy(X,σ)，用9×9的箱式濾波器代替尺度σ=1.2的二階高斯導(dǎo)數(shù)，Dxx、Dxy和Lxx、Lxy的關(guān)系為

(5)

式中：‖·‖F(xiàn)為Frobenius范數(shù)；ω為權(quán)重系數(shù)，取其近似值0.9。

則Hessian矩陣的行列式可近似表示為

det=DxxDyy-(0.9Dxy)2

(6)

點(diǎn)(x,y)經(jīng)過式(6)的計(jì)算可得出該點(diǎn)的角點(diǎn)響應(yīng)值。同理，對圖像上所有的點(diǎn)進(jìn)行計(jì)算將得到同一尺度下的角點(diǎn)響應(yīng)圖像。采用不同尺寸的模板進(jìn)行計(jì)算，便可構(gòu)造出圖像金字塔。將所有角點(diǎn)響應(yīng)值小于預(yù)設(shè)值的像素點(diǎn)舍棄之后，再將剩余的每個像素點(diǎn)與其同尺度點(diǎn)及其上下相鄰尺度共26個像素點(diǎn)進(jìn)行比較，通過非極大值抑制(non-maximum suppression，NMS)和插值運(yùn)算得到特征點(diǎn)[13]。

1.3 特征描述子生成

首先確定特征點(diǎn)的主方向：以特征點(diǎn)為中心，在半徑為6σ(σ為特征點(diǎn)所在尺度空間的尺度值)的圓形領(lǐng)域內(nèi)，計(jì)算各點(diǎn)在x和y方向的Harr小波響應(yīng)，并用特征點(diǎn)為中心的高斯函數(shù)對響應(yīng)值進(jìn)行加權(quán)計(jì)算；按每次5°的步長轉(zhuǎn)動張角為60°的扇形窗口，累加不同窗口內(nèi)的Harr小波響應(yīng)值，將其作為局部方向矢量，其中矢量最長的方向?yàn)橹鞣较颉?/p>

然后構(gòu)建描述子：將平面坐標(biāo)系的y軸旋轉(zhuǎn)到主方向上，以20σ為邊長選取一正方形區(qū)域，并以特征點(diǎn)作為該正方形區(qū)域的中心。再將正方形區(qū)域根據(jù)特征點(diǎn)的主方向進(jìn)行均等劃分，分成4×4個大小相同的小正方形，再分別將這16個小正方形區(qū)域分成5×5個大小相同的子區(qū)域。計(jì)算每個子區(qū)域內(nèi)所有像素點(diǎn)沿x和y方向的Harr小波響應(yīng)值并高斯加權(quán)，得到∑dx和∑dy。為了表征圖像灰度值變化的極性信息[1]，同時計(jì)算∑|dx|和∑|dy|，由此生成4維描述向量：v=(∑dx,∑dy,∑|dx|,∑|dy|)。將所有子區(qū)域的描述向量串聯(lián)便得到64維的特征向量，但由于特征維數(shù)太高增加了計(jì)算量，很難快速實(shí)現(xiàn)基于特征的圖像相似度分析，需要通過降維的方法來簡化特征和提高處理速度，采用類局部敏感哈希降維法(SLSH)實(shí)現(xiàn)這一目的[14]。

先隨機(jī)生成L個投影矩陣W1，…，Wi，…，WL，每個投影矩陣都是D×K維，其中D是特征向量維度；K是單個矩陣投影之后的數(shù)據(jù)維數(shù)；再將高維特征X分別在L個投影矩陣上投影，并將投影之后的數(shù)據(jù)特征進(jìn)行前后連接，形成低維數(shù)據(jù)特征H，從而得到最終的特征描述子[11]，如式(7)所示

H(X)=[XW1,…,XWi,…,XWL]

(7)

式中投影矩陣Wi通過式(8)生成

(8)

式中：RDK(-1,1)是一個[-1,1]區(qū)間的D×K維的隨機(jī)矩陣；c為固定參數(shù)。

2 結(jié)合RANSAC算法進(jìn)行圖像定位

利用提取的特征向量和特征點(diǎn)即可實(shí)現(xiàn)圖像配準(zhǔn)定位，但由于一些錯誤匹配特征點(diǎn)的存在，會降低匹配精度，原始SURF算法利用歐氏距離和最近鄰次近鄰比值法能夠有效剔除部分錯誤匹配點(diǎn)對，但不能保證完全剔除，因此結(jié)合RANSAC算法能夠進(jìn)一步將錯誤匹配點(diǎn)對剔除，提高匹配精度[11]。

2.1 RANSAC

RANSAC 算法的主要思想[1]是：構(gòu)造一個仿射數(shù)學(xué)模型，通過不斷隨機(jī)抽取樣本中的點(diǎn)對，以求取該數(shù)學(xué)模型的仿射系數(shù)，根據(jù)仿射系數(shù)把經(jīng)過粗配準(zhǔn)后留下的點(diǎn)對分為內(nèi)點(diǎn)和外點(diǎn)。其中，內(nèi)點(diǎn)是滿足仿射變換關(guān)系的配準(zhǔn)點(diǎn)對，外點(diǎn)則是不滿足該變換關(guān)系的配準(zhǔn)點(diǎn)對。然后選擇擁有最多內(nèi)點(diǎn)的點(diǎn)集，通過最小二乘法利用這些內(nèi)點(diǎn)重新計(jì)算仿射數(shù)學(xué)模型的系數(shù)，實(shí)現(xiàn)圖像的精確配準(zhǔn)。具體方法如下：

先假設(shè)兩副圖像滿足仿射變換關(guān)系[11]

(9)

式中M為變換矩陣，

式中：a1、a2、a3、a4、a5、a6為仿射系數(shù)；(x,y)和(x′,y′)分別為基準(zhǔn)圖像和目標(biāo)圖像的特征點(diǎn)坐標(biāo)。

然后進(jìn)行以下操作：

操作1：隨機(jī)從所有匹配點(diǎn)對中取出3組，通過計(jì)算得出變換矩陣M中6個仿射系數(shù)的值；

操作2：將計(jì)算出的6個仿射系數(shù)帶入變換矩陣，并利用生成的變換矩陣對目標(biāo)圖像中的所有特征點(diǎn)進(jìn)行變換；

操作3：計(jì)算出經(jīng)過變換后的特征點(diǎn)與參考圖像中的對應(yīng)特征點(diǎn)之間的距離d，并將該距離與設(shè)定的距離閾值進(jìn)行比較，若距離大于閾值則設(shè)為外點(diǎn)，反之則為內(nèi)點(diǎn)；

操作4：多次隨機(jī)選出不同的3組匹配點(diǎn)對，并重復(fù)操作1至操作3的步驟，然后從得到的所有內(nèi)點(diǎn)集當(dāng)中，選出點(diǎn)數(shù)最多的點(diǎn)集作為目標(biāo)點(diǎn)集；

操作5：將目標(biāo)點(diǎn)集內(nèi)的點(diǎn)，通過最小二乘法重新計(jì)算仿射模型變換矩陣M的系數(shù)。

操作6：根據(jù)仿射變換模型實(shí)現(xiàn)圖像的精確配準(zhǔn)和定位。

2.2 基于改進(jìn)SURF的精確定位算法流程

綜上所述，基于改進(jìn)SURF的精確定位算法流程可表述為如圖3所示。

圖3 基于改進(jìn)SURF的圖像精確定位算法流程圖

3 實(shí)驗(yàn)及分析

利用汽車線束上接插件對本文提出的基于改進(jìn)SURF算法的圖像精確定位方法進(jìn)行有效性驗(yàn)證，并通過實(shí)驗(yàn)將本文提出的方法與SIFT算法、SURF算法進(jìn)行比較。實(shí)驗(yàn)的硬件環(huán)境是64位Windows 7系統(tǒng)，CPU為Intel core i3，2.40 GHz，內(nèi)存為4 GB；軟件開發(fā)平臺是OpenCV 3.0和VS2013。

采用本文方法的實(shí)驗(yàn)過程如下：

首先利用雙樹復(fù)小波變換對輸入的圖像進(jìn)行分解，需要分解的圖像包括基準(zhǔn)圖像和目標(biāo)圖像，接著分別將分解后的圖像低頻部分輸入SURF算法中生成各自的特征向量，再由SLSH算法實(shí)現(xiàn)降維；然后部分錯誤匹配的點(diǎn)對將先通過歐式距離和最近鄰次近鄰比值法進(jìn)行刪減，完成粗匹配；再將剩余的大部分錯誤匹配點(diǎn)對通過RANSAC算法進(jìn)一步剔除，完成精確匹配，進(jìn)而實(shí)現(xiàn)圖像的精確定位。

圖4是汽車線束的全景圖，將其作為基準(zhǔn)圖像。圖5是汽車線束上4個不同的接插件，將其作為目標(biāo)圖像。這4個接插件在基準(zhǔn)圖像上的對應(yīng)位置由虛線圓指示，并分別標(biāo)有a，b，c，d，如圖4所示，實(shí)驗(yàn)需要達(dá)到的效果是依次輸入接插件的4張目標(biāo)圖像之后，能通過本文方法在基準(zhǔn)圖像上找到該目標(biāo)在基準(zhǔn)圖像上的對應(yīng)位置。

圖6是采用本文方法進(jìn)行實(shí)驗(yàn)的結(jié)果圖，表1為相應(yīng)的實(shí)驗(yàn)數(shù)據(jù)。

圖4 汽車線束全景圖

(a)

(b)

(c)

(d)

(a)

(b)

(c)

(d)圖6 實(shí)驗(yàn)的結(jié)果

從表1中可以發(fā)現(xiàn)，采用本文提出的方法對不同目標(biāo)圖像進(jìn)行定位，其定位正確率一般都能維持在80%以上，而且所消耗的時間都在1 s之內(nèi)，可見本文方法具有一定的時效性。

表1 采用本文方法的定位結(jié)果

為進(jìn)一步驗(yàn)證算法的性能，將本文方法與SURF和SIFT進(jìn)行了比較，比較結(jié)果如表2所示。

表2 本文方法與SURF、SIFT算法性能比較

從表2可以發(fā)現(xiàn)，SIFT算法得到的平均匹配對數(shù)最多，為91.2對，比SURF算法得到的匹配點(diǎn)數(shù)多了將近一半，也比本文方法多了將近三分之一。但SIFT算法消耗的時間也遠(yuǎn)多于其他兩種方法，是SURF算法的3倍左右。本文方法則是3種方法中耗時最少的，而且定位的正確率也是最高的，平均定位正確率可以達(dá)到82.7%，比SIFT算法和SURF算法都要高出20%以上，可見本文方法與SIFT算法和SURF算法相比具有較大的性能提升。

4 結(jié)論

本文提出了一種基于改進(jìn)SURF算法的圖像精確定位方法。首先將目標(biāo)圖像與基準(zhǔn)圖像利用雙樹復(fù)小波變換分解為高頻和低頻兩部分，再將其中的低頻部分作為SURF算法的輸入，得到特征向量后由SLSH算法進(jìn)行降維；特征匹配時，先進(jìn)行粗匹配剔除部分錯誤匹配點(diǎn)對，再通過RANSAC算法剔除其余錯誤匹配點(diǎn)對得到擁有最多內(nèi)點(diǎn)的點(diǎn)集，并利用這些點(diǎn)集內(nèi)的點(diǎn)求出仿射變換模型的系數(shù)，實(shí)現(xiàn)圖像的精確定位。利用汽車線束上的接插件進(jìn)行算法有效性驗(yàn)證實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文算法相比SIFT算法和SURF算法擁有更高的定位精度和更快的運(yùn)算速度。