基于相似特征點集的SIFT匹配改進算法

高　放，陸頻頻，王　旭

(遼寧工程技術大學 測繪與地理科學學院,遼寧 阜新 123000)

?

基于相似特征點集的SIFT匹配改進算法

高放，陸頻頻，王旭

(遼寧工程技術大學 測繪與地理科學學院,遼寧 阜新 123000)

摘要：當影像中存在相似或重復場景時，傳統(tǒng)SIFT匹配算法存在匹配成功率低，目前改進的SIFT匹配算法計算量大?；谙嗨铺卣鼽c集的SIFT匹配改進算法，依據(jù)相似性或重復場景的影像紋理特點，在SIFT特征點匹配過程中，通過設定閾值提取初始同名點，建立針對未成功匹配參考特征點的相似特征點集，利用已獲取初始同名點建立仿射幾何約束模型構建參考特征點的匹配約束窗口，在該窗口內(nèi)利用特征點相對主方向及尺度約束，對特征相似點集進行匹配獲得同名點，最后采用RANSAC算法剔除誤匹配點。對比實驗結果表明，在影像像對間存在較多相似性場景，同時存在較大尺度縮放、旋轉(zhuǎn)變換、視角及模糊差異的情況下，文中算法在匹配成功率和計算復雜度上具有明顯的優(yōu)勢。

關鍵詞：SIFT;相似特征點集;幾何約束;匹配;初始同名點

在基于特征的影像匹配技術中，尺度不變特征變換 (Scale Invariant Feature Transform,SIFT)算法由于對尺度縮放、旋轉(zhuǎn)及弱仿射變換保持良好的不變性而受到廣泛關注[1-3]。當影像中存在重復或相似場景時，以梯度方向向量距離作為相似性測度將會降低特征匹配的成功率[4-6]。因此SIFT算法近年來被廣泛改進，通常包括：第一類方法是建立幾何約束模型來對特征點進行約束匹配。如利用核線模型、同名直線模型或影像粗匹配模型對特征點進行幾何約束匹配[7-8]。這種方法匹配成功率較高，但需預先獲取一些約束模型的參數(shù)。第二類方法是以初始匹配點出發(fā)，通過構建幾何約束模型來對剩余特征點進行匹配[9]。相對于第一類方法，第二類方法匹配成功率更高，但不足之處在于需要對剩余特征點進行遍歷幾何約束，故耗時較長。第三類方法是在局部描述子的基礎上引入了全局向量，以此來增大重復相似場景特征之間的差異[10]。但該方法需對所有特征點進行全局計算，增加了算法的復雜度，同時也很難對影像尺度變換保持不變性。

針對上述方法中存在的問題，本文依據(jù)影像中重復或相似場景的紋理特點，在SIFT特征匹配階段，提出一種基于特征相似點集的匹配方法。該方法有異于先建立幾何約束模型再進行特征向量匹配策略，而是基于傳統(tǒng)SIFT特征匹配方法同時建立同名點集和相似特征點集，利用同名點約束相似點集進行匹配，從而有效限定相似性場景的特征匹配搜索范圍，避免了傳統(tǒng)特征點二次約束匹配的遍歷計算，大幅降低算法的復雜度，提高相似性場景同名點匹配成功率。

1算法

如圖1所示為本文提出匹配算法流程圖，首先在像對影像上提取特征點，利用最近次近鄰方法基于閾值判斷得到兩組點集，對不符合閾值要求的特征點求取對應影像中前n個最近鄰特征點，構成針對該特征點的相似特征點集。符合閾值要求的匹配點通過隨機幾何約束模型及RANSAC算法剔除誤匹配點后構成初始同名點，利用初始同名點構建約束窗口模型、特征點相對主方向和尺度約束模型，利用上述多種約束模型對特征相似點集進行約束匹配，滿足要求的點構成新同名點，采用RANSAC算法剔除誤匹配點后，最終基于同名點集對待匹配影像進行糾正。

圖1　匹配方法流程

1.1SIFT 算法簡介

Lowe 在2004年總結前期工作的基礎上，提出一種通過構建影像尺度空間的方式尋找對尺度、旋轉(zhuǎn)、光照變換保持不變的興趣點，并利用梯度方向向量來對特征點進行描述，其步驟包括：尺度空間構建、特征點主方向確定、描述符生成及特征匹配4個步驟。根據(jù)SIFT原理，特征點表達為

