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

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

用于公路勘測設(shè)計(jì)的LiDAR點(diǎn)云抽稀算法

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

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

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

公路勘測設(shè)計(jì);LiDAR;抽稀;平均曲率;點(diǎn)云空洞

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

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

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

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

1 改進(jìn)的點(diǎn)云數(shù)據(jù)抽稀算法

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

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

(1)

1.1 近鄰搜索

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

1.1.1 KD-tree的建立

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

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

1.1.2 KD-tree的查找

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

1.2 局部二次曲面的擬合

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

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

(2)

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

(3)

1.3 曲率的計(jì)算

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

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

(4)

記曲面參數(shù)方程的偏導(dǎo)數(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 點(diǎn)云數(shù)據(jù)抽稀策略

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

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

(1) 由目標(biāo)點(diǎn)pi及其k個(gè)鄰域點(diǎn)擬合局部二次曲面，并計(jì)算出平均曲率Hi，遍歷所有點(diǎn)云。

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

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

2 試驗(yàn)與分析

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

圖2 原始點(diǎn)云

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

圖4 本文抽稀算法結(jié)果

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

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

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

圖6 本文抽稀結(jié)果局部圖

表1 抽稀方法與DEM精度

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

3 結(jié) 語

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

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

[2] 杜浩,朱俊峰,張力，等.顧及地形特征的LiDAR點(diǎn)云數(shù)據(jù)抽稀算法[J].測繪科學(xué),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] 繆志修,齊華,王國昌,等.基于機(jī)載LiDAR數(shù)據(jù)構(gòu)建的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ā)榮,等. 散亂點(diǎn)云數(shù)據(jù)的曲率精簡算法[J]. 北京理工大學(xué)學(xué)報(bào),2010,30(7):785-789.

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

[9] 張濟(jì)忠. 分形[M]. 北京:清華大學(xué)出版社,1995.

[10] 龍毅. 擴(kuò)展分維模型在地圖目標(biāo)空間信息描述中的應(yīng)用研究[D]. 武漢:武漢大學(xué),2002.

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

[12] 蔣晶玨,張祖勛，明英. 復(fù)雜城市環(huán)境的機(jī)載LiDAR點(diǎn)云濾波[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),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ù)學(xué)基礎(chǔ)及其應(yīng)用[M]. 曾文曲，譯.沈陽：東北大學(xué)出版社,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

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

10.13474/j.cnki.11-2246.2017.0316.

2017-05-24

國家自然科學(xué)基金(41372330)

方程喜(1991—)，男，碩士，主要研究方向?yàn)長iDAR點(diǎn)云抽稀。E-mail:1358423791@qq.com

P237

A

0494-0911(2017)10-0058-04