王書民，李文寧，張愛武

(1.中國地震局地震預(yù)測研究所，北京 100036； 2. 首都師范大學(xué)三維信息獲取與應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室，北京 100048)

?

采用模糊C均值方法進(jìn)行激光點(diǎn)云分類

王書民1，李文寧2，張愛武2

(1.中國地震局地震預(yù)測研究所，北京 100036； 2. 首都師范大學(xué)三維信息獲取與應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室，北京 100048)

LiDAR波形數(shù)據(jù)的分解可以獲得地物的幾何坐標(biāo)屬性和物理屬性信息?；趲缀翁卣鞯狞c(diǎn)云分類方法較多，而對于波形特征分類方法的研究較少。本文首先對全波形數(shù)據(jù)進(jìn)行分解得到了振幅、波寬屬性，并結(jié)合振幅鄰域特征提取振幅方差，得到了具有3個(gè)屬性的激光點(diǎn)云數(shù)據(jù)；然后采用模糊C均值聚類方法進(jìn)行了激光點(diǎn)云數(shù)據(jù)的分割。試驗(yàn)使用Riegl vz-400激光掃描儀采集到的數(shù)據(jù)驗(yàn)證了算法的可行性，可成功將研究區(qū)域中的樹木、地面、建筑等進(jìn)行分類。

波形特征；振幅；波寬；模糊C均值

地面激光雷達(dá)能夠獲取發(fā)射激光脈沖與地物接觸后發(fā)射信號的全波形信息，揭示了地物的物理和幾何信息，這些信息是地物分類的重要依據(jù)。楊必勝[1]提出了一種基于空間分布特征的點(diǎn)云特征圖像生成方法，利用生成的特征圖像結(jié)合閾值分割、輪廓提取和跟蹤等理論實(shí)現(xiàn)了建筑和樹木的提取，但是此方法需要設(shè)置的閾值較多，且計(jì)算復(fù)雜，各屬性的權(quán)重難以確定。Li[2]提出了一種基于投影點(diǎn)密度的點(diǎn)云分割方法，但是此方法僅能提取房屋的邊界，對于復(fù)雜的地物則難以適用。Yan[3]利用法向量結(jié)合多尺度空間理論提出了DoN(difference of normals)特征的計(jì)算方法,應(yīng)用于點(diǎn)云的平面分割，然后結(jié)合歐氏聚類算法實(shí)現(xiàn)了點(diǎn)云的初步分割，此分割方法對于地物間距較大的區(qū)域分割效果較好，但是對于重疊地物分割效果則較差。盧秀山[4]提出了一種基于點(diǎn)云密度分布的數(shù)據(jù)格網(wǎng)化信息提取方法可以快速提取建筑物信息，但是提取精度較低。理論上如果能夠提取更多的用于分類的激光屬性信息就能夠提高分類的精度，而以上方法都只是應(yīng)用激光的幾何信息。但是目前將波形特征應(yīng)用于地物分類的研究還比較少，都偉冰[5]利用回波強(qiáng)度信息結(jié)合其他屬性進(jìn)行了道路的提取，此方法通過采樣統(tǒng)計(jì)地物回波強(qiáng)度的分布范圍，設(shè)定閾值提取道路，但僅能應(yīng)用于強(qiáng)度信息差異明顯的地物區(qū)分。駱社周[6]利用距離和角度校正后的回波強(qiáng)度提取植被用于葉面積指數(shù)反演取得了較好的效果，但不同的傳感器和掃描環(huán)境對于回波強(qiáng)度的影響不同，給回波強(qiáng)度的校正帶來了困難。

本文利用全波形激光點(diǎn)云數(shù)據(jù)的振幅、波寬屬性信息，再統(tǒng)計(jì)分析振幅屬性獲得振幅方差特征，然后采用模糊C均值(fuzzy C-means，F(xiàn)CM)聚類方法分割地物，最后通過試驗(yàn)驗(yàn)證該方法的有效性。

一、波形特征提取

1. 振幅與波寬計(jì)算

由于激光遇地物點(diǎn)返回的回波波形近似呈高斯分布，接收到的能量由多個(gè)高斯波形疊加而成，為了得到激光的振幅、波寬參數(shù)，需要波形分解方法。目前最常用的方法是阻尼高斯-牛頓法最優(yōu)化算法[7]。它根據(jù)高斯函數(shù)的標(biāo)準(zhǔn)差、波峰對應(yīng)的位置及振幅的初值利用非線性最小二乘法得到初始誤差平方和，之后不斷優(yōu)化初值，當(dāng)目標(biāo)函數(shù)的導(dǎo)數(shù)小于等于容差值或達(dá)到最大迭代次數(shù)時(shí)，停止迭代，最終得到每個(gè)目標(biāo)物的振幅和半波寬。