式中：x為特征點坐標，σ為平滑尺度因子，θ為特征點主方向，d為SIFT特征描述符。在SIFT算法中，匹配測度是通過計算特征點描述符之間的最近次近歐氏距離比值，低于最近次近距離閾值ε即為匹配點。

1.2初始匹配點提取與特征相似點集構建

當影像中存在重復或者相似場景時，傳統(tǒng)SIFT匹配測度中閾值ε作用受到弱化，特征描述子之間的歐氏距離將出現(xiàn)以下情況：①真實同名點和相似特征點歐氏距離比值高于閾值ε；②相似特征得到的歐氏距離低于真實同名特征。其原因在于，SIFT特征描述子刻畫的是特征點所在局部區(qū)域影像梯度方向向量信息。當不同特征點所在局部影像場景存在重復或者相似問題時，描述子趨于一致。依據(jù)相似性場景在影像中紋理信息近似的特點，假定歐氏距離最近鄰中前n個特征點均可能成為潛在同名點，建立針對參考影像特征點對應的特征相似點集。

算法：

for (int i = 0；i < m；i++)

for(int k = 0；k < n；k++ )

{

if(di1/di2<ε)

(放入初始匹配點隊列)break;

else

(將k點加入i點的相似特征點集)

}

其中，m為參考影像特征點數(shù)量，n為點i對應的待匹配影像上最近距離特征點數(shù)量。

1.3匹配測度

1)隨機抽取3對匹配點，同時記錄匹配點對之間的相對尺度和相對主方向平均值。兩兩判斷相對尺度之差和相對主方向之差是否低于閾值h1，滿足條件直接進入步驟(2)，否則重新隨機抽取3對匹配點。

2)利用3對匹配點構建影像仿射變換模型，利用該模型求取參考影像上同名點在待匹配影像上的理論匹配點，當待匹配影像上理論匹配點與匹配點之間距離低于閾值h2時，保留該匹配點，否則該匹配點被剔除。

3)采用誤匹配點剔除模型對步驟(2)處理后剩余的匹配點進行誤差剔除，獲得最終初始匹配點集。

利用初始匹配點集統(tǒng)計匹配點之間的平均相對尺度δσ和平均相對主方向δθ，對參考影像特征點及待匹配影像上的相似特征點集進行約束匹配。

首先利用初始匹配點采用最小二乘方法建立幾何約束模型，通常遙感影像糾正模型包括透射模型、多項式模型，采用仿射變換模型作為幾何約束模型：

(1)

式中：(X,Y)為待匹配影像點坐標；(x,y)為參考影像點坐標；a1，a2，a3，b1，b2,b3為變換系數(shù)。

如圖2所示，利用式 (1) 計算的待匹配影像上理論匹配點，dr為約束窗口半徑，窗口內(nèi)黑點為對應在該窗口內(nèi)相似特征點，箭頭方向為特征點主方向。判斷點PTref與窗口內(nèi)相似特征點的相對主方向是否滿足式(2)，符合要求方可作為候選匹配點。

(2)

圖2　約束窗口

通過式(3)判斷點PTref與候選匹配點之間的相對尺度是否滿足條件，滿足條件候選匹配點可作為新同名點。

(3)

利用誤匹配點剔除模型對新獲取的同名點和初始同名點進行處理，得到最終的匹配點集。

1.4誤匹配點剔除模型

初始匹配過程中均需要剔除低精度匹配點。通常誤差剔除方法包括Data snooping方法和一致性檢查方法[11-13]。但有關文獻表明上述方法均受到初始匹配點分布影響，僅能剔除部分誤匹配點。而隨機抽樣一致性算法 (Random Sample Consensus，RANSAC)采用隨機抽樣的方法，通過一種從局部到整體的策略實現(xiàn)誤差的剔除[14]。該算法在樣本中存在 50%以上的誤匹配時，依然可以有效獲取正確的匹配。因此，論文選取RANSAC方法剔除誤匹配點。

2實驗及其結果分析

2.1實驗數(shù)據(jù)

