一种基于奇异值分解和置信传播的图像匹配算法

窦建方，秦琴，屠子美

（上海第二工业大学智能制造与控制工程学院，上海201209）

一种基于奇异值分解和置信传播的图像匹配算法

窦建方，秦琴，屠子美

（上海第二工业大学智能制造与控制工程学院，上海201209）

图像匹配技术是计算机视觉中一个很重要的问题。当匹配在不同的视角、不同光照、局部遮挡以及复杂背景的情况时，由于特征的可重复性以及区分性下降会导致许多误匹配。针对上述问题，提出了一种提高图像匹配精度方法，这种方法能够去除误匹配的同时恢复丢失的匹配点对。首先采用快速鲁棒性特征（Speeded Up Robust Features，SURF）提取关键点和描述子，从而构建邻接矩阵，然后对邻接矩阵进行奇异值分解获得初始匹配。三角剖分用于提纯初始的匹配，最后通过双图限制恢复丢失的匹配点对。在Oxford数据集测试的实验结果表明，所提出的方法在匹配性能和精度方面，优于随机抽样一致性算法（Random Sample Consensus，RANSAC）。与此同时，该算法的稳定性也相应提高。

图像匹配；奇异值分解；邻接矩阵；三角剖分；置信传播；随机抽样一致性

0　引言

图像匹配是图像处理与模式识别领域中一个非常关键的问题，广泛地应用于图像检索、目标识别与跟踪、自动导航、图像融合和拼接以及双目视觉等方面［1］。图像匹配的方法一般可以分为基于灰度和特征的方法［2-3］。其中基于特征的匹配方法包括两个阶段，第一个阶段是提取图像中显著的结构特征，例如区域特征（森林、河流、田地等）、线特征（区域的边界、海岸线、道路等）、点特征（区域的角点、线的交叉点以及高曲率的点）；第二个阶段是建立两幅图像所提取特征之间的对应关系。这就需要提取的特征应当具备一定区分性和稳定性，以适应光照变化的环境。

Lowe［4］提出尺度不变特征变换算法（SIFT），该算法可以在一定程度上抵抗图像之间的尺度和旋转变化。Bay等［5］提出快速鲁棒性特征（SURF）算法，首先从图像中提取显著关键点，然后再计算这些关键点的描述子。Scott等［6］针对点模式的匹配，采用奇异值分解的方法来解决。这种方法有以下优点：①基于线性代数中的矩阵奇异值分解理论；②不需要进行迭代；③能够较好地处理图像之间的尺度、平移和畸变。但是当匹配在不同的视角、不同光照、局部遮挡以及复杂背景的情况时，由于特征的可重复性以及区分性下降会导致许多误匹配。关于删除误匹配的方法中，典型的方法有随机抽样一致性（RANSAC）［7］的方法。这种方法假定图像之间存在刚性变换，因此可以采用空间几何约束来提纯匹配点对。同时，也存在如下问题：①不能处理非刚性变换；②当初始匹配中的错误匹配点对的数目大于总数目的50%以上的时候，也不能很好的处理；③需要针对不同的应用场合来调整内部的参数，自适应性程度低。Delaunay三角剖分［8］是一种计算几何中对于点集进行三角剖分的方法。它不仅能够对二维平面的点集合以及邻域进行拓扑剖分，同时也具有最大化最小角、最接近于规则化以及唯一性特点。不同的作者探讨了基于奇异值分解的图像匹配方法。文献［9］把奇异值分解的方法用于双目匹配，可以很好地处理平移、切变以及尺度畸变，取得了不错的性能。文献［10］则用于匹配两幅不相关的图像对，从而证实了该方法可以匹配不同成像条件下的图像，而对于候选的匹配点不需要用相关的阈值。文献［11］把基于奇异值分解的方法用于稀疏特征点的图像匹配。Dou等［12］首次提出一种基于SIFT和三角剖分鲁棒的匹配的方法，然后采用仿射不变约束［13］提高匹配的精度。Zhao等［14］介绍了一种去除误匹配的方法。但是在以上所提出的方法中，没有考虑到采用匹配传播用于恢复丢失的匹配点对，从而进一步提高匹配的精度，方便后续的三维重建，目标识别和跟踪。所以本文延伸了原始三角剖分思想，引入置信传播以获得更多的匹配点对。

基于以上讨论，本文提出了一种既能够删除误匹配同时又能恢复丢失的匹配点对的鲁棒的匹配方法。首先采用SURF提取关键点和描述子，从而构建邻接矩阵，然后对邻接矩阵进行奇异值分解获得初始匹配。三角剖分用于提纯初始的匹配，最后通过双图限制恢复丢失的匹配点对。在Oxford数据集测试的实验结果表明，所提出的方法在匹配性能和精度方面，优于随机抽样一致性算法。

