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

楊建思，劉 華，林 鵬

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

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

楊建思，劉 華，林 鵬

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

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

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

一、引 言

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

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

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

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

二、KD樹

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

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

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

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

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

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

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

圖1

基于點數的劃分標準在最近點的查找時優勢明顯，基于空間范圍的劃分標準在優化顯示時操作比較簡單。考慮到基于空間范圍的劃分標準在數據空間分析時會有很大優勢，筆者采用的劃分策略為：確定一個相對較大的空間尺度，以這個大小為空間劃分的主要標準；預先確定每個節點最多能容納的點的個數nmax，經過空間標準劃分以后，如果某個區域內點個數大于nmax，繼續細分至點的個數小于nmax。

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

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

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

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

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

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

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

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

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

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

圖2 采用節點半徑劃分KD樹的層次

(1)包圍盒投影法

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

圖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中可根據gluPerspective函數參數求得。

(2)包圍球估算法

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

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

圖4 根據節點半徑估算屏幕精度

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

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

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

3.基于KD樹遮擋數據的裁切方法

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

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

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

四、試 驗

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

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

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

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

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

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

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

五、結束語

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

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

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

[2] 梁欣廉，張繼賢，李海濤，等.激光雷達數據特點[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] 黃先鋒，陶闖.機載激光雷達點云數據的實時渲染[J].武漢大學學報：信息科學版，2005，30(11)：975-978.

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

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

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

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

[16] 鄭順義，周朗明.旋轉平臺點云數據的配準方法[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—)，女，江西樟樹人，博士，副教授，研究方向為計算機圖形學、虛擬現實與數字城市。

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

10.13474/j.cnki.11-2246.2014.0216