一種基于SURF的全景圖像配準(zhǔn)算法*

梁艷菊，李 慶，林蓁蓁，陳大鵬

(1.中國科學(xué)院微電子所昆山感知中心，江蘇昆山215347;2.中國科學(xué)院微電子研究所集成先導(dǎo)工藝研究中心，北京100029)

0 引言

全景圖像的配準(zhǔn)和拼接已成為圖像處理、計(jì)算機(jī)視覺等領(lǐng)域的重要研究課題，其中，全景圖像的配準(zhǔn)是圖像融合、三維環(huán)境重建的技術(shù)基礎(chǔ)。全景圖像自動配準(zhǔn)［1］大體分為基于灰度［2］和基于特征兩類，其中，前者研究較少，后者特別是基于特征點(diǎn)的匹配研究較多?；谔卣鼽c(diǎn)配準(zhǔn)方法的大體流程為:先提取各個(gè)圖像的特征點(diǎn)，再完成特征點(diǎn)之間的匹配，然后通過匹配的特征建立圖像間的映射變換，最后給出配準(zhǔn)后的圖像。本文采用基于特征點(diǎn)的方法實(shí)現(xiàn)全景圖像配準(zhǔn)。

提取特征點(diǎn)的 算 法有 Harris［3］，SUSAN［4］，DOG［5］，Hessian-Laplace［6］，SIFT(scale-invariant feature transform)［7］，SURF(speeded up robust features)［8］等。其中 ，SIFT 算法是一種魯棒性好，具有尺度不變性的特征描述方法，但SIFT計(jì)算數(shù)據(jù)量大、時(shí)間復(fù)雜度太高［8］。新近提出的SURF算法較之SIFT在計(jì)算速度和魯棒性上有較大改進(jìn)，它已經(jīng)被廣泛地應(yīng)用于目標(biāo)識別和跟蹤?；谔卣鼽c(diǎn)的匹配主要采取最近鄰原則，搜索最近鄰時(shí)，若直接比較距離則時(shí)間復(fù)雜度較高，鑒于此，本文基于SURF算法，使用一種時(shí)間效率較高的最近鄰搜索算法實(shí)現(xiàn)特征點(diǎn)匹配，完成全景圖像的快速配準(zhǔn)。測試表明:該方法實(shí)時(shí)性好，魯棒性好，復(fù)雜度低，擴(kuò)展性好，可應(yīng)用于各種平臺上。

1 SURF算法

SURF是一種特征點(diǎn)提取算法，由荷蘭語魯汶大學(xué)的Bay H，Tuytelaars T，Gool L V于2006年提出，該算法的性能接近SIFT，計(jì)算速度提高了近3倍。SURF算法可分為兩部分，特征點(diǎn)檢測與特征點(diǎn)描述符表示。

1.1 SURF算法特征點(diǎn)檢測

SURF算法在積分圖像上進(jìn)行。積分圖像由Jones M［9］和Viola P定義，用符號 I∑(x)表示。積分圖像上點(diǎn)X=(x，y)處的值代表以圖像原點(diǎn) (0，0)和點(diǎn)X為頂點(diǎn)組成的長方形中的像素總和

Fast-Hessian［7，10］矩陣的定義為

式中 Lxx(x，σ)是圖像在點(diǎn)X處灰度值與二階高斯微分函數(shù)的卷積。Lxy(x，σ)，Lyy(x，σ)含義與之類似。采用框狀濾波器近似高斯微分函數(shù)，得到Fast-Hessian矩陣

其中，Happrox的行列式為

為使SURF算法具有尺度不變性，SURF算法用不同尺寸的框狀濾波器對原始圖像進(jìn)行濾波處理，組成圖像金字塔［4］，如圖1(a)所示。圖1(b)是SIFT圖像金字塔的生成方式。二者對比可以看出:SURF算法與同一尺寸圖像進(jìn)行處理，可以并行計(jì)算，提高了時(shí)間效率。

