王磊　郭清菊　姜晗

摘要：近年來利用三維激光掃描技術(shù)進(jìn)行的國內(nèi)各地城市數(shù)字化發(fā)展迅速，隨著硬件技術(shù)的升級(jí)和掃描范圍的逐漸擴(kuò)大，獲得的相應(yīng)的三維數(shù)據(jù)可達(dá)TB級(jí)。因此，如何合理的建立點(diǎn)云索引管理機(jī)制，是解決海量點(diǎn)云數(shù)據(jù)組織和管理的關(guān)鍵問題。本文首先對(duì)傳統(tǒng)八叉樹數(shù)據(jù)結(jié)構(gòu)的索引方法進(jìn)行了優(yōu)化，然后對(duì)三維點(diǎn)云分塊，建立八叉樹索引數(shù)據(jù)文件，同時(shí)用LOD方法對(duì)其進(jìn)行分層抽稀操作，通過建立改進(jìn)的八叉樹與LOD方法相結(jié)合的索引，來降低內(nèi)存的消耗、提高查詢的效率，最后根據(jù)屏幕顯示范圍與視角變化實(shí)時(shí)讀取釋放點(diǎn)云索引數(shù)據(jù)，從而實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的可視化。

關(guān)鍵詞：海量點(diǎn)云；八叉樹索引；細(xì)節(jié)層次模型；可視化

中圖分類號(hào)：000000 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2016.04.026

0 引言

近年來，城市數(shù)字化工作在國內(nèi)各線城市中開展，在對(duì)城市的三維空間信息的采樣獲取過程中，逐漸實(shí)踐和總結(jié)出了多種快速有效的手段。其中，使用三維掃描技術(shù)對(duì)被測目標(biāo)采集真實(shí)空間坐標(biāo)數(shù)據(jù)的方法被廣泛采用并應(yīng)用到采集工作中，三維激光掃描技術(shù)所依托的軟件硬件在近些年來得到了迅速的發(fā)展，掃描目標(biāo)場景的不斷增大和場景復(fù)雜度的不斷升高，都對(duì)掃描設(shè)備的存儲(chǔ)量和掃描算法的運(yùn)算效率提出了挑戰(zhàn)。例如，廣泛裝備于汽車的激光掃描設(shè)備，其工作原理就是使用數(shù)個(gè)激光掃描器對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行采集，最終獲取的掃描數(shù)據(jù)量接近TB級(jí)，由此看來，處理數(shù)據(jù)的算法亟待優(yōu)化和改進(jìn)。為了更好的將采集到的海量點(diǎn)云數(shù)據(jù)應(yīng)用到三維重建與快速輔助生成地形圖等實(shí)際應(yīng)用中來，需要對(duì)海量點(diǎn)云數(shù)據(jù)的管理算法進(jìn)行不斷的優(yōu)化。在管理海量點(diǎn)云數(shù)據(jù)時(shí)，最為常用的管理方法是利用索引管理點(diǎn)云數(shù)據(jù)，索引的好壞直接關(guān)系到點(diǎn)云數(shù)據(jù)處理的效率，因此如何完善現(xiàn)有的索引算法，建立更高效的海量點(diǎn)云索引，是近幾年相關(guān)方向的研究重點(diǎn)之一。

目前，實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)快速顯示的有效方法是構(gòu)建索引樹，常用的索引樹主要包括R樹、K-D樹、四叉樹和八叉樹等。其中，R樹具有較強(qiáng)的靈活性和調(diào)節(jié)性，但由于中間節(jié)點(diǎn)允許重疊，在查找速度、動(dòng)態(tài)操作性能方面仍存在一些不足；四叉樹和八叉樹結(jié)構(gòu)簡單，對(duì)于精確匹配點(diǎn)的查找性能較高，但樹的動(dòng)態(tài)性較差，樹的平衡性不好，以至于影響點(diǎn)云顯示的交互性。針對(duì)上述問題，國內(nèi)外研究者相繼提出了一系列改進(jìn)的方法。Beckmmann等在R樹的基礎(chǔ)上提出了R*樹，相比于R樹，R*樹的優(yōu)越性體現(xiàn)在查找方式和節(jié)點(diǎn)操作的多樣性，并且它同時(shí)支持點(diǎn)和空間數(shù)據(jù)的索引，但是R*樹的索引構(gòu)建時(shí)間比R樹略高。支曉棟等提出的一種改進(jìn)四叉樹算法可以快速完成索引樹的構(gòu)建，但是該算法構(gòu)建的索引樹的樹高減小，降低了數(shù)據(jù)的查詢速度。

