竇建方，秦琴，屠子美

（上海第二工業(yè)大學智能制造與控制工程學院，上海201209）

一種基于奇異值分解和置信傳播的圖像匹配算法

竇建方，秦琴，屠子美

（上海第二工業(yè)大學智能制造與控制工程學院，上海201209）

圖像匹配技術(shù)是計算機視覺中一個很重要的問題。當匹配在不同的視角、不同光照、局部遮擋以及復雜背景的情況時，由于特征的可重復性以及區(qū)分性下降會導致許多誤匹配。針對上述問題，提出了一種提高圖像匹配精度方法，這種方法能夠去除誤匹配的同時恢復丟失的匹配點對。首先采用快速魯棒性特征（Speeded Up Robust Features，SURF）提取關鍵點和描述子，從而構(gòu)建鄰接矩陣，然后對鄰接矩陣進行奇異值分解獲得初始匹配。三角剖分用于提純初始的匹配，最后通過雙圖限制恢復丟失的匹配點對。在Oxford數(shù)據(jù)集測試的實驗結(jié)果表明，所提出的方法在匹配性能和精度方面，優(yōu)于隨機抽樣一致性算法（Random Sample Consensus，RANSAC）。與此同時，該算法的穩(wěn)定性也相應提高。

圖像匹配；奇異值分解；鄰接矩陣；三角剖分；置信傳播；隨機抽樣一致性

0　引言

圖像匹配是圖像處理與模式識別領域中一個非常關鍵的問題，廣泛地應用于圖像檢索、目標識別與跟蹤、自動導航、圖像融合和拼接以及雙目視覺等方面［1］。圖像匹配的方法一般可以分為基于灰度和特征的方法［2-3］。其中基于特征的匹配方法包括兩個階段，第一個階段是提取圖像中顯著的結(jié)構(gòu)特征，例如區(qū)域特征（森林、河流、田地等）、線特征（區(qū)域的邊界、海岸線、道路等）、點特征（區(qū)域的角點、線的交叉點以及高曲率的點）；第二個階段是建立兩幅圖像所提取特征之間的對應關系。這就需要提取的特征應當具備一定區(qū)分性和穩(wěn)定性，以適應光照變化的環(huán)境。

Lowe［4］提出尺度不變特征變換算法（SIFT），該算法可以在一定程度上抵抗圖像之間的尺度和旋轉(zhuǎn)變化。Bay等［5］提出快速魯棒性特征（SURF）算法，首先從圖像中提取顯著關鍵點，然后再計算這些關鍵點的描述子。Scott等［6］針對點模式的匹配，采用奇異值分解的方法來解決。這種方法有以下優(yōu)點：①基于線性代數(shù)中的矩陣奇異值分解理論；②不需要進行迭代；③能夠較好地處理圖像之間的尺度、平移和畸變。但是當匹配在不同的視角、不同光照、局部遮擋以及復雜背景的情況時，由于特征的可重復性以及區(qū)分性下降會導致許多誤匹配。關于刪除誤匹配的方法中，典型的方法有隨機抽樣一致性（RANSAC）［7］的方法。這種方法假定圖像之間存在剛性變換，因此可以采用空間幾何約束來提純匹配點對。同時，也存在如下問題：①不能處理非剛性變換；②當初始匹配中的錯誤匹配點對的數(shù)目大于總數(shù)目的50%以上的時候，也不能很好的處理；③需要針對不同的應用場合來調(diào)整內(nèi)部的參數(shù)，自適應性程度低。Delaunay三角剖分［8］是一種計算幾何中對于點集進行三角剖分的方法。它不僅能夠?qū)ΧS平面的點集合以及鄰域進行拓撲剖分，同時也具有最大化最小角、最接近于規(guī)則化以及唯一性特點。不同的作者探討了基于奇異值分解的圖像匹配方法。文獻［9］把奇異值分解的方法用于雙目匹配，可以很好地處理平移、切變以及尺度畸變，取得了不錯的性能。文獻［10］則用于匹配兩幅不相關的圖像對，從而證實了該方法可以匹配不同成像條件下的圖像，而對于候選的匹配點不需要用相關的閾值。文獻［11］把基于奇異值分解的方法用于稀疏特征點的圖像匹配。Dou等［12］首次提出一種基于SIFT和三角剖分魯棒的匹配的方法，然后采用仿射不變約束［13］提高匹配的精度。Zhao等［14］介紹了一種去除誤匹配的方法。但是在以上所提出的方法中，沒有考慮到采用匹配傳播用于恢復丟失的匹配點對，從而進一步提高匹配的精度，方便后續(xù)的三維重建，目標識別和跟蹤。所以本文延伸了原始三角剖分思想，引入置信傳播以獲得更多的匹配點對。

