基于超體素的區域聚類的復雜場景分割

李 文,劉德兒,王有毅,劉 鵬,施貴剛

(1.江西理工大學土木與測繪工程學院,江西 贛州 341000；2.安徽建筑大學土木工程學院,安徽 合肥 230601)

1 引 言

隨著三維激光掃描技術的發展,不僅能快速、非接觸式的獲取物體的相關信息,而且獲取的坐標、顏色和反射強度信息的精度越來越高,廣泛應用到文物古跡的保護[1]、自動駕駛[2-3]、城市規劃[4]、變形監測[5-7]及醫學應用[8]等領域中。點云分割是點云處理的關鍵步驟,分割質量的好壞直接影響目標識別、三維重建[9]和定位,因而成為了當下三維領域的研究熱點。

國內外學者對此進行了大量的研究,劉慧等[10]把獲取的植物深度圖像和彩色圖像轉換為顯著性點云,通過Mean-shift算法生成超體素,最后利用LCCP算法融合聚類,對樹木實現了精確的枝葉分離；胡文慶等[11]通過使用點云的坐標和反射率作為為聚類條件的模糊C均值算法對建筑和椅子進行了分割,其分割精度較低；黎榮等[12]提出把點云的坐標、法向量、平均曲率和高斯曲率組成八維特征向量,然后使用遺傳算法聯合模糊聚類算法對汽車零件進行分割,獲得了合理的分類,同時解決了FCM 算法陷入局部解的問題；張瑞菊等[13]通過分析古建筑的結構特性,提出了使用歐式聚類、模型擬合和基于包圍盒的算法對古代亭子分割,雖然把每一個結構部件都準確的分割出來了,但是需要提前知道建筑的尺寸信息；Rabbani等[14]提出選擇最小殘差值的點作為種子點,并采用表面平滑性和局部連通性為約束條件,對工業機械點云進行區域生長分割,其分割結果較為理想；Lu等[15]首先使用區域生長對點云進行過分割,然后在此基礎上再一次使用區域生長算法進行聚類合并,該方法對具有平滑的墻面的建筑的分割取得了較好的結果；Qi等[16]人提出Point Net++點云分割網絡框架,并對點云數據集打標簽后用此網絡進行訓練分割,最終取得了精確的分割結果,其分割操作較為繁瑣。

上述分割算法皆是針對于簡單場景或單一物體的分割,且各自具有局限性,難以適用于復雜的大場景的聚類分割。本文通過對采集的學校圖書館周圍的點云數據的分析,提出一種基于超體素的改進的區域增長分割算法,并通過實驗證明了該算法對起伏較大的面分割較好,并可以對復雜的場景實現有效的分割。

2 研究方法

本研究采用的超體素過分割及改進的區域融合算法對場景分割的流程圖如圖1所示。

圖1 算法流程圖Fig.1 Flow chart of proposed algorithm

2.1 點云數據獲取及預處理

本文采用RIEGL VZ-1000三維激光掃描儀獲取學校圖書館及周圍的點云數據,采用的掃描儀掃描的范圍廣,獲取的數據密度大,采集的數據通常有上千萬個點,除此之外掃描時操作方式和周圍環境的影響產生噪聲,這兩者給后續的數據處理造成極大不便,因此需要對數據進行去適當的精簡和去噪[17]。本文利用Compare Cloud軟件的點云裁剪功能、統計濾波算法、八叉樹下采樣算法共同完成數據的預處理。

采用的統計濾波算法可以將稀疏分散在空間中的離群點噪聲去除,其算法原理較為簡單,只需統計每個點與其鄰域點的平均距離,確定其高斯分布,將不在標準距離閾值內的點視為噪聲點,將其去除。

2.2 點云超體素過分割

超體素過分割是超像素分割在三維空間中的創新應用,其通過無監督分割把具有相同幾何屬性的點劃分為同一小塊中。目前超體素被廣泛使用在點云分割、邊界提取、三維識別的預處理階段中[18]。本文所使用的超體素分割是Yang等[19]2018年提出的直接在點上而非在體素上執行的過分割算法,其優點在于不需要種子點的選取,直接對點云中的每個點進行相似性距離度量,其具體原理如下文所述。

