王新靜 段晨鑫 姚怡燁

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

關(guān)鍵詞：點(diǎn)云；分割；局部采樣；一致集

中圖分類號(hào)：TP391? ? ?文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：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 引言

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

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

本研究重點(diǎn)研究以下3個(gè)方面內(nèi)容：①基于海量點(diǎn)云數(shù)據(jù)建立空間索引；②對(duì)冗余的點(diǎn)云數(shù)據(jù)進(jìn)行分割；③實(shí)現(xiàn)一種優(yōu)于隨機(jī)采樣一致算法（RANSAC）的自動(dòng)識(shí)別點(diǎn)云平面特征的算法。

1 地面激光三維掃描數(shù)據(jù)處理

點(diǎn)云數(shù)據(jù)在分割前需要進(jìn)行處理。①為了提高鄰域搜索效率，使用全局格網(wǎng)劃分建立鄰域關(guān)系；②計(jì)算各點(diǎn)的法向量。

1.1 全局格網(wǎng)劃分

先將所有點(diǎn)云數(shù)據(jù)統(tǒng)一劃分為網(wǎng)格，再采用文獻(xiàn)［8］中的方法，使用k-d樹來構(gòu)造每個(gè)數(shù)據(jù)點(diǎn)的鄰域關(guān)系。網(wǎng)格結(jié)構(gòu)設(shè)計(jì)步驟包括確定最小包圍框、確定最小邊長(zhǎng)、確定編碼和編碼值。

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

1.1.2 確定最小邊長(zhǎng)。最小邊長(zhǎng)是指網(wǎng)格結(jié)構(gòu)劃分后的子塊，由最小邊長(zhǎng)可確定網(wǎng)格結(jié)構(gòu)劃分后的個(gè)數(shù)。所以，最小邊長(zhǎng)不能太小，否則會(huì)導(dǎo)致數(shù)據(jù)量過大，無法達(dá)到預(yù)期優(yōu)化效果；最小邊長(zhǎng)也不能過大，因?yàn)辄c(diǎn)云數(shù)據(jù)是離散的點(diǎn)，過大會(huì)導(dǎo)致建立拓?fù)潢P(guān)系的難度加大。有學(xué)者提出了一種評(píng)估最小邊長(zhǎng)的方法［9］，最小包圍框的體積見式（1）。

V = IX×IY×IZ （1）

點(diǎn)云密度ρ為散亂點(diǎn)的個(gè)數(shù)N與V的比值，見式（2）。

ρ=N/V （2）

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

[L=λ/ρ3] （3）

式中：λ為比例因子；ρ為點(diǎn)云密度；L為最小邊長(zhǎng)。

1.1.3 確定編碼和編碼值。編碼是對(duì)網(wǎng)格劃分后的每個(gè)子塊進(jìn)行編號(hào)，用來建立索引與查詢。編碼規(guī)則如下：按照逐層X、Y、Z的順序編碼，碼值的確定則是在眾多子塊中隨機(jī)選擇一點(diǎn)計(jì)算編號(hào)。確定編碼如圖1所示。

1.2 計(jì)算各點(diǎn)法向量

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

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

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

式中：向量n為平面p的法向量；d為p到坐標(biāo)原點(diǎn)的距離。

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

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

2 點(diǎn)云數(shù)據(jù)索引構(gòu)建

原始數(shù)據(jù)只有簡(jiǎn)單的三維坐標(biāo)，并不具有拓?fù)潢P(guān)系。為方便基于領(lǐng)域的快速查找與建模，需要通過空間索引來建立拓?fù)潢P(guān)系。

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

3 基于RANSAC的點(diǎn)云分割

3.1 RANSAC方法原理

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

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

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

3.2 霍夫變換算法原理

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

將圖像空間內(nèi)線的坐標(biāo)形式變換為參數(shù)空間內(nèi)的極坐標(biāo)形式，見式（7）。

ρ=xcosθ+ysinθ， （7）

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

