楊建思，劉 華，林 鵬

(武漢大學城市設計學院，湖北武漢 430072)

基于KD樹的點云數(shù)據(jù)自適應屏幕精度高效顯示方法

楊建思，劉 華，林 鵬

(武漢大學城市設計學院，湖北武漢 430072)

海量激光點云數(shù)據(jù)的快速顯示是目前一個技術瓶頸。本文提出一種基于KD樹的點云數(shù)據(jù)自適應屏幕精度的高效顯示方法，采用類似LOD的技術將點云進行KD樹的組織，并在KD樹節(jié)點上引入屏幕精度的概念，在點云數(shù)據(jù)顯示時，計算KD樹節(jié)點在屏幕上的投影范圍，進而決定其是否顯示點云細節(jié)。試驗證明，該算法在顯示大規(guī)模點云數(shù)據(jù)時，由于通過KD樹自適應屏幕精度調(diào)度點云數(shù)據(jù)使繪制點的數(shù)據(jù)量大大減少，從而大大加快了點云的顯示速度。

點云組織；索引；KD樹；可視化

一、引 言

機載激光雷達(light detection and ranging，Li-DAR)是激光掃描與探測系統(tǒng)的簡稱，它集激光、全球定位系統(tǒng)(GPS)和慣性導航系統(tǒng)(INS)3種技術于一體[1]，是一種通過位置、距離、角度等觀測數(shù)據(jù)直接獲取地球表面點三維坐標，從而實現(xiàn)地物信息提取和三維場景重建的對地觀測技術[2]。

為了獲取被觀測物的詳細信息，LiDAR數(shù)據(jù)的密度往往很大，使得LiDAR數(shù)據(jù)量很大，其數(shù)量通常達到GB級，在顯示系統(tǒng)中將數(shù)據(jù)點顯示出來的圖像往往非常密集，因而形象稱其為點云(pointcloud)。

目前有大量關于點云數(shù)據(jù)組織與數(shù)據(jù)結構的論文[3-10]，但大多數(shù)論文是關于點云數(shù)據(jù)結構與索引的空間利用率、平均檢索速度、內(nèi)外存調(diào)度算法及平衡性等問題的，在點云數(shù)據(jù)的可視化方面，一般是使用視口裁切去除視口外點[11-13]。已有的關于大數(shù)據(jù)量簡化顯示的辦法一般是基于三角面片的LOD，而對離散的LiDAR數(shù)據(jù)點云來說，傳統(tǒng)的LOD方法及遮擋面消除方法都不太適用。

本文提出一種基于KD樹的點云數(shù)據(jù)自適應屏幕精度的高效顯示方法。該方法類似于LOD方法[14-16]，將點云進行KD樹的組織，在KD樹節(jié)點上引入屏幕精度的概念；在點云數(shù)據(jù)顯示時，計算KD樹節(jié)點在屏幕上的投影范圍，進而決定其是否顯示點云細節(jié)。由于通過KD樹自適應屏幕精度調(diào)度點云數(shù)據(jù)可使繪制點的數(shù)據(jù)量大大減少，從而大大加快了點云的顯示速度。

二、KD樹

在數(shù)據(jù)組織結構中，二叉樹是非常簡單、高效且成熟的結構，但它僅僅適用于單維數(shù)據(jù)。LiDAR數(shù)據(jù)是三維數(shù)據(jù)，不存在某種排序能同時兼顧3個方向的維度屬性，從而不能保證原來鄰近的數(shù)據(jù)在排序以后也有鄰近的特征。

基于二叉樹向多維空間中的擴展，Bentley提出多維空間中的二叉樹索引，即KD樹[17]。KD樹將多維空間中的數(shù)據(jù)成功地在一個樹內(nèi)完成索引，但數(shù)據(jù)對插入順序非常敏感，樹的結構往往缺乏平衡性。自適應的KD樹[18]提出在建立KD樹時根據(jù)數(shù)據(jù)特征選取特定的劃分平面，使每次劃分都將空間分為數(shù)據(jù)相等的兩個子空間，但這種優(yōu)化只對靜態(tài)數(shù)據(jù)有用，對于數(shù)據(jù)的動態(tài)更新，樹的結構需要全部重新組織。

自適應的KD樹像KD樹一樣，依次選取與坐標軸垂直的平面將數(shù)據(jù)空間一分為二，其坐標軸依次在3個坐標軸之間選?。蛔赃m應的KD樹在向KD樹插入數(shù)據(jù)之前，預先計算數(shù)據(jù)點在各個方向的排序，進而選取特定的點，使得平面劃分的結果讓每個節(jié)點的左右子節(jié)點包含的點數(shù)目最多相差1。

