雙層優(yōu)化的激光雷達點云場景分割方法

李明磊，劉少創(chuàng)，楊 歡，亓 晨

1. 南京航空航天大學電子信息工程學院，江蘇 南京 211106； 2. 中國科學院遙感與數(shù)字地球研究所，北京 100101； 3. 武漢大學測繪學院，湖北 武漢 430079

三維點云分割的目標是依據(jù)點的屬性獲得空間同質(zhì)區(qū)域的聚類，分割處理是移動設備導航定位、目標提取識別和場景幾何建模等應用的重要底層技術[1-2]。然而，由于數(shù)據(jù)的采樣密度非均勻、點云非結構化分布、噪聲和外點等影響，完全地自動化分割在計算機視覺、計算機圖形學、攝影測量與遙感等研究領域仍然是一項艱巨的任務[3-5]。本文根據(jù)原理不同將點云分割算法歸為以下4類：

(1) 基于區(qū)域增長法(region growing)的分割技術。該方法從種子點出發(fā)根據(jù)相似性度量和距離度量對鄰域點判斷是否擴展合并為同一區(qū)域[6-7]。區(qū)域增長算法相對易于實現(xiàn)，但它對噪聲敏感，算法中的增長準則對不同局部區(qū)域的細節(jié)差異的自適應能力弱，而且種子點選取的不確定性將會影響到分割結果的可靠性。

(2) 基于圖(graph-based)的分割算法。這類算法通過將點云模式化為由節(jié)點和反映節(jié)點關系的邊組成的圖模型。假設存在一種條件隨機場模型，依據(jù)極大后驗估計準則使用圖割算法將圖模型的部分連接斷開形成獨立的區(qū)域[8-10]。該方法對前景和背景進行分割，適用于指定的目標提取，或以監(jiān)督分類方式實現(xiàn)多目標提取。

(3) 基于模型擬合(model-fitting)的分割算法。例如以隨機抽樣一致性檢驗(random sample consensus，RANSAC)為依據(jù)的參數(shù)化幾何元素(平面、橢球和圓柱等)擬合算法[11-12]，被廣泛應用于建筑物立面提取[13-14]。與此類似還有基于霍夫變換(Hough transform)的元素提取技術[15]，該類算法提取的幾何結構精簡緊湊，可視化效果好。但在參數(shù)求解時通常使用統(tǒng)一的閾值從而缺乏尺度適應能力，此外一次分割只能提取出一類基本元素，當場景具有復雜多樣的結構形態(tài)時并不適用。

(4) 以機器學習(machine learning)為基礎的分割算法。文獻[16]使用支持向量機將幾何特征歸類，文獻[17—18]提出一種以神經(jīng)網(wǎng)絡學習的方法將分割與分類同步結合進行目標識別，文獻[19]將點云轉(zhuǎn)化為體素(volume)數(shù)據(jù)來提取特征再使用AdaBoost進行訓練和目標提取。這類算法在訓練過程中需要大量的已有標記數(shù)據(jù)做訓練樣本，而且分割對象限定為已經(jīng)訓練過的目標物，因此使該算法難以靈活地推廣。

前兩類算法可以歸為自下而上的分割方法，而后兩類則是基于模式引導的自上而下的方法，它們的適用性都存在一定的局限。為了提高點云分割算法的抗噪性和對多種類型場景的適用性，解決三維點云特征描述困難的問題，本文針對激光雷達(light detection and ranging,LiDAR)數(shù)據(jù)的特性，在黎曼幾何框架下考慮將體素過分割方法和基于圖的方法相結合，設計分層優(yōu)化的自動分割算法，該算法邏輯清晰易于實現(xiàn)，而且運算速度快，對點云的局部細節(jié)具有良好的自適應性。

1 算法設計

本文雙層優(yōu)化策略的點云分割算法包括以下3個基本步驟：①通過定義局部坐標系來建立特征提取的參考基準；②以八叉樹節(jié)點為種子點，結合離散點的特征信息，通過迭代優(yōu)化聚類實現(xiàn)以超體素為輸出的底層分割；③以超體素為節(jié)點建立最小生成樹圖(minimal spanning tree，MST)，以MST為對象進行頂層優(yōu)化聚類實現(xiàn)場景目標分割。

