汪 驍 周大偉 占喜林 周 健 刁鑫鵬 耿智江

(中國礦業(yè)大學(xué)環(huán)境與測繪學(xué)院,江蘇 徐州 221116)

機(jī)載LiDAR是一種空間數(shù)據(jù)傳感器,可快速獲取物體的三維空間結(jié)構(gòu)信息,近年來成為了礦區(qū)地表監(jiān)測的重要手段之一。礦區(qū)地物作為煤礦開采規(guī)劃的重要參考依據(jù),對其進(jìn)行準(zhǔn)確分割是礦區(qū)后續(xù)部署的重要環(huán)節(jié)。但由于礦區(qū)地表起伏較大、地物混雜種類繁多、機(jī)載LiDAR點云數(shù)據(jù)呈現(xiàn)空間無序性等諸多影響因素的存在,利用常規(guī)點云分割算法進(jìn)行礦區(qū)地物的準(zhǔn)確分割存在一定的困難。

常規(guī)的點云分割算法主要分為基于屬性分割[1-3]、基于圖分割[4-7]、基于模型分割[8]、邊緣檢測分割[9]、區(qū)域增長分割[10-14]及深度學(xué)習(xí)分割[15-17]。其中基于屬性分割利用點云自身的特征作為閾值完成分割,但依賴于點云密度且分割精度較低;基于圖分割算法利用權(quán)值描述點與點的相似性,該方法分割精度較高但效率較低;基于模型分割可以有效分割規(guī)則幾何物體,但在復(fù)雜場景的點云分割效果欠佳;邊緣檢測分割主要靠檢測物體邊緣進(jìn)行分割,該方法分割效率高但易受到噪點影響;基于區(qū)域增長分割算法通過選取最小曲率的種子,按法線與曲率為閾值進(jìn)行區(qū)域增長,但選取的種子點優(yōu)劣直接決定了最終分割結(jié)果的優(yōu)良;深度學(xué)習(xí)分割效果最佳,但只適用于小范圍的數(shù)據(jù)集分割,對大場景分割效率極低。針對以上算法的缺點,眾多學(xué)者對其進(jìn)行了一定的改進(jìn)。例如,柯映林等[1]依據(jù)曲率變化劇烈程度實現(xiàn)了區(qū)域點云的邊界提取與分割,但在平滑區(qū)域該算法的適用性較差。Saglam等[2]提出了基于點云局部曲率相似度合并的非連續(xù)區(qū)域增長算法,該方法有效解決了噪聲點對精確分割的影響,但分割結(jié)果和點云密度等其他因素相關(guān)。Felzenswalb等[5]利用點云的數(shù)據(jù)結(jié)構(gòu)圖,提出一種快速的基于圖優(yōu)化的分割算法,用權(quán)值描述點之間的相似性來進(jìn)行點云分割,但該方法需要計算所有臨近點間的相似性,算法耗時較長。Cheng等[6]提出了一種結(jié)合點云法線信息結(jié)構(gòu)圖與收縮-擴(kuò)展技術(shù)的屋頂點云分割方法,該方法需要對點云平面條段精細(xì)分割,效率較低。鄒鵬等[8]提出一種改進(jìn)的RANSAC點云分割算法,該算法可以有效分割工件型面特征,但分割效果依賴于合并閾值的選擇。丁承君等[9]提出一種基于PCL庫與邊緣提取的分割算法,通過比較K鄰域法線夾角搜尋邊界特征進(jìn)行分割,但該方法需要經(jīng)過大量實驗進(jìn)行結(jié)果篩選尋找最優(yōu)解。Song等[10]基于分割網(wǎng)絡(luò)特征圖提出BSA模塊充分利用種子點進(jìn)行分割且取得了不錯的分割效果。錢建國等[16]利用最小分割與深度學(xué)習(xí)聯(lián)合的方法對室內(nèi)粘連點云進(jìn)行分割,分割結(jié)果具有較高的精度與數(shù)據(jù)完整性。

目前常用的分割算法均實驗于簡單的場景分割或點云數(shù)據(jù)集的分割,且算法流程均具有各自的局限性,對于類似礦區(qū)的復(fù)雜大場景點云地物分割的適用性也有待研究。針對以上問題,本文提出一種優(yōu)化超體素凹凸性的聚類分割算法。主要步驟:首先體素化原始點云,各體素中心作為初始種子點,根據(jù)半徑搜索法與基于顏色、歐式距離和法向量的特征距離完成超體素的初次分割;其次采用FCM算法計算超體素邊界點與其相鄰超體素中心的隸屬度,更新各超體素邊界及中心點,完成超體素邊界細(xì)化;最后相鄰超體素的中心點高程作差,對符合高程差閾值要求的凸相鄰超體素進(jìn)行合并,同時更新超體素中心,進(jìn)行超體素迭代聚類,最終獲取礦區(qū)地物點云。

