郭全民，胡曉星

（西安工業(yè)大學電子信息工程學院，西安710021）

一種基于SIFT的三角網(wǎng)格圖像匹配方法

郭全民，胡曉星

（西安工業(yè)大學電子信息工程學院，西安710021）

針對影像對匹配過程中，由于場景復雜，干擾嚴重，導致錯誤匹配率較高的問題，提出一種在三角形約束下，基于SIFT（Scale Invariant Feature Transform）算法的圖像匹配策略。該方法大致分兩步進行，首先是粗匹配，使用SIFT算法和Harris選擇區(qū)別度較高的特征點，得到良好特征點集。第二步為細匹配，根據(jù)良好點集建立Delaunay同名三角網(wǎng)格，對同名三角形再次使用SIFT算法提取特征點進行匹配。實驗表明，提出的算法一定程度上提高了特征點復現(xiàn)率和匹配準確率。

SIFT特征；Harris特征；自適應非最大抑制；Delaunay三角形；特征提取；特征匹配

1 引 言

長期以來制約數(shù)字攝影測量與計算機視覺自動化及可靠性的一個關(guān)鍵問題就是立體影像對的匹配，即在立體影像對的重疊區(qū)域內(nèi)以影像匹配代替（或模擬）人眼立體觀察自動尋找同名像點的過程。然而，面對千變?nèi)f化的影像，現(xiàn)有的影像匹配方法仍然存在許多問題，尤其是在植被茂密、建筑物密集和水域等區(qū)域影像匹配的可靠性還不高，建筑物角點和一些地物的主要邊界點還不能被自動地匹配出來，自動產(chǎn)生的數(shù)字表面模型存在著許多異常值，需要進行大量的人工編輯處理。

匹配難度大的部分原因是圖像缺失或者噪聲使匹配成為一個病態(tài)問題。通常，利用先驗知識也就是運用附加的假設(shè)或約束將影像匹配從一個“病態(tài)”問題轉(zhuǎn)化為“良性”問題。如對極幾何約束等，通過構(gòu)建優(yōu)化函數(shù)，優(yōu)化匹配質(zhì)量。近幾年針對SIFT的特征匹配策略改進涌現(xiàn)出很多創(chuàng)新。其中，文獻［1］結(jié)合SURF算法和Delaunay三角網(wǎng)來提高匹配正確率。文獻［2］提出了一種基于圓形區(qū)域和Harris角點檢測的圖像配準算法，充分利用圓形區(qū)域的旋轉(zhuǎn)不變性和互信息量最大原則進行特征點匹配。文獻［3］提出一種基于良好匹配點三角形局部連續(xù)性約束下的影像匹配方法，該方法使用改進的Harris算法提取特征點，并且使用核線約束和灰度相關(guān)約束得到可靠性高的同名點。文獻［4］提出了結(jié)合區(qū)域分割的SIFT方法，將圖像分成邊緣集中區(qū)域和非集中區(qū)域，設(shè)置一塊或者幾塊ROI區(qū)域作為SIFT特征提取的對象。

David Lowe于2009年提出SIFT算法［5］（Scale Invariant Feature Transformation），提取出的特征點具有尺度，旋轉(zhuǎn)，平移和縮放不變性，并對仿射和廣光照變化具有一定的不變性。是一種魯棒性較強的特征提取算法。文中提出了一種基于SIFT算法的匹配策略，利用良好匹配點三角形局部連續(xù)性約束進行匹配來提高匹配正確率。

2 基于三角形約束的影像匹配原理

算法流程如圖1所示，詳細介紹如下：

（1）利用SIFT算法提取特征點。先使用SIFT算法提取特征點，在較高的匹配閾值下（實驗中一般為0.4）選取差異性大正確率高的特征點。

