结合Harris与SIFT算子的图像快速配准算法

（1.中国科学院航空光学成像与测量重点实验室，吉林 长春 130033；2.中国科学院长春光学精密机械与物理研究所，吉林 长春 130033）

（1.中国科学院航空光学成像与测量重点实验室，吉林 长春 130033；2.中国科学院长春光学精密机械与物理研究所，吉林 长春 130033）

本文提出了一种结合Harris与SIFT算子的快速图像配准方法。首先，对Harris算法进行两方面的改进：一是构建高斯尺度空间，提取具有尺度不变性的角点特征；二是采用Forsnter算子对提取的角点精定位，提高配准精度。然后，利用SIFT算子的特征描述方法描述提取到的特征点，通过随机kd树算法对两幅影像的特征点进行匹配。最后采用RANSAC算法对匹配点对进行提纯，并通过最小二乘法估计两幅影像间的空间变换单应矩阵，完成图像配准。实验结果表明：本文方法在基本保持配准精度的同时，在配准过程的时间消耗上比标准SIFT算法减少了64％。

图像配准；多尺度Harris算子；SIFT；RANSAC

1 引言

基于特征的配准方法的首要任务是进行特征点检测及匹配。SIFT是目前公认的最为鲁棒的特征匹配算子，它是由Lowe［1］在总结了现有基于不变量技术特征提取方法基础上提出的一种基于尺度空间的局部特征描述算子。SIFT具有尺度不变性、旋转不变性及光照不变性等诸多优点，但其存在一个巨大缺陷——运算复杂，处理速度慢，难以处理大幅面影像或进行实时应用［2］。在其它的特征检测算子（如Maravec算子、Harris算子、Susan算子等）中，Harris角点检测算法计算简单、稳定且不受光照、旋转、噪声等影响，具有最好的检测效果［3-5］。但是Harris算子不具有尺度不变性，而且在角点定位方面存在偏差，可能导致匹配不准确，难以精确配准。

本文结合Harris角点检测和SIFT特征描述的优点，采用多尺度Harris算子检测图像角点特征，并利用Forstner算子思想对角点精定位，然后使用SIFT特征描述方法进行特征描述和匹配；最后利用获得的匹配点对采用最小二乘法计算图像变换参数，完成图像配准。

2 改进的Harris角点检测算法

Harris角点检测算法是由Chris Harris和Mike Stephens提出的一种基于信号的点特征提取算法。该算法利用Taylor级数展开法扩展了Moravec算法的思路，计算窗口沿任意方向移动后的灰度变化趋势，进而利用数学解析式检测出角点［6］。目前针对Harris的改进算法有很多，大部分集中在多尺度与精定位两方面。

2.1 快速多尺度Harris角点检测

本文引入高斯尺度空间思想以解决Harris算法不具有尺度不变性的缺点，提取具有尺度信息的Harris角点信息。

陈小华：基本上这个行业里大部分创业者都认识，往往他们做不下去的都会来找我们沟通，姚劲波（58集团CEO）还经常感叹悲剧一再重演。很多创业者会和我们说，你再给我一个亿我就能干到一百亿，因为我这个模式实在太好了。但我们在这个时候往往有一种无力感，这个教训只有自己走过才能算教训，别人提醒，你还会觉得是不是别人看我收入这么多眼红？这种案例很多，我们会建议一些公司在现金为零的时候停止，出售企业或者放缓节奏，活下来就好。但是这些企业往往会进行最后一搏，就是去让用户充值，等到了不得不去找投资人救市的时候，这些公司就不仅是一个价值为零的公司，而是一个负数，一个非常大的坑，没有投资人会愿意进来。

高斯尺度空间是采用不同尺度的高斯卷积核对图像进行卷积得到的［7］，如图1所示。因此，一幅图像的高斯尺度空间可以表示为：

图1 高斯尺度空间Fig.1 Gaussian scale-space

运用高斯尺度空间的概念，预先定义一组尺度：{σ1，…，σi}={σ0，…，kiσ0}，相应地，多尺度Harris算子的二阶矩可以改写为：

经典的Harris角点检测算法采用的角点响应函数CRF为：

式中，gx、gy分别为x、y方向上的梯度；λ1、λ2是矩阵M的特征值；k为常数项，它的取值通常是凭经验确定的，范围在0.04～0.06。但在实际应用中，靠经验选取k值往往会使结果存在偏差，影响后续的配准拼接效果。因此，为了避免k值的选取，引入新的角点响应函数［8］，考虑到多尺度特征，其表示如下：

式中，ε为一极小量（可取ε=10—6），以防止分母为零时出现异常。

