基于隨機森林方法的變電站三維建模點云自動分割

方彥軍，唐 勉，羅 嘉，龐志強

（1.武漢大學(xué) 自動化系，武漢 430072；2.廣東省電力科學(xué)研究院，廣州 510000）

0 引言

三維視覺技術(shù)在數(shù)十年的應(yīng)用和發(fā)展中已逐漸成熟起來，將這項新興技術(shù)運用于工業(yè)生產(chǎn)也隨之成為研究的焦點。現(xiàn)階段，我國變電站的信息可視化水平亟待提高，借助三維技術(shù)對變電站數(shù)據(jù)、圖像、視頻信息進(jìn)行歸納展示將極大地提升其管理智能化程度。對變電站進(jìn)行三維建模，由于對象場景較大，內(nèi)容復(fù)雜，為保證模型獲取的準(zhǔn)確性及快速性，需對變電站實行激光掃描，獲得的文件稱為點云。一份點云文件所包含的大量點中存在著相當(dāng)數(shù)量的冗余和噪聲點，因此需要對點云進(jìn)行聚類分割[1,2]，提取有效點再用于三維模型重構(gòu)。

目前，許多學(xué)者都在大型場景的點云分割方面展開了重要研究。文獻(xiàn)[3]針對曼哈頓式建筑大規(guī)模三維點云提出一種有效點自動分割提取方法，但適用對象局限于棱角分明的建筑物體。文獻(xiàn)[4]提出一種通用型準(zhǔn)則對城市非平坦區(qū)域的掃描數(shù)據(jù)進(jìn)行分割。文獻(xiàn)[5]利用隱含形狀模型描述物體，借助霍夫森林架構(gòu)對城市點云圖像進(jìn)行分塊檢測，并提出循環(huán)投票和距離權(quán)重投票機制。文獻(xiàn)[6]通過總結(jié)測量數(shù)據(jù)中隱含的空間信息，采用基于八叉樹的分割與合并方法幫助點云自動劃分為若干個共面點集。文獻(xiàn)[7]采用幾何特征進(jìn)行分割，這類方法對點云模型的要求極為嚴(yán)格，當(dāng)其應(yīng)用于粗糙實物點云時，容易產(chǎn)生過分割的問題。

當(dāng)前使用的點云分割方法，其效果很大程度上都依賴對象點的分布情況或初始種子點的選取，因此魯棒性不強。另外，對于變電站這種特殊的復(fù)雜場景，要在其三維掃描圖中進(jìn)行各類設(shè)備的模型自動識別本身也具有相當(dāng)大的難度[8]。為了更好地解決上述問題，本文提出運用隨機森林方法進(jìn)行變電站點云聚類分割，通過不同的點特征獲得不同的分類結(jié)果，再從中進(jìn)行比較和決策，幫助無序點云進(jìn)行無監(jiān)督學(xué)習(xí)聚類，取得了較好的實驗效果。

1 變電站點云特征分析

掃描獲得的數(shù)據(jù)是成千上萬個帶有三維坐標(biāo)信息（x, y, z）的點[9]，如圖1所示。對深度圖像平面分割的數(shù)學(xué)描述如下[10,11]：將深度圖像看作一個數(shù)據(jù)集合S，分割所采用的特征量集合F-{F1，F(xiàn)2，…，F(xiàn)n}，最終分割結(jié)果集合S-{S1，S2，…，Sn}。每個Si對應(yīng)一個Fi，表示依據(jù)特征量Fi分割得到的點集擬合而成的一個曲面，n為要求的分割曲面數(shù)。

圖1 變電站三維掃描全景圖

點云分割根據(jù)一定的特征量或者特征量組合對點云進(jìn)行聚類計算，也就是將原始點集分割成若干個具有簡單形狀意義且各自連通、互不相交的子集[12,13]。在不同的分割算法中，特征量的選擇不盡相同。分析變電站設(shè)備模型的空間幾何特性，除變壓器箱體之外，形狀比較特殊的計算對象主要有塔桿和絕緣子等。這些對象建模所用到最多的基本幾何體為圓柱體，且在一定區(qū)域內(nèi)這些物體的間隔固定，這是變電站點云分割工作可利用的一項特點。