為了使該數(shù)據(jù)結構能更好地適應點云數(shù)據(jù)的顯示，本文對自適應的KD樹作出以下改動。

1)原始的KD樹算法對劃分平面的選取為依次選取3個方向的劃分平面，這樣保證了數(shù)據(jù)的公平性，但是也造成了數(shù)據(jù)區(qū)域形狀各異，很不規(guī)則。因而筆者將劃分平面定義為使劃分的結果區(qū)域最接近正方形的劃分方式，即對需要進行劃分的區(qū)域分別計算區(qū)域在3個軸向的長度Length_X、Length_Y、Length_Z，求出其中的最大值，本次劃分將數(shù)據(jù)區(qū)域沿該軸方向一分為二，這樣能保持每個節(jié)點內(nèi)的數(shù)據(jù)在空間位置上更加相近。

2)在傳統(tǒng)KD樹中，每個節(jié)點進行細分一直到每個節(jié)點只包含一個數(shù)據(jù)點。對于海量點云數(shù)據(jù)來說，不需要將數(shù)據(jù)一直劃分到每個節(jié)點最多只有一個數(shù)據(jù)點才終止，KD樹的每個葉子節(jié)點可以有許多數(shù)據(jù)點，具體的點數(shù)或范圍可依應用而定。

對KD樹節(jié)點是否再分的標準有兩種基本的判別方法(如圖1所示)：基于點的數(shù)目，即如果某個節(jié)點內(nèi)數(shù)據(jù)點的個數(shù)小于等于N，則節(jié)點不需要再分；基于空間范圍，即如果節(jié)點數(shù)據(jù)的“尺寸”小于給定尺度R，則節(jié)點不需要再分。

圖1

基于點數(shù)的劃分標準在最近點的查找時優(yōu)勢明顯，基于空間范圍的劃分標準在優(yōu)化顯示時操作比較簡單?？紤]到基于空間范圍的劃分標準在數(shù)據(jù)空間分析時會有很大優(yōu)勢，筆者采用的劃分策略為：確定一個相對較大的空間尺度，以這個大小為空間劃分的主要標準；預先確定每個節(jié)點最多能容納的點的個數(shù)nmax，經(jīng)過空間標準劃分以后，如果某個區(qū)域內(nèi)點個數(shù)大于nmax，繼續(xù)細分至點的個數(shù)小于nmax。

本文提出的自適應屏幕精度的點云數(shù)據(jù)顯示算法不論是否采用內(nèi)外存調(diào)度策略，都能有效加快顯示速度。另一方面，自適應的KD樹在建立KD樹時，通過預先的計算使樹保持良好的靜態(tài)平衡性，從而使樹的深度減小，減少了平均查找時間，加快了處理速度。為了體現(xiàn)屏幕精度對顯示效率的提高，本文不采用內(nèi)外存調(diào)度算法，而選用比較高效的自適應的KD樹，以期更好地表現(xiàn)顯示屏幕精度算法的優(yōu)越性。

三、自適應屏幕精度顯示算法

1.自適應屏幕精度的概念

LOD最早是由Clark于1976年提出的[11]，其思想是當模型在屏幕中占據(jù)較小區(qū)域時，可以使用較粗略的模型來代替原始模型進行繪制，以便對復雜場景進行快速繪制。其核心是不繪制那些對視點來說“微不足道”的模型或模型細節(jié)，這些模型或是因為距離很遠，只需將復雜的物體用簡單的體素來渲染，或是因為太微小而根本不進行渲染。

對點云數(shù)據(jù)而言，對象是一個個數(shù)據(jù)點，不存在大小之分；每個點不論視點位置如何，投影到屏幕以后都是一個像素大小，沒有優(yōu)先之別，因而很難利用LOD算法。針對這個問題，筆者以自適應的KD樹為結構提出了樹模型中節(jié)點自適應屏幕顯示精度的算法。

首先，針對點數(shù)據(jù)是一個個沒有大小沒有體積的個體，拋棄在點的顯示中一直把一個個點當作獨立個體來看待的想法，將數(shù)據(jù)集合看作整體，即在數(shù)據(jù)組織時利用KD樹組織場景中的數(shù)據(jù)，在考慮場景中的LOD模型時把KD樹中的節(jié)點作為一個整體看待，考慮其投影到屏幕以后，如果節(jié)點內(nèi)所有點都在同一個像素區(qū)域內(nèi)，則可以將整個節(jié)點當作單點看待；如果投影到屏幕以后節(jié)點最大距離不超過半個像素，可以直接對該節(jié)點進行顯示。

