一種面向3D打印的點云快速重建算法

王 超，王長波

(華東師范大學 計算機科學與軟件工程學院，上海 200062)

一種面向3D打印的點云快速重建算法

王 超，王長波

(華東師范大學 計算機科學與軟件工程學院，上海 200062)

采用KinectFusion點云融合技術，探索三維重建技術與3D打印技術的結合性，設計并實現了一種面向3D打印的點云快速重建算法.首先使用手持型Kinect獲取物體表面點云數據，使用八叉樹存儲數據，利用ICP(iterative closest point)算法進行點云配準與融合；然后采用基于統(tǒng)計異常值檢測方法、隨機抽樣一致性算法(RANSAC)、移動最小二乘法等算法對點云數據進行后處理；再將處理后的點云數據進行三維表面重構并根據重心加入底座、支柱等缺失部位，以保持模型的平穩(wěn)性；最后使用自制的三角洲打印機打印成型.試驗結果表明，該算法實現了從實物到三維虛擬模型再到實物打印成型的整個過程，具有設備成本低、實現簡單并且高效快速等特點.

點云數據；三維重建；點云配準；3D打印

近幾年隨著3D打印技術[1-2]的發(fā)展，快速成型技術也取得了巨大的突破，其在工業(yè)制造、航空航天、生物醫(yī)療等領域占據重要地位.傳統(tǒng)用于3D打印的虛擬模型，需要圖形設計人員在相關軟件內進行設計與編輯，此類三維模型結構復雜，編輯耗時，增加了模型設計的難度，同時也降低了模型設計到打印實物整個過程的效率，亟需尋找一種高效快速的模型生成方法.

另外，三維重建技術在游戲、影視動畫制作、虛擬現實和文物保護等領域得到了廣泛應用.Kinect傳感器[3]的出現，使得深度攝像機姿態(tài)的跟蹤與重建[4]變得簡單方便.Kinect傳感器不受可見光影響，同時具有成像速度快、價格相對低廉、操作方式簡單等優(yōu)點，基于Kinect的三維重建方法也成為了一個研究熱點.在基于Kinect重建算法中，最具有代表性的為KinectFusion算法[5-6]，此方法抓取場景中的靜態(tài)物體表面點云并融合，實時地重建出物體的三維模型.文獻[7]拓展了原始的KinectFusion工作，克服了此算法重建空間有限制的缺點，使得KinectFusion算法適用于較大的場景.文獻[8]提出了基于八叉樹(octree)的表面形式，提高了基于Kinect的動態(tài)場景重建的速率.然而，使用Kinect重建的三維模型具有不完整、不平滑、不封閉等缺點，不能直接用于3D打印.因此，將三維重建技術與3D打印技術相結合仍然是一個開放性的課題[9].

針對上述問題，本文基于KinectFusion算法提出了一種面向3D打印的點云重建方法，探索三維重建技術與3D打印技術結合的可行性.首先使用Kinect攝像機對場景中的靜態(tài)物體進行快速重建，主要包括點云抓取與快速融合、點云去噪、點云融合、表面抽取等操作；再將重建的模型進行后處理，包括底面添加、模型閉合、打印支柱添加等操作；最后使用3D打印機將模型打印出來.本文算法具有以下特點：(1) 將點云重建技術與3D打印技術相結合，在KinectFusion算法框架的基礎上，加入八叉樹、點云后處理、抽取表面等處理，能夠使用點云快速重建目標物體模型.(2) 在制作打印機的同時，探索速度更快、價格更低廉、運行更穩(wěn)定的3D打印技術.將點云重建的模型進行處理，使模型滿足封閉、表面光滑、整體平穩(wěn)等特性，并加入底座、支柱等缺失部件，獲得適合3D打印的模型后進行3D打印成型. (3) 算法自適應性強，不嚴格設定試驗場景，具有較高的健壯性，同時試驗設備成本低、部署簡單.

1 算法概述

本文算法使用Kinect對場景物體進行掃描，將獲取的點云作為輸入，經過點云融合、去噪、重建，模型處理等步驟，最后將模型進行快速打印作為整個算法的輸出，算法框架如圖1所示.該算法主要分為兩個部分：Kinect點云重建與3D打印處理.Kinect點云重建主要包括點云抓取、點云融合、點云后處理和表面抽取等步驟；3D打印處理主要包括重建模型處理和快速打印成型兩個步驟.

圖1 算法框架Fig.1 Algorithm framework

2 Kinect點云重建

首先通過Kinect設備獲取點云數據，在掃描的過程中跟蹤攝像機的空間姿態(tài)參數(包括位置和朝向)，將多個角度抓取的點云數據不斷融合生成一個完整的點云數據，并進行后處理，最后進行表面抽取以獲得3D模型.

2.1 點云抓取

Kinect采集點云數據不受光線影響，精度較高，分辨率為640像素×480像素，幀率為30幀/s.將試驗場景選擇為空曠的大廳，這樣可以減少背景物體的影響，從而增加點云配準的精度.試驗過程中，轉椅上的物體正對Kinect旋轉，實時得到點云數據并顯示出來.在點云抓取過程中，計算物體相對于Kinect攝像頭的旋轉角度，并將新一幀抓取的點云數據融合到全局點云模型中.此處抓取點云使用KinectFusion框架，在保存點云數據的同時獲取對應的RGB圖像信息.