圖像空間內(nèi)的各點(diǎn)（x，y）對(duì)應(yīng)滿足參數(shù)ρ＝xcosθ+ysinθ的參數(shù)空間內(nèi)的正弦或余弦曲線，映射到參數(shù)空間相交于一點(diǎn)表示為（ρ0、θ0），參數(shù)空間如圖3所示。

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

3.3 基于RANSAC的局部采樣點(diǎn)云分割

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

3.3.2 局部打分規(guī)則。為了確定模型在當(dāng)前網(wǎng)格中的最優(yōu)參數(shù)，需要對(duì)擬合模型進(jìn)行打分，即確定在一定誤差范圍內(nèi)與候選模型一致的集合數(shù)，以下是兩種控制誤差的方法。

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

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

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

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

只有當(dāng)這兩個(gè)指數(shù)小于某個(gè)閾值時(shí)，其才能被認(rèn)為與該模型一致。在完成局部評(píng)分后，就確定了平面特征模型的最優(yōu)參數(shù)，并獲得一致集。

4 面片分割試驗(yàn)

通過對(duì)原始點(diǎn)云數(shù)據(jù)處理和常見的分割算法進(jìn)行分析，對(duì)本研究所提出的分割方法進(jìn)行試驗(yàn)驗(yàn)證分析。

4.1 數(shù)據(jù)采集與處理

4.1.1 外業(yè)數(shù)據(jù)收集。使用地面三維激光掃描儀掃描物體時(shí)，要嚴(yán)格按照三維激光掃描儀使用步驟。三維激光點(diǎn)云數(shù)據(jù)采集流程如圖4所示。

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

4.2 參數(shù)設(shè)置

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

4.3 分割結(jié)果

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

同一參數(shù)不在同一平面（同參異面）時(shí)，即某一參數(shù)模型的一致集合具有不同的面片聚集區(qū)域，會(huì)出現(xiàn)分割不充分的現(xiàn)象。因此，對(duì)平面類需要將共識(shí)集投影到相應(yīng)平面上，然后按照常規(guī)聚類方法對(duì)二維網(wǎng)格進(jìn)行劃分，并對(duì)空間進(jìn)行劃分，完成共面分割后，獲得各獨(dú)立的數(shù)據(jù)聚集區(qū)域。最終分割結(jié)果如圖7所示。

5 結(jié)語

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

參考文獻(xiàn)：

［1］劉鈺.激光掃描技術(shù)在文物建模及虛擬修復(fù)中的應(yīng)用研究［D］.西安：長(zhǎng)安大學(xué)，2012.

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

［3］丁延輝，邱冬煒，王鳳利，等.基于地面三維激光掃描數(shù)據(jù)的建筑物三維模型重建［J］.測(cè)繪通報(bào)，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ìn)多規(guī)則區(qū)域生長(zhǎng)的點(diǎn)云多要素分割［J］.光學(xué)學(xué)報(bào)，2021（5）：198-212.

［6］王曉輝，吳祿慎，陳華偉，等.基于區(qū)域聚類分割的點(diǎn)云特征線提取［J］.光學(xué)學(xué)報(bào)，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］王力.三維掃描數(shù)據(jù)處理中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與比較［J］.測(cè)繪通報(bào)，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］陳付幸，王潤(rùn)生.基于預(yù)檢驗(yàn)的快速隨機(jī)抽樣一致性算法［J］.軟件學(xué)報(bào)，2005（8）：1431-1437.

［11］田朋舉，花向紅，康停軍，等.一種基于點(diǎn)云數(shù)據(jù)的建筑物平面精細(xì)分割方法［J］.測(cè)繪科學(xué)，2021，46（2）：122-129.

［12］石宏斌，殷義程，袁曼飛.點(diǎn)云數(shù)據(jù)的多幾何面片特征自動(dòng)識(shí)別［J］.測(cè)繪通報(bào)，2017（2）：6-9，53.