改进FAST特征点支持下的实时影像地标匹配算法

杨琪莉 朱兰艳 李海涛

摘要：针对图像匹配技术中匹配时间与匹配精度不能同时满足要求的问题，提出一种基于特征点匹配的方法，利用随机森林分类器实现地标的匹配，将匹配问题转化为简单的分类问题，大大简化了计算过程，保证影像匹配实时性；采用FAST特征点表示影像地标，利用高斯金字塔结构以及仿射增强策略改进FAST特征点的尺度和仿射不变性，提升影像地标匹配率。将实验结果与尺度不变特征变换（SIFT）算法和加速鲁棒性（SURF）算法进行比较。实验结果表明在尺度变化、发生遮挡以及旋转情况下，匹配率能达到90%左右，保持与SIFT算法和SURF算法相近的匹配率，并且匹配时间相较其他两种算法减少了一个数量级，能有效地对影像地标进行匹配，匹配时间也满足实时影像地标匹配要求。

关键词：随机森林；地标匹配；FAST特征点；高斯金字塔结构；仿射增强策略

中图分类号：TP391.41 文献标志码：A

Abstract：Concerning the problem that matching time and accuracy requirements can not be met the simultaneously in image matching technology， a method based on feature points matching was proposed. Landmark matching was achieved successfully by using Random Forest （RF）， and matching problem was translated into simple classifying problem to reduce the complication of computation for realtime image matching.

Landmark image was represented by Features from Accelerated Segment Test （FAST） feature points， the scale and affine invariability of FAST feature points were improved by Gaussian pyramid structure and affine augmented strategy， and the matching rate was raised. Comparing with ScaleInvariant Feature Transform （SIFT） algorithm and Speed Up Robust Feature （SURF） algorithm， the experimental results show that the matching rate of the proposed algrorithm reached about 90%， keeping the matching rate approximately with SIFT and SURF in cases of scale change， occlusion or rotation， and its running time was an order of magnitude than other two algorithms. This method matches landmarks efficiently and its running time meets the realtime requirements.

Key words：Random Forest （RF）； landmark matching； Features from Accelerated Segment Test （FAST） feature point； Gaussian pyramid structure； affine augmented strategy

0 引言

影像地标匹配的主要支撑技术是图像匹配。文献[1]将图像匹配主要分为基于灰度相关匹配和基于特征匹配。其中，基于特征匹配又可以细分为基于特征点匹配以及基于变换域匹配两种类型。文献[2]总结出了灰度相关匹配方法是利用对待匹配图像遍历窗口进行相似性比较的方式进行搜索匹配的方法，该方法计算量较大，图像相似性计算对尺度变化和旋转情况比较敏感。文献[3]指出基于特征的匹配方法通过对两幅图像提取特征，按照某种数学法则或几何约束方法对特征进行描述，通过特征匹配实现图像的匹配；

该方法匹配效果好，但是计算复杂，达不到实时性要求。文献[4]对基于特征点的图像匹配算法进行概述，主要有尺度不变特征变换（ScaleInvariant Feature Transform， SIFT）算法以及加速鲁棒性（Speed Up Robust Feature， SURF）算法，Lowe[5]提出SIFT算法，通过引入高斯拉普拉斯算子建立尺度空间、卷积运算和差分近似，保证了特征点的尺度不变性，旋转不变性和仿射不变性，但是相应地增加了其计算复杂度，运行时间达不到实时性要求。Bay等[6]提出SURF算法，在SIFT算法的基础上进行了改进，利用Hessian矩阵和积分图像缩短了特征点计算时间，采用Haar小波计算特征点主方向，该算法匹配速度大于SIFT算法，但仍然没达到实时性的要求。文献[7-8]分别对两种算法进行影像匹配应用研究。变化域匹配方法将图像进行相应的特征空间转换， 在空间变化域进行图像匹配，该方法能有效处理图像的旋转和尺度变化，但其计算复杂、计算量大，不满足实时性要求。

