刘 洋， 张国山, 黄伟杰， 王欣博

(天津大学 电气与自动化工程学院，天津 300072)

随机蕨编码在三维重建中的应用

刘 洋， 张国山, 黄伟杰， 王欣博

(天津大学电气与自动化工程学院，天津300072)

针对KinectFusion算法中存在的重建范围小、缺少有效的重新定位策略及累计误差问题，提出了一种基于随机蕨编码的三维重建方法。应用随机蕨编码构建相机路径回环的检测策略减少长时间重建所产生的累积误差，通过检索相似关键帧进行相机位姿估计失败后的重新定位，通过与程序集成框架InfiniTAM相结合，增大重建范围。采用RGB-D SLAM验证数据集进行了对比实验。实验表明：提出的方法可以大大增加重建范围，在相机定位失败后有效地进行重新定位，同时减少了长时间重建产生的累积误差，使得三维重建的过程更加稳定，获得的相机位姿更加精确。

随机蕨编码； 三维重建； 相机路径回环； 关键帧

0 引 言

三维重建技术一直是计算机视觉领域的研究热点，在人机交互、机器人导航控制、增强现实等方面有着重要应用。自2010年11月微软公司发布Kinect以后，由于其操作简单、成本低廉、携带轻便，使得基于Kinect深度传感器的室内三维重建技术研究迅速发展起来。

2010 年，Henry P等人[1]利用 Kinect相机对室内场景进行三维重建。但此方法获得的三维模型较为粗糙，速度也只有2 fps左右。2011年，Newcombe R A等人提出了KinectFusion算法[2]，可以在可变光照条件下对室内环境进行密集表面重建,但该算法存在以下3个问题：1)重建范围受限制；2)建模过程中相机位姿估计会产生累积误差；3)相机位姿跟踪失败后不能有效地进行重新定位。

2013年，Matthias N等人[3]将哈希结构[4，,5]引入到了KinectFusion算法，利用高效的数据结构，内存与显存之间的数据流交换，使得三维重建的范围有了很大提升。2014年，Prisacariu V A等人实现了Matthias N等人[3]的思想，构造了一个KinectFusion算法的集成程序框架称为InfiniTAM[6]Prisacariu,将KinectFusion算法建模的各个步骤集成为模块，使得用户可以很容易地根据需要进行算法的改进或者更换，从而实现了基于哈希结构的快速、灵活的大范围三维重建。

2015年， Glocker B 等人[7,8]将随机蕨编码算法引入到三维重建系统中，利用随机蕨编码提取RGB-D图像的特征，通过对其快速匹配，实现了跟踪失败时相机位姿的重新获取。

与KinectFusion算法一样，许多基于稀疏特征点的三维建模算法[9,10]，均会产生累积误差，目前,主要通过检测相机路径回环(loop closure)[9，11]的方法解决。然而若将这些检测回环的算法用于基于密集点云的三维重建系统中，则需要匹配和计算的点的数量将会大大增加，计算成本和所需时间也会相应增加，这是实时三维重建系统所应该避免的。

文献[4]只解决了重建范围小的问题，文献[10,11]只解决了相机重新定位的问题，而文献[12,13]中检测相机路径回环的方法是基于稀疏特征点的检测方法，不适用于KinectFusion算法这样基于密集点云的三维重建系统。

针对KinectFusion算法中存在的重建范围小、缺少有效的重新定位策略及累计误差问题，本文利用随机蕨编码算法，实现了相机路径的回环检测，并将此算法与文献[9]中的InfiniTAM框架相结合，利用GPU的并行计算能力对随机蕨编码算法进行加速，使得InfiniTAM在进行大范围三维重建的过程中，可以在相机定位失败时快速重新定位，并且通过检测相机路径回环减少累积误差。

1 KinectFusion算法

KinectFusion算法的流程如图1所示，主要由以下4个部分组成：1)处理所采集的深度图，将其深度数据转换为三维点云，得到点云中顶点的三维坐标和法向量；2)估计相机位姿，将当前帧三维点云和由现有模型预测生成的三维点云进行ICP配准，得到当前帧相机的位姿；3)点云融合，根据计算出的当前的相机位姿，使用TSDF 模型进行点云融合，将当前帧的三维点云融合到现有模型中；4)场景渲染，使用光线跟踪的方法，根据现有模型和当前相机位姿预测出当前相机观察到的环境点云，一方面用于反馈给用户用于显示，另一方面提供给(2)进行ICP 配准。

