石宏斌，殷義程，袁曼飛

(1. 許昌學(xué)院城鄉(xiāng)規(guī)劃與園林學(xué)院，河南 許昌 461000； 2. 云南省測(cè)繪工程院，云南 昆明 650033；3. 陜西鐵路工程職業(yè)技術(shù)學(xué)院，陜西 渭南 714000)

點(diǎn)云數(shù)據(jù)的多幾何面片特征自動(dòng)識(shí)別

石宏斌1，殷義程2，袁曼飛3

(1. 許昌學(xué)院城鄉(xiāng)規(guī)劃與園林學(xué)院，河南 許昌 461000； 2. 云南省測(cè)繪工程院，云南 昆明 650033；3. 陜西鐵路工程職業(yè)技術(shù)學(xué)院，陜西 渭南 714000)

針對(duì)人工構(gòu)筑物豐富的面片特征，提出一種基于局部采樣優(yōu)化的多種幾何面片(平面、柱面、球面)點(diǎn)云數(shù)據(jù)分割方法。該方法首先利用三維格網(wǎng)建立點(diǎn)云數(shù)據(jù)的空間劃分，然后根據(jù)隨機(jī)采樣點(diǎn)確定局部格網(wǎng)單元，在格網(wǎng)單元內(nèi)部擬合多種幾何模型，通過局部打分確定局部候選模型(集)，利用統(tǒng)計(jì)推斷估算候選模型集的全局打分區(qū)間，最終獲得當(dāng)前最優(yōu)模型及其一致集，從而實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)分割。試驗(yàn)結(jié)果表明：該方法能夠?qū)Ω缓?guī)則幾何特征的人工構(gòu)筑物進(jìn)行有效分割。

地面激光三維掃描；分割；局部采樣；統(tǒng)計(jì)推斷；法向約束

地面LiDAR技術(shù)廣泛應(yīng)用于各種對(duì)象的精細(xì)三維重建，它所獲得的點(diǎn)云數(shù)據(jù)具有海量性、散亂性、高空間分辨率等特性[1]。根據(jù)一定的屬性或規(guī)則，將這些具有高空間分辨率的散亂點(diǎn)云數(shù)據(jù)劃分為若干互不相交的子集的過程，稱為點(diǎn)云數(shù)據(jù)分割[2]，它廣泛應(yīng)用于基于特征的配準(zhǔn)[3]、模型重建[4]、點(diǎn)云數(shù)據(jù)濾波與精簡(jiǎn)等[5]、語義分類[6]，是激光點(diǎn)云數(shù)據(jù)處理中的一項(xiàng)基礎(chǔ)性工作。目前，點(diǎn)云數(shù)據(jù)分割的方法主要分為基于邊的方法和基于面的方法?；谶叺姆椒ㄊ鞘紫忍綔y(cè)突變邊界，根據(jù)閉合邊界分割數(shù)據(jù)體；基于面的方法是根據(jù)對(duì)象的幾何面片特性，將數(shù)據(jù)分為具有不同面片特征的數(shù)據(jù)集合。其中，基于面的方法能為人們提供點(diǎn)云數(shù)據(jù)的抽象表達(dá)，有利于后期的表達(dá)與分析，因此獲得了廣泛的認(rèn)可[7]。

在基于面的方法中，隨機(jī)采樣一致性方法RANSAC(random sample consensus)是最為常用的方法，它具有內(nèi)存消耗低，方法簡(jiǎn)單、通用、易擴(kuò)展等特點(diǎn)，在實(shí)際中獲得了廣泛的應(yīng)用[8]。如BOLLES利用RANSAC方法從距離影像中提取圓柱[9]；CHAPERON利用RANSAC方法和高斯影像從點(diǎn)云數(shù)據(jù)中提取圓柱[10]；王植利用RANSAC方法對(duì)機(jī)載激光點(diǎn)云數(shù)據(jù)進(jìn)行平面分割以獲取建筑物輪廓信息[11]；皇甫中民利用RANSAC方法提取旋轉(zhuǎn)特征面[12]；Tarek M利用Seq-RANSAC方法從散亂點(diǎn)云數(shù)據(jù)中探測(cè)平面特征[13]。上述文獻(xiàn)中都是從點(diǎn)云數(shù)據(jù)中識(shí)別一種幾何特征，缺少多種幾何面片探測(cè)機(jī)制。而現(xiàn)實(shí)人工對(duì)象多以不同規(guī)則幾何形體有機(jī)構(gòu)成，如何在這些人工對(duì)象所對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)中有效自動(dòng)探測(cè)多種面片特征，在現(xiàn)實(shí)中具有重要意義。本文在傳統(tǒng)RANSAC方法的基礎(chǔ)上，提出基于局部采樣優(yōu)化和統(tǒng)計(jì)推斷策略的多幾何面片(本文以平面、柱面、球面為例)探測(cè)方法，最終實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)分割。

