一種基于金字塔相似層的SIFT雙向匹配算法研究

文雪中,馬紅(重慶市勘測院,重慶 400020)

一種基于金字塔相似層的SIFT雙向匹配算法研究

文雪中?,馬紅
(重慶市勘測院,重慶 400020)

摘 要:針對SIFT特征匹配算法誤匹配點多和特征空間中遍歷搜索速度慢的問題,提出了一種基于分層策略的SIFT雙向特征匹配算法。首先,建立待匹配圖像的金字塔影像,計算圖像的SIFT特征點,并根據不同金字塔層將特征點劃分為不同的集合;其次,選擇某一層集合,在另一圖像中尋找相似層,并確定兩幅圖像金字塔層之間的相似關系,在相似層之間設置閾值完成單方向匹配;然后,利用單向匹配結果完成已配對點集合的反向匹配。實驗結果證明本文方法能降低匹配時間,提高匹配正確率。

關鍵詞:SIFT特征匹配;金字塔;雙向匹配;圖像配準

1　引 言

長期以來,圖像匹配一直是模式識別、計算機視覺等領域的研究熱點,而圖像的局部不變特征,是研究圖像匹配的一個關鍵[1]。Lindeberg研究了圖像局部不變特征方法的理論基礎[2],而Lowe完善并實現了Lindeberg的理論;提出了SIFT(Scale Invariant Feature transform,即尺度不變特征變換)算子[3,4],它對幾何旋轉、尺度縮放、亮度變化保持不變性,對視角變化、仿射變換、噪聲也保持一定的穩定性[1]。

SIFT算子的缺點是計算量大,誤匹配點較多,對視角變化的穩定性不強;眾多學者對SIFT提出了很多改進方法,如PCA-SIFT算法利用主成分分析法對SIFT描述子進行降維處理[5],SUFT算法提高了特征點檢測速度[6],ASIFT算法增強了穩定性[7]。這些算法都繼承了SIFT的思想,并在特征點檢測或特征點描述上做了改進,但極少涉及對SIFT匹配策略的改進和優化。目前,SIFT算法的實現仍然是在整個特征空間進行的,當特征點空間較大時,匹配速度慢,且誤匹配率高[8,9]。本文針對這兩個問題,提出一種基于金字塔相似層間的特征匹配算法,減少特征空間搜索時間,并同時利用雙向匹配策略進行匹配,提高匹配正確率。

2　SIFT特征匹配的基本原理

SIFT特征匹配算法是基于尺度空間理論完成的,主要包括尺度空間極值點檢測、特征點定位、特征點方向確定、特征點描述符生成、特征點匹配[10,11],其基本流程如圖1所示。

圖1　SIFT特征匹配算法的基本流程

2．1高斯差分金字塔建立

利用DoG算子(Difference-of-Gaussian)構建高斯差分金字塔是實現SIFT特征匹配中極值點檢測的基礎。如式(1)所示,將一系列不同核值的高斯函數G (x,y,σ)與圖像I(x,y)做卷積運算,即可得到高斯尺度空間L(x,y,σ);根據式(2),對高斯尺度空間進行采樣可得到高斯金字塔,將相鄰的高斯尺度空間做差即可得到高斯差分尺度空間[12]。

高斯卷積核是實現尺度變換的唯一變換核,針對圖像I(x,y),其尺度空間L(x,y,σ)為原始圖像與一個可變尺度的二維高斯函數G(x,y,σ)的卷積運算。

將高斯差分尺度空間中間層的每個像素分別與同一層相鄰的8個像素、上層和下層各9個像素進行比較,確保在尺度空間和二維圖像空間都檢測到局部極值,找出極值點,即為特征匹配的候選點[13]。

2．2特征點定位

檢測到的極值點在位置和尺度上用2×2的Hessian矩陣H計算其穩定性,用穩定性度量標準η剔除不穩定的點(一般為對比度較低的極值點和邊緣上的極值點),剩下的極值點即為穩定性強的圖像特征點。H矩陣和η分別如式(3)和式(4)所示。

其中,γ是控制特征點穩定性的參數,表示最大特征值和最小特征值的比值。

2．3特征點方向確定

以某一特征點為中心,在高斯尺度空間中,計算該特征點及其領域點的梯度幅值m和方向θ,如式(5)和式(6)所示;利用直方圖統計特征點及其領域的梯度方向,并把直方圖的峰值作為特征點的主要方向,若存在其他方向能量高于主方向能量的80%,那么這些方向即為特征點的輔助方向[9,13]。

2．4特征點描述符生成

將坐標軸旋轉至特征點主方向,把特征點的16× 16窗口分為16個4×4的子窗口。計算每個字窗口中16個像素點的梯度方向,將所有梯度方向做高斯加權求和,得到一個包含8個方向梯度的種子點,最后得到一個128的特征向量[14,15]。