基于以上討論，本文提出了一種既能夠刪除誤匹配同時又能恢復丟失的匹配點對的魯棒的匹配方法。首先采用SURF提取關鍵點和描述子，從而構(gòu)建鄰接矩陣，然后對鄰接矩陣進行奇異值分解獲得初始匹配。三角剖分用于提純初始的匹配，最后通過雙圖限制恢復丟失的匹配點對。在Oxford數(shù)據(jù)集測試的實驗結(jié)果表明，所提出的方法在匹配性能和精度方面，優(yōu)于隨機抽樣一致性算法。

1　所提出的方法

圖1　所提出的算法流程圖Fig.1 Flowchart of the proposed matching method SURF DELTRIPROP

1.1SURF算法

SURF算法使用積分圖像和構(gòu)造尺度空間可以有效地提取關鍵點和描述子。它包括兩個步驟，分別是關鍵點檢測和關鍵點描述子計算［5］。在第一個步驟，與采用差分高斯（DoGs）的SIFT算法不同，通過計算積分圖像可以快速地來近似圖像的高斯的拉普拉斯變換。由于使用積分圖像表示，box濾波的計算所耗費的時間不依賴于濾波器的大小。Hessian矩陣行列式的值用來定位和檢測關鍵點。SUFR算法通過保持圖像的大小不變而改變?yōu)V波的大小，來構(gòu)造尺度空間。第二個步驟，則是計算關鍵點的描述子。

1.2基于SURF描述子的奇異值分解匹配

利用奇異值分解進行特征匹配的方法最早追溯到Scott［6］，計算兩幅圖像的點之間的距離構(gòu)建鄰接矩陣M，從而獲得初始的匹配點對。通常鄰接矩陣定義如下：式中，rij是xi和xj采用某種相似測度，計算兩點之間的距離；σ是可調(diào)的尺度函數(shù)。

本文中，采用文獻［6］提出的方法通過SURF描述子的歐式距離得到初始的匹配。

假定I1和I2為兩幅輸入圖像，包含的特征如下：

式中，F(xiàn)（A）和F（B）分別為I1和I2所提取的SURF描述子，匹配的目標是對于對應的SURF關鍵點，獲得一一對應的關鍵點對子集。

基于奇異值分解的匹配方法包含3個步驟：

（1）構(gòu)建鄰接矩陣M，M中的每一個元素根據(jù)式（1）計算。rij=||FAi-FBj||為兩點所對應的描述子的歐式距離。參數(shù)σ控制特征之間的影響。σ越小，局部的對應關系會加權(quán)；反之，就會趨向于全局。M中元素的大小位于0和1之間，越大表示兩點越相似。

（2）計算m×n矩陣M，其奇異值分解為

其中，U為m×m單位正交陣，D為m×n非負對角矩陣，V為n×n單位正交陣。

（3）通過用對角元素為1的矩陣E替換對角矩陣D，得到正交矩陣P：

（4）獲得初始的奇異值分解匹配點對。

正交矩陣P有如下特性［9］：可以增強好的匹配點對，同時減弱差的匹配。根據(jù)上述特性，兩個用于匹配SURF關鍵點的決策規(guī)則如下：

①Pij分別是矩陣在行和列上的最大值；

1.3三角剖分

