多Kinect实时室内动态场景三维重建

邓念晨， 杨旭波

(上海交通大学 软件学院，上海 200240)

多Kinect实时室内动态场景三维重建

邓念晨， 杨旭波

(上海交通大学 软件学院，上海 200240)

采用多个Kinect从不同角度同时捕获场景，将它们的深度图和彩色图结合在一起，通过数据预处理、顶点构建、点云注册和表面重建等步骤得到场景三维模型．整个流程均在GPU上实现以加速运算，实现了基于GPU的迭代最近点算法、基于GPU的八叉树构建、基于有向距离函数的表面重建等关键算法．试验中，整个算法运行帧率达到8.74 f/s；重建分辨率达到约5.9 mm．试验表明，算法基本满足实时动态场景重建的要求，重建模型的精度满足非精确计算类应用的需求．

三维重建；室内动态场景；多Kinect设备；迭代最近点配准；Marching Cubes算法

场景三维重建技术是利用传感器和计算机，通过对场景的纹理、深度等元数据进行分析和处理后自动(或半自动)地构建场景的三维模型．目前，场景重建技术在工业模拟、智能机器人等诸多方面都发挥着十分重要的作用．然而，较长的计算时间和昂贵的设备极大地阻碍了这一技术在协作办公和日常生活领域的推广应用．因此，基于廉价设备的实时场景三维重建技术具有巨大的研究意义和应用价值．本文以远程协作应用为背景，采用Kinect设备捕获场景数据，研究如何实时重建满足一般用户视觉精度要求的场景模型．

人们对三维重建技术的研究已达数十年，也提出了许多方法．根据原始场景数据的类型，三维重建技术主要分为基于深度数据的三维重建[1-5]和基于纹理数据的三维重建[6-7]，其中大多数方法是基于深度数据的．基于纹理数据的方法具有硬件成本低廉的优势，但物体表面的纹理本身受环境光影响较大，而且重建过程包含大量经验和假设，一般情况下的重建精度往往不能满足要求．而基于深度数据的三维重建方法更为简单、稳定，易于推广应用．根据重建模型的抽象等级，三维重建技术可以分为3个层次[4]：高层次关注的是一种或者一类物体，主要用于物体识别[8]；中层次使用基本几何图元构建模型，主要用于物体分割[1]；低层次则完全构建模型网格表面，不受任何假设的限制，用于对物体或场景精确建模以便重现[2, 4-5]．本文重点研究基于深度数据的网格模型精确建模方法．

近几年，由于通用图形处理器(GPGPU)的推广应用以及类似Kinect这样具有实时深度获取能力的设备的出现，实时三维重建技术开始成为研究热点．文献[9]利用Kinect从多个角度拍摄物体，然后离线重建完整的物体模型．而文献[10]则在Kinect输入数据上提出了更好的预处理方法．文献[5, 11]利用Kinect设备和GPU运算达到了实时重建的效率．文献[12]继续进行了改进，使得重建算法能较为快速地响应场景中发生的变化.而文献[13]则结合图像追踪技术来重建和追踪非刚体物体的变化．值得一提的是，上述方法都仅使用了单台Kinect设备，由于受限于单一设备的视野局限，需要手持设备移动扫描才能获取物体的多个视角，以便重建出较为完整的模型．本文采用多台Kinect设备从不同视角捕获场景并进行融合，用户不需要手持设备．这种配置更适合于远程协作的应用环境，使用户可以解放双手进行更好的交流和协作．

1　总体系统设计

1.1硬件系统设计

在远程协作的工作平台中，用户不便手持Kinect设备进行工作，因此，本文系统使用2～4个固定摆放在场景周围不同方位的Kinect设备拍摄场景(如图1所示)，采用普通的个人计算机进行计算，得到场景的三维网格模型，且固定Kinect设备能简化重建动态场景的算法，也使重建结果更加稳定．

图1　硬件系统布局示意图Fig.1　Hardware system layout

本系统在部署完成后需要进行一次标定操作，包括对所有Kinect设备分别进行内参标定，对所有Kinect设备统一进行外参标定．内参和外参标定均采用棋盘格标定法．

1.2算法流程概览

实时动态场景重建算法的主要流程为获取数据(深度数据和纹理色彩数据等)、对数据进行预处理、根据深度数据构建三维点云、对多组点云进行注册、从点云构建网格表面，具体如下所述.

