多重提純算法約束的圖像特征點(diǎn)匹配

熊 威，段云龍，潘 彤，李春雷

（1.中國地震局 第一監(jiān)測中心，天津 300180；2.中國電子科技集團(tuán)公司 第二十七研究所，河南 鄭州450047；3.天津市勘察院，天津 300000；4.海洋石油工程（青島）股份有限公司，山東 青島 266520）

多重提純算法約束的圖像特征點(diǎn)匹配

熊 威1，段云龍2，潘 彤3，李春雷4

（1.中國地震局 第一監(jiān)測中心，天津 300180；2.中國電子科技集團(tuán)公司 第二十七研究所，河南 鄭州450047；3.天津市勘察院，天津 300000；4.海洋石油工程（青島）股份有限公司，山東 青島 266520）

針對特征點(diǎn)匹配準(zhǔn)確度和效率不高的問題，提出了一種多重提純算法約束下的特征點(diǎn)匹配方法。采用影像的SURF特征點(diǎn)作為匹配基元，利用比率、對稱性和基于極線約束的隨機(jī)采樣一致性3種算法進(jìn)行圖像特征點(diǎn)提純和匹配。實驗表明，該方法能夠消除大多數(shù)的錯誤匹配，彌補(bǔ)了單一匹配算法的不足，具有較高的準(zhǔn)確性和效率。

比率；對稱性；隨機(jī)采樣一致性；極線約束；特征點(diǎn)匹配

特征點(diǎn)匹配問題可歸結(jié)為在2個點(diǎn)集中求解對應(yīng)關(guān)系，建立點(diǎn)對間匹配關(guān)系的問題。匹配的結(jié)果直接決定圖像拼接和三維重建效果的好壞。一般來說特征點(diǎn)匹配可分為3步：特征提取，利用一組參數(shù)對特征作描述，利用一定的匹配算法進(jìn)行特征點(diǎn)匹配并提純。

由于成像環(huán)境的復(fù)雜性，一個穩(wěn)定且可靠的匹配算法需要具備以下特性：①特征提取算子除了要具有準(zhǔn)確性、魯棒性還要具有光照、尺度、旋轉(zhuǎn)等不變性；②匹配算法要具有高效性和準(zhǔn)確性。鑒于此，在特征點(diǎn)匹配領(lǐng)域，前人提出了很多特征提取算子和匹配算法。目前，在特征算子的設(shè)計方面綜合性能最優(yōu)的當(dāng)屬SIFT[1]算子和SURF[2]算子。匹配算法的設(shè)計主要分2類：線性掃描法和先建立數(shù)據(jù)索引，再進(jìn)行快速匹配。由于實際數(shù)據(jù)一般都會呈現(xiàn)簇狀的聚類形態(tài)，通過設(shè)計有效的索引結(jié)構(gòu)可大大加速檢索速度。常用的索引結(jié)構(gòu)主要分為樹結(jié)構(gòu)索引和非樹結(jié)構(gòu)索引[3-4]。樹結(jié)構(gòu)索引主要有Kd?樹[5]和R?樹[6]；非樹結(jié)構(gòu)索引主要有Hash法和空間填充曲線法等[7]。窮盡搜索算法屬于線性掃描法，是最簡單的一種遍歷式搜索匹配算法，在特征點(diǎn)集規(guī)模不大時其效率更高。文獻(xiàn)[1]提出了基于最優(yōu)節(jié)點(diǎn)優(yōu)先 （BBF）的查詢機(jī)制的改進(jìn)Kd? 樹最近鄰查詢算法（NN）。但是BBF是以精度為代價獲得快速數(shù)據(jù)查詢的，屬于近似匹配，并非最佳的查詢算法。文獻(xiàn)[8]提出了改進(jìn)的Spill?樹算法，該算法中鄰域會隨查詢點(diǎn)的移動而自動被包含在它所處的節(jié)點(diǎn)一側(cè)，極具搜索效率。文獻(xiàn)[9]比較了多種匹配算法，并提出在層次性的K?均值樹中進(jìn)行優(yōu)化搜索，總結(jié)得出多個隨機(jī)Kd?樹取得的性能最好。經(jīng)過匹配算法得到的初始匹配經(jīng)常會包含一定數(shù)量的錯誤匹配點(diǎn)對，而求解高精度的變換參數(shù)需要精確的匹配點(diǎn)對。因此，在獲得初始匹配點(diǎn)對后需要加入若干約束關(guān)系用于剔除錯誤的匹配點(diǎn)對。在局部特征點(diǎn)匹配研究領(lǐng)域中，用于提純的約束關(guān)系有多種，其中相對簡單且常用的主要有比值法、對稱性法、透視變換法、極線約束法和三維模型法等。在模型估計中常見的魯棒算法主要有最小中值法（L-MedS）[10]、M估計法[11]、MLESAC法[12]和隨機(jī)采樣一致性（RANSAC）法[13]等。