因而，該思路將每個節(jié)點可以看成是一個模型，這個模型有3個細節(jié)層次：全細節(jié)模型、單點模型及零點模型。全細節(jié)模型即整個節(jié)點相對觀測點來說很大，需要將所有數(shù)據(jù)點顯示；單點模型是數(shù)據(jù)區(qū)域投影接近一個像素大小，可以將節(jié)點簡化為一個數(shù)據(jù)點；零點顯示即投影范圍很小以至于不需要進行處理。同時，注意到在樹狀結構中有父子節(jié)點的結構，因此對于全細節(jié)模型，實際上不需要顯示所有數(shù)據(jù)點，只需要分別對其子節(jié)點進行模型檢驗即可。這種樹形結構的遞歸正是該模型只需區(qū)分3個細節(jié)層次的原因。

圖2顯示了一顆簡單的KD樹，其中的數(shù)字用于標明節(jié)點半徑大小，假設該樹離觀察者距離較遠，通過計算發(fā)現(xiàn)所有半徑大于等于8的節(jié)點在屏幕上占據(jù)一個像素的范圍，則對于該樹的顯示，只會顯示其中的4個節(jié)點，對其他半徑小于8的節(jié)點，即使顯示，也只會被遮蓋，其顯示是沒有意義的。

2.自適應屏幕精度的顯示算法

如上節(jié)所述，自適應屏幕精度的顯示需要對每個節(jié)點的“大小”作一個定量的描述，以計算節(jié)點相對于觀察者來說占據(jù)了屏幕上多少像素的位置。對“大小”的計算，有基于節(jié)點的包圍盒和包圍球兩種屏幕精度算法。

圖2 采用節(jié)點半徑劃分KD樹的層次

(1)包圍盒投影法

節(jié)點的“大小”通過計算節(jié)點包圍盒到屏幕的投影范圍得到，即計算包圍盒的8個頂點投影到屏幕以后的屏幕坐標，根據(jù)這8個點的屏幕坐標確定節(jié)點是否需要細分。如果這8個二維坐標中某兩點的水平或豎直坐標差大于1.5個像素，則節(jié)點被定義為全細節(jié)；如果坐標差大于0.5個像素，即定義節(jié)點為單點模型；否則為零點模型。

圖3是推導任意點在特定視點下投影坐標的示意圖。圖中點O是觀察點，過點O沿視線方向是Z軸，向上的方向為Y軸，將Z軸與Y軸的外積作為X軸。點P是模型中的任意一點，設P在YZ、XZ的平面投影分別為E、A，A在Z軸和X軸上的投影為D、B，則AB(或DO)、PA、PE(或AD)分別為P到XY、XZ、YZ平面的距離。A′、P′、E′和D′分別是A、P、E、D投影到屏幕上的點，B′為A′在X軸的投影，C′為E′在Y軸的投影。

式中，AB、PA、PE分別為P到XY、XZ、YZ平面的距離；OD′為視點到屏幕的距離，在OpenGL中可根據(jù)gluPerspective函數(shù)參數(shù)求得。

(2)包圍球估算法

以上方法計算量比較大。實際上構建KD樹時在預處理階段把節(jié)點半徑作為參數(shù)存儲，則顯示時可以通過節(jié)點半徑在屏幕上的大小作近似估計。

如圖4所示，通過KD樹中的節(jié)點半徑信息，可以認為節(jié)點內(nèi)所有點都在圖中黑圓中。如果能用圓的直徑d代表節(jié)點尺度，則可以簡化計算。事實上對于需要判別大小的節(jié)點而言，其距離一般離視點較遠，用d來代替黑圓的誤差不大。通過計算可知，當fovy為60°時，最大誤差僅7.7%；當fovy為90°時，最大誤差也只有17%，這種誤差對節(jié)點大小的估計是允許的。

圖4 根據(jù)節(jié)點半徑估算屏幕精度

設圖中d(兩倍節(jié)點半徑)投影到屏幕以后的長度為d′，容易看出

式中，AO為點到標準面的距離；BO即包圍盒投影法中的OD′，即

