現代建筑物點云平面特征識別方法

王新靜 段晨鑫 姚怡燁

摘 要：【目的】基于現代建筑物點云數據面片特征，提出一種基于隨機抽樣一致算法的平面分割識別方法?！痉椒ā吭摲椒ㄏ壤萌S格網劃分來建立空間格網單元，再根據隨機采樣點來確定局部格網單元，通過隨機機制來擬合平面模型，經過局部打分來確定候選模型集，利用法向約束和共面分割來解決過分割和欠分割的問題?！窘Y果】采用該方法可獲取當前最優模型和一致集，并完成點云分割?！窘Y論】試驗結果表明，該方法能對富有平面特征的建筑物進行有效分割。

關鍵詞：點云；分割；局部采樣；一致集

中圖分類號：TP391? ? ?文獻標志碼：A? ? ?文章編號：1003-5168（2024）04-0004-05

DOI：10.19968/j.cnki.hnkj.1003-5168.2024.04.001

The Plane Feature Recognition Method for Modern Building Point Cloud

WANG Xinjing? ? DUAN Chenxin? ? YAO Yiye

（North China University of Water Resources and Electric Power， Zhengzhou 450046， China）

Abstract： [Purposes] According to the patch characteristics of modern building point cloud data， a plane segmentation recognition method based on random sampling consistent algorithm is proposed in this paper. [Methods] In this method， the spatial grid element is established by three-dimensional grid division， and then the local grid element is determined according to the random sampling points， the plane model is fitted by random mechanism， and the candidate model set is determined by local scoring. Normal constraints and coplanar segmentation are used to solve the problems of over-segmentation and insufficient segmentation. [Findings] Finally， the current optimal model and consistent set are obtained， and the point cloud segmentation can be completed. [Conclusions] The experimental results show that this method can segment the buildings with plane features effectively.

Keywords： point cloud; segmentation; local sampling; consistent set

0 引言

激光雷達技術是一種新型的高精度、多領域三維數據采集技術，使用三維激光掃描技術能獲取點云數據，并基于此來建立各種三維模型，從而被廣泛應用于文物保護［1］、地形測繪［2］、城市建筑測量［3］、大型構筑物［4］等領域中。對研究對象進行掃描，獲取的數據多為分布不均勻且數據量極大的點集，從這些數據中提取出有效的特征信息就顯得格外重要。在進行數據處理過程中，如果特征提取效果比較符合要求，相應的運行時間就會延長，如果分割速度過快，相應準確度則降低。所以，本研究旨在尋找出一種能有效且快速識別出建筑物平面特征的方法。

區域生長（Region growing）算法［4］是一種迭代方法，多用于分割復雜影像，但對硬件要求高，空間和時間開銷較大；基于聚類的點云分割（Cluster Analysis）算法［5］簡單，可發現任意形狀的簇，處理速度快，但對噪音不敏感，精確性不高，對較小數據量的分割效果不好；基于邊緣的點云數據分割［6］具有較高的分割速度，但受點云分布不均勻和誤差的影響，很難檢測出連續邊界；隨機采樣一致性算法（RANdom SAmple Consensus，RANSAC）［7］能魯棒的估計模型參數，但計算參數的迭代次數設置人為因素大。所以，本研究使用一種基于隨機抽樣一致性算法的局部采樣優化點云分割方法，實現對平面特征的有效識別。

本研究重點研究以下3個方面內容：①基于海量點云數據建立空間索引；②對冗余的點云數據進行分割；③實現一種優于隨機采樣一致算法（RANSAC）的自動識別點云平面特征的算法。

1 地面激光三維掃描數據處理

點云數據在分割前需要進行處理。①為了提高鄰域搜索效率，使用全局格網劃分建立鄰域關系；②計算各點的法向量。

1.1 全局格網劃分

先將所有點云數據統一劃分為網格，再采用文獻［8］中的方法，使用k-d樹來構造每個數據點的鄰域關系。網格結構設計步驟包括確定最小包圍框、確定最小邊長、確定編碼和編碼值。

1.1.1 確定最小包圍框。雖然點云數據體量較大，但仍然屬于有限個點集范疇。所以，有限個離散點總能確定一個最小的包圍框，包括所有離散點，有且僅有一個中心o點。這樣就可確定最小包圍框，并以o為原點來建立起三維直角坐標系，分別確定X、Y、Z的最大值與最小值，與原點o結合，可計算出最小包圍框的各個邊長（IX、IY、IZ）［8］。