本文在眾多學(xué)者研究的基礎(chǔ)上，提出了一種采用比率、對稱性和RANSAC三種提純算法約束的特征點(diǎn)提純和匹配方法，在RANSAC提純算法中使用的約束模型是極線幾何[14]。該方法能夠獲得兩幅圖像之間的特征點(diǎn)對優(yōu)質(zhì)匹配集合。

1 特征點(diǎn)匹配方法及步驟

多重提純算法約束的特征點(diǎn)匹配的主要思想是首先提取影像對的SURF特征算子生成特征描述符；然后采用最近鄰算法k-NN進(jìn)行匹配，同時采用基于Kd?樹搜索算法的BBF搜索算法對最近鄰進(jìn)行搜索，以此來提高匹配效率；再利用比率、對稱性和基于極線幾何的RANSAC三種約束關(guān)系消除不正確的匹配點(diǎn)對，生成用于圖像間變換計算的同名特征點(diǎn)對集合。

1.1 比值提純法

對于每一個特征點(diǎn)，在另一個視角中搜索出的兩個最近的特征點(diǎn)，如果對于最優(yōu)特征點(diǎn)的度量距離非常小，而對于次優(yōu)特征點(diǎn)度量距離非常大，則可以完全地接受最優(yōu)特征點(diǎn)為最匹配的特征點(diǎn)；反之，如果兩個候選特征點(diǎn)非常接近，那么選擇其中之一可能出錯，因此這兩個候選特征點(diǎn)都會被拒絕。具體做法為：兩幅圖像的SURF特征描述符都產(chǎn)生后，令圖像a中的特征點(diǎn)為基準(zhǔn)集{pi}，i=1，2，…，n，圖像b中的特征點(diǎn)目標(biāo)集{qj}，j=1，2，…，m。在進(jìn)行特征匹配時，對于圖像a中的每個特征點(diǎn)pi在圖像b中都搜尋兩個最近的特征點(diǎn)：最近特征點(diǎn)qm和次近特征點(diǎn)qn。如果特征點(diǎn)pi與最近特征點(diǎn)qm和次近特征點(diǎn)qn之間的距離的比值小于給定的閾值，則接受特征點(diǎn)qm為最匹配特征點(diǎn)；否則，拒絕接受這兩個特征點(diǎn)為最匹配特征點(diǎn)并將其移除。同樣，對于圖像b中的每個特征點(diǎn)qj重復(fù)以上操作。本文實驗中設(shè)置的比值閾值為0.65。

1.2 對稱性提純法

通過比值提純，同時獲得兩個相對優(yōu)質(zhì)的匹配集，一個來自圖像a到圖像b，另一個來自圖像b到圖像a。但還有一定數(shù)量的錯誤匹配通過了測試，因此設(shè)計了對稱性匹配提純（雙向匹配提純）。該方法提取同時滿足兩個匹配集的特征點(diǎn)對，這些特征點(diǎn)對必須是各自的最優(yōu)匹配特征點(diǎn)，即對于圖像a中的某個特征點(diǎn)pi，在匹配集a中搜索出其在圖像b中的匹配特征點(diǎn)qj，同時判斷qj在匹配集b中的匹配特征點(diǎn)是否為圖像a中的特征點(diǎn)pi；如果是，則這一匹配點(diǎn)對通過對稱性提純，視為匹配點(diǎn)對，否則不是匹配點(diǎn)對。

