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

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

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

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

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

關(guān)鍵詞:SIFT特征匹配;金字塔;雙向匹配;圖像配準(zhǔn)

1　引 言

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

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

2　SIFT特征匹配的基本原理

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

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

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

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

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

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

2．2特征點(diǎn)定位

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

其中,γ是控制特征點(diǎn)穩(wěn)定性的參數(shù),表示最大特征值和最小特征值的比值。

2．3特征點(diǎn)方向確定

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

2．4特征點(diǎn)描述符生成

將坐標(biāo)軸旋轉(zhuǎn)至特征點(diǎn)主方向,把特征點(diǎn)的16× 16窗口分為16個(gè)4×4的子窗口。計(jì)算每個(gè)字窗口中16個(gè)像素點(diǎn)的梯度方向,將所有梯度方向做高斯加權(quán)求和,得到一個(gè)包含8個(gè)方向梯度的種子點(diǎn),最后得到一個(gè)128的特征向量[14,15]。

2．5SIFT特征匹配

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

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

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

3　SIFT特征匹配策略的改進(jìn)

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

圖2　本文算法流程

其中,T1、T2為匹配閾值,在實(shí)驗(yàn)過程中T1、T2不相互影響,可取相同值。

具體步驟如下:

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

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

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

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

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

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

4　匹配實(shí)驗(yàn)及結(jié)果分析

為了全面驗(yàn)證本文改進(jìn)算法的性能,本文選擇了不同焦距拍攝的圖像分別進(jìn)行原始算法匹配和本文算法匹配實(shí)驗(yàn),從算法耗時(shí)、匹配點(diǎn)數(shù)以及匹配正確率三個(gè)方面進(jìn)行比較,實(shí)驗(yàn)環(huán)境如表1所示。

本文實(shí)驗(yàn)環(huán)境 表1

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

圖3　原SIFT特征匹配結(jié)果

圖4　本文算法匹配結(jié)果

原SIFT匹配算法與本文改進(jìn)匹配算法的結(jié)果對比 表2

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

5　結(jié) 語

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

參考文獻(xiàn)

[1] 閘旋,王慧,程挺等．一種基于分塊策略的SIFT特征快速提取與匹配方法_閘旋[J]．測繪科學(xué)技術(shù)學(xué)報(bào),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] 宛蓉,蔣丹妮,周天順．基于改進(jìn)的SIFT算法的異源影像匹配[J]．地理空間信息,2014,12(4):63～65．

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

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

[11] 鄭永斌,黃新生,豐松江．SIFT和旋轉(zhuǎn)不變LBP相結(jié)合的圖像匹配算法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010,22(2):286～292．

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

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

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

[15] 宋佳乾,汪西原．基于改進(jìn)SIFT特征點(diǎn)匹配的圖像拼接算法[J]．計(jì)算機(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

文獻(xiàn)標(biāo)識碼:A

收稿日期:?2015—02—06

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

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