1.1 局部坐標系建立

LiDAR點云能反映被觀測目標的表面形態(tài)特性，與影像重建的點云，如多視立體重建(multi view stereo)相比，LiDAR點云采樣均勻且密度高。盡管屬于非連續(xù)空間采樣，但致密的表面點滿足建立局部歐氏坐標系的條件，可以用黎曼度量來研究局部可微性質(zhì)，此時點的鄰域關系不再局限于全局坐標系的組織。對點云中的任意一點，以其切平面為基礎構建局部歐氏坐標框架，統(tǒng)計鄰域內(nèi)的點集的協(xié)方差，由此自適應調(diào)整距離度量并提取點特征向量，使特征參數(shù)可以考慮到數(shù)據(jù)局部結構的細節(jié)差異，避免了全局統(tǒng)一參數(shù)約束，有利于提高算法適用性。

在處理非結構化的LiDAR點云數(shù)據(jù)時，描述離散點的特征的方式具有多種多樣[20-22]，各種方法首先都需要建立起空間索引和鄰域搜索機制。本文中設p是一個查詢點，以Np：{qi|i=1,2,…,k}表示查詢輸出的一組鄰域點集，其中每個點qi與搜索點p的距離度量滿足‖qi,p‖n≤dmax，為此采用近似最鄰近查詢方法(approximate nearest neighbor，ANN)[23]作為檢索結構實現(xiàn)快速的鄰域搜索。

(1)

Xp=(-sinφ,cosφ,0)
Yp=(cosψcosφ,cosψsinφ,-sinψ)

(2)

圖1 局部歐氏坐標系定義示意圖Fig.1 A diagram of local Euclidean coordinate system

1.2 底層優(yōu)化超體素(super voxel)分割

本文將點云分割過程設計分為上下兩層遞進的組織形式，本節(jié)介紹底層優(yōu)化方法，1.3節(jié)內(nèi)容將介紹頂層優(yōu)化過程。底層結構的分割效果是利用改化的k均值聚類算法獲得過分割的(over-segmented)點云聚類，可以表示為點云體素(voxel)的形式，具體包含以下3步。

(1) 定義相似性度量參數(shù)。點云聚類算法通常以法向量、曲率和離散度等屬性信息構建特征向量來進行相似性度量，當具有影像數(shù)據(jù)時，顏色和紋理信息也被包含其中。本文中僅考慮原始LiDAR點云形式的數(shù)據(jù)，此時底層特征采用法向量和曲率組成的特征向量表示，具體的一點p的特征向量表示形式為fp∈R5:[nx,ny,nz,k1,k2]T，其中k1,k2表示表面位置的兩個主曲率值。

圖2 局部歐氏坐標系下的距離度量 Fig.2 Distance metric in local Euclidean coordinate system

(2) 聚類中心初始化。對于底層體素分割的另一個關鍵問題就是分割數(shù)目的選取和聚類中心的初始化。本文采用自適應八叉樹索引結構來創(chuàng)立聚類中心點集合S：{si|i=1,2,…,m}，與點p類似每一個種子點si也有一組特征fsi∈R5。對于三維數(shù)據(jù)而言，八叉樹可以快速實現(xiàn)鄰域點查詢，而葉子節(jié)點本身即是一類以空間距離做度量的廣義上的聚類。算法集成過程中利用了泊松表面重建算法[24]中的自適應八叉樹結構做引導，根據(jù)經(jīng)驗值以第6、7級節(jié)點(與點密度和場景范圍相關)作為局部聚類中心效果理想，而節(jié)點的寬度dr即作為下一步搜索半徑參數(shù)。

(3) 聚類搜索閾設計。不同于傳統(tǒng)的k均值聚類算法將每個點與所有聚類中心做判斷，本算法中原始點只與到自身距離在3倍搜索半徑(3×dr)內(nèi)的聚類中心點做相似性判斷。之后運算與k均值聚類相似，利用相似性度量和距離度量的加權距離判別查詢點p所屬的聚類中心sp。所有點判別結束后，根據(jù)聚類結果更新聚類中心sp的位置并進行下一輪迭代聚類，直到聚類中心位置收斂。聚類判別公式為