(1) 对数据进行预处理.从传感器获取的数据存在一定的噪声和误差分布特性，因此，需要对原始的深度数据进行特殊的预处理以降低噪声的干扰，从原始数据的层面减少误差.

(2) 根据深度数据构建三维点云.对于每个传感器获得的深度数据和彩色图像数据，根据传感器的内参和外参信息计算点云中各点的三维坐标、颜色和法向量．这时将它们可视化已经可以看出一定的重建效果，但是由于基于棋盘格的外参标定并不十分精确，从结构和纹理上可以看出多组点云并不能完全匹配.

(3) 对多组点云进行配准.旨在减小多组点云之间存在的变换偏差．许多有关三维重建的研究(例如文献[5, 11])都使用迭代最近点配准算法(ICP)[14]，本文亦在该算法基础上提出了改进方案.

(4) 从点云构建网格表面.从三维点云中构建较为完整的表面网格模型，具体涉及基于GPU的八叉树构建、有向距离函数计算和三角面片生成等算法．

2　彩色图和深度图的预处理

由于硬件层面的原因，Kinect设备获得的彩色图呈现出明显的条纹状噪声，深度图中也存在较为明显的随机噪声，影响重建效果．因此，在使用这些数据生成三维点云前，首先需要进行二维图像层面的降噪处理．针对色彩图的条纹噪声特征，本文采用反交错技术处理色彩图，基本消除了这一噪声，去噪效果如图2所示．

(a)预处理前

(b) 预处理后图2　彩色图预处理前后的效果对比Fig.2　Color images before and after preprocess

针对深度图中的随机噪声，如采用传统高斯滤波方法在降噪的同时会导致边缘模糊，因此，本文采用带边界检测的高斯滤波方法．该方法能够在消除内部高频噪声的同时，保持边界的清晰．经过这一处理的深度图所构建的三维模型不会在边缘部分产生毛刺，克服了传统高斯滤波方法的不足(如图3所示)．

(a) 传统高斯滤波

(b) 带边界检测的高斯滤波图3　使用经过传统高斯滤波和带边界检测的高斯滤波处理的单深度图的重建结果对比Fig.3　The reconstruct result from single depth images processed by Gauss filter without and with edge detection

3　基于改进的ICP算法配准三维点云

在外参标定过程中的微小误差会被构建三维点云时的逆投影变换放大,因此,本文利用ICP算法实时地改进外参标定的精度．为了增强算法的鲁棒性，本文采用位置-色彩混合空间下的距离定义[11]．

另外，考虑到GPU的并行计算特性以及由深度图生成的点云具有高度的结构化，本文提出了基于投影关系的快速最近邻搜索算法来加速最近邻搜索．该算法的主要依据是在深度图中排列的像素通过逆投影生成的三维顶点也具有一定的排列关系，即两个距离相近的顶点，其在深度图上的投影之间的距离也很接近(只要这两个点深度值不是很小)．因此，若假设某个顶点v1的最近邻顶点是v2，v2的投影p2有很大的概率落在v1的投影p1的小邻域内，则在计算v1的最近邻时搜索范围可以被缩减到p1的小邻域内．

4　从三维点云提取表面

场景重建的最后一个步骤是将点云变成表面模型．离线重建一般采用泊松表面重建方法[15]，但是该方法计算复杂度较高．本文所实现的表面提取算法采用八叉树结构组织点云和划分空间，使用有向距离函数模型计算零值面，最后利用基于八叉树的Marching Cubes算法构建三角面片．

4.1基于GPU的八叉树构建算法

本文参照文献[16]中所述设计并实现了基于GPU的八叉树构建算法．为了使八叉树构建和查找能在GPU上高效执行，本文采用了广度优先的构建算法，并使用预先计算好的邻居查找表查找节点的邻居，将带有数据依赖而无法并行执行的操作降到最少．

4.2基于有向距离函数的等值面计算

4.3Marching Cubes表面提取算法

Marching Cubes算法[18]是基于网格划分的表面提取算法，其基本思想是在每个网格中的小立方体单元中用平面结构近似表面．根据立方体上的8个顶点在模型的内部或外部的情况可以将立方体分为256类，又由于内外对称、立方体旋转对称，这256个种类可以规约到15个基本种类[18](如图4所示)．Marching Cubes算法的基本流程对于网格中的每个单元，以6个顶点的正负值(表示在三维模型的外部或内部)组成索引查表获得该单元需要形成的一系列三角形顶点索引．

