结合S U R F描述符和广义近邻图的图像配准算法*

2012-02-28 05:10孙登第卜令斌
网络安全与数据管理 2012年15期
关键词:互信息鲁棒性广义

孙登第 ,罗 斌 ,卜令斌

(1.安徽大学 计算机科学与技术学院,安徽 合肥 230039;2.安徽省工业图像处理与分析重点实验室,安徽 合肥 230088)

图像配准是对同一场景在不同条件下(如不同的时间、拍摄环境、视角和传感器等)得到的两幅或多幅图像寻求某种空间上的变换,使一幅图像能够和另一幅图像上的对应点达到空间上的一致[1]。图像配准技术是图像处理与分析中的基本任务,已经在计算机视觉、图像融合、全景图像拼接、医学诊断与辅助治疗等众多领域得到广泛的应用[2-3]。

目前,图像配准方法大体分为基于灰度和基于特征两大类。基于灰度的方法建立图像间像素灰度值的目标函数,如互信息测度[4],通过对目标函数的优化实现配准。该方法没有考虑像素的空间信息,在不同成像条件下的图像配准中,其精度较低、计算量大且配准时间长。

基于特征的配准方法先提取各个图像中的特征,再完成特征之间的匹配,通过匹配的特征建立图像间的映射变换,最后求出配准后的图像。特征点是该类方法最常使用的图像特征,其中BAY H等人提出的SURF(Speeded-Up Robust Features)算法是一种尺度空间的特征点描述方法[5],对图像间的分辨率、旋转、平移和光照变化等保持不变,且时间复杂度低、速度较快。基于特征点的配准方法减轻了图像灰度差异和噪声的影响,缩短了配准时间。然而,特征点匹配问题本身就是一个尚未得到较好解决的难题,特征点的误匹配直接影响了图像的最终配准结果。

为解决上述问题,RANGARAJAN A等提出了一种结合互信息与特征点的配准方法[6],定义了特征点集的互信息函数,通过对该函数最大化实现图像配准。这种方法减轻了灰度差异与特征点误配对配准的影响,但函数形式复杂,配准时间较长。

最新的研究结果表明,通过对随机抽样构建广义近邻图可以估计随机变量的熵[7],这已在统计学与信息论的研究中受到广泛关注。本文将该理论引入图像配准中,将图像配准中的特征点与互信息结合起来估计特征点的Rényi互信息,提出了一种结合SURF描述子和广义近邻图医学图像配准方法。该方法了融合图像空间信息且无需计算概率直方图。通过与几种传统配准算法相比较,结果表明,该算法在鲁棒性、配准时间和配准精度方面提供了更好的综合性能。

1 SURF检测及描述

SURF可以在图像尺度空间中提取特征点,并对每个特征点赋予特征,即SURF描述符。该算法提取的特征点对尺度、旋转、光照、仿射和透视变换等均具有较强鲁棒性,并在计算速度上明显快于以往同类方法。

1.1 特征点的检测

SURF是一种基于尺度空间的特征点检测算法。在尺度空间的每一层图像上,SURF使用快速Hessian矩阵来检测图像的极值点。对于尺度为σ的空间中任意一点(x,y),Hessian 矩阵的定义为:

其中,Lxx、Lxy与 Lyy是点(x,y)分别与高斯函数 g(σ)二阶偏导卷积的结果。

为加快SURF检测速度,BAY H等人在尺度图像金字塔中用不同尺寸的框状滤波 Dxx、Dxy与 Dyy代替二阶高斯滤波,用积分图像来加速卷积[8],进一步求解得到Hessian矩阵的行列式作为点(x,y)在尺度 σ空间中的响应值:

其中,ω为权重系数,约等于0.9。

对每个点(x,y),当 Hessian矩阵行列式大于设定的阈值时,就作为待判定点。对每个待判定点上下层与同层的3×3×3的立体领域中进行非极大值抑制,当响应值为局部极大或极小值时,该点被确定为特征点,并经过插值确定位置[9]。

1.2 主方向确定

为保证特征点描述符的旋转不变性,SURF赋予每个特征点主梯度方向。在以特征点为中心,半径为6σ(σ为特征点对应的尺度)的邻域内,用边长为4σ的Haar小波模板计算该点在x、y方向的Haar小波响应,并以该点的高斯函数对这些响应值加权,然后将60°范围内的响应相加形成新的向量,遍历整个圆形区域,选择最长向量的方向为该特征点的主方向。这样,对特征点逐个进行计算,就可以得到每一个特征点的主方向。

1.3 描述子生成

为了构建描述子向量,首先以特征点为中心,将坐标轴旋转到主方向,在新坐标轴中选取边长为20σ的正方形区域,再将该区域划分成4×4个子区域。计算每个子区域内水平方向与垂直方向的Haar小波响应dx与dy,并用特征点为中心的高斯函数对 dx、dy加权,以增加对几何变换的鲁棒性。

