方程喜，隋立春,2，朱海雄

(1. 長安大學地質工程與測繪學院，陜西 西安 710054； 2. 地理國情監(jiān)測國家測繪地理信息局工程技術研究中心，陜西 西安 710064)

用于公路勘測設計的LiDAR點云抽稀算法

方程喜1，隋立春1,2，朱海雄1

(1. 長安大學地質工程與測繪學院，陜西 西安 710054； 2. 地理國情監(jiān)測國家測繪地理信息局工程技術研究中心，陜西 西安 710064)

傳統(tǒng)的抽稀算法應用于公路點云數(shù)據抽稀時，往往存在不能很好地顧及地形特征，或者出現(xiàn)大面積點云空洞的缺陷。本文提出了一種改進的基于平均曲率算法，用于公路勘測設計中的點云數(shù)據的抽稀，該算法首先通過局部二次曲面擬合，依次求出所有點的平均曲率；然后根據平均曲率判斷地形特征，并作為判別點云數(shù)據抽稀的主要準則；最后利用標記法解決了平坦路面出現(xiàn)大面積空洞的問題。通過試驗與分析，證明了本文抽稀算法的可靠性和適用性。

公路勘測設計;LiDAR;抽稀;平均曲率;點云空洞

車載或機載激光雷達(light detection and ranging,LiDAR)移動測量技術，能快速獲取大面積、高密度、高精度的三維點云數(shù)據，是目前在大范圍內采集地形原始數(shù)據最理想、最有效的方法和手段之一，已逐步成為我國高等級公路測設中最主要的地形數(shù)據來源[1]。然而，大面積、高密度的點云數(shù)據必然會導致數(shù)據量的大幅增加，在地形復雜區(qū)域，海量點云數(shù)據有助于地形特征的表達，而對于地形起伏不大、地勢較平坦的區(qū)域，海量點云數(shù)據中則存在大量的冗余數(shù)據，這些冗余的數(shù)據不僅對地形的表達沒有任何幫助，而且會消耗大量的存儲空間，對數(shù)據的組織、處理、后期應用都帶來了諸多不便[2]。如果能對原始點云數(shù)據進行有策略的抽稀精簡，使得在減少點云數(shù)據量的同時，還能顧及地形特征，并保證地形精度，就可以有效地解決上述問題。因此，LiDAR點云數(shù)據抽稀是點云數(shù)據處理中的重要環(huán)節(jié)。

目前，國內外針對海量點云數(shù)據的抽稀算法可歸納為不顧及地形特征和顧及地形特征兩種。

不顧及地形特征的抽稀算法中比較經典的有兩種：①基于八叉樹的格網抽稀[3]。該算法利用八叉樹結構循環(huán)遞歸地將三維點云空間進行體元剖分，體元的大小控制著抽稀程度。②基于系統(tǒng)抽稀[4]。該算法首先確定采樣間隔，然后按照采樣間隔隨機抽取一點予以保留。不顧及地形特征的抽稀算法主要應用于點云的快速顯示。

顧及地形的抽稀算法主要有以下3種：①基于不規(guī)則三角網(TIN)的點云數(shù)據抽稀[5]。該算法首先對離散點云構建TIN,然后計算某一點周圍的三角面片間的法線偏差，并以此作為抽稀的判定條件。該算法能較好地顧及地形特征點，但是建立TIN的時間復雜度和空間復雜度大，效率低。②基于距離和高差的點云數(shù)據抽稀[6]。美國PAMELA女士提出的DDR(data density reduction)算法主要依靠兩個參數(shù)：搜索半徑及高差閾值。搜索半徑用來指定鄰域點云數(shù)據，高差閾值用來判定是否是冗余點。該算法利用高差作為判定條件只顧及了垂直方向上的地形特征。③基于曲率的點云數(shù)據抽稀[7-8]。該算法通過計算點云表面曲率作為抽稀判定條件，小于曲率閾值的點作為冗余點剔除，大于曲率閾值的點作為特征點予以保留。該算法能很好地顧及水平方向和垂直方向的地形特征，但是曲率閾值難以選取，而且在地勢均勻變化區(qū)域(如公路路面、斜坡)會出現(xiàn)點云空洞，對于地形精度有一定影響。鑒于已有算法的優(yōu)點和缺陷，本文提出一種改進的基于平均曲率的點云抽稀算法，該算法不僅顧及地形特征，減少冗余數(shù)據，還可避免點云空洞的出現(xiàn)。

