基于空間相似聚類的點(diǎn)云數(shù)據(jù)分割方法研究與實(shí)驗(yàn)

馬進(jìn)全，李玉忠，穆文龍

(1. 青海省測繪產(chǎn)品質(zhì)量監(jiān)督檢驗(yàn)站，青海 西寧 810001；2. 青海省第二測繪院，青海 西寧 810001)

0 引 言

三維點(diǎn)云數(shù)據(jù)是指通過激光雷達(dá)(LiDAR，Light Detecting And Ranging)掃描獲取的包含目標(biāo)表面三維坐標(biāo)、反射強(qiáng)度等信息的海量點(diǎn)數(shù)據(jù)，具有無損、高效、精準(zhǔn)、海量數(shù)據(jù)等特點(diǎn)[1]。點(diǎn)云信息除了目標(biāo)物體表面的離散點(diǎn)的空間坐標(biāo)信息外，還包含海量點(diǎn)云的子集所描述的曲面信息以及發(fā)射的激光脈沖經(jīng)過與目標(biāo)作用后反射的不同強(qiáng)度的回波信號。在對物體進(jìn)行測量的過程中，三維掃描儀可快速高效地對目標(biāo)物體進(jìn)行量測，獲取物體表面三維坐標(biāo)。由于點(diǎn)云數(shù)據(jù)的密度大并且不直接與地物表面接觸，被廣泛應(yīng)用在室外場景的處理中，以實(shí)現(xiàn)地物提取、物體識別、場景分析等工作。而這些應(yīng)用的輸入數(shù)據(jù)則是通過點(diǎn)云分割將具有相同屬性的點(diǎn)聚類為同質(zhì)區(qū)域的結(jié)果數(shù)據(jù)，且點(diǎn)云分割結(jié)果的優(yōu)劣直接影響到后續(xù)的應(yīng)用分析，故點(diǎn)云分割具有重要的研究價值，也得到了國內(nèi)外許多研究者的廣泛關(guān)注，并提出了許多點(diǎn)云分割算法。

1 國內(nèi)外研究現(xiàn)狀

三維點(diǎn)云分割就是從原始雜亂無章的點(diǎn)云中確定具有相同屬性的區(qū)域，賦予相同標(biāo)志的過程，其相同幾何屬性區(qū)域主要包含：線狀區(qū)域、面狀區(qū)域、球狀區(qū)域等；相同語義屬性區(qū)域是指環(huán)境中的地物，如道路、樹木、路燈、交通標(biāo)志牌、建筑物等。目前三維點(diǎn)云的分割方法多種多樣，按照分割方法的不同分為如下幾類：基于區(qū)域邊界的分割方法、基于聚類的分割方法、基于區(qū)域增長的分割方法、基于圖的分割方法、基于模型匹配的分割方法以及基于機(jī)器學(xué)習(xí)的分割方法等。

1.1 基于邊界的分割方法

通過計(jì)算每個點(diǎn)的幾何特性，估算出點(diǎn)的法向量或曲率，將突變處的三維點(diǎn)定義為特征點(diǎn)，將所有的特征點(diǎn)連接形成一個封閉的區(qū)域，得出分割結(jié)果。Fan等采用逐點(diǎn)計(jì)算點(diǎn)局部曲率的方法，依據(jù)曲率變化情況判斷是否為邊界點(diǎn)，該方法計(jì)算量較大[2]；Sappa等采用兩步邊界查找法，在邊界優(yōu)化過程中對曲面擬合的初始迭代參數(shù)精度要求高，實(shí)用性不強(qiáng)[3]?；谶吔绲姆指罘椒▽υ肼暠容^敏感，要求點(diǎn)云數(shù)據(jù)比較完整，對平面物體該方法能取得很好的效果，但對室外場景中比較散亂的點(diǎn)云應(yīng)用效果則不理想。

1.2 基于區(qū)域增長的分割方法

