增强现实(augmented reality，AR)，是一种将虚拟信息通过计算机系统叠加到真实世界的技术^[1] .对于增强现实技术来说，识别和跟踪自然特征相对来说更加困难.而较大的场景则包含了更多更复杂的情况，其跟踪定位问题更成为学者们近年来的研究热点.

Davison等^[2]提出了基于定位和三维重建(SLAM)同时进行的场景注册方法，但其时间复杂度为O(N²)，N为特征点个数，因此只适用N不太大的情况.张运超等^[3]提出了一种通过智能手机实现智慧城市导览的增强现实方法.该方法采用动态区域划分及BHKM聚类的大量场景识别算法，能够实现用户位置的精确定位.BRlSK与光流结合的特征跟踪注册方法满足了用户多尺度、多时空的信息需求，但无法处理光照、遮挡等情况. Mooser等^[4]提出了一种鲁棒的运动中恢复结构的方法应用于较大场景的定位中.该方法离线阶段建立3D点云，在线阶段通过近似最近邻匹配方法进行2D-3D特征点匹配，从而进行增强现实的注册.但该方法的运行时间也依赖于3D点云的大小，当3D点云较大时，2D-3D特征点匹配耗时很长，实时性不够好.

针对以上问题，本文提出了一种基于改进随机蕨的增强现实跟踪注册算法.本文提出的方法在运行时间上不依赖于真实3D点云的大小，基本能够满足实时性需求；通过利用所有可能的特征信息使定位更加准确.

本文提出的增强现实场景跟踪注册算法包括离线训练阶段和在线跟踪注册阶段，算法流程图如图 1所示.

图1(Figure 1)

图1 本文算法流程图 Fig. 1 The flowchart of the algorithm

在离线训练阶段，主要完成以下几个步骤：

1) 输入训练视频流.

2) 用Subtrack Optimization^[3]的SFM(structure from motion)方法建立3D点云.

3) 对3D点云中的3D点进行特征描述符提取.对于点云，它自己仅仅包含了几何信息，称为每个结构点的3D定位.对于每个3D点必须和一个可以在现阶段相匹配的视觉描述符相关联.使用Walsh-Hadamard描述符提取特征点，每个32×32像素大小的图像块被投影在一个20维的Walsh-Hadamard核上^[5].

4) 对提取的特征点描述符建立分类器，此分类器采用本文基于随机蕨的嵌入式分类器.

在线跟踪注册阶段，主要完成以下几个步骤：

1) 输入非训练视频流.

2) 对视频流进行预处理.

3) 利用FAST方法进行特征点检测，并提取特征点Walsh-Hadamard描述符.

4) 将提取到的描述符投入到离线阶段训练得到的分类器中，进行2D-3D特征点的匹配.

5) 利用顺序抽样一致性算法(PROSAC)对已匹配特征点对估计两图像的外极几何关系，计算摄像机位姿.

6) 渲染注册虚拟目标，直到视频的最后一帧结束.

给定一个视频帧图像Q，增强现实的目标是关于提供的稀疏3D点云而确认精确的6自由度摄像机位姿，进而进行虚拟注册.该方法的主要步骤如下：①提取图像Q的特征；②通过特征匹配建立2D-3D的对应；③摄像机位姿估计.

这里得到的稀疏3D点模型由M个3D点P^j 组成.对于每一个3D点P^j，用D_i^j∈R^D表示3D点P^j的一系列描述符，即包含被用来对P^j作三角测量的图像点的所有特征描述符.需要注意的是，一些3D点拥有数百个相关联的特征描述符，且这些具有最大量的对应描述符的点对于定位来说可能拥有最大的信息量，例如一个塔上的一点能够从许多视角观察到.目的是将在视频帧图像Q中检测到的这N个2D特征点(其描述符用Q_i∈R^D 表示)与M个3D点P^j进行匹配.通过制定把匹配当做分类问题而使用所有可用的信息.在训练分类器后，不必保留训练样本，因此，允许将所有描述符用于训练.其基本思想是，每个三维点由一个唯一的类标记表示(1,…,M)，及其相应的描述符被作用于判别分类标记的训练数据.其利用了判别设定的所有描述符(对比于最近邻分配)，这将产生一种改进的集的对应关系.

训练后，把所有查询描述符Q_i放到分类器中，并获得一个1×M的向量类条件概率，表示假设对应到3D点的确定性信息.这里的分类方法不需要保存描述符，因为如果最高类条件概率和次高类条件概率间的距离比小于阈值ε，那么就确定了对应关系.

对于分类来说，本文提出了一种对随机蕨原理的扩展，在分类过程中利用了所有可用的描述符，而几乎保持了相同的运行时间和存储信息.

