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

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

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

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

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

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

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

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

一、引 言

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

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

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

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

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

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

以上分類算法一般都是半自動或人工操作方式，計(jì)算量大，處理過程復(fù)雜。在研究現(xiàn)有激光點(diǎn)云分類技術(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ò)模型，最后通過該模型對激光點(diǎn)云進(jìn)行分類。本文把其命名為PCA-BP點(diǎn)云分類算法。

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

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

圖1 PCA-BP算法流程

1.主成分分析

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

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

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

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

不同地物的掃描點(diǎn)在三維空間中呈不同的分布形態(tài)。為了得到掃描點(diǎn)的統(tǒng)計(jì)描述信息，對式(4)所示的協(xié)方差矩陣進(jìn)行主成分分析得到按降序排列的特征值λ1≥λ2≥λ3[8]。若被掃物體為樹葉，則三個主成分滿足 λ1≈λ2≈λ3，見表1；若被掃物為墻面，則有λ1，λ2≥λ3，見表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í)際輸出與期望輸出不符，則誤差反向傳播，即輸出誤差以某種形式通過隱含層向輸入層逐層反傳，并將誤差分?jǐn)偨o各層的所有單元，以該誤差為依據(jù)對網(wǎng)絡(luò)權(quán)值和閾值進(jìn)行調(diào)整。信號正向傳播與誤差反向傳播的各層權(quán)值調(diào)整過程，周而復(fù)始地進(jìn)行，該過程就是神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)訓(xùn)練過程，一直進(jìn)行到網(wǎng)絡(luò)的輸出誤差減少到可接受的程度，或進(jìn)行到預(yù)先設(shè)定的學(xué)習(xí)次數(shù)為止[9]。

表1 樹葉激光點(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ù)測輸出；ωij和ωjk為權(quán)值；N、M、L分別表示輸入層、隱含層和輸出層神經(jīng)元的個數(shù)。由于表示點(diǎn)云空間幾何特征的輸入信息為三維，待分類的點(diǎn)云共有2類，因此本文采用的BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)為3-4-2，即輸入層有3個節(jié)點(diǎn)，隱含層有4個節(jié)點(diǎn)，輸出層有2個節(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個掃描點(diǎn)，通過地面激光掃描儀采集獲得。計(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)主成分分析。對式(4)所示的協(xié)方差矩陣進(jìn)行主成分分析得到3個特征值λ1、λ2、λ3。

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

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

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

圖4 分類前后效果圖

五、結(jié)束語

本文提出的基于PCA-BP算法的激光點(diǎn)云分類方法，首先根據(jù)協(xié)方差矩陣由點(diǎn)云三維坐標(biāo)計(jì)算出3個主成分，然后依此對BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，最后用訓(xùn)練好的網(wǎng)絡(luò)對待分類點(diǎn)云進(jìn)行分類，試驗(yàn)結(jié)果表明該方法能有效地將地物點(diǎn)云(建筑物和樹葉)進(jìn)行分類。BP神經(jīng)網(wǎng)絡(luò)具有很強(qiáng)的自學(xué)習(xí)能力，能夠通過大量的訓(xùn)練樣本，自動對權(quán)值等系數(shù)進(jìn)行調(diào)整，直到輸出誤差達(dá)到期望誤差為止。但是由于激光點(diǎn)云數(shù)據(jù)量大，訓(xùn)練和分類大量的數(shù)據(jù)樣本需要很長的時間；另外BP神經(jīng)網(wǎng)絡(luò)受經(jīng)驗(yàn)值影響較大，網(wǎng)絡(luò)層數(shù)、各層神經(jīng)元個數(shù)、傳遞函數(shù)、訓(xùn)練樣本的選擇等因素都會影響模型的建立和分類的效果，且泛化能力較差，可能會造成漏分和誤分的情況。因此，如何對BP神經(jīng)網(wǎng)絡(luò)進(jìn)行改進(jìn)、選擇其他類型的神經(jīng)網(wǎng)絡(luò)或與傳統(tǒng)分類方法相結(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] 張齊勇，岑敏儀，周國清，等.城區(qū)LiDAR點(diǎn)云數(shù)據(jù)的樹木提取[J].測繪學(xué)報，2009，38(4)：330-335.

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

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

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

[6] 鄭斌，包亞東.車載LiDAR數(shù)據(jù)的初探[C]∥江蘇省測繪學(xué)會2011年學(xué)術(shù)年會論文集.[S.l.]：江蘇省測繪學(xué)會，2011.

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

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

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

[10] 龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法[J].測繪學(xué)報，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

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

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

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

10.13474/j.cnki.11-2246.2014.0217