基于紅黑樹(shù)與K-D樹(shù)的LiDAR數(shù)據(jù)組織管理

吳波濤，張 煜，陳文龍，沈定濤，魏思奇

(1.云南省水利水電勘測(cè)設(shè)計(jì)研究院，昆明 650021；2.長(zhǎng)江科學(xué)院 空間信息技術(shù)應(yīng)用研究所，武漢 430010)

?

基于紅黑樹(shù)與K-D樹(shù)的LiDAR數(shù)據(jù)組織管理

吳波濤1，張 煜2，陳文龍2，沈定濤2，魏思奇2

(1.云南省水利水電勘測(cè)設(shè)計(jì)研究院，昆明 650021；2.長(zhǎng)江科學(xué)院 空間信息技術(shù)應(yīng)用研究所，武漢 430010)

LiDAR點(diǎn)云是由海量的激光離散腳點(diǎn)組成的三維點(diǎn)集，在平面以及垂直方向上均分布有數(shù)量不均的離散點(diǎn)。LiDAR點(diǎn)云離散點(diǎn)相互之間缺乏空間拓?fù)潢P(guān)系，所以建立適當(dāng)?shù)臄?shù)據(jù)組織結(jié)構(gòu)對(duì)LiDAR點(diǎn)云進(jìn)行組織是對(duì)LiDAR點(diǎn)云進(jìn)行處理的基礎(chǔ)。根據(jù)LiDAR點(diǎn)云的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，利用紅黑樹(shù)與K-D樹(shù)建立一種“非空”規(guī)則立方體格網(wǎng)和K-D樹(shù)相結(jié)合的雙層次數(shù)據(jù)結(jié)構(gòu)，用于LiDAR點(diǎn)云的組織管理，從而降低結(jié)構(gòu)冗余和提高索引效率。

LiDAR；紅黑樹(shù)；K-D樹(shù)；數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)組織；立方體網(wǎng)格

1 研究背景

LiDAR點(diǎn)云是由海量的激光離散腳點(diǎn)組成的三維點(diǎn)集，每個(gè)三維坐標(biāo)點(diǎn)除了空間坐標(biāo)外還有與掃描地物相關(guān)的額外屬性，使得一個(gè)掃描區(qū)的LiDAR點(diǎn)云數(shù)據(jù)的信息量一般非常巨大。此外與柵格數(shù)據(jù)的二維結(jié)構(gòu)不同，LiDAR點(diǎn)云是一種三維的空間數(shù)據(jù)，即在各個(gè)垂直方向上還分布有數(shù)量不均的離散點(diǎn)。LiDAR點(diǎn)云這種不同于以往的新特性，無(wú)論是在數(shù)據(jù)存儲(chǔ)方式上還是在數(shù)據(jù)組織管理上都帶來(lái)了頗具難度的挑戰(zhàn)。

以往LiDAR點(diǎn)云數(shù)據(jù)的存儲(chǔ)格式都是由各個(gè)LiDAR系統(tǒng)制造商自行決定的，有采用ASCII形式直接提供原始點(diǎn)云數(shù)據(jù)的，也有提供已經(jīng)插過(guò)值的格網(wǎng)數(shù)據(jù)的，提供的屬性和占用空間也是各不相同，這給LiDAR數(shù)據(jù)在不同硬件和軟件下的共享和處理帶來(lái)許多不便。為了改變LiDAR數(shù)據(jù)存儲(chǔ)格式不統(tǒng)一的局面，美國(guó)攝影測(cè)量與遙感協(xié)會(huì)(American Society for Photogrammetry and Remote Sensing)提出了LiDAR點(diǎn)云數(shù)據(jù)的存儲(chǔ)格式標(biāo)準(zhǔn)——LAS[1]，LAS經(jīng)過(guò)數(shù)個(gè)版本的發(fā)展而趨于成熟，并被各個(gè)LiDAR廠商所支持，已經(jīng)成為L(zhǎng)iDAR數(shù)據(jù)比較常用的存儲(chǔ)格式。相比較LiDAR點(diǎn)云物理存儲(chǔ)格式的逐漸成熟，LiDAR點(diǎn)云分析處理時(shí)的具體組織管理卻沒(méi)有統(tǒng)一而成熟的數(shù)據(jù)結(jié)構(gòu)方案，常用的分別有插值格網(wǎng)、不規(guī)則三角網(wǎng)、八叉樹(shù)等方式，這些LiDAR數(shù)據(jù)組織方式有著各自的適用范圍和缺點(diǎn)。