2.2 點云融合

在點云抓取與融合過程中，需要不斷計算攝像頭的空間姿態(tài)信息，這里的空間姿態(tài)信息Tg(如式(1)所示)具有6個自由度.

(1)

式中：t為平移向量，其自由度為3; 0T=[0 0 0]；R為旋轉矩陣，其自由度為3.由于Kinect具有較高的幀率，所以可以假設相鄰兩幀之間攝像機的空間位置移動非常小，基于此假設可以使用快速投影數據關聯算法[10]， 來獲得相鄰幀點云之間的對應關系以及點到面的幾何關系[11].計算攝像機空間姿態(tài)信息時，采用ICP(iterative closest point)算法[12]計算兩個點云之間的匹配程度，若點云匹配成功，可以得到兩個點云之間的平移和旋轉信息.點云配準時需要計算匹配點的誤差值.傳統(tǒng)方法一般采用點到點的方式計算兩個點的空間歐氏距離，方法簡單，但是對于大體積點云不能達到實時性的要求.此時采用點到面的方法，即不是計算對應點對之間的距離，而是計算源點到對應點處切面的距離，如圖2所示.源點si=(six,siy,siz, 1)和目標點di=(dix,diy,diz, 1)為一對匹配點，di處的法向ni=(nix,niy,niz, 0)，那么每次ICP迭代的目標最優(yōu)解Mopt為

(2)

式中：M和Mopt為4×4的剛體變換矩陣.雖然采用點到面的計算方式在每一步迭代中比點到點的計算方式慢，但前者收斂速度快，能夠達到實時性要求. 在ICP運行過程中需要不斷查找空間的匹配點，系統(tǒng)采用八叉樹來存儲數據，以加快空間中鄰居查找的速度.

圖2 兩平面間的點到面誤差計算Fig.2 Point-to-plane error calculation between two surfaces

隨著物體的不斷旋轉，系統(tǒng)可以得到不同角度的點云數據，遮擋或者丟失的部位在融合的過程中會被不斷填充，表面點云會被持續(xù)優(yōu)化，最終得到融合的點云信息.

在整個點云抓取和融合的過程中，記錄當前攝像機相對于初始幀時的旋轉角度，當相對旋轉角度大于360°時，表示物體已經完成一周掃描與融合，則結束點云抓取融合步驟.人像融合試驗效果如圖3所示.在整個掃描過程中Kinect保持固定，物體進行旋轉.但也可以選擇物體保持固定，移動Kinect來進行點云抓取和融合.

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

2.3 點云后處理

本文算法并不嚴格設置試驗環(huán)境，擺放好Kinect并啟動后，只要將物體放在轉椅上即可進行點云抓取.一方面由于Kinect本身分辨率與幀率存在限制，同時光斑匹配計算深度的方式使得獲取的空間深度數據并不穩(wěn)定，點云數據中存在著大量的誤差，去噪平滑處理必不可少.另一方面，融合得到的點云數據可能包含地面等額外數據，這些數據需要被去除，只保留目標物體模型的點云，例如圖3中的地面需要被剔除.

首先，使用隨機抽樣一致性算法(RANSAC)[13]分離出平面，此算法假設樣本中既包含正確數據(可以被模型描述的數據)，也包含異常數據(偏離正常范圍很遠、無法適應數學模型的數據)，即數據集中含有噪聲.這些異常數據可能是由于錯誤的測量、假設、計算等產生的.同時RANSAC也假設，給定一組正確的數據，存在可以計算出符合這些數據的模型參數的方法.使用RANSAC的一個優(yōu)點是即使數據集中存在大量的異常值，它也可以對模型參數進行較高精度的健壯估計.將模型參數設置為平面模型，即可以分離出地面點云.本文算法自動處理融合的點云，將地面、墻壁等額外點云信息進行切分，只保留目標物體的點云數據.

然后，使用基于統(tǒng)計的異常值檢測方法進行去噪.掃描通常會產生密度不均勻的點云數據集，同時測量中的誤差會產生稀疏的離群點，導致融合效果較差，使得估計局部點云特征(如采樣點法向量等)的相關運算變得復雜，并可能導致表面抽取等后續(xù)處理失敗.此去噪方法對每個點的鄰域進行一個統(tǒng)計分析，計算該點到所有鄰居點的平均距離.假設得到的結果是一個高斯分布，其形狀由均值和標準差決定，平均距離在標準范圍之外的點可被定義為離群點并從數據集中去除.這里使用八叉樹來進行數據結構的存儲，以便進行鄰居點的快速查找.圖4顯示了原始點云與點云去噪后K最近鄰平均距離的對比，橫軸標表示點編號，縱軸標表示每個點到K最近鄰平均距離的值.由圖4可知，本文算法能夠有效地去除小幅度噪聲，并且有效地保持模型中的原有特征.

