基于Harris角點和改進SURF描述子的圖像快速拼接

楊超　余厚云　劉斌

摘 要： 針對SURF算法計算量大、對應點匹配時間長的不足，以Harris角點取代SURF斑點作為特征點，改進了描述子生成區域的子塊劃分方式，使區域面積減小40%。同時，引入尺度因子[s]以彌補采樣區域減小的影響，形成一種計算量小、獨特性好的描述子。以該方法構造的角點特征矢量參與同名點匹配，可實現較好的匹配快速性和準確性。匹配完成后，分別使用RANSAC方法和L?M方法獲取變換矩陣并進行非線性優化，最后根據圖像的不同區域采用不同方法完成圖像融合。實驗結果表明，該圖像拼接方法與傳統SURF法相比，圖像匹配時間可節約35%以上，整體圖像的拼接時間可節約30%左右，大幅提高了圖像拼接的效率。

關鍵詞： Harris角點； SURF描述子； L?M非線性優化； 圖像匹配； 圖像拼接

中圖分類號： TN957.52?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2015）11?0087?04

Image fast mosaic based on Harris corner points and improved SURF descriptor

YANG Chao， YU Hou?yun， LIU Bin

（College of Mechanical and Electrical Engineering， Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China）

Abstract： Since the shortages of SURF algorithm are the large amount of calculations and long matching time of corresponding points， the Harris corner points are taken as the feature points instead of the SURF spots. The sub?block dividing mode of descriptor generated region is improved， and the region areas are reduced by 40%. The descriptor with little calculated quantity and good peculiarity is shaped by the introduced scale factor s to eliminate the influence of sample region decrease. The corner point characteristic vector parameter structured by the proposed method is matched with the same name point， so rapidity and accuracy of matching are well realized. After matching， RANSAC method and L?M method are respectively adopted to obtain the transformation matrix， and execute nonlinear optimization. Image fusion is accomplished with different methods according to different image regions. The experimental results show that the image mosaic method， compared with the traditional SURF method， can save more than 35% image matching time and about 30% mosaic time of the whole image. The efficiency of image mosaic is greatly improved.

Keywords： Harris corner point； SURF descriptor； L?M nonlinear optimization； image matching； image mosaic

0 引 言

圖像拼接是一種將多幅有重疊部分的圖像拼成一幅大型無縫高分辨率圖像的技術，它廣泛應用于照相繪圖、醫學影像以及視覺測量等領域。圖像拼接主要由特征提取、特征描述及匹配、變換矩陣計算和圖像融合四個部分組成。特征提取以對特征點的提取為主，提取算法包括以斑點檢測與匹配相結合的穩健的SIFT算法[1]、利用積分圖像和DoH近似實現快速斑點檢測匹配的SURF算法[2]和以角點為特征點的魯棒Harris角點提取法[3]等。特征匹配是將不同圖像中的對應點匹配起來，并盡可能剔除錯誤匹配點對，它為變換矩陣的計算提供原始數據。變換矩陣是利用若干匹配點計算后經優化得到，圖像融合則是指運用線性插值等方法使圖像過渡自然、色彩均勻。圖像拼接的精度很大程度上取決于特征描述和匹配環節，相應的算法有Lowe提出的SIFT算法、Bay提出的SURF算法以及Mikolajczyk提出的GLOH[4]算法等。然而這些算法均需要對圖像進行復雜的預處理以建立圖像金字塔等，再通過計算確定特征點，進而建立特征描述子參與匹配。它們雖然匹配效果較好，但運算復雜、耗時長，且特征點不可預測。國內也有研究人員提出基于不變矩結合區域灰度相關性的方法[5]進行特征匹配，然而在缺少更多約束條件的情況下，這些方法匹配效率不高。

事實上，角點作為圖像中的重要特征已被人們深入研究，以角點為特征點的特征匹配在圖像識別和測量等應用領域逐漸發揮越來越重要的作用。因此，本文提出一種以Harris角點為特征點，以改進的SURF描述子構造角點特征矢量，實現角點快速匹配并最終完成圖像拼接的方法。實驗結果表明，該方法與傳統SURF方法相比，圖像匹配效果達到同等水平，而匹配時間可節約35%，整幅圖像拼接時間可節約30%以上，大幅度提高了圖像拼接的效率。

