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

孙登第 ，罗 斌 ，卜令斌

（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.