1. 引言
当前智能手机作为应用最广的装置之一，在硬件上已经允许提供AR (Augment Reality)必须的三维场景。但是AR应用要想实现跟踪，物体检测的功能，就必须获得世界的详细的三维场景，而且由于显示场景总是在不停地发生变化，要求算法能够快速地进行场景的更改和修正。所以获取周围环境信息与当前位置是智能手机上实现增强现实应用的必要条件。原本一直活跃在机器人领域的SLAM算法进入AR的视野。
同步定位建图(Simultaneous Localization and Mapping，简称SLAM)最早由Randall Smith和Peter Cheeseman等人于1988年提出 [1]，最早被用于机器人定位问题。SLAM可以描述为未知环境中估计移动传感器的位置，与此同时进行周围三维环境的重建问题。
2014年提出的ORB-SLAM算法(Oriented FAST and Rotated BRIEF SLAM，简称ORB-SLAM) [2] 在PTAM的基础上加入了闭环检测 [3]，闭环 [4]，以及在大规模时的误差调整方法 [5]，以此构成一个新的SLAM系统。ORB-SLAM系统克服了PTAM的主要不足，但是由于ORB-SLAM仍然基于特征点，所以依然只能得到稀疏的地图点。
跟ORB同时提出的直接SLAM算法LSD-SLAM (Large-Scale Direct Monocular SLAM，简称LSD-SLAM) [6]，实现了一个实时的半稠密SLAM算法。这种方法使用直接图像对齐结合基于滤波的半稠密深度图估计。同样使用直接方法进行追踪的还有2010年提出的DTAM (Dense Tracking and Mapping，简称DTAM) [7]。与LSD-SLAM不同的是DTAM是一个生成稠密地图的SLAM算法。
在LSD-SLAM提出后不久，ORB-SLAM的作者对LSD-SLAM半稠密原理 [8] 进行修改，得到了一种适用于宽基线帧之间的半稠密重建方法 [9]。由于它的半稠密方法是在宽基线帧之间的，它的理论上的误差必定小于窄基线帧之间的计算。并且通过新的融合方式和对异常点严格的检测标准，产生了令人难以置信的结果。
对于现今的SLAM算法来说，可以根据它所生成的地图密度分为稀疏，半稠密和稠密三种。其中稀疏地图SLAM主要用于定位，基本丧失了外界环境的形状信息，优点是速度很快，修正和使用的时候速度都很快，当前很多基于特征的方法都是使用的这种制图。稠密建图会将图像中的所有区域的形状及纹理都展示出来，但是由于点的数量过于庞大，需要在当前最高性能的GPU上工作。而半稠密建图综合了稀疏建图速度快和稠密制图具备形状和轮廓信息的特点，在产生具备大部分形状信息和高纹理区域地图的同时摆脱对GPU并行计算的依赖，使用CPU并行计算生成地图。显然半稠密的地图可以得到更多的环境信息，用途更多。
目前的AR设备主要是智能手机和其他专有设备，智能手机相对于专用设备来说更加普及，更加廉价。但是目前在智能手机上的SLAM算法能够达到实时性要求的并不多。本实验的目的是实现智能手机上的实时定位与三维建模功能。智能手机的实时定位功能基于最新提出的ORB-SLAM算法。ORB-SLAM目前作为最新的SLAM方案之一，还没有将其移植到手机上的先例。但是ORB-SLAM公布出的开源算法中并没有之后加入的半稠密的功能，只能得到稀疏的点云。稀疏的地图只在追踪相机的位置的时候有用，不能提供给AR应用提供场景的有效信息。
主要工作是完成了智能手机上基于ORB-SLAM算法的实时定位功能，并且优化ORB-SLAM在智能手机上的运行效率。之后根据论文 [9] 中半稠密的原理实现了基于ORB-SLAM满足性能要求的半稠密三维重构。
主要内容可以分为以下三点：
(1) 将ORB算法移植到Android手机上，优化算法在Android上的实现效果。
(2) 在Android平台上重建ORB-SLAM的输入输出部分，改进在Android上的运行效率。
(3) 根据论文 [9] 独立实现满足性能需要的基于ORB-SLAM算法的半稠密建模功能。
2. 算法设计
目的是在Android实现满足实时性要求的半稠密SLAM算法。总体任务可以划分成两个部分：1) 选择合适的SLAM算法，SLAM算法是整个项目的核心模块，通过摄像机输入连续的图像在确定摄像机位置的同时建立周围环境的半稠密的三维模型；2) SLAM算法向Android平台的移植，这里包含在Android上获取SLAM算法需要的参数，获取Android摄像机的产生的图像作为输入，以及Android的应用层与算法所在的Native的交互。
2.1. SLAM算法的选择
最新的SLAM算法有很多种，像LSD-SLAM、DPPTAM [10]、DTAM和ORB-SLAM，繁多的SLAM系统各自有着各自的优点和缺陷。DTAM使用的直接法，但是由于直接生成稠密地图的原因，需要的运算量非常大，需要GPU参与并行运算，移植到Android程序上比较困难。DPPTAM与LSD-SLAM的原理一致，都是直接使用图片像素进行的相机位姿的修正，最后生成半稠密的地图，包含了场景中高梯度的区域。一般高梯度的区域就包含了场景中主要的形状信息。但是对于直接法SLAM来说，由于其涉及到每个像素的实际位置，需要的相机参数信息非常严格。由于手机平台的限制，在手机上只能算出相机内参的理想值，并且得不到畸变参数。畸变参数只有通过标定获取，对于用户来说，进行相机标定是不现实的。排除了直接法SLAM，就只能使用基于特征点的SLAM应用来减小相机畸变参数的不准确所造成的影响。
所以选择了最新的基于特征点的SLAM算法ORB-SLAM算法，在它的基础上实现半稠密算法，获取包含场景三维形状的地图。
2.2. 基于ORB-SLAM的半稠密
ORB-SLAM的半稠密算法是一个适用于宽基线的半稠密算法。它只使用关键帧进行半稠密算法的计算，对于任意两个关键帧之间，在极线上搜索同名点，逐像素计算高梯度区域内点的逆深度，然后使用卡方检验滤去异常值，使用方差的倒数计算逆深度的加权平均值。最后将改点投影到相邻的关键帧上，寻找投影点附近的兼容点，只有找到兼容点的邻近关键帧的数量大于某个阈值时，才会保留改点。
基于ORB-SLAM半稠密的实现是按照ORB-SLAM半稠密论文Probabilistic Semi-Dense Mapping from Highly Accurate Feature-Based Monocular SLAM [11] 中的原理进行的，为了加快程序的运行速度，对中间有些细微的地方做了修改。以下是方法的大致步骤：
(1) 对于每一个关键帧，进行逐像素的计算高梯度区域的逆深度。每一个像素计算在N个邻近关键帧上的极线，沿极线搜索改点的同名点，根据同名点和逆深度计算出一个逆深度的假定值。这样对于一个关键帧上每个像素就得到了N个对应于邻近关键帧的假定值。
(2) 每一个逆深度假定值都符合应当是一个高斯分布。在不考虑相机位置计算误差的情况下，这个高斯分布只受图像噪声、视差和匹配错误的影响。
(3) 由于在关键帧上的极线很宽，在图像上的搜索区域就会很大。为了处理相似像素点和梯度等值线区域造成的错误点，我们从N个假定值中得到其中一个最大数量的相互兼容点的子集，对这个子集中的逆深度进行融合。每一个在逆深度图上的逆深度都应该符合一个高斯分布。
(4) 由 [11] 中提到的正规化步骤，将上几步得到的点与周围点进行平滑调整。将一个像素点的逆深度设置为周围点的加权平均值。
(5) 在每个关键帧的深度都已经计算出来后，对于每一个点将其投影到他的邻近关键帧上。比较投影点与周围邻近点的一致性，邻近关键帧中一致点数量较少的时候，认为该点是异常点并删除该点。对于存在较多数量关键帧的邻近点数量，将深度设置为优化后的参数。
3. Android上的移植和优化
3.1. ORB-SLAM在Android上的优化
ORB-SLAM在电脑上运行速度非常快，一般在每帧50毫秒左右，但是在手机上的运行结果并不理想，在手机上不加任何修改或优化的运行时间是每帧1秒左右，完全不能够满足实时运行的需要。所以在Android上的SLAM需要进行特别的修改和优化。并且优化应当在不影响算法本身的运行结果情况下进行。
3.1.1. 相机输入调整
由于算法本身是一个对图片进行处理的过程可以将相机输入的图片进行缩放后再运算，缩放图片肯定可以提升算法的运行效率。在获得相机输入的时候，将图片按比例缩放到宽为400像素的固定值。
3.1.2. 修改ORB-SLAM的参数需求
ORB-SLAM是一个基于特征点的SLAM算法，需要一定的特征点才能够进行实时定位。这里可以优化的地方有两个方面，一个是特征点提取时的总数量要求，另外一个是当前关键帧没有丢失的特征点数量要求。我将特征点提取的总数量设置为原先的一半，原先每张图片要求提取1000个特征点，我将它设置为500，大大加快了特征匹配的时间。另一方面将追踪失败的特征点匹配数量要求改为原先的0.8。经过优化后算法明显的加快，并且由于初始化的要求降低，所以初始化更加容易，这里进行的参数调整将每帧的时间减少0.5秒。
3.1.3. 多线程优化
在算法中运行中，可以对算法中耗时较长的地方进行多线程的优化来提高算法的运行速度。具体方法是运行时加入算法时间的输出，着重优化算法耗时较长的部分。由于算法的主要耗时集中在循环内部，所以可以使用OpenMP并行加快算法的运行。主要进行多线程优化的部分集中在两个地方。
一是算法初始化寻找特征点匹配是通过RANSAC (随机抽样一致性算法)方法计算照片之间的本征矩阵时的运算，这里简单描述一下计算步骤：1) 在当前已经匹配点的集合中，随机选取8对同名点计算这八个点之间的本征矩阵，计算出本征矩阵后，将匹配的其余点代入计算实际点与本征矩阵计算出的极线的距离，以距离作为误差值，获得一个对当前计算出的本征矩阵的总体误差；2) 进行200次随机选取，选取总体误差最小的本征矩阵作为图像的本征矩阵。这个部分只在算法初始化的时候用到，能够将每帧初始化的时间提升0.1秒。
二是在特征点提取的部分可以进行多线程的优化。这里简单描述下特征点提取的流程，首先将图像分成若干个网格，在每一网格中提取特征点，分区域进行特征树的构建，主要是为了能够在每个区域存在特征点，返回后计算每个特征的特征描述符，这里能够进行多线程优化的地方有两个：一是在网格中提取特征点，另外一个是在计算每个特征的特征描述符上，其他步骤不适合进行多线程的优化。在这里进行的多线程优化可以将每帧的时间减少0.3秒左右。
3.2. Android的输入板块
SLAM算法在Android上的输入主要有三个部分，一个是配置文件的读取，二是相机标定参数的获取，三是相机的输入。
3.2.1. 配置文件的输入
配置文件包括两个部分，一个是应用本身的配置使用，应用本身的设置使用SharedPreferences保存。另外的SLAM算法的配置和词典文件放到Asserts中，在第一次运行的时候将Asserts中的内容拷贝到Android应用的文件目录files文件夹下。这里的词典文件被用于SLAM的重定位和闭环检测的地方。由于词典文件是一个143 M大小的庞然大物，手机上读取词典文件一般要花费两分钟的时间。又因为词典可以在程序运行的时候自动从场景中提取，所以这里将词典文件设置为空词典，由之后的运行进行提取。
3.2.2. 相机标定参数的获取
根据Computer Vision: Algorithms and Applications ( [12] )中提到的相机参数的计算，假设图像的宽高为W，H，图像x，y方向上的视场角分别为θx，θy，可以得到相机的标定参数为：
(1)
这样就可以使用图像宽高与相机x，y方向上的视场角获取到相机的标定参数。
3.2.3. 相机输入
相机输入使用OpenCV的依赖库实现，通过继承OpenCV的JavaCameraView的类实现。在相机初始化的时候设置摄像机的聚焦模式为定焦，设置帧率固定到[5, 15]的范围。它们的关系如图1所示。
Figure 1. Inheritance structure of camera view
图1. 相机View的继承结构
其中在CameraBridgeBase是一个抽象类，其中只完成了照相机的绘制屏幕工作，通过抽象方法调用子类的相机输入绘制当前相机图像。JavaCameraView中继承CameraBridgeBase并且实现了自身的的相机输入，里面保持一个工作线程去一直不停读取相机输入保存到自身队列中，并且在绘制的时候调用接口的监听函数onCameraFrame将照片传送到注册的接口中。
在图2中，我们通过SlamConnector实现照片接受接口，在接受到照片时将图片传到原生层的算法部分，做为算法的输入，并且SlamConnector还负责算法的初始化和结束，还负责在项目当前的声明周期发生变化的时候，传送消息到Native层。其中OrbSlamActivity是当前算法的主要Activity，在其中处理算法的输入输出。
3.3. Android的输出部分
本项目的输出部分可以划分为两个模块，两个模块共同完成输出。第一个模块位于Java上，通过SlamGLSurfaceView对GLSurfaceView的继承，并且实现自己的GLRender，在GLRender里的绘图函数onDrawFrame中调用C++部分完成输入。第二个模块使用C++代码完成。由于Java部分只是用来进行消息传递和一个绘制入口的作用，所以主要的输出在原生代码中。
4. 实验评估
4.1. 半稠密的实现效果
在电脑上测试了两个数据集与ORB-SLAM的半稠密部分的论文中提到的效果进行对比。数据集都是从网址http://vision.in.tum.de/data/datasets/rgbd-dataset/download中获得。第一个数据集A是一个接近平面的数据集，fr3/nostructure texture near with loop.，是在一个桌子上贴了几张报表。照相机绕着桌子上的几张报表转了一圈，场景时长是56.49秒，帧率是30帧每秒。第二个数据集B是一个桌面立体场景，名称是fr2/desk，照相机绕着工作台转了一圈。场景时长为99.36秒，帧率是30帧每秒。
4.2. ORB-SLAM在Android上的优化效果
经过SLAM算法在Android上的参数调整和对一些模块进行并行计算的修改后，在Android上的实现效果有了很大的提升。
如表1所示，在经过参数调整后，优化后的时间与先前的时间进行比较，可以看出经过参数调整后在Android上的运行效率有了明显的提升，而且定位精度的误差在可接受的范围内。
由表2可以看出在经过多线程优化后，算法在提取特征点所花费的时间有了显著的加快，并且关于多线程的优化没有更改算法的定位与制图结果，只加快了算法的运行时间。
Table 1. Running time comparison of SLAM algorithm before and after parameter adjustment
表1. SLAM算法在参数调整前后运行时间对比
Table 2. Running time comparison of SLAM algorithm before and after multithreading optimization
表2. SLAM算法在多线程优化前后运行时间对比
4.3. 在Android上的输出效果
在Android上输出良好，图3与图4分别是在初始化未完成与完成后进行追踪时的运行的截图。上面的输出分别代表当前关键帧的数量，地图点的数量，与当前帧上匹配点的数量。
Figure 3. Running effect on Android (during initialization)
图3. Android上的运行效果(初始化时)
Figure 4. Output on Android (duringtracking)
图4. Android上的输出效果(追踪时)
图5是算法在Android手机上的运行时结果。由图5和图6来看算法在手机上运行能够达到所要的效果。但是在Android上运行时的速度很慢，每一帧在运行时会花费4秒左右的时间，还需要在手机上的进一步优化实现。
Figure 5. Output on Android (duringSemi-dense)
图5. Android上的输出效果(做半稠密时)
Figure 6. Semi-dense output on Android (when viewed on a computer)
图6. Android上半稠密的输出效果(在电脑上查看时)
5. 结束语
总体上来说，对于ORB-SLAM移植到Android上的优化是非常成功的，成功在智能手机上达到了实时运行需要的效率，在Android上的输入输出部分非常完善地实现了所需的效果但是基于ORB-SLAM半稠密的实现结果并不理想，在结果的精确与花费时间上均落后于ORB半稠密论文 [11] 中提到的效果。所以可以认为半稠密部分的算法还有很大的提升空间，还需要进一步的优化。
基金项目
黔科合重大专项字[2016]3012。
NOTES
*第一作者。
#通讯作者。