1　所提出的方法

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

1.1SURF算法

SURF算法使用积分图像和构造尺度空间可以有效地提取关键点和描述子。它包括两个步骤，分别是关键点检测和关键点描述子计算［5］。在第一个步骤，与采用差分高斯（DoGs）的SIFT算法不同，通过计算积分图像可以快速地来近似图像的高斯的拉普拉斯变换。由于使用积分图像表示，box滤波的计算所耗费的时间不依赖于滤波器的大小。Hessian矩阵行列式的值用来定位和检测关键点。SUFR算法通过保持图像的大小不变而改变滤波的大小，来构造尺度空间。第二个步骤，则是计算关键点的描述子。

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

利用奇异值分解进行特征匹配的方法最早追溯到Scott［6］，计算两幅图像的点之间的距离构建邻接矩阵M，从而获得初始的匹配点对。通常邻接矩阵定义如下：式中，rij是xi和xj采用某种相似测度，计算两点之间的距离；σ是可调的尺度函数。

本文中，采用文献［6］提出的方法通过SURF描述子的欧式距离得到初始的匹配。

假定I1和I2为两幅输入图像，包含的特征如下：

式中，F（A）和F（B）分别为I1和I2所提取的SURF描述子，匹配的目标是对于对应的SURF关键点，获得一一对应的关键点对子集。

基于奇异值分解的匹配方法包含3个步骤：

（1）构建邻接矩阵M，M中的每一个元素根据式（1）计算。rij=||FAi-FBj||为两点所对应的描述子的欧式距离。参数σ控制特征之间的影响。σ越小，局部的对应关系会加权；反之，就会趋向于全局。M中元素的大小位于0和1之间，越大表示两点越相似。

（2）计算m×n矩阵M，其奇异值分解为

其中，U为m×m单位正交阵，D为m×n非负对角矩阵，V为n×n单位正交阵。

（3）通过用对角元素为1的矩阵E替换对角矩阵D，得到正交矩阵P：

（4）获得初始的奇异值分解匹配点对。

正交矩阵P有如下特性［9］：可以增强好的匹配点对，同时减弱差的匹配。根据上述特性，两个用于匹配SURF关键点的决策规则如下：

①Pij分别是矩阵在行和列上的最大值；

1.3三角剖分

文献［15-16］介绍了三角剖分的一些优良的特：①对于随机位置的扰动，三角剖分能够保持一定的结构稳定性。对于所检测到的SURF每一个关键点说，在由非线性畸变引起的平移、旋转以及小尺度变化，与邻域内的关键点保持相似的结构。②对于丢失或者变化剧烈的关键点只是影响三角网的局部区域，也就是说，在随机位置的扰动情况下，Delaunay三角网的一部分仍然具有稳定的结构［17］。图2（a）表示在二维平面上的10个离散点，图2（b）表示由图2（a）这些离散点所构成的Voronoi图以及Delaunay三角网。

图2　三角剖分实例：（a）平面上二维离散点集合；（b）Voronoi图（用实线表示）以及三角网（用虚线表示）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丢失匹配点对的恢复

经过Delaunay三角剖分去除大量的误匹配以后，可能一定数量的正确的匹配点对会同时去除，因此，恢复丢失的匹配点对对于图像的配准是很必要的。

三角剖分去除误匹配以后，剩下的匹配点对构成的图分别表示为Gident=（Vident，ΔTident）和G∗ident=（Vi∗dent，ΔTi∗dent）两个图，其中Gident表示为由图I1剩下的匹配点集Vident以及对该点集进行三角剖分构建的三角网ΔTident构成；同理表示为由图I2剩下的匹配点集以及对该点集进行三角剖分构建的三角网构成。它们可以分割成具有相同大小的Cident（为Voronoi多边形），即单元格。丢失的关键点对属于对应的Voronoi单元格，利用结构一致性，可以恢复得到，加入到Gident=（Vident，ΔTident）和中。数学公式表示如下：

式中：jrecover表示恢复的匹配点对集合表示其中一对匹配点对，分别属于和

图3表示从匹配的两幅输入图像的局部区域中恢复的匹配点对。左半边是输入图像I1，右半边是输入图像I2。用黑色多边形表示的是输入图像I1和I2对应的Voronoi单元格。P1，P2和分别是输入图像I1和I2对应的Voronoi单元格中的关键点。黑线连线表示的P1⇔和P2⇔为使用双图限制恢复的匹配点对。连接P3和的白线表示不存在的匹配点对，因为在输入图像I2上不存在。其中，用白色圆圈来表示的），）和）三对点分别对应图3中从上往下的三条卡线段的起点和终点。

