增强现实（augmented reality，AR）能将虚拟信息有机地融合到用户所看到的真实世界场景中^[1]，而真实世界与地理信息紧密相连，因此将户外移动AR技术与地理信息系统结合进行地理表达将更有效地增强用户对现实世界的认识与感知，同时能加强用户与真实环境的交互^[2]。AR技术具有虚实结合、实时交互和三维注册的特点^[3]。其中，三维注册是AR系统的核心，是衡量AR系统性能的重要指标。目前，三维注册方法主要分为基于硬件的三维注册和基于视觉的三维注册。

基于硬件的三维注册方法主要是利用全球定位系统（Global Positioning System，GPS）、地图服务、加速传感器与磁力传感器等硬件设备实现地物在设备的三维坐标系中的定位，主要应用于导航领域。如武雪玲等^[4]提出一种混合硬件跟踪定位的空间信息虚实配准方法以满足户外增强现实导航的需求；李丹等^[5]提出一种基于Android平台的多传感器式注册方法，并应用于户外导航中。但与基于视觉的三维注册方式相比，基于硬件的三维注册方法受传感器精度和户外环境影响较大，且匹配精度很难满足户外环境三维注册的要求。

基于视觉的三维注册通过摄像设备获取的视频流对目标物体进行特征识别和定位，研究重点主要集中在基于自然特征点的图像匹配算法上，且研究应用于室内较多，对户外自然场景下的移动设备上的图像匹配算法研究较少。室外场景下图像匹配易受光照、尺度、角度等因素影响，匹配效果不佳。如何在室外复杂环境下实现目标快速高效的匹配并保证匹配精度是当前重要的问题。目前，基于自然特征点的尺度不变特征变换（scale-invariant feature transform，SIFT）^[6]、基于改进加速鲁棒性特征（speed up robust features, SURF）^[7]等图像匹配算法应用比较广泛，此类算法具有匹配效果好、鲁棒性强的特点，但实时性较差，导致移动AR系统识别效率低、流畅性差。专家学者陆续提出局部不变特征检测（oriented fast and rotated brief，ORB）^[8]、二进制鲁棒性可扩展关键点算法（binary robust invariant scalable keypoints，BRISK）^[9]、快速视网膜关键点（fast retina keypoint，FREAK）算法^[10]等并进行改进。该类算法由于采用二进制描述符，在运算速度上有了较大的提升，但是存在匹配精度较低、鲁棒性差的情况，导致移动AR系统的匹配效果及稳定性较差。相比其他算法，SURF算法在实时性和鲁棒性表现较好，学者们针对SURF做了许多相关的工作。如戴雪梅等^[11]基于二分法对图像进行分块处理，并将SURF与ORB相结合，以提高跟踪的实时性，但算法鲁棒性有所下降；桂振文等^[12]提出了一种基于自然场景在线学习的AR跟踪注册算法，通过改进SURF描述符进行在线学习以提高注册效率，但是SURF描述符仍为浮点型，实时性不高。

综合分析上述算法的不足之处，本文提出一种基于改进SURF和角点跟踪算法（Kanade-Lucas-Tomasi，KLT）的移动AR户外三维注册方法，实现对户外场景高效的三维注册。通过结合FREAK算法改进SURF算法（以下简称SUFREAK），该算法在保持较高匹配精度的同时有效地解决了SURF算法实时性不足的问题，实现对户外场景快速有效的识别和初始三维矩阵的计算。同时，充分利用视频流之间帧的时序性和相关性，使用光流跟踪算法对户外场景的自然特征点进行跟踪预测，提高三维注册的实时性。

1 改进的户外移动AR三维注册 1.1 三维注册算法的框架

本文方法具体流程如图 1所示。该三维注册方法首先采用SUFREAK进行图像匹配，并为后续提供准确度较高的特征点；然后，采用KLT跟踪算法对图像匹配过程提供的特征点进行跟踪，从而实现目标跟踪。在整个目标跟踪过程中，目标的位置、姿态、尺寸以及光照等因素会发生变化，这些因素会导致特征点的跟踪减少和丢失。针对这一点，算法设计了特征点动态更新策略：当特征点跟踪丢失达到至少30点时，则重新进入图像匹配模块，进行目标识别和特征点提取。同时，为了提高图像匹配的效率，可通过预先对目标图像的特征点进行提取和描述子构建等方法来减少图像匹配的耗时。