就點云圖中的每一單個點而言，其本身除了坐標(biāo)信息之外，還需要計算一些特征作為點分類的依據(jù)[14]?？臻g曲面上任一點的法向量N是其重要的固有特征。計算單個點的法向量時，需借助該點周圍相鄰點所構(gòu)成的面片來對其法向量進(jìn)行估算[15]。由于一個點可與不同的相鄰點構(gòu)成不同的面片得到多個法向量，可采用平均加權(quán)的方法來做處理，如圖2所示。

圖2 點Pk的法向量計算

l為以Pk為頂點的三角形個數(shù)，αi為第i個三角形在頂點處的相對角，Vi為第i個三角形的法向量。則頂點Pk的法向量Nk計算公式如式(1)所示。

此外，每個點的曲率亦是其固有特征之一，它不隨曲面的位置、方向或參數(shù)化方法的變化而變化[16]。最普遍的邊緣檢測判據(jù)則是梯度幅值閾值判據(jù)，Canny算子[17]使用高斯函數(shù)進(jìn)行平滑后再由一階微分的極大值確定邊緣點。因此，每一點的梯度G及其與近鄰點構(gòu)成的曲率C也可作為聚類分割的特征判據(jù)。

2 點云分割

對變電站進(jìn)行三維建模，用來描述其中各種大小的圓柱體所需的幾何參數(shù)為底面半徑、柱體高度、中心線矢量。要得到這些參數(shù)需要對點云圖進(jìn)行準(zhǔn)確的區(qū)域分割。依據(jù)經(jīng)典的歐幾里得距離進(jìn)行分類需要設(shè)計一個合理的距離閾值[18]，閾值設(shè)置不當(dāng)會導(dǎo)致欠分割或過分割[19]。本文選擇先以點密度為基礎(chǔ)進(jìn)行初步分割，如圖3所示，然后利用隨機森林算法對初步分割得到的聚類的邊緣塊進(jìn)行更加精確的分類。

圖3 根據(jù)點云密度進(jìn)行初步分割

變電站點云分割的具體步驟如下：1）將三維點云圖平均劃分為n個方格；2）依據(jù)排列的空間位置對方格編號，依次計算每個方格的點密度Di(i=1,2…,n)；3）將D值相近且位置相鄰的方格合并成一類，并更新該類的位置信息及點密度信息；4）重復(fù)步驟1）～3），直至聚類結(jié)果穩(wěn)定；5）聚類結(jié)果中存在一部分特殊類，包含的是因點密度較小而獨立出來的方格，稱為邊緣方格。使用隨機森林算法對邊緣格中的點進(jìn)行計算和決策，使其能歸于相鄰的具有相似特征的聚類中，以完善分割結(jié)果；6）綜合基于密度的初步分割以及基于隨機森林方法的深入分割，得到最終的點云圖分割結(jié)果。

3 基于隨機森林方法的深入分割

隨機森林方法適合于多分類問題；訓(xùn)練和預(yù)測速度快；對訓(xùn)練數(shù)據(jù)有較強的容錯能力，即當(dāng)數(shù)據(jù)集中有大量數(shù)據(jù)缺失時可通過數(shù)據(jù)預(yù)估保持結(jié)果精度不變；能夠有效地處理大的數(shù)據(jù)集；可以處理沒有刪減的成千上萬的變量；能夠在分類的過程中生成一個泛化誤差的內(nèi)部無偏估計；并能檢測到特征之間的相互影響以及重要性程度；不易出現(xiàn)過度擬合；實現(xiàn)簡單且并行效率高。

3.1 隨機森林算法

在機器學(xué)習(xí)中，隨機森林由若干決策樹組成，決策樹將空間用超平面進(jìn)行劃分，每次分割都將當(dāng)前的空間一分為二。這些決策樹的形成采用了隨機的方法，決策樹之間沒有關(guān)聯(lián)。當(dāng)測試數(shù)據(jù)進(jìn)入隨機森林時，就是讓每一顆決策樹進(jìn)行分類，取所有決策樹中分類結(jié)果最多的作為最終結(jié)果。隨機森林就是一個包含多個決策樹的分類器，其輸出的類別是由個別樹輸出的類別的眾數(shù)而定。其具體步驟如下：

