一種基于SURF的全景圖像配準算法*

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

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

0 引言

全景圖像的配準和拼接已成為圖像處理、計算機視覺等領域的重要研究課題，其中，全景圖像的配準是圖像融合、三維環境重建的技術基礎。全景圖像自動配準［1］大體分為基于灰度［2］和基于特征兩類，其中，前者研究較少，后者特別是基于特征點的匹配研究較多。基于特征點配準方法的大體流程為:先提取各個圖像的特征點，再完成特征點之間的匹配，然后通過匹配的特征建立圖像間的映射變換，最后給出配準后的圖像。本文采用基于特征點的方法實現全景圖像配準。

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

1 SURF算法

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

1.1 SURF算法特征點檢測

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

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

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

其中，Happrox的行列式為

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

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

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

根據Fast-Hessian矩陣行列式的閾值，檢測圖像滿足閾值要求的點，然后在該點周圍的26個點范圍內進行非最大化抑制，得到特征點集，最后進行三維二次插值，對特征點實現亞像素級定位。

1.2 SURF算法興趣點描述符的表示

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

在圓心為特征點，半徑為6σ(σ為尺度)的圓內，計算尺寸為4σ 的 Harr小波響應 dx，dy，對 dx，dy進行高斯加權(2σ)。用角度為π/3的扇形繞特征點旋轉一周，計算扇形在每個角度時的dx+dy。當dx+dy最大時的方向即為特征點的方向，如圖2所示。

選定方向，以特征點為核心，構建一個大小為20σ的正方形窗，與特征點對齊。將這個正方形窗劃分為4×4個小正方向區域，計算每個小區域內的 dx，dy，并用高斯函數(3σ)進行加權。每個小區域內的描述符表示為

圖2 特征點方向計算Fig 2 Computation of feature point’s direction

式中 Desc_squre為四維向量，4×4個小區域就組成了特征點的64維描述符向量。

2 特征點匹配與仿射矩陣計算

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

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

2.1 K-D樹最近鄰搜索

64-D最近鄰搜索算法是一個遞歸的算法，在64-D樹上進行。

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

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

1)從根節點開始往下搜索子樹。

2)如果搜索到葉子節點，存儲該葉子節點為當前最近鄰點 current best。

3)在每個節點上，首先判斷計算當前節點與目標節點的距離，如果當前節點與給定的目標點的距離更小，則更新current best。然后，判斷以目標節點為中心，以當前最佳距離為半徑的子超空間是否與分裂超平面相交。若相交，則搜索右子樹;否則，忽略右子樹，繼續搜索。

4)最后算法在根節點上完成上述步驟，結束。

2.2 最近鄰次近鄰比值判別

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

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

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

2.3 變換矩陣參數計算

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

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

RANSAC分為3步進行:第1步隨機選取3組匹配點，估計H的6個參數;第2步利用估計的參數對余下的匹配點進行判斷，區分出內點和外點集，記錄內點集的數量，用新內點集重新估計參數;第3步，當內點數目最大時，在該內點集上給出H的最佳估計。

3 性能測試

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

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

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

表1 圖像配準用時比較Tab 1 Comparison of time-consumption of image registration

圖4 SURF特征點檢測Fig 4 SURF feature points detection

圖5 特征點匹配Fig 5 Feature point match

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

圖6 圖像旋轉后特征點匹配Fig 6 Feature point match after rotating

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

4 結束語

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

［1］Lowe D G，Brown M.Recognising panoramas［C］∥Proceedings of the Ninth IEEE International Conference on Computer Vision，Nice，France，2003.

［2］曹云峰，張 珍，丁 萌，等.一種基于廣義互信息的圖像配準算法［J］.傳感器與微系統，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樹在微型數據庫引擎中的應用［J］.自動化技術與應用，2007，26(1):9－14.

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

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