一种快速稳健的图像配准算法

摘要:本文对图像配准问题进行了研究,提出了一种快速、稳健的基于特征点匹配的配准算法。采用小波变换建立图像金字塔,从分辨率最低的图像层开始进行特征点匹配,在次一层匹配时以上层匹配结果为粗值,在原始图像上得到初始匹配点后采用RANSAC算法稳健估计变换矩阵H;为了提高配准算法的精度,采用变换矩阵H引导两幅原始图像上的所有特征点重新进行匹配,对得到的匹配点集重新用RANSAC算法估计变换矩阵,并采用LM非线性优化算法进一步优化。通过实验分析对比,本文的算法比原算法速度更快,更稳健。

关键词:图像配准;特征点匹配;图像金字塔

中图分类号:TP393.09 文献标识码:A文章编号:1007-9599 (2010) 05-0000-02

A Fast&Robust Algorithm for Image Registration

Wang Huaqin

(Changsha Sociol Work College,Changsha410004,China)

Abstract:This paper researched on image registration,presented a fast and robust algorithm based on feature point matching.Based on the analysis of the exiting methods and the researches of wavelet pyramidal matching algorithm,image pyramid is used to solve the problem of the high cost of the existing method.In this method,image pyramid is constructed by the wavelet transformation,the images in coarse layers are matched based on feature points,the matching starts from the coarsest layer and the result is up-sampled as initial estimation for the finer layer,after getting initial matching points on the original image,use anRANSAC algorithm to estimate transformation matrix between two images;the transformation matrix is used to guide local point matching again,then combine RANSAC algorithm and Levenberg-Marquardt optimization to decrease registration error.The experiment shows better results than existing methods on matching speed and the robustness of the algorithm.

Keywords:Image registration;Feature point matching;Image pyramid

一、引言

图像拼接技术是近些年的研究热点,其核心技术就是图像配准技术。文献[1]中Richard以手动确定至少4对特征点,并以特征点像素的亮度误差构造优化函数来估计图像间的点变换关系, 取得了比较好的平面和深度场景融合效果,但此算法以亮度误差来做点变换估计, 这对图像的光照变化非常敏感且整个算法的自动化程度不够。

在全自动稳健的图像拼接中对基于特征的图像配准算法研究得比较多的是一种以层层迭代、逐步求精的策略为基础的算法[3][7][8]。这种算法的思想如下:首先对图像提取特征,包括特征点(极值点、边缘点、角点)、特征线、特征区域等。针对不同的特征有相应的特征提取算子。特征点提取出来以后要根据特征点之间的局部特征进行粗略的匹配,找到待匹配点集合之间的对应关系。一般是基于灰度互相关进行初步估计,剔除差别较大的匹配对。然后进一步估计匹配,RANSAC算法[3]是用得最多的提纯匹配点集的方法。文献[3]针对RANSAC 算法进行了LM非线性优化以保证后续匹配的稳健。这种算法对有较大误差或者错误的匹配点进行逐步迭代过滤,并用提纯后的数据对模型进行计算,因而对于噪声和特征点提取错误有较强的鲁棒性。由于该方法在粗匹配阶段采用了灰度互相关方法直接对图像上的所有特征点进行遍历地搜索,因此计算量很大。

二、本文图像配准算法

(一)提取角点

Harris[2]算子是C.Harris和M.J.Stephens提出的一种基于信号的点特征提取算子,具有计算简单、提取的角点特征均匀合理、可以定量提取特征点以及算子稳定的特点。其处理过程表示如下:

(1)

(2)

其中, 为 方向的梯度,为 方向的梯度, 为高斯模板, 为矩阵的行列式, 为矩阵直迹, 为默认常数。矩阵 中每一点的元素值对应于原图相应点的兴趣值。

(二)角点粗匹配

特征点匹配是指找出图像1和2中的唯一对应特征点。特征点匹配常用的方法是归一化互相关(Normalised Cross-Correlation, NCC)法。归一化相关算法具有算法实现简单、抗白噪声干扰能力强等优点。

该方法依据特征点邻域像素灰度值的相似性来进行匹配。设w1和w2是分别以图像1的特征点p1和图像2的特征点2为中心的两个大小相同的匹配窗口,u1,u2为相关窗口内像素灰度的均值。NCC匹配方法去除了低频背景亮度信息的干扰。进行特征点匹配时,首先对于图像1中的任一角点,寻找在图像2中和它相关性最大的角点;然后对于图像2中的任一角点,寻找在图像1中和它相关性最大的角点,当双向搜寻到的最大相关性的角点彼此对应,即认为找到一对候选匹配点。w1和w2的取值范围为窗口大小,则定义NCC公式为:

(3)

(三)图像金字塔分层匹配

粗匹配阶段直接对两幅图像的全部角点进行遍历式搜索,时间开销大;由于采用遍历式搜索错误匹配难以避免,甚至重叠区域之外的点也可能被匹配,因此得到的正确匹配点少。引入图像金字塔结构,采用分层匹配来提高搜索匹配的效率。

小波金字塔分解的基本思想[4]是:首先利用小波变换理论将原始图像逐级分解得到一个分辨率从低到高、规模由小到大的金字塔结构;然后在分辨率低的图像层,通过线性搜索或其他策略得到该分辨率下的最优解估计:在次一层匹配时,以上层匹配结果为引导,在局部范围内完成匹配;并随着分辨率的提高匹配点对的精度逐层提高,最终在最高分辨率的图像层上得到满足精度要求的匹配。