多尺度Harris算法需要在多个尺度上检测角点，计算量比传统算法大大增加，因此本文参考王葳等人［9］提出的8邻域相似像素数目分析法，在图像进行梯度运算之前先剔除部分非角点；如图2所示，对于目标像素点I（x，y），通过计算与8邻域范围内像素点I（x+j，y+i）灰度差的绝对值，并与设定的阈值（记为T）相比较来确定该点是否可能为角点。以函数Num（x，y）表示邻域相似点数目的公式表达如下：

式中：

当Num（x，y）在［2，6］时，该点可能为角点，将进一步计算其角点响应函数以确定是否为角点。

图2 8邻域相似像素分析Fig.2 Similarity operation within 8 neighborhood pixels

2.2 Harris角点精定位

传统Harris算法获得的均是整数级像素坐标，而且使用CRF局部非极大值抑制法忽略了周围可能存在相似角点簇的影响，使得角点检测易受噪声影响，导致角点定位存在偏差［10］。本文借鉴Forstner算子思想对Harris角点进行精定位。

Forstner算子是摄影测量中经典的兴趣点定位算子，其特点是精度高、速度快。基本思想是：首先获得候选角点，然后以该点为中心建立最佳窗口，对最佳窗口内通过每个像素的边缘直线（垂直于梯度方向）进行加权中心化，得到角点的精确坐标［11］。

利用Harris算子提出的角点作为Forstner算子的最佳窗口中心点，在窗口内进行加权中心化精确定位角点坐标的具体计算原理如下：

最佳窗口内任一像素（x，y）的边缘直线l的方程可以表示为：

式中，ρ为原点（最佳窗口的左上角像素）到直线l的距离，θ为梯度角，tanθ=gy/gx，gy、gx为该点的robert梯度。设角点坐标为（x0，y0），v是点（x，y）到直线l的垂直距离，在（x，y）处的误差方程为：

式（8）的含义是：将原点到边缘直线的距离视为观测值，而边缘直线的方向保持不变，权w（x，y）是梯度模的平方，因此，权的实质即是该边缘尺度。对式（8）法化，得到法方程：

对式（9）求解，即可得到精确角点坐标（x0，y0）。

3 图像配准

3.1 特征描述与匹配

为了获得稳定准确的匹配效果，本文借鉴SIFT方法对提取的角点进行特征描述与匹配。SIFT特征描述方法分为四步：构建尺度空间检测极值；关键点精确定位；确定关键点主方向；生成关键点描述向量。本文中，角点检测与精定位已由其它方法完成，因此只需确定角点的主方向并生成描述子即可，具体过程请参考文献［1，12-14］。

完成特征描述之后，就要进行特征点匹配，即找出两幅影像特征点之间的对应关系。针对SIFT描述字的高维特点，本文采用Silpa-Anan［15］等人提出的随机kd树算法进行特征点搜索。

3.2 图像配准

图像配准是将一幅图像作为参考，对另一幅图像进行几何变换，使图像之间的重叠区在空间上对准。几何变换的实质是确定图像间的对应关系模型，因此，一旦确定了图像间的关系模型，那么图像配准即转化为确定图像之间对应关系模型的参数过程。目前常用的关系模型主要有刚性变换模型、仿射变换模型、投影变换模型等。

针对目前的应用需求，图像间一般存在旋转、平移、缩放变换，因此采用具有8参数的投影变换模型基本上可以满足需求。图像间的投影变换可用矩阵表示如下：

式中：（x1，y1，1）、（x2，y2，1）分别为参考图像和待变换图像对应特征点的齐次坐标，（h0，…，h7）为间接投影变换参数。

式（10）有8个未知参数，至少需要4对特征点对建立方程组解求变换参数。为了获得准确的变换参数，本文首先采用RANSAC算法［16］对匹配点对进行提纯，去除误匹配点；然后建立误差方程，利用最小二乘法解求变换参数［17］。

4 实验及分析

为了验证本文算法的配准效果以及速度上的优势，选取几种不同平台的图片进行配准实验。实验中，仿真平台硬件环境为：Intel（R）Core（TM）i5-3337U CPU，1.8GHz，4G内存的PC机；软件开发工具为Window 8 64位操作系统，VS2010编程环境。实验所用的图像均为实拍影像。图3中（a）、（b）为手持单反相机拍摄的市区影像，大小为2 464pixel×1 632pixel，（c）、（d）为城郊地区的航空影像，大小为1 024pixel×720pixel，（e）、（f）为QuickBird拍摄的不同时期的某市郊区影像，大小为510pixel×472pixel。

图3 3组测试图片Fig.3 Three groups of testing images

