優化超體素凹凸性的礦區地物提取算法研究

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

(中國礦業大學環境與測繪學院,江蘇 徐州 221116)

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

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

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

1 研究方法

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

1.1 超體素的生成

1.1.1 礦區點云超體素過分割

超體素是一種由體素數據組成的集合,是由體素構成的三維空間內的不規則的幾何體。超體素分割算法的目的不在于準確地分割點云,而是對獲取的點云數據進行過分割,根據分割點云之間的相似性,將相似點云進行合并。

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

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

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

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

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

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

1.1.2 基于FCM算法優化超體素邊界

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

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

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

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

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

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

設Ik={i|2≤c

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

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

1.2 改進凹凸性聚類算法融合超體素

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

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

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

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

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

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

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

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

(4)根據點云標記完成分割,輸出結果。

2 實驗與分析

2.1 實驗數據

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

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

2.2 實驗結果

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

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

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

2.3 討論及分析

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

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

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

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

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

3 結 論

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