(四)变换矩阵的鲁棒估计算法

本文采集的每组图像是在同一视点所拍摄,图像之间的变换关系可以用投影变换模型来描述。相邻两幅图像间的特征点匹配后形成了图像1和图像2之间的一组映射点集。需要从这一组映射点集中估算变换矩阵H。

在特征点的检测中往往由于定位测量不够精确或者得到的匹配点存在大量错配,从而引起噪声。由于噪声的存在,用一般的线性方法得到的变换矩阵往往不稳定。这是由于把误差较大的点和错误的匹配点也加入到变换矩阵的求解过程中,也就往往成误差较大的解。为克服噪声引起的误差,本文采用鲁棒估计算法RANSAC[6]来估计矩阵。

RANSAC的特点是充分地利用了所有的测量数据,并根据阙值把它们分成了内点和外点,利用内点数据比较准确的特点来进行参数估计而剔除了不准确的测量数据,因此,得到的结果应该是一种优化的结果。本文采用RANSAC来提纯内点。针对本文的估计问题, 就需要随机选取4对匹配点,每次采样后根据4 对匹配点计算出H,最后根据得到的内点集合来估计矩阵H。

在估计出矩阵和相应的匹配点后,通常采用均方根几何误差来衡量变换矩阵估计的精度,称为配准误差,公式如下:

(4)

其中xi为图像2上的匹配点位置,xi′为图像1上的匹配点位置,d(x′,Hx)是图像2上的点x经过矩阵 变换后得到的坐标与左图像上对应匹配点′坐标之间的欧式距离,n是匹配点对数。本文以图像1为参考图像,由图像2向图像1进行配准,如果配准误差过大,则会导致后续的拼接过程无法进行。

(五)引导匹配

为了得到更精确的矩阵,本文采用变换矩阵H引导两幅原始图像上的所有角点再次进行归一化互相关匹配,具体方法是利用变换矩阵H计算出图像2上所有角点在图像1上的位置,则对图像2上任一角点则只需在以图像1上对应位置为中心的某个窗口进行搜索匹配即可,这样相比起直接进行遍历搜索,不但增加了正确匹配点个数,而且也减少了误匹配的可能性,并且时间复杂度也比较低。

对互相关匹配得到的匹配点集重新采用RANSAC算法估计矩阵H,同时也获得了更多的内点匹配。

将矩阵H和这些内点匹配对代入公式(4),采用LM(Levenberg-Marquardt)非线性优化算法[5]来计算矩阵,能够进一步改进估计的变换矩阵。

三、实验结果:

下面采用本文算法对两幅640 480的校园广场图片进行实验分析,并且与原算法[3]进行比较,为了便于比较,对参数进行了统一设置,

本文算法中角点检测(包括小波分解的时间)共耗时2.45秒,匹配阶段(包括金字塔匹配阶段和引导匹配阶段)耗时1.57秒,共耗时4.02秒,得到匹配对300对,而原算法的角点检测耗时为1.62秒,匹配阶段耗时11.18秒,共耗时12.8秒,得到匹配点为140对,可见由于采用了金字塔分层匹配算法,本文在匹配阶段的搜索效率大大提高,并且采用了引导匹配产生更多的正确匹配对,从而提高了配准精度。

表1 校园广场图片实验对比

配准算法 角点检测时间(单位:秒) 匹配时间(单位:秒) 总耗时(单位:秒) 匹配点对数 配准误差(单位:像素)

本文算法 2.45 1.57 4.02 300 0.5470

原算法 1.62 11.18 12.8 140 0.5808

图1校园广场图片

四、小结

在基于特征点匹配的图像配准算法中,最为耗时的步骤是基于归一化互相关匹配的遍历搜索过程,本文以采用小波金字塔匹配来提高了归一化互相关匹配阶段的搜索效率,并且获得了获得较好的初始有匹配对,然后用 RANSAC算法来估算矩阵;为了获得更多的正确匹配点,用估算的H引导原始图像进行再次的归一化互相关匹配,对获得的匹配点集再次采

用RANSAC算法估算矩阵,经LM优化后配准误差被降低配准误差被降低。

参考文献

[1]Richard Szeliski. Video mosaics for virtual environments. IEEE Computer Graphics and Applications,1996.16(2): 22-30.

[2]张祖勋,张剑清.遥感影像的高精度自动配准.武汉测绘科技大学学报,1998.23(4):320-323.

[3]赵向阳,杜利民.一种全自动稳健的图像拼接融合算法.中国图形图像学报,2004.9(4):417-422.

[4]张艳,王涛,路威.基于小波影像金字塔的影像自动匹配.测绘学院学报,2002.19(1):25-27

[5]Richard Hartley,Andrew Zisserman. Multiple View Geometry in Computer Vision. Cambridge: The Press Syndicate of The University of Cambridge,U K,2000

[6]M.A.Fishler,R.C.Boles. Random sample consesus:A paradigm for model fitting with applications to image analysis and automated p, 1981.24(6):381-395.

[7]梁栋,童强,屈磊,等.一种基于极几何和单应约束的图像匹配算法.系统仿真学报,2006.18(1):44-46

[8]朱云芳,叶秀清,顾伟康.视频序列的全景图拼接技术.中国图形图像学报.2006.11(8):198-203.

作者简介:汪华琴(1982.8.19),女,湖北潜江,汉,湖南长沙民政职业技术学院辅导员,助教,硕士,计算机应用技术。