選取不同類型含有較多相似性場景的影像像對進行實驗，包括近景數(shù)字影像、航天衛(wèi)星影像，同時像對間存在著尺度縮放、角度變形、影像模糊及視角變換等多種差異，以此來驗證算法的穩(wěn)健性。如圖3所示4組測試數(shù)據(jù)中每行影像中按照從左到右順序的第一幅為參考影像(即a1、b1、c1、d1)，第二幅為待匹配影像(即a2、b2、c2、d2)，相關數(shù)據(jù)描述見表1，由于所選取的影像類型不同，局部幾何變形各異，無法采用如仿射、多項式、單應矩陣等全局性幾何轉(zhuǎn)換模型對影像進行糾正和檢測匹配精度。在ENVI軟件中利用人工來對影像均勻選取20對測試點，然后基于同名點利用小面元微分法對影像糾正計算測試點坐標，最后按照式(4)來計算匹配精度。

(4)

表1　測試數(shù)據(jù)描述

2.2實驗結果與分析

如圖3所示，由于同名點數(shù)量較大，尤其是c組數(shù)據(jù)同名點超過1 000對，無法采用連線方式清晰顯示同名點結果，為了更好的顯示糾正結果，將待匹配影像糾正結果與參考影像進行疊加分析。如圖3所示，每行影像中按照從左到右順序的第三幅為待匹配影像糾正后與參考影像的疊加結果，從圖3中可以看到糾正影像與參考影像紋理吻合效果很好。

表2給出本文算法與經(jīng)典SIFT算法匹配方法的比較分析結果。其中，表中匹配點表示剔除粗差后剩余的正確匹配點。

1)由表2可以看到，相對于其他兩種方法，雖然在4組像對中本文方法計算速度居中，但對比同名點數(shù)量，本文算法具有明顯的優(yōu)勢。這說明當影像存在相似或重復場景時SIFT算法的匹配成功率低問題，本文算法能夠給予很好的解決。從影像匹配精度上來看，本文算法具有最高的精度。

圖3　各組數(shù)據(jù)的匹配結果

測試數(shù)據(jù)經(jīng)典SIFT算法曾丹等算法論文算法匹配點σ(x)/σ(y)時間/s匹配點σ(x)/σ(y)時間/s匹配點σ(x)/σ(y)時間/sa531.1/1.016.2541.0/0.922.581030.7/0.921.01b1340.7/0.67.741390.4/0.511.271450.5/0.49.61c10140.5/0.727.5549720.7/0.631.11313990.5/0.428.34d291.5/1.620.32501.3/1.126.6371131.0/1.122.04

2)在數(shù)據(jù)(a)組和數(shù)據(jù)(d)組可以看到，影像間均存在較大的尺度縮放和角度變形問題，尤其(a)組像對間存在接近于3倍尺度縮放。通過對3種算法的同名點數(shù)量與影像匹配精度對比分析表明，本文算法的匹配點數(shù)量是其他兩種算法的2倍，同時精度更高，表明本文算法能夠滿足較大尺度縮放和旋轉(zhuǎn)變換下的影像匹配問題的需求；而對像對間存在接近于135°角度變形的數(shù)據(jù)(d)組分析表明，當影像中存在相似性場景的梯田特征數(shù)量較大，采用梯度方向向量作為匹配測度的SIFT匹配方法數(shù)量明顯較低。而本文算法由于利用場景間的特征相似性建立相似點集，并通過特征幾何約束、相對主方向及尺度等多重約束，避免了特征向量之間的二次匹配，因而能夠提高算法匹配的速度，并較好解決了相似性場景的匹配問題。

3)針對模糊影像的匹配問題，本文選取了數(shù)據(jù)(b)組的數(shù)據(jù)來進行驗證分析。由于數(shù)據(jù)(b)組影像間存在模糊現(xiàn)象，使得不同特征場景紋理特征之間相似性加大，相異性降低，這為不同場景特征的獨特性描述帶來困難，從而降低SIFT算法匹配的成功率。本文算法和曾丹等算法在匹配數(shù)量和精度上相差不大，均比SIFT算法有所提高，而相對于曾丹等算法，本文算法的計算速度更高。

4)如圖3(c)所示，針對視角變化問題，本文選取的是紋理相似度極大且視角存在較大差異的墻面。本文算法的匹配成功率和精度均為最高，表明本文算法良好的匹配性能。

3結論

