胡敏捷 謝 洪

（1.上海船舶研究設(shè)計(jì)院，上海201203；2.武漢大學(xué)，湖北 武漢400439）

0 前言

隨著計(jì)算機(jī)技術(shù)飛速進(jìn)步，基于矢量圖形信息的三維可視化和基于實(shí)景影像信息的三維可視化技術(shù)應(yīng)用越來越廣泛。激光掃描技術(shù)作為一種三維空間信息的實(shí)時(shí)采集手段，以日新月異的速度發(fā)展［1］。目前，相位式激光掃描儀的掃描速度可達(dá)每秒近百萬點(diǎn)，一次掃描可以采集被測(cè)對(duì)象表面上億點(diǎn)的三維空間坐標(biāo)，形成GB級(jí)的點(diǎn)云數(shù)據(jù)。因此，必須建立有效的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)快速索引機(jī)制，才能開展后續(xù)的數(shù)據(jù)處理分析。

八叉樹（Octree）是一種用于描述三維空間的數(shù)狀數(shù)據(jù)結(jié)構(gòu)。這種方法即可以看成是四叉樹方法在三維空間的推廣，也可以認(rèn)為是用三維體素陣列表示形體方法的一種改進(jìn)。八叉樹的每個(gè)節(jié)點(diǎn)表示正方體的體積元素，每個(gè)節(jié)點(diǎn)有八個(gè)子節(jié)點(diǎn)，將八個(gè)子節(jié)點(diǎn)所表示的體積元素加在一起就等于父節(jié)點(diǎn)的體積。

1 數(shù)據(jù)管理

1.1 建立點(diǎn)云數(shù)據(jù)八叉樹索引

在建立八叉樹的過程中，八叉樹的根節(jié)點(diǎn)為激光點(diǎn)云數(shù)據(jù)的外接包圍盒，從根節(jié)點(diǎn)開始進(jìn)行空間八方向劃分，形成八個(gè)子節(jié)點(diǎn)立方體，其中一部分含有點(diǎn)，一部分不包含點(diǎn)。不包含點(diǎn)的立方體成為葉節(jié)點(diǎn)，不再繼續(xù)劃分，含有點(diǎn)的立方體成為新的父節(jié)點(diǎn)繼續(xù)劃分，直到所有立方體中包含的點(diǎn)數(shù)小于設(shè)定閾值。在基于數(shù)據(jù)庫(kù)的點(diǎn)云管理時(shí)，每一個(gè)目標(biāo)所對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)作為一個(gè)表空間，八叉樹的每一層節(jié)點(diǎn)數(shù)據(jù)均作為一個(gè)單獨(dú)的表存儲(chǔ)。根據(jù)Morton編碼在表空間中建立對(duì)應(yīng)數(shù)據(jù)的索引表實(shí)現(xiàn)快速訪問。利用數(shù)據(jù)庫(kù)的二進(jìn)制數(shù)據(jù)類型來存儲(chǔ)每層節(jié)點(diǎn)中的點(diǎn)云數(shù)據(jù)，以便實(shí)現(xiàn)多分辨率的分層數(shù)據(jù)的存儲(chǔ)和快速訪問。在基于硬盤文件的管理時(shí)，同樣可以類似于數(shù)據(jù)庫(kù)的存儲(chǔ)方式來采用多文件的方式存儲(chǔ)八叉樹的各層節(jié)點(diǎn)數(shù)據(jù)。點(diǎn)云八叉樹的索引如圖1所示。

圖1 點(diǎn)云八叉樹索引

1.2 海量點(diǎn)云數(shù)據(jù)管理和動(dòng)態(tài)更新

圖2 量化格網(wǎng)的基本結(jié)構(gòu)

