高　放，陸頻頻，王　旭

(遼寧工程技術(shù)大學(xué) 測(cè)繪與地理科學(xué)學(xué)院,遼寧 阜新 123000)

?

基于相似特征點(diǎn)集的SIFT匹配改進(jìn)算法

高放，陸頻頻，王旭

(遼寧工程技術(shù)大學(xué) 測(cè)繪與地理科學(xué)學(xué)院,遼寧 阜新 123000)

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

關(guān)鍵詞：SIFT;相似特征點(diǎn)集;幾何約束;匹配;初始同名點(diǎn)

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

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

1算法

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

圖1　匹配方法流程

1.1SIFT 算法簡(jiǎn)介

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

式中：x為特征點(diǎn)坐標(biāo)，σ為平滑尺度因子，θ為特征點(diǎn)主方向，d為SIFT特征描述符。在SIFT算法中，匹配測(cè)度是通過(guò)計(jì)算特征點(diǎn)描述符之間的最近次近歐氏距離比值，低于最近次近距離閾值ε即為匹配點(diǎn)。

1.2初始匹配點(diǎn)提取與特征相似點(diǎn)集構(gòu)建

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

算法：

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

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

{

if(di1/di2<ε)

(放入初始匹配點(diǎn)隊(duì)列)break;

else

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

}

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

1.3匹配測(cè)度

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

2)利用3對(duì)匹配點(diǎn)構(gòu)建影像仿射變換模型，利用該模型求取參考影像上同名點(diǎn)在待匹配影像上的理論匹配點(diǎn)，當(dāng)待匹配影像上理論匹配點(diǎn)與匹配點(diǎn)之間距離低于閾值h2時(shí)，保留該匹配點(diǎn)，否則該匹配點(diǎn)被剔除。

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

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

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

(1)

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

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

(2)

圖2　約束窗口

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

(3)

利用誤匹配點(diǎn)剔除模型對(duì)新獲取的同名點(diǎn)和初始同名點(diǎn)進(jìn)行處理，得到最終的匹配點(diǎn)集。

1.4誤匹配點(diǎn)剔除模型

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

2實(shí)驗(yàn)及其結(jié)果分析

2.1實(shí)驗(yàn)數(shù)據(jù)

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

(4)

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

2.2實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

3結(jié)論

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

參考文獻(xiàn)：

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

[2]王亞?wèn)|,雷國(guó)華,安波,等.一種仿人足球機(jī)器人視覺(jué)系統(tǒng)環(huán)境特征獲取與識(shí)別方法[J].黑龍江工程學(xué)院學(xué)報(bào)(自然科學(xué)版),2013,27(2)：68-71.

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

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

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

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

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

[8]康永輝,戴激光,宋偉東.異源高分辨率遙感影像的三維重建[J].測(cè)繪科學(xué)，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] 紀(jì)華，吳元昊，孫宏海，等.結(jié)合幾何全局信息的SIFT特征匹配算法[J].光學(xué)精密工程,2009,17(2):439-444.

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

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

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

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

[責(zé)任編輯：李銘娜]

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

中圖分類號(hào)：P216

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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