利用PCA-BP算法進(jìn)行激光點(diǎn)云分類(lèi)方法研究

張 蕊，李廣云，李明磊，王石巖

(1.信息工程大學(xué)導(dǎo)航與空天目標(biāo)工程學(xué)院，河南鄭州 450001；2.華北水利水電大學(xué)軟件學(xué)院，河南鄭州 450011；3.河南省基礎(chǔ)地理信息中心，河南鄭州 450003)

利用PCA-BP算法進(jìn)行激光點(diǎn)云分類(lèi)方法研究

張 蕊1，2，李廣云1，李明磊1，王石巖3

(1.信息工程大學(xué)導(dǎo)航與空天目標(biāo)工程學(xué)院，河南鄭州 450001；2.華北水利水電大學(xué)軟件學(xué)院，河南鄭州 450011；3.河南省基礎(chǔ)地理信息中心，河南鄭州 450003)

在闡述現(xiàn)有激光點(diǎn)云分類(lèi)技術(shù)的基礎(chǔ)上，為滿(mǎn)足高精度、高速度、高可靠性、自動(dòng)化的數(shù)據(jù)處理要求，著重研究了基于主成分分析(PCA)和BP神經(jīng)網(wǎng)絡(luò)的激光點(diǎn)云分類(lèi)方法，并通過(guò)真實(shí)激光掃描數(shù)據(jù)進(jìn)行試驗(yàn)，將建筑物和樹(shù)葉有效分類(lèi)，達(dá)到了預(yù)期效果。

激光點(diǎn)云；數(shù)據(jù)處理；主成分分析(PCA)；BP神經(jīng)網(wǎng)絡(luò)；點(diǎn)云分類(lèi)

一、引 言

隨著三維激光掃描技術(shù)的普及和發(fā)展，空間數(shù)據(jù)的獲取從傳統(tǒng)的單點(diǎn)數(shù)據(jù)采集向連續(xù)的、密集型自動(dòng)數(shù)據(jù)獲取技術(shù)轉(zhuǎn)變，從而大大增加了數(shù)據(jù)采集量，提高了效率，使專(zhuān)業(yè)技術(shù)人員突破了傳統(tǒng)的數(shù)據(jù)處理模式，改進(jìn)了數(shù)據(jù)處理理論和方法；尤其對(duì)于由激光掃描獲取的海量點(diǎn)云數(shù)據(jù)的后期處理，迫切需要高精度、高速度、高可靠性、自動(dòng)化的數(shù)據(jù)處理技術(shù)，以滿(mǎn)足穩(wěn)定高效的數(shù)據(jù)處理要求，這不僅是測(cè)繪領(lǐng)域熱衷的研究方向，同時(shí)由于圖形、圖像處理技術(shù)和大數(shù)據(jù)處理技術(shù)等滲透其中，也成為計(jì)算機(jī)領(lǐng)域近年來(lái)研究的熱點(diǎn)。

點(diǎn)云分類(lèi)是三維激光掃描數(shù)據(jù)處理的重點(diǎn)和熱點(diǎn)問(wèn)題，也是點(diǎn)云數(shù)據(jù)處理的一項(xiàng)關(guān)鍵工作。而人工神經(jīng)網(wǎng)絡(luò)具有許多優(yōu)良特性，如具有較強(qiáng)的容錯(cuò)性，能夠識(shí)別帶有噪聲的數(shù)據(jù)；具有較強(qiáng)的自適應(yīng)學(xué)習(xí)能力；采用并行工作方式，匹配速度快等。這些特性對(duì)解決海量激光點(diǎn)云分類(lèi)問(wèn)題是非常適合的。

二、現(xiàn)有激光點(diǎn)云分類(lèi)技術(shù)

激光掃描點(diǎn)云中既含有地面點(diǎn)又包含地物點(diǎn)，若要進(jìn)行地物的提取和建筑物的三維重建，需要將植被、電線(xiàn)桿、建筑物、道路等進(jìn)行區(qū)分，得到不同類(lèi)型的點(diǎn)云系列，即激光掃描點(diǎn)云數(shù)據(jù)的分類(lèi)。