圖1 SURF算法和SIFT算法圖像金字塔比較Fig 1 Comparison of image scale-space between SURF and SIFT

初始尺度框狀濾波器與圖像卷積得到尺度空間的第一層，尺寸逐漸增大的濾波器與原始圖像卷積生成下面的圖像層，4個(gè)圖像層構(gòu)成一階(Octave)，一般取四階。

根據(jù)Fast-Hessian矩陣行列式的閾值，檢測圖像滿足閾值要求的點(diǎn)，然后在該點(diǎn)周圍的26個(gè)點(diǎn)范圍內(nèi)進(jìn)行非最大化抑制，得到特征點(diǎn)集，最后進(jìn)行三維二次插值，對特征點(diǎn)實(shí)現(xiàn)亞像素級定位。

1.2 SURF算法興趣點(diǎn)描述符的表示

興趣點(diǎn)描述符的提取分為兩步，首先，給特征點(diǎn)分配一個(gè)方向，然后生成描述符向量。

在圓心為特征點(diǎn)，半徑為6σ(σ為尺度)的圓內(nèi)，計(jì)算尺寸為4σ 的 Harr小波響應(yīng) dx，dy，對 dx，dy進(jìn)行高斯加權(quán)(2σ)。用角度為π/3的扇形繞特征點(diǎn)旋轉(zhuǎn)一周，計(jì)算扇形在每個(gè)角度時(shí)的dx+dy。當(dāng)dx+dy最大時(shí)的方向即為特征點(diǎn)的方向，如圖2所示。

選定方向，以特征點(diǎn)為核心，構(gòu)建一個(gè)大小為20σ的正方形窗，與特征點(diǎn)對齊。將這個(gè)正方形窗劃分為4×4個(gè)小正方向區(qū)域，計(jì)算每個(gè)小區(qū)域內(nèi)的 dx，dy，并用高斯函數(shù)(3σ)進(jìn)行加權(quán)。每個(gè)小區(qū)域內(nèi)的描述符表示為

圖2 特征點(diǎn)方向計(jì)算Fig 2 Computation of feature point’s direction

式中 Desc_squre為四維向量，4×4個(gè)小區(qū)域就組成了特征點(diǎn)的64維描述符向量。

2 特征點(diǎn)匹配與仿射矩陣計(jì)算

基于特征點(diǎn)匹配的目的是找到兩幅圖像中表示相同物理位置的特征點(diǎn)，形成特征點(diǎn)匹配對。采用K-D［10］(K-dimension)樹算法對兩幅圖像提取的特征點(diǎn)進(jìn)行快速最近鄰搜索，進(jìn)行最近鄰次近鄰比值判別，實(shí)現(xiàn)特征點(diǎn)的匹配，計(jì)算仿射變換矩陣。K-D最近鄰搜索算法充分利用K-D樹的特點(diǎn)，大幅度提高了搜索效率。最近鄰的判別標(biāo)準(zhǔn)是歐氏距離最短，歐氏距離表示如下

式中 desc1(i)，desc2(i)分別為兩幅圖像 Image1，Image2中利用SURF算法得到的特征點(diǎn)描述符desc1，desc2的分量。

2.1 K-D樹最近鄰搜索

64-D最近鄰搜索算法是一個(gè)遞歸的算法，在64-D樹上進(jìn)行。

用64-D的特征點(diǎn)描述符組成64-D搜索樹。SURF特征點(diǎn)的64-D樹的每一個(gè)節(jié)點(diǎn)都是64-D的數(shù)據(jù)，組成一個(gè)64-D超空間。每個(gè)節(jié)點(diǎn)都可以看作一個(gè)分裂超平面，將64-D超空間分為兩個(gè)子超空間。一個(gè)在分裂超平面的軸的左邊，另外一個(gè)在右邊。分裂超平面軸的選擇從第1—D軸到第64-D軸為一個(gè)循環(huán)，直到所有的特征點(diǎn)都被插入到64-D樹中。