(3)

1.3 頂層優(yōu)化圖聚類

底層優(yōu)化得到的是過分割的點云體素集合，這類集合表達了點云小尺度的相似性關系，為目標級別的分割提供支撐。頂層優(yōu)化的數(shù)據(jù)操作對象不再是獨立的點而是體素，具體過程分為以下3步。

(2) 當鄰域關系確立后，進行拓撲圖構建。本文利用Kruskal坐標系[25]建立以體素為節(jié)點的MST，實現(xiàn)對體素結構的拓撲關系索引。MST的建立步驟是首先設每一個體素為一個節(jié)點e，將其所有鄰域節(jié)點{Vneighbor}按邊的距離權值從小到大排序，循環(huán)從權值最小的邊開始遍歷每條邊直至圖中所有的節(jié)點都在同一個連通分量中，該連通分量所經(jīng)過的所有路徑和節(jié)點即構成了一個MST。

(3) 最后從MST中的起點出發(fā)，根據(jù)邊的權值按區(qū)域增長法進行聚類判別，當遇到增長終止條件時，自動開始新的區(qū)域聚類，從而實現(xiàn)頂層非監(jiān)督分割聚類。

2 試驗與分析

2.1 數(shù)據(jù)處理與算法實現(xiàn)

試驗環(huán)節(jié)采用了室內(nèi)和室外兩組點云數(shù)據(jù)分別進行處理分析，運算平臺為win10 64位系統(tǒng)，處理器為i7-6500U搭配8 GB內(nèi)存。算法功能采用C++編程實現(xiàn)，利用QT搭建軟件界面，OpenGL作為三維繪圖引擎，并開發(fā)實現(xiàn)八叉樹索引和RANSAC幾何元素檢測等相關功能。

圖3通過室內(nèi)數(shù)據(jù)試驗展示了處理過程的中間結果。該數(shù)據(jù)是一組利用Leica ScanStation C10掃描儀獲取的臥室點云，共包含45.1萬個空間點，掃描距離在1.5 m到3.5 m，采樣密度約為9000點/m2。圖3(a)給出原始點云的一個快照；圖3(b)是初始化的過分割聚類中心點，可以發(fā)現(xiàn)聚類中心點概括了原始點云的布局；圖3(c)是經(jīng)過迭代優(yōu)化后的底層過分割聚類結果，其中不同的體素以隨機生成的顏色進行區(qū)分標識；圖3(d)展示了以體素為基本節(jié)點的MST圖構建情況，該圖是區(qū)域增長法的路徑尋優(yōu)基礎。通過建立以超分割體素為節(jié)點的MST圖，一方面保持了原有數(shù)據(jù)的幾何信息和拓撲信息，另一方面從點云到體素節(jié)點極大地減少了數(shù)據(jù)量，為提高數(shù)據(jù)處理效率提供了重要的支撐。

2.2 試驗比較分析

為驗證本文算法的先進性，試驗中將基于RANSAC的參數(shù)化幾何元素擬合分割算法[11]與本文雙層優(yōu)化算法進行了比較，其中RANSAC點擬合距離閾值設為0.1 m。兩種算法的分割結果如圖4所示，其中圖4(a)、(b)分別表示RANSAC分割結果和本文算法的結果，圖4(c)、(e)是一個沙發(fā)的局部放大效果，圖4(d)展示了本文算法的超體素分割的局部效果。由于沙發(fā)表面并非規(guī)則的幾何形狀，從圖4(c)、(e)中可以比較發(fā)現(xiàn)，RANSAC擬合參數(shù)化表面的分割結果不理想，盡管通過設置距離和法向量的擬合殘差閾值，可以實現(xiàn)對場景的局部分段分割，但單一模式的平面表達會使分割得到的對象失去原有的細節(jié)特性。相反，本文算法利用點云過分割和體素聚類分割兩層優(yōu)化步驟，將掃描點云的局部可微性質(zhì)保留在體素內(nèi)部，并在適當?shù)倪^渡區(qū)域斷開MST圖，實現(xiàn)點云的非監(jiān)督分類，具有較好的細節(jié)保真度。