1 角點特征提取

角點是圖像灰度發生劇烈變化或圖像邊緣曲線上曲率為極大值的點。Harris角點提取算法簡單，具有旋轉和尺度不變性以及對圖像亮度和對比度的部分不變性等優點，使其在圖像角點檢測方面應用廣泛。本文首先將兩幅原始圖像預處理后以相同參數進行Harris角點提取，并將角點存于兩個不同序列中。再用這些角點代替SURF算法中矩陣運算得到的斑點作為圖像特征點，使圖像匹配的運算量小、速度快。

Harris角點檢測[6]過程可歸納為如下步驟：

（1） 計算圖像[I（x，y）]的水平和垂直方向的梯度[Ix，][Iy。]

（2） 計算[x，][y]方向梯度乘積[I2x，][I2y，][Ixy。]

（3） 對[I2x，][I2y，][Ixy]使用高斯函數加權生成[M]矩陣元素[A，][B，][C。]

（4） 按下式計算每個像元的Harris響應值[R，]小于閾值[T]的置0。

[R={R：detM-α（traceM）2

式中：det[M=AC-B2，]trace[M]為矩陣[M]的跡；α為經驗常數，一般取0.04～0.06。[α]增大則角點檢測的靈敏度降低，檢出的角點數量減少。[α]減小則角點檢測的靈敏度提高，檢出的角點數量增多。

（5） 進行鄰域非極大值抑制，局部極大值即認為是角點。

2 特征描述與匹配

特征描述子又稱特征矢量，它對特征點進行獨特性描述。為實現圖像旋轉不變性，首先根據特征點的局部圖像結構求得一個方向基準即主方向，再確定描述子。

2.1 主方向的確定

以Harris角點作為特征點，并以其為中心，對給定半徑（文中取12 pixel）的圓形區域內的采樣點計算Haar小波響應。然后對小波響應結果進行高斯加權，使角點附近采樣點的小波響應值權重大，以彌補仿射不變性的不足。最后依照SURF方法求得特征點的主方向角[θ。]

2.2 特征矢量生成

在積分圖像中以特征點為中心取大小為[L×L]的正方形區域[P，]正方形的兩條邊分別平行和垂直于主方向，[L]為正方形邊長，區域[P]即為計算特征矢量的區域。考慮到編程方便，實際計算時先取兩邊平行于積分圖像坐標軸且與[P]等大小的正方形區域[Q，]再按公式（1）對區域[Q]中包含的點做旋轉運算，得到其在對應區域[P]附近的坐標。

[xP=x0-Δx?s?sinθ+Δy?s?cosθyP=y0+Δx?s?cosθ+Δy?s?sinθ] （1）

式中：[Δx=xQ-x0，][Δy=yQ-y0；][（x0，y0），][（xQ，yQ）]和[（xP，yP）] 分別為特征點坐標和正方形[Q，][P]內的像元坐標。

同時，為了取得特征點附近盡可能大的區域，在公式（1）中引入了尺度因子[s。][s=1]表示采集區域[P]中所有的像元；[s>1]表示間隔采樣，采樣區域將大于[P，]系數[s]表征了采樣的疏密程度。[s]不宜過大，否則采樣點距離遠，對特征保持不利。如圖1和圖2所示，隨著[s]的增大，正確角點匹配對數先增后減，而錯誤匹配點對數有上升趨勢。本文中取[s=2.5。]

與SURF法類似，在求沿主方向和垂直于主方向的Haar小波響應時，先求像元水平、垂直方向的Haar響應值，經高斯加權后，再根據公式（2）按主方向對其進行旋轉變換。

[dx=ω（-dxPsinθ+dyPcosθ）dy=ω（dxPcosθ+dyPsinθ）] （2）

式中：[（dxP，dyP），][（dx，dy）]分別為區域[P]附近像元旋轉前、后的Haar響應。

特征矢量包含信息量的多少和運算量大小，均取決于區域[P]邊長的大小。設SURF法所取的正方形區域邊長為[L，]本文為降低計算量，取邊長[L=3L4。]SURF法在形成特征矢量中的元素時，將[L×L]的正方形劃分成均勻的4×4個邊長為[L4]的無重疊子塊。本文將正方形區域均分成4×4個子塊，子塊面積與SURF法等大，但由于[L

為避免重復計算，本文先求出[L×L]中所有像元對應的響應[dx，][dy，]再按照子塊的劃分，分別求出每個子塊的4維子塊矢量[[Σdx，Σdx，Σdy，Σdy]，]由16個子塊得到64維特征矢量，并進行歸一化處理。

2.3 對應點匹配

2.3.1 角點初始匹配

圖3和圖4分別為原始待拼接圖像的左、右兩圖，利用相似性準則依次計算左圖角點的特征矢量與右圖中全部特征矢量的歐式距離，記錄這些歐式距離中最小值所對應的右圖中的角點。若歐氏距離最小值與次小值的商小于給定閾值[μ，]則認為該最小值所對應的右圖中的角點與左圖中當前角點初始匹配成功；否則，認為右圖中不存在左圖角點的匹配點，舍去左圖中當前角點。根據以上算法，從而得到兩幅圖像角點的初始匹配集合。

2.3.2 匹配點集的提純

初始匹配集合中必然有誤匹配點對，這對求取變換矩陣危害很大。為此，本文采用RANSAC法[7]分兩步進行提純：

（1） 從初始匹配集合中隨機抽取4對點，計算出變換矩陣。利用該矩陣將初始匹配集合中圖4角點映射到圖3，計算映射點與圖3匹配點之間的歐氏距離[D，]設置距離閾值[d。]若[D

（2） 以[N]個內點對集合中內點對數最多的集合作為初始內點對集合，重復步驟（1）。此時提純所用的閾值應小于第一次，以提高精度，完成第二次提純。以本次提純后所得內點對數最多的集合所對應的矩陣作為初始變換矩陣。

應該注意的是，由于初始匹配集合中存在一定的誤配點對，且抽樣次數[N]遠小于集合中任意4點對的組合數，因此首次提純的閾值[d]不應設置得過小，否則會導致首次提純后的內點對數過小或不穩定。經首次提純去除大量誤配點后，再減小閾值[d]做二次提純，所得結果較好。

2.3.3 變換矩陣的優化

以上述步驟（2）提純所得變換矩陣為初始矩陣，利用Levenberg?Marquardt法[8]對其進行非線性優化。圖4中的角點[（xri，yri）]與它在圖3中的映射點[（x′i，y′i）]之間的對應關系為：

[x′iy′i1=m0m1m2m3m4m5m6m71?xriyri1] （3）

實際情況中，映射點與圖3中的匹配點[（xli，yli）]不完全重合。優化目標是求變換矩陣中[m0～m7]組成的向量[m]的最優解，即最優解滿足所有圖4角點的映射點與圖3匹配點之間的歐氏距離和[F（m）]取得最小值。

[F（mk）=in[（xli-xri）2+（yli-yri）2]12] （4）

令[fi（mk）=[（xli-xri）2+（yli-yri）2]14，]則[F（mk）=infi（mk）2=]

[f（mk）Tf（mk）。]公式（4）中，[n]為匹配點對數，[f（mk）=][[f1（mk）， f2（mk），…， fk（mk）]T]為[n]維列向量，[mk]為迭代[k]次后向量[m]的值。Levenberg?Marquardt迭代公式為：

[mk+1=mk+ΔmΔm=-[J（mk）TJ（mk）+uI]-1J（mk）Tf（mk）] （5）

式中：[J（mk）]為[fi]對[m]的[n×8]階雅可比矩陣；[I]為單位矩陣；[u>0]為比例系數。[uI]的存在可保證[J（mk）TJ（mk）+uI]正定。設置迭代次數[k，]通過調節比例系數[u]使[F（m）]逐步逼近最小值，從而得到最優變換矩陣。

3 圖像融合

利用提純優化后的變換矩陣計算出圖4四個頂點映射到圖3中的坐標，以確定融合后圖像的大小，開辟空白圖。先將圖3復制到空白圖上，再將圖4映射到空白圖中，兩圖經融合形成圖5。融合過程劃分為以下四部分：

（1） 圖5中僅屬于圖3的區域，不進行處理。

（2） 圖5中僅屬于圖4的區域，為避免空像素，采用后向映射的方法處理。即由該區域像素點反求該點映射到圖4的坐標，該坐標一般為非整數，采用雙線性插值法計算該坐標處的像素值，以該像素值作為圖4中對應坐標點的像素值。

（3） 圖5中圖3、圖4都映射不到的區域賦0。

（4） 圖5中屬于圖3和圖4映射重合的區域，首先按步驟（2）獲得當前位置映射到圖4的像素值，將該像素值與對應的圖3像素值按該位置離兩側重合區邊界的遠近進行加權融合，使圖像過渡自然。

4 實驗結果與分析

本文采用VC++6.0，OpenCV1.1實現變換矩陣的計算和圖像拼接融合，采用的原始圖像大小為360×480像素，圖像拼接的結果如圖5和圖6所示。從拼接結果看，圖6未對變換矩陣進行優化，圖像中建筑物右側有明顯放大趨勢。而在圖5中，變換矩陣經L?M優化后，圖像右側的放大趨勢得到很好地抑制。

表1中列出了分別采用本文方法與SURF法進行特征點匹配的效果對比，結果表明兩種方法的最終精確匹配點數相差較小，但本文方法匹配時間減少了35%左右，大幅提高了匹配效率。表2中列出了以不同方法完成特征匹配并獲得最終變換矩陣的結果以及整體拼接時間。結果表明，本文方法與SURF方法最終得到的變換矩陣十分相近，說明本文方法穩定可靠。整體拼接時間上，本文方法比SURF方法節約30%左右，在拼接速度上有較大優勢。

5 結 論

本文以Harris角點為特征點，以改進的SURF描述子構造角點特征矢量，提出了基于Harris角點快速匹配的圖像拼接方法，并利用RANSAC法進行二次內點對提純后，再通過L?M法實現了變換矩陣的非線性優化。該方法在保證匹配快速性和準確性的前提下，彌補了傳統方法特征點不可預測的不足。通過特征點匹配和圖像拼接實驗的結果表明，本文方法對存在尺度變化及拍攝角度差的兩幅圖像進行拼接，能達到良好的拼接水平。同時，圖像匹配時間可節約35%以上，整個圖像拼接時間可節約30%以上，大幅提高了圖像拼接的效率。

參考文獻

[1] LOWE D G. Object recognition from local scale?invariant feature [C]// International Conference on Computer Vision. Greece：IEEE， 1999： 1150?1157.

[2] BAY H， ESS A， TUYTELAARS T， et al. Speeded?up robust features （SURF） [J]. Computer Vision and Image Understanding， 2008， 110（3）： 346?359.

[3] HARRIS C， STENHENS M. A combined corner and edge detector [C]// Proceedings of Fourth Alvey Vision Conference. Manchester： ICASSP， 1988： 147?152.

[4] MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（10）： 1615?1630.

[5] 徐春萍，柴亞輝，李廣麗，等.一種基于Harris角點特征精確匹配的圖像拼接方法[J].實驗室研究與探索，2011（10）：40?43.

[6] 王永明，王貴錦.圖像局部不變性特征與描述[M].北京：國防工業出版社，2010.

[7] FISHER M， BOLLES R C. Random sample consensus： a paradigm for model fitting with application to image analysis and automated cartography [J]. Communications of ACM， 1981， 24（6）： 381?396.

[8] 伏燕軍，楊坤濤，鄒文棟，等.基于Levenberg?Marquardt算法的圖像拼接[J].激光雜志，2007，28（5）：46?48.

[9] GUI Yang， SU Ang， DU Jing. Point?pattern matching method using SURF and shape context [J]. Optik? International Journal for Light and Electron Optics， 2013， 124（14）： 1869?1873.

[10] TUYTELAARS T， MIKOLAJCZYK K. Local invariant feature detectors： a survey [J]. Foundations and Trends in Computer Graphics and Vision， 2008， 3（3）： 177?210.