基于超體素的區(qū)域聚類的復(fù)雜場景分割

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

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

1 引 言

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

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

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

2 研究方法

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

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

2.1 點(diǎn)云數(shù)據(jù)獲取及預(yù)處理

本文采用RIEGL VZ-1000三維激光掃描儀獲取學(xué)校圖書館及周圍的點(diǎn)云數(shù)據(jù),采用的掃描儀掃描的范圍廣,獲取的數(shù)據(jù)密度大,采集的數(shù)據(jù)通常有上千萬個(gè)點(diǎn),除此之外掃描時(shí)操作方式和周圍環(huán)境的影響產(chǎn)生噪聲,這兩者給后續(xù)的數(shù)據(jù)處理造成極大不便,因此需要對(duì)數(shù)據(jù)進(jìn)行去適當(dāng)?shù)木喓腿ピ隱17]。本文利用Compare Cloud軟件的點(diǎn)云裁剪功能、統(tǒng)計(jì)濾波算法、八叉樹下采樣算法共同完成數(shù)據(jù)的預(yù)處理。

采用的統(tǒng)計(jì)濾波算法可以將稀疏分散在空間中的離群點(diǎn)噪聲去除,其算法原理較為簡單,只需統(tǒng)計(jì)每個(gè)點(diǎn)與其鄰域點(diǎn)的平均距離,確定其高斯分布,將不在標(biāo)準(zhǔn)距離閾值內(nèi)的點(diǎn)視為噪聲點(diǎn),將其去除。

2.2 點(diǎn)云超體素過分割

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

2.2.1 點(diǎn)云法向量計(jì)算

點(diǎn)云的法向量是三維空間中重要的幾何特征,應(yīng)用到點(diǎn)云處理(點(diǎn)云濾波、點(diǎn)云分類、點(diǎn)云分割、點(diǎn)云重建、點(diǎn)云配準(zhǔn))的各個(gè)方面。三維空間中的法向量不同于二維平面的法向量計(jì)算,其通過目標(biāo)點(diǎn)的鄰域內(nèi)所有點(diǎn)擬合平面,把平面的法向量當(dāng)作點(diǎn)的法向量。針對(duì)于此,可以采用主成分分析算法計(jì)算圖書館及周圍每個(gè)點(diǎn)的法向量。首先利用KD-Tree數(shù)據(jù)結(jié)構(gòu)搜索點(diǎn)的K個(gè)鄰域點(diǎn)構(gòu)建協(xié)方差矩陣:

(1)

(2)

其中,λ1>λ2>λ3>0 為特征值,v1、v2、v3分別為λ1、λ2、λ3對(duì)應(yīng)的特征向量,分別代表目標(biāo)點(diǎn)的3個(gè)主方向,其中最小特征值對(duì)應(yīng)的特征向量就為所求點(diǎn)的法向量。

2.2.2 超體素初次分割

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

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

Δ′=λ-cjD(ri,rj)

(3)

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

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

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

(4)

式中,Ni是點(diǎn)p的近鄰點(diǎn)點(diǎn)集;P為整個(gè)場景的點(diǎn)云:

(5)

2.2.3 細(xì)化邊界

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

2.3 改進(jìn)的區(qū)域生長融合

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

(6)

(7)

式中,Ci為鄰接超體素的質(zhì)心;Cq為當(dāng)前聚類區(qū)域的質(zhì)心。

本文改進(jìn)后的基于超體素的區(qū)域聚類算法具體步驟如下:

1) 對(duì)每個(gè)超體素內(nèi)的每個(gè)點(diǎn)遍歷其所有近鄰點(diǎn),如果當(dāng)前點(diǎn)與其某個(gè)近鄰點(diǎn)屬于不同的超體素,就把近鄰點(diǎn)所屬的超體素標(biāo)記為當(dāng)前超體素的鄰接超體素；

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

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

4) 重復(fù)2)、3)步驟直至所有超體素都劃分到相應(yīng)區(qū)域;

5) 計(jì)算合并得到的每個(gè)區(qū)域內(nèi)的點(diǎn)數(shù),將小于閾值的區(qū)域視為噪聲點(diǎn)去除。

3 實(shí)驗(yàn)與分析

本文的算法的實(shí)驗(yàn)環(huán)境:Intel(R)Core(TM)i7-4770 CPU @3.40 GHz、運(yùn)行內(nèi)存為8 GB,在Microsoft Visual Studio 2017開發(fā)平臺(tái)上采用C++實(shí)現(xiàn)。采集的數(shù)據(jù)預(yù)處理后,點(diǎn)數(shù)為302646,其如圖3所示。

圖3 預(yù)處理后點(diǎn)云數(shù)據(jù)Fig.3 Point cloud data after preprocessing

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

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

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

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

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

(a)區(qū)域生長車

(b)改進(jìn)前算法車

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

(a)區(qū)域生長樓梯

(b)改進(jìn)前算法樓梯

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

圖9 假山提取Fig.9 Rockery extraction

圖10 墻面提取Fig.10 Wall extraction

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

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

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

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

4 結(jié) 論

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

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