2．5SIFT特征匹配

在SIFT特征匹配算法中,用歐式距離作為特征點描述符相似性的度量因子。假定圖像M的特征點集合為A={a1,a2,…,aM},圖像N的特征點集合為B = {b1,b2,…,bN},那么圖像M中某個特征點描述與圖像N中某個特征點描述符的歐式距離如式(7)所示。

設圖像M中某個特征向量am與N中特征向量bm有最短歐式距離為dmm,與特征向量bk有次短歐式距離為dmk(且m≠k),若兩個距離滿足式(8),則認為該匹配點對正確。

其中,T為匹配閾值,一般取[0．4,0．8]之間的常數[9,12]。

3　SIFT特征匹配策略的改進

現有SIFT特征匹配算法在整個特征點向量集合中進行搜索匹配,若集合元素很多時,匹配時間較長,因此需要構建金字塔檢測圖像不同尺寸下的特征點,在圖像金字塔相似層之間進行搜索,減少搜索時間,提高匹配效率。另一方面,SIFT特征向量的匹配采用最鄰近距離算法完成,這種在參考圖像中尋找待匹配圖像特征點對應點的方式是帶有方向性的,即為待匹配圖像到參考圖像的單向匹配,算法雖然簡便,但誤匹配概率較大。因此,需要對SIFT單向匹配算法進行改正,將唯一性約束引入到匹配策略中,實現SIFT特征向量的雙向匹配,可以減少誤匹配點,進而提高匹配的正確率。本文改進后的匹配算法流程如圖2所示。

圖2　本文算法流程

其中,T1、T2為匹配閾值,在實驗過程中T1、T2不相互影響,可取相同值。

具體步驟如下:

第一步,針對兩幅待匹配的影像M和N,分別建立金字塔影像,并確定兩幅影像金字塔層之間的相互關系。

第二步,計算圖像M和圖像N的SIFT特征點,并將處于同一個金字塔層的特征點組成一個集合;得到圖像M的特征點集合A={{A1},{A2},…,{Am}},圖像N的特征點集合B={{B1},{B2},…,{Bn}}。其中Ai表示圖像M中處于某一金字塔層的特征點。

第三步,取出圖像M中某一層的特征點子集Ai,分別在圖像N的特征點子集中進行匹配,如果圖像M的特征點子集Ai與圖像N的特征點子集Bj有最大匹配點數,那么圖像M的第i層金字塔與圖像N的第j層金字塔相似,同理可求得圖像M的第i+k層與圖像N的j+k層相似。

第四步,根據單向SIFT特征向量的匹配算法,計算特征點子集Ai到Bj的匹配點對,剔除閾值小于T1的匹配點對,保留匹配閾值大于T1的匹配點對,作為Ai到Bj的匹配點對集合。

第五步,根據第四步中計算得到的匹配點對集合,用同樣的方式逆向計算特征點子集Bj中已經被匹配的點在特征點子集Ai中的匹配點對,即求已被匹配點在特征點子集Ai中的最鄰近與次鄰近的距離比率,若比率小于匹配閾值T2,才作為正確匹配點[10],否則剔除匹配點對,最后得到的匹配點對即為特征點子集Ai與Bj的雙向匹配結果。

這種基于金字塔層的雙向匹配策略比單純的SIFT算法約束條件更強,一方面可以降低檢索時間,提高匹配效率,另一方面可以檢測出更多的誤匹配點,提高匹配的正確性;使得在大面幅的圖像匹配中適用性更強。

4　匹配實驗及結果分析

為了全面驗證本文改進算法的性能,本文選擇了不同焦距拍攝的圖像分別進行原始算法匹配和本文算法匹配實驗,從算法耗時、匹配點數以及匹配正確率三個方面進行比較,實驗環境如表1所示。

本文實驗環境 表1

本文選取一組不同焦距不同角度拍攝的圖像進行實驗,分辨率為1 200×1 800,檢測到的特征點數為1 051 和866。對圖像的特征點分別用原匹配策略和本文改進匹配策略進行匹配,匹配結果如圖3和圖4所示,兩種算法的耗時、匹配點數、正確率結果如表2所示。

圖3　原SIFT特征匹配結果

圖4　本文算法匹配結果

原SIFT匹配算法與本文改進匹配算法的結果對比 表2

根據表2的統計結果可知:在計算耗時上,改進匹配策略的算法耗時是原匹配算法耗時的0．65倍;在匹配點數上,針對同樣多的特征點,原匹配算法能匹配191對特征點,改進后的匹配算法能匹配112對特征點,匹配點數減少了約58%;在匹配正確率上,原匹配算法正確率為81．15%,改進后的匹配算法匹配正確率為95．53%。進一步分析,本文改進后的匹配算法雖然在匹配的特征點數上有所消減,但匹配效率提高了35%,匹配正確率提升了14．38%。本文改進的匹配策略能明顯降低匹配時間,提升匹配正確率,在大幅面圖像匹配中具有明顯優勢。

