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

郭全民，胡曉星

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

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

郭全民，胡曉星

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

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

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

1 引 言

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

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

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

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

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

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

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

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

（3）應(yīng)用自適應(yīng)非最大抑制（ANMS）使特征點(diǎn)分布平均化。

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

這時(shí)得到的匹配點(diǎn)對(duì)仍存在少許錯(cuò)匹配，實(shí)驗(yàn)中為圖像對(duì)匹配連線的長(zhǎng)度和傾斜角度分別設(shè)置一個(gè)閾值，去除部分明顯的錯(cuò)誤匹配。

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

（4）生成Delaunay同名三角形對(duì)

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

（5）再次使用SIFT算法進(jìn)行細(xì)致匹配

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

（6）匹配效果評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

檢測(cè)到的特征點(diǎn)復(fù)現(xiàn)率越高，則說(shuō)明檢測(cè)的性能越穩(wěn)定，對(duì)匹配也就越有利。

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

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

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

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

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

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

根據(jù)實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論：

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

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

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

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

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

4 結(jié)束語(yǔ)

針對(duì)大場(chǎng)景圖像對(duì)特征匹配錯(cuò)誤率較高的問(wèn)題，文中提出了一種基于SIFT算法的匹配方法。該方法限制了點(diǎn)對(duì)的位置，舍棄了對(duì)圖像變換敏感的點(diǎn)對(duì)間幾何相關(guān)性實(shí)現(xiàn)降低匹配搜索空間的縮小。實(shí)驗(yàn)結(jié)果表明，該方法不僅對(duì)平移、縮放、旋轉(zhuǎn)和一定程度的仿射等圖像變換具有魯棒性，還提高了匹配的正確率和特征點(diǎn)的復(fù)現(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ū)域選擇和特征點(diǎn)匹配的圖像配準(zhǔn)算法［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］ 張?jiān)粕?自適應(yīng)三角形約束的多基元多視影像匹配方法［D］.武漢：武漢大學(xué)，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－），男，陜西省渭南市人，副教授，主研方向：計(jì)算機(jī)測(cè)控技術(shù)。

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

2015－03－10