1 研究方法

點云過分割指將屬于同一物體的點按某一標(biāo)準(zhǔn)分割為多個集合。依據(jù)礦區(qū)點云的空間屬性將其過分割成多個集合,計算相鄰集合之間的相似度并按相似度的判定閾值對各集合進(jìn)行聚類操作,通過該思路可以實現(xiàn)礦區(qū)點云分割。具體算法流程如下:首先利用超體素分割算法對原始點云進(jìn)行初次過分割聚類。其次針對初始分割得到的超體素邊界存在越界現(xiàn)象,對超體素邊界點用FCM算法計算邊界點對臨近超體素中心的隸屬度,從而更新超體素的邊界與中心點。最后根據(jù)超體素中心點高差與臨近超體素的凹凸性對超體素迭代聚類,防止出現(xiàn)類似地物與地面點歸為一類的欠分割現(xiàn)象,確保最終分割地物的準(zhǔn)確性。具體流程如圖1所示。

1.1 超體素的生成

1.1.1 礦區(qū)點云超體素過分割

超體素是一種由體素數(shù)據(jù)組成的集合,是由體素構(gòu)成的三維空間內(nèi)的不規(guī)則的幾何體。超體素分割算法的目的不在于準(zhǔn)確地分割點云,而是對獲取的點云數(shù)據(jù)進(jìn)行過分割,根據(jù)分割點云之間的相似性,將相似點云進(jìn)行合并。

超體素分割算法具體步驟如下:

(1)將預(yù)處理后的點云P1按照半徑r1體素化,利用八叉樹獲取每個體素內(nèi)最接近中心的點作為該體素的代表點,這些中心點的集合為點云P2,以體素為單元計算P2點云的法向量。計算公式如下

式中,λ1、λ2、λ3為特征值,且λ1>λ2>λ3;v1、v2、v3分別為λ1、λ2、λ3對應(yīng)的特征向量值,分別代表目標(biāo)點的3個方向,其中最小特征值對應(yīng)的特征向量為所求點的法向量。

(2)點云P2按照半徑r2體素化,利用八叉樹獲取每個體素的中心點,加入到初始種子點集合S1中,對S1進(jìn)行半徑搜索篩選,確定最終種子點集合S。根據(jù)KdTree獲取種子點的鄰接關(guān)系,計算體素與相鄰種子點的特征距離,計算公式如下:

式中,Dc為歸一化RGB空間下的歐式距離;Ds為兩相鄰點之間的空間歐氏距離;Dn為兩點法向量之間的弧度;ωc、ωs、ωn分別為顏色、歐式距離和法向量的權(quán)重;Rs為S1的搜索半徑。

(3)以種子點為中心向外迭代,比較體素與種子點間的特征距離大小,特征距離越小,表明二者越相似,標(biāo)記該體素內(nèi)的所有點屬于此種子點,直到每個種子點達(dá)到搜索范圍邊界或沒有符合合并條件的體素為止。

1.1.2 基于FCM算法優(yōu)化超體素邊界

超體素分割效果取決于初始種子點的選取和初始固定的體素分辨率。若體素分辨率過低會導(dǎo)致不同點被分割至同一體素中,導(dǎo)致初次分割生成的超體素出現(xiàn)邊緣形狀不規(guī)則、相鄰超體素間的邊界存在越界問題;若分辨率過高則會大大降低算法的效率,導(dǎo)致后續(xù)的超體素聚類存在欠分割問題。為解決這一問題本文引入模糊C均值聚類算法對超體素邊界進(jìn)行細(xì)化從而解決超體素越界問題。模糊C均值聚類算法(FuzzyC-means,FCM)是一種基于目標(biāo)函數(shù)的模糊聚類算法,不同于硬性劃分算法,FCM算法是模糊劃分,其并不會明確規(guī)定某一點歸屬于哪一類。在{x1、x2、x3、…、xn},獲取當(dāng)前超體素的鄰接超體素并歸為集合A={a1、a2、a3、…、ac},對應(yīng)的各超體素聚類中心為V={v1、v2、v3、…、vc}。實際劃分中超體素邊界點的屬性并不清晰,因此需要利用FCM算法引入隸屬度對點云進(jìn)行模糊劃分。隸屬度描述邊界點屬于相鄰超體素的不確定性,可以客觀反映邊界點的隸屬程度,從而在超體素與鄰接超體素間尋找最優(yōu)解。

基于FCM的邊界細(xì)化算法具體流程如下:

(1)將標(biāo)記與臨近點不同的點定義邊界點,根據(jù)標(biāo)記大小順序選定某一超體素聚類,按邊界點定義尋找出當(dāng)前超體素的邊界點歸為數(shù)據(jù)樣本集X=