1 多幾何特征探測(cè)方法

1.1 基本原理

在現(xiàn)實(shí)人工對(duì)象中，面片屬于局部特征，高空間分辨率點(diǎn)云數(shù)據(jù)是對(duì)目標(biāo)對(duì)象的冗余表達(dá)。傳統(tǒng)RANSAC方法的全局采樣策略擴(kuò)大了探測(cè)多種幾何面片特征所需的比對(duì)空間。當(dāng)面片特征較多、體量較大時(shí)，勢(shì)必造成探測(cè)效率的降低[14]。鑒于此，本文多種幾何面片識(shí)別方法可表述為以下流程：

(1) 利用三維空間格網(wǎng)對(duì)當(dāng)前點(diǎn)云數(shù)據(jù)進(jìn)行空間劃分，利用kd-Tree構(gòu)建點(diǎn)的局部鄰域，以滿足點(diǎn)鄰域搜索和屬性計(jì)算。

(2) 在當(dāng)前點(diǎn)集中隨機(jī)抽取一待分類點(diǎn)，根據(jù)空間位置確定其所在的空間格網(wǎng)單元，在該格網(wǎng)單元內(nèi)執(zhí)行局部RANSAC方法以確定候選模型集。

(3) 確定各候選模型在鄰域單元格網(wǎng)打分，利用數(shù)理統(tǒng)計(jì)中的方法推斷各模型的全局打分，獲得最優(yōu)模型及其對(duì)應(yīng)的一致集，并將一致集從當(dāng)前數(shù)據(jù)集中分離出去。

(4) 循環(huán)以上過程，直至剩余點(diǎn)集為空或小于最小點(diǎn)集，從而完成分割。

1.2 數(shù)據(jù)預(yù)處理

在對(duì)點(diǎn)云數(shù)據(jù)分割之前，對(duì)點(diǎn)云數(shù)據(jù)作兩項(xiàng)預(yù)處理：①為了提高分割過程中的鄰域搜索效率，本文采用文獻(xiàn)[15]中的方法，對(duì)點(diǎn)云數(shù)據(jù)實(shí)現(xiàn)全局格網(wǎng)劃分，利用kd-tree構(gòu)建點(diǎn)的局部鄰域關(guān)系；②利用文獻(xiàn)[2]中的方法計(jì)算各點(diǎn)的法向量nm。

1.3 局部RANSAC

在當(dāng)前點(diǎn)云數(shù)據(jù)中隨機(jī)抽取一采樣點(diǎn)，根據(jù)其空間位置判定所屬格網(wǎng)單元，在格網(wǎng)單元內(nèi)部實(shí)施局部RANSAC方法，依次探測(cè)平面、柱面、球面模型的最優(yōu)參數(shù)。算法過程如下：

(1) 模型計(jì)算：隨機(jī)抽取m個(gè)必要采樣完成各模型Mi參數(shù)計(jì)算。①平面：只需要一個(gè)有向采樣(p,nm)即可確定一個(gè)平面Mp；②球面：以兩采樣點(diǎn)(p1,nm1)、(p2,nm2)確定兩空間直線l1l2，以l1l2間的最短線段的中點(diǎn)o作為球的球心，以r=(‖p1-o‖+‖p2-o‖)/2為半徑，確定球體參數(shù)Ms(o,R)；③圓柱面：以兩個(gè)采樣點(diǎn)p1、p2的法向nm1、nm2的叉積作為圓柱的軸向dir，以p1、p2及其法向nm1、nm2確定兩空間直線l1、l2，以l1、l2間的空間最短線段的中點(diǎn)o作為圓柱軸向所經(jīng)過一點(diǎn)，確定軸線方程l(o,dir)，以p1、p2至l(o,dir)的距離均值為半徑r，確定圓柱Mc(o,r,dir)。

(2) 打分：在格網(wǎng)單元內(nèi)對(duì)各模型Mi進(jìn)行局部打分。依據(jù)如下兩個(gè)規(guī)則，在局部格網(wǎng)單元中確定與所擬合模型Mi一致的點(diǎn)集數(shù)目，作為對(duì)應(yīng)模型的打分。

