基于改進的八叉樹索引與分層渲染的海量激光點云可視化技術

王磊　郭清菊　姜晗

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

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

中圖分類號：000000 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2016.04.026

0 引言

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

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

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

1 改進的八叉樹索引算法與LOD技術

1.1 改進的八叉樹索引算法

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

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

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

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

1.2 LOD可視化技術

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

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

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

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

2 實驗與分析

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

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

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

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

3 結語

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