鄭順義，何 源，徐 剛，王 辰，朱鋒博

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 立命館大學(xué)理工學(xué)部情報學(xué)科，日本 滋賀 520072

近年來，計算機(jī)視覺技術(shù)發(fā)展迅速，利用計算機(jī)視覺技術(shù)進(jìn)行三維重建已經(jīng)變得快速、高效和便捷，并在逆向工程、3D打印、工業(yè)檢測、文物保護(hù)等方面得到了廣泛的應(yīng)用[1]。在三維重建過程中，為了得到完整的三維模型，需要將不同角度獲取的數(shù)據(jù)配準(zhǔn)到統(tǒng)一的坐標(biāo)系下[2]。在實(shí)際應(yīng)用中，由于拼接誤差的存在，往往會導(dǎo)致重疊區(qū)域出現(xiàn)分層的現(xiàn)象，而且直接拼接得到的結(jié)果無法保證數(shù)據(jù)的均勻性。因此，對拼接好的數(shù)據(jù)作進(jìn)一步的融合處理具有十分重要的意義。

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

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

本文在借鑒Voxel Hashing的方法的基礎(chǔ)上，提出一種采用MD5[19]編碼的點(diǎn)云融合方法，有效降低了沖突次數(shù)，提高了數(shù)據(jù)索引、更新與插入的效率。并設(shè)計了一種新的內(nèi)存分配方式，可以在實(shí)時掃描的過程中自動分配內(nèi)存，有效增大了三維重建的可擴(kuò)展范圍。

1 三維點(diǎn)云數(shù)據(jù)實(shí)時管理方法

1.1 三維點(diǎn)云融合算法

TSDF的計算方法有很多[6,20-21]，如文獻(xiàn)[20]利用體素網(wǎng)格點(diǎn)與深度圖的特殊幾何關(guān)系解方程組求解有向距離，文獻(xiàn)[21]針對獲取的單幀深度數(shù)據(jù)為三維曲線的情況提出了相適應(yīng)的計算方法。由于本文研究的深度相機(jī)一次可以獲取一個面陣的深度圖，所以采用KinectFusion[6]的方法來計算有向距離場。

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

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

sdfi(x)=depthi(pic(x))-camz(x)

(1)

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

在文獻(xiàn)[6—7]中sdf的取值在閾值±t處被截斷了。這是因為距離非常遠(yuǎn)的格子對表面的重建是沒有作用的，而限制取值的范圍可以有效降低內(nèi)存的占用。這種sdfi(x)的變體被表示為tsdfi(x)?？梢杂扇缦鹿接嬎愕玫?/p>

(2)

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

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

TSDFi(x)=

(3)

Wi(x)=Wi-1(x)+wi(x)

(4)

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

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

1.2 數(shù)據(jù)結(jié)構(gòu)

本文采用了與Voxel Hashing相同的結(jié)構(gòu)體來存儲TSDF，結(jié)構(gòu)體定義如下：

struct voxel{

float tsdf;

uchar colorRGB[3];

uchar weight；}

每個結(jié)構(gòu)體占用8個字節(jié)，存儲了當(dāng)前體素的TSDF值、顏色和權(quán)重。將固定個數(shù)的體素(默認(rèn)為83個)合并到一起存儲，稱為一個體素塊(block)，存儲時以左下角點(diǎn)的坐標(biāo)定義整個體素塊的坐標(biāo)；體素塊內(nèi)所有的體素都按x-y-z的順序連續(xù)存儲，由體素塊的坐標(biāo)可以求出每個體素的坐標(biāo)。

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

struct HashEntry{

short position[3];

short offset;

int pointer;}

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

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

哈希表的鍵值由體素中心點(diǎn)的坐標(biāo)通過哈希函數(shù)計算得到，首先通過如下的公式將三維坐標(biāo)轉(zhuǎn)換為一個一維的索引

(5)

式中，Δ為當(dāng)前分辨率的大小，即一個體素的大小，通過簡單的移位運(yùn)算將三維坐標(biāo)轉(zhuǎn)換為一維索引，該索引可以表示x、y、z分別在±219范圍內(nèi)的所有坐標(biāo)值，滿足大多數(shù)的應(yīng)用場景。

計算好的一維索引通過MD5[19]轉(zhuǎn)化為哈希值。MD5具有抗沖突的特性，可以將任意長度的數(shù)據(jù)轉(zhuǎn)化為128位二進(jìn)制值，轉(zhuǎn)化的具體過程如下：

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

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