① 法向約束

θ=acos(n·n′)

(1)

式中，n為采樣點(diǎn)p的法向；n′為p點(diǎn)在模型Mi的投影點(diǎn)p′處的法向。

② 距離約束

dM

(2)

對(duì)于給定點(diǎn)P=(x,y,z)，該點(diǎn)到平面ax+by+cz+d=0的距離dM可表達(dá)為

(3)

該點(diǎn)到球心坐標(biāo)為Osp(a,b,c)球面方程(x-a)2+(y-b)2+(z-c)2=R2的距離dM可表達(dá)為

(4)

該點(diǎn)到中心軸向直線為L(zhǎng)(x=x0+mt;y=y0+nt;z=z0+qt;P0=(x0,y0,z0))、底面半徑為r的圓柱面距離dM可表達(dá)為

(5)

滿足以上約束的點(diǎn)為模型的一致點(diǎn)。經(jīng)過局部打分，確定各模型的最優(yōu)參數(shù)及其一致集，對(duì)于一致集數(shù)目超過格網(wǎng)內(nèi)部點(diǎn)數(shù)一半的最優(yōu)模型Mi加入到候選模型集M中。

(3) 循環(huán)：循環(huán)以上過程，獲得當(dāng)前格網(wǎng)各基元最優(yōu)模型，若各基元最優(yōu)參數(shù)模型的一致集均小于預(yù)定數(shù)目，則重新采樣；若通過，則將通過的各基元最優(yōu)參數(shù)模型加入候選模型集M中，M=M∪Mi。

1.4 確定最優(yōu)模型

若M中只有一種模型，則直接計(jì)算其全局一致集。若M中存在多種模型(例如在一定的誤差范圍內(nèi)，柱面或球面的局部可能被認(rèn)為是平面特征)，則需進(jìn)一步區(qū)分。理論上說，M中的最優(yōu)模型，需要在全局范圍內(nèi)具有最大一致集，但在海量點(diǎn)云數(shù)據(jù)中，即使對(duì)平面特征打分，仍需要較大的時(shí)間開銷。在數(shù)理統(tǒng)計(jì)中，常常通過抽樣來推測(cè)具有某一特征的樣本所占的總體比例，當(dāng)抽樣屬于不放回抽樣且當(dāng)樣本空間較大，可用正態(tài)分布來模擬描述該特性的隨機(jī)變量的分布特征，在當(dāng)前格網(wǎng)單元及其鄰域單元中，判定某個(gè)點(diǎn)pti是否屬于某個(gè)模型的過程可描述為

(6)

2 試 驗(yàn)

為了驗(yàn)證本文算法的有效性，以富含平面、柱面、球面特征的建筑物立面數(shù)據(jù)作為試驗(yàn)數(shù)據(jù)，如圖1所示，該數(shù)據(jù)點(diǎn)數(shù)為3 734 518，平均點(diǎn)間距為5 mm。算法實(shí)施采用單PC環(huán)境，內(nèi)存配置為8 GB，CPU為i7-2760QM，主頻為2.4 GHz。操作系統(tǒng)環(huán)境為Windows 7 64 bit專業(yè)版，算法采用C++語言，以VS.NET2010為平臺(tái)。

圖1 建筑物點(diǎn)云數(shù)據(jù)

在數(shù)據(jù)預(yù)處理中，為保證格網(wǎng)單元有足夠的樣本空間，格網(wǎng)間距一般設(shè)為40倍的平均點(diǎn)間距；計(jì)算法向的鄰域點(diǎn)數(shù)為25。在局部RANSAC算法中

最大迭代次數(shù)為10 000；法向偏差閾值thθ可以根據(jù)面片鄰接情況設(shè)置，相鄰面片間存在較大突變可以設(shè)較大閾值，當(dāng)面片間變換比較平緩，需設(shè)置較小閾值，設(shè)thθ=0.9 rad；距離閾值thd一般與儀器測(cè)距精度、多站配準(zhǔn)精度和表面精細(xì)程度有關(guān)，本文統(tǒng)一設(shè)為2 cm。最小點(diǎn)集數(shù)目可以根據(jù)實(shí)際靈活設(shè)置，數(shù)目較大時(shí)較小面片就會(huì)被忽略，數(shù)目較小時(shí)則會(huì)保留較多的微小面片，本文統(tǒng)一設(shè)為50。