該方法將相同幾何特征的點(diǎn)云歸類到同一區(qū)域當(dāng)中，依靠區(qū)域擴(kuò)張形成一個迭代的過程,主要分自上而下、自下而上的兩種迭代形式。通過選擇點(diǎn)云中的種子片面或者種子點(diǎn)，以該種子為中心，向四周以法向量、坡度或者曲率差異等臨近準(zhǔn)則進(jìn)行增長,直到滿足條件為止。Wang和Tseng提出基于體元的分裂與合并算法，運(yùn)用到共面體元合并的計(jì)算過程中，在這過程中體元大小以及合并準(zhǔn)則對分割結(jié)果影響很大[4]。而且該算法需要依據(jù)準(zhǔn)則對分割過程進(jìn)行不斷的干預(yù)，計(jì)算過程比較耗時[5]。

1.3 基于圖的分割方法

該方法包括正則化圖割、最小割等。主要通過K鄰近閾值建立一個三維圖，圖中的節(jié)點(diǎn)為空間劃分體元或者三維點(diǎn)，除了這些節(jié)點(diǎn)外還有兩個終端節(jié)點(diǎn)S與T，S表示前景節(jié)點(diǎn)，T表示背景節(jié)點(diǎn)，連接節(jié)點(diǎn)的邊上的權(quán)重一般是歐幾里得距離的函數(shù)，如圖1所示。正則化圖割是一種全局最優(yōu)的分割方法，通過不斷迭代直至達(dá)到最優(yōu)條件：分割塊內(nèi)部的差異最小同時分割塊之間的差異最大[6]。除此之外還有基于歐氏距離和圖割的聚類方法及過分割和層次化合并的方法等，先將點(diǎn)云分割成超級體素，再根據(jù)超級體素之間的相似性對超級體素進(jìn)行層次化合并[7]。

圖1 圖割示意圖Fig.1 Schematic diagram of drawing

1.4 基于特征聚類的分割方法

該方法是一種多元統(tǒng)計(jì)分析方法，重點(diǎn)是識別點(diǎn)云聚類模式。史文中等提出了基于投影點(diǎn)密度的車載激光掃描距離圖像分割方法，根據(jù)投影密度的差異區(qū)分不同地物，以達(dá)到對原始點(diǎn)云語義分割的目的[8]；張雨禾等提出基于密度空間聚類的散亂點(diǎn)云特征提取方法,對相關(guān)概念進(jìn)行重定義并建立新的特征識別準(zhǔn)則,對潛在曲面形狀差異較大的模型表現(xiàn)出了較強(qiáng)的優(yōu)越性[9]。

1.5 基于模型匹配的分割方法

該方法有時也指基于參數(shù)的方法，常采用Hough Transform和RANSAC算法?；舴蜃儞Q的主要過程是檢測平面、圓柱、球體等基本形狀。RANSAC算法通過用最少的點(diǎn)構(gòu)建基元形狀，構(gòu)建形狀的點(diǎn)通過與點(diǎn)云數(shù)據(jù)集中所有的點(diǎn)進(jìn)行對比檢核以確定當(dāng)前形狀即是正確最優(yōu)的形狀集合。雖然這兩種算法有較強(qiáng)的穩(wěn)定性與魯棒性，RANSAC算法在有較多噪聲和異常值的數(shù)據(jù)集中表現(xiàn)良好，但參數(shù)模型的缺點(diǎn)在于分割結(jié)果依賴于點(diǎn)云密度、位置精度等，且不適用于數(shù)據(jù)量較大、基本幾何形狀較復(fù)雜的點(diǎn)云數(shù)據(jù)[5]。

1.6 基于機(jī)器學(xué)習(xí)的分割方法

機(jī)器學(xué)習(xí)是目前比較熱門的一個研究方向，它通過對大量的樣本進(jìn)行機(jī)器學(xué)習(xí)，得出樣本的一些特征知識，然后運(yùn)用先驗(yàn)知識對目標(biāo)數(shù)據(jù)處理，得到分割結(jié)果。該方法需要先獲取大量的樣本，再通過神經(jīng)網(wǎng)絡(luò)算法進(jìn)行大量運(yùn)算，對于處理數(shù)據(jù)量較大的點(diǎn)云還是有一定困難。

