基于改進四叉樹結構的LAS數據空間索引建立方法

陶維重 徐 瑩 楊 陽 劉 揚

（1.黑龍江地理信息工程院，黑龍江 哈爾濱 150081；2.北京師范大學地理科學學部，北京 100000）

0.引言

LAS文件是由美國攝影測量與遙感協會ASPRS（American Society for Photogrammetry and Remote Sensing）提出的用于保存激光點云數據的文件格式，被廣泛使用在三維激光掃描、激光點云可視化、海量激光點云存儲等。根據ASPRS對LAS文件結構的描述可知，LAS文件本身并不存在空間索引，這使得對LAS文件直接進行空間查詢和空間分析等相關操作帶來了不便。目前的做法是將LAS數據導入到第三方軟件中再對激光點云數據建立空間索引，空間查詢和分析等相關操作則由第三方軟件提供接口來完成[1]。這種方式無法擺脫第三方軟件本身的束縛，并且這些軟件大多都不會公開空間索引算法，對激光點云分析的底層算法構建帶來了麻煩，需要自己建立LAS數據空間索引的方法來解決以上問題。

四叉樹空間索引結構是常見的地理數據空間索引的結構，四叉樹結構簡單易于實現，本文根據ASPRS對LAS文件的說明對其進行解析，結合空間索引建立方法和激光點云數據特點，分析傳統四叉樹結構針對該類型數據建立空間索引的一些缺陷，對四叉樹結構進行改進，利用改進后的結構建立LAS激光點云數據的空間索引。

1 LAS數據讀取方式介紹

1.1 LAS數據結構解析

根據ASPRS對LAS格式的說明，以目前較為通用的LAS1.3為例，LAS文件主要包含三個部分：公共文件頭區、變長記錄區、點集記錄區[2]。

公共文件頭區（Public header block）：該區域包含了該LAS文件的概要信息，如,版本號、總點數、范圍信息、偏移量、變長記錄區長度等信息。

變長記錄區（Variable length records）：該區域被用于提高LAS數據的可擴展性，使LAS數據的存儲方式更加靈活。

點集記錄區（Point data records）：包含了點的空間位置和屬性信息，如，XYZ、回波次數、回波強度等。

LAS本身不存在空間索引存儲部分，只是單純的點集數據，如果想進行空間查詢類操作，需要開發者根據文件說明提取對應信息建立，通過解析LAS文件以上的信息，可以對LAS文件存儲的激光點云數據規模進行預分析，得到建立空間索引所需要的相關數據。

1.2 開源LAS文件解析庫LIBLAS

ASPRS對于LAS文件各個分區存儲的長度均有說明，開發者可以根據文檔對LAS文件進行定長讀取，也可以使用LIBLAS開源庫對LAS文件進行讀取。LIBLAS是一個用于讀寫LAS文件開源C/C++庫，從LAS1.0開始便在點云開發者網站上被評為最優秀的激光點云讀寫開源庫，并且隨著LAS數據的不斷迭代而更新，在讀寫LAS數據上，被用于各種激光點云處理軟件當中。基于LIBLAS對LAS文件優秀的兼容性，可以輕松得到LAS文件保存的激光點云數據相關信息，通過建立Reader對象，讀取LAS文件中的公共文件頭區建立Header對象，獲取點云的概要信息，通過Reader中的ReadNextPoint方法移動指針對激光點云數據進行查找操作，從而實現讀取激光點云數據的目的。后文中的所有算法中的關于激光點云讀取部分的均是由LIBLAS實現。

2 基于改進四叉樹的空間索引

2.1 傳統的四叉樹空間索引結構

四叉樹索引是Tayeb在1998年提出的一種樹狀結構的數據索引[3]，其原理是將一塊矩形區域四等分成四個子區域，每個子區域再次四等分，自頂向下遞歸操作，直到每個子區域包含的元素數量小于或等于規定的容量為止。四叉樹具有明顯的空間特性，根據四叉樹的空間特性，可以利用其制作空間索引[4]，其原理結構（如圖1所示）:

圖1 四叉樹結構原理

假設矩形區域內存在編號為1至9的地理數據，將區域等分為四個子區域ABCD，其中，B區域又四等分四個子區域，則地理數據索引的存儲結構為（如圖1所示），地理數據索引被存儲在ACDxyzt子節點上，B節點作為父節點（子節點的上一級）不保存地理數據。這種存儲方式方便，在數據量不大時空間查詢的效率較高。但由于其是由頂向下依次劃分的結構，在數據量逐漸增大時，樹的層次結構也會隨之加深，查詢效率會受到影響[5]，此時需要重新調整單一節點的最大元素數量從而減少深度，保證查詢效率。同時，如果地理數據分布不均勻，某些子節點的深度將非常深，而一些子節點的深度則很淺，不利于組織數據，使得四叉樹索引的重心結構發生嚴重偏斜，尤其是針對數據量在千萬級甚至億級的激光點云數據上，這種傳統的四叉樹結構顯然會影響空間索引的效率，所以需要對傳統四叉樹結構和構建方式進行優化，以便解決上述問題。

2.2 改進的四叉樹空間索引結構

