陶維重 徐 瑩 楊 陽 劉 揚

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

0.引言

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

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

1 LAS數(shù)據(jù)讀取方式介紹

1.1 LAS數(shù)據(jù)結(jié)構(gòu)解析

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

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

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

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

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

1.2 開源LAS文件解析庫LIBLAS

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

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

2.1 傳統(tǒng)的四叉樹空間索引結(jié)構(gòu)

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

圖1 四叉樹結(jié)構(gòu)原理

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

2.2 改進的四叉樹空間索引結(jié)構(gòu)

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

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

這種改進四叉樹與傳統(tǒng)四叉樹本質(zhì)區(qū)別在于：傳統(tǒng)四叉樹是由最上層的根節(jié)點向下生成的，而改進四叉樹是優(yōu)先構(gòu)建好一個滿四叉樹的最深層，依次向上建立父節(jié)點，在向上建立父節(jié)點過程中，可以根據(jù)實際需要設(shè)定深度，不需要構(gòu)建到最頂層，以便達到自由控制深度的目的。

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

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

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

圖2 改進四叉樹結(jié)構(gòu)

3.空間查詢的實現(xiàn)

以最常見的多邊形查詢?yōu)槔?，假設(shè)存在圖2中的激光點云數(shù)據(jù)，對其進行多邊形查詢操作，其流程（如圖3所示）：

圖3 改進四叉樹結(jié)構(gòu)空間查詢流程

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

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

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

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

圖4 改進四叉樹結(jié)構(gòu)模擬點擊查詢流程

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

4.結(jié)束語

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