當(dāng)隨機(jī)采樣點(diǎn)落在格網(wǎng)單元E中時(shí)，如圖2所示，在E中利用RANSAC方法探測(cè)平面、柱面、球面的最優(yōu)參數(shù)模型，各參數(shù)模型在E中及各鄰域格網(wǎng)的內(nèi)點(diǎn)數(shù)目見表1?？梢钥闯?，在E格網(wǎng)內(nèi)，球面與柱面一致集相同且與平面類差別不大，基于統(tǒng)計(jì)推斷的置信區(qū)間區(qū)分也不明顯，見表2。為了獲得可靠的模型參數(shù)，在E格網(wǎng)的鄰域格網(wǎng)中隨機(jī)選取一格網(wǎng)，繼續(xù)打分推斷，設(shè)該隨機(jī)選取的格網(wǎng)為D格網(wǎng)，各參數(shù)模型在各格網(wǎng)的累計(jì)打分和置信區(qū)間見表2。由表可以看出，柱面的置信區(qū)間明顯高于平面和球面，因此可以判定柱面為格網(wǎng)E中探測(cè)到的最優(yōu)模型。同理，若該鄰域格網(wǎng)為非D的其他格網(wǎng)，表1給出了各鄰域格網(wǎng)的打分統(tǒng)計(jì)，依然可以利用該方法獲得當(dāng)前最優(yōu)模型。

表1 局部打分統(tǒng)計(jì)

表2 全局推斷統(tǒng)計(jì)

圖2 多幾何面片探測(cè)

根據(jù)獲得的最優(yōu)模型，在全局點(diǎn)云中，根據(jù)式(1)—式(5)的判定規(guī)則，計(jì)算該模型的內(nèi)點(diǎn)，從而將該面片從點(diǎn)云數(shù)據(jù)中分割出來。但是在該過程中存在過度分割和分割不充分的問題：

第一種是在點(diǎn)云數(shù)據(jù)分割過程中，由于不同面片的分割順序不同且允許誤差的存在(點(diǎn)到模型的距離)，在兩相鄰面片中會(huì)存在后分割面片中的點(diǎn)被誤分割到相鄰先分割的面片中，如圖3(a)所示，A、B、D為三相鄰面片，由于面片A比面片B、D先分割出來，由于距離誤差閾值的限制，面片B、D中到面片A的距離小于閾值的點(diǎn)被誤分到面片A中，如圖3(a)所示C、E區(qū)域，因此A存在分割不充分，B存在過度分割，這些都屬于誤分割。而相鄰面片交界處一般存在法向突變，因此本文的法向約束能較好地處理這類問題，約束后的分割效果如圖3(b)所示。

另外一種是同參異面的情況，也就是某一參數(shù)模型的一致集存在不同面片聚集區(qū)域，如圖4(a)所示，這屬于分割不充分的問題。因此對(duì)各模型的一致集進(jìn)行空間聚類，將各聚類結(jié)點(diǎn)歸為不同分割對(duì)象。對(duì)于平面類將其一致集投影至對(duì)應(yīng)平面上，然后進(jìn)行二維格網(wǎng)劃分，按照常規(guī)聚類方法實(shí)現(xiàn)空間劃分；柱面類面片需要按軸向展成平面，然后按照平面類方法進(jìn)行共面分割；球面類按三維空間格網(wǎng)進(jìn)行空間劃分，實(shí)現(xiàn)共面分割。格網(wǎng)間距設(shè)為平均分辨率的4倍。共面分割和最終分割效果如圖4(b)所示。

圖4 共面分割效果

3 結(jié)束語

本文介紹了一種激光點(diǎn)云數(shù)據(jù)多種面片特征識(shí)別方法。該方法利用地面激光點(diǎn)云數(shù)據(jù)的高空間分辨率的特性，認(rèn)為采樣點(diǎn)是對(duì)目標(biāo)對(duì)象的冗余表達(dá)，基于此提出基于局部采樣的局部RANSAC模型探測(cè)方法，并利用統(tǒng)計(jì)推斷策略估算各局部候選模型的全局打分，獲得當(dāng)前最優(yōu)模型。該方法在采樣策略上對(duì)傳統(tǒng)RANSAC方法進(jìn)行了優(yōu)化，利用統(tǒng)計(jì)推斷的策略對(duì)獲得最優(yōu)模型的方法進(jìn)行了拓展。