在每个子区域中对Haar小波响应以及响应的绝对值求和,形成这样,得到一个四维向量因此,对每一特征点,把4×4个子区域的向量连起来就形成64维的向量,即该特征点的SURF描述子。

2 结合SURF和广义近邻图的图像配准

2.1 算法流程

本文算法流程图如图1所示。

图1 算法流程图

2.2 广义近邻图估计 Rényi熵

Rényi熵 Rα是 Shannon熵 H的广义形式,具有比Shannon熵更为平滑的函数形式,因此在图像配准中受到越来越多的关注。

对于概率分布为 pi的随机变量 X,Rényi熵为:

式(3)通过样本概率来计算熵,但在许多实际问题中,样本概率并不容易获得。为克服这一缺陷,许多研究者从样本的随机分布情况出发,利用样本构成的图结构来描述样本的随机分布。最新的研究结果表明,通过对随机抽样构建广义近邻图可以较精确地估计随机变量的熵,收敛速度快且鲁棒性较好,已在统计学与信息论的研究中受到广泛关注。

广义近邻图是一般的K近邻图的推广,一般记作NNS(V)。 对于顶点集 V,|V|=n,S为某一非空的有限正整数集,k为S中的最大元素值。对每个i∈S和每个顶点x∈V,x与其第i邻近点构成一个边,这些边构成了NNs(V)的边集。

考虑V去除x之后余下顶点的集合 V{x},不妨记为{y1,y2,…,yn-1}。 对 V{x}到顶点 x 的欧式距离排序:则yi就是顶点x的第i邻近点。那么对S中的每个正整数 i,在 NNS(V)就有一个 x 到 yi的边。

PAL D等人最先提出用广义近邻图来描述样本点的空间位置分布,进而估计随机变量的Rényi熵。对欧式空间 Rd上的随机抽样点集 V,用 Lp(V)表示广义近邻图边的欧氏距离p次幂的和:

其中,E(NNS(V))表示 NNS(V)边的集合,p≥0 为参数。在这里,S是固定的有限非空正整数集合,如S={1,3,4}表示取点的 1邻近、3邻近和4邻近。Lp(V)是度量样本分布离散程度的测度。PAL D进一步证明了这一度量与Rényi熵中的样本概率幂的和成正比。通过合理设置比例,得到随机样本集 V 的 Rényi熵 Rα(V)在 α∈(0,1)时的估计:

其中,γ 为常数,p=d(1-α)。

2.3 目标函数的构造

将待配准的两幅图像定义为浮动图像A和参考图像B,分别提取特征点集 V1和 V2,用 64维的 SURF向量描述图像中特征点。每个SURF描述子可看作全像素上的密度函数在64维空间中的一个随机抽样,因此可以用式(5)估计 A 与 B 的 Rényi熵 Rα(A)、Rα(B),并利用点集 V=V1∪V2估计 A 与 B 的联合 Rényi熵 Rα(A,B),然后用 Rényi熵和联合 Rényi熵计算它们之间 Rényi互信息:

其中,Rα(A)与 Rα(B)是由图像自身特征点估计的 Rényi熵。对于单幅图像,事先按照主方向排序的SURF向量经过平移和旋转,其元素按照某一顺序进行统一重排,而元素以同样的顺序进行重排并不影响向量之间的欧式距离计算。因此,在插值影响不大的情况下,可以近似地认为对每幅单独的图像A或B,其特征点集的广义近邻图距 离 Lp(V1)、Lp(V2)在不同的 变换 T 下是不变的。进而,Rényi互信息简化为 MIα(A,B)=-Rα(A,B),配准问题变为求变换 T使 Rα(A,B)最小,互信息最大。

通过式(5)用特征点集V估计 Rα(A,B),在本文中d=64,由 p=d(1-α),式(5)转化为:

最终本文使用式(7)来估计 Rényi熵 Rα(A,B)。 求解最优变换矩阵的过程变转化为:

当A和B完全配准时,其对应的特征点的SURF向量重合或接近,此时构造的广义近邻图会包含大量的较短的边,Lp(V)达到最小;而当 A和 B的对齐度差时,特征点将会呈现更加散布的状态,广义近邻图中会增加许多很长的边,Lp(V)的值就增大。

3 实验结果与分析

为了验证本文提出的结合SURF描述子与广义近邻图的配准算法(GNN-SURF)的有效性,对多幅真实遥感图像进行配准实验。将本方法与传统的基于Shannon互信息 (NMI)的配准算法和形状特征点互信息配准算法(Point-MI)进行比较,在配准准确度、时间与鲁棒性等多项准则上进行实验。实验代码用Matlab编写,实验机器配置为 Inter (R)Dual-Core (TM)2 Quad, E5500 2.80 GHz CPU,4 GB内存。

3.1 配准准确度