針對(duì)點(diǎn)云數(shù)據(jù)的管理，根據(jù)點(diǎn)云數(shù)據(jù)文件的大小主要提供三種不同的管理方式：①對(duì)于點(diǎn)云數(shù)據(jù)量處于幾百GB級(jí)別的數(shù)據(jù)，采用基于Oracle數(shù)據(jù)庫(kù)的管理方式，對(duì)原始點(diǎn)云數(shù)據(jù)建立八叉樹索引并存入數(shù)據(jù)庫(kù)，并根據(jù)八叉樹索引實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)在瀏覽、量測(cè)等操作時(shí)的數(shù)據(jù)動(dòng)態(tài)調(diào)度；②對(duì)于點(diǎn)云數(shù)據(jù)量處于幾百M(fèi)B到幾十GB級(jí)的數(shù)據(jù)，可采用直接基于硬盤外存（out of core）的八叉樹索引多文件（multifile）點(diǎn)云管理方式，并通過動(dòng)態(tài)調(diào)度引擎（Dynamic Swap Engine）來進(jìn)行八叉樹節(jié)點(diǎn)的動(dòng)態(tài)調(diào)度，以實(shí)現(xiàn)點(diǎn)云的多層次細(xì)節(jié)處理；③對(duì)于點(diǎn)云數(shù)據(jù)量為幾十MB的數(shù)據(jù)，可直接采用基于內(nèi)存（in-core）的管理方式，即將點(diǎn)云數(shù)據(jù)全部讀入內(nèi)存以便高效的點(diǎn)云后處理操作。

在海量點(diǎn)云數(shù)據(jù)的處理過程中，為了實(shí)現(xiàn)海量點(diǎn)云的快速高效的動(dòng)態(tài)更新，采用八叉樹內(nèi)節(jié)點(diǎn)格網(wǎng)量化方法進(jìn)行點(diǎn)云數(shù)據(jù)的重采樣，將簡(jiǎn)化的多分辨率點(diǎn)云數(shù)據(jù)存儲(chǔ)到相應(yīng)的中間節(jié)點(diǎn)中，并在此基礎(chǔ)上進(jìn)行點(diǎn)云數(shù)據(jù)的動(dòng)態(tài)更新操作。

格網(wǎng)量化方法對(duì)于八叉樹中的每一個(gè)內(nèi)節(jié)點(diǎn)，首先建立一個(gè)單元個(gè)數(shù)為k3的格網(wǎng)（其中k的大小可以為128），然后將內(nèi)節(jié)點(diǎn)所對(duì)應(yīng)區(qū)域中的所有采樣點(diǎn)都量化到對(duì)應(yīng)的格網(wǎng)單元中，并選擇一個(gè)采樣點(diǎn)來表示該格網(wǎng)單元。為了在動(dòng)態(tài)更新過程中正確修改相關(guān)格網(wǎng)單元，每個(gè)格網(wǎng)單元都存儲(chǔ)一個(gè)權(quán)值用于記錄該單元中采樣點(diǎn)的個(gè)數(shù)（如圖2所示）。該權(quán)值對(duì)于在點(diǎn)云動(dòng)態(tài)更新的過程中有著十分重要的作用。同時(shí)，針對(duì)量化格網(wǎng)的存儲(chǔ)問題，采用一個(gè)哈希（hash）函數(shù)來存儲(chǔ)量化格網(wǎng)。根據(jù)采樣點(diǎn)量化的XYZ坐標(biāo)，可以通過一個(gè)偽隨機(jī)哈希函數(shù)訪問動(dòng)態(tài)哈希表中的某一數(shù)據(jù)塊，從而獲得內(nèi)節(jié)點(diǎn)中對(duì)應(yīng)格網(wǎng)單元的采樣信息。