算法中需要開辟必要的空間保存變量值，為提高計(jì)算效率，避免開方計(jì)算，歐氏距離直接用其平方代替。算法的執(zhí)行如下:

1)從根節(jié)點(diǎn)開始往下搜索子樹。

2)如果搜索到葉子節(jié)點(diǎn)，存儲該葉子節(jié)點(diǎn)為當(dāng)前最近鄰點(diǎn) current best。

3)在每個(gè)節(jié)點(diǎn)上，首先判斷計(jì)算當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離，如果當(dāng)前節(jié)點(diǎn)與給定的目標(biāo)點(diǎn)的距離更小，則更新current best。然后，判斷以目標(biāo)節(jié)點(diǎn)為中心，以當(dāng)前最佳距離為半徑的子超空間是否與分裂超平面相交。若相交，則搜索右子樹;否則，忽略右子樹，繼續(xù)搜索。

4)最后算法在根節(jié)點(diǎn)上完成上述步驟，結(jié)束。

2.2 最近鄰次近鄰比值判別

在匹配過程中，圖像的視角不同，景物范圍也不同，或是兩幅圖像之間存在縮放關(guān)系，這些情況都有可能導(dǎo)致圖像Image1中的特征點(diǎn)在Image2中沒有匹配點(diǎn)。當(dāng)Image1和Image2中存在鄰域灰度信息分布比較相似的點(diǎn)時(shí)，也會產(chǎn)生匹配錯(cuò)誤。

本文借鑒Lowe的做法，檢查最近鄰與次近鄰的比值，避免上述錯(cuò)誤的發(fā)生。檢測方法可表示為

其中，最近鄰距離表示為FND(first nearest distance)，次近鄰距離表示為SND(second neighbor distance)。經(jīng)過上述步驟，SURF算法在兩幅圖像檢測到的特征點(diǎn)匹配完成。

2.3 變換矩陣參數(shù)計(jì)算

假設(shè)兩幅圖像間存在仿射變換關(guān)系，則圖像Image1和Image2 中的一對匹配點(diǎn) p1(x1，y1)，p2=(x2，y2)間變換關(guān)系為

為了提高H矩陣中參數(shù)估計(jì)的精度，排除可能存在的誤匹配點(diǎn)影響，文中采用 RANSAC［11］(random sample consensus)隨機(jī)采樣一致算法來估計(jì)。

RANSAC分為3步進(jìn)行:第1步隨機(jī)選取3組匹配點(diǎn)，估計(jì)H的6個(gè)參數(shù);第2步利用估計(jì)的參數(shù)對余下的匹配點(diǎn)進(jìn)行判斷，區(qū)分出內(nèi)點(diǎn)和外點(diǎn)集，記錄內(nèi)點(diǎn)集的數(shù)量，用新內(nèi)點(diǎn)集重新估計(jì)參數(shù);第3步，當(dāng)內(nèi)點(diǎn)數(shù)目最大時(shí)，在該內(nèi)點(diǎn)集上給出H的最佳估計(jì)。

3 性能測試

測試在Microsoft Visual C++2010，Matlab 2010 R2010a環(huán)境下，在Pentium Dual-core E5500 CPU，主頻2.79GHz，內(nèi)存2 GB的主機(jī)上進(jìn)行。測試采用兩幅從不同視角拍攝的中國科學(xué)院微電子研究所圖片，大小為400×256。測試分為兩組，一組測試一般的兩幅圖像配準(zhǔn)效果;另一組測試兩幅圖像存在旋轉(zhuǎn)時(shí)，對本文的配準(zhǔn)算法、SIFT和一般SURF匹配的算法性能進(jìn)行對比。