文獻［15-16］介紹了三角剖分的一些優(yōu)良的特：①對于隨機位置的擾動，三角剖分能夠保持一定的結(jié)構(gòu)穩(wěn)定性。對于所檢測到的SURF每一個關鍵點說，在由非線性畸變引起的平移、旋轉(zhuǎn)以及小尺度變化，與鄰域內(nèi)的關鍵點保持相似的結(jié)構(gòu)。②對于丟失或者變化劇烈的關鍵點只是影響三角網(wǎng)的局部區(qū)域，也就是說，在隨機位置的擾動情況下，Delaunay三角網(wǎng)的一部分仍然具有穩(wěn)定的結(jié)構(gòu)［17］。圖2（a）表示在二維平面上的10個離散點，圖2（b）表示由圖2（a）這些離散點所構(gòu)成的Voronoi圖以及Delaunay三角網(wǎng)。

圖2　三角剖分實例：（a）平面上二維離散點集合；（b）Voronoi圖（用實線表示）以及三角網(wǎng)（用虛線表示）Fig.2 Examples of（a）2D points，（b）Voronoi diagram（solid line）and Delaunay triangulation net（dashed line）

圖3　通過雙Voronoi圖恢復丟失的匹配點對Fig.3 Recovered matches by dual graph voronoi

1.4丟失匹配點對的恢復

經(jīng)過Delaunay三角剖分去除大量的誤匹配以后，可能一定數(shù)量的正確的匹配點對會同時去除，因此，恢復丟失的匹配點對對于圖像的配準是很必要的。

三角剖分去除誤匹配以后，剩下的匹配點對構(gòu)成的圖分別表示為Gident=（Vident，ΔTident）和G?ident=（Vi?dent，ΔTi?dent）兩個圖，其中Gident表示為由圖I1剩下的匹配點集Vident以及對該點集進行三角剖分構(gòu)建的三角網(wǎng)ΔTident構(gòu)成；同理表示為由圖I2剩下的匹配點集以及對該點集進行三角剖分構(gòu)建的三角網(wǎng)構(gòu)成。它們可以分割成具有相同大小的Cident（為Voronoi多邊形），即單元格。丟失的關鍵點對屬于對應的Voronoi單元格，利用結(jié)構(gòu)一致性，可以恢復得到，加入到Gident=（Vident，ΔTident）和中。數(shù)學公式表示如下：

式中：jrecover表示恢復的匹配點對集合表示其中一對匹配點對，分別屬于和

圖3表示從匹配的兩幅輸入圖像的局部區(qū)域中恢復的匹配點對。左半邊是輸入圖像I1，右半邊是輸入圖像I2。用黑色多邊形表示的是輸入圖像I1和I2對應的Voronoi單元格。P1，P2和分別是輸入圖像I1和I2對應的Voronoi單元格中的關鍵點。黑線連線表示的P1?和P2?為使用雙圖限制恢復的匹配點對。連接P3和的白線表示不存在的匹配點對，因為在輸入圖像I2上不存在。其中，用白色圓圈來表示的），）和）三對點分別對應圖3中從上往下的三條卡線段的起點和終點。

2　仿真結(jié)果

2.1實驗數(shù)據(jù)集

實驗中所采用的測試數(shù)據(jù)集來自于文獻［18］，其中包括5種不同的成像條件，分別是視角變化、尺度變化、圖像模糊、JPEG壓縮以及光照變化。對于2種不同的場景類型，應用了視角、尺度和模糊變化。這就意味著不同的場景類型對應于不同的成像條件。對于graffiti，buildings這樣的場景類型包含顯著的邊界，其他則有不同形式的重復的紋理模式。實驗中所采用的7對圖像成像條件分別為：視角變化包括（graf，wall）圖像對，模糊變化包括bikes圖像對，JPEG壓縮變化包括ubc圖像對，leuven為光照變化圖像對，bark和boat為縮放加旋轉(zhuǎn)圖像對。

圖4　所提出的方法與算法對于圖像對graf匹配結(jié)果比較Fig.4 Matching results ofand Proposed method on Image pairs of graf

2.2仿真結(jié)果和分析

為了驗證所提出的方法的有效性，我們在文獻［18］的數(shù)據(jù)集合上進行了測試。對于下面的圖像中，所匹配的SURF關鍵點，圖像1用“°”表示，而圖像2則用“+”，圖像1和圖像2之間的匹配點對的連線用白線表示。