試驗(yàn)結(jié)果表明，本文所提出的基于局部采樣和統(tǒng)計(jì)推斷的方法能夠有效規(guī)避傳統(tǒng)RANSAC方法的全局采樣策略所造成的無法檢測(cè)多種幾何面片特征的問題，能夠有效探測(cè)人工構(gòu)筑物中存在的平面、柱面、球面特征，并且較好地處理了點(diǎn)云數(shù)據(jù)分割中的過度分割和分割不充分的問題、同參異面問題。

[1] 郭明.海量精細(xì)空間數(shù)據(jù)管理技術(shù)研究[D].武漢:武漢大學(xué),2011.

[2] RABBANI T.Automatic Reconstruction of Industrial Installations Using Point Clouds and Images[D].Delft：Delft University of Technology,2006.

[3] 何文峰.大型場(chǎng)景三維重建中的深度圖像配準(zhǔn)[D].北京:北京大學(xué),2004.

[4] 陳卓,馬洪超.基于機(jī)載LiDAR數(shù)據(jù)的大型立交橋自動(dòng)提取與建模方法[J].測(cè)繪學(xué)報(bào),2012,41(2):252-258.

[5] SITHOLE G,VOSSELMAN G.Filtering of Airborne Laser Scanner Data Based on Segmented Point Clouds[C]∥Laser Scanning 2005.[S.l.]：ISPRS，2005.

[6] TAMAS L, GORON L C. 3D Semantic Interpretation for Robot Perception Inside Office Environments[J].Engineering Applications of Artificial Intelligence, 2014,32(4-5):210-215.

[7] BELTON D. Classification and Segmentation of 3D Terrestrial Laser Scanner Point Clouds[D]. Bentley：Curtin University of Technology,2008.

[8] 李寶.三維點(diǎn)云的魯棒處理技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2011.

[9] BOLLES R C,FISCHLER M A.A RANSAC-based Approach to Model Fitting and Its Application to Finding Cylinders in Range Data[C]∥Proceedings of the 7th International Joint Conference on Artificial Intelligence.[S.l.]：International Joint Conference on Artificial Intelligence，1981,637-643.

[10] CHAPERON T,GOULETTE F.Extracting Cylinders in Full 3-d Data Using a Random Sampling Method and the Gaussian Image[J]. VMV，2001(1)：35-42.

[11] 王植,李慧盈,吳立新,等.基于RANSAC模型的機(jī)載LiDAR 數(shù)據(jù)中建筑輪廓提取算法[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,33(2):271-275.

[12] 皇甫中民,閆雒恒,劉雪梅.基于RANSAC算法的旋轉(zhuǎn)面特征提取[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(5):1295-1298.

[13] TAREK M A.基于散亂地面激光掃描點(diǎn)云數(shù)據(jù)的復(fù)雜立面中平面的自動(dòng)提取[D].武漢:武漢大學(xué),2010.

[14] 陳付幸,王潤(rùn)生.基于預(yù)檢驗(yàn)的快速隨機(jī)抽樣一致性算法[J].軟件學(xué)報(bào),2005,16(8):1431-1437.

[15] 王力.三維掃描數(shù)據(jù)處理中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與比較[J].測(cè)繪通報(bào),2010(9)：63-65.

An Automatic Method for Point Cloud Multi-Geometry Feature Recognition

SHI Hongbin1,YIN Yicheng2,YUAN Manfei3

(1. School of Urban-rural Planning and landscape Architecture, Xuchang University, Xuchang 461000,China； 2. Surveying and Mapping Engineering Institute of Yunnan Province,Kunming 650033,China； 3. Shaanxi Railway Institute, Weinan 714000, China)

A segmentation method is proposed in this paper，based on local sample for point cloud with rich geometry features(plane,cylinder,sphere). The proposed method firstly divides point cloud by 3D grid. Then a subcell is determined by a random sample point, in which multi-primitive models are fitted, and the candidate models are got by its local score. Then the global scores are determined by statistic inference. Hence, the best model and its consensus set can be selected, and a segmentation can be made on point cloud. The experimental results show that our method can efficiently segment man-made structures rich in regular geometry shape.

terrestrial laser 3D scanning；segmentation；local sample；statistics inference；normal vector constrain

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

10.13474/j.cnki.11-2246.2017.0038.

2015-12-08；

2016-07-07

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(17B420001)；國(guó)家自然科學(xué)基金(41301429)

石宏斌(1981—)，男，博士，講師，主要從事激光點(diǎn)云數(shù)據(jù)分割、特征提取、自動(dòng)配準(zhǔn)等方面的研究。E-mail：hbshi@whu.edu.cn

P225

A

0494-0911(2017)02-0006-04