李自豪，李培林，王　崴,2，瞿　珏，彭勃宇

(1.空军工程大学防空反导学院，陕西 西安　710051；2.西安交通大学机械制造系统工程国家重点实验室, 陕西 西安　710049)



多传感器辅助的快速图像匹配算法

李自豪1，李培林1，王崴1,2，瞿珏1，彭勃宇1

(1.空军工程大学防空反导学院，陕西 西安710051；2.西安交通大学机械制造系统工程国家重点实验室, 陕西 西安710049)

针对现有图像匹配算法效率和精度难以兼顾的问题，提出了多传感器辅助的快速图像匹配算法。该算法利用FAST算法提取特征角点，再利用SIFT算法为特征点生成主方向和描述符；并结合基于点积的相似度度量，利用多传感器输出的姿态数据辅助搜索策略，以完成快速初匹配；最后通过统计特征点距离误差的方法剔除误匹配点，获取最终同名点集。实验表明，该图像匹配算法在效率和精度方面均优于传统的SIFT算法，能够满足增强现实系统对图像匹配算法的精度高、速度快的要求。

FAST角点检测；SIFT特征；多传感器；误匹配剔除；快速匹配

0　引言

虚实注册作为增强现实系统的关键和难点，用来实现虚拟信息与真实世界场景的准确融合。由于视觉和定位传感器在特性上的互补，构建混合视觉和定位传感器的注册系统成为当前研究热点。混合系统中视觉注册的一个关键步骤就是找到图像之间的匹配点对，匹配的准确与否直接影响到后续摄像机位置和姿态的计算精度，而匹配的速度则影响到增强现实系统的实时性。由于增强现实诱导维修系统需要给用户呈现准确流畅的虚实叠加影像，所以对图像匹配的精度和速度都提出了较高的要求。

图像间匹配点对搜寻的过程主要分为图像特征的提取和特征的匹配两大步骤，快速提取较为鲁棒的特征并进行迅速准确的匹配是算法的发展方向。由 D.G.Lowe于2004年提出的SIFT(Scale Invariant Feature Transform)[1-2]算法在尺度空间中使用邻域梯度信息对特征进行提取和描述，使得SIFT特征对图像的旋转、缩放和噪声干扰甚至仿射变换都具有较好的鲁棒性。但其存在计算量大的缺点，难以满足系统的高实时性要求。

角点检测算法是一种常用的图像特征提取算法，常用的有Moravec[3]、Forstner[3]、Harris[4]、SUSAN[5]和FAST[6]。因为角点检测算法能够快速检测图像中角点特征，因而将角点检测算法与SIFT特征描述符结合成为了近年来图像匹配研究的热点。加速分割检测特征(features from accelerated segment test，FAST)是由Rosten和Drummond于2006年提出的一种简单、快速的角点检测算法，通过该算法可以快速确定出角点，使特征提取达到毫秒级别，可应用于实时视频的处理，但其旋转不变性差，光照不变性差，鲁棒性差，难以满足增强现实系统对匹配精度的要求。而且大多数增强现实应用中图像匹配过程只是单纯使用一种现有的匹配算法，没有针对所处的增强现实应用环境进行优化和改良，匹配的精度和效率难以有效提升。本文针对此问题，提出了多传感器辅助的快速图像匹配算法。

1　算法基础

1.1FAST角点检测算法

FAST算法中，为找到局部稳定特征，首先要在每帧内检测到稳定的角点位置。在某个像素点的周围邻域内有足够多的像素点与该点处于不同的灰度区域时，该点被确认为一个FAST角点。

首先通过分割测试，筛选候选角点。将目标图像与如图1所示的一固定半径的圆形模板进行比较和计算。待检测点O是否为角点取决于其周围编号为1—16的灰度值。只要周围像素点高于某一阈值的个数大于n，那么该O点就是候选角点。

经以上步骤后，在实际角点处可能仍然存在多个兴趣点，因此最后需要通过局部非极大值抑制定位角点特征。在上面的分割测试中，没有计算角点响应函数，非极大值抑制无法直接应用于提取的特征。因此，定义一个角点响应函数V，考虑到分割测试的特征以及计算速度的需要，角点函数定义如下：

(1)

定义了角点响应函数后，就可以采用非极大值抑制方法对非角点进行排除。

图1　FAST圆形模板示意图Fig.1　Schematic diagram of circular template

1.2特征点主方向的确定