随机蕨算法是一种机器学习分类方法，是在随机森林算法的基础上改进而来的，是一种半朴素贝叶斯分类器(SNBC，semi-naive Bayesian classifier)^[6].随机蕨算法通过对随机森林中树的每层节点选取相同决策而建立一种非层次的分配结构.

随机蕨由全部基分类器组成.在每一个基分类器中，通过做S个二元决策使得特征空间被唯一分离到L=2^S个箱子中的一个.在训练过程中，计算每个箱子类的发生，定义为类依赖概率.基分类器决策以半朴素贝叶斯方式联合.训练的目的是决定这S个分离参数，并估计到蕨F_m和类c_i的每个箱子l的类条件概率P(F_m=l|c_i).简化为

一旦通过训练数据估计得到蕨矩阵F，新的测试数据点被放到所有的蕨F_m中，对应箱子l的概率，测试点估计以半朴素贝叶斯方式联合，最终分配到类c^*为

本文的方法建立在随机蕨的基础上.假设已经拥有了一组包含N个数据点的集合{X₁,X₂,…,X_N}，该集合在一个D维特征空间，即，X_i∈R^D.把数据点堆叠到一起生成了N×D训练数据矩阵X∈R^N×D，其中，单元素x_id表示第i个数据点的第d个特征.

和传统的随机蕨相似，主要目的是把一个测试数据点分配到每个蕨L=2^S个箱子中的一个.因此，目标是要找到D维数据点到第m个蕨的S维二进制分配向量b^m∈{0,1}^S的映射，这唯一地分配了特征空间并允许把每一个特征点分配到L=2^S个箱子中的一个.

在矩阵符号中，传统的蕨获得二进制分配向量b^m通过随机选择特征IDs和通过分析对应数据点记录：

本文方法的核心思想是选择更多的B>S的特征，然后映射数据点的B个特征到最后的S维空间.对于每一个蕨随机选择一定数量的特征B≤D，但是B>S，对第m 个蕨减小输入训练矩阵X到一个蕨特定的N×B输入矩阵X^m={x_id|∀i and d∈K^m}，其中K^m是一组B个随机选择特征IDs.这里，进一步定义二进制分配向量b^m为一组线性组合:

本文核心思想是为了捕获训练数据集X^m(由随机选择的特征组成)的结构用于有监督的降维方法，确定最佳二元分离参数(V^m,J^m).为达到上述目的，本文提出使用典型相关分析(CCA)^[8]方法，能够从两个不同视图有效识别一般潜在的空间.这样，关联给定的特征和相对应的标记空间，组成了找到最佳二元分离的基础.

假设每个数据点x_i已经关联了相应的标签y_i∈{1,2,…,C}，则可以建立一个数据集标签矩阵Y∈{0,1}^N×C，如果数据点i属于类C，则相对应的条目y_il是1，否则是0.典型相关分析(CCA)试图找到两个基础向量v_x和v_y的集合，以便这些基础向量上的变量映射X^mv_x和Y^mv_y之间的关联被相互最大化.相关系数ρ定义为

系数ρ相对于基础向量按比例不变，因此，CCA也可以用式(7)表示：

为了找到基础向量，取相关系数ρ的最大值，必须解决一个广义特征值问题.用特征值问题的正则化来避免过度拟合，通过等式(8)解决:

考虑S主导的特征向量，从式(8)定义的广义特征值问题的解决而获得，像B×S映射矩阵V^m，允许将任何新的数据点放入这个新的嵌入式空间.在每一维分别定义分离值，通过简单的阈值，投入的值在训练数据值的中值，产生位移向量J^m.这样，通过式(5)，最后获得了所需要的S×1二元向量b^m，唯一分配数据点到2^S 个箱子中的一个.图 2说明了本文的嵌入式蕨用于一个单独蕨上的概念.

图2(Figure 2)

图2 本文方法用于一个单独的基础分类器 Fig. 2 The method for a single base classifier (a)—训练过程； (b)—测试过程.

①输入数据矩阵X，通过随机选择特征降维集合K^m而减少到一个特定蕨矩阵X^m.这个矩阵和提供的CCA中的标签矩阵一起使用，提出了一个被V^m定义的新的嵌入式空间.这种映射使每一个训练样本能够分配到一个箱子，和类的条件概率p_l,ci的计算一样.②在测试同样选择的特征降维时，通过训练学习到的映射被应用到把样本分配到一个箱子(二进制向量b^m).最后的基础分类器概率以半朴素贝叶斯方式联合得到.以上步骤仅仅是一个单独的基础分类器的形成和使用过程.重复前面的描述步骤，通过映射矩阵和位移向量(V^m,J^m)获得了一组随机蕨.注意，这里获得的映射矩阵，降维特征矩阵X^m对于每个蕨是不同的，而对于所有CCA步骤，标签矩阵Y是相同的.因此，和传统随机蕨形成对比，对于每个蕨仅通过选择特征降维来注入随机性，因为每个蕨的映射被估计在一个特定的方式.最终的映射到二元向量b^m被用来定义类的条件概率p_l,ci，通过计算估计到相应箱子的类成员的数目来得到.在测试过程中数据点映射到每个蕨的不同映射空间使用式(5)中的(V^m,J^m)，提供了类条件概率，最终的分类结果是通过联合如式(3)中描述的半朴素贝叶斯方法得到的蕨的概率.