對屏幕精度的判別：若d′＜1或d′＜1.5，該節(jié)點被定義為“很小”，不需要顯示其子節(jié)點。

3.基于KD樹遮擋數(shù)據(jù)的裁切方法

按照以上方式可以減少很多點的顯示，加快顯示速度。引入KD樹以后，還可以采用點(節(jié)點)的遮擋來加速繪制過程。

考慮到KD樹劃分時是在3個維度上劃分的，投影到二維平面時，在與二維平面垂直的深度上會有很多節(jié)點重疊投影到同一個像素上，樹越深，這種重疊引起的重繪越多。為了進一步提高顯示效率，可以考慮在遍歷樹結構時按照由前到后的順序遍歷，并對每個像素進行遮擋判斷，即如果屏幕上的像素已經(jīng)被正確繪制，則屏蔽掉該像素塊后面所有節(jié)點的顯示。對于屏幕像素而言，一種簡單的處理方式是引入一個BOOL型的屏幕緩沖區(qū)來存儲屏幕上的點是否已經(jīng)被繪制。

引入屏幕緩沖區(qū)以后，對每個節(jié)點的層次判斷可以再增加一個標準：如果該節(jié)點下所有點被某些已顯示的屏幕像素區(qū)域遮擋，則直接返回。在數(shù)據(jù)量很大而且屏幕像素比較多時，已繪制的屏幕像素比較密，這時遮擋會直接剔除很多遠處數(shù)據(jù)點的計算。

四、試 驗

本試驗使用的是 Intel Pentium Dual E2140 CPU、1 GB內(nèi)存、NVIDIA GeForce 8600 GT顯卡的機器，采取的數(shù)據(jù)源為一個城市的部分模型，該文件有300多萬個數(shù)據(jù)點。筆者先采用原始的KD樹對數(shù)據(jù)進行組織，并進行常規(guī)的遍歷顯示，顯示的平均時間為76 ms；再采用包圍球估算法計算屏幕精度，分別采用1.2個像素和2個像素的精確度進行顯示，結果發(fā)現(xiàn)顯示效果從視覺上幾乎都沒有區(qū)別，而顯示效率大大提高。點云顯示效果如圖5所示。

圖5 屏幕精度算法中的點云顯示結果

將3個顯示方案在不同距離視點的顯示時間繪制在圖6中。從圖中可以看出，原始的繪圖方式顯示時間不變，總是76 ms；兩種KD樹自適應屏幕精度的繪圖方式顯示時間隨著視點與模型距離的增大而減小，而且采用2個像素的屏幕精度的繪制時間要比1.2像素的顯示時間少很多。由此可以證明，該算法能有效減少點云顯示中點的繪制個數(shù)，而且在屏幕精確度要求降低的情況下，其顯示速度的加速非常明顯。

圖6 3個方案的顯示時間對比

注意到圖6中兩種屏幕精度顯示曲線的變化趨勢相當一致，因此制作了圖7所示的表，圖中顯示的是1.2個像素的精度與2個像素的精度在點的個數(shù)與顯示時間上的一致性。即盡管這兩個模型在同樣的場景下顯示時間差別很大，但它們都遵循著顯示時間與顯示點的個數(shù)成正比的規(guī)律，即對于任何顯示任務，顯示時間與顯示點的個數(shù)成正比。該結論也說明了筆者在數(shù)據(jù)處理過程中采取策略的正確性，即沒有對過多不需要顯示的點進行額外計算。

圖7 1.2個像素的精度與2個像素的精度在個數(shù)與時間上的對比

通過對上面的兩組數(shù)據(jù)進行分析，可以得出兩個結論：一是本文提出的基于KD樹的點云數(shù)據(jù)自適應屏幕精度顯示方法大大加快了顯示速度；二是由于這種算法的顯示時間與顯示點的數(shù)目成正比，在最壞的情況下對1440像素×900像素分辨率的滿屏幕場景顯示，也僅需要顯示130萬個數(shù)據(jù)點，按照筆者的推算顯示時間最多只需要50 ms，也就是說對于任何大小的點云場景，通過該方式進行精度控制，都可以實現(xiàn)每秒20幀的繪制效率。

五、結束語

本文所提出的算法通過對KD樹的改造，引入LOD算法，提出自適應屏幕精度的顯示與裁切，大大減少了點云數(shù)據(jù)繪制中點的繪制數(shù)目，從而有效加快了點云顯示速度。該算法重在將樹結構和傳統(tǒng)的LOD技術結合，提出的設計思路對所有層次模型都能有非常明顯的加速效果。