1.1.2 確定最小邊長。最小邊長是指網格結構劃分后的子塊，由最小邊長可確定網格結構劃分后的個數。所以，最小邊長不能太小，否則會導致數據量過大，無法達到預期優化效果；最小邊長也不能過大，因為點云數據是離散的點，過大會導致建立拓撲關系的難度加大。有學者提出了一種評估最小邊長的方法［9］，最小包圍框的體積見式（1）。

V = IX×IY×IZ （1）

點云密度ρ為散亂點的個數N與V的比值，見式（2）。

ρ=N/V （2）

由于使用的最小邊長有限制，格網劃分后的小立方體邊長見式（3）。

[L=λ/ρ3] （3）

式中：λ為比例因子；ρ為點云密度；L為最小邊長。

1.1.3 確定編碼和編碼值。編碼是對網格劃分后的每個子塊進行編號，用來建立索引與查詢。編碼規則如下：按照逐層X、Y、Z的順序編碼，碼值的確定則是在眾多子塊中隨機選擇一點計算編號。確定編碼如圖1所示。

1.2 計算各點法向量

計算各點法向量的方法由Hoppe等在研究重建表面算法時首次提出，通過對數據進行點云配準、點云去噪、點云精簡后，得到光滑且無噪聲的點云數據。然后對每個采樣點建立局部鄰域，并利用最小二乘法進行擬合，得到采樣點的法向量。該方法被稱為主成分分析（Principal Component Analysis，PCA）。

在建筑物表面光滑時進行點云采樣，隨機選擇每個點在其局部鄰域內都可使用片面模型進行擬合，所以，需要對每個掃描點p進行鄰域搜索。假設可搜索到k個鄰近點，這些點在最小二乘意義上的局部平面表示見式（4）［9］。

[P（n，d）=argminni=1k（n·pi-d）2] （4）

式中：向量n為平面p的法向量；d為p到坐標原點的距離。

這個結果表明，平面p是通過k個鄰近點擬合出來的，法向量n是由平面p通過主成分分析得到的。由式（1）可知，P0是P經過其k鄰域點的質心，且法向量n的模等于1。先對式（5）中的M（協方差矩陣）進行特征值分解，求得M的各特征值，得到M的特征值最小值與最大值，而其最小值對應一個特征向量，即平面p的法向量n［9］。

[M=1ki=1k（pi-p0）（pi-p0）T] （5）

2 點云數據索引構建

原始數據只有簡單的三維坐標，并不具有拓撲關系。為方便基于領域的快速查找與建模，需要通過空間索引來建立拓撲關系。

使用三維柵格建立索引的關鍵在于設置任意一個大于0的數值δ和在三維坐標系中找到X、Y、Z的最大值（Xmax，Ymax，Zmax）與最小值（Xmin，Ymin，Zmin）。與鄰域概念相似，取坐標值（Xmax+δ，Ymax+δ，Zmax+δ）和（Xmin+δ，Ymin+δ，Zmin+δ）的亮點為對角點，且以邊長平行于坐標軸的方向來構建長方體的包圍盒，并將邊界盒劃分為小網格，小網格邊長設為α，點云數據的邊界盒以α為間隔，沿坐標軸方向劃分為空間獨立的六面體網格，使點云中每個空間點沒有拓撲關系的數據具有相應的空間立方體網格，從而完成點云數據的索引。對不同大小的點云數據，可設置不同的網格大小α來劃分點云數據，從而靈活地控制點云數據領域的索引范圍。由于空間點是通過網格索引得到的，因此，需要對網格進行排序，從而提高點云數據的索引效率。

3 基于RANSAC的點云分割

3.1 RANSAC方法原理

RANSAC是在計算機視覺領域中廣泛應用的一種隨機采樣一致性算法。在進行分析和三維建模時，選擇合適的模型和正確的模型參數是學者們最關心的，也是算法中最重要的一步。采用隨機抽樣法可刪除無效點，避免其對集合產生影響，產生的子集都是由有效點組合而成的［10］。RANSAC方法原理如下：在估計參數具體問題時，根據需要預先設定一個評判標準，不斷刪除數據；然后使用判斷標準不一致的參數估計，反復使用判斷標準；最后通過有效的輸入數據刪除后來估計準確的參數。規定某一置信概率，基本子集的最小抽樣數M和獲得至少一個正確子集P（P>ξ）的概率滿足的關系見式（6）［10］。

