地下管廊特征保持的三維點云數據精簡研究

劉致遠 侯至群 朱大明

摘 ?要： 本文提出了一種基于RANSAC平面分割和PCA特征提取的移動背包Lidar點云地下管廊特征保持的數據精簡方法。首先基于移動背包獲得地下管廊原始點云數據;然后利用RANSAC算法對目標點云分割并識別出含有管廊整體輪廓信息的面狀點云;最后對所識別出的面狀點云基于PCA算法和通過設定投影向量角度閾值提取出管廊特征輪廓數據。試驗結果表明，該方法能夠有效快速地提取出地下管廊點云數據中的特征輪廓目標，提取的特征輪廓與原始點云能準確符合。在保留輪廓特征的同時精簡了數據，為三維點云數據的高效利用奠定了基礎。

關鍵詞： 移動背包;點云;RANSAC;輪廓特征提取;PCA;數據精簡

中圖分類號： P237; TP391; TN249 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.08.031

本文著錄格式：劉致遠，侯至群，朱大明，等. 地下管廊特征保持的三維點云數據精簡研究[J]. 軟件，2020，41（08）：110-115

【Abstract】： This paper presents a data reduction method based on RANSAC plane segmentation and PCA feature extraction for moving backpack Lidar point cloud in underground pipe gallery feature reserving. First， the original point cloud data of underground pipe gallery is obtained by mobile backpack; then the RANSAC algorithm is used to segment the target point cloud and identify the surface point cloud with the whole outline information of the pipe gallery; finally， based on the PCA algorithm and by setting the projection vector angle threshold， the pipe gallery feature contour data are extracted.The experimental results show that this method can effectively and quickly extract the feature contour targets in the point cloud data of underground pipe gallery， and the extracted feature contour can accurately match with the original point cloud. Reducing data while preserving contour features， laid the foundation for efficient utilization of 3d point cloud data.

【Key words】： Mobile backpack; Point cloud; RANSAC; Contour feature extraction; PCA; Data reduction

0 ?引言

大規模精細三維模型獲取技術的不斷發展，三維激光掃描技術憑借其數據獲取速度快、精度高、覆蓋廣的特點，成為高精度三維模型數據獲取的主流方式之一。但獲取的點云數據量呈幾何級數增長，可以輕易從模型表面獲取數百萬甚至更多的測量數據，使得人工處理數據效率低。由于海量三維點云數據在應用過程中并不都能產生作用，特別是對于地下建構筑物點云而言，其大體模型的建立只需要確定邊界區域上的點云即可。因此，面對如此龐大的數據量，如何對海量散亂點云數據精簡，從而加快處理速度，達到能提取出輪廓特征等有應用價值數據的目的，成為目前亟待解決的問題。

國內外眾多學者對點云數據基于曲率或法矢向量的特征提取進行了深入研究。M J Milroy[1]提出依據近鄰點求出該點曲率，剔除明顯大于和小于點以達到提取邊界特征點目的。當邊界點屬于較光滑、平坦區域時該方法能有效識別，但對曲率變化較大區域的特征提取效果不佳。王永波[2]等提出利用平均曲率和曲率極值法來實現對特征點的初始提取和精提取，該算法的缺點是受點云采樣密度及領域大小的影響，無法應用大范圍點云特征提取中。