1.3 一致性提純法

RANSAC算法是計算機(jī)視覺領(lǐng)域中應(yīng)用最廣的穩(wěn)健估計方法，屬于假設(shè)?驗證估計方法，在運(yùn)動姿態(tài)估計、基礎(chǔ)矩陣估計、特征匹配等方面應(yīng)用廣泛。它通過極線約束法來移除不滿足極線約束的匹配點(diǎn)對，不僅能有效剔除錯誤匹配，還能計算出基礎(chǔ)矩陣。

在RANSAC算法中，需要確定距離閾值和置信概率；距離閾值用來判定內(nèi)外點(diǎn)，置信概率決定隨機(jī)采樣的次數(shù)。本文中，距離閾值設(shè)為1，置信概率設(shè)為0.98，流程見圖1。

圖1 算法流程圖

2 實驗結(jié)果

本文在普通的PC機(jī)上實現(xiàn)了多重提純算法約束的特征點(diǎn)匹配。實驗平臺配置為：Windows XP SP3操作系統(tǒng)，Intel Core 2 Quad Q6600@2.40GHz處理器，2 GB內(nèi)存，ATI Radeon HD 2400 PRO顯卡，Visual C++2010開發(fā)環(huán)境。兩幅圖像的尺寸均為640像素×480 像素。匹配實驗結(jié)果如圖2所示。

圖2 多重提純算法約束的特征點(diǎn)匹配結(jié)果

用SURF算子分別對原圖像進(jìn)行特征檢測與描述，檢測出的特征如圖2c、圖2d所示，兩幅圖分別提取出3 229個和3 710個特征點(diǎn)。圖2e、圖2f是分別經(jīng)過最近鄰搜索算法初始匹配后再通過比值提純的結(jié)果，兩幅圖通過比值測試的點(diǎn)對分別為380個和376 個，大量不符合條件的匹配被剔除。圖2g和圖2h是分別經(jīng)過對稱性提純后的結(jié)果，兩幅圖共同通過對稱性測試的點(diǎn)對為289個。最后利用基于極線約束模型的RANSAC算法剔除錯誤匹配點(diǎn)對后得到234對正確匹配的特征點(diǎn)，如圖2i～圖2k所示。錯誤的匹配點(diǎn)對基本已被剔除，實現(xiàn)了特征點(diǎn)對的正確匹配。匹配實驗的統(tǒng)計信息如表1所示。

表1 匹配實驗結(jié)果統(tǒng)計表

3 結(jié) 語

本文在圖像特征點(diǎn)匹配過程中加入了3種提純算法，即比值提純法、對稱性提純法和基于極線約束的RANSAC算法。實驗結(jié)果表明，采用多重提純策略的特征點(diǎn)匹配可極大剔除錯誤的匹配點(diǎn)對，彌補(bǔ)了單一匹配算法的不足，提高了匹配可信度。該算法對圖像配準(zhǔn)、攝影測量和立體視覺等具有較大實用意義。

[1] David G Lowe. Distinctive Image Features from Scaleinvariant Key Points[J]. International Journal of Computer Vision,2004,60(2)∶91-110

[2] Herbert Bay, Andreas Ess, Tinne Tuytelaars, et al. Speeded-up Robust Features (SURF)[J].Computer Vision and Image Understanding, 2008,110(3)∶346-358

[3] 王永明,王貴錦.圖像局部不變特征與描述[M].北京∶國防工業(yè)出版社,2010

[4] Richard Szeliski.計算機(jī)視覺：算法與應(yīng)用[M].艾海舟,譯.北京∶清華大學(xué)出版社,2012

[5] Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communication of the ACM,1975,18(9)∶509-517

[6] Guttman A. R-trees∶ a Dynamic Index Structure for Spatial Searching[EB/OL]. http∶//pages.cs.wisc.edu/～nil/764/Relat/7_ rtree.pdf, 2014/2015-06-25

[7] Gaede V, Gunther O. Multidimensional Access Methods[J]. ACM Computer Surveys,1998,30(2)∶170-231

