赵越, 李晶皎, 李海鹏,杨丹
东北大学 信息科学与工程学院，辽宁 沈阳 110819
收稿日期: 2015-02-11
基金项目: 国家自然科学基金资助项目(60970157); 中央高校基础科研青年教师创新基金资助项目(N130404004).
作者简介: 赵越(1979-),女,辽宁抚顺人,东北大学博士研究生,渤海大学讲师; 李晶皎(1964-),女,辽宁沈阳人,东北大学教授,博士生导师.

摘要: 针对增强现实场景跟踪注册存在速度较慢等问题，提出了一种基于改进随机蕨的增强现实跟踪注册算法.该算法采用离线训练和在线跟踪两个模块.提出了一种嵌入式蕨分类器以提高特征点匹配精度，该分类器采用有监督的降维方法，并利用了所有可能的信息.通过该分类器进行特征匹配，进而计算摄像机位姿并渲染注册虚拟物体.实验结果证明，提出的嵌入式蕨在平均分类精度上优于其他算法.平均处理每帧图像的时间为34.22 ms，基本满足实时性.
关键词: 随机蕨降维分类器跟踪增强现实
Real-Time Tracking and Registration Algorithm of Scenarios of Augmented Reality Based on Improved Random Fern
ZHAO Yue, LI Jing-jiao, LI Hai-peng,YANG Dan
School of Information Science & Engineering, Northeastern University, Shenyang 110819, China.
Corresponding author: ZHAO Yue, E-mail: zy_ky7777@126.com
Abstract: Because of the slow speed of tracking and registration on scenarios of augmented reality, an algorithm was proposed based on the improved random fern on tracking and registration of augmented reality. The proposed algorithm has the offline training section and the online tracking section. A classifier based on the embedded fern was proposed. In the developed classifier, a supervised dimensionality reduction method and all possible information were used. What’s more, it was also used for the feature matching, and then camera pose was computed and virtual objects were rendered and registered. Experimental results show that the proposed algorithm is superior to other algorithms on the average classification accuracy. The average processing time of each frame is about 34.22 ms, which can almost meet the real-time.
Key words: random ferndimensionality reductionclassifiertrackingaugmented reality 增强现实(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所示.
图1(Figure 1)

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

1.1 离线训练阶段在离线训练阶段，主要完成以下几个步骤：
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 在线跟踪注册阶段在线跟踪注册阶段，主要完成以下几个步骤：
1) 输入非训练视频流.
2) 对视频流进行预处理.
3) 利用FAST方法进行特征点检测，并提取特征点Walsh-Hadamard描述符.
4) 将提取到的描述符投入到离线阶段训练得到的分类器中，进行2D-3D特征点的匹配.
5) 利用顺序抽样一致性算法(PROSAC)对已匹配特征点对估计两图像的外极几何关系，计算摄像机位姿.
6) 渲染注册虚拟目标，直到视频的最后一帧结束.
2 基于随机蕨的嵌入式分类器2.1 把特征点匹配看作分类问题给定一个视频帧图像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点的确定性信息.这里的分类方法不需要保存描述符，因为如果最高类条件概率和次高类条件概率间的距离比小于阈值ε，那么就确定了对应关系.
对于分类来说，本文提出了一种对随机蕨原理的扩展，在分类过程中利用了所有可用的描述符，而几乎保持了相同的运行时间和存储信息.
2.2 基本随机蕨随机蕨算法是一种机器学习分类方法，是在随机森林算法的基础上改进而来的，是一种半朴素贝叶斯分类器(SNBC，semi-naive Bayesian classifier)^[6].随机蕨算法通过对随机森林中树的每层节点选取相同决策而建立一种非层次的分配结构.
随机蕨由全部基分类器组成.在每一个基分类器中，通过做S个二元决策使得特征空间被唯一分离到L=2^S个箱子中的一个.在训练过程中，计算每个箱子类的发生，定义为类依赖概率.基分类器决策以半朴素贝叶斯方式联合.训练的目的是决定这S个分离参数，并估计到蕨F_m和类c_i的每个箱子l的类条件概率P(F_m=l|c_i).简化为
其中:l表示蕨F_m的L=2^S个箱子中的一个;p_l,ci是箱子l投票给类c_i的概率.因此，把所有类条件概率写进一个F×L×C(蕨的数量×箱子的数量×类的数量)的矩阵F中，且∑p_l,ci=1.在训练过程中，通过简单计算标记的数据点进到对应的箱子的数量来估计概率：
其中:N_l,ci是估计到蕨箱子l的类c_i的被标记的训练样本的数量;N_ci是类c_i的全部样本数量.
一旦通过训练数据估计得到蕨矩阵F，新的测试数据点被放到所有的蕨F_m中，对应箱子l的概率，测试点估计以半朴素贝叶斯方式联合，最终分配到类c^*为
2.3 嵌入式蕨分类器本文的方法建立在随机蕨的基础上.假设已经拥有了一组包含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和通过分析对应数据点记录：
其中，K^m = (r₁^m,r₂^m,… ,r^m_S)是一组S个随机选择特征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为一组线性组合:
其中:V^m是B×S映射矩阵；J^m是一个S×1位移向量.最直接的定义映射矩阵V^m的方式是在一种随机状态下选择它，这就经常产生一种被称为倾斜森林的分类器^[7].然而，这将忽略有用的训练数据标志，可以被利用找到一个改进的映射.基于这个原因，每个蕨确定一个映射矩阵，可以从各类间最佳的区分不同的类.
本文核心思想是为了捕获训练数据集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)解决:
其中:o_x和o_y是两个正则化参数;μ_x是系数;I是单位矩阵.正如文献[9]研究所示，通过o_y的 Y的正则化并没有影响X的映射，因此，这里设o_y=0，根据文献[7]，使o_x趋近于10^-6.
考虑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)中描述的半朴素贝叶斯方法得到的蕨的概率.
3 实验结果与分析实验在台式计算机上进行，用以评估本文的算法，CPU主频为3.1 GHz，内存为4 GB，显卡为NVIDIA GeForce GT 630 M.
假设已通过任意SFM方法生成一个感兴趣区域的三维重构.已得到了所有摄像机位姿，稀疏点云的三维坐标，及被用于3D点和所有相应描述符的三角测量的所有图像点列表.
3.1 几种匹配算法的性能对比这里使用两个常用的数据库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点的数量超过几百个时，其运行时间变得很慢.
3.2 增强现实注册结果实验采用室内视频序列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