2. 振幅方差特征計(jì)算

振幅方差的計(jì)算主要分為基于k-d樹的鄰域搜索與方差計(jì)算兩個(gè)步驟。

(1) 基于k-d樹的鄰域搜索

首先需要明確一下最近鄰點(diǎn)的定義，假設(shè)給定一含有N個(gè)點(diǎn)的樣本集合Q，和一查詢點(diǎn)p0(p0∈Q)，則p0的最近鄰為p′，需滿足

(1)

式中，兩點(diǎn)之間的距離使用歐氏距離度量

(2)

式中，x0、y0、z0分別表示點(diǎn)p0坐標(biāo)的3個(gè)分量。

在計(jì)算點(diǎn)云鄰域時(shí)，最簡單的方法就是計(jì)算中心點(diǎn)p0與所有點(diǎn)pi(pi∈Q)的距離，然后獲得距離最近的那個(gè)點(diǎn)?？紤]到點(diǎn)云的數(shù)據(jù)量較大，如果用此方法則耗時(shí)耗力。因此，選擇構(gòu)建k-d樹加速點(diǎn)云的搜索。k-d樹是一種帶有其他約束條件的二分查找樹，對于鄰域搜索十分有用。如圖1所示，k-d樹的每一級在指定維度上分開所有的子節(jié)點(diǎn)。在樹的根部所有子節(jié)點(diǎn)是在第一個(gè)指定的維度上被分開。樹的每一級都在下一個(gè)維度上分開，所有其他的維度用完之后就回到第一個(gè)維度,從而建立k-d樹。

圖1　k-d樹劃分規(guī)則

k-d樹建立之后，進(jìn)行最近鄰搜索，首先搜索二叉樹結(jié)點(diǎn)，比較對應(yīng)分裂維值的大小，小于進(jìn)入左分支，大于進(jìn)入右分支，按照搜索路徑即可得到最近鄰近似點(diǎn)；然后返搜索路徑，判斷路徑上結(jié)點(diǎn)的其他子節(jié)點(diǎn)空間中是否存在離查詢點(diǎn)更近的點(diǎn)，如果有，則進(jìn)入到此節(jié)點(diǎn)空間進(jìn)行搜素。重復(fù)此過程即可得到中心點(diǎn)的最近鄰點(diǎn)。據(jù)此方法推廣即可得到中心點(diǎn)p0的K近鄰域點(diǎn)集Pk(k=1,2,…，K)。

(2) 方差計(jì)算

根據(jù)K近鄰搜索得到的K個(gè)鄰近點(diǎn)及其對應(yīng)的振幅，利用方差求解公式即可得到點(diǎn)p0的振幅方差

(3)

二、模糊C均值分類