5　結 語

本文在研究SIFT特征匹配算法原理的基礎上,針對原有SIFT匹配算法計算時間長、誤匹配點多的問題,提出了一種基于金字塔相似層的雙向匹配策略。與原匹配策略相比,改進后的匹配策略一方面通過金字塔相似層之間搜索匹配點,縮小了搜索范圍,進而提高了匹配效率,另一方面,通過引入唯一性約束條件,利用匹配結果進行逆向匹配,將同時滿足雙向匹配的結果作為最終匹配結果,提高了匹配正確率;由于受金字塔相似層查找和反向閾值設定因素的影響,改進后的算法匹配點數有所下降。在圖像幅面越大、特征點數越多的情況下,本文改進的匹配算法速度提升和正確率提升也越大,相對消減的匹配點數影響也越小,實用性也更強。

參考文獻

[1] 閘旋,王慧,程挺等．一種基于分塊策略的SIFT特征快速提取與匹配方法_閘旋[J]．測繪科學技術學報,2014, 31:505～509．

[2] Lindeberg T．Detection and Ridge Detection with Automatic Scale Selection[J]．International Journal of Computer Vision．1998,2(30):117～154．

[3] Lowe D G．Object Recognition from Local Scale-Invariant Features[A]．7th International Conference on Computer Vision．Corfu,1999:1150～1157．

[4] Lowe D G．Distinctive Image Feature Form Scale-Invariant Keypoints[ J]．International Journal of Computer Vision．2004,60(2):91～110．

[5] Yan K,Sukthankar R．PCA-SIFT:a more distinctive representation for local image descriptors[A]．New Youk:2004．

[6] Herbert B,Tinne T,Luc V G．SURF:speeded up robust features[J]．Computer vision and image understanding．2008, 3(110):346～359．

[7] Morel J M,Yu G．A per[J]．SIAM journal on imaging sciences,2009,9(2):438～469．

[8] 宛蓉,蔣丹妮,周天順．基于改進的SIFT算法的異源影像匹配[J]．地理空間信息,2014,12(4):63～65．

[9] 盧朝梁,馬麗華,陳豪．改進的SIFT特征匹配算法[J]．空軍工程大學學報·自然科學版,2014,15(1):72～76．

[10] 呂倩利,邵永社．基于SIFT特征的異源遙感影像匹配方法研究[J]．計算機工程與應用,2012,48(36):171～175．

[11] 鄭永斌,黃新生,豐松江．SIFT和旋轉不變LBP相結合的圖像匹配算法[J]．計算機輔助設計與圖形學學報, 2010,22(2):286～292．

[12] 梁建國,馬紅．改進的SIFT雙向匹配算法在異源影像匹配中的應用[J]．地理空間信息,2014,12(6):57～64．

[13] 劉煥敏,王華,段慧芬．一種改進的SIFT雙向匹配算法[J]．兵工自動化,2009,28(6):89～91．

[14] 呂倩利,邵永社．基于SIFT特征的異源遙感影像匹配方法研究[J]．計算機應用與工程,2012,36(48)．

[15] 宋佳乾,汪西原．基于改進SIFT特征點匹配的圖像拼接算法[J]．計算機測量與控制,2015,23(2):512～515．

Research on Sift Bidirectional Matching Algorithm Between the Similar Prymid Layers

Wen Xuezhong,Ma Hong
(Chongqing Survey Institute,Chongqing 400020,China)

Abstract:Aimed at the high wrong match points and slow matching speed in searching the whole database of feature points of SIFT feature matching method,we proposed an improved matching method of searching between the similar pyramid layers using bidirectional matching．First,we calculate the pyramid image and SIFT feature points of the input images,and divid the feature points into different sets according to the different pyramid layers．Then a layer set in the input image pyramid is chosen to search for the similar layer in the another image pyramids,and then the similarity between tow image pyramid layers is determined,and matching the feature points between the similarity pyramid layers by single direction．Finally,matches the feature points which have been matched by reverse direction．The experimental results demonstrate that this approach can reduce the matching time and improve the matching accuracy．

Key words:scale invariant features transform match;pyramid image;bidirectional match algorithm;image matching

文章編號:1672-8262(2015)04-99-04中圖分類號:P234．1

文獻標識碼:A

收稿日期:?2015—02—06

作者簡介:文雪中(1979—),男,高級工程師,主要從事測繪地理信息工程建設管理工作。

基金項目:“十二五國家科技支撐計劃”課題(2011BAH12B07-03)