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

楊超　余厚云　劉斌

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

關(guān)鍵詞： Harris角點； SURF描述子； L?M非線性優(yōu)化； 圖像匹配； 圖像拼接

中圖分類號： 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 引 言

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

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

1 角點特征提取

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

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

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

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

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

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

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

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

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

2 特征描述與匹配

特征描述子又稱特征矢量，它對特征點進行獨特性描述。為實現(xiàn)圖像旋轉(zhuǎn)不變性，首先根據(jù)特征點的局部圖像結(jié)構(gòu)求得一個方向基準即主方向，再確定描述子。

2.1 主方向的確定

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

2.2 特征矢量生成

在積分圖像中以特征點為中心取大小為[L×L]的正方形區(qū)域[P，]正方形的兩條邊分別平行和垂直于主方向，[L]為正方形邊長，區(qū)域[P]即為計算特征矢量的區(qū)域?？紤]到編程方便，實際計算時先取兩邊平行于積分圖像坐標軸且與[P]等大小的正方形區(qū)域[Q，]再按公式（1）對區(qū)域[Q]中包含的點做旋轉(zhuǎn)運算，得到其在對應(yīng)區(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]內(nèi)的像元坐標。

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

與SURF法類似，在求沿主方向和垂直于主方向的Haar小波響應(yīng)時，先求像元水平、垂直方向的Haar響應(yīng)值，經(jīng)高斯加權(quán)后，再根據(jù)公式（2）按主方向?qū)ζ溥M行旋轉(zhuǎn)變換。

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

式中：[（dxP，dyP），][（dx，dy）]分別為區(qū)域[P]附近像元旋轉(zhuǎn)前、后的Haar響應(yīng)。

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

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

2.3 對應(yīng)點匹配

2.3.1 角點初始匹配

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

2.3.2 匹配點集的提純

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

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

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

應(yīng)該注意的是，由于初始匹配集合中存在一定的誤配點對，且抽樣次數(shù)[N]遠小于集合中任意4點對的組合數(shù)，因此首次提純的閾值[d]不應(yīng)設(shè)置得過小，否則會導(dǎo)致首次提純后的內(nèi)點對數(shù)過小或不穩(wěn)定。經(jīng)首次提純?nèi)コ罅空`配點后，再減小閾值[d]做二次提純，所得結(jié)果較好。

2.3.3 變換矩陣的優(yōu)化

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

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

實際情況中，映射點與圖3中的匹配點[（xli，yli）]不完全重合。優(yōu)化目標是求變換矩陣中[m0～m7]組成的向量[m]的最優(yōu)解，即最優(yōu)解滿足所有圖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]為匹配點對數(shù)，[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]為比例系數(shù)。[uI]的存在可保證[J（mk）TJ（mk）+uI]正定。設(shè)置迭代次數(shù)[k，]通過調(diào)節(jié)比例系數(shù)[u]使[F（m）]逐步逼近最小值，從而得到最優(yōu)變換矩陣。

3 圖像融合

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

5 結(jié) 論

本文以Harris角點為特征點，以改進的SURF描述子構(gòu)造角點特征矢量，提出了基于Harris角點快速匹配的圖像拼接方法，并利用RANSAC法進行二次內(nèi)點對提純后，再通過L?M法實現(xiàn)了變換矩陣的非線性優(yōu)化。該方法在保證匹配快速性和準確性的前提下，彌補了傳統(tǒng)方法特征點不可預(yù)測的不足。通過特征點匹配和圖像拼接實驗的結(jié)果表明，本文方法對存在尺度變化及拍攝角度差的兩幅圖像進行拼接，能達到良好的拼接水平。同時，圖像匹配時間可節(jié)約35%以上，整個圖像拼接時間可節(jié)約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].北京：國防工業(yè)出版社，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.