步驟1：在n個隨機樣本中用放回取樣的方式采樣n次，用這n個樣本來訓(xùn)練一個決策樹，訓(xùn)練結(jié)束后用這棵樹對剩余樣本進(jìn)行測試，并進(jìn)行誤差評估；

步驟2：設(shè)每個樣本有M個屬性，在決策樹的某節(jié)點分裂時，從這M個屬性中隨機選取m個屬性（m <

步驟3：決策樹形成過程中每個節(jié)點都按照步驟2來分裂，如果下一次該節(jié)點選出來的分裂屬性是剛剛其父節(jié)點分裂時用過的屬性，則表示該節(jié)點已經(jīng)達(dá)到了葉子節(jié)點，無須繼續(xù)分裂了；

步驟4：重復(fù)步驟1～3，建立大量的決策樹，如圖4所示，用它們對新的計算數(shù)據(jù)進(jìn)行分類，最終分類結(jié)果根據(jù)每個決策樹的投票多少來決定。

由于隨機森林每顆決策樹的訓(xùn)練樣本是隨機的，樹中每個節(jié)點的分類屬性也是隨機選擇的，因此就能保證不會產(chǎn)生過擬合現(xiàn)象。

圖4 依據(jù)不同分類屬性生成決策樹

3.2 針對變電站點云分割的算法設(shè)計

輸入帶有位置坐標(biāo)及特征信息的點數(shù)據(jù)，點的三維坐標(biāo)（可用于計算兩點之間的方向距離或歐式距離）、法向量N、梯度G、曲率C作為樣本屬性。隨機選取樣本訓(xùn)練生成多棵決策樹，運用決策樹對邊緣點進(jìn)行聚類，進(jìn)行多次決策與投票后，取投票數(shù)最多的結(jié)果為邊緣點的歸類結(jié)果。流程圖如圖5所示。

圖5 隨機森林進(jìn)行邊緣分割決策

三維圖像的每個區(qū)域?qū)?yīng)曲面物體上的一個有限曲面，分割完成后，可由相應(yīng)的深度數(shù)據(jù)計算該有限曲面的幾何矢量，并對分割后的曲面片以及它們的拓?fù)潢P(guān)系用特征關(guān)系圖描述，最后根據(jù)這些特征矢量基于特征關(guān)系圖匹配進(jìn)行識別。

4 實驗結(jié)果與分析

用以上提出的分割方法對變電站點云圖進(jìn)行聚類分割。關(guān)于初步分割劃分方格的尺寸，根據(jù)變電站掃描圖中點間距離，設(shè)置方格尺寸為2.5×2.5×2.5（坐標(biāo)單位），如圖6(b)所示。初步分割基于點云密度進(jìn)行，粗略將點云圖中的點密集部分分別成立為一個聚類Si（i=1,2, …, n），每個聚類包含的點記為P（x,y,z,N,C,G），其中（x,y,z）為每一點自帶的三維坐標(biāo)，而法向量N，梯度G，曲率C，則由公式計算得到。第二步，調(diào)用隨機森林程序，將點密度較小的方格及其鄰近方格中的點作為樣本輸入到程序中，訓(xùn)練生成的決策樹對邊緣點進(jìn)行分類。

實驗得到的結(jié)果如圖6(c)、(d)所示。圖6(c)用不同顏色顯示出分割結(jié)果中的幾個點分類作為示例；圖6(d)進(jìn)行簡單的曲面擬合驗證分割的效果。可以看出，在變電站錯綜復(fù)雜的幾何結(jié)構(gòu)下，點云分割效果很好。多次進(jìn)行該算法的實驗，其收斂結(jié)果穩(wěn)定且一致，說明該方法魯棒性較強。

圖6 變電站點云分割

5 結(jié)論

將三維可視化技術(shù)應(yīng)用于變電站管理系統(tǒng)有助于實現(xiàn)其在計算機上的仿真展示、導(dǎo)航定位、遠(yuǎn)程監(jiān)測和作業(yè)推演等。而這些功能開發(fā)的前提是變電站三維模型的重構(gòu)。點云分割是三維重構(gòu)的關(guān)鍵基礎(chǔ)。本文提出的點云分割方法借助隨機森林算法為變電站三維掃描圖中的點云數(shù)據(jù)實現(xiàn)了精準(zhǔn)的聚類分割，而且對于變電站大規(guī)模點云數(shù)據(jù)的計算，該方法保持了很好的魯棒性和穩(wěn)定性，克服了其它算法在分割效果上對初始種子點選取的依賴性。為變電站的三維模型重構(gòu)打下了可靠的基礎(chǔ)。