(3) 進(jìn)行四輪循環(huán)壓縮運(yùn)算，每一輪有16步，每步使用一個消息字wi，步函數(shù)為

Qi+1=Qi+1+

((Qi-3+fi(Qi,Qi-1,Qi-2)+wi+ti)<<

(6)

其中+是模32位加法，ti是一個常量，<<

(7)

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

1.3 內(nèi)存動態(tài)管理

Voxel Hashing的哈希表采用了預(yù)先分配內(nèi)存的方式，這樣雖然可以提高索引數(shù)據(jù)的效率，但是限制了三維重建場景的范圍。本文借鑒了C++11的STL(standard template library)標(biāo)準(zhǔn)模板庫中Hash map的內(nèi)存管理方式，實(shí)現(xiàn)了內(nèi)存的動態(tài)擴(kuò)展，當(dāng)預(yù)分配內(nèi)存已經(jīng)用滿，自動對哈希表進(jìn)行擴(kuò)容，擴(kuò)展了三維重建的場景范圍。

在哈希表結(jié)構(gòu)內(nèi)部增設(shè)了一個整型變量，用于實(shí)時更新已經(jīng)插入的元素個數(shù)，當(dāng)插入元素個數(shù)接近哈希表的大小時，停止向當(dāng)前哈希表插入元素，并分配一個同等大小的新哈希表，用新表的頭指向舊表的尾；然后對哈希表進(jìn)行重構(gòu)，設(shè)舊表的大小為n，那么新表的大小為2n，對之前所有插入的元素的哈希值模2n得到新的桶號，將之前舊表中的元素全部移動到擴(kuò)展后的新表中。重構(gòu)之后，可以對哈希表進(jìn)行插入操作。

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

圖2 重構(gòu)哈希表耗時統(tǒng)計Fig.2 Time for reconstitution of Hash table

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

在插入新元素時，為避免線程之間的寫入沖突，需要使用“原子鎖”對當(dāng)前寫入的數(shù)據(jù)進(jìn)行保護(hù)，直到當(dāng)前線程處理完畢，當(dāng)前的數(shù)據(jù)不可被其他線程操作。這樣既保證哈希表中沒有重復(fù)的數(shù)據(jù)，又保證了桶中的數(shù)據(jù)存儲的連續(xù)性。

在訪問表中的元素時，如果找到的目標(biāo)桶中有多個元素，則要遍歷桶中的所有元素，如果桶中最后一個元素指向了一個新的元素鏈表，則該鏈表也需要遍歷。雖然桶內(nèi)的元素在存儲時是連續(xù)存儲的，但刪除操作會導(dǎo)致元素變得碎片化，因此，當(dāng)遍歷出現(xiàn)空元素時，遍歷即可停止。

刪除元素跟插入元素類似，同樣需要遍歷桶和鏈表；如果刪除的元素是頭尾元素，則需要更新元素之間的指向關(guān)系，還需要對元素作“原子鎖”操作；如果刪除的是桶內(nèi)部的元素，則不需要“原子鎖”。

在更新TSDF時，首先用當(dāng)前幀的深度數(shù)據(jù)計算得到截斷區(qū)域范圍內(nèi)有效的體素塊，再根據(jù)哈希函數(shù)求出體素塊在哈希表中位置，如果數(shù)據(jù)是一個新插入的元素，則將其存入到一個實(shí)時維護(hù)的動態(tài)數(shù)組中，并將Hash entry中的pointer指向數(shù)組的對應(yīng)地址；如果數(shù)據(jù)索引到了表中已經(jīng)存在的元素，則更新元素指向的體素中的TSDF值。

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

1.4 等值面提取

在表面重建時，TSDF可以被認(rèn)為是一組等值面的集合。要提取的物體表面就是TSDF值為0處的等值面。通常在實(shí)時過程中，等值面是通過“光線跟蹤[24-25]”的方法來提取的。構(gòu)建好的TSDF也可以運(yùn)用Marching Cubes[26]方法來生成三角網(wǎng)表面數(shù)據(jù)。

“光線跟蹤”是從當(dāng)前相機(jī)位置的深度圖的每個像素發(fā)出的一條光線，投射到物體的體素格上，判斷沿著光線穿過的所有格子的符號，找到符號變化的位置(過零點(diǎn))，然后利用周圍的格子內(nèi)插得到過零點(diǎn)的坐標(biāo)。

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

(8)

圖3 三線性插值采樣點(diǎn)示意Fig.3 Sample points of trilinear interpolation

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

(9)

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

ρ(u,v,w)=(1-u)(1-v)(1-w)ρ000+

(1-u)(1-v)wρ001+

(1-u)v(1-w)ρ010+

u(1-v)(1-w)ρ100+

u(1-v)wρ101+(1-u)vwρ011+

uv(1-w)ρ110+uvwρ111

(10)

1.5 GPU與主機(jī)內(nèi)存的傳輸與調(diào)度

由于哈希表是在GPU上實(shí)現(xiàn)的，當(dāng)數(shù)據(jù)量較大時，所有數(shù)據(jù)是無法都存儲在顯存中的，而且在重建過程中當(dāng)前視圖也不需要顯示全部數(shù)據(jù)。“out-of-core[23]”方法是一種經(jīng)常被用于海量三維數(shù)據(jù)管理的方法，本文借鑒“out-of-core”方法，建立主機(jī)與GPU之間的雙向流。在相機(jī)移動時，

用當(dāng)前相機(jī)位置姿態(tài)確定的視錐體判斷體素格，落在視錐體外的格子被釋放，并將其壓入一個包含2幀緩存的隊列中，每當(dāng)有新數(shù)據(jù)進(jìn)入隊列中，則把上一幀數(shù)據(jù)壓出隊列，將其存入主機(jī)內(nèi)存；在主機(jī)端，這些格子的數(shù)據(jù)塊同樣以隊列的形式存儲，以方便查找。當(dāng)數(shù)據(jù)塊落入視錐體時，則將這部分?jǐn)?shù)據(jù)傳入緩存中，取出上一幀數(shù)據(jù)將其存入GPU的哈希表中。在哈希表中插入或刪除數(shù)據(jù)的方法已經(jīng)在2.3節(jié)中描述。