2 原理及方法

本文在前人研究的基礎(chǔ)上，提出一種基于空間相似性聚類的語義分割方法。其基本原理是：在空間距離聚類分割不足的基礎(chǔ)上，對分割不足的分割塊中具有相同幾何屬性的點(diǎn)集進(jìn)行精細(xì)化分割，再根據(jù)環(huán)境中地物語義屬性進(jìn)行組合分割，以提高語義分割識別的精確度，減少方法的計(jì)算量，提高方法的性能。其中，對于三維點(diǎn)云的語義分割目的在于：將屬于同一目標(biāo)物體表面的激光掃描點(diǎn)聚類到同一分割塊中，在對具有相似屬性的點(diǎn)云進(jìn)行聚類分割時，需要有一定的相似性測度，而點(diǎn)云之間的相似度有多種判定方法，最基本的是基于歐式距離聚類的方法。

本方法的思路是：先對點(diǎn)云數(shù)據(jù)進(jìn)行地面點(diǎn)、非地面點(diǎn)分離，然后對非地面點(diǎn)實(shí)施歐式聚類，再對歐式聚類分割塊中的點(diǎn)逐點(diǎn)計(jì)算其空間分布屬性，根據(jù)空間分布屬性再次進(jìn)行條件距離聚類分割得到最終的分割結(jié)果。其主要流程如圖2所示。

圖2 空間相似性分割算法流程圖Fig.2 Flowchart of spatial similarity segmentation algorithm

2.1 地面點(diǎn)與非地面點(diǎn)分離

據(jù)統(tǒng)計(jì)，車載或者地面站激光掃描儀獲取的點(diǎn)云數(shù)據(jù)中70%的數(shù)據(jù)屬于地面點(diǎn)。雖然地面點(diǎn)在點(diǎn)云數(shù)據(jù)中所占比例較大，但其地物種類比較單一，主要是道路及兩側(cè)的人行道或者道路旁側(cè)的草坪綠地等。而城區(qū)環(huán)境中的其他種類繁多、形態(tài)各異、數(shù)量較多的目標(biāo)主要位于非地面點(diǎn)中，若直接對原始點(diǎn)云數(shù)據(jù)分割，不僅會造成冗余計(jì)算，降低生產(chǎn)應(yīng)用效率，而且在很多情況下會引起分割錯誤等不良后果。如若直接對原始點(diǎn)云進(jìn)行歐式聚類，則無法有效地將環(huán)境中相離的兩個路燈分開，因?yàn)閮蓚€路燈均與地面相連，在歐式聚類時，它們最終會根據(jù)相鄰點(diǎn)距離聚類到同一分割區(qū)域中。

由上所述，在對點(diǎn)云進(jìn)行分割前需進(jìn)行地面點(diǎn)與非地面點(diǎn)分離處理。首先對原始點(diǎn)云數(shù)據(jù)進(jìn)行水平方向上格網(wǎng)化處理，并統(tǒng)計(jì)每個格網(wǎng)中的最小高程值；然后遍歷所有格網(wǎng)，對每個格網(wǎng)逐點(diǎn)比較其高程與當(dāng)前格網(wǎng)最小高程值的差異，若差異小于閾值則判定為地面點(diǎn)，若差異大于閾值則判定為非地面點(diǎn)；據(jù)此分離點(diǎn)云數(shù)據(jù)中的地面點(diǎn)與非地面點(diǎn)，為后續(xù)的非地面點(diǎn)的分割做準(zhǔn)備。

2.2 距離聚類