圖3 算法處理流程Fig.3 A pipeline of the algorithm

圖4 基于RANSAC分割與本文方法結果的比較Fig.4 A comparison between the results of RANSAC based method and our results

兩種算法的定量比較統(tǒng)計結果見表1，包含算法分割耗時、分割數(shù)目和擬合殘差指標。從表1中可以得出本文算法比較RANSAC擬合分割算法有優(yōu)異表現(xiàn)。在效率方面，RANSAC算法需要多次隨機采樣確定擬合參數(shù)，而且每提取一個分割面都需要單獨全局擬合計算，計算耗時相對較多；而本文利用超體素作為圖節(jié)點減少數(shù)據(jù)量，極大地降低了運算量。另外，RANSAC算法分割的目標局限為參數(shù)化的基本幾何形狀，因此分割數(shù)目有限，無法對復雜的場景形狀進行有效表達。兩種方法的擬合殘差接近，這是由于算法本身進行了擬合距離閾值設置，限定了最大的擬合殘差，因此具有統(tǒng)一的擬合殘差量級。

表1 兩種分割算法比較數(shù)據(jù)統(tǒng)計

此外，為驗證本文算法的廣泛適用性，利用車載LiDAR點云數(shù)據(jù)進行了室外場景分割測試，原始點云和分割結果如圖5所示。算法通過自適應八叉樹可以在突變區(qū)域提取可靠種子點，根據(jù)種子點的鄰域點集的局部可微性進行聚類，從而生成有效的超體素，避免丟失場景中的突變地形和地物信息。如圖5(b)所示，路燈和電線桿被正確地分割提取，充分證明了本文算法對多種場景的適用性。本文算法的局限性在于缺乏語義層次的判別，僅從幾何層面分析可能將一類目標物分割為幾個局部連貫的片段，如圖5(b)圖框選區(qū)域中將一輛卡車的車頭和車身分割成兩個區(qū)域。

圖5 車載LiDAR點云分割試驗Fig.5 An experiment on vehicle borne LiDAR data

3 結 論

本文設計了一種面向LiDAR點云的自動分割算法，首先對底層點云進行迭代均值聚類獲得過分割，形成超體素集合。然后，在頂層以體素為節(jié)點建立拓撲圖模型，利用MST結構極大地簡化了圖的結構，提高區(qū)域增長算法的效率。本文算法不需要限定分割結構是平面或柱面等幾何類型，因此適用于多類型目標分割，能夠同時兼顧點云的局部細節(jié)和全局整體分布情況，適合多類應用場景的推廣。下一步的研究工作將提取分割結果的高級特征進行語義層次的判別，實現(xiàn)點云目標識別。

[1] RUSU R B, COUSINS S. 3D is Here: Point Cloud Library (PCL)[C]∥Proceedings of 2011 IEEE International Conference on Robotics and Automation. Shanghai, IEEE, 2011: 1-4.

[2] LI Minglei, NAN Liangliang, SMITH N, et al. Reconstructing Building Mass Models from UAV Images[J]. Computers & Graphics, 2016, 54: 84-93.