2 試驗結(jié)果與分析

為了驗證本文所提出的改進(jìn)方法的有效性和可行性，用Kinect2.0作為深度數(shù)據(jù)采集設(shè)備(彩色相機(jī)分辨率：1920×1080，深度相機(jī)分辨率：512×424，單幀點(diǎn)云數(shù)：2.11×105)，測試了不同場景下，在不同配置等級的計算機(jī)設(shè)備上，本文方法的幀率。

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

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

表1 不同計算機(jī)設(shè)備算法平均幀率比較

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

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

表2本文算法與VoxelHashing算法的平均幀率比較

Tab.2 Comparison of frame rate for the proposed algorithm and Voxel Hashing 幀/s

3 結(jié) 論

本文提出了一種基于Hash map的三維點(diǎn)云數(shù)據(jù)實(shí)時管理方法，詳細(xì)介紹了算法使用的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)管理和點(diǎn)云融合的具體實(shí)現(xiàn)過程。通過在不同配置的計算機(jī)上試驗，證明了算法的可行性和有效性，對于單幀數(shù)據(jù)量在2.1×105左右的點(diǎn)云數(shù)據(jù)，算法幀率穩(wěn)定在60 幀/s以上，達(dá)到實(shí)時性的幀率要求，實(shí)現(xiàn)了高效地數(shù)據(jù)插入、更新和索引，滿足了三維構(gòu)像中三維點(diǎn)云數(shù)據(jù)高效管理的要求。

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

參考文獻(xiàn)：

[1] 鄭順義, 周漾, 黃榮永, 等. 館藏文物三維測量與重建方法研究[J]. 測繪科學(xué), 2014, 39(7): 76-79.

ZHENG Shunyi, ZHOU Yang, HUANG Rongyong, et al. A Method of 3D Measurement and Reconstruction for Cultural Relics in Museums[J]. Science of Surveying and Mapping, 2014, 39(7): 76-79.

[2] 翟瑞芳, 張劍清. 基于激光掃描儀的點(diǎn)云模型的自動拼接[J]. 地理空間信息, 2004, 2(6): 37-39.

ZHAI Ruifang, ZHANG Jianqing. Automatic Registration of Point Clouds Based on Laser Scanner[J]. Geospatial Information, 2004, 2(6): 37-39.

[3] RUSINKIEWICZ S, HALL-HOLT O, LEVOY M. Real-time 3D Model Acquisition[J]. ACM Transactions on Graphics (TOG), 2002, 21(3): 438-446.