2.2.1 點云法向量計算

點云的法向量是三維空間中重要的幾何特征,應用到點云處理(點云濾波、點云分類、點云分割、點云重建、點云配準)的各個方面。三維空間中的法向量不同于二維平面的法向量計算,其通過目標點的鄰域內所有點擬合平面,把平面的法向量當作點的法向量。針對于此,可以采用主成分分析算法計算圖書館及周圍每個點的法向量。首先利用KD-Tree數據結構搜索點的K個鄰域點構建協方差矩陣:

(1)

(2)

其中,λ1>λ2>λ3>0 為特征值,v1、v2、v3分別為λ1、λ2、λ3對應的特征向量,分別代表目標點的3個主方向,其中最小特征值對應的特征向量就為所求點的法向量。

2.2.2 超體素初次分割

本文采用的超體素過分割算法在首次的粗分割過程中,首先把圖書館及周圍的整個場景的每個點都初始化為一個小的超體素塊及對應超體素的代表點,隨后在每次的迭代合并中采用公式(3)計算相鄰兩個超體素假如合并時能減少的能量,如果減少的能量大于零,就執行合并操作,其示意圖如圖2所示,深色和淺色點分別為超體素Si、Sj,箭頭指向的點分別為兩個超體素的代表點,經過計算合并可以減少能量,最終把超體素Sj合并到Si。

上面提到的是無任何干擾頻率情況下的匹配網絡，也可以說是理想狀態下的匹配網絡，由于土地資源和其他方面的原因，一個發射臺往往同時發射多個頻率，存在著雙頻共塔或多頻共塔的情況，頻率與頻率之間相互干擾嚴重，特別是共塔頻率會存在嚴重的高頻倒送干擾，為了消除共塔頻率的相互影響，必須增加一個或多個抑制網絡——阻塞網絡。阻塞網絡的主要作用是抑制共塔頻率的相互影響，最大限度地阻止共塔頻率對本頻的影響。圖2是三種常見的阻塞網絡組成形式原理圖。

Δ′=λ-cjD(ri,rj)

(3)

圖2 兩個超體素合并示意圖Fig.2 Schematic diagram of merging two supervoxels

其中,λ是一個正則化參數,為了減少人工的干預,增加算法的魯棒性,通過公式(4)計算λ代替人為設定其初始值值,具體思想為首先計算每個點與其鄰域點內的最小相異距離,然后再取其中值,之后在每輪的迭代中λ的值翻倍；cj為超體素Sj內的點數；D為兩點之間的相異距離；其計算方法如公式(5)所示；ri,rj分別為代表超體素Si、Sj的點 。

λ0=median{minp(D(p,Ni))|p∈P}

(4)

式中,Ni是點p的近鄰點點集;P為整個場景的點云:

(5)

2.2.3 細化邊界

為了使最終得到的超體素的邊界形狀更加規整,避免在邊界處的分割出現越界現象,本文進行了重新分配相鄰超體素之間的邊界點的方式細化邊界。具體方法為:如果點與近鄰點分別歸屬于不同超體素,則認為這兩點是邊界點,然后通過這一方法找出所有邊界點,隨后分別計算兩個相鄰的超體素的代表點與其邊界點的相異距離,并判斷其大小關系,如果邊界點與鄰接超體素的代表點之間的距離小于同屬于一個超體素的代表點的相異距離,就把這個邊界點重新分配給鄰接超體素。

2.3 改進的區域生長融合

在超體素的基礎上,采用區域生長方式進行區域融合,使其最終聚類成為與現實物體對應的有意義的區域。為了使圖書館的不平整墻面、散亂的枝葉、路燈、樓梯、假山盡量合并,避免被當作噪聲去除,本文對融合算法加以改進:通過計算每塊區域聚類的種子超體素與其第一個鄰接超體素塊的高程差,與給定的閾值比較,把將要合并聚類成的區域預判為豎直或傾斜面和地面或與其平行平面,前一種面類型起伏較大,后一種面是表面比較光滑的平面,分別給定不同的法向量閾值進行生長聚類；采用K均值聚類算法的均值思想,當每次有新的超體素加入到當前合并區域里,就更新當前合并區域的法向量等幾何信息,隨后分別通過公式(6)和公式(7)計算與鄰接超體素塊的法向量夾角和正交距離作為區域聚類的融合條件。

