基于顧及曲率自適應(yīng)鄰域的點(diǎn)云單點(diǎn)分類方法

何鄂龍

（中國船舶集團(tuán)有限公司第七一五研究所，杭州 310023）

1 技術(shù)背景

隨著LiDAR（Light Detection and Ranging）技術(shù)的快速發(fā)展，通過機(jī)載激光掃描、地面激光掃描和移動激光掃描可以更加快速地獲取城市點(diǎn)云數(shù)據(jù)[1]。點(diǎn)云分類是三維點(diǎn)云場景分析中的關(guān)鍵[2]，現(xiàn)已經(jīng)成為攝影測量和遙感領(lǐng)域的研究主題[3]。

在點(diǎn)云分類任務(wù)中，點(diǎn)云數(shù)據(jù)缺失和不均勻的密度分布給分類任務(wù)帶來了巨大挑戰(zhàn)[4]。經(jīng)典算法是提取典型的特征[5]，并基于監(jiān)督分類算法進(jìn)行點(diǎn)云分類[6]，可以分為點(diǎn)云鄰域重構(gòu)、點(diǎn)云局部特征提取和點(diǎn)云分類3個步驟[7]。

點(diǎn)云局部特征可以有效地表達(dá)實(shí)際場景中物體的結(jié)構(gòu)信息，通常由局部鄰域的點(diǎn)云空間分布統(tǒng)計得到[2]。三維鄰域的構(gòu)建可分為固定尺度方法和自適應(yīng)尺度方法[4]。固定鄰域方法受限于場景先驗知識、點(diǎn)云密度以及曲率分布等。自適應(yīng)鄰域方法通過點(diǎn)云局部鄰域的空間分布情況生成鄰域，可以有效消除點(diǎn)云密度分布不均和線狀分布帶來的影響，但需要真實(shí)數(shù)據(jù)的先驗信息作為參數(shù)。最小熵方法通過搜索鄰域k或鄰域半徑r確定最優(yōu)鄰域[2]，其中基于鄰域半徑r的方法容易受到密度變化的影響，基于鄰域k的方法容易受到線狀分布的影響。

本文采用點(diǎn)云單點(diǎn)分類方法對點(diǎn)云數(shù)據(jù)進(jìn)行分類，創(chuàng)造性地提出了顧及曲率的自適應(yīng)鄰域估計方法，有效增強(qiáng)了點(diǎn)云統(tǒng)計特征的可分離性，進(jìn)一步提升了分類效果。

2 算法流程

本文的點(diǎn)云分類方法主要包括曲率的自適應(yīng)鄰域估計、特征提取和監(jiān)督分類3部分。整體的算法流程如圖1所示。

圖1 點(diǎn)云分類方法流程

2.1 顧及曲率的自適應(yīng)鄰域估計

點(diǎn)云的曲率用于描述三維點(diǎn)所在表面的局部變化情況，通常由一定鄰域范圍內(nèi)點(diǎn)集的統(tǒng)計信息得到。傳統(tǒng)的方法是使用鄰域內(nèi)三維點(diǎn)集的協(xié)方差矩陣。基于協(xié)方差矩陣的3個特征值，可以得到點(diǎn)云數(shù)據(jù)的曲率信息：

點(diǎn)云曲率被歸一化到[0，1/3]，0表示三維點(diǎn)處于一個平面，1/3表示三維點(diǎn)處于混亂的分布狀態(tài)。點(diǎn)云分布情況和自適應(yīng)鄰域的半徑分布，如圖2所示。通常點(diǎn)云數(shù)據(jù)中植被和物體的邊界區(qū)域曲率較大，如圖2（c）所示，此類點(diǎn)需要較小的鄰域半徑，反之小曲率區(qū)域，需要較大的鄰域。因此，良好可分的特征提取方法需要要合適的自適應(yīng)鄰域。