空間中同一地物的表面是連續(xù)表面，在點(diǎn)云數(shù)據(jù)中即為距離較近的點(diǎn)集。點(diǎn)云中的歐式聚類是指將點(diǎn)云中距離小于閾值的點(diǎn)聚類為同一集合。按照此原理，基于歐式聚類的點(diǎn)云分割會導(dǎo)致分割不足。實(shí)驗(yàn)時先對地面點(diǎn)與非地面點(diǎn)分離結(jié)果中的非地面點(diǎn)進(jìn)行歐式聚類，初步認(rèn)為空間中距離較近的點(diǎn)為某一同質(zhì)區(qū)域內(nèi)的內(nèi)部點(diǎn)，將非地面點(diǎn)中相離的點(diǎn)云分別聚類為不同的分割塊。

2.3 空間相似性分割

如前所述，將非地面點(diǎn)中的點(diǎn)云分別根據(jù)歐式距離聚類為不同的分割塊后，對于相互在空間上有粘連的地物而言，如電線桿與電線桿之間的電線，兩者在形態(tài)上存在很大差異，但是由于兩者在空間上粘連，故上一步的歐式聚類結(jié)果中兩者被聚類為同一分割塊，即分割不足現(xiàn)象。因此還需將分割不足的結(jié)果作為輸入，對每一塊分割不足的分割塊內(nèi)的點(diǎn)云進(jìn)行空間相似性分割。相似性分割測度為點(diǎn)云逐點(diǎn)分類的屬性，將屬性相同且距離小于閾值的點(diǎn)分割為同一分割塊；將距離小于閾值而屬性不同的點(diǎn)劃分到不同的分割塊中。

此步驟中，首先將分割不足的分割塊中的點(diǎn)云進(jìn)行逐點(diǎn)分類，賦予每個點(diǎn)一個屬性值，遍歷計(jì)算所有點(diǎn)后，對點(diǎn)云中具有相同屬性的點(diǎn)進(jìn)行距離聚類，即可以得到初始的語義分割結(jié)果，然后通過一定的優(yōu)化準(zhǔn)則對分割結(jié)果進(jìn)行優(yōu)化。

對于非地面點(diǎn)先逐點(diǎn)計(jì)算特征，將其分類為：桿狀點(diǎn)、面狀點(diǎn)、球類點(diǎn)以及未分類的點(diǎn)，逐點(diǎn)計(jì)算特征的方法如下:

（其中，M3+3為鄰域點(diǎn)集坐標(biāo)的協(xié)方差矩陣，為鄰域內(nèi)每個點(diǎn)的坐標(biāo)列向量，為鄰域內(nèi)所有點(diǎn)的坐標(biāo)平均值，即鄰域的中心〈重心〉點(diǎn)的坐標(biāo)，N為鄰域內(nèi)點(diǎn)的數(shù)量）。

由公式（1）中的協(xié)方差矩陣計(jì)算特征值λ1，λ2，λ3，其中λ1＞λ2＞λ3＞0；

對每個點(diǎn)分別計(jì)算以上α1D，α2D，α3D3個值中最大的值所對應(yīng)的生長要素的類型即為當(dāng)前點(diǎn)的空間形態(tài)類型；再對基礎(chǔ)分類后的點(diǎn)進(jìn)一步地語義分類，將桿狀點(diǎn)分為水平、豎直桿，將平面類的點(diǎn)分為水平面、立面。

精細(xì)分類的方法：

對于桿狀物，判斷其主方向的方位，主方向?yàn)樵擖c(diǎn)鄰域點(diǎn)的協(xié)方差矩陣最大特征值對應(yīng)的特征向量，主方向與天頂方向的夾角大于閾值，則為水平桿；主方向若與天頂方向的夾角小于閾值，則為立桿；

對于面狀物，判斷其法向的方向，法方向?yàn)樵擖c(diǎn)鄰域點(diǎn)的協(xié)方差矩陣最小特征值對應(yīng)的特征向量，若其法向與天頂方向的夾角小于閾值，則為水平面；若其法向與天頂方向的夾角大于某閾值，則為立面；

由以上步驟已初步得到每個點(diǎn)的空間形態(tài)特征，再以空間形態(tài)特征為判斷準(zhǔn)則對分割不足的分割塊中的點(diǎn)云進(jìn)行空間相似性分割，若距離小于閾值而空間形態(tài)不一致則分割為不同區(qū)域塊，由此解決前文中出現(xiàn)的分割不足問題。