(6)

(7)

式中,Ci為鄰接超體素的質心;Cq為當前聚類區域的質心。

本文改進后的基于超體素的區域聚類算法具體步驟如下:

1) 對每個超體素內的每個點遍歷其所有近鄰點,如果當前點與其某個近鄰點屬于不同的超體素,就把近鄰點所屬的超體素標記為當前超體素的鄰接超體素；

2) 根據上文所述的方法計算高程差。并設置不同的法向量夾角閾值;

3) 采用改進的方式計算區域間的法向量夾角和正交距離度量相鄰超體素的相似性,進行合并操作,直至合并區域與所有其鄰接超體素不滿足條件為止；

4) 重復2)、3)步驟直至所有超體素都劃分到相應區域;

5) 計算合并得到的每個區域內的點數,將小于閾值的區域視為噪聲點去除。

3 實驗與分析

本文的算法的實驗環境:Intel(R)Core(TM)i7-4770 CPU @3.40 GHz、運行內存為8 GB,在Microsoft Visual Studio 2017開發平臺上采用C++實現。采集的數據預處理后,點數為302646,其如圖3所示。

圖3 預處理后點云數據Fig.3 Point cloud data after preprocessing

對數據進行過分割時,設置求法向量的鄰域值K為7,超體素分辨率設置為2。初次過分割和細化邊界后的最終超體素分割圖如圖4所示。在圖4(a)中每個超體素的邊界線非常不規則,并且相鄰超體素之間出現跨越邊界的現象,經過細化邊界操作后,每個超體素的形狀規則,其之間的邊界也定義明確。

圖4 超體素過分割Fig.4 Supervoxel oversegmentation

在區域生長合并時,首先根據超體塊的大小設置高程差為0.25,如果大于0.25的就判定將要生成的區域為豎直或傾斜面,將其聚類的法向量夾角閾值參數設置為70,將小于0.25的,就提前認定為地面或者與地面平行的平面,由于地面很平整,將其設置一個較小的法向量夾角閾值15；其正交距離閾值在聚類過程中動態獲取。為了更加直觀地體現本文提出的算法的分割效果的優良性,本文采用PCL庫里的區域生長分割算法、改進前的超體素分割融合算法與其對比。對于兩種對比算法使用的KD-tree中的k鄰域搜索、法向量夾角閾值和最小聚類點數關鍵參數均與本文改進算法設置的參數一樣。三種算法分割的結果如圖5所示。為了更加清晰的顯示分類結果,現把每類地物單獨提取出來顯示,如圖6～圖11所示。

圖5 各算法分割效果圖Fig.5 Segmentation effect diagram of each algorithm

圖6 路燈提取Fig.6 Street light extraction

(a)區域生長車

(b)改進前算法車

(c)本文算法車圖7 車輛提取Fig.7 Vehicle extraction

(a)區域生長樓梯

(b)改進前算法樓梯

(c)本文算法樓梯圖8 樓梯提取Fig.8 Stair extraction

圖9 假山提取Fig.9 Rockery extraction

圖10 墻面提取Fig.10 Wall extraction

圖11 小樹木提取Fig.11 Small tree extraction