Pauly[3]基于移動最小二乘（Moving Least Squares）提出了一個完整的采樣點幾何自由曲面造型框架，并且可以在采樣點對象上生成和保留尖銳的特征。Abdalla Alrashdan[4]提出計算每個點的法矢方向，依據相鄰法矢方向的突變情況，判斷提取邊界點。當邊界點處法矢方向變化較小時會出現漏提現象。T. Rabbani[5]等依據掃描點法向量的聚類分析和區域增長點云分割算法，對固定激光掃描儀獲取的工業設備點云進行表面分割和提取。Tarsha[6]針對相同的LiDAR數據源，分別采用3D Hough和RANSAC算法進行平面提取試驗，試驗結果表明RANSAC算法具有較高的計算效率和精度。鄧博文[7]等提出利用隨機抽樣一致算法的形態學梯度來實現對目標物邊界的提取，然而該算法受法向量計算準確性的影響，同時也受構造面判斷準確性的影響。孫殿柱[8]提出一種新的提取算法，以R*-tree作為散亂點云的空間存取模型來組織數據點之間的拓撲關系，根據k近鄰搜索算法與最小二乘法將待判斷點與其k個點集擬合切平面。再通過點集在為切面上的投影計算出相鄰向量夾角，根據設定閾值夾角判斷條件進行取舍，最終達到提取邊界點目的。裴書玉[9]首先采用移動最小二乘法進行法矢估計，然后將k鄰域法矢夾角的均值作為點的顯著性指標進行特征點判別，最后對特征點進行下采樣得到清晰完整的特征線。石波和盧秀山[10]提出基于kd-tree在不知道點云之間的拓撲關系時快速確定某一點及其周圍鄰域，并計算該點法向量，利用建筑物的平面特征對先驗知識即共向性條件和共面性條件改進，根據法向量相似性實現了散亂點云的平面分割。楊必勝等人[11-13]引入自適應鄰域法避免了點云密度變化帶來的影響，提出除了法向量和主方向的幾何特征外增加了維數特征以精確計算每個掃描點的幾何特征，兼顧了幾何特征和強度信息的最優，綜合建筑物立面語義知識，提高了對復雜區域內不同地物提取的完整性和精確度。

眾多研究表明，基于點云的邊界提取成為人們研究的重點，因其不需提前構建三角格網步驟，只需直接針對點云進行邊界點提取。基于對海量點云的特征輪廓提取，考慮到研究區掃描對象種類豐富且形狀不一以及算法的時間效率。因此，在分析上述算法的基礎上，本論文的總體研究目標是：以移動背包三維激光掃描系統一個行走軌跡的原始點云為單位，從采用隨機抽樣一致性算法（RANSAC）的整體分割到基于主成分分析法（PCA）的局部提取的思想，探討一套適合城市常見地下建、構筑物特征保持的海量三維點云數據精簡方法。

1 ?算法概述

本文基于海量三維點云數據，并考慮到后期應用于三維建模的點云數據需具有針對性和高效性，提出基于地下管廊特征保持的三維點云數據精簡方法，該方法在剔除大量數據的前提下保持了原有特征輪廓。流程圖如圖1所示，主要步驟如下：

（1）原始點云數據的生成，明顯噪聲的剔除;

（2）基于RANSAC算法，通過閾值t和最小N的確定對原始點云分割，得到如頂、墻、地面等包含了特征輪廓的整個面狀點云數據;

（3）對分割后的面狀點云數據構建kd-tree空間索引，利用最鄰近點搜索算法，對k個鄰近點進行搜索，利用主成分分析法（PCA）實現數據的降維，將鄰近點投影到投影面上，通過判斷相鄰向量夾角最大角度差與設定角度閾值的大小關系從而確定數據的特征輪廓。

1.1 ?基于RANSAC的點云分割

1.1.1 ?RANSAC算法基本思想

隨機抽樣一致算法（RANdom SAmple Consensus，RANSAC），它可以通過迭代方式從一組包含正確數據和離群數據（噪聲）的觀測數據集中魯棒的估計數學模型參數，從而區分出“inliers”（局內點）和“outliers”（局外點）。該算法最早由Fischler和Bolles于1981年提出。是數據處理的一種經典算法，其作用是在大量噪聲情況下，提取物體中特定的成分。RANSAC算法的核心思想是其非確定性，在某種意義上說，它會產生一個在一定概率下合理的結果，其允許通過提高迭代次數來提高概率從而得出一個合理的結果。RANSAC算法也有不足之處，其迭代次數沒有上限，因此參數計算結果的好壞會受到迭代次數設置的影響，并且它要求設置跟問題相關的閾值。

1.1.2 ?平面擬合步驟及參數確定

利用RANSAC算法對點云進行平面擬合，其詳細步驟為：

（1）在原始點云數據中隨機選取3個不共線的點（兩兩斜率相同即共線）;

1.2 ?基于PCA的特征提取