具体步骤如下：

1）获取移动端上视频流，并对视频帧进行灰度化处理。

2）判断该帧是否存在匹配标记。若不存在匹配标记，则认为未进行图像匹配，进入步骤3）；若存在匹配标记，则认为已进行图像匹配，进入步骤6）。

3）采用SUFREAK算法对当前场景的视频帧进行特征点提取和描述子构建。

4）与离线目标图像进行特征匹配，并采用随机采样一致性算法进行误匹配剔除。

5）根据匹配点对数量，判断该场景是否与离线目标图像成功匹配。如果匹配成功，则将该场景帧提取的特征点和图像分别存储为prePts、preImg，并添加匹配标记，进入步骤8）；如果匹配失败，则删除匹配标记，返回步骤1）。

6）以存储的preImg、prePts和当前帧curImg为参数进行KLT目标跟踪计算，获取跟踪目标的特征点为nextPts。

7）根据特征点nextPts的数量，判断跟踪是否丢失。如果特征点数量大于设定的阈值，则更新跟踪参数，令preImg=curImg，prePts=nextPts，进入步骤8）；如果特征点数量小于设定的阈值，则删除匹配标记，返回步骤1）。

8）根据目标特征点，利用透视n点算法计算三维注册矩阵，以此进行虚实融合或者模型姿态调整。

1.2 SUFREAK算法 1.2.1 SURF特征提取

SURF算法延续SIFT尺度空间理论，采用方框滤波替代SIFT算法的高斯滤波，使用积分图像和Hessian矩阵技术进行特征点提取，有效地降低SURF算法的运算量。

1) 积分图像I_∑(x，y)表示在灰度图像中左上角到G点（x, y）围成矩形区域的像素值之和，用公式表示为：

${I_\sum}\left( {x, y} \right) = \sum\limits_{j = 0}^{i \le x} \sum\limits_{j = 0}^{j \le x} G\left( {i, j} \right)$

(1)

2) Hessian矩阵斑点检测SURF算法使用Hessian矩阵检测极值点可以得到精度较高的点。在一幅尺度为σ的图像中，任意点P=(x，y)的Hessian矩阵定义为：

$\mathit{\boldsymbol{H}}\left( {P, \sigma } \right) = \left[ {\begin{array}{*{20}{c}} {{L_{xx}}\left( {P, \sigma } \right)}&{{L_{xy}}\left( {P, \sigma } \right)}\\ {{L_{xy}}\left( {P, \sigma } \right)}&{{L_{yy}}\left( {P, \sigma } \right)} \end{array}} \right]$

(2)

式中，L_xx(P，σ)、L_yy(P，σ)、L_xy(P，σ)分别表示点P在x、y、xy方向的高斯二阶偏导数∂g(σ)/∂x²、∂g(σ)/∂y²、∂g(σ)/∂xy与图像的卷积。

SURF为了加快卷积的运行速度，采用方框滤波，并将σ=1.2的高斯二阶微分模板简化为9×9像素大小。其中，白色像素值为1，黑色像素值为-2，灰度像素值为0，如图 2所示。

则式(2)的行列式可化简为：

${\rm{det}}\left( {{\mathit{\boldsymbol{H}}_{{\rm{approx}}}}} \right) = {D_{xx}}{D_{yy}} - {(w{D_{xy}})^2}$

(3)

式中，_Dxx、D_yy、D_xy是模板与图像进行卷积的结果，分别是L_xx、L_yy、L_xy的近似值；而w是固定值参数，经实验测得为0.9。

据此，使用Hessian行列式计算某一尺度下的图像，即可获得该尺度下响应图像。