Lepetit等[9-10]提出运用随机森林算法进行宽基线匹配，根据这一思路，可将影像地标匹配转换为分类问题进行处理。随机森林算法通过将匹配过程分为离线训练以及在线匹配两个过程，离线过程对目标图像计算FAST（Features from Accelerated Segment Test）特征点，并训练得到随机森林。文献[11-12]对随机森林算法学习以及利用随机森林对目标进行检测、跟踪、识别等方面进行研究。由于FAST特征点的提取只与影像的灰度值有关，不具有尺度不变形和仿射不变性，对光照变化、旋转变换与尺度变化等较为敏感，会对随机森林的匹配性能产生影响。不同于SIFT、SURF稳健的特征点提取过程，为了保证算法的实时性，本文利用高斯金字塔结构以及仿射增强对FAST特征点进行改进，使其具有尺度不变性和仿射不变性的同时，亦能保持实时匹配性能。

根据式（5）建立高斯金字塔，将目标图像设置为金字塔第0组的第0层图像I00，对I00进行降采样处理可生成图像I10（金字塔第一组第0层图像），以此类推可建立好高斯金字塔结构中每一组的第0层图像；对图像Ii0进行高斯模糊操作生成图像Ii1，对每一组中的第0层图像依次进行高斯模糊可生成该组的其他层图像。即采用组间降采样处理，层间高斯模糊操作的方式构建高斯金字塔尺度空间。本文算法采用高斯模版为7×7，设置金字塔组数为3，每组图像层数为3。

建立好影像尺度空间，分别计算在金字塔每组下的每层图像的FAST特征点集 Fscale_ij，金字塔每组的特征点为Fscale_i={ Fscale_i1，Fscale_i2，…，Fscale_ij}；将金字塔每组特征点集合到一起形成带有尺度属性的影像FAST特征点集F={Fscale_1， Fscale_2，…，Fscale_i}；影像FAST特征点集F能表示不同尺度下的同一幅地标影像，增强FAST特征点的尺度不变性。

图1表示目标地标图像在不同尺度空间下的FAST特征点， 图（a）为高斯金字塔图像的第0层以及在该尺度下的FAST特征点集，图像分辨率为715×438；图（b）为高斯金字塔图像的第1层以及在该尺度下的FAST特征点集，图像分辨率为357×219；图（c）为高斯金字塔图像的第2层以及在该尺度下的FAST特征点集，图像分辨率为178×109。由图1可以看出，在不同的尺度空间下图像的特征点概括了不同图像信息，图（a）特征点表示图像的细节信息，图（b）特征点表示的主要是图像的边缘信息等，图（c）特征点表示的信息比较概括。

考虑到地标影像的表现形式，对仿射矩阵的参数进行了优化设置。地标影像通常不会出现与原始图像完全翻转等情况，对于两个旋转角度进行实验优化，设置角度参数θ，φ的取值范围为[-π/2，π/2]，比例缩放因子λ1、λ2取值范围为[0.5，1.5]。由于有些地标的特殊性，有些地标影像基本上不会发生遮挡的情况（如实验一地标），可以对平移矩阵进行抑制，有些影像在采集过程中可能会受到围栏、树木等的影响发生遮挡（如实验二地标），可以设置合适的平移矩阵。通过对仿射矩阵参数的优化设置，使得训练过程中的仿射图像能较好地模拟现实情况中的地标表现形式。图2是部分实验一过程中的仿射图像，其分别对应的仿射矩阵Ai如表1所示。

1.3 关键点选取

选取关键点是随机森林算法离线过程中重要的部分，选取对目标地标影像表达能力强的关键点，对随机森林分类正确率有至关重要的作用。本文算法在FAST特征点的基础上，利用高斯金字塔和仿射增强策略对其进行改进，使FAST特征点具有尺度不变性和仿射不变性。通过计算目标图像的改进FAST特征点集，从中选取表达能力强的作为目标图像的关键点集。改进FAST选取关键点集过程如下：

1）对目标图像按1.1节建立尺度空间，即建立高斯金字塔结构。

2）在每个金字塔尺度空间中每一组图下的每一层图像Ij提取FAST特征点Fscale_ij={fi}，图像高斯金字塔每一层图像上提取的特征点的集合形成该图像的FAST特征点F={Fscale_i}。

3）按仿射增强策略，将目标地标影像根据仿射矩阵Ai进行仿射变化生成仿射影像，并按照1）、2）步对仿射影像提取FAST特征点F′={ Fscale_i′}。

4）根据仿射矩阵Ai，逐个计算特征点集合F和F（中的同一尺度下的特征点fi和fj′的相似性，若fi-A-1fj′