在SIFT算法中，为实现图像旋转的不变性，需要利用图像局部特征给每个特征点分配主方向。统计以特征点为中心的邻域内梯度的模值和方向并用直方图表示。统计时，对邻域内梯度进行高斯加权，其中σ=1.5，图2中的圆圈表示加权范围。图2中为简化给出了8个方向的直方图统计结果，D.G.Lowe的原文中采用36方向直方图。取图中达最大值80%以上的为辅方向，这样一个特征点可能具有多个方向，可增强匹配的鲁棒性。

图2　生成特征点主方向Fig.2　Generate the main direction of feature point

1.3SIFT描述符的生成

为使特征描述符具备旋转不变性，首先以特征点为中心将坐标轴旋转至特征点的主方向。以特征点为中心取16×16窗口邻域，对邻域内梯度进行高斯加权，并在每4×4的小块上统计8个方向上每个方向的梯度和，形成图3所示的子点。每个子点有8个方向的梯度信息，特征点邻域内有4×4共16个子点，可形成128维梯度描述向量，即SIFT特征描述符。此时的特征描述符已经去除了尺度、旋转等几何因素的影响，最后将描述向量进行单位化以进一步去除光照变化的影响。利用邻域梯度信息的方法在降低算法对噪声的敏感性的同时提升了算法对特征定位误差的容错能力。

图3　生成特征点描述符Fig.3　Generate the feature point descriptors

2　混合多传感器的快速匹配算法

综合FAST角点和SIFT描述符的优势并结合惯性传感器的位姿辅助提出了本文的混合匹配算法。首先利用FAST算法提取特征角点，然后利用SIFT算法为特征点生成主方向和描述符。之后，结合基于点积的相似度度量，利用多传感器输出的姿态数据辅助搜索策略，以完成快速初匹配。然后，通过统计特征点距离误差的方法剔除误匹配点，获取最终同名点集图4为算法的流程图。

图4　算法流程图Fig.4　Flow chart of the algorithm

2.1基于向量点积的相似度度量

特征点的匹配本质上是描述符间相似度的度量，传统的欧氏距离度量法是通过搜索待匹配图像中特征点A到参考图像中欧氏距离最小点C和距离次小点D(最邻近点与次邻近点)，计算最邻近距离与次邻近距离的比值rat，并将rat与设置的阈值T进行比对，若小于阈值则认为待匹配点A与最邻近点C为一对匹配点。这里T通常取0.8。

(2)

对于n维的特征描述符，每求一次欧氏距离都要进行n次减法、n次平方、n-1次加法和1次开方。计算量较大，对此本文提出了一种通过向量点积度量特征点之间相似度的快速匹配算法。

特征描述符X，Y之间的夹角θ(X,Y)可表示为：

(3)

由于特征描述符已进行过单位化处理，所以模值均为1，因此X，Y之间夹角的余弦值可表示为两向量的内积形式。

(4)

当T1增大，T2减小时匹配对数逐渐减少，通过实验发现当T1=0.5，T2=0.7时可有效剔除90%的误匹配同时正确匹配损失不超过5%，能够取得较好的匹配效果。

由式(4)可知，对于n维的特征描述符，作一次点积只需要进行n次乘法和n-1次加法，运算量和计算欧氏距离相比大大减少，因此用点积代替欧氏距离作为相似性度量能有效提高算法的快速性。

2.2多传感器辅助的图像匹配策略

2.2.1多传感器硬件系统

混合跟踪注册[8]的传感器系统由视觉传感器(摄像头)、陀螺仪、加速度计和地磁感应计组成。选用集成了三轴陀螺仪和三轴加速度计的MEMS芯片MPU6050作为惯性传感器，且选用集成了三轴地磁传感器的MEMS芯片HMC5883采集地磁数据，芯片内置OFFSET/SET/RESET电路，不会出现磁饱和与累加误差现象，支持自动校准程序，简化使用步骤，能够满足测量要求。MPU6050和HMC5883内部都自带16位A/D转换器并支持I2C总线。

MPU6050和HMC5883焊接在一块电路板上，并选用基于CortexM3内核的STM32系列ARM处理器STM32F103U8T6进行数据采集，以此构建了惯性/地磁传感器模块。STM32F103U8T6主频达72 MHz，具有1.25 DMIPS/MHz的计算能力，具有硬件单周期乘法器，以保证姿态更新的实时性。模块上的传感器通过I2C接口和处理器连接，传感器数据中断引脚与STM32的I/O相连，使得处理器能在传感器在完成AD转换后的第一时间读取更新数据。图5为惯性/地磁模块硬件框图。

