論文推薦| 鄭順義:三維點雲數據實時管理的Hash map方法

三維點雲數據實時管理的Hash map方法

鄭順義1 , 何源1 , 徐剛2 , 王辰1 , 朱鋒博1     

1. 武漢大學遙感信息工程學院, 湖北 武漢 430079; 
2. 立命館大學理工學部情報學科, 日本 滋賀 520072

收稿日期：2017-11-06；修回日期：2018-04-08

基金項目：國家自然科學基金（41671452；41701532）；中央高校基本科研業務費專項資金（2042016kf0012）；中國博士後科學基金（2017M612510）

第一作者簡介：鄭順義(1973-), 男, 博士, 教授, 博士生導師, 主要從事數字攝影測量與計算機視覺研究。E-mail: [e-mail]

通信作者：何源, E-mail：[e-mail]

摘要：本文基於機器視覺探討數字攝影測量三維構像下的智能數據處理要素之一：海量點雲高效管理技術，提出了一種基於GPU的hash map三維點雲數據組織的改進算法，算法可以高效地完成數據的動態插入、更新和索引，而不受數據規模限制。同時，通過傳感器位置姿態估計當前活動範圍，進行主機與GPU的數據交換，保證了GPU的低內存佔用率。在搭載不同等級顯卡（GTX960、GTX1050、GTX1060）的計算機設備上試驗，本文算法均可以達到60 fps以上的幀率（單幀處理點雲數：2.11×105），證明算法滿足了三維構像中三維點雲數據高效管理的要求。

關鍵詞：三維點雲    數據組織    哈希表    圖形處理器    並行計算    

Hash Map Method of 3D Point Cloud Data for Real-time Organizing

ZHENG Shunyi1 , HE Yuan1 , XU Gang2 , WANG Chen1 , ZHU Fengbo1     

Abstract: In this paper, one of the key elements of intelligent data processing in digital photogrammetry is discussed based on machine vision:efficient management technology of massive point cloud, an improved algorithm for hash mapping 3D data on GPU is proposed.The algorithm can efficiently perform dynamic insertion, update and indexing of data without the limitation of data scale.We applied the algorithm to TSDF (truncated signed distance field) algorithm for point cloud fusion, which can reduce the noise of single frame and the data registration error between different frames in a very efficient way.Currently, most of the data structures of point cloud fusion algorithms are regular or hierarchical grid data structures, so the object bounding boxes should be specified in advance.Moreover, the hierarchical data structure is complex and hard to parallelization.Therefore, the requirements of dynamic scalability, updating and indexing data of real-time 3D reconstruction cannot be satisfied.This paper exploited hash map to manage 3D data.At the same time, the current active region could be estimated with sensor motion to exchange data between host and GPU, keeping low memory utilization of GPU.In the experiments on different levels of graphics cards(GTX960, GTX1050, GTX1060), the algorithm can satisfy the real-time frame rate requirements(60 fps, 2.11×105 points per frame), so it meets the requirement of efficient management of 3D point cloud data in three-dimensional imaging.

Key words: 3D point cloud     data organization     hash table     graphics processing unit (GPU)     parallel computing    

近年來，計算機視覺技術發展迅速，利用計算機視覺技術進行三維重建已經變得快速、高效和便捷，並在逆向工程、3D列印、工業檢測、文物保護等方面得到了廣泛的應用[1]。在三維重建過程中，為了得到完整的三維模型，需要將不同角度獲取的數據配準到統一的坐標系下[2]。在實際應用中，由於拼接誤差的存在，往往會導致重疊區域出現分層的現象，而且直接拼接得到的結果無法保證數據的均勻性。因此，對拼接好的數據作進一步的融合處理具有十分重要的意義。

