王磊　郭清菊　姜晗

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

1.2 LOD可視化技術(shù)

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

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

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

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

2 實驗與分析

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

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

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

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

3 結(jié)語

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