基于八叉樹的點(diǎn)云數(shù)據(jù)的組織與可視化

張會(huì)霞

（太原師范學(xué)院 城市與旅游學(xué)院，山西 太原 030012）

基于八叉樹的點(diǎn)云數(shù)據(jù)的組織與可視化

張會(huì)霞

（太原師范學(xué)院 城市與旅游學(xué)院，山西 太原 030012）

三維激光掃描獲取了大量的點(diǎn)云數(shù)據(jù)，數(shù)據(jù)的組織直接影響點(diǎn)云數(shù)據(jù)的操作速度.采用數(shù)據(jù)庫(kù)管理點(diǎn)云數(shù)據(jù)，對(duì)點(diǎn)云數(shù)據(jù)采用八叉樹數(shù)據(jù)模型進(jìn)行組織，建立空間索引，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行分塊提取，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的檢索以及可視化.

八叉樹；點(diǎn)云數(shù)據(jù)；組織；可視化

三維激光掃描技術(shù)（3D Laser Scanning Technology）是一種先進(jìn)的全自動(dòng)高精度立體掃描技術(shù).它是一項(xiàng)新興的獲取空間數(shù)據(jù)的技術(shù)，同傳統(tǒng)的測(cè)量手段相比，三維激光掃描測(cè)量技術(shù)可以連續(xù)、自動(dòng)、快速地采集大量的目標(biāo)物表面數(shù)據(jù)，即點(diǎn)云數(shù)據(jù)，并且擁有許多獨(dú)特的優(yōu)勢(shì)［1］.由于點(diǎn)云數(shù)據(jù)量大，把所有的點(diǎn)一次性的調(diào)入內(nèi)存，系統(tǒng)運(yùn)行緩慢，故需要進(jìn)行合理的數(shù)據(jù)組織，建立索引.

三維激光掃描獲取的數(shù)據(jù)為三維目標(biāo)物點(diǎn)云數(shù)據(jù)，由于目標(biāo)物多為不規(guī)則形狀，對(duì)于體狀目標(biāo)物數(shù)據(jù)的管理，八叉樹數(shù)據(jù)模型具有獨(dú)到的優(yōu)勢(shì)，故采用八叉樹數(shù)據(jù)模型進(jìn)行組織.

1 八叉樹模型的基本理論

三維激光掃描獲取大量的點(diǎn)云數(shù)據(jù)，對(duì)點(diǎn)云數(shù)據(jù)采用八叉樹模型進(jìn)行組織，通過對(duì)點(diǎn)云數(shù)據(jù)層層分割，最后葉節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)量大大減少，可以加快檢索速度.

八叉樹是一種非常直觀的數(shù)據(jù)結(jié)構(gòu)，具有樹的深度小，遍歷速度快的特點(diǎn)［2］.八叉樹分為規(guī)則八叉樹和線性八叉樹.規(guī)則八叉樹是指直接通過八叉樹結(jié)構(gòu)來描述空間信息，即顯性地描述節(jié)點(diǎn)及通過指針來表達(dá)父子關(guān)系.八叉樹由中間節(jié)點(diǎn)組成，葉子節(jié)點(diǎn)保存在中間節(jié)點(diǎn)的子節(jié)點(diǎn)中.八叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)要存儲(chǔ)8個(gè)子節(jié)點(diǎn)的指針、父節(jié)點(diǎn)的指針，對(duì)于非葉子節(jié)點(diǎn)，還要存儲(chǔ)下一個(gè)子節(jié)點(diǎn)的指針，以及該節(jié)點(diǎn)的屬性數(shù)據(jù)，內(nèi)存消耗大.

線性八叉樹是為了克服規(guī)則八叉樹編碼的不足而形成的一種高效的編碼方法.這種方法只存儲(chǔ)葉節(jié)點(diǎn)，包括葉節(jié)點(diǎn)的位置、大小、屬性值.葉節(jié)點(diǎn)的編碼稱為地址碼，常用的地址碼是Morton碼，它隱含了葉節(jié)點(diǎn)的位置和大小信息.比如空間目標(biāo)的大小為2n×2n×2n，分辨率為1，那么任意葉節(jié)點(diǎn)的Morton碼是一個(gè)n位數(shù)的編碼［3］，可以寫成：

八叉樹的結(jié)構(gòu)示意圖如圖1所示：

點(diǎn)云數(shù)據(jù)由于數(shù)據(jù)量大，且都分布在目標(biāo)物的外表面，在八叉樹中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)數(shù)據(jù)塊.本文對(duì)點(diǎn)云數(shù)據(jù)分割3次，分為4級(jí)，目的是為了分塊檢索數(shù)據(jù).

2 點(diǎn)云數(shù)據(jù)八叉樹模型的生成