[4] ROSSIGNAC J, BORREL P. Multi-resolution 3D Approximations for Rendering Complex Scenes[C]∥FALCIDIENO B, KUNII T L. Modeling in Computer Graphics. Berlin, Heidelberg: Springer, 1993: 455-465.

[5] 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. [S.l.]: ACM, 1996: 303-312.

[6] NEWCOMBE R A, IZADI S, HILLIGES O, et al. Kinect-Fusion: Real-time Dense Surface Mapping and Tracking[C]∥Proceedings of the 10th IEEE International Symposium on Mixed and Augmented Reality. Basel, Switzerland: IEEE, 2011: 127-136.

[7] 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. Santa Barbara, California: ACM, 2011: 559-568.

[8] 譚歆. KinectFusion三維重建的再優(yōu)化[D]. 杭州: 浙江大學(xué), 2015.

TAN Xin. Global Optimization for 3D Reconstruction Based on KinectFusion[D]. Hangzhou: Zhejiang University,

2015.

[9] WHELAN T, MCDONALD J, KAESS M, et al. Kintinuous: Spatially Extended Kinectfusion[R]. Cambridge: MIT, 2012.

[10] WHELAN T, JOHANNSSON H, KAESS M, et al. Robust Real-time Visual Odometry for Dense RGB-D Mapping[C]∥Proceedings of 2013 IEEE International Conference on Robotics and Automation. Karlsruhe, Germany: IEEE, 2013: 5724-5731.

[11] ROTH H, VONA M. Moving Volume KinectFusion[C]∥Proceedings of the British Machine Vision Conference. Boston, MA: BMVA Press, 2012: 1-11.

[12] ZENG Ming, ZHAO Fukai, ZHENG Jiaxiang, et al. Octree-based Fusion for Realtime 3D Reconstruction[J]. Graphical Models, 2013, 75(3): 126-136.

[13] ZENG Ming, ZHAO Fukai, ZHENG Jiaxiang, et al. A Memory-efficient Kinectfusion Using Octree[M]∥Proceedings of the 1st International Conference on Computational Visual Media. Beijing, China: Springer, 2012: 234-241.

[14] CHEN Jiawen, BAUTEMBACH D, IZADI S. Scalable Real-time Volumetric Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(4): 113.

[16] NIEβNER M, ZOLLH?FER M, IZADI S, et al. Real-time 3D Reconstruction at Scale Using Voxel Hashing[J]. ACM Transactions on Graphics (TOG), 2013, 32(6): 169.

[17] KLINGENSMITH M, DRYANOVSKI I, SRINIVASA S, et al. Chisel: Real Time Large Scale 3D Reconstruction Onboard a Mobile Device Using Spatially-Hashed Signed Distance Fields[C]∥Proceedings of Robotics: Science and Systems. Rome, Italy: [s.n.], 2015: 4.

[18] TESCHNER M, HEIDELBERGER B, MüLLER M, et al. Optimized Spatial Hashing for Collision Detection of Deformable Objects[C]∥Proceedings of the 8th Workshop on Vision, Modeling, and Visualization. Munich, Germany: AKA, 2003: 47-54.

[19] RIVEST R. The MD5 Message-digest Algorithm[R]. Request for Comments 1321 Cambridge：MIT Laboratory for Computer Science and RSA Data Security, Inc, 1992.

[20] TUBIC D, HéBERT P, LAURENDEAU D. A Volumetric Approach for Interactive 3D Modeling[J]. Computer Vision and Image Understanding, 2003, 92(1): 56-77.

[22] WERNER D, AL-HAMADI A, WERNER P. Truncated Signed Distance Function: Experiments on Voxel Size[C]∥Proceedings of the 11th International Conference Image Analysis and Recognition. Cham: Springer, 2014: 357-364.

[23] 王攀. 基于Out-of-Core的海量數(shù)據(jù)等值面繪制技術(shù)研究與實(shí)現(xiàn)[D]. 長沙: 國防科學(xué)技術(shù)大學(xué), 2008.

WANG Pan. Research on Isosurface Extraction of Large Scale Datasets With Out-of-core Method[D]. Changsha: National University of Defense Technology, 2008.

[25] ZWICKER M, PFISTER H, VAN BAAR J, et al. Surface splatting[C]∥Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. Los Angeles: ACM, 2001: 371-378.

[26] LORENSEN W E, CLINE H E. Marching Cubes: A High Resolution 3D Surface Construction Algorithm[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 163-169.