首先，通过实验对比以证明本文方法在特征点检测时间上相较于SIFT的优势。分别采用本文提出的Harris-SIFT算法以及标准SIFT算法与SURF算法对图3中的三组图像进行特征点检测比较实验，3种方法的时间统计结果见表1。结果表明，采用Harris算法进行特征检测确实具有明显的时间优势：在图3的三组测试图像中，Harris特征检测时间比标准SIFT至少减少了42％，最多减少量达到了79％，其特征提取速度基本达到了SURF算法的水平。这是因为多尺度Harris不需要构造太复杂的尺度空间，所需计算的像素量大大减少，节省了相当一部分计算时间。另外，通过比较本文方法与标准SIFT算法所提特征点在图像中的分布（见图4）可以看出，采用本文方法所获得的特征点数量虽然少，但在图像中分布均匀，并不过密，这也节省了后续匹配过程的时间消耗。

表1 分别用本文方法以及SIFT、SURF进行特征点检测的时间统计Tab.1 Statistics of cost time for feature points detection using SIFT，SURF and the proposed method

图4 特征点分布比较Fig.4 Comparison of feature points distribution

然后，通过实验证明在保证配准正确率的前提下，本文提出的多尺度Harris-Sift算法相对于标准SIFT在整体配准速度上的提高。利用2种方法对图3中的3组测试图象进行特征点匹配的正确率与时间统计对比见表2、表3、表4。

表2 本文方法特征点匹配的正确率和时间统计Tab.2 Statistics of accuracy and cost time of feature points matching using the proposed method

表5 使用不同方法对图3（c）和图3（d）进行配准的精度对比Tab.5 Comparison of registration accuracy for Fig.3（c）and Fig.3（d）using different methods

最后，统计所有匹配点对变换后坐标与参考坐标间的均方根误差RMSE以定量的评价配准精度，公式表示如式（11）［18］。

式中，pi和q是匹配点对变换前后的坐标，k为最终匹配点对个数。

图5 图3（c）和图3（d）匹配结果及配准结果Fig.5 Results of（a）feature matching and（b）registration for Fig.3（c）and Fig.3（d）

图5是特征匹配和图像配准结果，表5为使用不同方法对图3（c）和图3（d）进行配准的精度对比，在保证配准正确率的前提下，本文提出的改进Harris-SIFT算法比标准SIFT算法在整体配准过程的时间消耗上减少了64％。

5 结论

本文针对SIFT算法匹配速度慢的问题，提出了改进Harris算法与SIFT算子相结合的快速图像配准方法。该方法以Harris角点检测代替SIFT算法的极值检测部分，同时为了保证特征点的尺度不变性，对Harris进行了改进。首先建立高斯尺度空间，检测具有尺度信息的Harris角点，，然后利用摄影测量学中的Forstner算子思想对角点进行精定位，最后采用SIFT描述符对角点进行描述，利用RANSAC法以及随机K-D树算法完成特征点匹配。实验表明，该算法比标准SIFT算法在整体配准过程的时间消耗上减少了64％，是一种快速鲁棒的图像配准算法。

［1］LOWE D.Distinctive image features from scale-invariant keypoints［J］.International J.Computer Vision，2004，60（2）：91-110.

［2］贾平，徐宁，张叶.基于局部特征提取的目标自动识别［J］.光学 精密工程，2013，21（7）：1898-1905.

JIA P，XU N，ZHANG Y.Automatic target recognition based on local feature extraction［J］.Opt.Precision Eng.，2013，21（7）：1898-1905.（in Chinese）

［3］CORDELIA S，ROGER M，CHRISTIAN B.Evaluation of interest point detectors［J］.International J.Computer Vision，2000，37（2）：151-272.

［4］刘志文，刘定生，刘鹏.应用尺度不变特征变换的多源遥感影像特征点匹配［J］.光学 精密工程，2013，21（8）：2146-2153.

LIU Z W，LIU D S，LIU P.SIFT feature matching algorithm of multi-source remote image［J］.Opt.Precision Eng.，2013，21（8）：2146-2153.（in Chinese）

［5］余先川，吕中华，胡丹.遥感图像配准技术综述［J］.光学 精密工程，2013，21（11）：2960-2972.

YU X CH，LV ZH H，HU D.Review of remote sensing image registration techniques［J］.Opt.Precision Eng.，2013，21（11）：2960-2972.（in Chinese）

［6］CHRIS H，MIKE S.A combined corner and edge detector［A］.In Proceedings of the 4th Alvey Vision conference［C］，Manchester.United Kingdom：the University of Sheffield Printing Unit，1988.

［7］王国栋，徐洁，潘振宽，等.基于归一化超拉普拉斯先验项的运动模糊图像盲复原［J］.光学 精密工程，2013，21（5）：1340-1348.

WANG G D，XU J，PAN ZH K，et al..Blind image restoration based on normalized hyper laplacian prior term［J］.Opt.Precision Eng.，2013，21（5）：1340-1348.（in Chinese）

