王劍飛 林金花 王璐

摘 要：目前，隨著深度傳感器的更新發(fā)展，使得三維重建的在線方法得以實現(xiàn).在線重建的難點(diǎn)在于如何能夠在保證較好的重建效果和重建規(guī)模的前提下，實時地將多個動態(tài)重疊深度圖轉(zhuǎn)化成一個三維模型.針對這一問題，本文算法基于空間索引策略構(gòu)建了一種存取高效的空間體素數(shù)據(jù)結(jié)構(gòu)，改進(jìn)了傳統(tǒng)體積融合方法中的規(guī)則分層網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，對隱含表面數(shù)據(jù)進(jìn)行實時存取與更新的同時，實現(xiàn)大尺度的在線三維重建.這些表面數(shù)據(jù)僅在觀測時存儲，并且高效地流入和流出索引表，實現(xiàn)了傳感器運(yùn)動過程中的在線場景重建.算法通過在GPU（Graphics Processing Pipeline）上完成深度圖預(yù)處理，攝像姿態(tài)估計，深度圖融合和表面繪制幾個核心階段，實現(xiàn)對細(xì)粒度的細(xì)節(jié)和大尺度的環(huán)境進(jìn)行交互式實時重建.通過實驗表明，改進(jìn)后的重建系統(tǒng)能夠在保證重建質(zhì)量與重建性能的同時，平均重建時間為21.6 ms，ICP姿態(tài)估計15次，用時8.0 ms，平均幀繪制速率提高13.3%，實現(xiàn)了對大尺度場景的實時三維重建.

關(guān)鍵詞：在線； 空間索引； 數(shù)據(jù)結(jié)構(gòu)； GPU； 實時重建

中圖分類號：TP391.41文獻(xiàn)標(biāo)志碼：A

Abstract：At present， with the development of the depth sensor， the on-line method of 3D reconstruction is realized. The difficulty of the online reconstruction is how to convert multiple dynamic overlapping depth maps into a three-dimensional model in real time under the premise of better reconstruction effect and reconstruction scale. To solve this problem， this paper constructed an efficient spatial voxel data structure based on the spatial index strategy， improving the hierarchical grid data structure of the traditional volume fusion method and realizing the real-time access to the hidden surface data. These surface data are only stored during the observation to achieve the sensor movement in the process of online scene reconstruction. The algorithm performs interactive real-time reconstruction of fine-grained detail and large-scale environment by completing several core stages， such as depth map preprocessing， camera pose estimation， depth map fusion and surface rendering， on the GPU （Graphics Processing Pipeline）. The experimental results show that the average reconstruction time is 21.6 ms， the ICP pose estimation is 15 times， and the average frame rendering rate is increased by 13.3% when the reconstruction time is 8.0 ms and the reconstruction time is 21.6 ms， realizing the real - time 3D reconstruction of large scale scenes.

Key words：online； spatial index； data structure； GPU； real-time reconstruction

三維重建是計算機(jī)視覺與圖形學(xué)的重要研究領(lǐng)域，隨著深度攝像機(jī)的廣泛使用，使得三維重建獲得了新的發(fā)展勢頭.由于這些設(shè)備能夠?qū)崟r輸出帶有噪聲的深度圖，使得最近的研究重點(diǎn)是如何使用這種深度攝像機(jī)獲得在線表面重建.在線表面重建在計算機(jī)交互式應(yīng)用領(lǐng)域表現(xiàn)良好，例如，增強(qiáng)現(xiàn)實（AR），其中真實世界的幾何信息可以與3D（three dimension）圖形融合并實時渲染；自主指導(dǎo)機(jī)器人重建及其對周圍環(huán)境的快速響應(yīng)；或者在3D打印過程中實現(xiàn)向用戶提供即時反饋[1-2].

傳統(tǒng)重建方法[3-4]大多基于一組完整的三維點(diǎn)坐標(biāo)實現(xiàn)重建，而在線重建是將多個重疊深度圖增量融合成一個不斷精進(jìn)的三維表示.為了達(dá)到較好的實時重建性能，重建質(zhì)量與重建規(guī)模不受影響，出現(xiàn)了許多先進(jìn)的基于GPU硬件加速的在線方法，這些方法通常采用不同類型的底層數(shù)據(jù)結(jié)構(gòu)，在重建速度、規(guī)模和質(zhì)量方面都具有不同程度的相互抵償.

參數(shù)重建方法[5-6]簡單地平均重疊樣本，并通過對表面拓?fù)涞暮唵渭僭O(shè)來實現(xiàn)點(diǎn)和局部多邊形的連接.同時出現(xiàn)的網(wǎng)格拉鏈方法[7]為每個表面區(qū)域選擇一個深度圖，并去除重疊區(qū)域中的冗余三角形進(jìn)而實現(xiàn)網(wǎng)格縫合.這些方法通過點(diǎn)的局部平均化來處理噪聲，但是在異常值和高曲率的區(qū)域表現(xiàn)不佳.因此出現(xiàn)了多種非直連多邊形網(wǎng)格的三維重建方法.