FCM是用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類的程度，是一種柔性的模糊劃分。設(shè)FCM把n個(gè)點(diǎn)pi(i=1,2,…,N)分為K類，求每類的聚類中心，使得目標(biāo)函數(shù)值最小。通過模糊劃分計(jì)算每個(gè)點(diǎn)與所有類的距離獲得隸屬度u(0

(4)

(5)

(6)

由式(6)可得目標(biāo)函數(shù)J(U,c1,c2,…,cc)達(dá)到最小的必要條件為

(7)

由式(6)—式(7)可得每個(gè)類別的聚類中心及所有點(diǎn)到該類的隸屬度。FCM算法中聚類中心Ci和隸屬矩陣U的確定通過迭代獲得，如圖2所示。

圖2　FCM 分類算法流程

振幅是激光回波強(qiáng)度信息的直接表現(xiàn)，回波強(qiáng)度與地物的反射率呈正相關(guān)，即地物反射率越大激光強(qiáng)度的值越大。而反射率則由脈沖的波長、目標(biāo)的材料及其表面的明亮程度決定。因此，對于同一激光掃描儀獲得的點(diǎn)云數(shù)據(jù)，可利用點(diǎn)云的振幅不同區(qū)分目標(biāo)地物。

(8)

式中，k為常數(shù)；PR為激光雷達(dá)系統(tǒng)記錄的強(qiáng)度；R為激光距離目標(biāo)的距離；A為目標(biāo)有效相交面積；α為激光光束的入射角；μ為大氣消光系數(shù)；ρ為目標(biāo)反射率。

波寬與地物本身的性質(zhì)有關(guān)。對于機(jī)載激光雷達(dá)來說不同地物波寬的區(qū)分度較小，但是對于地面激光雷達(dá)，掃描儀距離地物較近，測量精度高，能在一定程度上反映地物的類別。通過一定的方法可以將波寬用于地物的區(qū)分。

振幅方差是地物鄰域中振幅變化程度的一種度量。由式(8)可知振幅的大小除了與地物的類型有關(guān)外，與激光的入射角、掃描儀與地物之間的距離也有很大的關(guān)系。對于建筑來說，某一激光點(diǎn)與其鄰近點(diǎn)都位于同一個(gè)平面內(nèi)，入射角相同且深度近似相等，振幅方差較小。而對于樹木點(diǎn)云，用于樹葉的不規(guī)則分布導(dǎo)致的入射角不同、激光點(diǎn)的深度存在一定的差異，其鄰域內(nèi)振幅變化較大，造成振幅方差較大。因此，通過計(jì)算振幅方差屬性用于地面激光點(diǎn)云中樹木與建筑物的分割。

高程是LiDAR數(shù)據(jù)中較穩(wěn)定的信息，是機(jī)載激光分類的一個(gè)重要屬性，但是對于地面激光雷達(dá)，高程僅能用于地面點(diǎn)的分離。因此，本文選擇波寬、振幅、振幅方差3個(gè)屬性構(gòu)建FCM特征空間。

三、試驗(yàn)與分析

本文采用Rieglvz-400激光掃描儀獲取的激光點(diǎn)云數(shù)據(jù)，試驗(yàn)場景內(nèi)包括墻面、門窗、地面、樹木、階梯式看臺等，共861 236個(gè)激光點(diǎn)，詳細(xì)分割流程如圖3所示。

圖3　點(diǎn)云數(shù)據(jù)分割流程

1. 特征計(jì)算

試驗(yàn)使用Riegl掃描儀配套的處理軟件，將波形分解為波寬、振幅兩個(gè)屬性。然后再計(jì)算振幅方差，本文選擇了10個(gè)點(diǎn)的鄰域進(jìn)行計(jì)算。經(jīng)過這種方法處理后每條記錄包含了X坐標(biāo)、Y坐標(biāo)、Z坐標(biāo)、波寬、振幅、振幅方差6個(gè)屬性。將X、Y、Z坐標(biāo)分別與波寬、振幅、振幅方差結(jié)合生成3個(gè)具有4個(gè)屬性列的表文件，如圖4—圖6所示。

圖4　按振幅顯示

圖5　按波寬顯示

圖6　按振幅方差顯示

2. 基于振幅和波寬的FCM分割

FCM是一種非監(jiān)督分類方法，但是在分類開始前需要指定分類的數(shù)目。由于本文研究區(qū)域內(nèi)主要的地物類型有5種，因此，采用非監(jiān)督分類的一般規(guī)則大于類別數(shù)的2倍，本文設(shè)為14個(gè)類別進(jìn)行試驗(yàn)。試驗(yàn)獲得的特征屬性有振幅、波寬、振幅方差，分別對不同特征組合進(jìn)行分類試驗(yàn)。考慮到振幅方差，其主要表現(xiàn)的特征為樹木與其他物體之間的區(qū)分，需要對振幅方差屬性單獨(dú)分割。因此，本文分為振幅、波寬、振幅和波寬、振幅方差4個(gè)組合，得到分類結(jié)果如圖7所示。圖7左上為按振幅進(jìn)行的FCM分類，圖7右上為按波寬進(jìn)行的FCM分類，圖7左下為按振幅與波寬進(jìn)行的FCM分類，圖7右下為按振幅方差進(jìn)行的FCM分類。

圖7　初步分割結(jié)果

3. 空間域?yàn)V波

從非監(jiān)督分類得到的結(jié)果可以看出，最后得到的結(jié)果是以單點(diǎn)的形式作為類別存在，對于一個(gè)鄰近區(qū)域中雖然某一個(gè)類別的點(diǎn)數(shù)較多，但仍然存在錯(cuò)誤點(diǎn)。因此，本文才用概率密度濾波算法對區(qū)域內(nèi)的點(diǎn)進(jìn)行平滑校正。