(2)根據(jù)公式(5)計算樣本集中第i個邊緣點對第k個臨近超體素聚類中心的隸屬度μik且需滿足式(6)。

式中,dik為歐氏距離;m為樣本的特征數(shù);b為模糊指數(shù)(取值范圍為1≤b≤∞,其通常設(shè)為2或2.5)。

(3)由步驟(2)求得的樣本點對聚類中心的隸屬度μik更新聚類中心集合V及目標(biāo)函數(shù)J,方法如下:

設(shè)Ik={i|2≤c

(4)執(zhí)行步驟(2)、(3)反復(fù)更新聚類中心、數(shù)據(jù)隸屬度和目標(biāo)函數(shù),當(dāng)Jn+1/Jn收斂或達(dá)到最大迭代次數(shù)時,便得到了當(dāng)前超體素邊界點對于鄰接超體素聚類的隸屬度,從而完成了當(dāng)前超體素的邊界細(xì)化。

(5)按照標(biāo)記大小順序遍歷所有超體素,重復(fù)上述步驟完成所有超體素的邊界細(xì)化。

1.2 改進(jìn)凹凸性聚類算法融合超體素

在細(xì)化邊界超體素的基礎(chǔ)上,采用基于相鄰聚類凹凸性的局部凸連接算法,使過分割的場景超體素聚類成與實際物體相對應(yīng)的區(qū)域。為使礦區(qū)地表典型地物例如房屋、圍墻、高壓線塔、信號接收站經(jīng)過聚類算法后盡量合并,防止出現(xiàn)欠分割現(xiàn)象,本文對局部凸連接算法進(jìn)行優(yōu)化:計算當(dāng)前超體素類中心與其相鄰超體素類中心的高程差,與給定的閾值相比較,若在閾值范圍內(nèi),則從當(dāng)前超體素類的鄰接列表里剔除該相鄰超體素,隨后以凹凸判定準(zhǔn)則CC(Extended Convexity Criterion)及其補(bǔ)充準(zhǔn)則SC(Sanity criterion)為依據(jù)判斷當(dāng)前超體素與其余鄰接超體素的凹凸關(guān)系,如圖2所示。

圖2 相鄰超體素凹凸關(guān)系Fig.2 Bump relationship of adjacent super-voxel

擴(kuò)展凸性準(zhǔn)則利用相鄰點云的中心連線與法向量的夾角判斷凹凸性。圖2中x1、x2為相鄰超體素的質(zhì)心,、為其對應(yīng)的法向量,α1為與的夾角,α2為與的夾角。由圖可知,當(dāng)α1<α2時相鄰超體素為凹關(guān)系,當(dāng)α1>α2時相鄰超體素為凸關(guān)系。同時為防止測量引起的平面較小凹凸誤差,需要引入某一閾值β去除錯誤,至此CC的判定規(guī)則如下:

某些特殊情況下,兩鄰接超體素具有公共點而不具有公共邊,此時需要加入凹凸判定的補(bǔ)充準(zhǔn)則SC對其進(jìn)行補(bǔ)充判定。SC利用相鄰點云法向量叉乘向量與中心連線的夾角判斷兩面形成凸面的概率。如圖3所示,,用θ的大小判斷相鄰超體素的連接方式,θ越接近90°,表明二者連接方式越接近邊連接;越接近0°,表明二者連接方式越接近點連接。設(shè)置閾值θ′,保留θ大于閾值的凸關(guān)系,其余舍棄,至此SC的判定規(guī)則如下:

改進(jìn)后的融合超體素的凹凸性聚類算法具體步驟如下:

(1)按標(biāo)記大小順序遍歷超體素的中心點,獲取其鄰接關(guān)系,計算相鄰超體素的中心點高程差,判定兩超體素是否符合合并條件。

(2)采用CC與SC的判定規(guī)則判斷相鄰超體素的凹凸性,對滿足凸面關(guān)系的鄰接超體素進(jìn)行合并操作,直到所有鄰接超體素不滿足合并條件。

(3)更新融合超體素的中心點,重復(fù)步驟(1)、(2)直到所有超體素都完成遍歷且相鄰超體素不滿足融合條件。

(4)根據(jù)點云標(biāo)記完成分割,輸出結(jié)果。

2 實驗與分析

2.1 實驗數(shù)據(jù)

點云數(shù)據(jù)由大疆M600無人機(jī)搭載ARS-450i激光雷達(dá)掃描內(nèi)蒙古鄂爾多斯某首采工作面地表獲取。但采集的數(shù)據(jù)受到儀器精度、電磁波衍射、及環(huán)境自身的影響,原始數(shù)據(jù)中含有大量噪聲,因此利用CloudComapre軟件對點云數(shù)據(jù)進(jìn)行預(yù)處理。隨后采用1.1節(jié)算法處理,對比算法結(jié)果可知改進(jìn)后算法得到的超體素邊界較為規(guī)則,超體素間基本不存在類似部分地表點與建筑點邊界越界現(xiàn)象。最終得到的實驗點數(shù)總計49 118 377,具體如圖4所示。

圖4 點云對應(yīng)地物超體素生成對比Fig.4 Comparison of super-voxel generation effect of house point cloud

2.2 實驗結(jié)果

考慮到礦區(qū)內(nèi)房屋、電塔等地物的高度,因此在進(jìn)行超體素凹凸性合并時設(shè)置高差閾值為2.5～4 m,相鄰超體素在該范圍內(nèi)不考慮凹凸性合并,范圍外則根據(jù)1.2節(jié)的凹凸準(zhǔn)則判定是否合并。從分割數(shù)與點云損失率對3種方法的礦區(qū)整體點云分割效果進(jìn)行對比,具體效果如圖5和表1所示。

表1 整體點云分割結(jié)果Table 1 Result of all point cloud segmentation

圖5 整體點云分割效果Fig.5 Effect of all point cloud segmentation

2.3 討論及分析

結(jié)合圖5與表1可知,在整體上3種方法均將礦區(qū)地面與地物分割開,但在地物的分割細(xì)節(jié)、點云損失率等方面存在較大差異。改進(jìn)前的超體素分割算法沒有點云損失且分割數(shù)與本文算法接近,但整體分割效果較差,存在大面積過分割現(xiàn)象,對地物的整體提取效果不利;區(qū)域增長算法點云分割數(shù)是其余2種算法的2倍左右,在部分區(qū)域的點云分割效果與本文算法較為接近,但存在44%的點云損失率,且存在原始數(shù)據(jù)特征信息丟失的現(xiàn)象,不利于地物的準(zhǔn)確提取。因此從整體分割點云的角度看,本文分割算法可以在保證數(shù)據(jù)完整的情況下,仍可以滿足礦區(qū)在地物分割上的效果需求。

對區(qū)域內(nèi)的部分房屋、信號塔及植被3種地物的分割細(xì)節(jié)效果進(jìn)行對比。由圖6可知,在房屋分割上,本文算法成功將圖中的三間房屋的相鄰超體素完全聚類并分割出來,與之對比,其他2種算法并沒有將房屋完全分割成一類,存在將部分地面點歸于房屋一類或部分房屋邊角超體素未被歸于一類;在信號塔分割上,本文算法可以明顯看出整個電塔被歸為一類,不存在上下部分欠分割現(xiàn)象,而改進(jìn)前的超體素分割算法明顯將塔尖與塔身等區(qū)域分為多類,區(qū)域增長算法則是在聚類后電塔大量點云缺失只剩下一半;在地表植被分割上,本文算法在植被密集區(qū)分割效果較好,可以分割出大區(qū)域植被,在植被稀疏區(qū)分割同樣有較好的效果,改進(jìn)前超體素的分割算法在大植被區(qū)存在欠分割現(xiàn)象,而區(qū)域增長算法存在大量植被點云缺失。

為定量分析算法效果,從精確度與召回率兩方面對放大區(qū)域的點云分割效果進(jìn)行定量比較,計算公式如下:

式中,TP為算法分割的正確點數(shù);FP為算法未分割的正確點數(shù);FN為算法分割的錯誤點數(shù)。

定量分析結(jié)果如表2所示,3種算法欠分割現(xiàn)象均較少,因此點云召回率大部分在90%以上,但存在點云缺失或過分割現(xiàn)象,導(dǎo)致精確度存在較大的差異。由于本文算法解決了超體素分割邊界越界現(xiàn)象以及凹凸性分割時部分超體素凸連接錯誤聚類的問題,因此在精確度與召回率相對其余2種算法均有了一定程度的提高,相較于改進(jìn)前超體素分割算法加權(quán)平均精確度提升了13.1%,加權(quán)平均召回率提升了2.3%;與區(qū)域增長算法相比加權(quán)平均精確度提升了30%,加權(quán)平均召回率提升了6.3%。

3 結(jié) 論

針對常規(guī)點云分割算法在礦區(qū)地物分割效果不理想的現(xiàn)狀,本文提出一種優(yōu)化超體素凹凸性的礦區(qū)地物提取算法,該方法克服了區(qū)域生長算法分割點云缺失現(xiàn)象及傳統(tǒng)超體素分割算法的過分割問題,可以在保證點云完整性的前提下,完成地物較為準(zhǔn)確的分割。比改進(jìn)前超體素分割算法的加權(quán)平均精確度提升了13.1%,加權(quán)平均召回率提升了2.3%,比區(qū)域增長算法的加權(quán)平均精確度提升了30%,加權(quán)平均召回率提升了6.3%。