基于FAST和SURF的图像配准算法

安维胜，余让明，伍玉铃

（西南交通大学机械工程学院，成都 610031）

该特征点，否则就舍弃。

基于FAST和SURF的图像配准算法

安维胜，余让明，伍玉铃

（西南交通大学机械工程学院，成都 610031）

尺度不变特征变换（SIFT）和加速鲁棒特征（SURF）方法在进行角点检测和特征点匹配时的时间较长。为此，提出一种改进的图像配准算法。建立参考图像与待配准图像的高斯图像金字塔，在金字塔各层图像进行检测，得到具有不同尺度的加速分割测试特征（FAST）点，采用SURF算法为各特征点分配方向，并计算各特征点的描述向量，使用快速近似最近邻搜索算法获取图像间的初始匹配点对，用随机抽样一致性算法剔除误匹配点对，同时得到2幅图像之间的几何变换矩阵。实验结果表明，与SURF算法和SIFT算法相比，该算法的特征检测速度和匹配速度较快，匹配正确率较高。

图像配准；加速分割测试特征；加速鲁棒特征；近似最近邻；随机抽样一致性

DO I：10.3969/j.issn.1000-3428.2015.10.043

1 概述

图像配准是对不同时间、不同视角或不同传感器拍摄的2幅或多幅图像进行空间变换处理，使各图像在几何上相互对应［1］。其应用范围相当广泛，包括计算机视觉和模式识别（如图像分割、三维重建、目标识别、运动跟踪与估计等）、医学图像分析、遥感图像处理、图像融合、全景图像拼接［2］等。图像配准方法大致可分为2类：基于区域的配准方法和基于特征的配准方法［3］。

基于区域的配准方法计算简单、速度快，但是对存在较大噪声的图像或者待配准图像的重叠部分较少时，配准效果不理想，且易受光照变化的影响。基于特征的配准方法将对整个图像的各种分析转化为对图像特定特征的分析，大大减小了图像处理过程的运算量，且对灰度变化、图像变形以及遮挡等都有较好的适应能力［4］，其应用越来越广泛。

文献［5-6］提出的尺度不变特征变换（Scale

Invariant Feature Transform，SIFT）算法对图像旋转、缩放、光照变化保持不变性，对视角变化、仿射变换、噪声也保持一定的稳定性，但SIFT算法的特征检测、特征描述符的生成与匹配计算量很大，速度较慢，不适合实时应用。为提高特征提取速度，文献［7］提出了加速鲁棒特征（Speeded-up Robust Feature，SURF）算法，它是对SIFT算法的一种改进，它通过计算积分图像和Fast Hessian矩阵大大提高了特征点检测的速度，但采用全局最近邻搜索进行特征匹配，计算量大、匹配速度慢。文献［8］提出加速分割测试特征（Features from Accelerated Segment Test，FAST）提取算法，该算法角点检测速度很快，但易受噪声干扰和光照变化影响，不具备尺度不变性。文献［9］提出基于SURF和快速近似最近邻搜索算法的图像匹配方法，提高了SURF算法的匹配正确率和实时性。文献［10］采用FAST角点检测、SURF描述向量和最佳值优先（Best-Bin First，BBF）搜索匹配点的方法进行棉花图像的匹配。

本文在前人工作的基础上，研究了FAST和SURF特征检测原理，通过FAST检测可能的特征角点，使用Hessian检测子提取特征，然后采用SURF特征描述和快速近似最近邻搜索匹配对的方法实现图像的配准。

2 图像配准实现流程

基于特征的图像配准主要有特征检测、特征匹配、变换模型估计和图像重采样与几何变换［3］。特征检测和特征匹配是基于特征的配准方法的2个关键步骤。本文提出采用FAST特征检测、SURF特征描述和快速近似最近邻搜索的图像配准算法，其实现过程如图1所示。

图1 图像配准算法流程

3 特征点检测

特征点检测是查找和定位图像中的具有代表性的像素点或者与周围像素迥异的斑点等，是图像配准的基础。FAST角点检测算法不具备尺度不变性，因此，本文建立原始图像的高斯金字塔，对每一层图像提取FAST特征点。为提高算法的光照不变性，对光照变化较大的原始图像进行直方图均衡化处理。