图5　惯性/地磁模块硬件框图Fig.5　Hardware block of inertia/ geomagnetism module

摄像头和惯性/地磁模块一同固连在自制的增强现实头盔上，如图6所示。

图6　混合注册AR头盔Fig.6　AR helmet of mixed registration

2.2.2位姿估计和辅助策略

摄像头的采样频率为30 Hz，相邻两幅帧图像拍摄时间间隔为1/30 s，根据观察者头部运动实际情况，相邻两幅帧图像间摄像头运动应是短时间、小范围的姿态位置变化，且惯性数据的更新频率远高于视觉图像更新频率。因此匹配相邻两幅帧图像时，通过对陀螺仪、加速度计的量测值积分进行积分得到摄像头的位姿变化。获取姿态变化后可将特征点在待匹配图像中进行重新投影，并根据投影位置划定匹配搜索区域。

通过互补滤波器[9]的姿态输出和对加速度计进行积分得到两幅帧图像拍摄时摄像头姿态和位置变换为ΔR和ΔT，空间中一点P在第k帧图像(参考图像)中的坐标为pk(uk,vk)，第k帧和第k+1帧时刻点P在摄像头坐标系下的坐标分别为Pk(xk,yk,zk)和Pk+1(xk+1,yk+1,zk+1)，下面求点P在第k+1帧图像(待匹配图像)中重新投影的位置pk+1(uk+1,vk+1)。

首先由透视投影模型得到式(5)和式(6)：

(5)

(6)

由式(5)得

(7)

代入式(6)得

根据惯性数据点P在待匹配图像上的重投影的坐标pk+1(uk+1,vk+1)并根据其划定匹配搜索范围。这里以pk+1为圆心，R为半径划定圆形匹配区域，R根据帧图像时间间隔和摄像头运动参数按式(9)自适应选取：

(9)

根据摄像头姿态预测特征点区域，在有效降低运算量的同时，合理降低了误匹配点的出现概率，有效提升了算法的速度和精度。摄像机坐标系，物体坐标系和图像坐标系之间关系如图7所示。

图7　摄像机、物体坐标系、图像面坐标系关系图Fig.7　The relationship between coordinate system

2.3误匹配点快速剔除

经过上述特征匹配后得到初匹配点集S，不可避免地其中会存在一定数量的误匹配点，因此需要对初匹配点集进行误匹配点剔除。RANSAC(Random Sample Consensus)算法[10]是常用的误匹配点剔除方法，它是从一组包含“局外点”的观测数据中，通过迭代方式估计模型的参数。它是一种不确定算法，通过增加迭代次数提高概率，会产生较大的计算量，因此本文提出了一种通过统计特征点间距离均值误差以剔除误匹配点的方法。设Ai,Bi∈S(i=1，2，…，n)，其中Ai,Bi分别是位于待匹配图像和参考图像中相匹配的特征点，统计特征点间距离均值误差的方法可描述如下：

(10)

3　实验分析

在CoreI5 3.1GHzCPU，4GBRAM的windows7微机上使用VS2010结合openCV编程实现了本文算法。首先对本文的算法与SIFT算法的匹配性能进行了比较；然后验证了本文算法在视角变化和有无遮挡干扰下的鲁棒性；系统中摄像机拍摄的视频图像分辨率为640×480。

图8和图9为二组不同图像的匹配结果，每幅图的上下半幅分别为使用SIFT和本文算法的匹配效果。表1、表2为图8、图9匹配结果统计。本文算法在二组图像下的平均匹配正确率为97.4%，比SIFT算法高出11.2%；平均单个特征点匹配用时为1.63ms，为SIFT算法的38%左右。图10为使用本文算法的AR虚实注册效果。图11统计了0～10s内使用Harris-SIFT[11]、SURF[12]和本文算法的AR系统输出视频帧速率。

图8　第一组图像匹配结果Fig.8　The matching results of first group images

算法SIFTFAST-SIFT匹配时间/ms704.671.2匹配点数16843误配点数231正确率/%86.497.7

图9　第二组图像匹配结果Fig.9　The matching results of second group images

图10　虚实注册效果Fig.10　Virtual-real registration results