3) 尺度金字塔SURF算法借鉴SIFT算法构建尺度金字塔的思想，但通过不同尺寸的方框滤波与图像卷积构建金字塔图像，且滤波模板尺寸的变化不增加计算量，因此显著减少了运算量。SURF算法构建图像时，将尺度金字塔空间分为若干组（octaces），每组又分为若干层（level），每层的方框滤波的尺度不同。由于越往后划分每组检测到的点越少，所以一般分为4组，每组尺寸分别为（9，15，21，27）、（15，27，39，51）、（27，51，75，99）、（51，99，147，195）。

4) 兴趣点定位SURF算法首先通过Hessian矩阵检测获得的斑点响应图像寻找极值点。极值点的搜索采用3×3×3邻域非最大值抑制法，即如果图中X点值大于（或者小于）上下层周围的26点，则认定点X为特征点。然后，采用三维线性插值法得到亚像素级的特征点位置信息。

1.2.2 结合FREAK改进SURF算法

可以看出，SURF算法特征点提取相对SIFT算法在计算速度方面有了很大提升，但是其浮点型64维描述子仍达不到实时性的要求。而FREAK算法的描述子采用二进制计算与存储方法，相比SURF算法浮点型描述子在描述子生成、存储和匹配方面的运算速度有较大优势。因此，本文结合FREAK描述子计算量小、鲁棒性好的特性提出改进算法SUFREAK，以解决SURF算法实时性差和户外复杂环境图片匹配不佳的问题。

1）FREAK特征描述子

（1）视觉采样模式

相比SURF算法描述子提取方式，FREAK算法借鉴了BRISK算法^[13]的平均采样模式思想，不同的是FREAK算法通过模仿人眼视觉的成像特性进行样点设置和对应点对选择，视网膜采样格越靠近中心特征点，样点密度越高。FREAK算法对样点进行高斯处理以降低对噪音的敏感度，样点的圆半径、高斯核大小与采样点到中心特征点的距离成正比^[13]，相邻采样点的感受野相互重叠，丰富了图像信息的同时使其具备了一定的尺度不变性和光照不变性。其采样结构如图 3所示：以特征点为中心，由中心向外分为7层，每层6个采样点，包含在同心圆内。

（2）粗到精的描述子

相比SURF的64维描述子（占用256 bytes），FREAK采用的二进制描述子占用存储空间小，其粗描述子由级联高斯平滑后的采样点对的灰度值比较结果生成，用F表示，则：

$F = \sum\limits_{0 \le a \le N} {2^a}T\left( {{P_a}} \right)$

(4)