圖4 去噪前后K最近鄰平均距離對比Fig.4 K-nearest neighbor mean distance before and after denoising operation

最后，使用移動最小二乘法(least moving square)來平滑點云以及填補孔洞，并進行重采樣.在測量較小的對象時會產生一些誤差，這些誤差造成的噪聲很難使用基于統(tǒng)計分析的方法來去除，并且在表面重建的過程中會造成表面不光滑或者產生漏洞，為了建立完整的模型必須對此類的表面進行平滑處理和漏洞修復.對于不能進行額外掃描的遮擋部分，可以使用數據重采樣方法來解決這個問題，重采樣算法通過對周圍點云數據進行高階多項式插值來填補表面缺失的部分.通過實現重采樣，一些小的誤差會得到校正.人像重采樣操作前后的效果如圖5所示.由圖5可以看到，重采樣后的點云數量增加了，表面變得平滑且局部的小孔洞被填充.

2.4 表面抽取

在獲取融合好的點云數據后，需要將點云轉化成光滑表面.由于掃描得到的點云是散亂的，使用貪婪投影三角化算法對有向點云進行三角化.首先將有向點云投影到某一局部二維坐標平面上，然后在這個二維坐標平面內進行三角化，最后根據平面內三維點的拓撲連接關系獲得一個三角網格曲面模型.三角化過程是局部進行的，首先沿著一點的法線將該點投影到局部二維平面內并連接其他懸空點，然后再處理下一個點，直到所有符合幾何正確性和拓撲正確性的點都被連接上，算法則結束.表面重建的結果如圖6所示. 整個表面重建過程使用GPU實現，降低了算法的處理時間，提高了系統(tǒng)的效率.

(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打印相關技術，探索并研制速度更快、價格更低廉、運行更穩(wěn)定的桌面級3D打印機.圖7為自制的三角洲式Delta打印機.

圖7 Delta打印機Fig.7 Delta printer

3.1 重建模型處理

由于點云重建的三維模型是不完整的，同時尺寸大小也需要考慮，并不能直接用于3D打印.首先，三角剖分抽取的表面并不是一個封閉的模型，特別是模型的底部，由于并沒有獲取點云，在三角剖分階段也不會產生三角面片.由于3D打印是從下到上一層一層進行打印，此時需要在調整模型大小后，在模型底部手動交互添加一個圓柱形的底座，使得模型底部平整.其次，需要考慮模型的重心問題.圓柱形底座抽樣為離散點組成的結構，與重建模型上的原始點云一起計算整個模型的重心，需要保證重心垂線投影點位于底面內部，否則在3D打印的過程中產品不能保持平衡而傾倒，造成3D打印失敗.此時需要加入額外的支柱，保持整個模型的平穩(wěn)性，這些細小的支柱在打印完成后即可手動去除.最后，模型是空心的，一方面節(jié)省材料，另一方面縮減了打印時間，提高整個系統(tǒng)的效率.人像最終模型效果如圖8所示.

圖8 人像最終模型效果Fig.8 Final model of human body

3.2 打印實例

將處理好的三維模型使用Slic3r軟件進行切片處理，即將三維模型轉換成3D打印機可以執(zhí)行的G代碼來控制整個打印機的電流控制、電機轉動、擠絲等操作.使用Printrun軟件進行打印機監(jiān)控和控制，三維模型即可一層一層地打印出來.相比較于同類的重建算法[14-15]，本文的三維模型重建算法具有試驗場景搭建簡單，自適應性強，能夠快速重構出靜態(tài)物體模型等特點.除此之外，該算法能夠將重建的虛擬模型進行后續(xù)處理，使其滿足封閉、光滑、平穩(wěn)等特性，并最終進行3D打印，實現了由實物到虛擬三維模型再到實物的過程.人像打印結果如圖9所示.

圖9 人像打印結果Fig.9 3D printed result of human body

4 結 語

本文提出了一種面向3D打印的點云快速重建算法，該算法利用Kinect廉價、快速精確、可移動、光照影響低等特性，實現了攝像機姿態(tài)的快速跟蹤，同時加入點云數據后處理的方法(包含去噪、配準、平滑升采樣等操作)，得到完整的點云融合數據，并重建出光滑的三維模型.為了將Kinect重建的三維模型直接用于3D打印，本文描述了生成封閉、光滑、整體平衡的模型處理方法，并將模型保持為空心結構，最終實現3D打印.在制作打印機的同時，探索速度更快、價格更低廉、運行更穩(wěn)定的3D打印技術.本文算法部署簡單且自適應性強，不嚴格設定試驗場景，具有較高的健壯性，同時該算法融合八叉樹、GPU等方法，加快點云重建的效率，實現了由實物到虛擬三維模型再到實物的過程，相對于傳統(tǒng)的模型設計與打印，具有快速性和高效性.未來工作將對三維重建做進一步完善，并加入顏色紋理信息進行紋理映射，從而打印彩色模型，同時提高系統(tǒng)的快速性與穩(wěn)定性，實現由實物到打印實物的自動化過程.

[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的三維人體重建系統(tǒng)[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)；國家高技術研究發(fā)展計劃(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