实验在台式计算机上进行，用以评估本文的算法，CPU主频为3.1 GHz，内存为4 GB，显卡为NVIDIA GeForce GT 630 M.

假设已通过任意SFM方法生成一个感兴趣区域的三维重构.已得到了所有摄像机位姿，稀疏点云的三维坐标，及被用于3D点和所有相应描述符的三角测量的所有图像点列表.

这里使用两个常用的数据库Dubrovnik和Rome^[10]来进行算法性能的评估.Dubrovnik由约6千个图像，200万个点和1千万个描述符组成.Rome由约1万5千个图像，400万个点和21亿个描述符组成.两个数据库中，从稀疏3D点云确认潜在的视觉集，把它们放入到几个更小的视图单元.潜在的视觉集决定了3D点云和在当前视图单元里必须考虑的对应的描述符子集.

通过使用本文提出的分类器方法进行特征匹配，和其他标准最近邻匹配方法、随机蕨方法和随机森林方法相比较.用K折交叉验证(K=10)验证每个视觉集.而最近邻方法采用K-D树最近邻方法.对所有蕨方法使用相同的基分类器数F=30.随机蕨中每个基分类器采用10个二元决策.随机森林中的树是完全分裂树，且固定估计节点测试的数量为D.本文提出分类器的S取值16，B取值25.表 1显示了在两个数据库上的平均分类精度.从表中可以看出本文提出方法在两个数据库上的实验结果，在平均分类精度上高于其他几种方法.

表1(Table 1)

表1 不同算法采用10折交叉验证法的平均分类精度Table 1 Mean classification accuracies for 10-fold cross validation in different methods % 算法 Rome Dubrovnik 随机蕨法 87.85 92.14 随机森林法 88.76 96.21 最近邻法 94.28 95.87 本文的法 97.33 98.76

表1 不同算法采用10折交叉验证法的平均分类精度 Table 1 Mean classification accuracies for 10-fold cross validation in different methods

运行时间上，本文提出方法不依赖于3D点的数量，且对于分类器来说是基本稳定的.本文提出方法比随机蕨方法平均时间长，是其1.12倍，这是因为映射的原因.而随机森林相对更慢一些，是随机蕨方法的1.41倍.最近邻方法的运行时间依赖于3D点的数量，所以，当数据库中3D点的数量超过几百个时，其运行时间变得很慢.

实验采用室内视频序列room(长度为786帧)和室外视频序列building(长度为1 372帧),视频序列均为320×240 像素、帧率为30帧／s.图 3为本文算法的增强现实跟踪注册结果.从图 3可以看出，无论是室内场景还是室外场景，注册效果令人满意，证明了本文提出算法的有效性.

图3(Figure 3)

图3 本文算法增强现实跟踪注册结果 Fig. 3 The results of tracking and registration of the proposed algorithms (a)—为视频序列room的跟踪注册结果； (b)—为视频序列building的跟踪注册结果.

表 2是不同算法每帧图像的增强现实平均处理时间.将本文提出的算法与文献[2]的算法进行比较，本文提出算法的每帧图像处理的平均总时间为34.22 ms，基本可以满足实时性要求.而文献[2]的算法的平均总时间为161.42 ms，是本文提出方法的4.7倍之多.这是因为3D的数量太多从而导致匹配过程消耗了过多时间.

表2(Table 2)

表2 不同方法每帧图像的增强现实平均跟踪注册时间Table 2 The average processing time of augmented reality of each frame in different algorithms ms 步骤 本文算法 文献[2]算法 图像预处理 1.20 1.20 特征点检测和描述 4.10 7.40 特征点匹配 19.40 143.30 摄像机位姿计算 8.30 8.30 OpenGL绘图 1.22 1.22 总时间 34.22 161.42

表2 不同方法每帧图像的增强现实平均跟踪注册时间 Table 2 The average processing time of augmented reality of each frame in different algorithms

1) 本文提出的嵌入式蕨在平均分类精度上有所提高.

2) 本文提出的算法的每帧图像处理的平均总时间为34.22 ms，基本可以满足实时性要求.

3) 本文提出的算法在室内外场景下，注册效果均令人满意.