图4　15类立方体可以形成的三角面片[18]Fig.4　Fifteen kinds of triangle generation in a cube [18]

基于八叉树的Marching Cubes算法和传统的Marching Cubes算法相似，由于八叉树的叶子节点仅存在于有原始点云中的点的区域，因此，会有部分三角面片因节点的缺失而无法构建，导致最终生成的表面中包含许多小洞(如图5所示)．

图5　基于八叉树的Marching Cubes算法重建的表面Fig.5　Surface reconstructed from octree-based Marching Cubes algorithm

为了解决这一问题，本文提出了构造伪节点的方法，其基本思路是对于所有在面f上与表面存在交线的节点n，构造一个伪节点nf，与n在f上邻接，并将在结构关系上属于nf的顶点和边赋给nf．然后再对所有伪节点执行Marching Cubes算法生成三角面片，便可补上这些空洞(如图6所示，图中顶点上的黑色标记表示该顶点为正值，反之为负值，下同)．

图6　伪节点与在伪节点上构造的面片(图中画阴影的三角形)Fig.6　Fake node and the patch on it (the triangle marked with shadow)

由伪节点的构造而引出的一个问题，即伪节点中不包含任何原始点云中的点，因此由伪节点而新增的顶点(可以称其为伪顶点)并不存在一个有向距离值(可以假定其为无穷大)．一个无穷大的值并不属于正值或负值，这导致无法明确识别该立方体的类型．因此，本算法采用就近原则，将一个无穷大值的符号定义为该顶点的3个邻接顶点中非无穷大值的符号(如图7(a))．若3个邻接顶点中存在不同的符号(如图7(b))或3个邻接顶点均为伪顶点(如图7 (c))，则抛弃该伪节点，不生成任何三角面片．

(a) 3个相邻顶点符号相同

(b) 3个相邻顶点符号不同

(c) 3个相邻顶点均为伪顶点图7　就近原则处理无穷大值的符号Fig.7　The sign of infinite decided by principle of proximity

而在生成三角面片方面，由于为伪顶点赋予了符号，Marching Cubes算法生成的三角面片中可能会存在顶点在伪边上的情况．对于这种情况，仅需要将该三角面片删除即可．使用构造伪节点的方法后则重建结果中含有的空洞明显减少了(如图8所示)．

图8　用构造伪节点方法改进后的重建结果Fig.8　The improved result by using fake nodes

5　试验结果和性能

通过一系列试验验证本文所设计的场景重建算法的执行结果，测试和优化算法执行性能．所有试验均在同一台普通的家用型笔记本电脑上进行，其主要硬件参数为：Intel®CoreTMi7-2670QM处理器，8.00 GB内存以及AMD®RadeonTMHD 6770M图形显示卡．所有试验均采用两台Kinect设备捕获场景，两台Kinect设备中心轴之间的夹角约为45°，使用的深度图和彩色图分辨率均为320×240．

试验场景为桌面物体及人物雕像，Kinect设备与场景主要物件的距离范围为60～100 cm．试验包括不同八叉树层级的重建结果比较、时间和空间测试的性能分析．

5.1不同八叉树层级的重建结果比较

该试验目的是对比在不同的八叉树层级上执行表面提取的效果．用8～11层八叉树(分别对应叶节点边长为23.4, 11.7, 5.9 和2.9 mm)重建的结果如图9所示．从图9中可以看出，使用8和9层八叉树重建的结果十分粗略，尤其是使用8层时，雕像的五官几乎不可分辨．而使用11层八叉树重建结果虽然保留了非常细致的细节，但由于原采样点的密度不足，该重建结果也存在大量的空洞．使用10层八叉树重建的结果虽然细节较11层有所缺失，但在大部分区域都没有空洞，是最为适合当前所使用的采样分辨率的．因此，以下试验均采用10层八叉树重建．

(a) 8层八叉树

(b) 9层八叉树

(c) 10层八叉树

(d) 11层八叉树图9　使用不同层数的八叉树重建场景的结果Fig.9　The reconstruct results using different levels of octree