文獻[3]中提出的融合方法，是將空間劃分成固定大小的體素格，將落入同一個體素格的所有點求加權平均值作為融合後的點[4]；這種方法保證了數據的均勻性，但是無法降低由於拼接誤差帶來的噪聲。文獻[5]提出了截斷有向距離場(truncated signed distance field, TSDF)的方法，該方法利用有向距離提取等值面來得到表面重建結果。這種算法可以降低單幀數據的噪聲、減小不同幀數據之間的拼接誤差。文獻[6-7]借鑑了文獻[5]的方法，提出了KinectFusion算法，主要思想是在GPU顯存中建立一個固定大小的立方體(volume)[8]，將立方體劃分為體素格，在體素格中構建TSDF；雖然算法速度較快，但是由於立方體的大小是固定的，因此無法完成大場景的三維重建。

針對KinectFusion算法的局限性，很多論文提出了改進[9-17]。文獻[9-11]提出了立方體隨相機移動的方法以實現空間的擴展，可是在相機移動時，移出當前視野範圍的體素格被清空，如果後續還需要這部分格子，則已經無法恢復。目前最新的研究主要是通過改變數據結構來壓縮立方體佔用的空間，其中文獻[12-15]都用到了樹形數據結構，如八叉樹、KD樹[15]等，但是這些算法時間複雜度較高，無法滿足實時性的要求。文獻[16-17]提出了用Voxel Hashing[18]的方法來存儲TSDF，由於哈希表查詢、插入、刪除的時間複雜度為常數級O(1)，因此該方法不僅有效降低了內存容量的佔用而且具有較高的速度優勢。但該方法所用的哈希函數發生衝突的概率較高，當衝突次數較多時會嚴重拖慢算法的效率，同時增加了內存溢出的風險，而且Voxel Hashing[18]方法仍然需要一次性分配固定大小的內存容量，限制了三維重建的可擴展範圍。

本文在借鑑Voxel Hashing的方法的基礎上，提出一種採用MD5[19]編碼的點雲融合方法，有效降低了衝突次數，提高了數據索引、更新與插入的效率。並設計了一種新的內存分配方式，可以在實時掃描的過程中自動分配內存，有效增大了三維重建的可擴展範圍。

1 三維點雲數據實時管理方法1.1 三維點雲融合算法

TSDF的計算方法有很多[6, 20-21]，如文獻[20]利用體素網格點與深度圖的特殊幾何關係解方程組求解有向距離，文獻[21]針對獲取的單幀深度數據為三維曲線的情況提出了相適應的計算方法。由於本文研究的深度相機一次可以獲取一個面陣的深度圖，所以採用KinectFusion[6]的方法來計算有向距離場。

首先，將三維空間劃分為相等大小的體素(voxel)，體素x的位置由其中心點決定。每個體素中存儲了兩個值[22]，有向距離sdfi(x)和權重wi(x)。sdfi(x)表示沿著當前觀測方向體素格中心點與最近的物體表面的有向距離。在物體表面之前(物體外部)距離被定義為正值，在物體表面之後(物體內部)為負值。wi(x)權重用來評價當前sdfi(x)值的可靠性。下標i表示第i次的觀測值。

sdfi(x)的計算方法可以通過如下公式表示

 (1)

式中，pic(x)是體素中心點在深度圖中的投影；因此depthi(pic(x))是相機沿著穿過x的觀測光線到最近的物體表面點p的深度。相應的，camz(x)是體素與相機沿著主光軸方向的距離。所以，最終計算的sdfi(x)也是一個沿著主光軸方向的距離。

在文獻[6-7]中sdf的取值在閾值±t處被截斷了。這是因為距離非常遠的格子對表面的重建是沒有作用的，而限制取值的範圍可以有效降低內存的佔用。這種sdfi(x)的變體被表示為tsdfi(x)。可以由如下公式計算得到

 (2)

圖 1表示了體素格的tsdfi(x)在物體表面的分布，tsdfi(x)的值用不同深度的顏色進行區分，在視場範圍外的tsdfi(x)格子表示為白色。體素x的sdf值由物體上的點P的深度與體素x到相機的距離camz(x)相減求得。

圖 1 TSDF計算原理Fig. 1 Principle of TSDF

圖選項

將每次觀測到的tsdfi(x)值整合到一個TSDF中，整合的過程是通過加權平均實現的。具體方法如下

 (3)

 (4)