本文根據(jù)LiDAR點(diǎn)云的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，探索一種雙層次雙類型索引的混合點(diǎn)云數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)結(jié)構(gòu)的低冗余和快速空間檢索。

2 常用LiDAR點(diǎn)云數(shù)據(jù)組織方式

LiDAR點(diǎn)云最直觀的特點(diǎn)就是數(shù)據(jù)規(guī)模龐大，而且離散點(diǎn)分布不規(guī)則，相互之間缺乏空間拓?fù)潢P(guān)系，這給LiDAR點(diǎn)云的空間搜索和地理分析帶來(lái)了很大的困難，所以建立高效的數(shù)據(jù)組織結(jié)構(gòu)對(duì)LiDAR點(diǎn)云來(lái)說(shuō)是非常重要的。目前，應(yīng)用較為廣泛的LiDAR點(diǎn)云組織方式主要有：規(guī)則格網(wǎng)、不規(guī)則三角網(wǎng)、八叉樹(shù)等。

2.1 規(guī)則格網(wǎng)組織方式

規(guī)則格網(wǎng)是LiDAR點(diǎn)云組織研究中應(yīng)用較早的一種數(shù)據(jù)結(jié)構(gòu)[2-4]。規(guī)則格網(wǎng)是將整個(gè)LiDAR點(diǎn)云的平面覆蓋區(qū)域劃分為固定大小方格網(wǎng)，每個(gè)格網(wǎng)內(nèi)部都包含若干數(shù)目的LiDAR離散點(diǎn)。規(guī)則格網(wǎng)的優(yōu)點(diǎn)是構(gòu)造簡(jiǎn)單、快速而且易于編碼[5]，但是，當(dāng)LiDAR點(diǎn)云在各個(gè)位置分布不均時(shí)，會(huì)造成離散點(diǎn)的空間檢索效率急劇降低。

2.2 不規(guī)則三角網(wǎng)組織方式

使用不規(guī)則三角網(wǎng)對(duì)LiDAR點(diǎn)云這種不規(guī)則的離散點(diǎn)數(shù)據(jù)集進(jìn)行組織，能夠很大程度上保留離散點(diǎn)的原始形態(tài)，不會(huì)造成嚴(yán)重的數(shù)據(jù)結(jié)構(gòu)冗余，所以也有不少的研究者使用不規(guī)則三角網(wǎng)來(lái)對(duì)LiDAR點(diǎn)云進(jìn)行組織和管理[6-8]。但是三角網(wǎng)的構(gòu)造復(fù)雜，點(diǎn)云的海量數(shù)據(jù)規(guī)模使得三角網(wǎng)的構(gòu)造相對(duì)費(fèi)時(shí)，對(duì)于有突出變化的數(shù)據(jù)集組織效果較差。

2.3 八叉樹(shù)組織方式

規(guī)則格網(wǎng)和不規(guī)則三角網(wǎng)都是以平面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，八叉樹(shù)則是一種用于描述三維空間的樹(shù)狀數(shù)據(jù)組織方式[9]。由于LiDAR點(diǎn)云就是一種三維數(shù)據(jù)，且在八叉樹(shù)構(gòu)造中離散點(diǎn)的歸屬很容易劃分，所以使用八叉樹(shù)來(lái)組織LiDAR點(diǎn)云具有很大的優(yōu)勢(shì)[10-11]。如果LiDAR點(diǎn)云的分布不均，很容易造成八叉樹(shù)層次太深，降低LiDAR點(diǎn)云的空間索引效率。