1 改進的點云數(shù)據抽稀算法

由于曲率反映了曲面性質的重要特征，因此它是描述地形特征的主要依據之一。目前曲率的計算一般采用的方法有：圖像梯度求解法[9]、三角格網法[10]、二次曲面擬合法[11]。二次曲面擬合法計算簡單、穩(wěn)定性強、效率高，因此本文采用二次曲面擬合來計算曲率，其基本思路為：先取點云中任意一點pi(1≤i≤n，n為點云個數(shù))的k個近鄰點來進行二次曲面z(x,y)的擬合，再根據二次曲面的第一基本量和第二基本量來求出pi的平均曲率。二次曲面方程如下

z(x,y)=ax2+bxy+cy2+dx+ey+f

(1)

1.1 近鄰搜索

為了快速高效地得到海量點云數(shù)據中每個點的鄰域信息，需要對原始點云數(shù)據建立空間索引。蔣晶鈺等[12]認為KD-tree是一種組織LiDAR數(shù)據的有效方式。KD-tree由Bentley[13-14]于1975年首先提出，是一種分割k維數(shù)據空間的數(shù)據結構，主要應用于多維空間關鍵數(shù)據的搜索(如范圍搜索和k近鄰搜索)。本文采用三維KD-tree來實現(xiàn)k鄰域搜索。KD-tree的核心技術包括建樹和查找兩個部分。

1.1.1 KD-tree的建立

建立KD-tree的過程是一個遞歸的自頂向下的過程，將點云數(shù)據集所包含的整個三維空間作為根結點，用分割平面循環(huán)遞歸的按照X，Y，Z3個方向分裂，得到下級子空間作為中間結點，直到每個子空間所包含的點個數(shù)滿足預先設定的值停止分割，并作為葉子結點。分割平面的選擇通常采用以下幾種規(guī)則[15]：標準差分割規(guī)則、中點分割規(guī)則、滑動中點分割規(guī)則。KD-tree的三維空間分割示意圖如圖1所示。

圖1 KD-tree三維空間分割示意圖

1.1.2 KD-tree的查找

KD-tree的查找步驟與二叉樹相同。在對點云數(shù)據集中的點進行k近鄰查找時，在中間結點上根據分割該結點的分割平面的值與查找點對應維度的值的大小，決定是往左子空間查找還是往右子空間查找，最終搜索到所需要查找的葉子結點，在搜索過程中保存搜索路徑。找到葉子結點后，在葉子結點中搜索k個近鄰點，如果離查找點最遠的近鄰點的距離大于查找點到分割其父結點的分割平面的距離，則需要沿著搜索路徑進行回溯，直到找到k個最近鄰點。而進行范圍查找時，是通過計算搜索路徑上的點與查找點的距離是否小于搜索半徑，來找到所有滿足鄰域條件的點集。

1.2 局部二次曲面的擬合

國內外學者對鄰域數(shù)據量k的確定做了大量試驗，證明k值取24～30為最佳，太小不能滿足精度要求，太大影響計算效率[16]。因此本文k取25來進行局部二次曲面的擬合。

由數(shù)據點pi和其k個鄰域點，采用最小二乘法擬合局部二次曲面，建立目標函數(shù)為

(2)

聯(lián)立式(1)和式(2)，對各項系數(shù)求偏導，并令偏導數(shù)等于零，得到線性方程組，見式(3)，求解線性方程組，得到局部二次擬合曲面方程為

(3)

1.3 曲率的計算

將式(1)寫成曲面參數(shù)方程的形式，如下

r=(x,y,z(x,y))

(4)

記曲面參數(shù)方程的偏導數(shù)

rx，ry，rxy，rxx，ryy。

則二次曲面的第一基本量為

E=rx·rx

(5)

F=rx·ry

(6)