主成分分析方法（Principal Component Analysis，PCA），是一種數據降維算法，其目的是對冗余的數據特征進行降維處理的同時保留數據最重要的一部分特征，使其主要的特征成分最大的保持整個數據信息完整性。PCA的主要思想是在原有的n維特征基礎上將k維正交特征即主成分映射出來，通過計算數據集的協方差矩陣得到相應的特征值和特征向量，按特征值最大將k個維度的特征值對應的特征向量排序（最大特征值即最大方差，其反映了數據的最重要的信息），因此就將n維數據矩陣轉換到了k維數據矩陣中，實現了數據特征的降維。算法步驟如下：

（5）如圖所示，根據k個投影點所構成的相鄰向量夾角 排序，將鄰近向量夾角差值的最大值和角度閾值AngleThreshold對比，根據經驗閾值，鄰近向量夾角差值的閾值近似于90°，最終將閾值確定為90°。若最大值大于等于閾值，該點為邊界點;若最大值小于閾值，該點為非邊界點。投影面上的邊界點判斷如圖2所示。

2 ?實驗與分析

2.1 ?背包數據

本次試驗采集數據設備為Leica Pega-sus：Backpack移動背包三維激光掃描系統，集成了GNSS技術、慣性導航技術和SLAM技術于一體，其中GNSS可接收GPS、GLONASS、Galileo及北斗衛星信號，能夠實時確定室內室外場景的儀器所處位置及姿態，2個激光掃描儀和5個相機能夠快速準確的獲取室內外的三維點云數據以及全景照片的采集，并結合軌跡數據解算，實現三維點云數據的高精度自動拼接。該設備可由人員背負或者在車上搭載，在采集數據過程中可以根據環境條件和采集需要隨時上下移動，對于人員能經過的地方都能進行數據采集，對工作環境要求低，適應性強，真正實現“走哪測哪、實景再現”。

研究區為某地下管廊，為了能獲得更精確的數據，背包采用Fused SLAM模式，該模式通過1個或多個GNSS基準站的架設來進行數據后處理差分解算，以實現室外及室內外一體化的數據采集。室外環境下主要使用GNSS/INS組合的軌跡定位模式，從室外進入室內的過程中，系統將室外的時空基準傳導到室內。在此基礎上，室內環境下的數據采集主要使用Lidar/INS組合的軌跡定位模式。固背包獲取POS數據后要進行軌跡以及SLAM的解算以得到原始點云數據，之后在ReCap里刪除明顯離群噪聲點，最后共保留1526615個數據點。如圖3所示。

2.2 ?基于RANSAC分割

本次試驗平臺為Win7 64位操作系統，主要硬件配置為Inter core i5 2.8GHz，12 GB內存。算法基于點云庫PCL 1.8.0（Point Cloud Library）在Visual Studio2013中實現。根據需要設置分割閾值，如圖4閾值設置不合理造成過分割現象。本試驗采用閾值t=0.034，采樣分辨率為0.068，至少有一個數據基本子集包含的數據全部是局內點數據的概率大于99%時，迭代次數M應為1000次[15]。地下管廊內部環境特征豐富，包括支撐架、通風口、投料口、防火門等，固設置保留最小面狀點云數據個數為2000，判斷參與擬合模型的點數是否大于2000，若大于，則認為得到正確的數學模型參數，停止迭代。經RANSAC分割后僅保留能反應管廊特征輪廓面上的點云數據，共保留9個面388363個數據點，如圖5所示。

2.3 ?基于PCA的特征提取

（1）建立空間索引

三維激光掃描點云數據是一種散亂、無序的表面的海量點集合，并不具備傳統實體網絡數據的幾何拓撲信息，這種大數據量且分布不均勻點云數據點云數據給后續處理帶來一定難度。尤其是在對點云數據進行處理時往往需結合其近鄰點而無法根據單個點坐標進行處理判斷，這一過程涉及到點云近鄰點查詢。所以點云數據處理最核心的問題，就是建立離散點間的拓撲關系，以便將點云數據進行合理組織，從而實現基于鄰域關系的快速查找。構建點云數據空間索引在點云數據處理中已有廣泛應用，比較有代表性的包kd-tree和oc-tree。kd-tree在不知道點云數據之間的拓撲關系時能快速確定散亂點云中判斷點的某一鄰域，特別在點云數量増加到百萬級別以上，快速獲取近鄰點時對算法的耗時要求就高，此時優先選擇kd-tree效率更高[16]。故本文采用 kd-tree建立三維數據點之間的拓撲關系，進而找出各數據點的k近鄰。