P=1-[1-（1-ξ）m]M （6）

式中：ξ為錯誤的數據概率；m為參數估計的最小數據量；M為基本子集最小抽樣數；P為至少取得一個良性取樣子集的概率，一般取值為0.9～0.99。

3.2 霍夫變換算法原理

霍夫變換［11］（Hough）是在原始圖像空間或點云數據處理中，根據點與線之間的對偶性，將給定曲線的檢測問題轉換成參數空間各點。轉換后的問題發生變化，即不再是原始圖像存在的曲線問題，而是在參數空間計算峰值的問題。通過簡單的閾值就可確定目標，從而提高效率。由于RANSAC方法不能很好地解決噪聲干擾問題，而霍夫變換在檢測直線或圓時，通過簡單的轉化，可有效避免噪聲的干擾。以線性檢測為例，霍夫變換基本流程如下。

將圖像空間內線的坐標形式變換為參數空間內的極坐標形式，見式（7）。

ρ=xcosθ+ysinθ， （7）

式中：ρ為原點到線的距離；θ為直線的垂直線和x軸之間的角度。圖像空間函數如圖2所示。

圖像空間內的各點（x，y）對應滿足參數ρ＝xcosθ+ysinθ的參數空間內的正弦或余弦曲線，映射到參數空間相交于一點表示為（ρ0、θ0），參數空間如圖3所示。

由于圖像空間內同一線上的點映射在參數空間內的同一點上，可通過求解參數空間內的局部極值點來解交點，并求出圖像空間內的線，即將圖像空間中的線性方程轉換成參數空間中點的極值問題。

3.3 基于RANSAC的局部采樣點云分割

3.3.1 隨機采樣。在當前點云數據中隨機選擇采樣點，并根據空間位置來確定局部網格單元。局部RANSAC方法是在局部網格中搜索平面特征的模型，算法步驟如下：①隨機選擇所需樣本，完成平面模型參數的計算（平面模型需要確定有向采樣點）；②對平面模型進行局部打分；③迭代計算完成模型的最優參數。如果基本單元里最優參數模型的一致集合小于預定數量，則執行重新抽樣［12］。

3.3.2 局部打分規則。為了確定模型在當前網格中的最優參數，需要對擬合模型進行打分，即確定在一定誤差范圍內與候選模型一致的集合數，以下是兩種控制誤差的方法。

①法向偏差。通常的偏差是候選模型的投影點p中基準點的法線方向和候補模型投影點P的法線方向成的角度，法向偏差的表示見式（8）。

[θ=αcos（n·n′）] （8）

②點到候選模型的距離。給定一點P（x，y，z），其法向量為（u，v，w），該點到平面ax+by+cz+d=0的距離見式（9）。

[Dplane=a×x+b×y+c×z+da×a+b×b+c×c] （9）

只有當這兩個指數小于某個閾值時，其才能被認為與該模型一致。在完成局部評分后，就確定了平面特征模型的最優參數，并獲得一致集。

4 面片分割試驗

通過對原始點云數據處理和常見的分割算法進行分析，對本研究所提出的分割方法進行試驗驗證分析。

4.1 數據采集與處理

4.1.1 外業數據收集。使用地面三維激光掃描儀掃描物體時，要嚴格按照三維激光掃描儀使用步驟。三維激光點云數據采集流程如圖4所示。

4.1.2 內業數據處理。為了驗證本研究提出的算法的有效性，采用leicahds6000掃描儀對具有豐富平面特征的現代建筑進行數據采集?，F代建筑的平均點間距為6 mm，包括24 712點云。算法是在單PC環境中運行，內存配置為8 GB，CPU為i7-2 760 QM，主頻為2.4 GHz。操作系統環境為Windows 10 64 bit專業版，算法采用C++語言，以VS.NET2010為平臺。試驗數據如圖5所示。

4.2 參數設置