5.2时间性能分析和优化

优化前后主要步骤所用时间如表1所示．鉴于优化前算法在清空八叉树和提取表面花费的时间最多，优化主要针对这两个步骤进行．

表1　优化前后主要步骤所用时间Table 1　Time spent in key steps before and after optimization

清空八叉树的时间耗费过长主要是由于内存到显存的带宽相对较窄，采用从内存中将初始数据重新导入GPU缓存中的开销巨大．因此，针对这一步骤的优化采取了通过执行shader为缓存写入初始数据的方法．

对于提取表面步骤，首先进一步分析了表面提取算法中的各个步骤的时间开销．优化前后表面提取算法的各步骤时间开销对比如图10所示．由图10可知，计算每个八叉树顶点的有向距离花费了绝大多数的时间，而优化该步骤的代码后表面提取算法的时间开销明显缩短．

(a) 优化前

(b) 优化后图10　优化前后表面提取算法的各步骤时间开销对比Fig.10　Time spent in each step of surface extraction before and after optimization

由表1可知，优化后重建算法执行时间是原来的33%，加速比达到3.02．优化后的运行帧率可达到8.74 f/s．

5.3GPU内存空间性能分析与优化

场景重建算法所占用的GPU内存空间如表2所示，所列数据为分析具体实现后计算而得．

表2　优化前后主要数据结构空间的使用效率Table 2　The space usage of main data structures before and after optimization

由表2可知，优化前执行场景重建算法需要329.88 MB的显存空间，有效率仅有16.53%．主要原因是动态分配GPU缓存资源的开销极大，一般都是在初始化时就创建了足够大的空间．例如基于极端情况下每个八叉树的叶子节点可能只包含一个点云中的点，因此，优化前为八叉树叶子节点分配的空间与分辨率和Kinect的个数的乘积一致．但是事实上由于点集分布的集中性，上述极端情况是不可能出现的．另外由于分辨率的增加只会导致点云的密度增加，并不会增加许多覆盖区域，因此，实际上分辨率的增加并不会导致叶子节点的大幅增加．经过对试验数据的分析后，本文进行了3步优化：

(1) 对点云数据进行压紧处理，使得有效数据都集中在数组前端；

(2) 将为节点分配的空间大小与分辨率的关系从线性关系修正为与输入分辨率的二次根呈线性关系，可以有效减少使用高分辨率输入数据时的空间浪费；

(3) 将节点边和节点顶点改为紧凑排列，并减少分配给节点边和节点顶点的空间．

经过3步优化，算法所耗费的GPU内存空间仅为优化前的1/3，有效率提升至57.83%．

5.4办公场景的重建

场景包含人物和放置着一些办公物品的桌面．使用两台Kinect设备拍摄场景，其中心轴之间的夹角约为30°，与场景中主要物体的距离范围为80～150 cm．重建结果如图11．

图11　办公场景的重建结果Fig.11　Reconstruction of work scene

6　结　语

本文设计并实现了基于多个Kinect设备的实时动态场景重建技术，性能基本满足实时要求．主要研究成果包括：提出了基于投影关系的快速最近邻搜索算法；用构造伪节点法改进了基于八叉树的Marching Cubes算法的重建结果；实现了完整的场景重建算法，并利用GPU并行技术达到了三维重建实时性．

未来工作将主要集中于以下几点：深入研究更多应用在表面重建中的数学模型，以期提出一个更好的数学模型减少空洞和噪声敏感度，并提升重建模型的细节；引入纹理色彩分析算法，考虑研究色调补偿和表面材质提取等方面的内容，并改进模型纹理的生成方法，提高模型纹理的真实感；进一步优化性能．

[1] DENG S W, YUAN B Z. A method for 3D surface reconstruction from range images[C]// 1994 International Symposium on Speech, Image Processing and Neural Networks. 1994:429-432.