TSDFi(x)表示所有觀測值tsdfj(x)(1≤j≤ i)的集合，Wi(x)是評價TSDFi(x)的可靠性的權重。體素格的初值TSDF0(x)=0和W0(x)=0。每次獲得的新觀測值都通過以上的公式整合到每個體素x中。每次需要更新的體素的新權重wi(x)=1，而對於超出相機視場範圍的所有體素的權重wi(x)=0。通過上述方法對於每次測量的TSDF觀測值進行動態的加權平均。

1.2 數據結構

本文採用了與Voxel Hashing相同的結構體來存儲TSDF，結構體定義如下：

struct voxel{

float tsdf;

uchar colorRGB[3];

uchar weight；}

每個結構體佔用8個字節，存儲了當前體素的TSDF值、顏色和權重。將固定個數的體素(默認為83個)合併到一起存儲，稱為一個體素塊(block)，存儲時以左下角點的坐標定義整個體素塊的坐標；體素塊內所有的體素都按x-y-z的順序連續存儲，由體素塊的坐標可以求出每個體素的坐標。

所有的體素塊通過一個Hash table(哈希表)來管理，哈希表的底層可以被認為是一個大小為n的數組，數組的每一項指向一個被稱為bucket(桶)的類似於鍊表的結構。哈希表中每個元素存儲的結構體如下：

struct HashEntry{

short position[3];

short offset;

int pointer; }

其中，pointer一個是指向體素塊的地址的標記；position存儲了該體素塊的坐標，offset是一個bucket偏移量標記，是為了解決哈希衝突而設計的。

在插入數據時，由哈希函數計算出哈希值，用哈希值模n獲取到桶號Hi，即該數據在哈希表中的地址，將數據存入該地址；當發生數據衝突(不同的數據落入同一個桶內)時，該元素被存入桶中下一個空缺的位置。為提高尋址的效率，桶的大小是固定的，但是這樣無法避免桶溢出現象的發生，通過一種類似於鍊表的機制可以解決這個問題。當溢出發生時，這個桶的最後一個元素被預留出來，用這個元素的offset欄位來指向哈希表中一個新的桶，從該位置開始仍然按照順序存儲每個溢出的元素。鍊表之間的相互關係都通過offset欄位來指示。在確定鍊表的新地址時需要對哈希表進行線性地搜索，來找到一個空的桶存儲新元素。

哈希表的鍵值由體素中心點的坐標通過哈希函數計算得到，首先通過如下的公式將三維坐標轉換為一個一維的索引

 (5)

式中，Δ為當前解析度的大小，即一個體素的大小，通過簡單的移位運算將三維坐標轉換為一維索引，該索引可以表示x、y、z分別在±219範圍內的所有坐標值，滿足大多數的應用場景。

計算好的一維索引通過MD5[19]轉化為哈希值。MD5具有抗衝突的特性，可以將任意長度的數據轉化為128位二進位值，轉化的具體過程如下：

(1) 在數據後面添補一個1和若干0，使字節長度模512得448，數據在被添補前的長度表示在最後的64位，添補後的數據長度是512的整數倍。

(2) 以512位為分組處理添補後的數據，每個組又分為16個32位子塊，使用4個32位寄存器Qt，Qt-1，Qt-2，Qt-3循環處理子塊；用四個連結變量作為參數初始化MD5，這4個變量分別為：a=0x0x67452301，b=0xefcdab89，c=0x98badcfe, d=0x10325476。

(3) 進行四輪循環壓縮運算，每一輪有16步，每步使用一個消息字wi，步函數為

 (6)

其中+是模32位加法，ti是一個常量，＜＜＜si表示循環左移si位；每一輪的布爾函數如下

 (7)

(4) 將4個32位子塊級聯得到一個128位值，即最終的哈希值。

1.3 內存動態管理