图1 KinectFusion算法流程

KinectFusion算法的点云模型存储于显存，由于显存空间有限，使得模型大小受到了限制，进而导致该算法无法进行大范围的三维重建。KinectFusion算法的相机位姿估计采用的是ICP配准，ICP的初值选取的是上一帧的相机位姿，由于上一帧的位姿存在误差，在进行长时间重建时，误差累积会越来越大。当相机位姿估计失败时，算法将上一帧的相机位姿作为当前时刻的相机位姿，这种重新定位的策略不能有效地恢复相机的位姿。针对以上问题，本文提出了基于随机蕨编码的回环检测及重新定位算法。

2 基于随机蕨编码的回环检测及重新定位

利用随机蕨编码检测相机路径回环及位姿估计失败后重新定位的流程如图2所示，主要由以下5步组成：1)利用随机蕨对RGB-D图像进行编码，作为其特征信息；2)定义了BlockHD(block-wise hamming distance)作为相似性度量，计算当前帧与关键帧的相似性；3)获得关键帧，根据计算得到的BlockHD值，断定是否将此帧添加到关键帧中；4)找到与当前帧相似的关键帧，若当前帧与此关键帧的BlockHD小于预先设定的阈值，即可认为检测到了路径回环。5)当相机位姿估计失败后，通过检索相似关键帧所对应的相机位姿对相机进行重新定位。

图2 基于随机蕨编码的回环检测及重新定位流程

2.1 利用随机蕨对RGB-D图像编码

对于RGB-D图像I中的一个像素点x,R,G,B,D4个通道的值分别用IR(x),IG(x),IB(x),ID(x)表示，将F={fi}，i∈{R,G,B,D}定义为一个随机蕨

(1)

式中τi的值通过随机函数产生(τR,τG,τB∈[0,255],τD∈[800,4 000])。将随机蕨F中所有的fi按顺序排列，得到一个二进制编码块bF

bF=fRfGfBfD∈B4

(2)

若选取n个像素点，那么一帧RGB-D图像I即可由像素点对应的随机蕨编码

(3)

式中n个像素点的位置由随机函数产生。

2.2 RGB-D图像的相似性度量

为了度量两帧图像I和J的相似性，采用了block-wise hamming distance(BlockHD)进行度量，定义为

(4)

2.3 获取关键帧

对于每一新进帧I来说，计算其与之前所有关键帧的BlockHD，并找到BlockHD的最小值

(5)

式中ζl的值越小说明存在一个与当前帧十分相似的关键帧J，将ζI的值与预先设定的阈值t进行比较，若ζI>t，则可以将此帧作为关键帧，并将其所对应的相机位姿及顶点法向量存储。

2.4 相机路径回环检测

在获取关键帧的过程中，根据式(5)可以得到当前帧与关键帧的BlockHD的最小值ζI。若ζI的值特别小，则说明当前帧与此关键帧差异性特别小，即相机回到了此关键帧所对应的位置，此关键帧的相机位姿和当前帧的相机位姿相近甚至相同，即检测到了相机路径的回环。考虑到噪声对精度的影响，设定一个较小的阈值σ，比较ζI与σ的大小。若ζI<σ，说明检测到了相机路径回环。

当获取了一系列的关键帧后，相机路径回环即可通过快速检索相似关键帧实现。当检测到相机路径回环后，将当前帧与对应关键帧的顶点法向量进行ICP配准，并将关键帧所对应的相机位姿作为ICP的初值，从而有效地减少累积误差。

2.5 相机位姿恢复

当相机位姿估计失败后，通过检索关键帧所对应的相机位姿对相机进行重新定位。

假设在某帧时相机位姿估计失败，首先计算此帧与所有关键帧的BlockHD值，找到k个与当前帧的BlockHD值最相近的关键帧，继而可以得到这k个关键帧所对应的相机位姿。将这k个位姿分别作为初值代入到当前帧与相应关键帧的ICP配准算法，从而实现相机的重新定位。若这k个位姿仍不能恢复相机位姿，则处理下一帧RGB-D图像，直至相机重新定位成功，在此过程中，系统将暂停对室内场景的重建。当相机位姿恢复后，系统才继续进行重建。