3 LiDAR點(diǎn)云雙層次雙索引數(shù)據(jù)結(jié)構(gòu)的建立

從LiDAR點(diǎn)云常用組織方式的分析可以看出，只使用一種數(shù)據(jù)結(jié)構(gòu)對(duì)LiDAR點(diǎn)云進(jìn)行組織，在構(gòu)造速度、數(shù)據(jù)冗余、檢索效率等方面難以達(dá)到平衡和高效。本文研究將“非空”規(guī)則立方體格網(wǎng)和K-D樹(shù)相結(jié)合，采用在不同數(shù)據(jù)范圍下使用相對(duì)應(yīng)的空間數(shù)據(jù)結(jié)構(gòu)并相互結(jié)合的方式建立LiDAR點(diǎn)云的數(shù)據(jù)管理和組織方式。

3.1 LiDAR數(shù)據(jù)組織方式的概念設(shè)計(jì)

從大尺度看，LiDAR點(diǎn)云構(gòu)成了可以目視分辨的地表和各種地物，在一定程度上具有地理的連續(xù)性；從小尺度看，LiDAR點(diǎn)云又是一個(gè)個(gè)離散點(diǎn)，相互之間沒(méi)有直接的聯(lián)系(圖1)。

圖1 點(diǎn)云不同尺度范圍Fig.1 Different scales of point cloud

這種大、小尺度上的差異，沒(méi)有一種數(shù)據(jù)結(jié)構(gòu)能涵蓋解決，只有運(yùn)用不同類型的數(shù)據(jù)組織方式能夠比較好地解決對(duì)應(yīng)的其中一種尺度的組織問(wèn)題。本文運(yùn)用不同類型的數(shù)據(jù)結(jié)構(gòu)，首先在大尺度的整體范圍上，使用“非空”規(guī)則立方體格網(wǎng)對(duì)LiDAR點(diǎn)云進(jìn)行初次劃分組織，組織方式就是在三維空間里將點(diǎn)云范圍用一定的邊長(zhǎng)劃分立體格網(wǎng)，使得若干個(gè)立方體組成的格網(wǎng)完整包圍點(diǎn)云。由于點(diǎn)云可能存在分布不均的現(xiàn)象，所以會(huì)有某些立方體內(nèi)沒(méi)有包含LiDAR離散點(diǎn)，這種空立方體將會(huì)從格網(wǎng)中排除，即格網(wǎng)是由包含有一定數(shù)量離散點(diǎn)的“非空”立方體組成的“非空”規(guī)則立方體格網(wǎng)，使用這種非空的立方體格網(wǎng)能夠避免數(shù)據(jù)冗余，同時(shí)在鄰近搜索時(shí)也避免了對(duì)于空立方體的檢索，每個(gè)立方體都有根據(jù)其空間位置而賦予的編號(hào)，這樣對(duì)于某個(gè)或者某些離散點(diǎn)的空間位置就能快速初步定位。