目前該算法亟待改進的方面有：在建立KD樹的時候，節(jié)點特征的選取應該根據(jù)模型本身特征選取特征點，以使其更適應應用的需求；對于建立 KD樹索引的標準，由于實際任務的不同，應用所關心的屬性也不同，需要針對點的顏色、方向等難量化的屬性建立便于量化的索引機制，以使得本算法可以實現(xiàn)多屬性的查詢功能。

[1] 李清泉，李必軍，陳靜.激光雷達測量技術及其應用研究[J].武漢測繪科技大學學報，2000，25(5)：387-392.

[2] 梁欣廉，張繼賢，李海濤，等.激光雷達數(shù)據(jù)特點[J].遙感信息，2005(3)：71-75.

[3] HENRICH A，SIX H W，WIDMAYER P.The LSD Tree： Spatial Access to Multidimensional Point and Non-point Objects[C]∥Proceeding of the 15th International Conference on Very Large Databases，1989：45-53.

[4] CLARK J H.Hierarchical Geometric Models for Visible Surface Algorithms[J].Communication of the ACM，1976(19)：547-554.

[5] BENTLEY J L.Multidimensional Binary Search Trees in Database Applications[J].IEEE Transactions on Software Engineering，2006(4)：333-340.

[6] GONG J，KE S N，ZHU Q，et al.An Efficient Point Cloud Management Method Based on a 3D R-Tree[J]. Photogrammetric Engineering＆Remote Sensing，2012， 78(4)：373-381.

[7] KOTHURI R，GODFRIND A.Pro Oracle Spatial for Oracle Database 11g[M].[S.l.]：Springer，2008.

[8] SCHN B，BERTOLOTTOA M.Storage，Manipulation，and Visualization of LiDAR Data[C]∥Proceedings of 3D-ARCH.Trento：[s.n.]，2009：25-28.

[9] RAVADA S，HORHAMMER M，BARIS M K.Point Cloud：Storage，Loading，and Visualization[C]∥National Science Foundation TeraGrid Workshop on Cyber-GIS.Washington DC：[s.n.]，2010：2-3.

[10] VOSSELMAN G.Automated Planimetric Quality Control in High Accuracy Airborne Laser Scanning Surveys[J]. ISPRS Journal of Photogrammetry and Remote Sensing，2012(74)：90-100.

[11] GEOSYSTEMS L.Leica Cyclone，3D Point Cloud Processing Software[EB/OL].2011-07-26.http：∥hds.leica-geosystems.com/en/6515.htm.

[12] 黃先鋒，陶闖.機載激光雷達點云數(shù)據(jù)的實時渲染[J].武漢大學學報：信息科學版，2005，30(11)：975-978.

[13] 支曉棟，林宗堅.基于改進四叉樹的LiDAR點云數(shù)據(jù)組織研究[J].計算機工程與應用，2010，46(9)：71-74.

[20] 龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點云數(shù)據(jù)管理方法[J].測繪學報，2012，41 (4)：597-604.

[14] 王晏民，郭明.大規(guī)模點云數(shù)據(jù)的二維與三維混合索引方法[J].測繪學報，2012，41(4)：605-612.

[15] 徐文學，楊必勝，魏征，等.多標記點過程的LiDAR點云數(shù)據(jù)建筑物和樹冠提取[J].測繪學報，2013，42 (1)：51-58.

[16] 鄭順義，周朗明.旋轉(zhuǎn)平臺點云數(shù)據(jù)的配準方法[J].測繪學報，2013，42(1)：73-79.

[17] ROBINSON J T.The K-D-B-tree：A Search Structure for Large Multidimensional Dynamic Indexes[C]∥ Proceeding of ACM SIGMOD International Conference on Management of Data，1981：10-18.

A High Efficient Display Method Based on KD Tree Index for Point-cloud Data

YANG Jiansi，LIU Hua，LIN Peng

TP391.9

B

0494-0911(2014)07-0018-05

2014-01-13

國家863計劃(170325)；國家自然科學基金(61331016)

楊建思(1963—)，女，江西樟樹人，博士，副教授，研究方向為計算機圖形學、虛擬現(xiàn)實與數(shù)字城市。

楊建思，劉華，林鵬.基于KD樹的點云數(shù)據(jù)自適應屏幕精度高效顯示方法[J].測繪通報，2014(7)：18-22.

10.13474/j.cnki.11-2246.2014.0216