相較于傳統(tǒng)方法在處理點(diǎn)云數(shù)據(jù)時(shí)，內(nèi)存占用率高，執(zhí)行效率低等問題，本文提出了一種新的方法，該方法以優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，對(duì)可視化過程中需要的海量點(diǎn)云數(shù)據(jù)進(jìn)行有效的組織。由于本文對(duì)海量點(diǎn)云數(shù)據(jù)同時(shí)進(jìn)行八叉樹結(jié)構(gòu)的索引創(chuàng)建操作和LOD抽稀采樣操作，并對(duì)傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)經(jīng)過了優(yōu)化，所以，在索引創(chuàng)建與檢索過程中，可以實(shí)時(shí)降低內(nèi)存的消耗、提高查詢效率。最終根據(jù)顯示范圍查找索引讀取對(duì)應(yīng)數(shù)據(jù)塊，從而實(shí)現(xiàn)海量的點(diǎn)云數(shù)據(jù)更加高效的可視化瀏覽。

1 改進(jìn)的八叉樹索引算法與LOD技術(shù)

1.1 改進(jìn)的八叉樹索引算法

八叉樹結(jié)構(gòu)是一種用來描述三維空間的數(shù)據(jù)結(jié)構(gòu)，八叉樹中任一節(jié)點(diǎn)的子節(jié)點(diǎn)均為八個(gè)，各節(jié)點(diǎn)分別指向下一個(gè)八叉樹節(jié)點(diǎn)。對(duì)一定的三維空間做基于三維坐標(biāo)軸方向的分割，可以得到相應(yīng)的八個(gè)小立方體，各小立方體被稱為體元，每個(gè)體元中存儲(chǔ)相應(yīng)的屬性數(shù)據(jù)，這就是八叉樹結(jié)構(gòu)。通過對(duì)經(jīng)典八叉樹算法分析可知，如果將經(jīng)典八叉樹數(shù)據(jù)結(jié)構(gòu)直接應(yīng)用于海量點(diǎn)云數(shù)據(jù)的管理，其各節(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)上存在冗余，比如，為提高檢索速度，相鄰指針和父指針會(huì)被存儲(chǔ)在節(jié)點(diǎn)之間，但是相應(yīng)的內(nèi)存空間會(huì)增大。如圖1.1所示，指向父節(jié)點(diǎn)的指針我們在這里使用m parent命名，相應(yīng)的，定義孩子節(jié)點(diǎn)指針為m_child，使用m_pointsNum保存數(shù)據(jù)塊ID，另外，m_points表示當(dāng)前指針。

雖然在設(shè)計(jì)時(shí)對(duì)八叉樹的結(jié)構(gòu)考慮的各方面都非常細(xì)致，但是在點(diǎn)云數(shù)據(jù)管理的應(yīng)用中其中的某些屬性信息并沒有保存的必要。為了降低程序在運(yùn)行時(shí)的內(nèi)存占用率，本文分以下幾步對(duì)八叉樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化：首先對(duì)以上的存儲(chǔ)結(jié)構(gòu)中的非必需字段進(jìn)行刪除，以釋放內(nèi)存容量，降低存儲(chǔ)冗余。比如可以將節(jié)點(diǎn)的父指針入棧，使用基于棧的相關(guān)操作方法來完成對(duì)其父節(jié)點(diǎn)指針的查找操作，因此各節(jié)點(diǎn)不需要為父節(jié)點(diǎn)指針作單獨(dú)的存儲(chǔ)。其次，優(yōu)化結(jié)構(gòu)以節(jié)省存儲(chǔ)空間。由于點(diǎn)云一般都是采集現(xiàn)實(shí)區(qū)域中的數(shù)據(jù)，比如學(xué)校、村莊、高速公路等，因其地理位置的不定性，在采集空間數(shù)據(jù)時(shí)，只有一部分區(qū)域會(huì)生成點(diǎn)云，相應(yīng)在進(jìn)行存儲(chǔ)時(shí)就會(huì)有很大的空閑空間。在存儲(chǔ)八叉樹的線性鏈表中，各節(jié)點(diǎn)是否有子節(jié)點(diǎn)直接決定了該節(jié)點(diǎn)是否需要進(jìn)行下一步分割處理?；诖耍梢远x一個(gè)指針指向所有的子樹。1個(gè)字節(jié)有8個(gè)比特，恰好對(duì)應(yīng)八個(gè)子節(jié)點(diǎn)，即可以用每個(gè)比特作為標(biāo)識(shí)，來表示當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否存在。