图11　输出视频帧速率对比Fig.11　The rate comparison of video frame

4　结论

本文提出了多传感器辅助的快速图像匹配算法。该算法首先用FAST算法检测两幅图像中的特征角点，然后利用SIFT算法为特征点生成主方向和描述符；其次，结合基于点积的相似度度量完成初匹配；其中，通过惯性传感器数据预测摄像头姿态和特征点在待匹配图像中的位置，缩小匹配范围，同时运用随机K-D树完成邻近点搜索，提高运算效率；最后利用距离均值误差统计法剔除误匹配点得到最终同名点集。实验表明，该图像匹配算法在效率和精度方面均优于传统的SIFT算法，能够满足增强现实系统对图像匹配算法的精度高、速度快的要求。总的来说，该算法解决了现有的图像匹配算法在AR系统中应用的三个问题[13-14]：1)计算量大不适用于实时运算；2)特征定位精度和匹配正确率不能满足AR系统虚实注册的要求；3)数据利用效率低，没有针对具体AR应用特点对匹配算法进行优化。实验证明，该算法是一种快速鲁棒的图像匹配方法，能够很好地应用于AR系统。

[1]LoweDG.DistinctiveImageFeaturesfromScale-InvarientKeypoints[J].InternationalJournalofComputerVision，2004, 60(2):91-110.

[2]曾峦，王元钦，谭久彬.改进的SIFT特征提取和匹配算法[J].光学精密工程，2011,19(6):1391-1397.

[3]郭宝龙，孙伟.数字图像处理系统工程导论[M]. 西安：西安电子科技大学出版社，2012:74-77.

[4]王崴，唐一平.一种改进的Harris角点提取算法[J].光学精密工程，2008，16(10):1995-2000.

[5]Smith S M，Brady J M. SUSAN a new approach to low level image processing [J].Journal of Computer Vision，1997，23(1):45-78.

[6] Rosten，Drummond T. Machine Learning for High-speed Corner Detection[C]// European Conference on Computer Vision，Graz，Austria，2006:430-443.

[7]丁南南，刘艳滢.基于SURF-DA-ISY算法和随机k-d树的快速图像配准[J].光电子.激光，2012，23(7):1395-1401.

[8]李薪宇，陈东义.基于混合跟踪的增强现实系统设计与实现[J].计算机应用，2009,29(10):2853-2858.

[9]郭军海.弹道测量数据融合技术[M].北京：国防工业出版社，2012:169-174.

[10]Fischler M，Bolles R. Random samples consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM，1981，24(6):381-395.

[11]赵钦君，赵东标.Harris-SIFT算法及其在双目立体视觉中的应用[J].电子科技大学学报，2010，39(4):546-550.

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

[13]许宪东，洪炳镕，关毅，等. 机器人视觉导航的几种特征点方法比较[J].华中科技大学学报(自然科学版)，2011，39:200-203.

[14]贾平，徐宁，张叶.基于局部特征提取的目标自动识别[J]. 光学精密工程，2013，21(7):1898-1904.

Multi-sensor Aided Fast Image Matching Algorithm

LI Zihao1, LI Peilin1, WANG Wei1,2, QU Jue1, PENG Boyu1

(1. College of Air Defense and Anti-Missile, Air Force Engineering University, Xi’an 710051, China;2. State Key Laboratory for Manufacturing System Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Aiming at the problem that the existing image-matching algorithms can’t give consideration to both efficiency and precision, a multi-sensor aided and fast matching algorithm was proposed. Firstly, the feature points were detected by using robust FAST operator. Then, the main direction of feature point and the feature point descriptors were generated by using SIFT algorithm. Afterward, the preliminary matching was finished by using the similarity matric method based on the dot product, using position and attitude data of multi-sensor to narrow the range of search. Afterwards, the final matching points set was obtained by counting the distance error of feature points. Finally, the process of target tracking became more robust through template updating. Experimental results indicated that the accuracy and speed of this algorithm was superior to the traditional SIFT algorithm, which could satisfy the system requirements of higher precision and rapid speed.

FAST corner detection; SIFT feature; multi-sensor; error points eliminating; fast match

2016-02-18

国家自然科学基金项目资助(51405505)

李自豪(1992—)，男，土家族，湖南张家界人，硕士研究生，研究方向：增强现实，人机交互和诱导维修。E-mail:871805104@qq.com。

TP391

A

1008-1194(2016)04-0108-06