圖4表示的是對于“graf”圖像對匹配的結(jié)果。圖4（a）是對SUFR描述子進行初始匹配的結(jié)果，從中可以看到其中有許多的誤匹配點對，這些點對表示為圖像1和圖像2之間的連線點對的與水平方向的夾角過大。圖4（b）是在圖4（a）初始的匹配的基礎上采用RANSAC算法進行提純得到的正確的匹配點對，一共有454對，而我們提出的方法則有610對。從圖4（c）～圖4（e）表示的是所提出方法的匹配步驟。圖4（c）是對于通過奇異值分解獲得初始匹配的基礎上，基于Delaunay三角剖分的唯一性，得到的匹配的三角形，表示為白線，分別在圖像1和圖像2中畫出來。圖4（d）表示的是通過雙圖限制恢復的丟失的匹配點對。圖4（e）為我們提出的方法的最終匹配結(jié)果。對于其他6對圖像的匹配結(jié)果顯示在圖5～10中。

圖5　所提出的方法與算法對于圖像對bikes匹配結(jié)果比較Fig.5 Matching results ofand Proposed method on Image pairs of bikes

圖6　所提出的方法與算法對于圖像對ubc匹配結(jié)果比較Fig.6 Matching results ofand Proposed method on Image pairs of ubc

圖7　所提出的方法與SURFRANSAC算法對于圖像對leuven匹配結(jié)果比較Fig.7 Matching results of SURFRANSAC and Proposed method on Image pairs of leuven

圖8　所提出的方法與SURFRANSAC算法對于圖像對bark匹配結(jié)果比較Fig.8 Matching results of SURFRANSAC and Proposed method on Image pairs of bark

圖9　所提出的方法與SURFRANSAC算法對于圖像對boat匹配結(jié)果比較Fig.9 Matching results of SURFRANSAC and Proposed method on Image pairs of boat

圖10　所提出的方法與SURFRANSAC算法對于圖像對wall匹配結(jié)果比較Fig.10 Matching results of SURFRANSAC and Proposed method on Image pairs of wall

表1和表2定量分析了SURFRANSAC方法和所提出的方法SURFDELTRIPROP對于7對實驗圖像的測試結(jié)果，評價的指標采用召回率和匹配精度。其中表1表示匹配結(jié)果的召回率，表2表示了匹配的精度，所提出方法的指標列在表格第2列。從仿真結(jié)果可以看出，相比于SURFRANSAC方法，所提出的方法有效并能夠在一定程度上提高匹配的精度，這對于后續(xù)的三維重建以及目標識別是很重要的。

表1　匹配結(jié)果的召回率Tab.1 Matching result of recall

表2　匹配結(jié)果的精度Tab.2 Matching result of precision

3　結(jié)論

本文提出了一種提高圖像匹配精度的方法。首先采用SURF提取關鍵點和描述子，從而構(gòu)建鄰接矩陣，然后對鄰接矩陣進行奇異值分解獲得初始匹配。三角剖分用于提純初始的匹配，最后通過雙圖限制恢復丟失的匹配點對，這種方法能夠去除誤匹配的同時恢復丟失的匹配點對。通過在Oxford數(shù)據(jù)集測試的仿真結(jié)果表明，所提出的方法與隨機抽樣一致性（RANSAC）的方法相比，有更好的匹配性能和匹配精度。后續(xù)的研究主要集中在基于圖論以及稀疏理論來解決圖像匹配的相關問題。

［1］CRUM W R，HARTKENS T，HILL D L G.Non-rigid image registration：Theory and practice［J］.The British Journal of Radiology，2004，77（2）：S140.

［2］ZITOVA B，F(xiàn)LUSSER J.Image registration methods：A survey［J］.Image Vision Computing，2003，21（11）：977-1000.

［3］BROWN L G.A survey of image registration techniques［J］.ACM Computing Surveys，1992，24（4）：325-376.

［4］LOWE D G.Distinctive image features form scale-Invariant keypoints［J］.International Journal Computing Vision，2004，60（2）：91-110.