圖2（d）為基于k-最小熵的自適應(yīng)鄰域vk，k的取值范圍為10～100，取值間隔Δk=1，點(diǎn)云鄰域在區(qū)域Ⅰ中的高密度規(guī)則區(qū)域呈現(xiàn)為一種纖細(xì)的線狀分布，不足以提供魯棒的特征。圖2（e）為基于r-最小熵的自適應(yīng)鄰域vr，r的取值范圍為0.25～2.00 m，采樣間隔Δr=0.05 m。在區(qū)域Ⅱ中存在與區(qū)域Ⅰ一樣的問題。從區(qū)域Ⅲ可以看到，植被區(qū)域的鄰域尺寸較大，無法有效提取細(xì)節(jié)特征。因為沒有考慮點(diǎn)云在復(fù)雜城區(qū)場景中的不均勻分布，所以當(dāng)前的自適應(yīng)鄰域在高密度的規(guī)則區(qū)域仍然呈現(xiàn)出線狀分布。

圖2 點(diǎn)云分布情況以及自適應(yīng)鄰域的半徑分布。

基于兩種最小熵的鄰域估算方法，本文設(shè)計了一種估計曲率的自適應(yīng)鄰域估算方法vc。該方法主要是基于曲率閾值ct將點(diǎn)云數(shù)據(jù)預(yù)分割為規(guī)則區(qū)域和非規(guī)則區(qū)域，然后分而治之，如圖3所示。

圖3 顧及曲率自適應(yīng)鄰域估算方法流程圖

由于離散點(diǎn)沒有足夠的鄰近點(diǎn)支撐鄰域構(gòu)建，曲率需設(shè)置為1/3。點(diǎn)云數(shù)據(jù)中當(dāng)曲率大于ct時被分類為散亂區(qū)域，并使用vk方法估算鄰域，小于ct的則被分為規(guī)則區(qū)域，并使用vr方法估算鄰域。

由于現(xiàn)實(shí)場景中的點(diǎn)云先驗知識是未知的，點(diǎn)云自適應(yīng)鄰域需要以較小的邊界覆蓋場景中絕大部分類型的物體，并減小運(yùn)算量。自適應(yīng)鄰域vk法選取最小邊界kmin=10，通過主成分分析（Principal Components Analysis，PCA）法來估算3D局部幾何特征，并根據(jù)數(shù)據(jù)的計算量合理設(shè)置上邊界值。同時，自適應(yīng)鄰域vr法應(yīng)設(shè)置下邊界rmin=0.25 m，避免vr鄰域集中在點(diǎn)云數(shù)據(jù)中某一條掃描線上。由于自適應(yīng)鄰域vc估算方法已經(jīng)考慮了點(diǎn)云數(shù)據(jù)中規(guī)則與非規(guī)則區(qū)域的先驗信息，并將參數(shù)k的上邊界設(shè)置為50，以減小運(yùn)算量，變化范圍為10～50，采樣間隔Δk=1。在本文方法中，綜合考慮城市場景中物體的大小分布，自適應(yīng)鄰域的最大尺寸被限制為3 m。在規(guī)則區(qū)域內(nèi)，鄰域通常較大，可以將參數(shù)r的下邊界設(shè)置為0.5 m來減少運(yùn)算量。參數(shù)r∈[0.5,2.0]，以Δr=0.05 m的步長采樣，劃分為30個尺度計算。通過上述兩種辦法，生成最終的顧及曲率自適應(yīng)鄰域vc。

曲率閾值通過k-means方法得到，因此要將點(diǎn)云數(shù)據(jù)劃分為兩個聚類，初始化聚類中心為點(diǎn)云中的最大曲率和最小曲率值。設(shè)兩個聚類的中心點(diǎn)曲率值為cur1和cur2（cur2＞cur1），ct計算如下：

從圖2（e）中可以看到，在立面和地面等規(guī)則分布區(qū)域的點(diǎn)云數(shù)據(jù)通常有較大的點(diǎn)云鄰域尺寸，而相對散亂分布的區(qū)域，其鄰域尺寸相對較小。

2.2 特征提取

因為部分公開數(shù)據(jù)集點(diǎn)云數(shù)據(jù)只包含點(diǎn)云的空間位置特征，所以本文只選用點(diǎn)云數(shù)據(jù)的幾何特征。點(diǎn)云特征可以表示為三維點(diǎn)所在局部表面的結(jié)構(gòu)信息，主要通過計算局部鄰域內(nèi)點(diǎn)集的空間分布得到。本文方法通過點(diǎn)云曲率增強(qiáng)了點(diǎn)云單點(diǎn)特征的可分離性。點(diǎn)云特征主要包括點(diǎn)云立面度量V、歸一化高差Dz以及基于特征值的特征Lλ、Pλ、Sλ和Cλ。

