多重提純算法約束的圖像特征點匹配

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

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

多重提純算法約束的圖像特征點匹配

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

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

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

比率；對稱性；隨機采樣一致性；極線約束；特征點匹配

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

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

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

1 特征點匹配方法及步驟

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

1.1 比值提純法

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

1.2 對稱性提純法

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

1.3 一致性提純法

RANSAC算法是計算機視覺領域中應用最廣的穩健估計方法，屬于假設?驗證估計方法，在運動姿態估計、基礎矩陣估計、特征匹配等方面應用廣泛。它通過極線約束法來移除不滿足極線約束的匹配點對，不僅能有效剔除錯誤匹配，還能計算出基礎矩陣。

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

圖1 算法流程圖

2 實驗結果

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

圖2 多重提純算法約束的特征點匹配結果

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

表1 匹配實驗結果統計表

3 結 語

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

[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].北京∶國防工業出版社,2010

[4] Richard Szeliski.計算機視覺：算法與應用[M].艾海舟,譯.北京∶清華大學出版社,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.計算機視覺中的多視圖幾何[M].韋穗, 楊尚駿,譯.合肥∶安徽大學出版社,2002

圖1 靜態最佳路徑圖

圖2 動態最佳路徑圖

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

參考文獻

[1] 李發文.洪災避遷決策理論及其應用研究[D].南京∶河海大學,2005

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

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

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

[5] 魏一鳴,金菊良,楊存建,等.洪水災害風險管理理論[M].北京∶科學出版社,2002

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

[7] 于德新.車輛誘導系統理論模型和關鍵技術研究[D].長春∶吉林大學交通學院,2006

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

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

P23

B

1672-4623（2016）05-0078-03

10.3969/j.issn.1672-4623.2016.05.025

熊威，主要從事基于水準及GPS數據的地殼形變研究。

2015-07-08。

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