3.1 高斯图像金字塔建立

文献［11］表明在某些合理的假设条件下高斯函数是唯一的实现尺度变换的线性核。用函数L（χ，y，σ）表示一幅二维图像 I（χ，y）的尺度空间为：

其中，⊗表示卷积运算；G（χ，y，σ）是尺度可变的高斯函数，其定义为：

其中，σ为尺度因子，表示图像被平滑的程度，σ越大图像越模糊。

为了提高算法效率，本文建立3组3层高斯金字塔，共9层图像。经过实验比较，图像金字塔的第0组0层图像平滑尺度σ0=1.4，任意层与0层之间的尺度关系为σs=σ0ks，相邻层间尺度因子k= 21/S，S为每组总层数3，s为金字塔中图像的层序数，s=｛0，1，…，9｝。每组的第一层图像由前一组的最后一层图像下采样得到，因此，每组增加1层图像，但不进行特征点检测。为了获取更多的特征点，可将原始图像放大2倍作为第0组图像。

3.2 FAST角点检测

FAST算法通过检测中心点与周围像素点的明暗程度来确定中心点是否是特征点，由于计算简单使FAST算法速度快。

在以侯选像素点P为中心，半径为3的Bresenham圆上共有16个像素点，对圆周上每一个像素点χ（χ∈｛1，2，…，16｝）逐一检测，按照式（3）的规则判断测试点是亮点、暗点还是相似点。点χ与点P亮度比较结果如下：

其中，d，b，s分别表示暗点集、相似点集和亮点集；IP表示点P的亮度灰度值；Iχ表示点χ的亮度灰度值；t为亮度阈值。

如果有n个连续的像素点（图2中的虚线），属于亮点（或暗点），那么点P属于角点。

文献［8］表明n取9检测特征的可重复性最好。由于FAST没有角点响应函数，且具有很大的边缘响应，本文在检测FAST特征点时使用Hessian矩阵去除不稳定的边缘响应，并采用Harris角点响应函数值对FAST特征点进行排序。若想得到N个关键点，先降低阈值得到多于N个点，然后根据Harris响应值取前N个点。

Hessian矩阵H的公式为：

其中，Dχχ，Dχy，Dyy是候选角点处的二阶偏导数，通过附近区域的差分近似计算。由于D的主曲率和 H的特征值成正比，为了避免直接计算这些特征值，而求其比率ratio。令α为最大特征值，β为最小的特征值，α=rβ，则：

该特征点，否则就舍弃。

4 SURF特征描述

4.1 主方向确定

为使特征点描述子具有旋转不变性，需要对每个特征点分配主方向。首先计算以某个特征点为圆心，6s（s为特征点对应的尺度）为半径的圆形邻域内所有点在χ和y方向上的Haar小波响应，Haar小波边长为4s，取样步长为s。然后给响应值赋以特征点为中心的高斯（σ=2.5）权重系数。接下来以χ方向的响应为横坐标，以 y方向的响应为纵坐标，取60°的扇形区域作为滑动窗口，使用该窗口以5°为步长旋转遍历整个圆形邻域，分别计算在每个角度下该扇形区域内所有点在χ和y方向的Haar小波响应和，生成一个局部的方向向量，选择所有窗口中最长的向量方向作为该特征点的主方向。

4.2 特征描述向量的生成

以特征点为中心构建边长为 20s的正方形区域，旋转该区域使之与特征点的主方向平行，沿主方向将该区域划分为4×4个子区域，每个子区域有5s×5s个像素点，计算每个子区域内每个像素点在χ方向（平行于主方向）和y方向（垂直于主方向）的Haar小波响应值，Haar小波边长为2s，分别记为dχ，dy。为增加对几何变换的鲁棒性，对dχ和dy赋以特征点为中心的高斯（σ=3.3s）权重系数。然后把每个子区域内的Haar小波响应值及响应值的绝对值相加得到这样，在每个子区域得到一个四维向量：

对每个特征点，就产生了一个4×4×4=64维的SURF特征描述向量，再对描述向量进行归一化处理以获得对比度不变性。

5 特征匹配