5）重复3）、4）步，直到满足仿射停止条件（本算法设置仿射次数为1000）。

选取出现次数最多的FAST特征点产生关键点集K={K1，K2，…，KN}。

2 随机森林匹配

利用随机森林匹配影像地标，将传统的匹配方式转换为离线的训练过程和在线的匹配过程。在离线过程对地标图像建立尺度空间并进行特征点检测，按照仿射增强的策略选取图像的稳定点，生成N个点的关键点集K={K1，K2，…，KN}，利用该关键点集训练生成由m棵树组成的随机森林分类器CT={CT1，CT2，…，CTm}。在线过程，输入图像检测特征点，并对每一个特征点i利用随机森林分类器判断其所属类别Y（i）∈ C={-1，1，2，…，N}，-1表示没有与N个类别中的任意一个匹配。

2.1 随机森林训练

随机树的每个节点包含一个简单的二元测试，通过节点测试剖分数据空间并分类。在每个叶子节点包含对所有类别的后验概率分布。由于存在大量的数据类别、训练样本和节点测试，建立单一的一棵随机树将无法满足分类要求，需要建立多棵树即森林，每棵树产生不同的空间剖分。随着随机树的数量和树的深度增加，剖分变得越来越好，叶子节点的后验概率分布越来越接近真实，但是相应的计算复杂度和内存的需求会越来越大。本文算法均衡了随机森林的规模以及耗时，设定随机树的数目为16棵，每棵树深度为10层。

随机树里的节点二元测试都是随机生成的，节点二元测试与点m1、m2的亮度值有关，m1、m2是以特征点为中心的剖分空间（测试片元）中的两个随机点。若点m1亮度值小于m2亮度值，则该片元进入左子树，否则，进入右子树。将每个训练数据按照式（10）通过每棵随机树，并在叶子节点记录下每个类别出现的概率，进行归一化处理后生成后验概率分布。

为保证随机森林分类效果，在训练过程中分别从两个方面保证本文算法的随机性：在训练过程中的仿射增强阶段，随机选取范围内的仿射因子生成随机仿射矩阵，保证训练样本包含了所有的地标图像出现的情况，使得关键点集能很好地表达地标建筑。在建立随机森林的节点测试阶段，测试位置的随机选取，即每个节点随机剖分数据空间，将每棵树的随机剖分结构组合到一起形成的随机森林具有很强的分类能力。

2.2 随机森林分类

对一个新片元分类的时候，根据每棵树的每个节点测试判断新片元从左子树或右子树往下落，当落到叶子节点，叶子节点所存储的概率分布将决定该片元所属的类别。如图5所示，当待分类片元按图4（a）方法通过随机树时，都将落到某个叶子节点，图5第一列列出部分叶子节点的概率分布，将通过每棵树所得到的概率分布平均得到新片云的平均概率分布，其中最大概率类别即为片元类别。

2.3 本文算法过程

本文算法过程如下：

1）对目标地标影像按照第1章介绍提取关键点集，并生成关键点片元。

2）生成在每个节点都包含随机二元测试的随机森林。

3）按照2.1节方法，将步骤1）中的关键点片元投入步骤2）中的随机森林，通过不断的二元测试比较得到随机森林叶子节点的后验概率分布，至此随机森林训练完毕。

4）对新的测试影像按1.1节建立尺度空间，计算其FAST特征点集Ftest并生成特征点片元。

5）测试影像的每个FAST特征点片元投入随机森林，随机森林分类器按2.2节将每个特征点进行分类。

6）通过随机采样一致性（RANdom SAmple Consensus，RANSAC）方法剔除误分类点，得出匹配结果。

本文算法关键步骤：1）提取改进FAST稳定点并生成稳定点训练片元，2）训练随机森林生成叶子节点概率分布，3）根据训练好的随机森林对待分类片元进行分类。每个步骤计算简单，计算复杂度低，保证算法的实时性。

1）提取改进FAST稳定点，需要将原图像进行仿射变换1000次，并对每一个仿射后图像计算改进FAST特征点，最后对每个特征点出现次数进行排序，选取前400个作为稳定点；由于对每个图像计算改进FAST特征点只需几十毫秒，整个稳定点计算过程不会产生较大的时间开销。