[1] Tahir Rabbani Shah.Automatic Reconstruction of Industrial Installations Using Point Clouds and Images[M].Netherlands. 2006.

[2] Mac Queen J.Some Methods for Classification and Analysis of Multivariate Observations//Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley,USA,1967: 28l-297.

[3] Carlos A Vanegas,Daniel G Aliaga,Bedrich B. Automatic Extraction of Manhattan-World Building Masses from 3D Laser Range Scans.IEEE Transactions on Visualization and Computer Graphic.2012,18(10):1627-1637.

[4] Moosmann F, Pink O, Stiller C.Segmentation of 3D Lidar Data in Non-flat Urban Environments Using a Local Convexity Criterion[C].Proceedings of IEEE Intelligent Vehicles Symposium.Piscataway, NJ,USA,2009:215-220．

[5] Hanyun WANG, Cheng WANG, Huan LUO,Peng LI,et al.Object Detection in Terrestrial Laser Scanning Point Clouds Based on Hough Forest[J].IEEE Geoscience and Remote Sensing Letters,2014,11:1807-1811.

[6] Miao WANG,Yi-Hsing TSENG.Automatic Segmentation of Lidar Data into Coplanar Point Clusters Using an Octree-based Split-and-Merge Algorithm[J].Photogrammetric Engineering and Remote Sensing,2010,76(4):407-420.

[7] Douilard B,Underwood J, Kuntz N,et al.On the Segmentation of 3D Lidar Point Clouds[C].Proceedings of IEEE International Conference on Robotics and Automation Piscataway,NJ,USA:IEEE,2011:2798-2805.

[8] Clarice S,Alexandre P.Challenges in 3D Reconstruction from Images for Diff i cult Large Scale Objects A Study on the Modeling of Electrical Substations[D].2012 14th Symposium on Virtual and Augmented Reality

[9] 王小超,劉秀平,李寶軍,張紹光.基于局部重建的點云特征點提取[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報.2013,25(5):659-665.

[10] Bianca Schon, Abu Saleh Mohammad Mosa, Debra F,Laefer.Octree-based indexing for 3D point clouds within an Oracle Spatial DBMS[J].Computers & Geosciences. 2013,51:430-438.

[11] 傅歡,梁力,王飛,趙季中.采用局部凸性和八叉樹的點云分割算法[J].西安交通大學(xué)學(xué)報.2012,46(10):60-64.

[12] 柯映林,單東日.基于邊特征的點云數(shù)據(jù)區(qū)域分割[J].浙江大學(xué)學(xué)報(工學(xué)版).2005,39(3):377-379.

[13] 孫永偉,孫殿柱,朱昌志,朱宗偉.散亂點云切片數(shù)據(jù)快速獲取與優(yōu)化[J].哈爾濱工程大學(xué)學(xué)報.2010,31(11):1514-1518.

[14] Mahmoud Fouad Ahmed, Carl T. Haas, Ralph Haas.Automatic Detection of Cylindrical Objects in Built Facilities[J].Journal of Computing in Civil Engineering,2014,28(3).

[15] 范劍英,于舒春,王洋,等.基于法向分量邊緣融合的深度圖像分割[J].計算機工程.2010,36(17):221-225.

[16] 王申懷,劉繼志.微分幾何[M].北京:北京師范大學(xué)出版社,1990.

[17] Canny J.A Computational Approach to Edge Detection[J].1EEE Transactions on Pattern Analysis and Machine Intelligence,1986,8(6):679-698．

[18] R. B. Rusu.Semantic 3D Object Maps for Everyday Manipulation in Human Living Environment. KI-Künstliche Intelligenz,2010,24(4):345-348.

[19] Ying ZHOU,Dan WANG, Xiang XIE, et al. A Fast and Accurate Segmentation Method for Ordered Lidar Point Cloud of Large-Scale Scenes[J].IEEE Geoscience and Remote Sensing Letters,2014,11:1981-1985.