特征匹配的目的是根据参考图像和待配准图像在提取的特征及其属性信息，求出反映2幅图像之间几何变化关系的最优变换模型参数。本文以特征点描述向量之间的欧氏距离作为特征点的相似性度量。SURF特征向量是高维向量，虽然采用穷举搜索最近邻的匹配方法得到的最近邻结果较准确，但搜索速度慢。文献［12］对计算机视觉中高维向量的近似最近邻匹配算法进行了比较，提出对于高维空间中的最近邻搜索问题，采用分层k-means树和多重随机k-d树具有较好的性能，并且实现了根据用户输入数据和期望的精度自动选择最佳算法和参数值的算法。本文采用快速近似最近邻搜索算法进行特征的搜索，其实现过程基于目前流行的OpenCV的FLANN（Fast Library for Approximate Nearest Neighbors）库。

首先采用FLANN搜索算法从待配准图像中找出与参考图像的欧氏距离最近和次近的2个点，以最近欧氏距离与次近欧氏距离的比值同给定的阈值T比较来判定特征点是否匹配。阈值T通常为0.4～0.8，阈值越大匹配点数越多，但匹配正确率会降低。

经过欧氏距离匹配后的匹配点对仍会存在错误匹配的情况，需对初始匹配结果进行去误提纯。本文采用随机抽样一致性（Randomized Sample Consensus，RANSAC）算法剔除误匹配对。

6 实验结果与分析

图像配准的目的是找到待配准图像间的变换关系，图像间的变换通常有刚体变换、仿射变换和透射变换。透射变换只要给定 4对点就可获得图像间的单应性矩阵。众所周知，需要处理的数据越

少算法的总体时间消耗就少。本文通过设定合理的阈值来得到一定数量的特征点和匹配点对，并获得图像间的单应性矩阵，以进行不同算法的性能比较。

6.1 实验环境

本文实验环境为Intel Core i3-2310@2.10 GHz，内存2 GB。实验所用测试图像均为现实场景图像，来自Mikolajczyk和Schmid提供的一组图像数据集。FAST角点检测亮度阈值t=20，图像匹配的最近与次近欧氏距离比值阈值T=0.5。

6.2 结果分析

以 boat图像为例，图像分辨率大小为 850× 680像素，图像间具有尺度和旋转变化，分别使用本文算法、SURF算法和SIFT算法进行特征检测及匹配，通过设置阈值提取适量的角点，检测结果如表1所示，匹配结果如表2所示，检测时间为5次实验平均值。

表1 角点检测时间比较

表2 特征匹配性能比较

从表1和表2可以看出，本文算法与SURF和SIFT算法相比，特征点检测速度更快，匹配时间更短。SIFT和SURF特征点的检测定位通过搜索尺度空间局部三维极值点来确定特征点的位置和尺度，定位效果好，但计算复杂运算量大。FAST角点检测依据像素点亮度差值，不像SURF和SIFT需要大量的计算过程，因此，速度更快。本文采用 SURF的64 bit浮点描述向量，其生成与匹配过程中的计算量比SIFT的128 bit描述向量的计算量小，因此，速度比SIFT快很多。同时，本文采用快速近似邻搜索方法进行特征点的匹配，速度比全局最近邻搜索方法快很多。虽然匹配点数量较少，但其正确率比较高。总的来说，在相同的匹配阈值条件下，SIFT算法的匹配正确率最高，本文算法次之，SURF算法的匹配正确率最低，但SURF算法的匹配数量较本文算法多。SIFT算法定位精度好，但总匹配时间长，不适用于实时应用场合。

本文算法对视角变化、尺度和旋转、光照变化等情况也进行了匹配实验，实验结果如图 3所示。图3（a）、图3（b）为光照变化的情况，图3（b）对右图进行了直方图均衡化处理，可以看出，处理后匹配特征点数量更多，分布更均匀。图3（c）为尺度和旋转变化的情况，图3（d）中待匹配图像与匹配图像为不同视角下拍摄所得。从图3中可见本文算法对于视角变化、尺度和旋转、光照变化等具有一定的不变性。

图3 不同变化情况下的匹配结果

7 结束语