如圖8所示，設(shè)一點(diǎn)o，通過k-d樹搜索鄰域50個(gè)點(diǎn)，藍(lán)色點(diǎn)、綠色點(diǎn)、黃色點(diǎn)，分別標(biāo)記類別為1、2、3 其中點(diǎn)個(gè)數(shù)大小為藍(lán)色點(diǎn)>綠色點(diǎn)>黃色點(diǎn)。則將中心點(diǎn)o標(biāo)記為藍(lán)色點(diǎn)。通過此濾波算法對分類后的點(diǎn)云進(jìn)行濾波處理，如圖9所示，最終分割結(jié)果如圖10所示。

圖8　空間域?yàn)V波示意圖

圖9　空間域?yàn)V波結(jié)果

圖10　模糊C均值分類結(jié)果

通過模糊C均值進(jìn)行點(diǎn)云數(shù)據(jù)分類總體精度為92.742%，具體混淆矩陣見表1。

表1　模糊C均值分類的混淆矩陣

本文對同樣的試驗(yàn)數(shù)據(jù)進(jìn)行了k均值法分類，分類結(jié)果如圖11所示，表2是k均值法分類的誤差混淆矩陣，整體分類精度為總分類精度為90.213%，具體混淆矩陣見表2，將表1與表2進(jìn)行對比可以發(fā)現(xiàn)，F(xiàn)CM各類別的誤分類程度均小于k均值法分類的誤分。

圖11　采用k-mean分類結(jié)果

樹地面建筑門看臺樹94．4650．4141．9670．0253．128地面0．46892．1255．5160．1861．705建筑3．69810．06380．4392．7353．065門0．3590．0094．06594．2361．331看臺2．9993．0054．1080．08789．801

四、結(jié)束語

本文提出了一種結(jié)合點(diǎn)云數(shù)據(jù)的波形信息同時(shí)利用模糊C均值的分類方法，該方法利用了從激光波形數(shù)據(jù)中分離的波寬和振幅屬性，并通過分析振幅的鄰域方差獲得振幅方差屬性。較傳統(tǒng)的激光點(diǎn)云分類方法相比具有更高的分類精度，在基于激光點(diǎn)云數(shù)據(jù)的地物分類識別上具有較大應(yīng)用前景。

[1]楊必勝,魏征,李清泉，等.面向車載激光掃描點(diǎn)云快速分類的點(diǎn)云特征圖像生成方法[J]. 測繪學(xué)報(bào),2010,39(5):540-545.

[2]LI B J, LI Q Q, SHI W Z, et al. Feature Extraction and Modeling of Urban Building from Vehicle-borne Laser Scanning Data[J]. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci, 2004, 35: 934-939.

[3]IOANNOU Y, TAATI B, HARRAP R, et al. Difference of Normals as a Multi-scale Operator in Unorganized Point Clouds[C]∥3D Imaging Modeling Processing Visualization and Transmission (3DIMPVT), 2012 Second International Conference on.[S.l.]：IEEE, 2012：501-508.

[4]盧秀山,黃磊. 基于激光掃描數(shù)據(jù)的建筑物信息格網(wǎng)化提取方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2007,32(10):852-855.

[5]都偉冰,王雙亭,王春來.基于機(jī)載LiDAR粗糙度指數(shù)和回波強(qiáng)度的道路提取[J]. 測繪科學(xué)技術(shù)學(xué)報(bào),2013,30(1):63-67.

[6]駱社周,王成,張貴賓，等. 機(jī)載激光雷達(dá)森林葉面積指數(shù)反演研究[J]. 地球物理學(xué)報(bào),2013,56(5):1467-1475.

[7]MADSEN K, NIELSEN H B, TINGLEFF O. Methods for Non-linear Least Squares Problems[M]. Denmark: Informatics and Mathematical Modelling Technical University of Denmark, 2004 : 1-57.

The Classification of Laser Point Clouds Using Fuzzy C-means Method

WANG Shumin,LI Wenning,ZHANG Aiwu

王書民，李文寧，張愛武.采用模糊C均值方法進(jìn)行激光點(diǎn)云分類[J].測繪通報(bào)，2016(10)：21-24.DOI:10.13474/j.cnki.11-2246.2016.0321.

2015-10-01；

2015-11-02

中國地震局地震預(yù)測研究所基本科研業(yè)務(wù)經(jīng)費(fèi)專項(xiàng)(2014IES0203)

王書民(1985—)，男，博士，助理研究員，研究方向?yàn)橛?jì)算機(jī)視覺與攝影測量等方面。E-mail：wmcnu@163.com

P23

B

0494-0911(2016)10-0021-04