G=ry·ry

(7)

二次曲面第二基本量為

L=rxx·n

(8)

M=rxy·n

(9)

N=ryy·n

(10)

式中，n為單位法線

(11)

通過曲面的第一、第二基本量可求出局部曲面的高斯曲率K和平均曲率H為

(12)

(13)

1.4 點云數(shù)據抽稀策略

點云數(shù)據抽稀策略為：在顧及地形特征的前提下，點云抽稀后的點云密度應該與該點所在的曲面變化程度成正比，即在地勢平坦區(qū)域(平均曲率小)多抽稀，地形復雜區(qū)域(平均曲率大)少抽稀。

傳統(tǒng)的基于平均曲率的抽稀方法為設置一個曲率閾值，當某一點的平均曲率小于該閾值時，則將該點從點云中抽稀掉。首先，閾值難以確定，對不同點云閾值選取不同，一般采用經驗閾值，需要人為設置；其次，由于公路點云數(shù)據的特殊性，其在公路路面處非常平坦，即路面上相鄰點的曲率都非常小，抽稀后容易出現(xiàn)大面積點云空洞，對地形精度會有一定的影響。因此本文對傳統(tǒng)的基于平均曲率的算法作了兩方面改進，使其適用于公路點云數(shù)據的抽稀。具體步驟如下：

(1) 由目標點pi及其k個鄰域點擬合局部二次曲面，并計算出平均曲率Hi，遍歷所有點云。

(2) 將點云按平均曲率從小到大排序，依據抽稀率，將平均曲率排在前面的點設置標記flag=1，即待抽稀掉的非特征點，其他的點默認為0。

(3) 遍歷被標記的點，進行半徑為R的鄰域搜索，如果搜索到的鄰域點的flag全部為1，則將該點保留，并將flag設置為0，反之則抽稀掉該點。其中半徑R表示在抽稀區(qū)域處允許出現(xiàn)的點云空洞范圍上限，本文設置為3 m。

2 試驗與分析

為了檢驗本文算法針對公路點云數(shù)據的抽稀效果，在VS2013平臺上使用C++編程語言實現(xiàn)了傳統(tǒng)的基于曲率的抽稀方法和本文的改進算法。對京津唐高速公路一段點云數(shù)據(如圖2所示)，共389 916個點，點云平均密度為2.4個/m2，進行抽稀試驗，抽稀率設為50%。傳統(tǒng)的平均曲率抽稀方法結果如圖3所示，本文改進算法抽稀結果如圖4所示。

圖2 原始點云

圖3 傳統(tǒng)抽稀算法結果

圖4 本文抽稀算法結果

對比圖2—圖4可知，原始點云經過傳統(tǒng)抽稀算法和本文抽稀算法處理后，點云數(shù)據明顯減少，地形特征更加明顯。

由于測量面積較大，圖3、圖4都進行了縮小顯示，不易體現(xiàn)點云空洞的問題，因此本文還提供了抽稀結果的局部圖。圖5是傳統(tǒng)抽稀結果局部圖，圖6是本文改進抽稀結果局部圖。同時使用檢查點法(檢查點數(shù)為756個)評價抽稀后的點云數(shù)據生成數(shù)字高程模型的精度，統(tǒng)計信息見表1。

圖5 傳統(tǒng)抽稀結果局部圖

圖6 本文抽稀結果局部圖

表1 抽稀方法與DEM精度

對比圖5和圖6可發(fā)現(xiàn)，傳統(tǒng)基于平均曲率的抽稀算法存在大面積的點云空洞問題，而本文算法則沒有。結合表1，可定量分析出在相同抽稀率下，由于點云空洞的存在使得傳統(tǒng)算法的抽稀結果生成DEM的精度較低，而改進的算法抽稀結果生成DEM的精度較高，甚至與原始點云生成的DEM精度接近。

3 結 語

本文提出的用于公路點云數(shù)據的抽稀算法不僅顧及了地形特征，還解決了點云空洞的問題。在減少了LiDAR點云數(shù)據存儲空間的同時，還保證了數(shù)據的質量。研究保證數(shù)據質量符合特定工程需求的最小抽稀率，從而最大限度地減少存儲空間，是本文后續(xù)研究的重點。