基于點(diǎn)的重建方法[8]通過合并重疊點(diǎn)來實現(xiàn)重建，從而避免推斷連通性.由于大多數(shù)深度傳感器的輸出是三維點(diǎn)樣本，使得基于點(diǎn)的三維重建更加容易，例如針對單個小對象的掃描系統(tǒng)[9].由于重建規(guī)模較小，使得小規(guī)模高質(zhì)量的三維重建得以實現(xiàn).較大尺度場景的三維重建通常需要降低重建速度或質(zhì)量來實現(xiàn)[10].這種方法使用簡單的非結(jié)構(gòu)化表示，可以緊密地映射到深度傳感器，但是缺乏直接重建表面的能力.對小物體的高質(zhì)量在線重建已經(jīng)得以實現(xiàn)[11]，但是大尺度重建需要以重建質(zhì)量或速度為代價[12].

基于高度圖的表示方法[13]支持連接表面數(shù)據(jù)的高效壓縮，使用更緊湊的2.5維度的連續(xù)表面表示來實現(xiàn)三維重建，這種方法尤其適用于大型建筑物的重建[14]，并且可以有效擴(kuò)展到更大尺度的場景，但是無法實現(xiàn)對復(fù)雜模型的三維重建.

基于體積數(shù)據(jù)結(jié)構(gòu)的重建方法（VRM，Volume Reconstruction Method）對三角測量的傳感器噪聲特性進(jìn)行有效估計，支持增量更新，不對表面數(shù)據(jù)進(jìn)行拓?fù)鋲嚎s，對于給定的樣本進(jìn)行累加平均，可以得到較好的重建效果和重建速度[15-17].然而，這種方法依賴于存取低效的規(guī)則體素網(wǎng)格，反而限制了重建規(guī)模.

為解決體積重建方法的空間限制問題，出現(xiàn)了多種重建方法.Keller等人[18]使用基于點(diǎn)的表示方法來加強(qiáng)體積融合的質(zhì)量，雖然擺脫了空間數(shù)據(jù)結(jié)構(gòu)的限制，但重建質(zhì)量隨之降低[19].

同時出現(xiàn)了移動體積方法[20]，擴(kuò)展了基于深度傳感器融合的GPU渲染管線[21].這種方法在攝像機(jī)運(yùn)動過程中使用GPU管線并行處理體素流，釋放了用于存儲新近數(shù)據(jù)的空間.然而這些數(shù)據(jù)流是單向有損的，即當(dāng)表面數(shù)據(jù)被壓縮到網(wǎng)格時，無法從主機(jī)回流到GPU，并且算法仍然使用規(guī)則網(wǎng)格結(jié)構(gòu)，這意味著數(shù)據(jù)流必須保持較小，才能確保精細(xì)的重建質(zhì)量.這使得重建被限制在鄰近幾何體的場景重建，由深度傳感器得到的全范圍數(shù)據(jù)沒有得到充分利用.

規(guī)則體素網(wǎng)格的限制使得許多研究人員進(jìn)一步尋求更加有效的體積數(shù)據(jù)結(jié)構(gòu).例如，基于稀疏空間體素的體積表示方法[22]，用于大數(shù)據(jù)集的外核流架構(gòu)[23].這些分層數(shù)據(jù)結(jié)構(gòu)被應(yīng)用到三維重建的難點(diǎn)在于：在重建過程中需要對基礎(chǔ)數(shù)據(jù)進(jìn)行實時更新.例如，Zeng等人[24]實現(xiàn)了一個9到10級的八叉樹結(jié)構(gòu)，將傳感器融合管線擴(kuò)展到8m*8m*2m的室內(nèi)空間.Ptzold等人[25]進(jìn)一步提出了一種基于GPU的八叉樹體素網(wǎng)格表示方法，實現(xiàn)了對無網(wǎng)格外核體素的實時重建.然而，這些方法需要構(gòu)建復(fù)雜的八叉樹結(jié)構(gòu)，計算復(fù)雜度隨之增加，指針訪問的額外開銷較大[26-27].

基于深度傳感器融合的三維重建方法使用體積重建方法中的規(guī)則體素網(wǎng)格來重建表面，存儲空間占用量較大，并需要同時密集地表示空白的空間和表面，重建的難點(diǎn)是如何在不降低質(zhì)量的情況下重建大尺度的場景.

