一种改进的松弛迭代图像配准算法

摘要： 本文展示了一种改进的松弛迭代图像配准算法，此算法首先使用归一化自相关运算求得图像的粗匹配对，接着使用改进的松弛迭代匹配算法进行精匹配。本文通过优化筛选第一轮迭代结果，使得后续迭代时间明显减少。实验证明此算法效率比原始算法有了很大的提高。

Abstract： This paper presents an improved relaxation algorithm for image matching. The algorithm obtains candidate matches with normalized correlation method firstly, and then uses then improved relaxation matching to find the unique matches. This algorithm optimized the results from first round iteration. This makes the algorithm saves lots of time. The experimental results demonstrate the significant improvement of the iterations speed.

关键词： 图像配准；松弛迭代算法；归一化自相关

Key words： image registration; relaxation algorithm; normalized correlation

中图分类号：TP39 文献标识码：A文章编号：1006-4311（2011）05-0180-02

0引言

图像配准是指通过一定的匹配算法在两幅或多幅图像之间识别同名点。它在诸如机器人视觉、医学成像、虚拟现实等领域都有着广泛的用途。配准方法有灰度方法[1]和特征方法[2，4]。其征点的匹配精度更高速度更快，但计算相对复杂。

特征点的图像配准算法首先提取图像灰度变化值足够高的点作为特征点，然后用归一化自相关运算[5]进行特征点粗匹配，最后用松弛迭代匹配算法[6]得到最终匹配对，但匹配速度比较慢。本文提出了一种改进的松弛迭代匹配算法，利用第一轮迭代过程所得到的匹配对，优化筛选一部分候选匹配对进入下一轮迭代，从而减少了算法的计算量。实验证明改进算法的运行速度上比原始算法有了很大的提高，精确性与原始算法基本一致。

1图像特征点的提取与匹配算法

1.1 提取特征点利用Harris算子[3]提取特征点：

R=det（C）-k•trace（C），k=0.04（1）

det为矩阵的行列式，trace为矩阵直迹，矩阵C为：

C=G I IIII I（2）

其中，G为高斯模板，I和I分别为x方向和y方向的梯度。

矩阵R中每一点的元素值对应于原图相应点的兴趣值。但每幅图像所提取的特征点有很多冗余。

1.2 粗匹配粗匹配是利用特征点附近的灰度信息，建立一个局部匹配的准则，将两幅图像的特征点划分为多对多匹配对。设图像I中的特征点m1（u1，v1）和图像I中的特征点m2（u2，v2），则计算m1和m2的自相关系数[5]：

Score（m，m）I（u+i，v+j）-

×（3）

其中，是点（u，v）处的灰度均值，σ（I）则为（2n+1）×（2m+1）邻域内的灰度标准差。

经过阈值处理，可以得到候选匹配对,本文采用的阈值为0.8。

1.3 精匹配候选匹配对（多对多匹配对）需要精确为一对一的真匹配对。

假设存在候选匹配对（m，m），N（m）和N（m）分别为以m和m为中心，半径为R的邻域内的特征点集。定义匹配强度如下 [5]：

SM（m，m）=cij×（4）

其中，cij和ckl分别为（m，m）和其领域内其他匹配对（n，n）的自相关系数，dist（m，m；n，n）为两对特征点之间的平均距离，δ为相对距离的影响因子。

通过此公式求出每个候选匹配对的匹配强度。松弛迭代匹配算法分为以下几步：

①利用式（4）求得到每个候选匹配对的匹配强度。

②计算候选匹配对的明确度：U=1-S（X）S（X）（5）

其中，S（X）为点X的最大匹配强度，S（X）为点X的第二大匹配强度。

③若候选匹配对的匹配强度和明确度数值都高，就将此候选匹配对定为真匹配对。若候选匹配对的两个特征点对应的具有最大匹配强度的点都不是对方，就将此候选匹配对定为假匹配对。剔除候选匹配对中的真匹配对和假匹配。

④返回第一步，进行下一步迭代。直到没有新的真匹配对出现为止。

2改进的松弛迭代匹配算法

当松弛迭代完成第一轮迭代后，我们得到了候选匹配对中的最相似的一部分匹配对。从精确度和数量上来说，这些匹配对完全可以代表两幅图像的匹配。那么，我们可以利用这些匹配对所代表的匹配性质，筛选出更优的候选匹配对进入下一轮迭代。

筛选的策略可以根据不同的图像配准类型进行自定义。本文定义两幅图像的位置偏移作为筛选条件：

w=（6）

其中R为第一轮迭代后的真匹配对集合，dist（m，m）为两个特征点的相对距离，n为R中真匹配对的数量。给定w阈值，我们可以在进入第二轮迭代前，筛选掉不在阈值范围内的候选匹配对。

3实验结果

实验使用航拍图像对改进算法与原始算法进行对比，如图1和图2所示。比较两算法的用时和最终匹配对数量，如表1所示。改进后的算法在速度上与原始算法相比具有很大的优势，最终的真匹配对与原始基本一致。

4结束语

本文改进的松弛迭代算法利用第一轮迭代过程所得到的匹配对，把进入下一轮迭代的候选匹配对进行优化筛选，使得进入下一轮迭代的候选匹配对大幅度减少，从而减少了大量迭代时间。经实验证明此算法的效率远优于原始算法。

参考文献：

[1]罗钟铉，刘成名.灰度图像匹配的快速算法[J].计算机辅助设计与图形学学报，2005，17（5）：966-970.

[2]周骥，石教英，赵友兵.图像特征点匹配的强壮算法[J].计算机辅助设计与图形学学报，2002，14（8）：754-757.

[3]Harris C G，Stephens M J.A Combined Corner and Edge Detector.Proceedings Fourth Alvey Vision Conference，Manchester，1988：147-151.

[4]Ji Zhou and Jiaoying Shi. A Robust Algorithm for Feature Point Matching[J].Computers & Graphics，2002，26（3）：429-436.

[5]ZHANG Z Y. A robust technique for matching two uncalibrated images through recovery of the unknown epipolar geometry[R]. Technical Report, INRIA, 1994.

[6]刘博，胡正平，王成儒.基于模糊松弛迭代的分层图像增强算法[J].光学技术，2009，35（1）：131-135.