2）生成关键点训练片元，每个关键点就是一个类别，每个类别的训练片元由不同视角影像中的关键点片元组合而成，只需对图像进行简单的仿射变换，并根据仿射变换矩阵计算关键点位置坐标截取片元即可。

3）训练随机树，需要将每个类别的训练片元依次通过每一个节点，随机树的每个节点仅仅包含了简单的二元比较，不涉及复杂的计算步骤，保证算法实时性。

4）随机森林分类，利用随机森林对待分类的片元分类时，只需要在每个树节点进行简单的二元比较，并对每个叶子节点的概率分布进行均值计算。

3 实验结果与分析

为对本文算法的地标影像匹配效果进行验证，分别从算法匹配效率以及匹配正确性两方面将实验结果与SIFT算法、SURF算法以及原始FAST特征点随机森林算法进行比较，采用两组实验数据表明本文算法在保证匹配正确率的情况下匹配时间上的优点。第一组数据是昆明市地标建筑碧鸡坊，地标图像为碧鸡坊正面视图图像，分辨率为715×438，测试图像为任意角度下的碧鸡坊图像，图像分辨率为348×464；第二组实验数据地标建筑是陆军讲武堂，地标图像分辨率为355×433，测试图像分辨率为608×810。实验硬件环境为Intel Core i3 2.13GHz CPU，2GB RAM；软件环境为Microsoft Visual Studio 10.0及OpenCV 2.45。

实验一地标碧鸡坊为城市中心地标建筑，采集的图片含有行人、车辆以及周边建筑物的干扰信息。表2列出了实验一测试图像计算4种特征点所需时间，FAST特征点计算所需时间最短，其次为本文改进FAST特征点，最后是SURF和SIFT算法。FAST特征点虽然计算速度快，但直接用其进行匹配效果不理想，本文改进FAST特征点，加强了FAST特征点的尺度和仿射不变性，仍能保持算法的实时性；在匹配时间方面，本文算法相对SIFT算法和SURF算法减少了两个数量级，能实现对地标影像的实时匹配。

本文算法利用改进FAST特征点匹配并对匹配后的匹配点对运用RANSAC剔除误匹配。当匹配点数大于20即可表示两个地标图像匹配成功。实验一测试影像在尺度上相较于目标影像发生了很大的变化，FAST特征点不具备尺度不变性，利用FAST特征点随机森林算法匹配未成功。在影像发生遮挡或是影像中有大量的相似的结构时，SIFT算法和SURF算法会产生一定误匹配。三种算法实验结果如图7所示，结果表明本文算法具有很好的匹配性能。

表3将实验一的结果进行对比分析，分别对图7中的两组图像的匹配点数、点匹配率和匹配时间进行了分析。点匹配率是对测试图像计算得到的特征点与匹配成功的点的比值。经过对比分析，本文算法能保持与SIFT相近的点匹配率，成功匹配地标影像，并且在匹配时间方面远远优于其他两种算法，实现实时匹配地标。

实验二对地标建筑陆军讲武堂进行测试，与实验一地标碧鸡坊相比背景相对简单。实验二测试影像在尺度上较目标影像变化不大，只是产生较大的旋转、遮挡以及杂乱背景等情况。FAST特征点随机森林算法对图8三个影像的点匹配数分别为：8、20和21（RANSAC后），对发生较大旋转的情况无法进行匹配。本文算法在训练阶段利用仿射增强策略增强FAST特征点仿射不变性，能对实验二测试影像高效匹配，实验结果见图8。

对实验二结果进行统计分析，从匹配效率以及匹配正确性两方面与SIFT算法、SURF算法以及FAST随机森林算法进行比较，对比结果如图9所示。

图9（a）表示四种算法的匹配时间对比分析，采用样本量为10的倍数，分别统计四种算法进行匹配所需时间。对比结果表明，本文算法平均的匹配时间大约在220ms每个图像，FAST随机森林算法匹配时间大约在180ms，而SIFT算法和SURF算法分别在4000ms和8500ms左右每个图像。通过对比本文算法在匹配速率远远优于其他两种算法，与SIFT算法和SURF算法匹配时间的1/10进行比较仍然是本文算法具有更优匹配速率。匹配正确率对比分析，采用样本量为10的倍数，统计四种算法的匹配正确率如图9（b）。本文算法匹配率在90%左右，FAST特征点随机森林算法在60%左右，SIFT算法和SURF算法匹配正确率分别维持在92%和95%左右。本文算法在匹配正确率方面稍弱于SIFT和SURF算法，但是远远高于FAST特征点随机森林算法。本文算法在保证匹配正确率与SIFT算法和SURF算法相近的情况下，匹配时间满足实时性要求。