3 随机蕨编码与InfiniTAM框架结合

InfiniTAM是一个KinectFusion算法的集成框架，它使用基于哈希结构的体素块表示三维模型，并且在CPU和GPU之间实时地互换数据，使得三维重建范围不受空间限制。本文将随机蕨编码算法集成为一个模块，增加到InfiniTAM框架中，其算法流程如图3所示。

图3 本文算法流程

当一帧RGB-D图像进入系统后：1)一方面将其深度数据转换成三维点云，得到点云中顶点和法向量，另一方面利用随机蕨编码算法对RGB-D图像进行编码，并计算当前帧与关键帧的BlockHD值；通过比较BlockHD值与阈值σ的大小，判断相机路径中是否触发了回环，若触发了回环，则将关键帧所对应的位姿作为ICP算法的初值，将当前帧与对应关键帧的顶点法向量进行ICP配准。2)将当前帧三维点云和由现有模型预测生成的三维点云进行ICP配准，并判断ICP是否成功。若ICP配准成功，通过比较BlockHD值与阈值t的大小，判断此帧是否添加到关键帧中；并进行下一步点云的融合；若配准失败，则利用找到的相似关键帧与当前帧进行ICP配准，并将此关键帧对应的位姿作为初值代入ICP算法，若此时的配准成功则进行下一步点云融合，若再次失败，等待下一帧RGB-D图像。

在InfiniTAM框架中，为保证建模的实时性,ICP配准算法在GPU中计算。由于GPU显存的限制，随机蕨编码算法中关键帧对应的顶点和法向量存储在了内存中。一旦检测到了相机路径回环或者需要相机位姿恢复，系统将使对应的顶点和法向量复制到显存中，利用GPU的并行运算加快当前帧与关键帧的ICP配准，得到相机位姿后再将相机位姿从显存复制到内存中，与关键帧的顶点和法向量对应存储。

4 实 验

通过在慕尼黑工业大学的RGB-D SLAM验证数据集上进行建模测试，将InfiniTAM[9]与本文提出的算法进行对比。

RGB-D SLAM验证数集提供了很多场景。每个场景的数据包中包含了彩色图像、深度图像、精确的相机位姿等信息。选取了第一个场景中的数据包“freiburg1_room”和“freiburg1_360”进行实验。

首先在“freiburg1_room”数据包上进行实验。“freiburg1_room”数据包的轨迹范围是2.5 m×2.2 m×0.5 m，重建范围远大于7 m3。为了方便观察，验证数据集提供的Python工具将轨迹投影到x-y平面后进行对比，如图4(a),图4(b)所示，其中线①为ground truth，线②为程序得到的相机轨迹的估计(estimate)。从图中可以看出，算法在(1.0，-1.0)和(0.5，-1.0)附近检测到闭环后，相机的轨迹明显向ground truth收敛，与ground truth更加吻合。同时，验证数据集提供的工具给出了各类误差的对比数据，误差统计值如表1所示，误差的计算方法可参照文献[17]。从表1可以看出：算法较InfiniTAM，轨迹误差均有所降低，通过检测相机路径回环，可以有效减少累积误差。

图4 轨迹对比

m

为验证本文算法相机重新定位的有效性，在“freiburg1_360”数据包上进行实验。在“freiburg1_360”数据包中相机的运动速度很快，InfiniTAM在此数据包上实验时重建失败。由于InfiniTAM没有有效的重定位策略，因而重建失败后相机位姿无法恢复，而本文算法除了可以检测相机路径回环外，还可以实现相机相机位姿估计失败后的重新定位。实验效果如图5所示。图5(a)，图5(b)为在相同时刻采集，包含了该时刻的重建模型、深度图和彩色图。可以看出：相对于InfiniTAM，本文算法可以在相机位姿估计失败时重新定位。

图5 重建效果对比

5 结 论