八叉樹模型是一種中間結(jié)構(gòu)，它不能直接由原始采樣數(shù)據(jù)生成，只能由其他模型轉(zhuǎn)換得到［4］.本節(jié)由三維陣列生成八叉樹模型，由于三維陣列表示的數(shù)據(jù)量大，一般情況下只作為過渡表示，把點(diǎn)云數(shù)據(jù)先轉(zhuǎn)換成三維陣列表示，再轉(zhuǎn)換成八叉樹模型.

圖1 八叉樹結(jié)構(gòu)示意圖

對(duì)于2n×2n×2n的三維陣列表示的目標(biāo)，若某一單元的三維坐標(biāo)為（I，J，K）（I，J，K＝0，1，2，...，2n－1），將三維坐標(biāo)轉(zhuǎn)換成二進(jìn)制表示有如下形式［3］：

把點(diǎn)云數(shù)據(jù)采用八叉樹模型進(jìn)行分割，分割三次就產(chǎn)生23×23×23個(gè)三維陣列格網(wǎng).確定每個(gè)點(diǎn)所屬的三維陣列格網(wǎng)，也就是把點(diǎn)云數(shù)據(jù)歸屬于不同的格網(wǎng)中，即八叉樹葉節(jié)點(diǎn)中.八叉樹的地址碼采用八進(jìn)制的Morton碼進(jìn)行編碼，通過計(jì)算每個(gè)格網(wǎng)的Morton碼，按Morton碼的大小進(jìn)行排序.可根據(jù)Morton碼進(jìn)行分塊檢索.

2.1 Morton碼的生成

Morton碼的生成算法有兩種：一種是比特運(yùn)算法，另一種是求余數(shù)法.比特運(yùn)算法是按位操作，十進(jìn)制的行號(hào)在計(jì)算機(jī)內(nèi)部采用二進(jìn)制的形式表示，把X、Y、Z方向的行列號(hào)用二進(jìn)制的形式II、JJ、KK表示，通過取出KK、JJ、II的二進(jìn)制中的各位交叉結(jié)合，就可得到每個(gè)單元的Morton碼.按位運(yùn)算主要利用C語(yǔ)言按位操作的“或”運(yùn)算，由于本文是采用C＃語(yǔ)言進(jìn)行開發(fā)，故采用第二種求Morton碼的方法求余數(shù)法進(jìn)行計(jì)算.求余數(shù)法是把十進(jìn)制的行列號(hào)通過求余數(shù)轉(zhuǎn)換為二進(jìn)制的行列號(hào)，再通過公式求出Morton碼.

每個(gè)點(diǎn)的Morton碼算法如下：

1）求點(diǎn)云數(shù)據(jù)X，Y，Z方向的最大最小點(diǎn)值：

2）求出點(diǎn)云數(shù)據(jù)的外包絡(luò)六面體的長(zhǎng)L、寬W、高H：

3）求出三維陣列中每個(gè)單元格的大小△X，△Y，△Z：

4）求出每一個(gè)點(diǎn)在三維陣列中的十進(jìn)制行列號(hào)l，m，k：

5）將每一單元格十進(jìn)制的行列號(hào)轉(zhuǎn)換為二進(jìn)制表示：

十進(jìn)制的行列號(hào)l，m，k通過求余運(yùn)算，轉(zhuǎn)換成二進(jìn)制的行列號(hào)Ib，Jb，Kb.

6）根據(jù)二進(jìn)制的行列號(hào)，計(jì)算每一點(diǎn)的Morton碼的值.

2.2 點(diǎn)云數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

八叉樹的構(gòu)建在內(nèi)存中進(jìn)行，由于系統(tǒng)內(nèi)存的限制，把內(nèi)存結(jié)構(gòu)映射到外存數(shù)據(jù)庫(kù)中，并把一些信息寫入外存數(shù)據(jù)庫(kù)中.在數(shù)據(jù)量大時(shí)，可直接在外存數(shù)據(jù)庫(kù)中進(jìn)行檢索，避免把所有的數(shù)據(jù)一次性的裝入系統(tǒng)，使得系統(tǒng)運(yùn)行緩慢.點(diǎn)的數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言表示如下：

struct Point

數(shù)據(jù)庫(kù)中點(diǎn)表字段設(shè)計(jì)，如表1.

所對(duì)應(yīng)的八叉樹表字段設(shè)計(jì)，如表2.

表2 八叉樹表字段結(jié)構(gòu)

表2中Point1為葉節(jié)點(diǎn)的最小坐標(biāo)點(diǎn)，Point2為葉節(jié)點(diǎn)的最大坐標(biāo)點(diǎn).code為葉節(jié)點(diǎn)的Morton碼.

