梁宇乾 袁希平 甘淑

摘 要：機載LIDA點云數(shù)據(jù)中的回光強度信息可對地物進行精細分類。KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法是目前比較熱門的分類算法，在數(shù)據(jù)分類方面應(yīng)用廣泛，對這兩種算法進行了分類比較研究。將回光強度信息作為訓(xùn)練樣本，利用兩種不同的方法進行分類。實驗結(jié)果表明，BP神經(jīng)網(wǎng)絡(luò)在地物的精細分類以及邊界線提取方面要優(yōu)于KNN算法。

關(guān)鍵詞：機載LIDAR；回光強度；KNN算法；BP神經(jīng)網(wǎng)絡(luò)；分類

DOI：10.11907/rjdk.172941

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號：1672-7800（2018）004-0077-05

Abstract：The light intensity information of airborne LIDA point cloud data can be classified on the ground objects.At present， there are many classification methods of intensity information.In this paper， two popular algorithms are classified and compared.KNN algorithm and BP neural network algorithm are popular classification algorithms， especially in data classification.This paper use light intensity information as the training samples for classification by two different methods.The experimental results show that BP neural network is better than KNN algorithm in fine classification of ground objects and extraction of boundary lines.

Key Words：airborne LIDAR； intensity； KNN algorithm； BP neural network algorithm； classification

0 引言

機載LIDAR即激光探測與測量，是集全球定位系統(tǒng)和慣性導(dǎo)航系統(tǒng)為一體的機載激光掃描，其所測數(shù)據(jù)為數(shù)字表面模型的離散點表示，數(shù)據(jù)中不僅含空間三維信息，還有入射角、GPS時、激光回光強度等信息。其中，回光強度大小與目標(biāo)表面材質(zhì)、入射光角度以及反射光角度都有關(guān)系。目前，LIDAR回光強度等信息越來越被重視，用回光強度提取空間信息的應(yīng)用研究較多[1]。不同地物的反射強度不同，根據(jù)這一特性，可以利用回光強度對地物進行分類[2-3]。

分類是數(shù)據(jù)挖掘的核心和基礎(chǔ)技術(shù)，在經(jīng)營、決策、管理、科學(xué)研究等多個領(lǐng)域有著廣泛應(yīng)用。目前熱門的分類技術(shù)有人工神經(jīng)網(wǎng)絡(luò)分類法、決策樹分類法、KNN算法分類法等。KNN分類經(jīng)過多年發(fā)展，已經(jīng)成為一種簡單、便捷、成熟、非參數(shù)的方法，廣泛應(yīng)用于文本分類、圖像分類等多個領(lǐng)域，如沈泓等[4]學(xué)者通過K聚類的方法對數(shù)據(jù)進行整合。BP人工神經(jīng)網(wǎng)絡(luò)不僅具有自我學(xué)習(xí)能力，而且具有聯(lián)想儲存能力和尋找最優(yōu)解能力，是時下最熱門的一種分類方法，如顧亞風(fēng)等[5]通過神經(jīng)網(wǎng)絡(luò)對古玩圖片進行分類；茅千千[6]利用神經(jīng)網(wǎng)絡(luò)對石油項目進行綜合評價。

1 KNN算法

最近鄰算法是根據(jù)實例學(xué)習(xí)然后進行數(shù)據(jù)分類的一種最常用的方法。