4 结语

本文提出了利用改进FAST特征点的随机森林算法进行影像地标的匹配，实现对地标的识别。对昆明市地标建筑碧鸡坊和陆军讲武堂分别进行实验，并将实验结果与SIFT算法、SURF算法以及FAST特征点随机森林算法进行比较。在匹配正确率方面本文算法通过改进FAST特征点将匹配正确率从60%提升到90%，保证与SIFT算法和SURF算法相近的匹配正确率。在匹配效率上较SIFT算法和SURF算法而言，提高了不止10倍，满足实时性要求。通过实验验证了本文算法在保证匹配正确率的同时能有效地提高匹配效率，能快速且高效地对地标图像进行匹配识别。由于本文只训练了地标建筑的正面图像，只能对地标建筑物的正面进行匹配与识别，可以对地标建筑建立三维模型再进行匹配与识别。

参考文献：

[1]ZITOVA B， FLUSSER J. Image registration methods： a survey [J]. Image and Vision Computing， 2003， 21（11）：977-1000.

[2]饶俊飞.基于灰度的图像匹配方法的研究[D]. 武汉： 武汉理工大学， 2005：14-19.（RAO J F. Research of image matching method based on intensity[D]. Wuhan： Wuhan University of Technology， 2005：14-19.）

[3]惠国保， 童一飞， 李东波. 基于改进的图像局部区域相似度学习架构的图像特征匹配技术研究[J].计算机学报， 2015， 38（6）：1148-1161. （HUI G B， TONG Y F， LI D B. Image features matching based on improved patch similarity learning framework[J]. Chinese Journal of Computers， 2015， 38（6）：1148-1161.）

[4]MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors[C]// Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2003：257-263.

[5]LOWE D G. Distinctive image features from scale invariant keypoints [J]. Computer Vision， 2004， 20（2）： 91-110.

[6]徐秋辉， 佘江峰， 宋晓群， 等. 利用HarrisLaplace和SIFT描述子进行低空遥感影像匹配[J].武汉大学学报（信息科学版）， 2012， 37（12）：1443-1447.（XU Q H， SHE J F， SONG X Q， et al. Matching low altitude RS image with HarrisLaplace and SIFT descriptor[J]. Geomatics and Information Science of Wuhan University， 2012， 37（12）： 1443-1447.）

[7]BAY H， TUYTELAARS T. SURF： speeded up robust features[C]// ECCV 2006： Proceedings of the 9th European Conference on Computer Vision， LNCS 3951. Berlin： Springer， 2006： 404-417.

[8]闫利， 陈林. 一种改进的SURF及其在遥感影像匹配中的应用[J]. 武汉大学学报（信息科学版）， 2013， 38（7）： 770-773.（YAN L， CHEN L. A modified SURF descriptor and its application in remote sensing image matching[J]. Geomatics and Information Science of Wuhan University， 2013， 38（7）： 770-773.）

[9]LEPETIT V， FUA J P. Keypoint recognition using randomized trees [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006， 28（9）： 1465-1479.

[10]LEPETIT V， PILET J， FUA P. Point matching as a classification problem for fast and robust object pose estimation[C]// CVPR 2004： Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2004， 2： II244【【页码就这样排II250.

[11]LEISTNER C， SAFFARI A， BISCHOF H. MIForests： multipleinstance learning with randomized trees[C]// ECCV 2010： Proceedings of the 11th European Conference on Computer Vision， LNCS 6316. Berlin： Springer， 2010：29-42.

[12]GALL J， YAO A， RAZAVI N， et al. Hough forests for object detection， tracking， and action recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（11）： 2188-2202.

[13]ROSTEN E， DRUMMOND T. Machine learning for highspeed corner detection[C]// ECCV 2006： Proceedings of the 9th European Conference on Computer Vision， LNCS 3951. Berlin： Springer， 2006： 430-443.