王 超，王长波

(华东师范大学 计算机科学与软件工程学院，上海 200062)

一种面向3D打印的点云快速重建算法

王 超，王长波

(华东师范大学 计算机科学与软件工程学院，上海 200062)

采用KinectFusion点云融合技术，探索三维重建技术与3D打印技术的结合性，设计并实现了一种面向3D打印的点云快速重建算法.首先使用手持型Kinect获取物体表面点云数据，使用八叉树存储数据，利用ICP(iterative closest point)算法进行点云配准与融合；然后采用基于统计异常值检测方法、随机抽样一致性算法(RANSAC)、移动最小二乘法等算法对点云数据进行后处理；再将处理后的点云数据进行三维表面重构并根据重心加入底座、支柱等缺失部位，以保持模型的平稳性；最后使用自制的三角洲打印机打印成型.试验结果表明，该算法实现了从实物到三维虚拟模型再到实物打印成型的整个过程，具有设备成本低、实现简单并且高效快速等特点.

点云数据；三维重建；点云配准；3D打印

近几年随着3D打印技术[1-2]的发展，快速成型技术也取得了巨大的突破，其在工业制造、航空航天、生物医疗等领域占据重要地位.传统用于3D打印的虚拟模型，需要图形设计人员在相关软件内进行设计与编辑，此类三维模型结构复杂，编辑耗时，增加了模型设计的难度，同时也降低了模型设计到打印实物整个过程的效率，亟需寻找一种高效快速的模型生成方法.

另外，三维重建技术在游戏、影视动画制作、虚拟现实和文物保护等领域得到了广泛应用.Kinect传感器[3]的出现，使得深度摄像机姿态的跟踪与重建[4]变得简单方便.Kinect传感器不受可见光影响，同时具有成像速度快、价格相对低廉、操作方式简单等优点，基于Kinect的三维重建方法也成为了一个研究热点.在基于Kinect重建算法中，最具有代表性的为KinectFusion算法[5-6]，此方法抓取场景中的静态物体表面点云并融合，实时地重建出物体的三维模型.文献[7]拓展了原始的KinectFusion工作，克服了此算法重建空间有限制的缺点，使得KinectFusion算法适用于较大的场景.文献[8]提出了基于八叉树(octree)的表面形式，提高了基于Kinect的动态场景重建的速率.然而，使用Kinect重建的三维模型具有不完整、不平滑、不封闭等缺点，不能直接用于3D打印.因此，将三维重建技术与3D打印技术相结合仍然是一个开放性的课题[9].

针对上述问题，本文基于KinectFusion算法提出了一种面向3D打印的点云重建方法，探索三维重建技术与3D打印技术结合的可行性.首先使用Kinect摄像机对场景中的静态物体进行快速重建，主要包括点云抓取与快速融合、点云去噪、点云融合、表面抽取等操作；再将重建的模型进行后处理，包括底面添加、模型闭合、打印支柱添加等操作；最后使用3D打印机将模型打印出来.本文算法具有以下特点：(1) 将点云重建技术与3D打印技术相结合，在KinectFusion算法框架的基础上，加入八叉树、点云后处理、抽取表面等处理，能够使用点云快速重建目标物体模型.(2) 在制作打印机的同时，探索速度更快、价格更低廉、运行更稳定的3D打印技术.将点云重建的模型进行处理，使模型满足封闭、表面光滑、整体平稳等特性，并加入底座、支柱等缺失部件，获得适合3D打印的模型后进行3D打印成型. (3) 算法自适应性强，不严格设定试验场景，具有较高的健壮性，同时试验设备成本低、部署简单.

1 算法概述

本文算法使用Kinect对场景物体进行扫描，将获取的点云作为输入，经过点云融合、去噪、重建，模型处理等步骤，最后将模型进行快速打印作为整个算法的输出，算法框架如图1所示.该算法主要分为两个部分：Kinect点云重建与3D打印处理.Kinect点云重建主要包括点云抓取、点云融合、点云后处理和表面抽取等步骤；3D打印处理主要包括重建模型处理和快速打印成型两个步骤.

图1 算法框架Fig.1 Algorithm framework

2 Kinect点云重建

首先通过Kinect设备获取点云数据，在扫描的过程中跟踪摄像机的空间姿态参数(包括位置和朝向)，将多个角度抓取的点云数据不断融合生成一个完整的点云数据，并进行后处理，最后进行表面抽取以获得3D模型.

2.1 点云抓取

Kinect采集点云数据不受光线影响，精度较高，分辨率为640像素×480像素，帧率为30帧/s.将试验场景选择为空旷的大厅，这样可以减少背景物体的影响，从而增加点云配准的精度.试验过程中，转椅上的物体正对Kinect旋转，实时得到点云数据并显示出来.在点云抓取过程中，计算物体相对于Kinect摄像头的旋转角度，并将新一帧抓取的点云数据融合到全局点云模型中.此处抓取点云使用KinectFusion框架，在保存点云数据的同时获取对应的RGB图像信息.