該算法的參數包括在三維網格之間的距離、法向量鄰域數量、局部RANSAC算法重疊的最大數、法向偏差閾值和距離閾值、共平面分割中格網間的間隔等。網格間距一般設置為平均點間距的35倍，以保證每個網格單元有足夠的樣本空間。法向鄰域點數為24，RANSAC算法的最大迭代次數為1 000。根據相鄰面片的連接情況來設置法向偏差閾值，如果相鄰面之間的突變較大，則可設置較大的閾值；如果面片之間的過渡平滑，則可根據需要設置較小的閾值。距離閾值通常與儀器的測距精度和建筑物表面的粗糙程度有關，為簡便起見，本研究將其設置為1.1 cm，共面分割的網格間距設置為平均分辨率的1.5倍。

4.3 分割結果

一般來說，對進行分割的立體模型，根據最優模型集能很好地完成分割，但在現實生活中，建筑物并非為規則的立體模型，面片分割時會出現過分割和分割不充分。由于不同面的分割順序不同，并存在誤差（點與模型之間的距離），兩個相鄰面的第二段中的點可能會被錯誤地分割到相鄰的第一段中，這種現象被稱為過分割現象。在一個建筑物角落里，分別定義右平面A、鉛垂線C和左平面B，由于距離誤差閾值的限制，面片A和面片B中與鉛垂線C距離較近的點，會因為距離小于閾值而相互誤分割。此外，相鄰兩面片在交界處一般存在法向突變，使用法向量的值與方向進行法向約束能很好解決這類問題。法向約束效果如圖6所示。

同一參數不在同一平面（同參異面）時，即某一參數模型的一致集合具有不同的面片聚集區域，會出現分割不充分的現象。因此，對平面類需要將共識集投影到相應平面上，然后按照常規聚類方法對二維網格進行劃分，并對空間進行劃分，完成共面分割后，獲得各獨立的數據聚集區域。最終分割結果如圖7所示。

5 結語

本研究使用一種根據地面三維激光掃描現代建筑物而形成點云數據的方法，通過數據檢測、識別、由點到線再到面，從而實現對建筑物平面分割。該方法利用地面激光點云數據的高空間分辨率，將采樣點視為目標對象的冗余表示。在此基礎上，提出了一種基于局部采樣的局部RANSAC模型檢測方法，并通過統計推斷策略對每個局部候選模型的全局得分進行估計，從而獲得當前最優模型，有效避免了點云數據分割中的過度分割、分割不充分和同參異面的問題，從而實現對現代建筑物平面特征的識別與提取。

參考文獻：

［1］劉鈺.激光掃描技術在文物建模及虛擬修復中的應用研究［D］.西安：長安大學，2012.

［2］耿霄雯.三維激光掃描技術在地形測繪中的應用探究［J］.建材與裝飾，2019（3）：234-235.

［3］丁延輝，邱冬煒，王鳳利，等.基于地面三維激光掃描數據的建筑物三維模型重建［J］.測繪通報，2010（3）：55-57.

［4］MIRCEAEMIL N，SILVIA C，CALIMANUTIONUT C，et al.Non-destructive measurements for 3D modeling and monitoring of large buildings using terrestrial laser scanning and unmanned aerial systems［J］.Sensors，2023（12）：5678.

［5］汪文琪，李宗春，付永健，等.基于改進多規則區域生長的點云多要素分割［J］.光學學報，2021（5）：198-212.

［6］王曉輝，吳祿慎，陳華偉，等.基于區域聚類分割的點云特征線提?。跩］.光學學報，2018（11）：66-75.

［7］FAN T J，MEDIONI G，NEVATIA R.Segmented descriptions of 3-D surfaces［J］.IEEE Journal on Robotics and Automation，1987（6）：527-538.

［8］王力.三維掃描數據處理中數據結構的設計與比較［J］.測繪通報，2010（9）：63-65.

［9］SHAH T R.Automatic reconstruction of industrial installations using point clouds and images［D］.Delft：Delft University of Technology，2006.

［10］陳付幸，王潤生.基于預檢驗的快速隨機抽樣一致性算法［J］.軟件學報，2005（8）：1431-1437.

［11］田朋舉，花向紅，康停軍，等.一種基于點云數據的建筑物平面精細分割方法［J］.測繪科學，2021，46（2）：122-129.

［12］石宏斌，殷義程，袁曼飛.點云數據的多幾何面片特征自動識別［J］.測繪通報，2017（2）：6-9，53.