（2）利用Harris算法篩選穩(wěn)定的特征點。文獻［6］提出，由于與基于自相關(guān)性的檢測器不同，雖然SIFT算法在實際應用中效果較好，但是其特征點提取理論并不是基于最大化空間穩(wěn)定性。所以，文中使用Harris算法［7］過濾出角點響應強度較高的穩(wěn)定點集。

圖1 基于SIFT的Delaunay三角網(wǎng)格匹配方法

（3）應用自適應非最大抑制（ANMS）使特征點分布平均化。

由于特征點檢測器僅尋找興趣函數(shù)的局部最大值，得到的匹配點通常分布不均勻，在紋理豐富的區(qū)域密集，而缺少紋理的區(qū)域以及視差不連續(xù)的區(qū)域密度較小，甚至沒有，導致不能構(gòu)建面積大小合適的三角形區(qū)域。文中使用自適應非最大抑制（ANMS）［8］算法去除部分密集處的特征點，得到分布較均勻的良好點集合。

這時得到的匹配點對仍存在少許錯匹配，實驗中為圖像對匹配連線的長度和傾斜角度分別設(shè)置一個閾值，去除部分明顯的錯誤匹配。

在每幅影像上自動提取出數(shù)以百計的備選匹配特征點，經(jīng)過嚴格的粗檢測和剔除，那些剩下的特征點被認為是最初始的良好點（紋理特征明顯、匹配正確、分布均勻），因此可以作為后續(xù)密集匹配的可靠先驗知識。

（4）生成Delaunay同名三角形對

假設(shè)經(jīng)過篩選后剩余的點均是初始良好點，也就是種子點中不存在錯誤匹配。提出的算法采用Delaunay三角形法則在立體像對上構(gòu)建同名三角網(wǎng)。將第一幅建立Delaunay三角形網(wǎng)格的影像稱為主圖，待匹配的圖稱為輔圖，也就是根據(jù)主圖中Delaunay三角網(wǎng)格中特征點的順序，建立三角網(wǎng)格，并以輔圖中同名點的順序在輔圖中插入三角網(wǎng)格，最后得到同名三角形對。

（5）再次使用SIFT算法進行細致匹配

在三角網(wǎng)格的約束下，對同名三角形對區(qū)域內(nèi)的圖像進行特征提取并匹配。需要注意的是，文中選擇NNDR（最近鄰距離比率）作為匹配策略，即通過比較最近鄰和次近鄰距離，確定匹配點對。經(jīng)過多次實驗，初始匹配的閾值為0.4，細致匹配的閾值為0.6，當圖像失真嚴重程度增加時，如仿射變化較大，通過增加初始匹配和細匹配的閾值，會降低特征點質(zhì)量，提高匹配對數(shù)量，反之，則提高特征點質(zhì)量，降低匹配點對數(shù)量。

（6）匹配效果評價標準

特征匹配時，使用次近鄰準則進行匹配。匹配的閾值即NNDR（最近距離比值）的高低直接影響匹配的數(shù)量和質(zhì)量。提出的算法使用下面的定義來計算正確和錯誤匹配以及匹配失敗的數(shù)目。提出的算法使用PPV（肯定預測值），將得到的實驗結(jié)果轉(zhuǎn)化為單位比率。

其中，TP（正確肯定）為正確匹配的數(shù)目，F(xiàn)P（誤報）為給出的匹配中不正確的數(shù)量。TP與FP的和等于實際肯定的數(shù)目，理想情況下，準確率PPV應該接近于1。

同時提出的算法使用復現(xiàn)率來衡量匹配結(jié)果的好壞。若在兩幅圖像中檢測到的特征點個數(shù)分別為n1和n2，而在兩幅圖中均檢測到的特征點個數(shù)也就是匹配對為n3，那么復現(xiàn)率定義為：

檢測到的特征點復現(xiàn)率越高，則說明檢測的性能越穩(wěn)定，對匹配也就越有利。

3 實驗結(jié)果與分析