SIFT特征描述子作為一種局部描述子，當影像中存在相似性大或重復的場景時傳統(tǒng)匹配算法成功率低，而目前改進的SIFT匹配算法也存在計算量大的問題。有鑒于此，本文依據(jù)相似性場景的紋理特點，提出一種基于相似特征點集的SIFT匹配改進算法。當影像間存在相似性場景及不同幾何變形差異情況下，與其他算子的實驗比較表明，本文算法具有計算量小、匹配點數(shù)量大、匹配精度高的優(yōu)點。但由于在算法設計過程中需要人為分析設定一些參數(shù)，因此如何進一步改進算法實現(xiàn)參數(shù)的自動化設定將是未來研究的方向。

參考文獻：

[1]郭俊喜.多源高分辨率遙感影像自動匹配算法[J].測繪工程，2014,23(7)：17-21.

[2]王亞東,雷國華,安波,等.一種仿人足球機器人視覺系統(tǒng)環(huán)境特征獲取與識別方法[J].黑龍江工程學院學報(自然科學版),2013,27(2)：68-71.

[3]曾丹,史浩,張琦.多相似內(nèi)容圖像的特征匹配[J].計算機輔助設計與圖形學學報, 2011,23(10):1725-1733.

[4]袁修孝,李然.帶匹配支持度的多源遙感影像SIFT匹配方法[J].武漢大學學報(信息科學版),2012,37(12):1438-1442.

[5]史建東，耿利川，秦永志.基于BSIFT的無人機影像快速拼接算法[J].測繪與空間地理信息，2015，38(5)：124-127

[6]李鵬,武文波,王宗偉,基于非線性尺度空間的多源遙感影像匹配[J].測繪科學，2015，40(7)：41-45.

[7]戴激光,宋偉東,賈永紅,等.一種新的異源高分辨率光學衛(wèi)星遙感影像自動匹配算法[J].測繪學報,2013,42(1):80-86.

[8]康永輝,戴激光,宋偉東.異源高分辨率遙感影像的三維重建[J].測繪科學，2015，40(6)：156-161.

[9]WU B,ZHANG Y,ZHU Q.A triangulation-based hierarchical image matching method for wide-baseline images[J].Photogrammetric Engineering & Remote Sensing,2011,77(7)：695-708.

[10] 紀華，吳元昊，孫宏海，等.結合幾何全局信息的SIFT特征匹配算法[J].光學精密工程,2009,17(2):439-444.

[11] 王愷,陳世平,曾湧,一種遙感影像同名點密集匹配方法[J].測繪科學，2015，40(4)：141-146.

[12] 張登榮,蔡志剛,俞樂.基于匹配的遙感影像自動糾正方法研究[J].浙江大學學報(工學版),2007,41(3):402-406.

[13] 張海榮,劉燕華,孫久運.航空影像自動化鑲嵌及幾何糾正[J].測繪科學，2015，40(8)：72-76.

[14] 侯天怡,尤紅建,孫顯.以衛(wèi)星影像為底圖的無人機圖像自動拼接方法[J].測繪科學，2015，40(6)：11-16.

[責任編輯：李銘娜]

Improved sift matching algorithm based on similar feature point setGAO Fang,LU Pinpin,WANG Xu

(School of Geomatics,Liaoning Technical University,Fuxin 123000,China)

Abstract：Considering the low matching rate of traditional SIFT algorithm and large amount of calculation for the present improved SIFT matching method when similar or repeat scene existing in images,a new improved SIFT matching method is proposed based on similar feature point set in this paper.Firstly,initial matching points are extracted by threshold during traditional SIFT mateching method,at the same time the similar feature point set is built for the reference point feature which can not be matched.Secondly,geometrical constraint model is constructed by the initial homonymy points,which is used to build constraint window for reference point feature.Then the relative scale and main orientation of SIFT features are utilized to extract the homonymy points.At last,RANSAC is imbedded to eliminate mismatching points.Compared with other matching algorithms,the proposed algorithm has significant advantages in terms of successful matching rate and computational complexity.

Key words：SIFT(scale inveriant feature transform);similar feature point set;geometrical constraint;matching;initial homonymy point

中圖分類號：P216

文獻標識碼：A

文章編號：1006-7949(2016)06-0019-05

作者簡介：高放(1992-)，女，碩士研究生.

收稿日期：2015-01-15;修回日期：2015-08-29