基于點(diǎn)云法線信息，可以得到點(diǎn)云的立面度特征：

式中：V表示點(diǎn)云局部平面與水平面之間的角度；nz是點(diǎn)云法向量的第3個分量。

歸一化高差Dz，計算如下：

式中：Dz主要表示鄰域內(nèi)點(diǎn)集的高差分布情況；dz為點(diǎn)云鄰域內(nèi)的高差；zmax和zmin為鄰域內(nèi)點(diǎn)云最大值最小值。式（6）中hmax和hmin分別代表點(diǎn)云中的最大高度和最小高度。

特征值特診計算如下：

式中：Lλ、Pλ和Sλ的和為1，分別代表點(diǎn)云鄰域內(nèi)的線性度、平面度以及離散度。

2.3 點(diǎn)云分類

本文點(diǎn)云分類使用隨機(jī)森林（Random Forest，RF）方法，采用200棵樹，樹的高度為，其中d為分類特征的緯度。

3 實(shí)驗結(jié)果

3.1 數(shù)據(jù)介紹

為評估本文方法的有效性，使用Oakland 3D Point Cloud Dataset進(jìn)行點(diǎn)云分類，并將數(shù)據(jù)手動標(biāo)記為植被、電線、電線桿/樹干、地面和立面5類。

3.2 實(shí)驗內(nèi)容

實(shí)驗中，考慮點(diǎn)云曲率閾值的影像，并驗證基于k-means的方法估算曲率閾值的有效性，同時比較基于k-最小熵的自適應(yīng)鄰域vk、基于r-最小熵的自適應(yīng)鄰域vr和顧及曲率自適應(yīng)鄰域vc這3種不同的自適應(yīng)鄰域的估算方法。

3.3 結(jié)果與討論

實(shí)驗結(jié)果評價指標(biāo)采用分類結(jié)果的召回率（Recall）、分類結(jié)果的正確率（Precision）、召回率和正確率的平均值（F1-score）以及代表分類結(jié)果的整體正確率（Overall Accuracy）。由于測試數(shù)據(jù)是非均衡數(shù)據(jù)集，整體正確率容易受點(diǎn)云數(shù)據(jù)中占比較大的類別影響，在實(shí)驗中使用召回率和正確率以及平均值來評價不同類別的分類結(jié)果。

實(shí)驗使用半徑r=1 m來估算Oakland Point Cloud的曲率信息，選取閾值ct=0.03將點(diǎn)云數(shù)據(jù)分為規(guī)則和非規(guī)則區(qū)域。

通過k-means方法得到曲率閾值，初始聚類中心為0和1/3，迭代17次后達(dá)到穩(wěn)定狀態(tài)。各類別點(diǎn)云數(shù)據(jù)在規(guī)則區(qū)域和非規(guī)則區(qū)域的分布情況如表1所示。

從表1可以得到，90%的植被點(diǎn)和地面點(diǎn)都被有效區(qū)分開。為了評估曲率閾值的有效性，實(shí)驗從區(qū)間ct∈[0.5,2.0]按照Δc=0.005的步長實(shí)驗得到整體精度，如圖4所示。當(dāng)ct=0.03時，達(dá)到最高精度96.1%，驗證了k-means方法選取曲率閾值的有效性。

圖4 不同曲率閾值下的整體正確率

表1 通過ct=0.03劃分的規(guī)則區(qū)域與非規(guī)則區(qū)域類別分布情況

由于自適應(yīng)鄰域估算方法vc綜合了vk和vr的優(yōu)點(diǎn)，對比這3種方法的結(jié)果如表2所示。從表2可以看到，自適應(yīng)鄰域估算方法顯著提高了各個類別的3項指標(biāo)結(jié)果。通過將點(diǎn)云數(shù)據(jù)劃分為規(guī)則與非規(guī)則區(qū)域，可以充分挖掘vk和vr的潛力。

表2 評價指標(biāo)比較 （單位：%）

4 結(jié)語

本文提出了一種基于顧及曲率自適應(yīng)鄰域的點(diǎn)云單點(diǎn)分類方法。基于Oakland數(shù)據(jù)集的實(shí)驗表明，該方法有效提取了點(diǎn)云自適應(yīng)鄰域信息，并增強(qiáng)了點(diǎn)云單點(diǎn)特征的魯棒性和可分性。