[3] ROTTENSTEINER F, SOHN G, GERKE M, et al. Results of the ISPRS Benchmark on Urban Object Detection and 3D Building Reconstruction[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 93: 256-271.

[4] BERGER M, TAGLIASACCHI A, SEVERSKY L, et al. State of the Art in Surface Reconstruction from Point Clouds[R]. Proceedings of Eurographics 2014: State of the Art Reports. Strasbourg, France: The Eurographics Association, 2014.

[5] VOSSELMAN G, COENEN M, ROTTENSTEINER F. Contextual Segment-based Classification of Airborne Laser Scanner Data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 128: 354-371.

[6] VO A V, TRUONG-HONG L, LAEFER D F, et al. Octree-based Region Growing for Point Cloud Segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 104: 88-100.

[7] VIEIRA M, SHIMADA K. Surface Mesh Segmentation and Smooth Surface Extraction through Region Growing[J]. Computer Aided Geometric Design, 2005, 22(8): 771-792.

[8] GOLOVINSKIY A, FUNKHOUSER T. Min-cut Based Segmentation of Point Clouds[C]∥Proceedings of the IEEE 12th International Conference on Computer Vision Workshops. Kyoto, Japan: IEEE, 2009: 39-46. DOI: 10.1109/ICCVW.2009.5457721

[9] URAL S, SHAN J. Min-cut Based Segmentation of Airborne LiDAR Point Clouds[C]∥International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXIX-B3. Melbourne, Australia: ISPRS, 2012: 167-172.

[10] RUSU R B, HOLZBACH A, BLODOW N, et al. Fast Geometric Point Labeling Using Conditional Random Fields[C]∥Proceedings of 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. St. Louis, MO, USA: IEEE, 2009.

[11] SCHNABEL R, WAHL R, KLEIN R. Efficient RANSAC for Point-cloud Shape Detection[J]. Computer Graphics Forum, 2007, 26(2): 214-226.

[12] 李卉, 鐘成, 黃先鋒, 等. 集成激光雷達數(shù)據(jù)和遙感影像的立交橋自動檢測方法[J]. 測繪學報, 2012, 41(3): 428-433.

LI Hui, ZHONG Cheng, HUANG Xianfeng, et al. Automatic Overpass Detection with LiDAR and Remote Sensing Image[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(3): 428-433.

[13] 魏征, 董震, 李清泉, 等. 車載LiDAR點云中建筑物立面位置邊界的自動提取[J]. 武漢大學學報(信息科學版), 2012, 37(11): 1311-1315.

WEI Zheng, DONG Zhen, LI Qingquan, et al. Automated Extraction of Building Facade Footprints from Mobile LiDAR Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2012, 37(11): 1311-1315.

[14] 閆利, 謝洪, 胡曉斌, 等. 一種新的點云平面混合分割方法[J]. 武漢大學學報(信息科學版), 2013, 38(5): 517-521.

YAN Li, XIE Hong, HU Xiaobin, et al. A New Hybrid Plane Segmentation Approach of Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5): 517-521.

[15] VOSSELMAN G, GORTE B G H, SITHOLE G, et al. Recognizing Structure in Laser Scanner Point Clouds[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2004, 46(8): 33-38.

[16] YANG Bisheng, DONG Zhen. A Shape-based Segmentation Method for Mobile Laser Scanning Point Clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 81: 19-30.

[17] YU Yongtao, LI J, GUAN Haiyan, et al. Learning Hierarchical Features for Automated Extraction of Road Markings from 3-D Mobile LiDAR Point Clouds[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2015, 8(2): 709-726.

[18] 張蕊, 李廣云, 李明磊, 等. 利用PCA-BP算法進行激光點云分類方法研究[J]. 測繪通報, 2014(7): 23-26. DOI: 10.13474/j.cnki.11-2246.2014.0217.

ZHANG Rui, LI Guangyun, LI Minglei, et al. Classification of LiDAR Point Clouds Based on PCA-BP Algorithm[J]. Bulletin of Surveying and Mapping, 2014(7): 23-26. DOI: 10.13474/j.cnki.11-2246.2014.0217.

[19] PANG Guan, NEUMANN U. Training-based Object Recognition in Cluttered 3D Point Clouds[C]∥Proceedings of 2013 International Conference on 3D Vision-3DV 2013. Seattle, WA, USA: IEEE, 2013: 87-94.

[20] DONG Zhen, YANG Bisheng, LIU Yuan, et al. A Novel Binary Shape Context for 3D Local Surface Description[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 130: 431-452.

[21] HACKEL T, WEGNER J D, SCHINDLER K. Fast Semantic Segmentation of 3D Point Clouds with Strongly Varying Density[J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016, III-3: 177-184.

[22] GUO Yulan, BENNAMOUN M, SOHEL F, et al. A Comprehensive Performance Evaluation of 3D Local Feature Descriptors[J]. International Journal of Computer Vision, 2016, 116(1): 66-89.

[23] ANDONI A, INDYK P. Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[C]∥Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. Berkeley, CA, USA: IEEE, 2006: 459-468.

[24] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3): 29.

[25] ROBLES-KELLY A, HANCOCK E R. A Riemannian Approach to Graph Embedding[J]. Pattern Recognition, 2007, 40(3): 1042-1056.