kd-tree（k-demension tree）是從BST（Binary Search Tree）發展而來，也是二叉樹的一種分割k維數據空間的高維索引樹形數據結構，對一個三維空間，kd-tree按照一定的劃分規則將多個點劃分為節點空間，劃分規則通常是根據距離的平方作為劃分權重，即根據距離權重的二分法形成的樹結構，目的用于快速查找一個指定點的鄰域的其他點的信息。如圖6所示。

基于點云構造kd-tree的方法如下：在樹的根部，所有子節點在第一個指定的維度上被分開，也就是說把制定維度的點放在根上，在指定的第一個維度中坐標小于根節點的點將被分在左邊的子樹中，大于根節點的點將分在右邊的子樹中。樹的每一級都在下一個維度上分開，所有其它的維度用完之后就回到第一個維度。然后重復這個過程，直到準備分類的最后一個分類僅僅由一個點組成。隨著樹的深度增加，循環的選取坐標軸，如根節點選取x軸，根節點的子節點選取y軸，再下一個節點選取z軸劃分，三個維度劃分完繼續循環下去，直到葉子節點出現，即kd-tree構建結束。如圖7所示。

（3）基于點云庫PCL采用PCA算法實現對分割后面片上的388363個點云（如圖9所示）的特征輪廓提取。根據先驗知識k值的選取在10-30之間為最佳[17]，取決于點云的密度，當數據密度大時可以取小些，數據比較稀疏時該值可以取大些。設定最優的k值是接下來特征輪廓提取的第一也是關鍵一步。k值的大小與鄰近點的數量成正比，設置的越小，鄰近點包含的信息就越少，達不到特征輪廓判斷的要求，如圖10所示，提取輪廓特征點數為25148個，程序運行時間為189.38秒;反之設置的越大，鄰近點包含的信息越多，對特征輪廓造成錯判斷，并且對算法效率大大降低，如圖11所示，提取輪廓特征點數為7490個，程序運行時間為653.42秒。

最佳提取結果如圖12所示，當k為15時，提取輪廓特征點共12414個，程序運行時間為278.20秒。所提取點云數據在剔除了大量數據的前提下很好的保留了管廊的特征輪廓。把所提取的特征輪廓與原始點云套合比對如圖13所示，發現所提取數據能很好地反應原始點云的特征輪廓。

3 ?結束語

移動背包三維激光掃描系統其采集對象距離更近，數據精度、數據量總量、數據密度等也都相應比較高，能彌補傳統測量方式在作業時因室內環境的復雜度與空間局限性受到諸多限制，做到無死角測量，已成為一種快速的空間數據獲取手段。本文基于城市地下管廊提出了一套特征輪廓提取的方法，其中RANSAC算法的優點在于它的抗噪性，能從包含大量噪聲的點云中估計出高精度的數據。而利用PCA算法在進行局部提取并計算特征值的過程中能很好的降低算法的計算開銷，為后期的三維模型建立提供了很好的數據基礎。一方面對點云數據進行了精簡，去除點云數據中大量冗余數據，使數據占用更少的存儲空間，提高了利用率。另一方面提取的特征輪廓與原始點云能準確符合，在數據應用于三維重建時，可以快速準確重建掃描對象，提高整個重建過程的效率。

本文提出的特征輪廓提取方法適用于地下管廊及其相似的地下建構筑物等某一特定區域內的研究對象特征輪廓的提取，對于提取對象種類豐富，特別是一些精細對象的特征輪廓提取還需要人工的大量干預，因此在之后研究工作中，充分合理利用點云的幾何特征、顏色信息、照片信息、強度信息、密度信息等，建立多源數據下的自動化特征輪廓提取算法，實現在地理場景采集的點云數據最終用少而有效的點描述掃描對象。