针对KinectFusion算法中存在的重建范围小、缺少有效的重新定位策略及累积误差问题，通过引入随机蕨编码算法，在InfiniTAM系统中实现了相机路径的回环检测，使得改进后的系统在进行大范围三维重建的过程中，可以在相机定位失败时快速重新定位，并且通过检测相机路径回环减少累积误差。实验表明：提出算法可以使得三维重建过程更加稳定，获得的相机位姿更加精确。

[1] Henry P,Krainin M,Herbst E,et al.RGB-D mapping:Using depth cameras for dense 3D modeling of indoor environment-s[C]∥Proceedings of the International Symposium on Experimental Robotics(ISER),2010.

[2] Newcombe R A,Davison A J,Izadi S et al.Kinect Fusion:Real-time dense surface mapping and tracking[C]∥2011 10th IEEE International Symposium on Mixed and Augmented Reality(ISMAR),IEEE,2011:127-136.

[3] Matthias N,Michael Z,Shahram I,et al.Real-time 3D reconstruction at scaleusing voxel hashing[J].ACM Transactions on Graphics,2013,32(6):1-11.

[4] García I,Lefebvre S,Hornus S,et al.Coherent parallel hashing[J].ACM Transactions on Graphics,2011,30(6):1-8.

[5] Pan J,Manocha D.Fast GPU-based locality sensitive hashing for k-nearest neighbor computation[C]∥Proceedings of International Conference on Data Engineering,2012:378-389.

[6] Prisacariu V A,Kahler O,Cheng M M et al.A farmework for the volumetri integration of depth images[EB/OL].2014—09—25.https:∥arxiv.org/abs/1410.0925.

[7] Glocker B,Izadi S,Shotton J,et al.Real-time RGB-D camera relocalization[C]∥2013 IEEE International Symposium on Mixed and Augmented Reality(ISMAR),IEEE,2013:173-179.

[8] Glocker B,Shotton J,Criminisi A,et al.Real-time RGB-D camera relocalization via randomized ferns for keyframe encoding[J].IEEE Transactions on Visualization & Computer Graphics,2015,21(5):571-583.

[9] Davison A J.Real-time simultaneous localisation and mapping with a single camera[C]∥IEEE International Conference on Computer Vision,IEEE Computer Society,2003:1403.

[10] Klein G,Murray D.Parallel tracking and mapping for small AR workspaces[C]∥IEEE and ACM International Symposium on Mixed and Augmented Reality,2007:225-234.

[11] Strasdat H,Davison A J,Montiel J M M,et al.Double window optimisation for constant time visual SLAM[C]∥IEEE International Conference on Computer Vision,IEEE Computer Society,2011:2352-2359.

[12] Parker S,Shirley P,Livnat Y,et al.Interactive ray tracing for isosurface rendering[C]∥Proceedings of the Conference on Visua-lization,IEEE Computer Society,1998:233-238.

[13] Sturm J,Engelhard N,Endres F,et al.A benchmark for the evaluation of RGB-D SLAM systems[C]∥IEEE/RSJ International Conference on Intelligent Robots & Systems,2012:573-580.

Applicationofrandomfernencodingin3Dreconstruction

LIU Yang, ZHANG Guo-shan，HUANG Wei-jie, WANG Xin-bo

(SchoolofElectricalEngineering&Automation，TianjinUniversity,Tianjin300072,China)

Aiming at problem of small reconstruction range,lack of effective relocalization strategy and cumulative error in KinectFusion algorithm,propose a 3D reconstruction method based on random fern coding.The camera trajectory loop closures is detected by using the random fern encoding to reduce the accumulated error caused by long time reconstruction.By retrieval similarity key frames,relocate camera pose estimation after failure.By combining with InfiniTAM,range of reconstruction are increased.A comparison experiment is carried out using the RGB-D SLAM dataset.Experimental results show that the proposed method can greatly increase reconstruction range,effectively relocate the camera pose after failure,and reduce accumulated error,which makes the 3D reconstruction process more stable and obtains camera pose more accurately.

random fern encoding; 3D reconstruction; camera trajectory loop closures; key frames

10.13873/J.1000—9787(2017)12—0157—04

TP 391

A

1000—9787(2017)12—0157—04

2016—10—19

刘 洋(1991-)，女，硕士研究生，从事基于kinect相机的三维重建研究。张国山(1961-)，男，教授，博士生导师，从事非线性系统控制理论与智能控制的研究工作。