目前，對(duì)于激光點(diǎn)云分類(lèi)的研究主要體現(xiàn)在道路、植被和建筑物的提取等幾個(gè)方面，大部分的研究都是針對(duì)其中一個(gè)方面進(jìn)行的。如在植被提取方面，文獻(xiàn)[1]使用 LiDAR數(shù)據(jù)生成距離圖像，然后使用圖像處理的方法提取植被；文獻(xiàn)[2]采用區(qū)域增長(zhǎng)和梯度分割的方法來(lái)提取樹(shù)木；文獻(xiàn)[3]通過(guò)SVM分類(lèi)實(shí)現(xiàn)城區(qū)植被的識(shí)別；關(guān)于建筑物的提取，文獻(xiàn)[4]利用強(qiáng)度信息和高程進(jìn)行數(shù)據(jù)分類(lèi)和分割，利用多次回波進(jìn)行數(shù)據(jù)分類(lèi)，先將植被提取出來(lái)，為分割相互毗鄰的房屋和樹(shù)木提供了一種有效的途徑；文獻(xiàn)[5]采用逐級(jí)分類(lèi)的策略，先將點(diǎn)云數(shù)據(jù)分為地面點(diǎn)和非地面點(diǎn)，對(duì)于非地面點(diǎn)，首先將影像與點(diǎn)云數(shù)據(jù)套合，將影像的光譜信息賦予點(diǎn)云，根據(jù)光譜信息提取出光譜特征較為明顯的植被，然后在剩余的點(diǎn)云中利用高程紋理提取出建筑物，最后根據(jù)回波次數(shù)提取剩余植被點(diǎn)云。

除了常用的激光點(diǎn)云分類(lèi)算法，還可利用專(zhuān)業(yè)的激光雷達(dá)點(diǎn)云數(shù)據(jù)處理軟件，如TerraScan、LASEdit等。其中TerraScan軟件是國(guó)內(nèi)外處理激光掃描點(diǎn)云數(shù)據(jù)的主要軟件，可以完成海量點(diǎn)云數(shù)據(jù)的讀取、分類(lèi)、處理、建模等相關(guān)工作。對(duì)于分類(lèi)，可以完成對(duì)建筑物、電線(xiàn)、植被等點(diǎn)云的自動(dòng)分類(lèi)提取[6]。如需要專(zhuān)業(yè)模塊，也可以人工手動(dòng)提取，但工作量巨大。

以上分類(lèi)算法一般都是半自動(dòng)或人工操作方式，計(jì)算量大，處理過(guò)程復(fù)雜。在研究現(xiàn)有激光點(diǎn)云分類(lèi)技術(shù)的基礎(chǔ)上，本文提出先根據(jù)主成分分析(principal component analysis，PCA)得到不同地物點(diǎn)在三維空間的幾何特征分布，然后將其特征送入神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，構(gòu)建神經(jīng)網(wǎng)絡(luò)模型，最后通過(guò)該模型對(duì)激光點(diǎn)云進(jìn)行分類(lèi)。本文把其命名為PCA-BP點(diǎn)云分類(lèi)算法。

三、PCA-BP激光點(diǎn)云分類(lèi)算法

基于PCA-BP算法的激光點(diǎn)云數(shù)據(jù)分類(lèi)算法包括主成分分析、BP神經(jīng)網(wǎng)絡(luò)構(gòu)建、BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練及BP神經(jīng)網(wǎng)絡(luò)分類(lèi)4個(gè)步驟，其算法流程如圖1所示。

圖1 PCA-BP算法流程

1.主成分分析

主成分分析是一種數(shù)學(xué)變換的方法，又稱(chēng)主分量分析或矩陣數(shù)據(jù)分析，是指當(dāng)變量之間存在一定的相關(guān)關(guān)系時(shí)，將相關(guān)變量通過(guò)線(xiàn)性組合變換成另一組不相關(guān)的變量，這些新的變量按照方差依次遞減的順序排列。在數(shù)學(xué)變換中保持變量的總方差不變，使第一變量具有最大的方差，稱(chēng)為第一主成分，第二變量的方差次大，并且和第一變量不相關(guān)，稱(chēng)為第二主成分，依次類(lèi)推。

基于主成分分析的點(diǎn)云分類(lèi)使用掃描點(diǎn)的空間分布統(tǒng)計(jì)對(duì)點(diǎn)云局部幾何特征進(jìn)行描述。對(duì)于平面點(diǎn)集

激光點(diǎn)云幾何特征的分布通過(guò)構(gòu)造協(xié)方差矩陣(公式(4))并對(duì)該矩陣進(jìn)行主成分分析得到。三維點(diǎn)集的協(xié)方差矩陣為三階，共3個(gè)主成分，從主成分的幾何意義出發(fā)，第一和第二主成分代表曲面上的主趨勢(shì)，第三主成分(最小主成分)代表了三維表面法向方向的趨勢(shì)(平面度越好的點(diǎn)集第三主成分越接近零)，如圖2所示。

圖2 主成分對(duì)應(yīng)特征向量幾何示意圖

不同地物的掃描點(diǎn)在三維空間中呈不同的分布形態(tài)。為了得到掃描點(diǎn)的統(tǒng)計(jì)描述信息，對(duì)式(4)所示的協(xié)方差矩陣進(jìn)行主成分分析得到按降序排列的特征值λ1≥λ2≥λ3[8]。若被掃物體為樹(shù)葉，則三個(gè)主成分滿(mǎn)足 λ1≈λ2≈λ3，見(jiàn)表1；若被掃物為墻面，則有λ1，λ2≥λ3，見(jiàn)表2。