參考文獻

[1] M J Milroy， C Bradley， GW Vickers. Segmentation of a wrap- around model using an active contour[J] . Computer-Aided Design， 1997， 29（4）： 299-320.

[2] 王永波， 盛業華. 一種基于曲率極值法的LiDAR點云特征提取算法[J]. 中國礦業大學學報， 2011， 40（04）： 640-646.

[3] Pauly M， Keiser R， Kobbelt L P， et al. Shape modeling with point-sampled geometry[J]. ACM Trans Graph， 2003， 22（3）： 641-650.

[4] Abdalla Alrashdan， Saeid Motavalli， Behrooz Fallahi. Automatic segmentation of digitized data for reverse engineering applications[J]. IIE Transactions（2000）32： 59-69.

[5] Rabbani T， Van Den Heuvel F， Vosselmann G. Segmentation of point clouds using smoothness constraint[J]. International Archives of Photogrammetry， Remote Sensing and Spatial Information Sciences， 2006， 36（5）： 248-253.

[6] Tarsha Kurdi F， Landes T， Grussenmeyer P. Hough-Transform and extended ransac algorithms for automatic detection of 3D building roof planes from LiDAR data [J]. International Archives of Photogrammetry， Remote Sensing and Spatial Information Systems， 2007， 36： 407-412.

[7] 鄧博文， 王召巴， 金永， 等. 基于形態學梯度的激光掃描點云特征提取方法[J]. 激光與光電子學進展， 2018， 55（05）： 239-245.

[8] 孫殿柱， 范志先， 李延瑞. 散亂數據點云邊界特征自動提取算法[J]. 華中科技大學學報（自然科學版）， 2008（08）： 82-84.

[9] 裴書玉， 杜寧， 王莉， 等. 基于移動最小二乘法法矢估計的建筑物點云特征提取[J]. 測繪通報， 2018（04）： 73-77.

[10] 石波， 盧秀山， 陳允芳. 基于kd-tree的建筑物散亂點云平面分割[J]. 測繪科學， 2008（01）： 135-136+250.

[11] 楊必勝， 董震， 魏征， 等. 從車載激光掃描數據中提取復雜建筑物立面的方法[J]. 測繪學報， 2013， 42（3）： 411-417.

[12] Yang B， Xu W， Dong Z. Automated extraction of building outlines from airborne laser scanning point clouds[J]. IEEE Geoscience & Remote Sensing Letters， 2013， 10（6）： 1399-1403.

[13] Yang B， Wei Z， Li Q， et al. Semiautomated building facade footprint extraction from mobile LiDAR point clouds[J]. Geoscience & Remote Sensing Letters IEEE， 2013， 10（4）： 766-770.

[14] 張蕊， 李廣云， 李明磊， 等. 利用PCA-BP算法進行激光點云分類方法研究[J]. 測繪通報， 2014（07）： 23-26.

[15] 李娜， 馬一薇， 楊洋， 高晟麗. 利用RANSAC算法對建筑物立面進行點云分割[J]. 測繪科學， 2011， 36（05）： 144-145+138.

[16] 劉艷豐. 基于kd-tree的點云數據空間管理理論與方法[D]. 中南大學， 2009.

[17] 錢錦鋒， 陳志楊， 張三元， 葉修梓. 點云數據壓縮中的邊界特征檢測[J]. 中國圖象圖形學報， 2005（02）： 164-169.

[18] 朱海德. 點云庫PCL學習教程[M]. 北京航空航天大學出版社， 2012， 10.

[19] 王磊， 郭清菊， 姜晗. 基于改進的八叉樹索引與分層渲染的海量激光點云可視化技術[J]. 軟件， 2016， 37（3）： 114-117.

[20] 杜宇楠， 葉平， 孫漢旭. 基于激光與立體視覺同步數據的場景三維重建[J]. 軟件， 2012， 33（11）： 1-5.

[21] 黃昉菀， 戴禮豪， 陳國龍， 等. 基于激光數據特征提取的一般環境下實時定位方法[J]. 軟件， 2012， 33（5）： 9-11.