依據(jù)上文中的分析，優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)如圖1.2所示：

其中m_child指向了第一個(gè)孩子。m_allChilds表示孩子的狀態(tài)，即依次標(biāo)示每個(gè)節(jié)點(diǎn)的8個(gè)孩子是否存在。顯而易見，相較于經(jīng)典的八叉樹，這樣的編碼方式在運(yùn)行時(shí)的內(nèi)存占用率有了很大降低。尤其在程序運(yùn)行時(shí)，相應(yīng)索引的建立和檢索操作大大降低了內(nèi)存占用率，提高了執(zhí)行效率。

1.2 LOD可視化技術(shù)

這里提到的LOD技術(shù)，其英文全稱為level ofdetails，簡稱LOD，字面意思可以理解為“多層次（展現(xiàn)）細(xì)節(jié)”技術(shù)，在該技術(shù)的作用下，渲染資源會(huì)依據(jù)模型各區(qū)域的重要程度進(jìn)行重分配，從而對(duì)提高渲染效率。例如，視角靠近物體的時(shí)候，就選擇精細(xì)的、高分辨率的模型來進(jìn)行實(shí)時(shí)渲染，而當(dāng)視角遠(yuǎn)離的時(shí)候，就選擇低分辨率的、粗糙的模型來進(jìn)行渲染；根據(jù)視角的變化來實(shí)時(shí)地進(jìn)行顯示模型的切換，從而快速繪制顯示圖形、實(shí)現(xiàn)海量數(shù)據(jù)的實(shí)時(shí)交互。

經(jīng)典的基于規(guī)則格網(wǎng)構(gòu)建LOD模型的方法是Lindstrom等人提出的，基于視點(diǎn)的連續(xù)細(xì)節(jié)層次（Continuous LOD，簡稱CLOD）算法。將一個(gè)正方體的點(diǎn)云區(qū)域均等分割成八個(gè)小正方體點(diǎn)云區(qū)域，而被分割出來的正方體均為要構(gòu)造的八叉樹的一個(gè)節(jié)點(diǎn)，在這些節(jié)點(diǎn)中存有對(duì)應(yīng)區(qū)域的點(diǎn)云數(shù)據(jù)，依據(jù)所掃描的區(qū)域的具體情況，越復(fù)雜的點(diǎn)云所分割的精細(xì)度就更大，從而得到的精確度就更高。本文基于該方法，自頂向下遞歸地對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行劃分，并建立了對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，同時(shí)，根據(jù)屏幕顯示的覆蓋范圍，決定什么時(shí)候、加載哪些節(jié)點(diǎn)存儲(chǔ)的點(diǎn)云數(shù)據(jù)，來進(jìn)行LOD模型的動(dòng)態(tài)更新。

本文根據(jù)LOD算法的基本思想，使用八叉樹數(shù)據(jù)結(jié)構(gòu)對(duì)該模型分層重構(gòu)。首先根據(jù)原始點(diǎn)云數(shù)據(jù)量的大小，得到原始數(shù)據(jù)的范圍，即Xmin，Xmax，Ymin，Ymax，Zmin，Zmax，根據(jù)總體數(shù)據(jù)的Zmax、Zmin與實(shí)際需要來確定分割深度N。然后，依據(jù)本文提出的改進(jìn)的八叉樹方法對(duì)獲得的數(shù)據(jù)進(jìn)行點(diǎn)云分塊，這種分塊操作的順序是自頂向下的。如，首先對(duì)第N層深度的點(diǎn)云進(jìn)行等間距抽稀，每隔2N個(gè)點(diǎn)進(jìn)行采樣，生成的數(shù)據(jù)使用八叉樹結(jié)構(gòu)存儲(chǔ)，作為第N層的節(jié)點(diǎn)，存儲(chǔ)到八叉樹結(jié)構(gòu)中去；然后繼續(xù)對(duì)N-l層的點(diǎn)云數(shù)據(jù)采用相同處理，此時(shí)抽稀間距為2N-l，并排除掉已經(jīng)在八叉樹中存儲(chǔ)的（即抽稀間距為2N的點(diǎn)云數(shù)據(jù)），這些作為八叉樹的第N-1層的節(jié)點(diǎn)，存儲(chǔ)到八叉樹結(jié)構(gòu)中去，持續(xù)分割，直到N=1，當(dāng)N=1時(shí)，不再需要抽稀，直接將該區(qū)域范圍內(nèi)未存儲(chǔ)到八叉樹結(jié)構(gòu)中的點(diǎn)存儲(chǔ)到該層對(duì)應(yīng)節(jié)點(diǎn)即可。