格網(wǎng)量化技術(shù)能夠支持點(diǎn)云的刪除與插入動(dòng)態(tài)更新的高效實(shí)現(xiàn)。對(duì)于通過空間劃分已經(jīng)建好的點(diǎn)云多分辨率層次結(jié)構(gòu)而言，動(dòng)態(tài)插入一個(gè)點(diǎn)需要區(qū)分以下兩種情況：待插入點(diǎn)可能位于八叉樹的根節(jié)點(diǎn)所對(duì)應(yīng)的空間區(qū)域之中，也可能在其之外。對(duì)于第一種情況，首先從根節(jié)點(diǎn)處開始遍歷，找到待插入點(diǎn)所處的最底層節(jié)點(diǎn)。如果該節(jié)點(diǎn)是葉節(jié)點(diǎn)，則將新的采樣點(diǎn)插入其中，如果其為中間節(jié)點(diǎn)，則根據(jù)待插入點(diǎn)的位置建立一個(gè)新的葉節(jié)點(diǎn)。此外，為了更新多分辨率層次信息，在遍歷的過程中還需要從根節(jié)點(diǎn)開始逐層向下將新的采樣點(diǎn)插入到下層子節(jié)點(diǎn)所維護(hù)的量化格網(wǎng)中，根據(jù)需要修改格網(wǎng)單元代表點(diǎn)的屬性值并將計(jì)數(shù)器加一，直到葉節(jié)點(diǎn)為止（如圖3）。當(dāng)待插入點(diǎn)位于八叉樹的根節(jié)點(diǎn)所對(duì)應(yīng)的空間區(qū)域之外時(shí)，可擴(kuò)大原有的根節(jié)點(diǎn)包圍盒范圍，并且將原根節(jié)點(diǎn)變?yōu)樾赂?jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)，然后根據(jù)待插入點(diǎn)的位置建立一個(gè)新的葉節(jié)點(diǎn)用于存放該插入點(diǎn)。此時(shí)必須計(jì)算新根節(jié)點(diǎn)的多分辨率層次信息，并由上而下逐層重復(fù)以上計(jì)算，直到舊的根節(jié)點(diǎn)為止。具體做法即采用與情況一相同的格網(wǎng)量化算法更新上述中間節(jié)點(diǎn)所維護(hù)的量化格網(wǎng)，修改與之對(duì)應(yīng)的量化點(diǎn)云重采樣點(diǎn)集，從而完成整個(gè)多分辨率層次結(jié)構(gòu)的更新操作。

圖3 點(diǎn)云數(shù)據(jù)的動(dòng)態(tài)插入

點(diǎn)云數(shù)據(jù)動(dòng)態(tài)刪除操作相對(duì)比較簡(jiǎn)單，具體做法為：首先找到待刪除點(diǎn)所在的葉節(jié)點(diǎn)，然后從該葉子節(jié)點(diǎn)所維護(hù)的點(diǎn)集列表中刪除該點(diǎn)。之后從葉子節(jié)點(diǎn)開始逐層向上更新上層父節(jié)點(diǎn)所維護(hù)的量化格網(wǎng)（如圖4所示）。對(duì)于在此過程中訪問的每一個(gè)中間節(jié)點(diǎn)，根據(jù)待刪除點(diǎn)的位置找到與之對(duì)應(yīng)的量化格網(wǎng)單元，將其計(jì)數(shù)權(quán)值減一，并修改代表點(diǎn)的屬性信息。如果計(jì)數(shù)權(quán)值變?yōu)榱悖摳窬W(wǎng)單元實(shí)體將會(huì)從存儲(chǔ)量化格網(wǎng)數(shù)據(jù)的哈希表中刪除。

2 數(shù)據(jù)存儲(chǔ)、訪問及查詢

2.1 索引數(shù)據(jù)存儲(chǔ)與訪問

圖4 點(diǎn)云數(shù)據(jù)的動(dòng)態(tài)刪除

針對(duì)海量點(diǎn)云多分辨率層次結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)與動(dòng)態(tài)調(diào)度，其基本思想是將點(diǎn)云八叉樹中的節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)在外存磁盤文件中，然后根據(jù)用戶的觀察視點(diǎn)參數(shù)只將那些用于繪制或編輯的節(jié)點(diǎn)導(dǎo)入到內(nèi)存中進(jìn)行繪制并提供交互。當(dāng)改變?cè)紨?shù)據(jù)中的某一個(gè)采樣點(diǎn)時(shí)，只需要訪問整條遍歷路徑（從根節(jié)點(diǎn)至葉節(jié)點(diǎn)）上的節(jié)點(diǎn)即可，一般情況下被訪問的節(jié)點(diǎn)個(gè)數(shù)十分少。在進(jìn)行繪制時(shí)，由于視場(chǎng)角度與屏幕分辨率的限制，只有一小部分的節(jié)點(diǎn)會(huì)被繪制，而大多數(shù)的節(jié)點(diǎn)不會(huì)被使用。首先在內(nèi)存中維護(hù)了一小塊空間用于存儲(chǔ)需要使用的節(jié)點(diǎn)數(shù)據(jù)，然后建立一個(gè)標(biāo)準(zhǔn)的LRU隊(duì)列用于交換不使用的節(jié)點(diǎn)數(shù)據(jù)。對(duì)于那些被修改的節(jié)點(diǎn)數(shù)據(jù)，需要重寫回到硬盤上，而那些未發(fā)生變化的節(jié)點(diǎn)數(shù)據(jù)則直接刪除。由于數(shù)據(jù)操作具有一定的連貫性，在訪問某一節(jié)點(diǎn)時(shí)會(huì)根據(jù)相鄰原則先預(yù)提取一些節(jié)點(diǎn)數(shù)據(jù)（例如待處理點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)），這樣就使得在下一步數(shù)據(jù)操作中可以直接訪問這些節(jié)點(diǎn)，而不用從外存中讀取數(shù)據(jù)，從而提高了數(shù)據(jù)的訪問速度。為了有效隱藏外存訪問延遲，可利用多線程技術(shù)為節(jié)點(diǎn)數(shù)據(jù)的預(yù)提取操作建立一個(gè)獨(dú)立的線程，使得預(yù)提取操作能與內(nèi)核處理同時(shí)進(jìn)行，從而進(jìn)一步加快了數(shù)據(jù)訪問速度。關(guān)于節(jié)點(diǎn)數(shù)據(jù)的外存文件存儲(chǔ)，可將其存儲(chǔ)到多個(gè)文件中，每個(gè)文件由固定尺寸的數(shù)據(jù)塊組成，不同文件存儲(chǔ)不同大小的塊，塊的大小以2的階次方增加。具體做法如下：