令樣本集D={x1`````xn}，在集合X中的每個樣本xi類別已知。現(xiàn)有一個未知樣本x，在集合X中有已知樣本點x1，且x與x1距離最近，那么x的樣本類型就與x1相同。

K最近鄰算法（K-NearestNeighbor）是最近鄰算法的變形應(yīng)用。該算法將一個未知數(shù)據(jù)點n分類為與它距離最近的K個近鄰點中個數(shù)最多且最近的那個類別。K最近鄰算法從未知樣本點n開始計算，不斷擴大分類范圍，直到包含進K個訓(xùn)練樣本點結(jié)束，并把未知樣本點n歸為距離最近的K個訓(xùn)練樣本點中出現(xiàn)頻率最大的類別。一般測試樣本與訓(xùn)練樣本的距離使用歐式距離測量。圖1和圖2分別是KNN算法的一般流程和KNN算法使用步驟。

1.1 KNN中距離度量

在對數(shù)據(jù)進行挖掘和分析過程中需要知道數(shù)據(jù)間的差異，從而判斷數(shù)據(jù)的相似性和類別。最常見的數(shù)據(jù)分析和挖掘方法是相關(guān)分析和分類、聚類算法。衡量個體差異的方法有很多，在KNN中分析數(shù)據(jù)相關(guān)性一般采取距離度量和相似度度量方法。

1.1.1 距離度量

在KNN算法中，未知數(shù)據(jù)與已知數(shù)據(jù)的相似性用距離判別，距離越大表示兩個點越不相似。在KNN算法中基本的距離度量有3類：明可夫斯基距離、曼哈頓距離和歐式距離。

p值是一個變量，當(dāng)p=2時就得到上述歐氏距離。

曼哈頓距離（Manhattan Distance）源于曼哈頓城市區(qū)塊距離，是將不同維度上的距離進行求和后得到的結(jié)果。曼哈頓距離是明式距離的一種變形應(yīng)用，當(dāng)明氏距離p=1時得到距離度量公式：

切比雪夫距離（Chebyshev Distance）起源于國際象棋中國王的走法。我們知道國王每次只能往周圍的8格中走一步，如果要從棋盤中A格（x1， y1）走到B格（x2， y2）最少需要走幾步？擴展到多個維度空間，切比雪夫距離就是明式距離的一種變形應(yīng)用，當(dāng)明氏距離中p趨向無窮大時，有公式：

由此可見歐氏距離、曼哈頓距離和切比雪夫距離都是由明可夫斯基距離變形的另一種應(yīng)用。

1.2 K值確定

在KNN算法中，所有的計算幾乎都發(fā)生在分類階段，而且分類效果的優(yōu)劣主要體現(xiàn)在K值的選取上，所以取到合適的K值至關(guān)重要。如果K值數(shù)值偏小，得到的近鄰數(shù)就會減少從而降低分類精度，同時提高了噪聲對數(shù)據(jù)干擾；如果K值數(shù)值偏大，并且未知數(shù)據(jù)樣本類型屬于訓(xùn)練數(shù)據(jù)中包含數(shù)據(jù)較少的那一類，那么在用K值進行分類時，通常會把一些并不相似的數(shù)據(jù)包含進來，這樣會使得噪聲增加以及分類準(zhǔn)確性降低。選取合適的K值一直是KNN的研究熱點。

從圖3可以看到有兩個類型的樣本數(shù)據(jù)，一類是正方形，另一類是三角形，而圓形是待分類的數(shù)據(jù)。如果K=3，離圓形距離最近的包含了2個三角形以及1個正方形，由于K值為3，于是圓形這個待分類點就屬于三角形。如果K=5，那么圓形最近的有2個三角形和3個正方形，于是待分類點屬于正方形。

K取值經(jīng)驗規(guī)則：

（1）K一般低于訓(xùn)練樣本數(shù)的平方根。

（2）K是通過大量的樣本數(shù)據(jù)進行測試、不同模型進行驗證作出的最佳選擇。

（3）當(dāng)采用固定距離指標(biāo)，那么K值可以提前確定，或者采用動態(tài)K值[10]。樣本間類別不平衡時K值相對來說難以確定，朱響斌等[7]提供了K值的選擇方法：當(dāng)最近鄰使用歐氏距離而且樣本數(shù)據(jù)較大時，K的選擇應(yīng)當(dāng)遵從：K→：∞，K/N→0[8-9]。普遍采取交叉驗證法，評估最小錯誤率的K值作為最優(yōu)K值[10-11]。

（4）如果給定訓(xùn)練樣本中的類別個數(shù)是偶數(shù)，一般K會設(shè)置為一個奇數(shù)；如果類別個數(shù)為奇數(shù)，K通常設(shè)置為偶數(shù)。

2 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)（Back Propagation）由以Rumelhart和McCelland為首的科學(xué)家小組于1986年提出，是一種逆向傳播誤差算法訓(xùn)練的多層前饋網(wǎng)絡(luò)，也是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。

BP神經(jīng)網(wǎng)絡(luò)是多層前饋神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)的主要特點是信號向前傳遞，誤差逆向傳播。在信號的前向傳播中，輸入的信號從輸入層開始，經(jīng)過隱含層逐層處理，直到輸出層輸出數(shù)據(jù)。每一層中的神經(jīng)元（閾值大?。┲挥绊懴乱粚由窠?jīng)元。如果輸出層得不到理想輸出結(jié)果則進入逆向傳播，根據(jù)所預(yù)測的誤差調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，從而使BP神經(jīng)網(wǎng)絡(luò)的預(yù)測輸出不斷向期望輸出靠近。如圖4所示，BP神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)模型包括輸入層（input）、隱層（hide layer）和輸出層（output layer）。

2.1 神經(jīng)網(wǎng)絡(luò)算法建立

基于機載LIDAR點云分類的BP神經(jīng)網(wǎng)絡(luò)算法建模包括BP神經(jīng)網(wǎng)絡(luò)構(gòu)建、BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練和BP神經(jīng)網(wǎng)絡(luò)分類，算法流程如圖5所示。

2.2 神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程

設(shè)X2，…，Xn是BP神經(jīng)網(wǎng)絡(luò)的輸入值，Y1，Y2，…，Yn ωjk是BP神經(jīng)網(wǎng)絡(luò)的預(yù)測值， ωij和ωjk為BP神經(jīng)網(wǎng)絡(luò)權(quán)值。當(dāng)神經(jīng)網(wǎng)絡(luò)輸入節(jié)點數(shù)為n、輸出節(jié)點數(shù)為m時，整個網(wǎng)絡(luò)就表示一個從n個自變量到m個因變量的函數(shù)關(guān)系。

BP神經(jīng)網(wǎng)絡(luò)在做分類預(yù)測前首先要訓(xùn)練主動學(xué)習(xí)能力。BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練步驟：

（1）網(wǎng)絡(luò)初始化。根據(jù)分類所需類別以及輸出結(jié)果種類，確定網(wǎng)絡(luò)輸入層節(jié)點數(shù)n、隱含層節(jié)點數(shù)1、輸出層節(jié)點數(shù)m，對輸入層、隱含層和輸出層進行初始化處理，各個神經(jīng)元之間的連接權(quán)值ωij，ωjk，初始化隱含層閾值a，輸出層閾值b，給定神經(jīng)元激勵函數(shù)以及學(xué)習(xí)速率。

（2）隱含層輸出計算。根據(jù)輸入向量X、輸入層和隱含層間連接權(quán)值ωij以及隱含層閾值a，計算隱含層輸出H：

（7）判斷算法迭代是否結(jié)束，若沒有結(jié)束，返回步驟（2）。

3 分類結(jié)果與對比研究

試驗區(qū)為云南某湖泊的灘涂機載LIDAR點云數(shù)據(jù)，圖6是該區(qū)域的平面點云圖。由這幅點云圖把該區(qū)域大致分為兩類：水域點和陸地點。圖中藍色點為已知水域點，棕色點為陸地點，灰色點代表未分類的點云數(shù)據(jù)（如需看彩圖，請與編輯部聯(lián)系）。

3.1 KNN分類

首先，該區(qū)域的點云數(shù)量約為10萬個，選取已知類型的8 000個點為訓(xùn)練數(shù)據(jù)。其次，通過多次實驗取K值。表1是K值大小與測試集準(zhǔn)確率間的關(guān)系。由表1可以看出，K值取15時測試集的準(zhǔn)確率最高。隨著K值的增加，測試集的準(zhǔn)確率逐步下降。圖7為該實驗區(qū)KNN算法分類效果。

3.2 BP神經(jīng)網(wǎng)絡(luò)分類

用已知分類點進行訓(xùn)練并且進行數(shù)據(jù)測試，圖8是神經(jīng)網(wǎng)絡(luò)在訓(xùn)練數(shù)據(jù)過程中迭代次數(shù)和訓(xùn)練誤差的關(guān)系。由圖8可以看出，隨著迭代次數(shù)的增加，訓(xùn)練誤差迅速下降，在第6次迭代趨于平穩(wěn)，但仍有下降趨勢，誤差無限趨近于0.1。

圖9是通過BP神經(jīng)網(wǎng)絡(luò)分類后得到的點云分類效果。從圖中可以看到，通過BP網(wǎng)絡(luò)分類可以有效區(qū)分陸地點和水域點。在水域點中有部分點云數(shù)據(jù)是算法中認(rèn)為的陸地點，造成這種情況原因的是因為水域較淺，機載LIDAR的激光束穿透能力很強，激光束穿透水面打到水面底部巖石或土地上，造成分類錯誤。

3.3 對比研究

通過圖10和圖11對比發(fā)現(xiàn)，KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法都能較好地將點云絕大部分的地面點和水域點分開，但是通過對比發(fā)現(xiàn)有以下3點可以看出KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法的不同[9-10]：

（1）兩幅圖中紅框所標(biāo)注出的1區(qū)、3區(qū)、4區(qū)，KNN算法不能很好判別，把一些地面點判別為水域點。雖然神經(jīng)網(wǎng)絡(luò)也出現(xiàn)類似情況，但是通過比較發(fā)現(xiàn)，BP神經(jīng)網(wǎng)絡(luò)的分類更為精細。

（2）對于2區(qū)來說，KNN算法的分類效果好于BP神經(jīng)網(wǎng)絡(luò)，BP神經(jīng)網(wǎng)絡(luò)會把一些明顯的水域點判別為地面點。這里有兩個原因：①KNN算法是通過近鄰點分類；②由于機載LIDAR的激光束穿過水面，直接打在了水底造成了誤分類。

（3）在區(qū)分地物邊界方面，BP神經(jīng)網(wǎng)絡(luò)顯然比KNN算法更出色。通過對比不難看出，KNN算法對明顯的邊界不能很好地區(qū)分。

4 結(jié)語

通過該實驗對比發(fā)現(xiàn)，BP神經(jīng)網(wǎng)絡(luò)算法在分類方面比KNN算法更為精細，尤其表現(xiàn)在對邊界線的提取方面。這取決于BP神經(jīng)網(wǎng)絡(luò)利用積極學(xué)習(xí)的方法，擁有自動學(xué)習(xí)能力，并且能充分逼近復(fù)雜的非線性關(guān)系。反觀KNN算法，其采用懶惰學(xué)習(xí)方法，導(dǎo)致對擁有海量數(shù)據(jù)和類別多的數(shù)據(jù)不能實現(xiàn)很好的分類。

參考文獻：

[1] ACKERMANN F. Airborne laser scanning-present status and future expectation[J].ISPRS Journal of Photogrammetry & Remote Sensing，1999（54）：64-67.

[2] 左志權(quán).顧及點云類別屬性與地形結(jié)構(gòu)特征的機載LiDAR數(shù)據(jù)濾波方法[D].武漢：武漢大學(xué)， 2011.

[3] 賈廣帥.機載激光雷達數(shù)據(jù)特點和濾波方法研究[D].青島：山東科技大學(xué)，2007.

[4] 沈泓，劉順.基于K-means聚類算法的數(shù)據(jù)分析模型應(yīng)用研究[J].軟件導(dǎo)刊，2017，16（3）：103-107.

[5] 顧亞風(fēng)，葉學(xué)義.基于卷積神經(jīng)網(wǎng)絡(luò)的古玩圖片分類方法[J].軟件導(dǎo)刊，2017，16（5）：174-178.

[6] 茅茜茜.BP神經(jīng)網(wǎng)絡(luò)在石油項目經(jīng)濟效益綜合評價中的應(yīng)用[J].軟件導(dǎo)刊，2017，16（4）：145-148.

[7] 朱響斌.一種基于八叉樹的三維實體內(nèi)部可視化技術(shù)[J].中國圖象圖形學(xué)報，2002，7（3）：229-233.

[8] LOFTSGAARDEN D O， QUESENBERRY C P.A nonparametric estimate of multivariate density function[J].Ann Math Statist，1965，36（3）：1049-1051.

[9] COVER T M，HART P E.Nearest neighbor pattern classification[J].IEEE Trans Inform Theory，1968，13（1）：21-27.

[10] LACHENBRUCH P A，MICKEY M R.Estimation of error rates in discriminant analysis[J].Technometrics，1968，10（1）：1-11.

[11] STONE M. Cross validation： a review， math operationsforschung und statist[J].Series Statistics，1978，9（1）：127-139.

（責(zé)任編輯：杜能鋼）