至此，數(shù)據(jù)索引構(gòu)建完成。在瀏覽的過程中，根據(jù)當(dāng)前視角的坐標(biāo)來計(jì)算需要顯示的點(diǎn)云塊的范圍，根據(jù)視角遠(yuǎn)近比例來計(jì)算顯示深度，即可在保證運(yùn)行效率的前提下實(shí)現(xiàn)動(dòng)態(tài)的點(diǎn)云渲染。

2 實(shí)驗(yàn)與分析

本文利用c++與vtk實(shí)現(xiàn)了海量點(diǎn)云數(shù)據(jù)的索引快速建立與動(dòng)態(tài)調(diào)度，并實(shí)現(xiàn)了渲染與繪制，實(shí)驗(yàn)數(shù)據(jù)為某地區(qū)的點(diǎn)云掃描數(shù)據(jù)，實(shí)驗(yàn)環(huán)境為intel corei7處理器，8G內(nèi)存。

如圖2.1與圖2.2中所示為實(shí)驗(yàn)過程中海量激光點(diǎn)云數(shù)據(jù)的實(shí)現(xiàn)效果。表2.1將本文方法與傳統(tǒng)構(gòu)建八叉樹索引處理方式進(jìn)行了比較。對(duì)于兩種方法對(duì)同一組點(diǎn)云數(shù)據(jù)，在海量數(shù)據(jù)索引的構(gòu)建、內(nèi)存占用情況、節(jié)點(diǎn)存儲(chǔ)文件大小等數(shù)據(jù)信息做了對(duì)比與分析。

經(jīng)過對(duì)表2.1中的數(shù)據(jù)進(jìn)行分析我們可以得到，使用本文中的算法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理時(shí)，所消耗的時(shí)間和點(diǎn)云的體積是有著類似線性相關(guān)性的。傳統(tǒng)方法對(duì)點(diǎn)云數(shù)據(jù)的處理步驟為：先對(duì)原始點(diǎn)云做八叉樹分塊處理，再進(jìn)行LOD抽稀，即分層抽稀操作需要等到前一步（分塊處理）完成后再進(jìn)行，而本文中提到的算法思想為：對(duì)點(diǎn)云數(shù)據(jù)的分塊操作與LOD抽稀同時(shí)進(jìn)行，所以本方法在生成索引文件的過程中所消耗的時(shí)間與傳統(tǒng)方法相比要短得多，并且，為了降低八叉樹索引操作在運(yùn)行時(shí)的內(nèi)存消耗，本文還對(duì)傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行了優(yōu)化。另外，本文方法的最大優(yōu)勢，就是在創(chuàng)建索引時(shí)，就通過抽稀分層實(shí)現(xiàn)了LOD算法，因此在實(shí)時(shí)瀏覽時(shí)，直接調(diào)用八叉樹，即實(shí)現(xiàn)了LOD算法，不需要在顯示時(shí)二次構(gòu)建渲染分層模型，節(jié)省了大量內(nèi)存。

實(shí)驗(yàn)數(shù)據(jù)表明：本文方法較傳統(tǒng)方法相比更適合應(yīng)用于海量點(diǎn)云數(shù)據(jù)的實(shí)時(shí)呈現(xiàn)。本文對(duì)傳統(tǒng)的八叉樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了優(yōu)化，使其在對(duì)點(diǎn)云數(shù)據(jù)的處理中有著更高的運(yùn)行效率。改進(jìn)后的方法首先對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行索引分塊，在對(duì)數(shù)據(jù)進(jìn)行LOD抽稀的同時(shí)，使用優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)管理，節(jié)省了存儲(chǔ)空間，降低了內(nèi)存占用率。

3 結(jié)語

綜上，本文提出的對(duì)點(diǎn)云數(shù)據(jù)的處理方法相較于經(jīng)典算法在執(zhí)行渲染操作時(shí)，顯示效率更高，更能滿足實(shí)際海量點(diǎn)云數(shù)據(jù)可視化的需求。通過對(duì)比數(shù)據(jù)表明，本文的算法是值得進(jìn)一步研究與應(yīng)用的。此外，為了提高點(diǎn)云渲染效率，需要進(jìn)一步研究如何與GPU渲染方法相結(jié)合，從而取得更好的顯示效果。