首先根據(jù)節(jié)點(diǎn)數(shù)據(jù)的大小依式（1）得到文件編號(hào)fn；

然后將該節(jié)點(diǎn)數(shù)據(jù)存入到此文件中，并確定其所處的數(shù)據(jù)塊位置編號(hào)。

使用這一方法可以減少數(shù)據(jù)訪問時(shí)間。這是因?yàn)樵谠L問節(jié)點(diǎn)時(shí)由于文件fn是由若干個(gè)大小為2 fn的數(shù)據(jù)塊組成，每個(gè)數(shù)據(jù)塊只需要一次查詢操作便能直接獲得（如圖5所示）。

圖5 基于塊的點(diǎn)云數(shù)據(jù)存儲(chǔ)方式

2.2 動(dòng)態(tài)調(diào)度與繪制機(jī)制

圖7 外存場(chǎng)景交互繪制框架

對(duì)于點(diǎn)云數(shù)據(jù)量處于百萬級(jí)到千萬級(jí)甚至更高級(jí)的點(diǎn)云數(shù)據(jù)，基于計(jì)算機(jī)內(nèi)存以及渲染限制，為了實(shí)現(xiàn)海量數(shù)據(jù)的實(shí)時(shí)動(dòng)態(tài)調(diào)度，通過動(dòng)態(tài)調(diào)度引擎［2］，采用前向投影（Forward Mapping algorithm）算法，根據(jù)觀察視點(diǎn)進(jìn)行八叉樹節(jié)點(diǎn)的動(dòng)態(tài)調(diào)度以實(shí)現(xiàn)點(diǎn)云的LOD瀏覽。海量點(diǎn)云動(dòng)態(tài)調(diào)度示意圖如圖6所示。

結(jié)合視點(diǎn)相關(guān)的層次細(xì)節(jié)、可見性剔除和外存繪制技術(shù)，采用一種大規(guī)模外存場(chǎng)景的交互繪制算法，算法的框架如圖7所示。首先對(duì)場(chǎng)景進(jìn)行空間分割，將場(chǎng)景表示為一個(gè)場(chǎng)景圖；然后采用連續(xù)分層層次細(xì)節(jié)模型（Continuous Hierarchical Level Of Detail，CHLOD）進(jìn)行組織，場(chǎng)景圖層次在繪制時(shí)保留在內(nèi)存中，而場(chǎng)景CHLOD模型存儲(chǔ)在外存；同時(shí)將視點(diǎn)空間劃分為多個(gè)視點(diǎn)單元，并為每個(gè)視點(diǎn)單元計(jì)算恰好滿足單元內(nèi)任意視點(diǎn)屏幕像素誤差的場(chǎng)景圖節(jié)點(diǎn)列表，稱為cell-front。在實(shí)時(shí)繪制時(shí)，對(duì)當(dāng)前視點(diǎn)單元的cell-front進(jìn)行層次可見性剔除，并對(duì)可見節(jié)點(diǎn)的CHLOD模型進(jìn)行視點(diǎn)相關(guān)的局部細(xì)化。為了減少磁盤訪問造成的延遲，采用多線程技術(shù)，利用相鄰視點(diǎn)單元之間cell-front的變化設(shè)計(jì)有效的預(yù)取機(jī)制，從而使CPU、GPU和IPO三者的效率能夠得到充分發(fā)揮。