針對分層數(shù)據(jù)結(jié)構(gòu)在體積融合過程中存在的計算過度復(fù)雜的問題，本文提出了一種新的實時表面重建方法，支持大尺度高質(zhì)量的三維重建.本文算法兼具體積方法的優(yōu)點(diǎn)，但不依賴于受存儲約束的體素網(wǎng)格，同時無需分層數(shù)據(jù)結(jié)構(gòu)的計算開銷.與傳統(tǒng)分層數(shù)據(jù)結(jié)構(gòu)不同，本文算法基于一種存取高效的空間索引策略，對隱含表面數(shù)據(jù)進(jìn)行實時融合.表面數(shù)據(jù)被密集存儲在觀測單元格中，同時數(shù)據(jù)可以高效地流入或流出索引表，從而在傳感器運(yùn)動過程中進(jìn)一步實現(xiàn)可伸縮重建.本文給出了一種基于空間索引策略的空間體素數(shù)據(jù)結(jié)構(gòu)，通過對基礎(chǔ)數(shù)據(jù)的不斷更新，實現(xiàn)了對細(xì)粒度和大尺度場景的交互式重建.

1 相關(guān)概念與理論

體積重建方法（VRM，Volume Reconstruction Method）將深度圖轉(zhuǎn)換成帶符號的距離場，通過疊加平均得到一個規(guī)則體素網(wǎng)格，并使用等值面多邊形或光線投射來生成隱式函數(shù)的零級集合，從中提取最終的重建表面，實現(xiàn)對三維物體的重建.

體積重建方法在體數(shù)據(jù)結(jié)構(gòu)中存儲一個隱式帶符號距離場（SDF，Signed Distance Field），這里假設(shè)輸入一組深度圖，且有一個規(guī)則的密集體素網(wǎng)格，深度傳感器在網(wǎng)格的中心點(diǎn)處被初始化，并使用ICP變量[28]來估計傳感器的剛性六自由度（6DoF，Six Degree-of-Freedom）.網(wǎng)格中的每個體素都包含兩個數(shù)值：帶符號距離和權(quán)值.對于單個的深度圖，傳感器均勻地掃描物體表面，剔除掉視錐體以外的體素，將全部體素的中心點(diǎn)投影到深度圖中，接著更新體數(shù)據(jù)結(jié)構(gòu)中的SDF值，實現(xiàn)深度圖到網(wǎng)格的數(shù)據(jù)融合.投影到同一像素點(diǎn)的所有體素成為深度樣本的貢獻(xiàn)分支.每個體素都存儲了一個從體素中心到觀測表面測量的帶符號距離值，其中帶符號距離為正值，表示觀測在前，反之為負(fù)，零值表示在觀測表面的邊界面.

為了降低計算成本，VRM方法引入了截斷式帶符號距離場（TSDF，Truncated Signed Distance Field）概念，僅在被觀測表面周圍的區(qū)域中存儲帶符號距離.該區(qū)域的尺寸可以調(diào)節(jié)，并將傳感器噪聲近似表示成一個基于深度的高斯方差.只有該區(qū)域內(nèi)的體素的TSDF值被加權(quán)平均后更新，從而獲得一個表面估計.最后，作為每個深度樣本的貢獻(xiàn)分支，但在截斷區(qū)域之外的體素被明確的標(biāo)記為自由空間.

VRM方法截斷表面周圍的SDF，存儲在規(guī)則體素網(wǎng)格中的大部分?jǐn)?shù)據(jù)被標(biāo)記為自由空間或不可見空間.因此問題的關(guān)鍵是：基于TSDF表示方法的稀疏特性建立一種存取高效的數(shù)據(jù)結(jié)構(gòu).

本文算法對傳統(tǒng)的體積重建方法進(jìn)行擴(kuò)充，通過建立一種快速有效的空間查找數(shù)據(jù)結(jié)構(gòu)，遞增地將噪聲深度圖融合到指定存儲單元，實現(xiàn)對隱含表面數(shù)據(jù)的存儲、訪問和更新，在保證重建質(zhì)量與重建速度的同時，實現(xiàn)了對三維曲面的大尺度重建.

2 本文算法概述

本文算法的核心是建立一個基于空間索引策略[29]的空間體素數(shù)據(jù)結(jié)構(gòu)，并在傳感器運(yùn)動過程中，使用GPU渲染管線實現(xiàn)對大尺度場景的實時重建.由于重建物體的幾何特性是未知的并且連續(xù)變化的，本文提出的空間體素數(shù)據(jù)結(jié)構(gòu)能夠?qū)SDF進(jìn)行動態(tài)存儲與更新，可以高效處理索引表的沖突問題，進(jìn)而實現(xiàn)可伸縮的體積重建過程.本文提出的空間體素數(shù)據(jù)結(jié)構(gòu)的核心功能主要有以下幾個方面：