為驗證提出的算法可靠性、效率與精確度，采用CPU主頻2.5GHz，RAM 2G，Windows 7系統(tǒng)，MATLAB 2009a開發(fā)平臺實現(xiàn)上述討論的影像匹配算法，使用牛津大學仿射協(xié)變標準圖像集進行實驗。這個數(shù)據(jù)集共有8個子集，包含5種圖像變換：視點變化，尺度變化，圖像模糊，JPEG壓縮，光照變化。每個子集有6張圖片，拍攝的是同一場景的不同情況，文中選取其中六個子集進行驗證。

圖2顯示了對Wall圖片集進行三角網(wǎng)格化，Wall子集含有透視失真和許多重復結(jié)構(gòu)，屬于圖像集中最難匹配的例子。由圖可知，一定的視角變換下，噪聲點或特征點有丟失會使Delaunay三角網(wǎng)局部發(fā)生改變，但總體結(jié)構(gòu)變化不大，而超過一定的仿射變換程度，得到的網(wǎng)格難以代表圖像紋理和結(jié)構(gòu)信息。

圖2 對wall圖片集進行Delaunay三角網(wǎng)格化

圖3中下方兩條線為SIFT（NNDR）方法的匹配效果和基于SIFT（NNDR）的改進匹配算法的復現(xiàn)率對比。中、下曲線分別對應其改進的算法和基于SIFT（NNDR）的復線率，反映了使用NNDR作為匹配準則的SIFT匹配結(jié)果和使用提出的匹配策略且NNDR作為匹配準則時的SIFT匹配效果對比，最上面的曲線為其改進算法的匹配準確度。每組圖包含了對應子集的實驗結(jié)果。下圖中橫坐標表示每一個測試子集中參考圖像（失真度最輕）與其他5幅圖像的效果對比，隨著橫坐標的增大，比對圖像的失真程度越大?？v坐標包含SIFT使用NNDR算法匹配和提出的基于三角形網(wǎng)格的SIFT匹配算法的復現(xiàn)率對比，以及匹配算法改進后的匹配準確率。

圖3（a）是視角變換和透視失真時的復現(xiàn)率和提出的改進算法準確率，圖3（b）是重復紋理加透視失真下的復現(xiàn)率和改進算法準確率，圖3（c）是亮度變化時復現(xiàn)率對比和改進算法準確率?？梢钥闯鰓all和（a）圖像集中，隨著視角變化程度加大，改進算法的匹配準確率出現(xiàn)急劇惡化。然而，通過改變參數(shù)，提高初始特征點的數(shù)量，可以間接地提高匹配準確度。圖3（d）是JPEG人工壓縮變換下的復現(xiàn)率對比和改進算法準確率，圖3（e）是旋轉(zhuǎn)、尺度變化時的復現(xiàn)率對比和改進算法準確率，圖3（f）是圖像模糊和平移時的復現(xiàn)率對比和改進算法準確率?？梢钥闯?，在圖3（d）、（e）、（f）中，均保持較高的匹配準確率。在每個子集中，用第一張圖片與其余圖像進行匹配，隨著圖像失真程度的加大，匹配任務難度增加，復現(xiàn)率和準確率都呈下降趨勢。除了wall和（a）圖像集，提出的方法均保持了較高的正確匹配率，且對于平移變換、尺度變化、旋轉(zhuǎn)、亮度變化、模糊度變化等失真表現(xiàn)良好。

根據(jù)實驗結(jié)果可以得到以下結(jié)論：

（1）由于采用了局部連續(xù)性約束方法，同名點的搜索區(qū)域顯著縮小，基于三角網(wǎng)約束的匹配方法有效改善了特征的誤匹配問題；

（2）大部分建筑物角點能夠直接被匹配出來，從而提高了數(shù)字表面模型的可靠性和信息完整性；

（3）匹配點的生成遵循了紋理特征由顯著到不顯著的順序，實現(xiàn)了與紋理自適應的、由粗略到細致的多級匹配，有利于提高重復紋理的匹配率；

