方彥軍，唐 勉，羅 嘉，龐志強(qiáng)

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

0 引言

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

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

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

1 變電站點(diǎn)云特征分析

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

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

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

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

圖2 點(diǎn)Pk的法向量計(jì)算

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

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

2 點(diǎn)云分割

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

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

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

3 基于隨機(jī)森林方法的深入分割

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

3.1 隨機(jī)森林算法

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

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

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

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

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

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

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

3.2 針對(duì)變電站點(diǎn)云分割的算法設(shè)計(jì)

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

圖6 變電站點(diǎn)云分割

5 結(jié)論

將三維可視化技術(shù)應(yīng)用于變電站管理系統(tǒng)有助于實(shí)現(xiàn)其在計(jì)算機(jī)上的仿真展示、導(dǎo)航定位、遠(yuǎn)程監(jiān)測(cè)和作業(yè)推演等。而這些功能開發(fā)的前提是變電站三維模型的重構(gòu)。點(diǎn)云分割是三維重構(gòu)的關(guān)鍵基礎(chǔ)。本文提出的點(diǎn)云分割方法借助隨機(jī)森林算法為變電站三維掃描圖中的點(diǎn)云數(shù)據(jù)實(shí)現(xiàn)了精準(zhǔn)的聚類分割，而且對(duì)于變電站大規(guī)模點(diǎn)云數(shù)據(jù)的計(jì)算，該方法保持了很好的魯棒性和穩(wěn)定性，克服了其它算法在分割效果上對(duì)初始種子點(diǎ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] 王小超,劉秀平,李寶軍,張紹光.基于局部重建的點(diǎn)云特征點(diǎn)提取[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).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] 傅歡,梁力,王飛,趙季中.采用局部凸性和八叉樹的點(diǎn)云分割算法[J].西安交通大學(xué)學(xué)報(bào).2012,46(10):60-64.

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

[13] 孫永偉,孫殿柱,朱昌志,朱宗偉.散亂點(diǎn)云切片數(shù)據(jù)快速獲取與優(yōu)化[J].哈爾濱工程大學(xué)學(xué)報(bào).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].計(jì)算機(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.