由于“非空”規(guī)則立方體格網(wǎng)構(gòu)造簡(jiǎn)單、查詢效率高，而且一定程度上避免了空立方體的冗余，所以對(duì)于LiDAR點(diǎn)云的初步大尺度組織是比較好的。此時(shí)，在每個(gè)立方體的內(nèi)部，由若干數(shù)量的LiDAR離散點(diǎn)構(gòu)成了LiDAR點(diǎn)云的小尺度范圍，在這個(gè)尺度上，離散點(diǎn)的數(shù)量相對(duì)不多，利用K-D樹(shù)對(duì)立方體內(nèi)的離散點(diǎn)進(jìn)行再組織就形成一顆層次明顯的查詢樹(shù)，這樣組織內(nèi)部離散點(diǎn)可以實(shí)現(xiàn)LiDAR點(diǎn)的精確快速定位和數(shù)據(jù)結(jié)構(gòu)上的低冗余，而且由于立方體內(nèi)部的離散點(diǎn)數(shù)量有限且比較均勻，使得內(nèi)部K-D樹(shù)的構(gòu)造費(fèi)時(shí)較少，結(jié)構(gòu)也比較平衡，能夠進(jìn)一步提高空間檢索效率。通過(guò)這種大范圍初次組織、內(nèi)部小范圍再次組織，不同類型數(shù)據(jù)結(jié)構(gòu)相結(jié)合的方式，就形成了LiDAR點(diǎn)云的雙層次雙索引數(shù)據(jù)結(jié)構(gòu)(圖2)。

圖2 雙層次雙索引數(shù)據(jù)結(jié)構(gòu)示意圖Fig.2 Two-level double-indexing data structure

雙層次雙索引數(shù)據(jù)結(jié)構(gòu)將LiDAR點(diǎn)云分為不同層次分別進(jìn)行組織，然后再綜合統(tǒng)一為整體結(jié)構(gòu)。對(duì)于數(shù)據(jù)的空間檢索先沿著大尺度定位至立方體網(wǎng)格，接著在立方體內(nèi)部使用空間樹(shù)精確定位的路線，根據(jù)LiDAR點(diǎn)云的數(shù)據(jù)特征，利用了不同類型數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)，從而達(dá)到較高效率和有效組織的目標(biāo)。

3.2 LiDAR數(shù)據(jù)組織方式的具體實(shí)現(xiàn)

LiDAR點(diǎn)云的雙層次雙索引數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)是外圍為“非空”規(guī)則立方體格網(wǎng)，內(nèi)層為空間K-D樹(shù)的2層結(jié)構(gòu)，需要采用特定的物理結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

外層的“非空”規(guī)則立方體格網(wǎng)雖然具有類似普通格網(wǎng)的性質(zhì)，但是由于“非空”格網(wǎng)的網(wǎng)格排列存在不連續(xù)性，所以不能采用連續(xù)數(shù)組來(lái)表達(dá)，本文選取紅黑樹(shù)[12]來(lái)實(shí)現(xiàn)“非空”規(guī)則立方體格網(wǎng)的物理結(jié)構(gòu)。紅黑樹(shù)是一種具有自平衡特性的二叉查找樹(shù)，所謂自平衡指的是在對(duì)紅黑樹(shù)進(jìn)行插入和刪除節(jié)點(diǎn)的時(shí)候，紅黑樹(shù)能調(diào)整自身的結(jié)構(gòu)從而確保樹(shù)結(jié)構(gòu)大致平衡。紅黑樹(shù)的一個(gè)關(guān)鍵特性是查找的最長(zhǎng)路徑總是在最短路徑的2倍以下，這個(gè)特性確保了紅黑樹(shù)具有極好的查找效率，是目前查找樹(shù)中性能突出的一種結(jié)構(gòu)[13]。

“非空”規(guī)則立方體格網(wǎng)是一種三維結(jié)構(gòu)，確定一個(gè)立方體網(wǎng)格需要通過(guò)x，y，z3個(gè)索引來(lái)查找，而紅黑樹(shù)是只能用于1個(gè)維度檢索的二叉樹(shù)，所以需要將“非空”規(guī)則立方體格網(wǎng)分解為3個(gè)維度，每個(gè)維度都用1顆紅黑樹(shù)來(lái)組織。具體來(lái)說(shuō)，首先以立方體的x索引作為比較值，使用紅黑樹(shù)進(jìn)行第1層組織，每個(gè)節(jié)點(diǎn)存儲(chǔ)了同一x位置下的立方體構(gòu)成的yz平面，對(duì)每個(gè)節(jié)點(diǎn)的yz平面以y索引為比較值繼續(xù)使用紅黑樹(shù)進(jìn)行第2層組織，此時(shí)第2層的紅黑樹(shù)的每個(gè)節(jié)點(diǎn)就存儲(chǔ)了同一y位置下的一列立方體，同樣對(duì)這一列立方體使用紅黑樹(shù)進(jìn)行以z索引為查找值的第3層組織，這樣使用3層紅黑樹(shù)分別索引3個(gè)維度坐標(biāo)，就構(gòu)成了“非空”規(guī)則立方體格網(wǎng)的整體物理實(shí)現(xiàn)結(jié)構(gòu)(圖3)。

