基于SURF算法和SLSH算法的圖像定位方法

周 強，周 虎，徐利軍，劉 濤，游 政，羅賓鴻

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

0 引言

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

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

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

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

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

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

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

(1)

式中φh、φg(t)為實數(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)組成，依次代表了實部和虛部；高頻部分則由6個高頻子帶D(j+1,n)，n=1,2,…,6組成。

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

1.2 特征點檢測

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

(2)

圖2 積分圖像

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

(3)

(4)

實際應(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)

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

1.3 特征描述子生成

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

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

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

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

(7)

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

(8)

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

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

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

2.1 RANSAC

RANSAC 算法的主要思想[1]是：構(gòu)造一個仿射數(shù)學(xué)模型，通過不斷隨機抽取樣本中的點對，以求取該數(shù)學(xué)模型的仿射系數(shù)，根據(jù)仿射系數(shù)把經(jīng)過粗配準(zhǔn)后留下的點對分為內(nèi)點和外點。其中，內(nèi)點是滿足仿射變換關(guān)系的配準(zhǔn)點對，外點則是不滿足該變換關(guān)系的配準(zhǔn)點對。然后選擇擁有最多內(nèi)點的點集，通過最小二乘法利用這些內(nèi)點重新計算仿射數(shù)學(xué)模型的系數(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)圖像的特征點坐標(biāo)。

然后進行以下操作：

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

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

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

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

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

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

2.2 基于改進SURF的精確定位算法流程

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

圖3 基于改進SURF的圖像精確定位算法流程圖

3 實驗及分析

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

采用本文方法的實驗過程如下：

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

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

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

圖4 汽車線束全景圖

(a)

(b)

(c)

(d)

(a)

(b)

(c)

(d)圖6 實驗的結(jié)果

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

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

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

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

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

4 結(jié)論

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