對于算法分割的結果,本文把不同的類別賦予不同的顏色,從圖5的3種算法各自分割的整體結果圖,可以看出區域生長算法的地面與其他物體分為了一類,改進前算法及本文算法均把地面單獨分為了一類。從圖6可以看出,區域生長算法分割只提取得到了6根路燈,缺失了2根,并且由于分割結果中點數小于閾值,造成部分路燈的下部分、燈頭部分或整個燈頭的缺失；改進前的算法雖然得到了8根路燈,但是該算法把其中的4根路燈分為了上下兩截,同時提取的路燈中也存在路燈的下部分和燈頭部分的缺失的現象；本文算法把8根路燈都完整地提取出來了。從圖7中的車的提取,可以看出區域生長算法把兩輛車的正面和側面均分為了一類,并且其中一輛車的側面還存在欠分割；改進前算法提取的兩輛車的其中一輛的正面和另外一輛的頂部均分為了兩類；本文算法均把兩輛車的正面、側面和頂部各自分為了一類。從圖8的樓梯提取的結果中可知,區域生長算法把樓梯與墻面、地面、假山分為了一類；改進前算法把樓梯分為了多個類；本文算法雖然在樓梯的一側扶手的邊緣處存在欠分割現象,但把樓梯的其余部分分為了一類,提取效果理想。從圖9的三幅圖可以看出,區域生長算法沒有把假山從其他物體中分割出來；改進前的算法把假山分為了4類；只有本文算法把假山分割成了一個整體。從圖10中可以看出,區域生長和改進前的算法均對圖書館的墻面的分割存在欠融合想象,并且區域生長算法把凹凸的墻面與地面等物體分為了一類,同時避雷針也沒有分割出來；本文的算法均把凹凸的墻面、避雷針、上部的墻面、其余墻面各自分為了一類。圖11的三幅圖為三種算法對一棵掃描較好的小樹的提取的圖,可以很清楚的看出區域生長和改進前的算法對樹的樹冠超體素沒有很好的融合,并且區域生長算法提取的小樹的樹根和部分樹葉缺失了；本文算法把小樹的葉子和樹根超體素融合為了一個整體,提取出來了。同時結合圖5的各算法的分割效果圖,可以進一步看出區域生長算法對樹木的點云信息損失與其他兩種算法相比較為嚴重；圖5(b)改進前的算法結果圖可知,樹葉存在欠融合現象；從圖5(c)可以看出雖然提出的算法沒有把各棵樹都完整的單獨分割為一類,但是也盡量的把具有相似的幾何信息的枝葉超體素生長融合為了一類。

本文采用分割后得到的區域數量和通過分割前后的點數計算的點云損失率,定量地對比這三種算法,如表1所示。從表1中可以看出,雖然PCL庫里的區域生長算法對場景的分類數為853,在三者中最小,但是這是由于過度聚類造成的,同時點云損失率為55.7 %,為三者最高,點云幾何信息損失極為嚴重；改進前后算法的點云損失率比較接近,分別為6.9 %和4.3 %,但是改進前算法出現了欠聚類現象,最終分割得到2653塊區域,是改進后算法的區域數量的2.49倍。綜上所述本文提出的算法無論從視覺上還是兩項指標的衡量上,均優于改進前和區域生長算法。

表1 不同分割算法下的損失率和區域塊數Tab.1 Loss rate and number of regions under different segmentation algorithms

4 結 論

針對復雜場景分割較難的現狀,本文提出了一種基于超體素的區域生長算法,該算法不需要對圖書館及周圍場景的先驗知識,僅計算點云固有的幾何屬性,就能完成精確分割。首先使用了最新的超體素分割算法,減少了跨越邊界的現象的發生,使最終的每塊區域的邊界與真實邊界相吻合。其次為了避免屬于同一類的復雜物體被分割為多個類別,同時減少因欠分割而被當作噪聲去除的現象的發生,對區域生長算法進行了兩點改進:①對平滑的平面和起伏較大的面分別使用不同的法向量夾角閾值進行聚類合并；②在生長過程中,當當前合并區域改變時,就重新計算其法向量等幾何信息。改進后的算法與區域生長算法和改進前的算法對自行采集的數據進行分割,實驗結果表明,只有本文提出的算法對場景的各個物體進行了正確的分割,同時在點云損失方面優于后兩種算法。總的來說本文的算法對復雜場景分割具有準確性和可靠性,為后續的三維重建、目標識別、物體的分類奠定了良好的基礎。

本文的算法的不足之處在于引入了新的參數,使在分割過程中自動化程度降低,且過分割得到的超體素的好壞,直接影響最終的區域聚類分割效果,在未來的學習研究中可以消除此參數和減小依賴程度,增加算法的自適應能力。