Voxel Hashing的哈希表採用了預先分配內存的方式，這樣雖然可以提高索引數據的效率，但是限制了三維重建場景的範圍。本文借鑑了C++ 11的STL(standard template library)標準模板庫中Hash map的內存管理方式，實現了內存的動態擴展，當預分配內存已經用滿，自動對哈希表進行擴容，擴展了三維重建的場景範圍。

在哈希表結構內部增設了一個整型變量，用於實時更新已經插入的元素個數，當插入元素個數接近哈希表的大小時，停止向當前哈希表插入元素，並分配一個同等大小的新哈希表，用新表的頭指向舊錶的尾；然後對哈希表進行重構，設舊錶的大小為n，那麼新表的大小為2n，對之前所有插入的元素的哈希值模2n得到新的桶號，將之前舊錶中的元素全部移動到擴展後的新表中。重構之後，可以對哈希表進行插入操作。

重構哈希表的時間與哈希表的大小呈正相關，如圖 2所示，元素個數增加，哈希表重構的耗時增加。當預分配的哈希表較小時，需要進行多次哈希表的擴展，每次擴展哈希表都要產生一次重構操作，因此，預分配哈希表的大小合理可以減少重構的次數，提高插入數據的效率。影響哈希表大小的主要是體素格的個數，場景越大三維重建需要的體素格的數量越多；場景大小不變，劃分的體素格越小(即解析度越高)，體素格的數量也越多，因此，預分配的哈希表的大小需要根據三維重建場景的大小和解析度來確定。

圖 2 重構哈希表耗時統計Fig. 2 Time for reconstitution of Hash table

圖選項

由於本文採用了「out-of-core[23]」方法(見2.5節)進行GPU與主機的數據交換，保存在GPU中哈希表的實際大小由當前相機的視錐體來確定，落入視錐體中的體素格被傳入GPU的顯存中，落在視錐體之外的格子在GPU上釋放並傳入主機內存中。因此，預分配的哈希表的大小如果可以滿足當前視錐體中場景的需要，那麼就不需要對哈希表進行重構。以kinect深度相機為例，深度識別範圍為0~4 m，水平方向視場角為70°，垂直方向視場角為60°，可以計算出視錐體的體積約為34.50 m3。設體素的大小為4 mm，則填充整個視錐體需要約5.39×108個體素。由於哈希表的每個元素指向的是一個由512個體素構成的體素塊，所以根據以上的測算哈希表的大小應為106。在實際中三維場景不可能填滿整個視錐體，因此預分配4.0×105個元素的哈希表就可以滿足大部分實際三維場景的需要。

在插入新元素時，為避免線程之間的寫入衝突，需要使用「原子鎖」對當前寫入的數據進行保護，直到當前線程處理完畢，當前的數據不可被其他線程操作。這樣既保證哈希表中沒有重複的數據，又保證了桶中的數據存儲的連續性。

在訪問表中的元素時，如果找到的目標桶中有多個元素，則要遍歷桶中的所有元素，如果桶中最後一個元素指向了一個新的元素鍊表，則該鍊表也需要遍歷。雖然桶內的元素在存儲時是連續存儲的，但刪除操作會導致元素變得碎片化，因此，當遍歷出現空元素時，遍歷即可停止。

刪除元素跟插入元素類似，同樣需要遍歷桶和鍊表；如果刪除的元素是頭尾元素，則需要更新元素之間的指向關係，還需要對元素作「原子鎖」操作；如果刪除的是桶內部的元素，則不需要「原子鎖」。

在更新TSDF時，首先用當前幀的深度數據計算得到截斷區域範圍內有效的體素塊，再根據哈希函數求出體素塊在哈希表中位置，如果數據是一個新插入的元素，則將其存入到一個實時維護的動態數組中，並將Hash entry中的pointer指向數組的對應地址；如果數據索引到了表中已經存在的元素，則更新元素指向的體素中的TSDF值。