圖3 “非空”規(guī)則立方體格網(wǎng)實(shí)現(xiàn)結(jié)構(gòu)示意圖Fig.3 Implementation of “non-null” regular cube grid structure

在每個(gè)立方體內(nèi)部，則對(duì)其所包含的離散點(diǎn)集進(jìn)行最終層次的組織，由于離散點(diǎn)的數(shù)量相對(duì)較少，直接采用3個(gè)維度的K-D樹(shù)將這些LiDAR點(diǎn)構(gòu)造成1顆查詢樹(shù)，建立K-D樹(shù)時(shí)，仍然使用常用的構(gòu)造方式，即輪流使用x,y,z維度作為劃分維度，并按照離散點(diǎn)的編號(hào)依次進(jìn)行劃分。至此，立方體格網(wǎng)的內(nèi)部層次也組織完畢，這樣就形成了用于LiDAR點(diǎn)云組織的外圍、內(nèi)層2個(gè)層次和格網(wǎng)、查詢樹(shù)2種空間索引的混合數(shù)據(jù)結(jié)構(gòu)。

LiDAR點(diǎn)云雙層次雙索引數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn),如圖4所示。

圖4 雙層次雙索引數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)Fig.4 Implementation diagram of two-level double-indexing data structure

4 結(jié) 論

LiDAR點(diǎn)云的數(shù)據(jù)量非常龐大，而且激光腳點(diǎn)之間缺乏空間關(guān)聯(lián)信息，對(duì)LiDAR點(diǎn)云進(jìn)行分析處理前必須將點(diǎn)云數(shù)據(jù)通過(guò)一定的方式組織起來(lái)。

本文提出建立雙層次雙索引混合空間索引的方式對(duì)LiDAR點(diǎn)云數(shù)據(jù)進(jìn)行組織管理，雙層次雙索引數(shù)據(jù)結(jié)構(gòu)利用“非空”規(guī)則立方體格網(wǎng)和三維K-D樹(shù)對(duì)點(diǎn)云的大、小尺度范圍分別進(jìn)行組織，并統(tǒng)一為整體結(jié)構(gòu)，在物理實(shí)現(xiàn)上則采用了紅黑樹(shù)、K-D樹(shù)等高效的數(shù)據(jù)結(jié)構(gòu)作為實(shí)現(xiàn)基礎(chǔ)。通過(guò)這種多層劃分、多種索引類型混合組織的方式，可擺脫單一類型空間索引應(yīng)用在LiDAR點(diǎn)云上的索引效率低和結(jié)構(gòu)冗余問(wèn)題，為L(zhǎng)iDAR點(diǎn)云數(shù)據(jù)組織管理的研究提供一定方向上的啟示。

[1]SAMBERG A. An Implementation of the ASPRS LAS Standard[C]∥Proceedings of the ISPRS Workshop on Laser Scanning and SilviLaser. Espoo, Finland. September 12-14, 2007: 363-372.

[2] CHARANIYA A P,MANDUCHI R,LODHA S K.Supervised Parametric Classification of Aerial LiDAR Data[C]∥Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW04) Volume 3. IEEE Computer Society Washington, DC, USA, 2004: 30.[3] DONOGHUE N M, WATT P J, NICHOLAS J,etal. Remote Sensing of Species Mixtures in Conifer Plantations Using LiDAR Height and Intensity Data[J]. Remote Sensing of Environment, 2007, 110(4): 509-522.