$T\left( {{P_a}} \right) = \left\{ {\begin{array}{*{20}{c}} {1, }&{I\left( {{P_a}{r_1}} \right) - I\left( {{P_a}{r_2}} \right) > 0}\\ {0, }&{其他情况} \end{array}} \right.$

(5)

式中，P_a是采样点对；I(P_ar₁)、I(Pa_r2)是采样点对高斯平滑后的值；N是描述子的维度903（特征点周围共43个采样点，可组成903个采样点对）。

粗描述子二进制长度为903位，包含冗余、噪音信息，因此需要从中筛选有用信息。由粗到精的描述子筛选方法如下。首先，建立粗描述子矩阵D，每个特征点的粗描述子为一行903列；然后，对计算矩阵每一列的均值按均值与0.5之差的绝对值由小到大排列，并选取前512列组成描述子，即完成粗描述子的降维处理。

（3）扫视匹配搜索

FREAK算法进行描述子匹配时利用人观察寻找事物的扫视方式（即先整体后局部），先对两个待匹配描述子的前128 bit（16 bytes）进行匹配，如果小于设定的阈值T，则继续对两个待匹配描述子后续字节进行匹配。实验证明，扫视匹配搜索利用前16 bytes可剔除超过90%的误匹配描述子，同时匹配速度也有显著提升。而SURF算法进行描述子匹配时，需要通过局部敏感哈希方法(locality-sensitive Hashing, LSH)将浮点型转为二进制描述子，增加了内存开销和运算时间。

（4）方向

为了使算法具备旋转不变性，SURF算法以特征点为中心，计算其在水平和垂直方向的Haar小波滤波器响应值来确定特征点的主方向，计算量较大。而FREAK则采用特征点周围43个采样点中连线最长、对称的45个采样点对来计算特征点方向O：

$O = \frac{1}{M}\sum\limits_{{P_o} \in G} \left( {I\left( {P_o^{{r_1}}} \right) - I\left( {P_o^{{r_2}}} \right)} \right)\frac{{P_o^{{r_1}} - P_o^{{r_2}}}}{{\left| {\left| {P_o^{{r_1}} - P_o^{{r_2}}} \right|} \right|}}$

(6)

式中，G是采样点对的集合；M是采样点对的数目（即45）；P_o^r_i是采样点的空间位置。

2）FREAK特征点匹配

SUFREAK算法采用k-近邻算法（k-nearest neighbors, kNN）进行特征点匹配。令k=2，经过kNN算法筛选仍存在特征点错误匹配的情况，因此再采用随机抽样一致算法进行误匹配剔除。该算法具有较强的抗噪性，能较好地完成对匹配点对的提纯工作。

1.3 KLT光流跟踪算法

基于改进SURF算法的三维注册方法虽然在计算速度上已有所提高，但是仍然无法在视频场景对目标进行实时追踪，且该注册方式没有充分利用视频流之间帧的时序性和相关性。然而，在常见的移动AR应用中，视频流中相邻两帧图像的变化往往较小，因此可以利用这一特点，采用KLT算法的局部搜索方式来获取当前帧与前一帧的变换矩阵，从而完成目标的跟踪注册，使得AR的三维注册更加高效。

KLT是一种基于最优估计的图像特征光流跟踪算法^[14]，通过已知图像帧的特征点推测下一帧特征点的粗略位置。该算法具有较好的抗噪性和实时性，主要基于光流的3个假设：①相邻视频帧之间的亮度恒定；②相邻视频帧之间的目标物体运动值较小；③空间一致性。设视频帧中灰度图像在时刻t像素点M(x，y)的灰度值为I(x，y，t)，在时刻t+dt时，其灰度值为I(x+dt，y+dt，t+dt)，将其按Taylor级数展开如下：

$ \begin{array}{c} I\left( {x + {v_x}{\rm{d}}t, y + {v_y}{\rm{d}}t, t + {\rm{d}}t} \right) = \\ I\left( {x, y, t} \right) + \frac{{\partial I}}{{\partial x}}{\rm{d}}x + \frac{{\partial I}}{{\partial y}}{\rm{d}}y + \frac{{\partial I}}{{\partial t}}{\rm{d}}t + \varepsilon \end{array} $

(7)

式中，ε是二阶无穷小项。而当dt趋近于0时，可得：

$ \frac{{\partial I}}{{\partial x}}{\rm{d}}x + \frac{{\partial I}}{{\partial {\rm{y}}}}{\rm{d}}y + \frac{{\partial I}}{{\partial t}}{\rm{d}}t = 0 $

(8)

令$ u = \frac{{\partial x}}{{\partial t}}$，$ v = \frac{{\partial y}}{{\partial t}}$，假设$ {I_x} = \frac{{\partial I}}{{\partial x}}, {I_y} = \frac{{\partial I}}{{\partial y}}, {I_t} = \frac{{\partial I}}{{\partial t}}$，式（8）两边乘1/dt，则公式变换为：

$ {I_x}u + {I_y}v + {I_t} = 0 $

(9)

此即光流场的基本方程，即光流约束方程。

针对视频尺度变换和运动量较大的图像序列，将高斯金字塔分层与光流算法(Lucas-Kanade, LK)结合，能够较好地完成目标跟踪。将移动端获取的视频流通过高斯采样进行分层，并从最低层金字塔开始进行LK计算，并以低层次计算结果作为下一层的参数，依次类推到金字塔最顶层。在移动终端进行跟踪，通过仿真实验，当设定高斯金字塔层次L=4时，可以有效提高跟踪运算速度。

2 实验与分析

实验软件开发环境为Windows 7 Intel (R) Core i3-2120 CPU，3.3 GHz，4 GB内存；以Eclipse为开发平台，开发包OpenCV2.4.9和ARToolKit for Android 5.2；实验设备为Vivo手机, V3L型号1.5 GHz 8核处理器，3 GB内存。

2.1 SUFREAK算法实验 2.1.1 实验方案

为了验证本文SUFREAK算法的性能，实验选取了SURF、ORB、FREAK（以加速分割检测特征（feature from accelerated segment test，FAST）算法提取特征点）3种算法为对比方法。实验从匹配速度和算法鲁棒性两个方面分别对匹配性能和稳定性进行对比分析，并采用正确匹配点对和匹配分数两个指标对算法进行综合性能评价。其中，匹配性能主要通过匹配速度指标进行衡量，该匹配速度是指特征点检测、描述符提取和特征匹配的综合耗时。稳定性采用旋转、尺度、光照和视角4种变换图像下提取的正确匹配点对与匹配分数两个指标进行衡量。正确匹配点对体现该算法对图像匹配检测的性能，匹配点对数量越多，匹配效果越好^[15]；匹配分数是指两幅匹配图像中筛选出的正确匹配点对与提取出的较少特征点数量之比^[16]，用于衡量各类算法对各种图像变换的不变性，值越大表示区域检测器的鉴别能力越好。匹配分数计算公式如下：

$ {r_m} = \frac{N}{{{\rm{min}}\left( {{n_1}, {n_2}} \right)}} $

(10)

式中，r_m为匹配分数的值；N是两幅图像中提取出的正确匹配点对数量；n₁和n₂表示在两幅待匹配图像上的相同区域内分别检测出的特征点数量；min(n₁, n₂)是n₁和n₂的较小值。

2.1.2 实验数据

实验选取10个建筑场景为图像数据，用于测试算法的实时性和鲁棒性。因测试效果类似，这里只选取其中一个场景进行阐述，如图 4所示，由4组建筑物场景图像构成，每组均为6幅图像（尺寸均为960×720像素）。

2.1.3 匹配速度

为了验证SUFREAK算法的实时性，本文对SUFREAK、SURF、FREAK和ORB算法的平均匹配耗时进行统计，如表 1所示。

将表 1中各算法的匹配平均耗时和匹配点数量进行对比，可发现SUFREAK算法的平均耗时约为SURF算法的27.81%，在计算速度上有很大提升，克服了SURF算法实时性不强的缺陷。SUFREAK算法为了使得算法具备尺度不变性而构建较为耗时的尺度金字塔，因此相比ORB、FREAK算法在运算速度方面处于劣势，但其匹配点对数量较多，匹配效果较好。

2.1.4 图像变换鲁棒性

以图像变换数据集做算法对比测试，验证算法对视角、光照、视角、旋转不变性的鲁棒性，匹配点对与匹配分数实验结果如图 5所示。

光照变换时，各算法的匹配点对数量随着光照亮度下降而减少，其中FREAK算法匹配点对数量下降较为明显，而ORB算法的匹配点对数量波动性相对较小，但其匹配分数较差。本文SUFREAK算法比SURF算法平均匹配分数得分高，且光照鲁棒性更强。原因在于SUFREAK描述子由高斯平滑后的采样点对的灰度值对比生成，高斯平滑处理减少光照的影响，比SURF算法利用邻近像素块的灰度差建立的描述子更具统计性。

视角变换时，各算法对视角变换较为敏感，随着图像视角变化越大，匹配点对数量和匹配分数值下降幅度越大。对比之下，本文SUFREAK算法匹配点对数量最多、匹配分数最高，实验表明其视角变换鲁棒性优于SURF等其他算法。

旋转变换时，各匹配算法在图像旋转45°左右匹配点对数量下降幅度最大，但是在图像旋转接近90°时，匹配点对数量快速回升。同样，匹配分数曲线呈现先下降再上升的趋势。旋转变换中，FREAK和ORB都表现出较强的鲁棒性。而SUFREAK算法匹配点对数量与SURF差距较小，在匹配分数曲线整体上相比SURF算法得分更高，因此旋转鲁棒性强于SURF算法。究其原因，在于SURF算法采用60°扇形窗口在其圆形邻域滑动计算Haar小波组成的矢量来确定特征点主方向。而SUFREAK算法以围绕特征点周围的43个采样点中连线最长、对称的45个采样点对全窗口邻域来确定特征点主方向，受角度变化影响较大。

尺度变换时，各种算法的匹配点对和匹配分数整体呈下降趋势，而SUFREAK算法和SURF算法在下降过程中出现小幅上升。其中，SURF和SUFREAK算法在匹配点对数量和匹配分数上都表现出较强的鲁棒性。在图像变换过程中，SUFREAK算法在整体尺度变换中的鲁棒性稍弱于SURF算法，但是在小尺度变换中鲁棒性强于SURF算法。而ORB和FREAK算法的尺度匹配点对数量和匹配分数曲线都下降得较快，尺度不变性的鲁棒性较差。

实验表明，改进算法SUFREAK相比SURF算法具有更高的运行效率，能满足实时性的要求，并且SUFREAK算法在视角、光照变换下的鲁棒性一定程度上比SURF算法更高，对解决室外复杂环境下视角、光照差异引起的图像匹配不佳问题有一定的帮助。

2.2 基于改进SURF和KLT三维注册实验

为了验证KLT光流跟踪算法对移动AR系统的效率，本文设计对比实验方案如下。首先，采用基于改进SURF和KLT的特点跟踪方法对同一张图像在视频流中构成的帧序列进行图像识别跟踪；然后，对图像匹配模块和目标跟踪模块的耗时分别进行记录；最后，对耗时统计进行对比分析。实验视频数据通过移动Android端的前端摄像头进行获取，视频流的平均帧频约为27~28帧/s，视频图像尺寸为480×320像素大小。KLT光流算法的跟踪效果如图 6所示。图 6（a）是跟踪前一帧的特征点，图 6（b）右图是跟踪后的特征点偏移，红线的长度代表的是目标图像在视频流中前后帧的偏移量（运动量）。

图 7、图 8分别为改进的SURF图像匹配算法和KLT跟踪算法的耗时统计。基于改进SURF算法的图像匹配对一张图像进行匹配的平均耗时约为222.11 ms，而使用KLT光流跟踪算法平均耗时约为97.85 ms，可知KLT跟踪算法耗时约为改进SURF图像匹配算法的44.05%，因此可以有效替代图像匹配算法进行目标跟踪，提高了移动AR系统的流畅性，体现出KLT跟踪算法在时间上的优势。

3 系统实现及运行结果

本文基于改进SURF和KLT算法的三维注册方法设计并实现了一款基于Android的移动AR的原型系统，应用于户外建筑物识别及信息增强。首先通过移动端GPS获取用户当前位置信息，并以此为中心，在一定半径内进行空间检索，查找这一空间区域的建筑物图像，进行匹配图像粗筛选。然后，将移动端对准建筑物图像，进行建筑图像的匹配和跟踪，并通过叠加文字和三维模型等信息对建筑物进行增强现实，如图 9所示。最后，通过对建筑进行遮挡、移动等实验，系统实现了对建筑的快速识别，且识别跟踪效率较高。

4 结语

本文提出一种基于改进SURF和KLT算法的AR现实户外三维注册方法，该方法结合FREAK算法对SURF算法进行改进，使得改进算法SUFREAK既继承了SURF鲁棒性强的特点，又具有FREAK描述子快速提取的优势，有效弥补了SURF算法实时性不强的缺点，实现对户外建筑物场景的高效识别。在完成图像识别后，采用光流跟踪方法，有效提升了系统的实时性和流程性。实验结果表明，该三维注册方法鲁棒性强、注册精度高、实时性好，满足户外移动AR系统对三维注册识别效率和实时性的要求。

本文改进算法SUFREAK虽然在匹配速度上有较大的提升，但其在匹配速度上仍慢于ORB算法，因此下一步工作将考虑在不影响算法鲁棒性的基础上，利用图像的二分法对图像进行分块处理，以期提高匹配效率。