根據LAS文件的說明，在LAS文件的公共文件頭區，可以得到文件中的激光點云數據概要信息。包括總點數量、范圍信息，可以預估出整個LAS文件中的激光點云分布情況。而且在采集激光點云數據時，往往是采用均勻打點的方式，整個區域內的激光點云密集程度是相對一致的。根據這種特性，假設有一個深度為L的滿四叉樹（每個父節點都有四個子節點區域），其最深節點是由多個長為k寬為m的矩形區域的容器組成的，該容器用來存儲激光點云的唯一標識ID，設LAS文件中最大最 小XY坐標為（MaxX，MaxY）、（MinX，MinY），則有關系：

這里所有的變量都是已知的，調整k和m的值，可以依此直接建立四叉樹的最深一層，以最深層向上依次建立父節點容器，父節點容器存儲子節點容器的索引，根據實際需要，可以繼續向上建立父節點，這樣便建立了一套可以控制深度的改進四叉樹。

這種改進四叉樹與傳統四叉樹本質區別在于：傳統四叉樹是由最上層的根節點向下生成的，而改進四叉樹是優先構建好一個滿四叉樹的最深層，依次向上建立父節點，在向上建立父節點過程中，可以根據實際需要設定深度，不需要構建到最頂層，以便達到自由控制深度的目的。

遍歷LAS文件中的點數據，每個點數據均有XYZ坐標及遍歷時的指針位置，將三維的激光點云向二維平面投影，計算投影坐標XY，根據XY值計算該點數據所在的容器位置，假設存儲位置為（IndexX，IndexY），則有以下關系：

此時找到了容器的位置，將點的標識ID存入容器中，這樣便構成了改進四叉樹最深層結構，為了節約內存，只有容器中有元素時，才在內存中劃定一塊區域用于存儲，若容器元素數量為0，則該容器設置為NULL。

最深層構建完畢后，根據四叉樹結構反推上一級容器結構，臨近上層的容器長為2k，寬為2m，L2層級就是由L1層級推算而來（如圖2所示），四個區域分別存儲了其各自子節點容器的索引值，這樣L1層與L2層便建立起關系。以這種方式向上繼續構建父節點，可以構造任意深度的改進四叉樹，該四叉樹深度可控，同時，可根據數據量大小和數據分布情況調整容器大小，以便達到最佳的空間查詢效率，不會存在傳統四叉樹深度過深、重心偏斜的情況，同時在組織數據時更加合理，使后續的空間分析功能更加高效易用。

圖2 改進四叉樹結構

3.空間查詢的實現

以最常見的多邊形查詢為例，假設存在圖2中的激光點云數據，對其進行多邊形查詢操作，其流程（如圖3所示）：

圖3 改進四叉樹結構空間查詢流程

（1）首先判斷多邊形的最大最小XY值，可以簡單計算出該多邊形區域的空間范圍W；

（2）從改進四叉樹最深層向上遍歷，假設L層級中單個容器的空間范圍為W（L），確保W（L）＜W＜W（L＋1），根據四叉樹的結構特點，在L＋2層級必有一個容器完全包含W范圍，根據最大最小XY值可以計算出該容器的索引；

（3）拿到該容器后，找到該容器的子節點上的所有容器，根據最大最小XY值判斷哪些容器是完全包含的，這些容器下的最深節點處的容器中的點索引所指向的點將完全被包含在矩形框內部。而不完全包含的容器，則繼續向下遍歷，逐層判斷，直到最深層，判斷單點XY是否處于最大最小XY之間，如果是，歸于結果集合，如果不是則舍去。

當模擬點擊查詢或最近距離R時，假設有一輸入點，其坐標（X0，Y0），想找到離其最近的點數據來模擬點擊查詢或最近距離R范圍內查詢，其步驟（如圖4所示）：

圖4 改進四叉樹結構模擬點擊查詢流程

該查詢方式是針對改進四叉樹結構中的數據索引進行查詢，再由數據索引找到對應點。由于改進四叉樹索引的查詢本質上是將空間位置查詢轉化為數組索引的查詢，速度是十分快的，理論上性能很強，在實際應用中也驗證了這一點。改進四叉樹空間索引使得LAS數據進行高效空間查詢操作得到了可能。

4.結束語

空間索引是高效空間查詢的必要組成部分，空間索引的結構決定了空間查詢的效率。本文針對LAS激光點云數據文件格式特點，對傳統四叉樹結構空間索引進行改進，不借助任何第三方軟件建立了一套適用于LAS激光點云數據的空間索引，在激光點云處理軟件中具有很大意義，具有高效的空間索引結構意味著更多復雜算法的實現，從而豐富軟件功能，提高了軟件的可用性。傳統的LAS處理軟件旨在針對LAS數據整體進行操作，例如，濾波、分類等，空間索引的加入使得LAS數據的分析由整體變為局部，可以針對特定區域進行分析，甚至是建立拓撲分析等操作，使得海量激光點云數據的分析達到更高的層次。在黑龍江省基礎測繪項目中，針對LAS處理過程中遇到的空間查詢類問題均采用該方式進行操作，效率高、效果好，突破了第三方軟件的限制。然而，該改進四叉樹空間索引目前只是建立了改進四叉樹空間索引模型，并沒有對其中的細節進行優化，如，編碼方式、數據壓縮方式、最小單個容器最優范圍選取等，可見該改進四叉樹仍然具有優化空間，下一步將針對上面提出的細節進行優化，提升空間索引的效率，以提升軟件在實際應用時的性能。