[1] 趙文彥,丁瑞. 遙感技術在公路測設中的應用綜述[J].西部探礦工程,2006,18(5):231-233.

[2] 杜浩,朱俊峰,張力，等.顧及地形特征的LiDAR點云數(shù)據抽稀算法[J].測繪科學,2016,41(9):140-146.

[3] MARTIN R R, STROUD I A, MARSHAL A D. Data Reduction for Reverse Engineering,No.1068[R]. [S.l.]:Computer and Automation Institute of Hungarian Academy of Science,1996:63-69.

[4] 繆志修,齊華,王國昌,等.基于機載LiDAR數(shù)據構建的DEM抽稀算法研究[J].鐵道勘察,2010,36(4):35-40.

[5] CHEN Y H, NG C T, WANG Y Z. Data Reduction in Integrated Reverse Engineering and Rapid Prototyping[J]. International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.

[6] PAMELA S.A Data Density Deduction Algorithm for Post-processed Airborne Bathymetric Survey Data [D].Florida:University of Florida,2000.

[7] 周煜,張萬兵,杜發(fā)榮,等. 散亂點云數(shù)據的曲率精簡算法[J]. 北京理工大學學報,2010,30(7):785-789.

[8] 蔡志敏,王晏民,黃明.基于KD樹散亂點云數(shù)據的Guass平均曲率精簡算法[J].測繪通報,2013(S1):44-46.

[9] 張濟忠. 分形[M]. 北京:清華大學出版社,1995.

[10] 龍毅. 擴展分維模型在地圖目標空間信息描述中的應用研究[D]. 武漢:武漢大學,2002.

[11] 王厚祥.海圖制圖綜合[M]. 大連:大連艦艇學院,1998.

[12] 蔣晶玨,張祖勛，明英. 復雜城市環(huán)境的機載LiDAR點云濾波[J]. 武漢大學學報(信息科學版),2007,32(5): 303-306.

[13] FINKEL R A， BENTLEY J L. Quad Trees a Data Structure for Retrieval on Composite Keys[J]. Acta Informatica,1974,4(1):1-9.

[14] BENTLEY J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM, 1975, 18(9):509.

[15] ARYA S, MOUNT D M, NETANYAHU N S, et al. An Optimal Algorithm for Approximate Neraest Neighbor Searching [J]. Journal of the ACM,1998,45: 891-923.

[16] FALCONER K.分形幾何：數(shù)學基礎及其應用[M]. 曾文曲，譯.沈陽：東北大學出版社,1991.

LiDARPointCloudThinningAlgorithmforRoadSurveyandDesign

FANG Chengxi1，SUI Lichun1,2，ZHU Haixiong1
(1. College of Geology Engineering and Geomatics, Chang’an University, Xi’an 710054, China; 2. National Administration of Surveying, Mapping and Geoinformation Engineering Research Center of Geographic National Conditions Monitoring, Xi’an 710064, China)

When the traditional thinning algorithm is applied to data extraction of road point cloud, there are many defects, such as cannot take good account of terrain features, or appear the large area point cloud hole. In this paper, an improved algorithm based on mean curvature is proposed for the extraction of point cloud data in road survey and design. Firstly, the mean curvature of all points is obtained by local quadratic surface fitting. And then according to the mean curvature to determine the terrain features, and as the main criteria for the identification of point cloud data dilution. Finally, the problem of the large area point cloud hole in the flat road surface is solved by using the marking method. Through the experimental results and analysis, the reliability and applicability of the thinning algorithm are proved.

road survey and design; LiDAR; thinning; mean curvature; point cloud hole

方程喜，隋立春，朱海雄.用于公路勘測設計的LiDAR點云抽稀算法[J].測繪通報，2017(10)：58-61.

10.13474/j.cnki.11-2246.2017.0316.

2017-05-24

國家自然科學基金(41372330)

方程喜(1991—)，男，碩士，主要研究方向為LiDAR點云抽稀。E-mail:1358423791@qq.com

P237

A

0494-0911(2017)10-0058-04