第一組測試的程序流程圖如圖3所示，結(jié)果如圖4、圖5、圖6、表1所示。圖4是SURF算法檢測特征效果圖，圖上的圓的圓心表示特征點(diǎn)位置，半徑表示其尺度。圖5是兩幅圖像平行時(shí)的配準(zhǔn)情況，圖6是一幅圖像旋轉(zhuǎn)時(shí)的配準(zhǔn)情況。左邊圖像為Image1，右邊為Image2。從表1可以看出:在匹配精度很高的情況下，檢測時(shí)間和配準(zhǔn)時(shí)間加起來不超過 0.2 s。

圖3 程序流程圖Fig 3 Program flow chart

表1 圖像配準(zhǔn)用時(shí)比較Tab 1 Comparison of time-consumption of image registration

圖4 SURF特征點(diǎn)檢測Fig 4 SURF feature points detection

圖5 特征點(diǎn)匹配Fig 5 Feature point match

另一組測試結(jié)果如表2所示。從表中可以看出:在配準(zhǔn)正確度近似的情況下，SIFT配準(zhǔn)算法的時(shí)間效率最低。該測試證明:本文采用的配準(zhǔn)算法以極高的時(shí)間效率實(shí)現(xiàn)了高質(zhì)量的圖像配準(zhǔn)。

圖6 圖像旋轉(zhuǎn)后特征點(diǎn)匹配Fig 6 Feature point match after rotating

表2 各種算法時(shí)間效率比較Tab 2 Comparison of time efficiency of different algorithms

4 結(jié)束語

本文提出了一種基于SURF算法的快速全景圖像配準(zhǔn)方法。采用兩幅現(xiàn)實(shí)全景圖像，提取SURF特征點(diǎn)，使用KD樹搜索算法實(shí)現(xiàn)快速最近鄰的查找，并對圖像特征點(diǎn)匹配進(jìn)行有效的優(yōu)化，最后用RANSAC算法計(jì)算變換矩陣。經(jīng)實(shí)際圖像測試驗(yàn)證，該方法具有實(shí)時(shí)性好、復(fù)雜度低、魯棒性好的特點(diǎn)。本文提出的方法為全景圖像拼接、立體視覺、三維環(huán)境重建等研究領(lǐng)域提供了一種新的解決思路。

［1］Lowe D G，Brown M.Recognising panoramas［C］∥Proceedings of the Ninth IEEE International Conference on Computer Vision，Nice，F(xiàn)rance，2003.

［2］曹云峰，張 珍，丁 萌，等.一種基于廣義互信息的圖像配準(zhǔn)算法［J］.傳感器與微系統(tǒng)，2008，27(4):108－110.

［3］Stephens M，Harris C.A combined corner and edge detection［C］∥Proceedings of the Fourth Alvey Vision Conference，Manchester，UK，1988.

［4］Michael J，Stephen B，Smith M.SUSAN—A new approach to low level image processing［J］.Int’l J of Comput Vision，1997，23(1):45－78.

［5］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［6］Schmid C，Mikolajczyk K.Scale and affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60(1):63－86.

［7］Lowe D G.Object recognition from local scale-invariant features［C］∥Proceedings of the International Conference on Computer Vision，Corfu，Greece，1999.

［8］Ess A，Bay H，Tuytelaars T，et al.SURF:Speeded up robust features［J］.Computer Vision and Image Understanding，2008，110(3):346－359.

［9］Jones M，Viola P.Rapid object detection using a boosted cascade of simple features［C］∥Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Kauai，HI，USA，2001.

［10］楊克儉，吳 涵.K-D樹在微型數(shù)據(jù)庫引擎中的應(yīng)用［J］.自動化技術(shù)與應(yīng)用，2007，26(1):9－14.

［11］安 波，曲天偉，陳桂蘭.改進(jìn)的RANSAC算法在圖像配準(zhǔn)中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2010，30(7):1849－1872.

［12］張銳娟，張建奇，楊 翠.基于SURF的圖像配準(zhǔn)方法研究［J］.紅外與激光工程，2009，38(1):160－165.