2.BP神經(jīng)網(wǎng)絡(luò)模型的率定

BP(back propagation)神經(jīng)網(wǎng)絡(luò)是一種基于誤差反向傳播算法多層前饋神經(jīng)網(wǎng)絡(luò)，其具有分層結(jié)構(gòu)，信息從輸入層傳遞到隱含層，逐層向前傳遞，最后到輸出層，除輸入層之外，每一層的輸入是上一層的輸出，如果輸出層的實(shí)際輸出與期望輸出不符，則誤差反向傳播，即輸出誤差以某種形式通過(guò)隱含層向輸入層逐層反傳，并將誤差分?jǐn)偨o各層的所有單元，以該誤差為依據(jù)對(duì)網(wǎng)絡(luò)權(quán)值和閾值進(jìn)行調(diào)整。信號(hào)正向傳播與誤差反向傳播的各層權(quán)值調(diào)整過(guò)程，周而復(fù)始地進(jìn)行，該過(guò)程就是神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)訓(xùn)練過(guò)程，一直進(jìn)行到網(wǎng)絡(luò)的輸出誤差減少到可接受的程度，或進(jìn)行到預(yù)先設(shè)定的學(xué)習(xí)次數(shù)為止[9]。

表1 樹(shù)葉激光點(diǎn)云三維坐標(biāo)及主成分示例

表2 面狀激光點(diǎn)云三維坐標(biāo)及主成分示例

本文采用的BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。其中，λ1、λ2、λn是BP神經(jīng)網(wǎng)絡(luò)的輸入；Y1、Ym是 BP神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)輸出；ωij和ωjk為權(quán)值；N、M、L分別表示輸入層、隱含層和輸出層神經(jīng)元的個(gè)數(shù)。由于表示點(diǎn)云空間幾何特征的輸入信息為三維，待分類(lèi)的點(diǎn)云共有2類(lèi)，因此本文采用的BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)為3-4-2，即輸入層有3個(gè)節(jié)點(diǎn)，隱含層有4個(gè)節(jié)點(diǎn)，輸出層有2個(gè)節(jié)點(diǎn)。

圖3 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

四、試驗(yàn)結(jié)果與分析

本文試驗(yàn)所用數(shù)據(jù)為自新校區(qū)幼兒園室外掃描數(shù)據(jù)，包含有2 151 693個(gè)掃描點(diǎn)，通過(guò)地面激光掃描儀采集獲得。計(jì)算機(jī)硬件環(huán)境為 Intel Core i5 CPU 2.6 GHz，內(nèi)存為8 GB，軟件環(huán)境為Win7、Matlab7.0、VS2012和PtCloudPro。試驗(yàn)步驟如下：

1)主成分分析。對(duì)式(4)所示的協(xié)方差矩陣進(jìn)行主成分分析得到3個(gè)特征值λ1、λ2、λ3。

2)為訓(xùn)練樣本增加類(lèi)別標(biāo)識(shí)。由于樹(shù)葉點(diǎn)和平面點(diǎn)3個(gè)主成分之間的關(guān)系有顯著差異，依此給兩類(lèi)點(diǎn)云增加類(lèi)別標(biāo)識(shí)1和0，其中標(biāo)識(shí)為1的點(diǎn)為平面點(diǎn)，標(biāo)識(shí)為0的點(diǎn)為樹(shù)葉點(diǎn)。

3)建立BP神經(jīng)網(wǎng)絡(luò)模型。經(jīng)過(guò)反復(fù)試驗(yàn)和驗(yàn)證，最終采用newff建立一前向BP網(wǎng)絡(luò)，訓(xùn)練函數(shù)為 trainlm，隱含層傳遞函數(shù)為 logsig，學(xué)習(xí)率為0.05，訓(xùn)練步數(shù)為50 000，訓(xùn)練目標(biāo)誤差為1e-6。

4)訓(xùn)練神經(jīng)網(wǎng)絡(luò)。把平面樣本和樹(shù)葉樣本進(jìn)行合并，隨機(jī)選取部分?jǐn)?shù)據(jù)作為訓(xùn)練樣本，其余作為測(cè)試樣本，λ1、λ2、λ3作為輸入，1、0組成的矩陣作為輸出，對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，當(dāng)在指定的訓(xùn)練次數(shù)范圍之內(nèi)達(dá)到指定的目標(biāo)，訓(xùn)練成功。