[4] POPESCU S C, WYNNE R H, NELSON R F. Estimating Plot-level Tree Heights with LiDAR: Local Filtering with a Canopy-height Based Variable Window Size[J]. Computers and Electronics in Agriculture, 2002, 37(1): 71-95.

[5] PIEGL L A. TILLER W. Algorithm for Finding All k Nearest Neighbors[J]. Computer-Aided Design, 2002, 34(2): 167 - 172.

[6] ZENG Qi-hong,LAI Jia-zhen,XI Xian-hua,etal.Simple Building Reconstruction from LIDAR Point Cloud[C]∥Proceedings of the 2008 International Conference on Audio, Language and Image Processing. IEEE. Shanghai, China, July 7-9, 2008:1040-1044.

[7] WANG Z, SCHENK T. Building Extraction and Reconstruction from LiDAR Data[J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B3/2): 958-964.

[8] ZHANG K, CHEN S C, WHITMAN D,etal. A Progressive Morphological Filter for Removing Nonground Measurements from Airborne LIDAR Data[J]. IEEE Transactions on Geoscience and Remote Sensing, 2003, 41(4): 872-882.

[9] 李清泉,李德仁. 八叉樹(shù)的三維行程編碼[J]. 武漢測(cè)繪科技大學(xué)學(xué)報(bào), 1997,22(2): 102-106.

[10]LINH T H, LAEFER D F. Octree-based, Automatic Building Fa?ade Generation from LiDAR Data[J]. Computer-Aided Design, 2014, 53: 46-61.

[11]WANG M, TSENG Y. LiDAR Data Segmentation and Classification Based on Octree Structure[J]. Parameters, 2004,1:5.

[12]BAYER R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms[J]. Acta Informatica, 1972, 1(4): 290-306.

[13]HANKE S. The Performance of Concurrent Red-black Tree Algorithms[M]. New York: Springer, 1999.

(編輯：王 慰)

Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree

WU Bo-tao1, ZHANG Yu2, CHEN Wen-long2, SHEN Ding-tao2, Wei Si-qi2

(1.Yunnan Institute of Water & Hydropower Engineering Investigation, Design and Research, Kunming 650021, China; 2.Spatial Information Technology Application Department, Yangtze River Scientific Research Institute, Wuhan 430010, China)

LiDAR point cloud is a 3D point set composed of massive discrete laser dots which exist in both plane and vertical directions. Because of lacking space topological relations among the discrete dots of LiDAR point cloud, it is important to establish an appropriate data structure for LiDAR point cloud as the foundation of LiDAR processing. According to the structural characteristics of LiDAR point cloud data, a two-level data structure with “non-null” regular cube grid and K-D tree is established for the organization and management LiDAR point cloud using red-black tree and K-D tree to build. The structure could reduce the structural redundancy and improve indexing efficiency.

LiDAR; red-black tree; K-D tree; data structure; data organization; regular cube grid

2016-08-20

云南省水利廳水資源費(fèi)項(xiàng)目(41501558)；云南省水利重大科技項(xiàng)目(CKSK2015852/KJ)

吳波濤(1970-)，男，云南呈貢人，高級(jí)工程師，研究方向?yàn)楣こ虦y(cè)量與攝影測(cè)量，(電話)13987116160(電子信箱)wbt5190523@126.com。

張 煜(1971-)，男，山東陽(yáng)谷人，高級(jí)工程師，博士，研究方向?yàn)閿z影測(cè)量與遙感，(電話)18986061273(電子信箱)zhangyu_1999@126.com。

10.11988/ckyyb.20160854

2016,33(11):32-35

TP317.4

A

1001-5485(2016)11-0032-04