2　仿真结果

2.1实验数据集

实验中所采用的测试数据集来自于文献［18］，其中包括5种不同的成像条件，分别是视角变化、尺度变化、图像模糊、JPEG压缩以及光照变化。对于2种不同的场景类型，应用了视角、尺度和模糊变化。这就意味着不同的场景类型对应于不同的成像条件。对于graffiti，buildings这样的场景类型包含显著的边界，其他则有不同形式的重复的纹理模式。实验中所采用的7对图像成像条件分别为：视角变化包括（graf，wall）图像对，模糊变化包括bikes图像对，JPEG压缩变化包括ubc图像对，leuven为光照变化图像对，bark和boat为缩放加旋转图像对。

图4　所提出的方法与算法对于图像对graf匹配结果比较Fig.4 Matching results ofand Proposed method on Image pairs of graf

2.2仿真结果和分析

为了验证所提出的方法的有效性，我们在文献［18］的数据集合上进行了测试。对于下面的图像中，所匹配的SURF关键点，图像1用“°”表示，而图像2则用“+”，图像1和图像2之间的匹配点对的连线用白线表示。

图4表示的是对于“graf”图像对匹配的结果。图4（a）是对SUFR描述子进行初始匹配的结果，从中可以看到其中有许多的误匹配点对，这些点对表示为图像1和图像2之间的连线点对的与水平方向的夹角过大。图4（b）是在图4（a）初始的匹配的基础上采用RANSAC算法进行提纯得到的正确的匹配点对，一共有454对，而我们提出的方法则有610对。从图4（c）～图4（e）表示的是所提出方法的匹配步骤。图4（c）是对于通过奇异值分解获得初始匹配的基础上，基于Delaunay三角剖分的唯一性，得到的匹配的三角形，表示为白线，分别在图像1和图像2中画出来。图4（d）表示的是通过双图限制恢复的丢失的匹配点对。图4（e）为我们提出的方法的最终匹配结果。对于其他6对图像的匹配结果显示在图5～10中。

图5　所提出的方法与算法对于图像对bikes匹配结果比较Fig.5 Matching results ofand Proposed method on Image pairs of bikes

图6　所提出的方法与算法对于图像对ubc匹配结果比较Fig.6 Matching results ofand Proposed method on Image pairs of ubc

图7　所提出的方法与SURFRANSAC算法对于图像对leuven匹配结果比较Fig.7 Matching results of SURFRANSAC and Proposed method on Image pairs of leuven

图8　所提出的方法与SURFRANSAC算法对于图像对bark匹配结果比较Fig.8 Matching results of SURFRANSAC and Proposed method on Image pairs of bark

图9　所提出的方法与SURFRANSAC算法对于图像对boat匹配结果比较Fig.9 Matching results of SURFRANSAC and Proposed method on Image pairs of boat

图10　所提出的方法与SURFRANSAC算法对于图像对wall匹配结果比较Fig.10 Matching results of SURFRANSAC and Proposed method on Image pairs of wall

表1和表2定量分析了SURFRANSAC方法和所提出的方法SURFDELTRIPROP对于7对实验图像的测试结果，评价的指标采用召回率和匹配精度。其中表1表示匹配结果的召回率，表2表示了匹配的精度，所提出方法的指标列在表格第2列。从仿真结果可以看出，相比于SURFRANSAC方法，所提出的方法有效并能够在一定程度上提高匹配的精度，这对于后续的三维重建以及目标识别是很重要的。

表1　匹配结果的召回率Tab.1 Matching result of recall

表2　匹配结果的精度Tab.2 Matching result of precision

3　结论

本文提出了一种提高图像匹配精度的方法。首先采用SURF提取关键点和描述子，从而构建邻接矩阵，然后对邻接矩阵进行奇异值分解获得初始匹配。三角剖分用于提纯初始的匹配，最后通过双图限制恢复丢失的匹配点对，这种方法能够去除误匹配的同时恢复丢失的匹配点对。通过在Oxford数据集测试的仿真结果表明，所提出的方法与随机抽样一致性（RANSAC）的方法相比，有更好的匹配性能和匹配精度。后续的研究主要集中在基于图论以及稀疏理论来解决图像匹配的相关问题。

［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，FLUSSER 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。

上海第二工业大学校基金（No.EGD15XQD08）项目资助