4 结论1) 本文提出的嵌入式蕨在平均分类精度上有所提高.
2) 本文提出的算法的每帧图像处理的平均总时间为34.22 ms，基本可以满足实时性要求.
3) 本文提出的算法在室内外场景下，注册效果均令人满意.

参考文献

[1]	Azuma R, Baillot Y, Behringer R, et al.Recent advances in augmented reality[J].IEEE Computer Graphics and Applications, 2001, 21(6):34-47.(1)
[2]	Davison A, Reid I, Molton N D, et al. Mono-SLAM:realtime single camera SLAM[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(6):1052-1067.(3)
[3]	张运超,陈靖,王涌天,等.基于移动增强现实的智慧城市导览[J].计算机研究与发展,2014, 51(2):302-310. (Zhang Yun-chao, Chen Jing, Wang Yong-tian, et al.Smart city guide using mobile augmented reality[J].Journal of Computer Research and Development, 2014, 51(2):302-310.)(2)
[4]	Mooser J, You S, Neumann U, et al.Applying robust structure from motion to markerless augmented reality[C]//Applications of Computer Vision.Snowbird, 2009:1-8.(1)
[5]	Hel-Or Y, Hel-Or H.Real-time pattern matching using projection kernels[J].Pattern Analysis and Machine Intelligence, 2005, 27(9):1430-1445.(1)
[6]	Zheng F, Webb G I.A comparative study of semi-naive Bayes methods in classification learning[C]// Proceedings of the Fourth Australasian Data Mining Conference.Sydney, 2005:141-156.(1)
[7]	Heath D, Kasif S, Salzberg S.Induction of oblique decision trees[J].Journal of Artificial Intelligence Research, 1993, 135:3-12.(2)
[8]	Hotelling H.Relations between two sets of variates[J].Biometrika, 1936, 28:312-377.(1)
[9]	Sun L, Ji S, Ye J.Canonical correlation analysis for multilabel classification:a least-squares formulation, extensions, and analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1):194-200.(1)
[10]	Li Y, Snavely N, Huttenlocher D P.Location recognition using prioritized feature matching[C]//Proceedings of 11th European Conference on Computer Vision.Heraklion, 2010:791-804.(1)

1

本文献在全文中的定位：
... 是一种将虚拟信息通过计算机系统叠加到真实世界的技术^[1] .对于增强现实技术来说，识别和跟踪自然特征相对来说更加困难.而较 ...



3

本文献在全文中的定位：
... Davison等^[2]提出了基于定位和三维重建(SLAM)同时进行的场景注册方法，但其时间复 ...

... 是不同算法每帧图像的增强现实平均处理时间.将本文提出的算法与文献[2]的算法进行比较，本文提出算法的每帧图像处理的平均总时间为34.22 ms ...

... 文献[2]算法 ...



2

本文献在全文中的定位：
... 为特征点个数，因此只适用N不太大的情况.张运超等^[3]提出了一种通过智能手机实现智慧城市导览的增强现实方法.该方法采 ...

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



1

本文献在全文中的定位：
... 户多尺度、多时空的信息需求，但无法处理光照、遮挡等情况. Mooser等^[4]提出了一种鲁棒的运动中恢复结构的方法应用于较大场景的定位中.该 ...



1

本文献在全文中的定位：
... 特征点，每个32×32像素大小的图像块被投影在一个20维的Walsh-Hadamard核上^[5]. ...



1

本文献在全文中的定位：
... 改进而来的，是一种半朴素贝叶斯分类器(SNBC，semi-naive Bayesian classifier)^[6].随机蕨算法通过对随机森林中树的每层节点选取相同决策而建立一种 ...



2

本文献在全文中的定位：
... 在一种随机状态下选择它，这就经常产生一种被称为倾斜森林的分类器^[7].然而，这将忽略有用的训练数据标志，可以被利用找到一个改进的映 ...

... 化并没有影响X的映射，因此，这里设o_y=0，根据文献[7]，使o_x趋近于10^-6. ...



1

本文献在全文中的定位：
... 为达到上述目的，本文提出使用典型相关分析(CCA)^[8]方法，能够从两个不同视图有效识别一般潜在的空间.这样，关联给定 ...



1

本文献在全文中的定位：
... 是两个正则化参数;μ_x是系数;I是单位矩阵.正如文献[9]研究所示，通过o_y的 Y的正则化并没有影响X的 ...



1

本文献在全文中的定位：
... 这里使用两个常用的数据库Dubrovnik和Rome^[10]来进行算法性能的评估.Dubrovnik由约6千个图像，200万个点和1千万个描述 ...