3 點(diǎn)云數(shù)據(jù)八叉樹模型的實(shí)現(xiàn)

采用八叉樹模型組織點(diǎn)云數(shù)據(jù)，可以達(dá)到樹的深度小，檢索速度快的效果.以下代碼是點(diǎn)云數(shù)據(jù)的八叉樹模型生成算法代碼，求出每個(gè)點(diǎn)所歸屬的葉節(jié)點(diǎn)，并把它保存在數(shù)據(jù)庫(kù)中，用數(shù)據(jù)庫(kù)管理點(diǎn)云數(shù)據(jù)，可視化時(shí)，根據(jù)需要提取出數(shù)據(jù)，加快系統(tǒng)運(yùn)行效率.本文采用SQL Server2008管理點(diǎn)云數(shù)據(jù)，采用C＃語(yǔ)言開發(fā)Map Objects組件，在Map Objects組件下進(jìn)行可視化.

八叉樹分為四層，分割3次算法如下：

1）從數(shù)據(jù)庫(kù)中讀出點(diǎn)云數(shù)據(jù)；

2）求出點(diǎn)云數(shù)據(jù)的外包絡(luò)六面體；

3）求出每個(gè)點(diǎn)所在的十進(jìn)制行列號(hào)；

4）把每個(gè)十進(jìn)制的行列號(hào)轉(zhuǎn)換成二進(jìn)制行列號(hào)；

5）求出點(diǎn)的八叉樹Morton碼；

6）寫入數(shù)據(jù)庫(kù).

關(guān)鍵代碼如下：

4 點(diǎn)云數(shù)據(jù)的檢索及可視化

根據(jù)組織好的點(diǎn)云數(shù)據(jù)進(jìn)行檢索，可根據(jù)Morton碼提取出點(diǎn)云數(shù)據(jù)，也可根據(jù)區(qū)域范圍，通過八叉樹索引表，確定包括那些Morton碼，然后進(jìn)行查詢.圖2是采用三維激光掃描儀獲取的點(diǎn)云數(shù)據(jù)，本文對(duì)建筑物點(diǎn)云數(shù)據(jù)以文本的格式導(dǎo)入到SQL Server 2008數(shù)據(jù)庫(kù)軟件中采用八叉樹數(shù)據(jù)模型進(jìn)行重新組織，圖3是根據(jù)Morton碼提取出的點(diǎn)云數(shù)據(jù)，不考慮反射率，記錄數(shù)71 960條，用時(shí)1 s，并在MO組件下進(jìn)行可視化.實(shí)驗(yàn)證明，采用八叉樹模型組織后的點(diǎn)云數(shù)據(jù)檢索速度較快，適于點(diǎn)云數(shù)據(jù)的分塊提取.

圖2 原始的建筑點(diǎn)云數(shù)據(jù)

圖3 根據(jù)Morton碼提取出的點(diǎn)云數(shù)據(jù)

5 結(jié)論

本文采用八叉樹組織點(diǎn)云數(shù)據(jù)，可實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的分塊快速檢索，采用MO組件進(jìn)行可視化，可實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的可視化.通過編程驗(yàn)證，該算法效率較高.

［1］李必軍，方志祥，任 娟.從激光掃描數(shù)據(jù)中進(jìn)行建筑物特征提取研究［J］.武漢大學(xué)（信息科學(xué)版），2003，28（1）：65-70

［2］惠文華，郭新成.三維 GIS中的八叉樹空間索引研究［J］.測(cè)繪通報(bào)，2003，1：25-27

［3］路明月，何永健.三維海量點(diǎn)云數(shù)據(jù)的組織與索引方法［J］.地球信息科學(xué)，2008，10（2）：190-194

［4］李清泉，楊必勝，史文中，等.三維空間數(shù)據(jù)的實(shí)時(shí)獲取、建模與可視化［M］.武漢：武漢大學(xué)出版社，2003

The Organization and Visualization of Point Cloud Data Based on the Octree

Zhang Huixia
（College of Urban and Tourism，Taiyuan Normal University，Taiyuan 030012，China）

The three dimensional laser scanning gains the massive point cloud data，and the data organization immediate influence point cloud data operating speed.By using the database administrated point cloud data，using Octree data model to carry on the organization of the cloud data，establishing the spatial index，the point cloud data are carried on the block extraction，and realize the cloud data retrieval as well as the visualization.

octree；point cloud data；data organization；visualization

張麗萍】

1672-2027（2011）03-0128-05

TP39

A

2011-04-14

張會(huì)霞（1972-），女，山西運(yùn)城人，博士，太原師范學(xué)院城市與旅游學(xué)院講師，主要從事地圖制圖、GIS、三維激光掃描方面的研究.