2.3 鄰域查詢

對(duì)于點(diǎn)云的臨近點(diǎn)查詢、鄰域選取［3］等操作，采用二級(jí)K-D樹來對(duì)一級(jí)八叉樹索引中的葉節(jié)點(diǎn)建立高效快速的鄰近點(diǎn)查詢索引。由于一級(jí)八叉樹中的葉節(jié)點(diǎn)包含點(diǎn)云數(shù)目較小，能夠快速高效的動(dòng)態(tài)建立更為精細(xì)的K-D索引，以充分支持點(diǎn)云的濾波、分割、建模等點(diǎn)云數(shù)據(jù)后處理操作?；诎瞬鏄浜蚄-D樹相結(jié)合的二級(jí)索引機(jī)制如圖8所示。

圖8 結(jié)合八叉樹和K-D樹的二級(jí)索引機(jī)制

對(duì)于八叉樹中葉節(jié)點(diǎn)中，為了實(shí)現(xiàn)單點(diǎn)的K鄰域查詢以便于后期的濾波、簡(jiǎn)化、特征提取等操作，由于葉節(jié)點(diǎn)中的數(shù)據(jù)量較小，可以采用K-D樹構(gòu)建查詢索引并設(shè)計(jì)包含該索引的點(diǎn)云數(shù)據(jù)共享格式。K-D樹是二叉檢索樹的擴(kuò)展，樹的每一層將空間分層兩個(gè)。樹的頂層節(jié)點(diǎn)按一維進(jìn)行劃分，下一層節(jié)點(diǎn)按另一維進(jìn)行劃分，以此類推。K-D樹劃分通常用來查找高維空間距離相近的向量，是一種便于空間中點(diǎn)搜索的數(shù)據(jù)結(jié)構(gòu)。首先按X軸尋找分割線，即計(jì)算所有點(diǎn)的x值的平均值，以最接近這個(gè)平均值的點(diǎn)的x值將空間分成兩部分;然后在分成的子空間中按Y軸尋找分割線，將其各分成兩部分;分割好的子空間在按X軸分割，依此類推;最后直到分割的區(qū)域內(nèi)最后一個(gè)點(diǎn)。這樣的分割過程就對(duì)應(yīng)于一個(gè)二叉樹。二叉樹的分支節(jié)點(diǎn)就對(duì)應(yīng)于一條分割線，而二叉樹的每個(gè)葉節(jié)點(diǎn)就對(duì)應(yīng)一個(gè)點(diǎn)。這樣，點(diǎn)的拓?fù)潢P(guān)系就建立了。

3 結(jié)語(yǔ)

本文采用了一種基于八叉數(shù)的點(diǎn)云管理方法。該方法借助八叉樹細(xì)粒度地劃分點(diǎn)云的三維空間，避免了海量點(diǎn)云的逐點(diǎn)插入操作，顯著提升索引效率。保證了深度平衡的樹狀結(jié)構(gòu)，實(shí)現(xiàn)良好的空間查詢效率。通過研究點(diǎn)云數(shù)據(jù)動(dòng)態(tài)更新、索引數(shù)據(jù)的存儲(chǔ)、動(dòng)態(tài)調(diào)度與繪制、領(lǐng)域的查詢等技術(shù)，形成了一套高效快速的海量點(diǎn)云數(shù)據(jù)管理方法。本文研究不僅為大規(guī)模點(diǎn)云數(shù)據(jù)提供管理支持，而且還可為點(diǎn)云后處理如點(diǎn)云壓縮、自動(dòng)構(gòu)網(wǎng)提供支持。

［1］徐源強(qiáng)，高井祥，王堅(jiān).三維激光掃描技術(shù)［J］.測(cè)繪信息與工程，2010（4）：9-10.

［2］孟放.大型三維點(diǎn)云數(shù)據(jù)的交互繪制研究［D］.北京：北京大學(xué)，2005.

［3］周儒榮，張麗艷，蘇旭.海量散亂點(diǎn)的曲面重建算法研究［J］.軟件學(xué)報(bào)，2001（2）：91-97.