[2] CURLESS B, LEVOY M. A volumetric method for building complex models from range images[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, ACM. 1996: 303-312.

[3] SCHUTZ C, JOST T, HUGLI H. Free-form 3D object reconstruction from range images[C]// 1997 International Conference on Virtual Systems and MultiMedia. 1997: 69-70.

[4] WHITAKER R T. A level-set approach to 3D reconstruction from range data[J]. Int J Comput Vision, 1998, 29(3): 203-231.

[5] IZADI S, NEWCOMBE R, KIM D, et al. Kinect Fusion: Real-time dynamic 3D surface reconstruction and interaction[C]//ACM SIGGRAPH 2011 Talks (SIGGRAPH′11). Vancouver, British Columbia, Canada: ACM, 2011.

[6] 杨敏,沈春林.基于场景几何约束未标定两视图的三维模型重建[J]. 中国图象图形学报:A版, 2003, 8(8): 872-876.

[7] REMONDINO F, EL-HAKIM S F, GRUEN A, et al. Turning images into 3-D models[J]. Signal Processing Magazine, IEEE, 2008, 25(4): 55-65.

[8] BESL P J, JAIN R C. Three-dimensional object recognition[J]. ACM Computing Surveys (CSUR), 1985, 17(1): 75-145.

[9] 刘田间,郭连朋,陈向宁,等.基于 Kinect 传感器多深度图像融合的物体三维重建[J]. 应用光学, 2014, 35(5):811-816.

[10] 应忍冬,陈晓明,蒋乐天.基于 Kinect 深度信息的实时三维重建和滤波算法研究[J]. 计算机应用研究, 2013, 30(4):1216-1218.

[11] NEUMANN D, LUGAUER F, BAUER S, et al. Real-time RGB-D mapping and 3-D modeling on the GPU using the random ball cover data structure[C]// 2011 IEEE International Conference on Computer Vision Workshops, 2011: 1161-1167.

[12] KELLER M, LEFLOCH D, LAMBERS M, et al. Real-time 3D reconstruction in dynamic scenes using point-based fusion[C]//2013 International Conference on 3D Vision. IEEE, 2013: 1-8.

[13] ZOLLHÖFER M, NIEßNER M,IZADI S,et al. Real-time non-rigid reconstruction using an RGB-D camera[J]. ACM Transactions on Graphics (TOG), 2014, 33(4):

[14] BESL P J, MCKAY N D. A method for registration of 3-D shapes[J]. IEEE Trans Pattern Anal Mach Intell, 1992, 14(2): 239-256.

[15] KAZHDAN M, BOLITHO M, HOPPE H. Poisson surface reconstruction[C]//Proceedings of the Fourth Eurographics Symposium on Geometry Processing. Cagliari, Sardinia, Italy: Eurographics Association, 2006: 61-70.

[16] ZHOU K, GONG M, HUANG X, et al. Highly parallel surface reconstruction[J]. Microsoft Research Asia, 2008.

[17] HOPPE H, DEROSE T, DUCHAMP T, et al. Surface reconstruction from unorganized points[C]//Computer Graphics (SIGGRAPH ’92 Proceedings).1992: 71-78.

[18] LORENSEN W E, CLINE H E. Marching cubes: A high resolution 3D surface construction algorithm[C]//Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87).1987: 163-169.

Real-Time Dynamic Indoor Scene 3D Reconstruction Using Multiple Kinect

DENGNian-chen,YANGXu-bo

(School of Software, Shanghai Jiaotong University, Shanghai 200240, China)

Multiple Kinect devices are used to capture a scene from different views at the same time. Depth and RGB images of the scene are combined to model the scene. The reconstruction process mainly includes data preprocessing, vertex construction, point clouds registration and surface reconstruction. All processes are GPU implemented to speed up the calculating. Key algorithms implemented in this subject include iterative closest point based on GPU, octree construction based on GPU, surface reconstruction based on the signed distance function. Experimental results show that the algorithm efficiency reaches 8.74 f/s and the resolution of models reconstructed are about 5.9 mm. The experimental results prove that, the reconstruction process implemented meets the requirements of the real-time dynamic scene reconstruction and the precision of reconstructed models meets the need of non-exact calculation application.

3D reconstruction; indoor dynamic scene; multiple Kinect devices; iterative closest point registration; Marching Cubes algorithm

1671-0444(2015)04-0448-07

2014-11-14

国家自然科学基金资助项目(61173105， 61373085)

邓念晨(1990—)，男，山东潍坊人，硕士研究生，研究方向为计算机图形学.E-mail:dengnianchen@sjtu.edu.cn

杨旭波(联系人)，男，教授，E-mail:yangxubo@sjtu.edu.cn

TP 391

A