2.2 点云融合

在点云抓取与融合过程中，需要不断计算摄像头的空间姿态信息，这里的空间姿态信息Tg(如式(1)所示)具有6个自由度.

(1)

式中：t为平移向量，其自由度为3; 0T=[0 0 0]；R为旋转矩阵，其自由度为3.由于Kinect具有较高的帧率，所以可以假设相邻两帧之间摄像机的空间位置移动非常小，基于此假设可以使用快速投影数据关联算法[10]， 来获得相邻帧点云之间的对应关系以及点到面的几何关系[11].计算摄像机空间姿态信息时，采用ICP(iterative closest point)算法[12]计算两个点云之间的匹配程度，若点云匹配成功，可以得到两个点云之间的平移和旋转信息.点云配准时需要计算匹配点的误差值.传统方法一般采用点到点的方式计算两个点的空间欧氏距离，方法简单，但是对于大体积点云不能达到实时性的要求.此时采用点到面的方法，即不是计算对应点对之间的距离，而是计算源点到对应点处切面的距离，如图2所示.源点si=(six,siy,siz, 1)和目标点di=(dix,diy,diz, 1)为一对匹配点，di处的法向ni=(nix,niy,niz, 0)，那么每次ICP迭代的目标最优解Mopt为

(2)

式中：M和Mopt为4×4的刚体变换矩阵.虽然采用点到面的计算方式在每一步迭代中比点到点的计算方式慢，但前者收敛速度快，能够达到实时性要求. 在ICP运行过程中需要不断查找空间的匹配点，系统采用八叉树来存储数据，以加快空间中邻居查找的速度.

图2 两平面间的点到面误差计算Fig.2 Point-to-plane error calculation between two surfaces

随着物体的不断旋转，系统可以得到不同角度的点云数据，遮挡或者丢失的部位在融合的过程中会被不断填充，表面点云会被持续优化，最终得到融合的点云信息.

在整个点云抓取和融合的过程中，记录当前摄像机相对于初始帧时的旋转角度，当相对旋转角度大于360°时，表示物体已经完成一周扫描与融合，则结束点云抓取融合步骤.人像融合试验效果如图3所示.在整个扫描过程中Kinect保持固定，物体进行旋转.但也可以选择物体保持固定，移动Kinect来进行点云抓取和融合.

图3 人像融合效果Fig.3 Human body fusion result

2.3 点云后处理

本文算法并不严格设置试验环境，摆放好Kinect并启动后，只要将物体放在转椅上即可进行点云抓取.一方面由于Kinect本身分辨率与帧率存在限制，同时光斑匹配计算深度的方式使得获取的空间深度数据并不稳定，点云数据中存在着大量的误差，去噪平滑处理必不可少.另一方面，融合得到的点云数据可能包含地面等额外数据，这些数据需要被去除，只保留目标物体模型的点云，例如图3中的地面需要被剔除.