本文基于FAST特征检测、SURF特征描述向量和快速近似最近邻搜索方法，提出一种快速的图像配准算法。实验结果表明，该算法对图像的视角变化、尺度变化和旋转以及光照变化等具有不变性，特征点提取速度快、匹配正确率高，可用于对实时性要求高、存在尺度变化和旋转、光照变化以及视角变化不大的图像匹配。下一步将实现本文算法阈值的自适应调整，并用于图像拼接。

［1］ 陈秀新，邢素霞.图像/视频检索与图像融合［M］.北京：机械工业出版社，2012.

［2］ Brown M，Low e D G.Automatic Panoramic Im age Stitching Using Invariant Features［J］.International Journal of Computer Vision，2007，74（1）：59-73.

［3］ Zitová B，Flusser J.Image Registration Methods：A Survey［J］.Image and Vision Computing，2003，21（11）：977-1000.

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

［5］ Lowe D G.Object Recognition from Local Scaleinvariant Features［C］//Proceedings of the 7th IEEE International Conference on Computer Vision. Washington D.C.，USA：IEEE Press，1999：1150-1157.

［6］ Lowe D G.Distinctive Image Features from Scaleinvariant Keypoints［J］.International Journal of Computer Vision，2004，60（2）：91-110.

［7］ Bay H，Ess A，Tuytelaars T，et al.SURF：Speeded-up Robust Features［J］.Computer Vision and Image Understanding，2008，110（3）：346-359.

［8］ Rosten E，Porter R，Drummond T.Faster and Better：A Machine Learning Approach to Corner Detection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1）：105-119.

［9］ 赵璐璐，耿国华，李 康，等.基于SURF和快速近视最近邻的搜索的图像匹配算法［J］.计算机应用研究，2013，30（3）：921-923.

［10］ 时 颢，赖惠成，龚金辉，等.基于SURF和BBF的棉花图像匹配算法［J］.江苏农业科学，2014，42（3）：343-346.

［11］ Lindeberg T.Scale-space Theory：A Basic Tool for Analysing Structures at Different Scales［J］.Journal of Applied Statistics，1994，21（2）：224-270.

［12］ Muja M，Low e D G.Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration［C］// Proceedings of the 4th International Conference on Computer Vision Theory and Application.Lisboa，Portugal：INSTICC Press，2009：331-340.

编辑 刘 冰

Image Registration Algorithm Based on FAST and SURF

AN Weisheng，YU Rangming，WU Yuling
（School of Mechanical Engineering，Southwest Jiaotong University，Chengdu 610031，China）

For Scale Invariant Feature Transform（SIFT）and Speeded-up Robust Feature（SURF）needing a long time in the corner detecting and feature points matching，an improved image registration algorithm is put forward.A Gaussian scale pyramid of the reference image and the matching image are established.Feature points which have different scale information are detected from each level in the image pyramid.It gets Features from Accelerated Segment Test（FAST）point with different scales.An orientation is assigned to every feature point，and feature vector is calculated by using the same way as SURF.The original matching points which have minimum Euclidean distance under some condition are determined through fast approximate nearest neighbor search.The false matching points are excluded by Randomized Sample Consensus（RANSAC）algorithm，and the transformation matrix is gained.Experimental results show that the algorithm is better than SURF and SIFT in feature detection speed and matching speed，and matching accuracy is higher.

image registration；Features from Accelerated Segment Test（FAST）；Speeded-up Robust Feature（SURF）；Approximate Nearest Neighbor（ANN）；Randomized Sample Consensus（RANSAC）

安维胜，余让明，伍玉铃.基于FAST和SURF的图像配准算法［J］.计算机工程，2015，41（10）：232-235，239.

英文引用格式：An Weisheng，Yu Rangming，Wu Yuling.Image Registration Algorithm Based on FAST and SURF［J］. Computer Engineering，2015，41（10）：232-235，239.

1000-3428（2015）10-0232-04

A

TP391

中央高校基本科研业务费专项基金资助项目（2682013CX024）。

安维胜（1974-），男，副教授、博士，主研方向：计算机图形学，虚拟现实；余让明、伍玉铃，硕士研究生。

2014-09-23

2014-11-21E-mail：anweisheng@swjtu.edu.cn