由於噪聲和拼接誤差的存在，往往會存在一些格子存儲了難以被重複採集到的離群點，這些點會影響表面重建的質量，因此，清理離群點是十分必要的，清理可以通過判斷TSDF的絕對值和權重來完成。當採集較長時間，權重一直較小，說明該點一直沒有被採集到，但是也不能完全就此斷定該點為離群點，因為物體的一些縫隙、邊緣往往也很難被採集。這就需要通過TSDF的絕對值來進一步判斷，當TSDF絕對值較大，說明該點距離物體表面較遠，為離群點。由於體素格數據在內存中是連續存儲的，在清理離群點時，如果直接對數組進行刪除操作，則需要大量地進行內存的移位操作，非常影響效率，所以，對離群點設定一個無效標記，使其不參與實時渲染和最終結果的生成。這樣做既保證了數據質量，又不影響效率。

1.4 等值面提取

在表面重建時，TSDF可以被認為是一組等值面的集合。要提取的物體表面就是TSDF值為0處的等值面。通常在實時過程中，等值面是通過「光線跟蹤[24-25]」的方法來提取的。構建好的TSDF也可以運用Marching Cubes[26]方法來生成三角網表面數據。

「光線跟蹤」是從當前相機位置的深度圖的每個像素髮出的一條光線，投射到物體的體素格上，判斷沿著光線穿過的所有格子的符號，找到符號變化的位置(過零點)，然後利用周圍的格子內插得到過零點的坐標。

三線性插值是一種常用的插值方法，設待插值p(x, y, z)為如圖 3所示的立方體中的任意一點，插值所需要的8個角點上的值可以表示為

 (8)

圖 3 三線性插值採樣點示意Fig. 3 Sample points of trilinear interpolation

圖選項

插值權重u、v、w∈[0, 1]，可以表示為

 (9)

那麼點p的值ρ(u, v, w)可以通過下面的方法獲得

 (10)

1.5 GPU與主機內存的傳輸與調度

由於哈希表是在GPU上實現的，當數據量較大時，所有數據是無法都存儲在顯存中的，而且在重建過程中當前視圖也不需要顯示全部數據。「out-of-core[23]」方法是一種經常被用於海量三維數據管理的方法，本文借鑑「out-of-core」方法，建立主機與GPU之間的雙向流。在相機移動時，用當前相機位置姿態確定的視錐體判斷體素格，落在視錐體外的格子被釋放，並將其壓入一個包含2幀緩存的隊列中，每當有新數據進入隊列中，則把上一幀數據壓出隊列，將其存入主機內存；在主機端，這些格子的數據塊同樣以隊列的形式存儲，以方便查找。當數據塊落入視錐體時，則將這部分數據傳入緩存中，取出上一幀數據將其存入GPU的哈希表中。在哈希表中插入或刪除數據的方法已經在2.3節中描述。

2 試驗結果與分析

為了驗證本文所提出的改進方法的有效性和可行性，用Kinect2.0作為深度數據採集設備(彩色相機解析度：1920×1080，深度相機解析度：512×424，單幀點雲數：2.11×105)，測試了不同場景下，在不同配置等級的計算機設備上，本文方法的幀率。

圖 4為不同場景的三維重建結果，場景1為一張辦公桌及周圍的環境(大致範圍1.4 m×1.2 m×1.6 m)，掃描時長4 min，融合的體素大小(即解析度)為4 mm，最終獲得模型數據共有3 445 256個面。從結果可以看出該解析度下細節保留較好，植物葉片可以清晰地辨認。數據實際佔用體素格2.01×107個，使用內存153 MB左右。如果按照KinectFusion的方法，按照包圍整個場景大小的立方體分配內存，則需要4.2×107個體素格, 需要佔用內存320 MB左右，因此，使用Voxel Hashing方法節省了約52.19%的內存。場景2為一間辦公室的一側(9.0 m×1.2 m×1.6 m)，掃描時長8 min，解析度為6 mm，得到的模型數據共有6 534 607個面，場景範圍較大，佔用體素格2.24×107個，使用內存170 MB左右。如果用KinectFusion的方法則需要8.0×107個體素格，約佔用內存610 MB，Voxel Hashing節省了大約72.04%左右的內存。

圖 4 本文算法不同場景三維重建效果Fig. 4 Output from the proposed algorithm of different test scenes