［8］ROCKETT P I.Performance assessment of feature detection algorithms a methodology and case study on corner detectors［J］.IEEE Transactions on Image Processing，2003，12（12）：1668-1676.

［9］王葳.一种改进的Harris角点提取算法［J］.光学 精密工程，2008，16（10）：1995-2001.

WANG W.An improved algorithm for Harris corner detection［J］.Opt.Precision Eng.，2008，16（10）：1995-2001.（in Chinese）

［10］何海清，黄声享.改进的Harris亚像素角点快速定位［J］.中国图象图形学报，2012，17（7）：853-857.

HE H Q，HUANG SH X.Improved algorithm for Harris rapid sub-pixel corners detection［J］.J.Image and Graphics，2012，17（7）：853-857.（in Chinese）

［11］FORSTNER W，GULCH E.A fast operator for detection and precise location of distinct points，corners and centres of circulat features［C］.Proceeding of the ISPRS，In Proceeding of Intercommission Workshop on Fast Processing of Photogrammetric Data，Interlaken Switzerland，1987：281-305.

［12］程德志，李言俊，余瑞星.基于改进SIFT算法的图像匹配方法［J］.计算机仿真，2011，28（7）：285-289.

CHENG D ZH，LI Y J，YU R X.Image matching method Based on Improved SIFT algorithm［J］.Computer Simulation，2011，28（7）：285-289.（in Chinese）

［13］刘立，彭复员，赵坤，等.采用简化SIFT算法实现快速图像匹配［J］.红外与激光工程，2008，37（1）：181-184.

LIU L，PENG F Y，ZHAO K，et al..Simplified SIFT algorithm for fast image matching［J］.Infrared and Laser Engineering，2008，37（1）：181-184.（in Chinese）

［14］刘小军，杨杰，孙坚伟，等.基于SIFT的图像配准方法［J］.红外与激光工程，2008，37（1）：156-160.

LIU X J，YANG J，SUN J W，et al..Image registration approach based on SIFT［J］.Infrared and Laser Engineering，2008，37（1）：156-160.（in Chinese）

［15］SILPA-ANAN C，HARTLEY R.Optimised KD-trees for fast image descriptor matching［C］.In Computer Vision and Pattern Recognition，2008（CVPR 2008），23-28 June 2008，Anchorage，AK，2008：1-8.

［16］FISCHLER M A，BOLLES R C.Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography［J］.Commun.ACM，1981，24（6）：381-395.

［17］赵立荣，朱玮，曹永刚，等.改进的加速鲁棒特征算法在特征匹配中的应用［J］.光学 精密工程，2013，21（12）：3263-3271.

ZHAO L R，ZHU W，CAO Y G，et al..Application of improved SURF algorithm to feature matching［J］.Opt.Precision Eng.，2013，21（12）：3263-3271.（in Chinese）

［18］丁南南，刘艳滢，张叶，等.基于SURF-DAISY算法和随机kd树的快速图像配准［J］.光电子·激光，2012，2（7）：1395-1402.

DING N N，LIU Y Y，ZHANG Y，et al..Fast Image registration based on SURF-DAISY algorithm and randomized kd trees［J］.J.Optoelectronics·Laser，2012，2（7）：1395-1402.（in Chinese）

许佳佳（1986—），男，河南信阳人，硕士，助理研究员，2012年于武汉大学获得硕士学位，主要从航空图像拼接方面的研究。E-mail：xujia_whu@163.com

结合Harris与SIFT算子的图像快速配准算法

许佳佳1，2

Fast image registration method based on Harris and SIFT algorithm

XU Jia-jia1，2
（Key Laboratory of Airborne Optical Imaging and Measurement，hinese Academy of Science，Changchun 130033，China； 2.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Science，Changchun 130033，China）
*Corresponding author，E-mail：xujia_whu@163.com

A new method for fast image registration based on improved Harris-Sift algorithm is proposed.Firstly，classic Harris algorithm is improved by building Gaussian scale space to extract scale invariant Harris corners and they are refined to sub-pixel corners using Forsnter algorithm.Then the SIFT descriptor is utilized to characterize those feature points and the matching procedure is carried out via randomized kd trees.At last，RANSAC is used to remove wrong matches and the optimal transform parameters are estimated using the least square method to accomplish the image registration process.The experimental results demonstrate that compared with the classic SIFT algorithm the proposed method decreases the cost time of the registration procedure mostly by 64％while almost keeping the same performance.

image registration；multiple scale Harris operator；SIFT；RANSAC

吉林省重大科技攻关资助项目（No.11ZDGG001）

2095-1531（2015）04-0574-08

TP391 文献标识码：A doi：10.3788/CO.20150804.0574

2015-02-18；

2015-03-22