[8] LIU T, Moore A. An Investigation of Practial Approximate Nearest Neighbor Algorithms[EB/OL]. http∶//www.cs.cmu. edu/～tingliu/my_papers/nips04.pdf, 2014/2015-06-27

[9] M Muja, Lowe D G. Fast Approximate Nearest Neighbors with Automatic Algorithms Configuration[EB/OL].http∶//citeseerx. ist.psu.edu/viewdoc/summary?doi=10.1.1.160.1721&rank=1,20 14/2015-06-22

[10] ZHANG Zhengyou, Rachid Deriche, Oliver Faugeras, et al. A Robust Technique for Matching Two Uncalibrated Image through the Recovery of the Unknown Epipolar Geometry[J]. Artificial Intelligence,1995,28(1/2)∶87-119

[11] Huber P J. Robust Statistics[M]. New York∶ John Wiley,1981

[12] Torr P H S, Zisserman A.MELSAC∶ a New Robust Estimator with Application to Estimating Image Geometry[J]. Computer Vision and Image Understanding,2000(1)∶138-156

[13] Fischler M A, Bolles R C. Random Sample Consensus∶ a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communication Association Machine,1981,24(6)∶381-395

[14] Hartley R, Zisserman A.計算機(jī)視覺中的多視圖幾何[M].韋穗, 楊尚駿,譯.合肥∶安徽大學(xué)出版社,2002

圖1 靜態(tài)最佳路徑圖

圖2 動態(tài)最佳路徑圖

3）通過比較圖1、2可以得出，從陶寓村到新西社區(qū)的靜態(tài)和動態(tài)最佳路徑差別較大，靜態(tài)最佳路徑所走路程為15 647.1 m，花費(fèi)時間為59.7 min；而動態(tài)最佳路徑所走路程為17 713.1 m，花費(fèi)時間為21.9 min。靜態(tài)最佳路徑所走路程少，但耗時較多，相反動態(tài)最佳路徑所花時間較少，這與區(qū)域的道路等級和交通狀況等有著密切的關(guān)系。在實際轉(zhuǎn)移工程中，可以根據(jù)實際情況選擇不同的交通工具和選擇不同的路徑。

參考文獻(xiàn)

[1] 李發(fā)文.洪災(zāi)避遷決策理論及其應(yīng)用研究[D].南京∶河海大學(xué),2005

[2] 劉家福,梁雨華.基于信息擴(kuò)散理論的洪水災(zāi)害風(fēng)險分析[J].吉林師范大學(xué)學(xué)報(自然科學(xué)版),2009(3)∶78-80

[3] 劉碩,賈艾晨.洪災(zāi)中避難路線的選擇研究[J].水利與建筑工程學(xué)報,2008,6(4)∶132-134

[4] 李超杰,宮輝力,李小娟.洪災(zāi)避難遷移模型研究與應(yīng)用[J].地理空間信息,2007,5(2)∶39-42

[5] 魏一鳴,金菊良,楊存建,等.洪水災(zāi)害風(fēng)險管理理論[M].北京∶科學(xué)出版社,2002

[6] 侯燕,賈艾晨.基于ArcGIS的洪災(zāi)避難方案選擇研究[J].水電能源科學(xué),2010,28(9)∶106-109

[7] 于德新.車輛誘導(dǎo)系統(tǒng)理論模型和關(guān)鍵技術(shù)研究[D].長春∶吉林大學(xué)交通學(xué)院,2006

[8] 張郭燕.地鐵施工對城市道路服務(wù)水平的影響[D].西安∶長安大學(xué),2008

第一作者簡介：于大超，碩士，研究方向為空間信息分析與應(yīng)用。

P23

B

1672-4623（2016）05-0078-03

10.3969/j.issn.1672-4623.2016.05.025

熊威，主要從事基于水準(zhǔn)及GPS數(shù)據(jù)的地殼形變研究。

2015-07-08。

項目來源：一測中心科技創(chuàng)新主任基金資助項目（FMC2014010）；中國綜合地球物理場觀測資助項目（201208009）。