圖選項

表 1比較了在不同計算機設備上，同一場景(圖 4(b))不同解析度，算法的執行效率。可以看出，解析度對幀率的影響很大，這是因為解析度提高每一幀需要處理的體素增多；同時顯卡性能對幀率的影響也比較大，在性能相對較弱的GTX1050上，算法速度最慢，但是幀率都保持在了60幀/s以上，滿足了實時性的要求。從本次試驗選用的硬體配置可以看出，算法對硬體的要求並不高，消費級設備即可滿足需求。

表 1 不同計算機設備算法平均幀率比較Tab. 1 Frame rate on different computers

幀/s設備解析度/mm6810Inter Core i7 2.8 GHz 16 GB RAM，NVIDIA GeoForce GTX105071.490.9141.5Inter Core i7 3.6 GHz 16 GB RAM，NVIDIA GeoForce GTX96078.298.6150.1Inter Core i7 3.6 GHz 16 GB RAM，NVIDIA GeoForce GTX106084.6101.3161.3

表選項

表 2比較了同一場景(圖 4(b))不同解析度，在同樣的計算機設備(Inter Core i7 2.8 GHz 16 GB RAM NVIDIA GeoForce GTX1050)上，本文提出的改進算法與Voxel Hashing原算法的平均幀率，可以看出本文的算法對原算法平均貢獻了20%左右的速率提升，改進效果比較明顯。

表 2 本文算法與Voxel Hashing算法的平均幀率比較Tab. 2 Comparison of frame rate for the proposed algorithm and Voxel Hashing

幀/s算法解析度/mm6810本文算法71.490.9141.5Voxel Hashing算法58.871.494.3

表選項

3 結論

本文提出了一種基於Hash map的三維點雲數據實時管理方法，詳細介紹了算法使用的數據結構、數據管理和點雲融合的具體實現過程。通過在不同配置的計算機上試驗，證明了算法的可行性和有效性，對於單幀數據量在2.1×105左右的點雲數據，算法幀率穩定在60幀/s以上，達到實時性的幀率要求，實現了高效地數據插入、更新和索引，滿足了三維構像中三維點雲數據高效管理的要求。

相比於Voxel Hashing，本文採用MD5方法編碼哈希值，有效降低了衝突次數，從試驗結果中可以看出本文的算法可以帶來20%左右的速率提升。本文還設計了一種新的內存分配方式，可以在實時掃描的過程中自動分配內存，提高了算法的實用性。本文提出的內存管理方式，雖然較Voxel Hashing更為靈活更加適合實際的三維掃描過程，但缺點在於內存重新分配時需要對哈希表進行重構，在實時掃描過程中會表現為一次較長時間的卡頓，用戶體驗感較差。因此，未來的研究側重於如何減少哈希表重構的耗時，以進一步提升算法的性能。

【引文格式】鄭順義, 何源, 徐剛, 等. 三維點雲數據實時管理的Hash map方法[J]. 測繪學報，2018，47(6)：825-832. DOI: 10.11947/j.AGCS.2018.20170619

院士論壇︱李德仁院士：展望大數據時代的地球空間信息學（論文版）

學術前沿| 龔健雅院士：攝影測量與深度學習

李德仁院士：老師教我做人做學問

院士論壇| 楊元喜：微PNT與綜合PNT

院士論壇| 楊元喜：我國海洋大地測量基準與海洋導航技術研究進展與展望（英文版）

院士論壇| 龔健雅：高解析度光學衛星遙感影像高精度無地面控制精確處理的理論與方法

院士論壇 | 龔健雅:中國高解析度對地觀測系統的成長與突破

書訊 | 楊元喜院士：自適應動態導航定位（第二版）

李德仁院士論夜光遙感數據挖掘

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | [e-mail]

微信公眾號中搜索「測繪學報」，關注我們，長按上圖二維碼，關注學術前沿動態。

歡迎加入《測繪學報》作者QQ群： 297834524

進群請備註：姓名+單位+稿件編號