首先，使用随机抽样一致性算法(RANSAC)[13]分离出平面，此算法假设样本中既包含正确数据(可以被模型描述的数据)，也包含异常数据(偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声.这些异常数据可能是由于错误的测量、假设、计算等产生的.同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法.使用RANSAC的一个优点是即使数据集中存在大量的异常值，它也可以对模型参数进行较高精度的健壮估计.将模型参数设置为平面模型，即可以分离出地面点云.本文算法自动处理融合的点云，将地面、墙壁等额外点云信息进行切分，只保留目标物体的点云数据.

然后，使用基于统计的异常值检测方法进行去噪.扫描通常会产生密度不均匀的点云数据集，同时测量中的误差会产生稀疏的离群点，导致融合效果较差，使得估计局部点云特征(如采样点法向量等)的相关运算变得复杂，并可能导致表面抽取等后续处理失败.此去噪方法对每个点的邻域进行一个统计分析，计算该点到所有邻居点的平均距离.假设得到的结果是一个高斯分布，其形状由均值和标准差决定，平均距离在标准范围之外的点可被定义为离群点并从数据集中去除.这里使用八叉树来进行数据结构的存储，以便进行邻居点的快速查找.图4显示了原始点云与点云去噪后K最近邻平均距离的对比，横轴标表示点编号，纵轴标表示每个点到K最近邻平均距离的值.由图4可知，本文算法能够有效地去除小幅度噪声，并且有效地保持模型中的原有特征.

图4 去噪前后K最近邻平均距离对比Fig.4 K-nearest neighbor mean distance before and after denoising operation

最后，使用移动最小二乘法(least moving square)来平滑点云以及填补孔洞，并进行重采样.在测量较小的对象时会产生一些误差，这些误差造成的噪声很难使用基于统计分析的方法来去除，并且在表面重建的过程中会造成表面不光滑或者产生漏洞，为了建立完整的模型必须对此类的表面进行平滑处理和漏洞修复.对于不能进行额外扫描的遮挡部分，可以使用数据重采样方法来解决这个问题，重采样算法通过对周围点云数据进行高阶多项式插值来填补表面缺失的部分.通过实现重采样，一些小的误差会得到校正.人像重采样操作前后的效果如图5所示.由图5可以看到，重采样后的点云数量增加了，表面变得平滑且局部的小孔洞被填充.

2.4 表面抽取

在获取融合好的点云数据后，需要将点云转化成光滑表面.由于扫描得到的点云是散乱的，使用贪婪投影三角化算法对有向点云进行三角化.首先将有向点云投影到某一局部二维坐标平面上，然后在这个二维坐标平面内进行三角化，最后根据平面内三维点的拓扑连接关系获得一个三角网格曲面模型.三角化过程是局部进行的，首先沿着一点的法线将该点投影到局部二维平面内并连接其他悬空点，然后再处理下一个点，直到所有符合几何正确性和拓扑正确性的点都被连接上，算法则结束.表面重建的结果如图6所示. 整个表面重建过程使用GPU实现，降低了算法的处理时间，提高了系统的效率.

(a) 重采样前 (b) 重采样后图5 重采样操作前后的效果Fig.5 Results before and after resampling operation

图6 表面重建结果Fig.6 Surface reconstruction result

3 3D打印处理

重建得到物体的三维模型后，需要使用3D打印机将模型快速成型.目前的桌面级3D打印机多采用熔丝制造的方法，而三角洲式打印机相比于同等精度的DIY打印机，机械复杂程度低，在xyz三个维度上都可以自由运动，打印速度和精度较高.参考rostock机型的工作原理以及组装方式，设计、采购并组装Delta打印机，这样既可以大大降低打印机的成本，又可以详细了解3D打印相关技术，探索并研制速度更快、价格更低廉、运行更稳定的桌面级3D打印机.图7为自制的三角洲式Delta打印机.

图7 Delta打印机Fig.7 Delta printer

3.1 重建模型处理

由于点云重建的三维模型是不完整的，同时尺寸大小也需要考虑，并不能直接用于3D打印.首先，三角剖分抽取的表面并不是一个封闭的模型，特别是模型的底部，由于并没有获取点云，在三角剖分阶段也不会产生三角面片.由于3D打印是从下到上一层一层进行打印，此时需要在调整模型大小后，在模型底部手动交互添加一个圆柱形的底座，使得模型底部平整.其次，需要考虑模型的重心问题.圆柱形底座抽样为离散点组成的结构，与重建模型上的原始点云一起计算整个模型的重心，需要保证重心垂线投影点位于底面内部，否则在3D打印的过程中产品不能保持平衡而倾倒，造成3D打印失败.此时需要加入额外的支柱，保持整个模型的平稳性，这些细小的支柱在打印完成后即可手动去除.最后，模型是空心的，一方面节省材料，另一方面缩减了打印时间，提高整个系统的效率.人像最终模型效果如图8所示.

图8 人像最终模型效果Fig.8 Final model of human body

3.2 打印实例

将处理好的三维模型使用Slic3r软件进行切片处理，即将三维模型转换成3D打印机可以执行的G代码来控制整个打印机的电流控制、电机转动、挤丝等操作.使用Printrun软件进行打印机监控和控制，三维模型即可一层一层地打印出来.相比较于同类的重建算法[14-15]，本文的三维模型重建算法具有试验场景搭建简单，自适应性强，能够快速重构出静态物体模型等特点.除此之外，该算法能够将重建的虚拟模型进行后续处理，使其满足封闭、光滑、平稳等特性，并最终进行3D打印，实现了由实物到虚拟三维模型再到实物的过程.人像打印结果如图9所示.

图9 人像打印结果Fig.9 3D printed result of human body

4 结 语

本文提出了一种面向3D打印的点云快速重建算法，该算法利用Kinect廉价、快速精确、可移动、光照影响低等特性，实现了摄像机姿态的快速跟踪，同时加入点云数据后处理的方法(包含去噪、配准、平滑升采样等操作)，得到完整的点云融合数据，并重建出光滑的三维模型.为了将Kinect重建的三维模型直接用于3D打印，本文描述了生成封闭、光滑、整体平衡的模型处理方法，并将模型保持为空心结构，最终实现3D打印.在制作打印机的同时，探索速度更快、价格更低廉、运行更稳定的3D打印技术.本文算法部署简单且自适应性强，不严格设定试验场景，具有较高的健壮性，同时该算法融合八叉树、GPU等方法，加快点云重建的效率，实现了由实物到虚拟三维模型再到实物的过程，相对于传统的模型设计与打印，具有快速性和高效性.未来工作将对三维重建做进一步完善，并加入颜色纹理信息进行纹理映射，从而打印彩色模型，同时提高系统的快速性与稳定性，实现由实物到打印实物的自动化过程.

[1] CIMA M, SACHS E, FAN T, et al. Three-dimensional printing techniques: US 538 7380[P]. 1995-02-07.

[2] GIBSON I, ROSEN D, STUCKER B. Additive manufacturing technologies[M]. New York: Springer, 2015.

[3] ZHANG Z. Microsoft kinect sensor and its effect[J]. IEEE Multimedia, 2012, 19(2):4-10.

[4] CAI Q, GALLUP D, ZHANG C, et al. 3D deformable face tracking with a commodity depth camera[C]// Computer Vision-ECCV 2010. Springer Berlin Heidelberg, 2010:229-242.

[5] NEWCOMBE R A, IZADI S, HILLIGES O, et al. Kinect-Fusion: Real-Time dense surface mapping and tracking[C]// 2011 IEEE International Symposium on Mixed and Augmented Reality. 2011:127-136

[6] IZADI S, KIM D, HILLIGES O, et al. KinectFusion: Real-time 3D reconstruction and interaction using a moving depth camera[C]// Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology. 2011:559-568.

[7] WHELAN T, KAESS M, FALLON M, et al. Kintinuous: Spatially extended KinectFusion[J]. RSS Workshop on RGB-D: Advanced Reasoning with Depth Cameras, (Sydney,

Australia), 2012.

[8] ZENG M, ZHAO F, ZHENG J, et al. Octree-based fusion for real-time 3D reconstruction[J]. Graphical Models, 2013, 75(3):126-136.

[9] TAUBIN G, MORENO D, LANMAN D. 3D scanning for personal 3D printing: Build your own desktop 3D scanner[C]// ACM SIGGRAPH 2014 Studio. 2014.

[10] BLAIS G, LEVINE M D. Registering multiview range data to create 3D computer objects[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1995, 17(8):820-824.

[11] CHEN Y, MEDIONI G. Object modeling by registration of multiple range images[C]// Proceedings of IEEE Conference on Robotics and Automations, Sacremento. 1991:2724-2729.

[12] LOW K L. Linear least-squares optimization for point-to-plane ICP surface registration[R].Technical Report TR04-004,Department of Computer Science,University of North Carolina at Chapel Hill,February 2004.

[13] BOLLES R C, FISCHLER M A. Ransac-based approach to model fitting and its application to finding cylinders in range data[C]// Proceedings of the 7th International Joint Conference on Artificial intelligence. 1981.

[14] 朱江涛, 吴以凡, 周亮. 基于多Kinect的三维人体重建系统[J]. 东华大学学报(自然科学版), 2015, 41(2):227-231.

[15] 周瑾, 潘建江, 童晶,等. 使用Kinect快速重建三维人体[J]. 计算机辅助设计与图形学学报, 2013, 25(6):873-879.

Point Cloud Reconstruction Rapid Algorithm for 3D Printing

WANGChao,WANGChang-bo

(School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China)

Using KinectFusion point cloud fusion technology, the combination of 3D reconstruction and 3D printing is explored and a new point cloud reconstruction rapid method for 3D printing is designed and implemented. Surface point cloud data captured by handheld Kinect is stored by octree and ICP (iterative closest point) algorithm is adopted to implement point cloud registration and fusion. The statistical outlier detection method, random sampling consensus algorithm (RANSAC) and moving least squares method are employed to process point cloud data. Then the point cloud data is used in the surface reconstruction step. A base, pillars and other missing parts are added into the model to maintain the stability of the model. Finally the virtual model is printed using homemade Delta printer. Experimental results show that the algorithm implements the process of getting 3D virtual model from real objects and using virtual model for rapid prototyping. The devices are at low price and simple to deploy and the algorithm is effective.

point cloud data; 3D reconstruction; point cloud registration; 3D printing

2015-12-31

国家自然科学基金资助项目(61532002，61272199)；国家高技术研究发展计划(863)资助项目(2015AA016404)；教育部博士点基金资助项目(20130076110008).

王 超(1990—),男,吉林四平人，硕士研究生,研究方向为点云重建、流体仿真、3D打印等.E-mail:598027501@qq.com 王长波(联系人),男，教授，E-mail:cbwang@sei.ecnu.edu.cn

TP 301.6

A

1671-0444 (2016)04-0466-07