鄧念晨, 楊旭波
(上海交通大學 軟件學院,上海 200240)
多Kinect實時室內(nèi)動態(tài)場景三維重建
鄧念晨, 楊旭波
(上海交通大學 軟件學院,上海 200240)
采用多個Kinect從不同角度同時捕獲場景,將它們的深度圖和彩色圖結(jié)合在一起,通過數(shù)據(jù)預處理、頂點構(gòu)建、點云注冊和表面重建等步驟得到場景三維模型.整個流程均在GPU上實現(xiàn)以加速運算,實現(xiàn)了基于GPU的迭代最近點算法、基于GPU的八叉樹構(gòu)建、基于有向距離函數(shù)的表面重建等關(guān)鍵算法.試驗中,整個算法運行幀率達到8.74 f/s;重建分辨率達到約5.9 mm.試驗表明,算法基本滿足實時動態(tài)場景重建的要求,重建模型的精度滿足非精確計算類應用的需求.
三維重建;室內(nèi)動態(tài)場景;多Kinect設備;迭代最近點配準;Marching Cubes算法
場景三維重建技術(shù)是利用傳感器和計算機,通過對場景的紋理、深度等元數(shù)據(jù)進行分析和處理后自動(或半自動)地構(gòu)建場景的三維模型.目前,場景重建技術(shù)在工業(yè)模擬、智能機器人等諸多方面都發(fā)揮著十分重要的作用.然而,較長的計算時間和昂貴的設備極大地阻礙了這一技術(shù)在協(xié)作辦公和日常生活領(lǐng)域的推廣應用.因此,基于廉價設備的實時場景三維重建技術(shù)具有巨大的研究意義和應用價值.本文以遠程協(xié)作應用為背景,采用Kinect設備捕獲場景數(shù)據(jù),研究如何實時重建滿足一般用戶視覺精度要求的場景模型.
人們對三維重建技術(shù)的研究已達數(shù)十年,也提出了許多方法.根據(jù)原始場景數(shù)據(jù)的類型,三維重建技術(shù)主要分為基于深度數(shù)據(jù)的三維重建[1-5]和基于紋理數(shù)據(jù)的三維重建[6-7],其中大多數(shù)方法是基于深度數(shù)據(jù)的.基于紋理數(shù)據(jù)的方法具有硬件成本低廉的優(yōu)勢,但物體表面的紋理本身受環(huán)境光影響較大,而且重建過程包含大量經(jīng)驗和假設,一般情況下的重建精度往往不能滿足要求.而基于深度數(shù)據(jù)的三維重建方法更為簡單、穩(wěn)定,易于推廣應用.根據(jù)重建模型的抽象等級,三維重建技術(shù)可以分為3個層次[4]:高層次關(guān)注的是一種或者一類物體,主要用于物體識別[8];中層次使用基本幾何圖元構(gòu)建模型,主要用于物體分割[1];低層次則完全構(gòu)建模型網(wǎng)格表面,不受任何假設的限制,用于對物體或場景精確建模以便重現(xiàn)[2, 4-5].本文重點研究基于深度數(shù)據(jù)的網(wǎng)格模型精確建模方法.
近幾年,由于通用圖形處理器(GPGPU)的推廣應用以及類似Kinect這樣具有實時深度獲取能力的設備的出現(xiàn),實時三維重建技術(shù)開始成為研究熱點.文獻[9]利用Kinect從多個角度拍攝物體,然后離線重建完整的物體模型.而文獻[10]則在Kinect輸入數(shù)據(jù)上提出了更好的預處理方法.文獻[5, 11]利用Kinect設備和GPU運算達到了實時重建的效率.文獻[12]繼續(xù)進行了改進,使得重建算法能較為快速地響應場景中發(fā)生的變化.而文獻[13]則結(jié)合圖像追蹤技術(shù)來重建和追蹤非剛體物體的變化.值得一提的是,上述方法都僅使用了單臺Kinect設備,由于受限于單一設備的視野局限,需要手持設備移動掃描才能獲取物體的多個視角,以便重建出較為完整的模型.本文采用多臺Kinect設備從不同視角捕獲場景并進行融合,用戶不需要手持設備.這種配置更適合于遠程協(xié)作的應用環(huán)境,使用戶可以解放雙手進行更好的交流和協(xié)作.
1.1硬件系統(tǒng)設計
在遠程協(xié)作的工作平臺中,用戶不便手持Kinect設備進行工作,因此,本文系統(tǒng)使用2~4個固定擺放在場景周圍不同方位的Kinect設備拍攝場景(如圖1所示),采用普通的個人計算機進行計算,得到場景的三維網(wǎng)格模型,且固定Kinect設備能簡化重建動態(tài)場景的算法,也使重建結(jié)果更加穩(wěn)定.
圖1 硬件系統(tǒng)布局示意圖Fig.1 Hardware system layout
本系統(tǒng)在部署完成后需要進行一次標定操作,包括對所有Kinect設備分別進行內(nèi)參標定,對所有Kinect設備統(tǒng)一進行外參標定.內(nèi)參和外參標定均采用棋盤格標定法.
1.2算法流程概覽
實時動態(tài)場景重建算法的主要流程為獲取數(shù)據(jù)(深度數(shù)據(jù)和紋理色彩數(shù)據(jù)等)、對數(shù)據(jù)進行預處理、根據(jù)深度數(shù)據(jù)構(gòu)建三維點云、對多組點云進行注冊、從點云構(gòu)建網(wǎng)格表面,具體如下所述.
(1) 對數(shù)據(jù)進行預處理.從傳感器獲取的數(shù)據(jù)存在一定的噪聲和誤差分布特性,因此,需要對原始的深度數(shù)據(jù)進行特殊的預處理以降低噪聲的干擾,從原始數(shù)據(jù)的層面減少誤差.
(2) 根據(jù)深度數(shù)據(jù)構(gòu)建三維點云.對于每個傳感器獲得的深度數(shù)據(jù)和彩色圖像數(shù)據(jù),根據(jù)傳感器的內(nèi)參和外參信息計算點云中各點的三維坐標、顏色和法向量.這時將它們可視化已經(jīng)可以看出一定的重建效果,但是由于基于棋盤格的外參標定并不十分精確,從結(jié)構(gòu)和紋理上可以看出多組點云并不能完全匹配.
(3) 對多組點云進行配準.旨在減小多組點云之間存在的變換偏差.許多有關(guān)三維重建的研究(例如文獻[5, 11])都使用迭代最近點配準算法(ICP)[14],本文亦在該算法基礎(chǔ)上提出了改進方案.
(4) 從點云構(gòu)建網(wǎng)格表面.從三維點云中構(gòu)建較為完整的表面網(wǎng)格模型,具體涉及基于GPU的八叉樹構(gòu)建、有向距離函數(shù)計算和三角面片生成等算法.
由于硬件層面的原因,Kinect設備獲得的彩色圖呈現(xiàn)出明顯的條紋狀噪聲,深度圖中也存在較為明顯的隨機噪聲,影響重建效果.因此,在使用這些數(shù)據(jù)生成三維點云前,首先需要進行二維圖像層面的降噪處理.針對色彩圖的條紋噪聲特征,本文采用反交錯技術(shù)處理色彩圖,基本消除了這一噪聲,去噪效果如圖2所示.
(a)預處理前
(b) 預處理后圖2 彩色圖預處理前后的效果對比Fig.2 Color images before and after preprocess
針對深度圖中的隨機噪聲,如采用傳統(tǒng)高斯濾波方法在降噪的同時會導致邊緣模糊,因此,本文采用帶邊界檢測的高斯濾波方法.該方法能夠在消除內(nèi)部高頻噪聲的同時,保持邊界的清晰.經(jīng)過這一處理的深度圖所構(gòu)建的三維模型不會在邊緣部分產(chǎn)生毛刺,克服了傳統(tǒng)高斯濾波方法的不足(如圖3所示).
(a) 傳統(tǒng)高斯濾波
(b) 帶邊界檢測的高斯濾波圖3 使用經(jīng)過傳統(tǒng)高斯濾波和帶邊界檢測的高斯濾波處理的單深度圖的重建結(jié)果對比Fig.3 The reconstruct result from single depth images processed by Gauss filter without and with edge detection
在外參標定過程中的微小誤差會被構(gòu)建三維點云時的逆投影變換放大,因此,本文利用ICP算法實時地改進外參標定的精度.為了增強算法的魯棒性,本文采用位置-色彩混合空間下的距離定義[11].
另外,考慮到GPU的并行計算特性以及由深度圖生成的點云具有高度的結(jié)構(gòu)化,本文提出了基于投影關(guān)系的快速最近鄰搜索算法來加速最近鄰搜索.該算法的主要依據(jù)是在深度圖中排列的像素通過逆投影生成的三維頂點也具有一定的排列關(guān)系,即兩個距離相近的頂點,其在深度圖上的投影之間的距離也很接近(只要這兩個點深度值不是很小).因此,若假設某個頂點v1的最近鄰頂點是v2,v2的投影p2有很大的概率落在v1的投影p1的小鄰域內(nèi),則在計算v1的最近鄰時搜索范圍可以被縮減到p1的小鄰域內(nèi).
場景重建的最后一個步驟是將點云變成表面模型.離線重建一般采用泊松表面重建方法[15],但是該方法計算復雜度較高.本文所實現(xiàn)的表面提取算法采用八叉樹結(jié)構(gòu)組織點云和劃分空間,使用有向距離函數(shù)模型計算零值面,最后利用基于八叉樹的Marching Cubes算法構(gòu)建三角面片.
4.1基于GPU的八叉樹構(gòu)建算法
本文參照文獻[16]中所述設計并實現(xiàn)了基于GPU的八叉樹構(gòu)建算法.為了使八叉樹構(gòu)建和查找能在GPU上高效執(zhí)行,本文采用了廣度優(yōu)先的構(gòu)建算法,并使用預先計算好的鄰居查找表查找節(jié)點的鄰居,將帶有數(shù)據(jù)依賴而無法并行執(zhí)行的操作降到最少.
4.2基于有向距離函數(shù)的等值面計算
4.3Marching Cubes表面提取算法
Marching Cubes算法[18]是基于網(wǎng)格劃分的表面提取算法,其基本思想是在每個網(wǎng)格中的小立方體單元中用平面結(jié)構(gòu)近似表面.根據(jù)立方體上的8個頂點在模型的內(nèi)部或外部的情況可以將立方體分為256類,又由于內(nèi)外對稱、立方體旋轉(zhuǎn)對稱,這256個種類可以規(guī)約到15個基本種類[18](如圖4所示).Marching Cubes算法的基本流程對于網(wǎng)格中的每個單元,以6個頂點的正負值(表示在三維模型的外部或內(nèi)部)組成索引查表獲得該單元需要形成的一系列三角形頂點索引.
圖4 15類立方體可以形成的三角面片[18]Fig.4 Fifteen kinds of triangle generation in a cube [18]
基于八叉樹的Marching Cubes算法和傳統(tǒng)的Marching Cubes算法相似,由于八叉樹的葉子節(jié)點僅存在于有原始點云中的點的區(qū)域,因此,會有部分三角面片因節(jié)點的缺失而無法構(gòu)建,導致最終生成的表面中包含許多小洞(如圖5所示).
圖5 基于八叉樹的Marching Cubes算法重建的表面Fig.5 Surface reconstructed from octree-based Marching Cubes algorithm
為了解決這一問題,本文提出了構(gòu)造偽節(jié)點的方法,其基本思路是對于所有在面f上與表面存在交線的節(jié)點n,構(gòu)造一個偽節(jié)點nf,與n在f上鄰接,并將在結(jié)構(gòu)關(guān)系上屬于nf的頂點和邊賦給nf.然后再對所有偽節(jié)點執(zhí)行Marching Cubes算法生成三角面片,便可補上這些空洞(如圖6所示,圖中頂點上的黑色標記表示該頂點為正值,反之為負值,下同).
圖6 偽節(jié)點與在偽節(jié)點上構(gòu)造的面片(圖中畫陰影的三角形)Fig.6 Fake node and the patch on it (the triangle marked with shadow)
由偽節(jié)點的構(gòu)造而引出的一個問題,即偽節(jié)點中不包含任何原始點云中的點,因此由偽節(jié)點而新增的頂點(可以稱其為偽頂點)并不存在一個有向距離值(可以假定其為無窮大).一個無窮大的值并不屬于正值或負值,這導致無法明確識別該立方體的類型.因此,本算法采用就近原則,將一個無窮大值的符號定義為該頂點的3個鄰接頂點中非無窮大值的符號(如圖7(a)).若3個鄰接頂點中存在不同的符號(如圖7(b))或3個鄰接頂點均為偽頂點(如圖7 (c)),則拋棄該偽節(jié)點,不生成任何三角面片.
(a) 3個相鄰頂點符號相同
(b) 3個相鄰頂點符號不同
(c) 3個相鄰頂點均為偽頂點圖7 就近原則處理無窮大值的符號Fig.7 The sign of infinite decided by principle of proximity
而在生成三角面片方面,由于為偽頂點賦予了符號,Marching Cubes算法生成的三角面片中可能會存在頂點在偽邊上的情況.對于這種情況,僅需要將該三角面片刪除即可.使用構(gòu)造偽節(jié)點的方法后則重建結(jié)果中含有的空洞明顯減少了(如圖8所示).
圖8 用構(gòu)造偽節(jié)點方法改進后的重建結(jié)果Fig.8 The improved result by using fake nodes
通過一系列試驗驗證本文所設計的場景重建算法的執(zhí)行結(jié)果,測試和優(yōu)化算法執(zhí)行性能.所有試驗均在同一臺普通的家用型筆記本電腦上進行,其主要硬件參數(shù)為:Intel?CoreTMi7-2670QM處理器,8.00 GB內(nèi)存以及AMD?RadeonTMHD 6770M圖形顯示卡.所有試驗均采用兩臺Kinect設備捕獲場景,兩臺Kinect設備中心軸之間的夾角約為45°,使用的深度圖和彩色圖分辨率均為320×240.
試驗場景為桌面物體及人物雕像,Kinect設備與場景主要物件的距離范圍為60~100 cm.試驗包括不同八叉樹層級的重建結(jié)果比較、時間和空間測試的性能分析.
5.1不同八叉樹層級的重建結(jié)果比較
該試驗目的是對比在不同的八叉樹層級上執(zhí)行表面提取的效果.用8~11層八叉樹(分別對應葉節(jié)點邊長為23.4, 11.7, 5.9 和2.9 mm)重建的結(jié)果如圖9所示.從圖9中可以看出,使用8和9層八叉樹重建的結(jié)果十分粗略,尤其是使用8層時,雕像的五官幾乎不可分辨.而使用11層八叉樹重建結(jié)果雖然保留了非常細致的細節(jié),但由于原采樣點的密度不足,該重建結(jié)果也存在大量的空洞.使用10層八叉樹重建的結(jié)果雖然細節(jié)較11層有所缺失,但在大部分區(qū)域都沒有空洞,是最為適合當前所使用的采樣分辨率的.因此,以下試驗均采用10層八叉樹重建.
(a) 8層八叉樹
(b) 9層八叉樹
(c) 10層八叉樹
(d) 11層八叉樹圖9 使用不同層數(shù)的八叉樹重建場景的結(jié)果Fig.9 The reconstruct results using different levels of octree
5.2時間性能分析和優(yōu)化
優(yōu)化前后主要步驟所用時間如表1所示.鑒于優(yōu)化前算法在清空八叉樹和提取表面花費的時間最多,優(yōu)化主要針對這兩個步驟進行.
表1 優(yōu)化前后主要步驟所用時間Table 1 Time spent in key steps before and after optimization
清空八叉樹的時間耗費過長主要是由于內(nèi)存到顯存的帶寬相對較窄,采用從內(nèi)存中將初始數(shù)據(jù)重新導入GPU緩存中的開銷巨大.因此,針對這一步驟的優(yōu)化采取了通過執(zhí)行shader為緩存寫入初始數(shù)據(jù)的方法.
對于提取表面步驟,首先進一步分析了表面提取算法中的各個步驟的時間開銷.優(yōu)化前后表面提取算法的各步驟時間開銷對比如圖10所示.由圖10可知,計算每個八叉樹頂點的有向距離花費了絕大多數(shù)的時間,而優(yōu)化該步驟的代碼后表面提取算法的時間開銷明顯縮短.
(a) 優(yōu)化前
(b) 優(yōu)化后圖10 優(yōu)化前后表面提取算法的各步驟時間開銷對比Fig.10 Time spent in each step of surface extraction before and after optimization
由表1可知,優(yōu)化后重建算法執(zhí)行時間是原來的33%,加速比達到3.02.優(yōu)化后的運行幀率可達到8.74 f/s.
5.3GPU內(nèi)存空間性能分析與優(yōu)化
場景重建算法所占用的GPU內(nèi)存空間如表2所示,所列數(shù)據(jù)為分析具體實現(xiàn)后計算而得.
表2 優(yōu)化前后主要數(shù)據(jù)結(jié)構(gòu)空間的使用效率Table 2 The space usage of main data structures before and after optimization
由表2可知,優(yōu)化前執(zhí)行場景重建算法需要329.88 MB的顯存空間,有效率僅有16.53%.主要原因是動態(tài)分配GPU緩存資源的開銷極大,一般都是在初始化時就創(chuàng)建了足夠大的空間.例如基于極端情況下每個八叉樹的葉子節(jié)點可能只包含一個點云中的點,因此,優(yōu)化前為八叉樹葉子節(jié)點分配的空間與分辨率和Kinect的個數(shù)的乘積一致.但是事實上由于點集分布的集中性,上述極端情況是不可能出現(xiàn)的.另外由于分辨率的增加只會導致點云的密度增加,并不會增加許多覆蓋區(qū)域,因此,實際上分辨率的增加并不會導致葉子節(jié)點的大幅增加.經(jīng)過對試驗數(shù)據(jù)的分析后,本文進行了3步優(yōu)化:
(1) 對點云數(shù)據(jù)進行壓緊處理,使得有效數(shù)據(jù)都集中在數(shù)組前端;
(2) 將為節(jié)點分配的空間大小與分辨率的關(guān)系從線性關(guān)系修正為與輸入分辨率的二次根呈線性關(guān)系,可以有效減少使用高分辨率輸入數(shù)據(jù)時的空間浪費;
(3) 將節(jié)點邊和節(jié)點頂點改為緊湊排列,并減少分配給節(jié)點邊和節(jié)點頂點的空間.
經(jīng)過3步優(yōu)化,算法所耗費的GPU內(nèi)存空間僅為優(yōu)化前的1/3,有效率提升至57.83%.
5.4辦公場景的重建
場景包含人物和放置著一些辦公物品的桌面.使用兩臺Kinect設備拍攝場景,其中心軸之間的夾角約為30°,與場景中主要物體的距離范圍為80~150 cm.重建結(jié)果如圖11.
圖11 辦公場景的重建結(jié)果Fig.11 Reconstruction of work scene
本文設計并實現(xiàn)了基于多個Kinect設備的實時動態(tài)場景重建技術(shù),性能基本滿足實時要求.主要研究成果包括:提出了基于投影關(guān)系的快速最近鄰搜索算法;用構(gòu)造偽節(jié)點法改進了基于八叉樹的Marching Cubes算法的重建結(jié)果;實現(xiàn)了完整的場景重建算法,并利用GPU并行技術(shù)達到了三維重建實時性.
未來工作將主要集中于以下幾點:深入研究更多應用在表面重建中的數(shù)學模型,以期提出一個更好的數(shù)學模型減少空洞和噪聲敏感度,并提升重建模型的細節(jié);引入紋理色彩分析算法,考慮研究色調(diào)補償和表面材質(zhì)提取等方面的內(nèi)容,并改進模型紋理的生成方法,提高模型紋理的真實感;進一步優(yōu)化性能.
[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] 劉田間,郭連朋,陳向?qū)?等.基于 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
楊旭波(聯(lián)系人),男,教授,E-mail:yangxubo@sjtu.edu.cn
TP 391
A