［5］BAY H，TUYTELAARS T，VAN GOOL L V.SURF：Speeded uprobust features［C］//9th European Conference on Computer Vision European Conference on Computer-Vision.Graz，Austria：Springer Berlin Heidelberg，2006：407-417.

［6］SCOTT G L，LONGUET-HIGGINS H C.An algorithm for associating the features of two images［J］.Proceedings of the Royal Society of London B：Biological Sciences，1991，244（1309）：21-26.

［7］FISCHLER M A，BOLLES R C.Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography［J］.Comm.of the ACM，1981，24（6）：381-395.

［8］BARBER C B，DOBKIN D P，HUHDANPAA H.Thequickhull algorithm for convex hulls［J］.ACM Transactionson Mathematical Software，1996，22（4）：469-483.

［9］PILU M.A direct method for stereo correspondence based on singular valuedecomposition［C］//1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Juan，PR，USA：IEEE，1997：261-266.

［10］ZHAO F.Imagematchingbasedonsingularvaluedecomposition［C］//Advances in Multimedia Information Processing -PCM 2004：5th Pacific-Rim Conferenceon Multimedia. Tokyo，Japan：Springer Berlin Heidelberg，2004：119-126.

［11］DELPONTE E，ISGR`O F，ODONE F，et al.SVD-matching using SIFT features［J］.Graphical Models，2006，68（5/6）：415-431.

［12］DOU J，LI J.Robust image matching based on SIFT anddelaunay triangulation［J］.Chinese Optical Letter，2012，10（s1）：54-58.

［13］DOU J，LI J.Image matching based local Delaunay triangulation and affine invariant geometric constraint［J］.International Journal for Light and Electron Optics，2014，125（1）：526-531.

［14］ZHAO X，HE Z，ZHANG S.Improved keypoint descriptors based on Delaunay triangulation for image matching［J］.International Journal for Light and Electron Optics，2014，125（13）：3121-3123.

［15］ABELLANAS M，HURTADO F，RAMOS P A.Structural toleranceand Delaunay triangulation［J］.Information Processing Letters，1999，71（5/6）：221-227.

［16］KHANBAN A A，EDALAT A.Computing Delaunay triangulation withimprecise input data［C］//15th Canadian Conference on Computational Geometry.Halifax，Canada：CCCG，2003：94-97.

［17］BOISSONNAT J D，YVINEC M.Algorithmic geometry，chapter Voronoi diagrams：Euclidian metric，Delaunaycomplexes［M］.UK：Cambridge University Press，1998.

［18］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Transactionson Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

An Image Matching Algorithm Based On Singular Value Decomposition and Belief Propagation

DOU Jianfang，QIN Qin，TU Zimei
（School of Intelligent Manufacturing and Control Engineering，Shanghai Polytechnic University，Shanghai 201209，P.R.China）

Finding correspondences between pair of images of the same scene is a key problem in computer vision.When matching images undergoes viewpoint change，partial occlusion，clutters and illumination change，there will be a lot of mismatches due to the limited repeatability and discriminative power of features.A robust matching algorithm that can remove false matches and propagate the correct ones to obtain more matches is proposed，thus improve the matching accuracy.Firstly，SURF（Speeded Up Robust Features）descriptorsofeachimageareextracted，whichcanbeusedtobuildtheproximitymatrix.Secondly，SVD（SingularValueDecomposition）is performed on the proximity matrix to obtain the initial matches.Thirdly，the unique property of delaunay triangulation is adopted to refine the initial matches which can produce the maximum clique of the two delaunay graph.Finally，the lost matches are recovered with the constraint of dual graph of Voronoi.Experimental results on Oxford datasets indicate that the algorithm can improve match performance compared to the RANSAC-based method.At the same time，the stability of our method is better than RANSAC.

image matching；singular value decomposition；proximity matrix；delaunay triangulation；belief propagation；Random Sample Consensus（RANSAC）

TP391.4

A

1001-4543（2016）03-0222-09

2015-12-25

竇建方（1982-），男，河北定州人，講師，博士，主要研究方向為目標檢測跟蹤與識別。電子郵箱jfdou@sspu.edu.cn。

上海第二工業(yè)大學校基金（No.EGD15XQD08）項目資助