取一对待配准的图像A与B分别作为模板图像和浮动图像。用3种比较方法对图像A与B进行配准实验, 得到配准变换参数 (△x′,△y′,△θ′)。 计算配准参数(△x′,△y′,△θ′)与真实参数(△x,△y,△θ)之间误差的绝对值作为配准准确度,结果如表1所示。

表1 配准准确性的比较

从表 1可知,采用特征点的Point-MI与GNN-SURF都要比NMI方法准确,这主要是因为实验中采用的遥感图像成像条件不同,图像内容、灰度差异较大,因此基于像素灰度的NMI方法配准效果最差。此外,Point-MI仅依赖特征点坐标,而GNN-SURF方法融入了图像的空间信息,配准更加准确。

图2是两幅遥感图像配准例子。这两幅图像拍摄位置不同,图像内容仅有部分重合,特征点提取的数目与位置都不同(图 2(a)、(b))。 然而在两幅图重合的部分中,图 2(a)中的特征点与图 2(b)中特征点是完全对应的,因此,配准时(图 2(d))的广义近邻图在中间重合部分比未配准之前(图 2(c))的结构简单、清晰得多,对应点之间的连线使得SURF向量距离和最小,从而达到整体最优配准。

图2 配准前后广义近邻图比较

3.2 配准鲁棒性与时间

为了比较配准鲁棒性,先对浮动图像进行随机平移和旋转变换,平移参数(△x,△y)分别在[-20 mm,20 mm]中随机选择,旋转参数(△θ)在[-20°,20°]中随机选择,共同构成初始误配参数(△x,△y,△θ),总共选择 50 个初始误配参进行试验。对每次实验结果计算平移和旋转的误差。根据常用评估标准[10],当平移误差小于1个像素、旋转误差小于1°时,认为配准达到了亚像素级,配准成功。

表2给出了3种比较方法的配准成功率和配准时间。从表2可知,GNN-SURF方法的成功率最高,而NMI方法效果最差。在配准时间上,NMI方法需要计算两幅图像的所有像素,耗时最久;Point-MI虽然只需要计算图像特征点的坐标信息,但其定义的特征点集Rényi互信息函数形式过于复杂,增加了配准时间。而本文提出的GNN-SURF方法融合了快速计算鲁棒特征点空间信息的SURF描述子,同时采用了广义近邻图估计Rényi熵,在配准鲁棒性与配准时间上都明显优于其他两种方法。本文提出了一种结合SURF描述子和广义近邻图的图像配准算法。采用SURF快速、鲁棒地提取图像特征点,并形成特征点描述子,再结合特征点的广义近邻图估计Rényi互信息进行配准。在真实遥感图像中进行实验,结果表明该算法在配准鲁棒性、配准准确性和配准时间3个方面都优于另外两种传统图像配准方法。

表2 配准鲁棒性与配准时间的比较

[1]ZITOVA B, FLUSSER J.Image registration methods: a survey[J].Image and Vision Computing, 2003, 21:977-1000.

[2]赵仕俊,孙林港.基于纹理特征的图像自动配准方法研究[J].微型机与应用,2011,30(9):36-38.

[3]李靖宇,穆伟斌,沈焕泉.医学图像配准的优化算法改进研究[J].微型机与应用,2010(8):47-49.

[4]COLLIGNON A, MAES F, DELAERE D, et al.Automated muhimodality medical image registration using information theory[C].Proceedings of Information Processing in Medical Imaging, 1995:263-274.

[5]BAY H,TUVTELLARS T,GOOL L VAN.SURF:speeded up robust features[C].Proceedings of the European Conference on Computer Vision, 2006:404-417.

[6]RANGARAJAN A, Chui Haili, DUNCAN J S, et al.Rigid point feature registration using mutual information[J].Medical Image Analysis,1999,3(4):425-440.

[7]PAL D, POCZOS B, SZEPESVARI C.Estimation of Rényi entropy and mutual information based on generalized nearestneighbor graphs[C].NIPS,2010.

[8]VIOLA P,JONES M J.Rapid object detection using a boosted cascade of simple features[C].Proceedings of Computer Vision and Pattern Recognition, 2001:511-518.

[9]BROWN M,LOWED.Invariant features from interest point groups[C].BMVC, 2002:1-10.

[10]LUAN H X,QI F H,XUE Z,et al.Multimodality image registration by maximization ofquantitative-qualitative measure of mutual information[J].Pattern Recognition, 2008,41:285-298.

猜你喜欢
互信息鲁棒性广义
Rn中的广义逆Bonnesen型不等式
荒漠绿洲区潜在生态网络增边优化鲁棒性分析
基于确定性指标的弦支结构鲁棒性评价
从广义心肾不交论治慢性心力衰竭
王夫之《说文广义》考订《说文》析论
基于改进互信息和邻接熵的微博新词发现方法
广义RAMS解读与启迪
基于非支配解集的多模式装备项目群调度鲁棒性优化
非接触移动供电系统不同补偿拓扑下的鲁棒性分析
基于互信息的贝叶斯网络结构学习