經(jīng)過相似性分割處理后，對每個獨(dú)立的分割塊根據(jù)地物語義信息分類：大面積立面組成的地物為建筑物，球狀體與臨近豎直線狀地物為樹木，豎直線狀地物與鄰接的水平線狀地物為電線桿等。

3 實(shí)驗(yàn)結(jié)果及分析

按照上述技術(shù)方法對某地一塊十字路口的點(diǎn)云數(shù)據(jù)進(jìn)行分割實(shí)驗(yàn)，原始數(shù)據(jù)如圖3所示。實(shí)驗(yàn)時設(shè)定平面格網(wǎng)長度和寬度為1 m，歐式聚類閾值設(shè)為0.2 m，則地面點(diǎn)與非地面點(diǎn)分離后結(jié)果如圖4所示，其中藍(lán)色部分為地面點(diǎn)，綠色部分為非地面點(diǎn)，由圖可得，本文的方法可有效分離地面點(diǎn)與非地面點(diǎn)。

圖3 原始點(diǎn)云數(shù)據(jù)Fig.3 Original point cloud data

圖4 地面點(diǎn)與非地面點(diǎn)分離結(jié)果Fig.4 Separation result of ground point and non-ground points

圖5為對非地面點(diǎn)逐點(diǎn)計(jì)算空間形態(tài)特征的結(jié)果，其中，紅色部分表示空間垂直，主要為建筑物墻面表面點(diǎn)；橘黃色為水平面，主要為建筑物陽臺部分的表面點(diǎn)云；藍(lán)色為空間豎直線狀地物，主要為電線桿及路燈燈桿表面點(diǎn)；綠色為水平線狀地物，主要為電線表面點(diǎn)。除此之外，由圖可見，直接通過逐點(diǎn)計(jì)算空間形態(tài)的方法對空間雜亂點(diǎn)云進(jìn)行分類有很多錯分的結(jié)果，而且同一地物表面點(diǎn)的屬性計(jì)算結(jié)果不一致，主要由于計(jì)算空間形態(tài)時，點(diǎn)鄰域大小選擇對屬性計(jì)算結(jié)果的影響，故直接通過此方法進(jìn)行分割結(jié)果不佳。

圖6所示為根據(jù)本文提出的方法對該數(shù)據(jù)進(jìn)行分割及優(yōu)化后的結(jié)果，對比圖6及圖5可知：圖6的分割結(jié)果在正確性、一致性方面均優(yōu)于直接分類的結(jié)果。其中，藍(lán)色為地面，青色為建筑物，綠色為樹木，灰色為未分類目標(biāo)，黃色為電線桿，橙色為路燈，灰色為歸類目標(biāo)。但是依然存在一些問題：如圖6目視判別的所示電線桿的分割結(jié)果存在一定的問題，將電線桿分割成兩部分，需要后續(xù)優(yōu)化改進(jìn)。

圖5 非地面點(diǎn)逐點(diǎn)分類結(jié)果Fig.5 Point by point classif i cation results of non-ground point

圖6 語義分割結(jié)果Fig.6 Semantic segmentation results

4 結(jié)束語

本文主要探討了點(diǎn)云分割的方法，并通過具體實(shí)驗(yàn)介紹了基于空間相似性的語義分割流程，將數(shù)據(jù)量巨大的點(diǎn)云數(shù)據(jù)由多到少，由粗到細(xì)進(jìn)行逐步分割優(yōu)化，分割結(jié)果較直接歐式聚類與直接逐點(diǎn)分類結(jié)果的正確性、一致性等方面均有較大進(jìn)步。實(shí)驗(yàn)表明，采用該方法可以取得良好的分割效果，但還存在一定的缺點(diǎn)（如路燈的分割等），后續(xù)需增加更多的分割約束準(zhǔn)則，使得分割結(jié)果更優(yōu)；而且，在時間效率方面，后續(xù)研究及應(yīng)用中也需進(jìn)一步強(qiáng)化。