基于改進(jìn)四叉樹(shù)結(jié)構(gòu)的LAS數(shù)據(jù)空間索引建立方法

陶維重 徐 瑩 楊 陽(yáng) 劉 揚(yáng)

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

0.引言

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

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

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

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

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

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

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

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

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

1.2 開(kāi)源LAS文件解析庫(kù)LIBLAS

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

2 基于改進(jìn)四叉樹(shù)的空間索引

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

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

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

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

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

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

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

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

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

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

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

圖2 改進(jìn)四叉樹(shù)結(jié)構(gòu)

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

以最常見(jiàn)的多邊形查詢?yōu)槔僭O(shè)存在圖2中的激光點(diǎn)云數(shù)據(jù)，對(duì)其進(jìn)行多邊形查詢操作，其流程（如圖3所示）：

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

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

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

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

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

圖4 改進(jìn)四叉樹(shù)結(jié)構(gòu)模擬點(diǎn)擊查詢流程

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

4.結(jié)束語(yǔ)

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