（4）由于SIFT算法對仿射只具有一定程度的不變性，且初始良好點對匹配效果起主導作用，所以當視角變化較大時，無法得到足夠的高初始良好點，導致后續(xù)的三角網(wǎng)格化效果急劇惡化。

圖3 SIFT（NNDR）和其改進算法的復現(xiàn)率對比以及其改進算法的匹配準確度

4 結(jié)束語

針對大場景圖像對特征匹配錯誤率較高的問題，文中提出了一種基于SIFT算法的匹配方法。該方法限制了點對的位置，舍棄了對圖像變換敏感的點對間幾何相關(guān)性實現(xiàn)降低匹配搜索空間的縮小。實驗結(jié)果表明，該方法不僅對平移、縮放、旋轉(zhuǎn)和一定程度的仿射等圖像變換具有魯棒性，還提高了匹配的正確率和特征點的復現(xiàn)率。

［1］ Yan ZiGeng，JIANG JianGuo，GUO Dan.Image matching based on SURF feature and delaunay triangular meshes［J］.Acta Automatica Sinica，2014，40（6）：1216－1222.

［2］ 劉貴喜，王蕾.基于區(qū)域選擇和特征點匹配的圖像配準算法［J］.光電子激光，2007，18（8）：999－1002.

LIU GuiXi，WANG Lei.An image registration method based on region selecting and feature points matching［J］.Journal of Optoelectronics Laser，2007，18（8）：999－1002.

［3］ 張云生.自適應三角形約束的多基元多視影像匹配方法［D］.武漢：武漢大學，2011.

Zhang Yunsheng.A multi－primitive and multi－view imagematching method based on self－adaptive triangle constraint［D］.Wuhan：Wuhan University，2011.

［4］ 丘文濤，趙建，劉杰.結(jié)合區(qū)域分割的SIFT圖像匹配方法［J］.液晶與顯示，2012，27（6）：827－831.

QIU Wen－tao，ZHAO Jian，LIU Jie.Image matching algrithm combining SIFT with region segmentation［J］.Chinese Journal of Crystals and Displays，2012，06：827－831.

［5］ Lowe D G.Distinctive image features frome scale－invariant keypoints［J］.International Journal of Computer vision，2004，6（2）：91－110.

［6］ Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2003，27（10）：1615－1630.

［7］ Harris C，Stephens M.A combined corner and edge detector［J］.In Proc.of Fourth Alvey Vision Conference，1988：147－151.

［8］ Brown M，Szeliski R，Winder S.Multi－image matching usingmulti－scale oriented patches［J］.Computer Vision and Pattern Recognition，Cvpr，IEEE Computer Society Conference on，2005，1：510－517.

A SIFT－based Trianglation Network Method for Image Matching

Guo Quanmin，Hu Xiaoxing
（School of Electronics and Information Engineer，Xi’an Technology University，Xi’an 710021，China）

Aiming at decreasing the high falsematching rate caused by scene complexity and serious disturbance lying in images matching，a method based on triangle constraint is proposed.It is a novel imagematching strategy based on SIFT（Scale Invariant Feature Transform）algorithm and uses the information of image structure.Themethod is separated into two steps.The first step is rough matching and good feature point is selected by applying SIFT and Harris algorithm to acquire distinctive feature point.The second step is elaboration matching，and the corresponding Delaunay triangulation network is established based on good feature points，and then SIFT is performed again to select feature points.Itwas verified that themethod improved the repetition and accuracy of featurematching.

SIFT Feature；Harris Feature；ANMS（Adaptive Non－Maximal Suppression）；Delaunay triangle；Feature extraction；Featurematching

10.3969/j.issn.1002－2279.2015.05.011

TP391

A

1002－2279（2015）05－0043－04

郭全民（1974－），男，陜西省渭南市人，副教授，主研方向：計算機測控技術(shù)。

胡曉星（1987－），女，河南新鄉(xiāng)人，工程碩士，主研方向：圖形圖像處理。

2015－03－10