5)點(diǎn)云分類(lèi)。將待分類(lèi)樣本輸入已訓(xùn)練好的BP網(wǎng)絡(luò)，根據(jù)輸出的值1或0確定是平面點(diǎn)或樹(shù)葉點(diǎn)。分類(lèi)效果如圖4所示，從圖4(a)和(b)可以看出，建筑物點(diǎn)云與樹(shù)葉點(diǎn)云基本分開(kāi)。

圖4 分類(lèi)前后效果圖

五、結(jié)束語(yǔ)

本文提出的基于PCA-BP算法的激光點(diǎn)云分類(lèi)方法，首先根據(jù)協(xié)方差矩陣由點(diǎn)云三維坐標(biāo)計(jì)算出3個(gè)主成分，然后依此對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，最后用訓(xùn)練好的網(wǎng)絡(luò)對(duì)待分類(lèi)點(diǎn)云進(jìn)行分類(lèi)，試驗(yàn)結(jié)果表明該方法能有效地將地物點(diǎn)云(建筑物和樹(shù)葉)進(jìn)行分類(lèi)。BP神經(jīng)網(wǎng)絡(luò)具有很強(qiáng)的自學(xué)習(xí)能力，能夠通過(guò)大量的訓(xùn)練樣本，自動(dòng)對(duì)權(quán)值等系數(shù)進(jìn)行調(diào)整，直到輸出誤差達(dá)到期望誤差為止。但是由于激光點(diǎn)云數(shù)據(jù)量大，訓(xùn)練和分類(lèi)大量的數(shù)據(jù)樣本需要很長(zhǎng)的時(shí)間；另外BP神經(jīng)網(wǎng)絡(luò)受經(jīng)驗(yàn)值影響較大，網(wǎng)絡(luò)層數(shù)、各層神經(jīng)元個(gè)數(shù)、傳遞函數(shù)、訓(xùn)練樣本的選擇等因素都會(huì)影響模型的建立和分類(lèi)的效果，且泛化能力較差，可能會(huì)造成漏分和誤分的情況。因此，如何對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行改進(jìn)、選擇其他類(lèi)型的神經(jīng)網(wǎng)絡(luò)或與傳統(tǒng)分類(lèi)方法相結(jié)合等是下一步要研究的內(nèi)容。

[1] CHEN G，ZAKHOR A.2D Tree Detection in Large Urban Landscapes Using Aerial LiDAR Data[C]∥16th IEEE International Conference.[S.l.]：IEEE，2009：1693-1696.

[2] 張齊勇，岑敏儀，周?chē)?guó)清，等.城區(qū)LiDAR點(diǎn)云數(shù)據(jù)的樹(shù)木提取[J].測(cè)繪學(xué)報(bào)，2009，38(4)：330-335.

[3] 劉峰，龔健雅.基于3D LiDAR數(shù)據(jù)的城區(qū)植被識(shí)別研究[J].地理與地理信息科學(xué)，2009，25(6)：5-8.

[4] 張小紅.機(jī)載激光掃描測(cè)高數(shù)據(jù)濾波及地物提取[D].武漢：武漢大學(xué)，2002.

[5] 龔亮.機(jī)載LiDAR點(diǎn)云數(shù)據(jù)分類(lèi)技術(shù)研究[D].鄭州：信息工程大學(xué)，2011.

[6] 鄭斌，包亞?wèn)|.車(chē)載LiDAR數(shù)據(jù)的初探[C]∥江蘇省測(cè)繪學(xué)會(huì)2011年學(xué)術(shù)年會(huì)論文集.[S.l.]：江蘇省測(cè)繪學(xué)會(huì)，2011.

[7] 王學(xué)民.應(yīng)用多元分析[M].2版.上海：上海財(cái)經(jīng)大學(xué)出版社，2004：232-238.

[8] 梁玉斌.面向建筑測(cè)繪的地面激光掃描模式識(shí)別方法研究[D].武漢：武漢大學(xué)，2013.

[9] 施彥，韓力群，廉小親，等.神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)方法與實(shí)例分析[M].北京：北京郵電大學(xué)出版社，2009.

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

Classification of LiDAR Point Clouds Based on PCA-BP Algorithm

ZHANG Rui，LI Guangyun，LI Minglei，WANG Shiyan

P234.5

B

0494-0911(2014)07-0023-04

2014-04-08

國(guó)家自然科學(xué)基金(41274014)

張 蕊(1980—)，女，河南濮陽(yáng)人，博士生，研究方向?yàn)榧す恻c(diǎn)云數(shù)據(jù)處理、大數(shù)據(jù)處理。

張蕊，李廣云，李明磊，等.利用PCA-BP算法進(jìn)行激光點(diǎn)云分類(lèi)方法研究[J].測(cè)繪通報(bào)，2014(7)：23-26.

10.13474/j.cnki.11-2246.2014.0217