方　軍，李朝奎，張新長，張　強，廖孟光，卜　璞

(1. 湖南科技大學(xué)地理空間信息技術(shù)國家地方聯(lián)合工程實驗室，湖南 湘潭 411201；2. 湖南科技大學(xué)地理空間信息湖南省工程實驗室，湖南 湘潭 411201)

?

顧及幾何特征的規(guī)則激光點云分割方法

方軍1,2，李朝奎1,2，張新長1,2，張強1,2，廖孟光1,2，卜璞1,2

(1. 湖南科技大學(xué)地理空間信息技術(shù)國家地方聯(lián)合工程實驗室，湖南 湘潭 411201；2. 湖南科技大學(xué)地理空間信息湖南省工程實驗室，湖南 湘潭 411201)

三維激光掃描儀能快速地獲取三維場景的高精度點云數(shù)據(jù)，已成為快速三維建模的重要工具。點云分割是三維點云模型數(shù)據(jù)預(yù)處理中的首要環(huán)節(jié)，也是影響重建效率與模型質(zhì)量的重要因素。以激光點云的分割為研究切入點，以八叉樹空間劃分方式對數(shù)據(jù)進行組織，并用八進制編碼進行命名，結(jié)合K鄰近搜索法獲取目標(biāo)點的局部鄰近點，采用加權(quán)平均目標(biāo)點相鄰的三角面片法向量來估算單點法向量?；谕队皻W氏距離擬合曲面求取曲率。量化了規(guī)則點云集的分割約束條件，采用法向量信息來進行平面點的提取，根據(jù)曲率在兩個主方向上的差異性來識別和分割柱面和球面信息。試驗結(jié)果表明：①基于法矢量的平面點分割效果理想；②基于曲率差異性的規(guī)則曲面點分割效果較差；③基于幾何特性的規(guī)則激光點分割方法合理可行。

激光點云；空間劃分；鄰近點；點云分割；法矢量；曲率

三維激光掃描技術(shù)以其精度高、采集數(shù)據(jù)速度快、數(shù)據(jù)格式簡單，可操作性強等特點在三維數(shù)字城市建模過程中占有一席之地[1-2]。近年來，激光技術(shù)和通信技術(shù)的研究取得了重要突破，使得三維激光掃描儀得到廣泛應(yīng)用。三維激光掃描儀是根據(jù)紅外線的高速發(fā)射與返回接收來獲得建筑物的特征信息，尤其是其表面的空間信息。觀測對象的表面空間信息是以點的方式表現(xiàn)出來的，點與點之間是分散布局的，彼此之間沒有明顯的空間拓?fù)潢P(guān)系的離散點[3]。因此在其使用過程中，用戶普遍反映出一些問題，如獲取的數(shù)據(jù)規(guī)模太大，后續(xù)的數(shù)據(jù)處理工作量大、繁雜瑣碎等，使得模型建立效率過低。當(dāng)前三維點云建模中出現(xiàn)的問題，可以歸結(jié)為3種主要矛盾：①數(shù)據(jù)量大、手工建模勞動強度大的難題與現(xiàn)狀模型重建的效率和精度要求高之間的矛盾；②分塊建模后幾何模型缺乏拓?fù)潢P(guān)系、幾何特征參數(shù)不能獲取與當(dāng)前要求空間數(shù)據(jù)快速檢索與處理之間的矛盾；③不能對象化及規(guī)則化描述精細(xì)三維模型，紋理信息不全且計算復(fù)雜與當(dāng)前建立高逼真性、高精細(xì)化模型之間的矛盾。

針對點云數(shù)據(jù)離散、無直接拓?fù)潢P(guān)系的特點，目前的三維激光后數(shù)據(jù)處理軟件主要包含以下的處理功能[4]：初始數(shù)據(jù)的濾波除噪，多測站數(shù)據(jù)的融合與配準(zhǔn)，三維數(shù)據(jù)的特征分割與提取，三維點云面片的重建與顯示。由于復(fù)雜、不規(guī)則物體的掃描數(shù)據(jù)往往更加難以用統(tǒng)一的數(shù)學(xué)公式和計算機語言對其進行描述和表達(dá)，造成現(xiàn)在的數(shù)據(jù)分割主要通過人工或半人工方式得以完成，工作量龐大、耗時且效率低下[5]。針對三維數(shù)據(jù)處理與三維重建中存在的問題，選擇三維數(shù)據(jù)分割作為研究切入點，通過建立有效的點云分割方法，根據(jù)鄰近點擬合成目標(biāo)表面所體現(xiàn)出的目標(biāo)點的幾何特征，將大量的點云數(shù)據(jù)分割成不同類型的點的集合，采用聚類的方法完成點云聚類，再根據(jù)不同類型數(shù)據(jù)的特征，運用相應(yīng)的數(shù)學(xué)模型對點集進行三維重建。該方法有助于解決海量點云數(shù)據(jù)的存儲管理及點云數(shù)據(jù)的高效分割難題，進而為點云數(shù)據(jù)的三維重建奠定基礎(chǔ)。

一、空間數(shù)據(jù)劃分方法

1. 八叉樹空間劃分

空間八叉樹(Octree)劃分方法是平面四叉樹方法在維度上的一個升級，目的是為了達(dá)到將復(fù)雜三維物體簡化的目的。如圖1所示，取一個立方體空間，將其在6個面的垂直中分面處進行空間8等分，得到了8個空間結(jié)構(gòu)一致的子立方體，稱為8個體元[6-7]。依此類推，直至子節(jié)點符合劃分條件后不再對其進行劃分。在遞歸式的八叉樹空間劃分過程中，要判斷每個級別中的子立方體中所包含的三維空間點的數(shù)量，如果數(shù)量為零，則該子立方體的空間劃分到此結(jié)束，如果其數(shù)量不為零，則繼續(xù)執(zhí)行空間劃分，直至滿足應(yīng)用需求。

圖1　八叉樹空間結(jié)構(gòu)

八叉樹空間劃分方法思路清晰，結(jié)構(gòu)簡單，在點云數(shù)據(jù)處理中有兩個主要優(yōu)勢：

1) 八叉樹空間劃分的存儲方式使得數(shù)據(jù)按空間分開存儲，提高了數(shù)據(jù)在調(diào)用時的效率，降低了內(nèi)存的使用率。

2) 八叉樹空間劃分完成后，葉節(jié)點的訪問及修改成本低。

2. 八叉樹分割流程

結(jié)合八叉樹空間劃分的思想和空間劃分的終止條件(如圖2所示)，將八叉樹的劃分算法歸結(jié)如下：

1) 遍歷整個點云集，查出點的坐標(biāo)值在3個正交軸向上均為最大和最小的點，記作(xmax，ymax，zmax)和(xmin，ymin，zmin)。根據(jù)該點云集的空間跨度，選擇合適的微分量ρ，以上一步中的兩點的坐標(biāo)值為參照，對八叉樹空間的邊界進行微調(diào)，得出八叉樹空間最終邊界值(xm，ym，zm)和(xn，yn，zn)，根據(jù)邊界坐標(biāo)構(gòu)建點云的最小空間體。

2) 對八叉樹的根節(jié)點立方體進行首次八叉樹結(jié)構(gòu)劃分，并依據(jù)上文所提及的空間編碼方法和編碼順序?qū)Φ贸龅?個空間子立方體進行八進制編碼。并將各子立方體空間所包含的點云數(shù)據(jù)存儲到其八進制編碼所對應(yīng)的集合中，建立空間點與子立方體的對應(yīng)關(guān)系。

3) 選取合適的子立方體包含點數(shù)閾值γ，對上一步中的8個子立方體進行判斷，如果子立方體中點的數(shù)量大于閾值γ，則將該子立方體當(dāng)作根節(jié)點返回至步驟2)進行第2級的劃分，否則進行下一步。

4) 判斷子立方體中點的數(shù)量，如果數(shù)量不為零，則確定子立方體編碼與其內(nèi)部點集的對應(yīng)關(guān)系；如果數(shù)量為零，則該空間子立方體為冗余空間，空間不保存。

5) 反復(fù)迭代執(zhí)行步驟3)和4)，直至所有子立方體滿足劃分要求，那么點云的八叉樹索引基本建立。

圖2　八叉樹網(wǎng)格劃分流程

3. 八叉樹分割終止條件

現(xiàn)階段主要形成兩類分割終止的依據(jù)[8]：一種是根據(jù)分割后子立方體的空間大小進行判斷，即判斷子節(jié)點立方體的體積或各邊的長度，如果分割后子立方體的體積小于預(yù)先設(shè)定的閾值，或邊長小于一定的閾值，則停止劃分，否則繼續(xù)進行迭代分割，直至該判斷條件成立，八叉樹空間劃分得以完成；另一種方法是針對點云數(shù)據(jù)的空間劃分而言，即基于子立方體中包含的點云數(shù)量的方法，以子節(jié)點中點的數(shù)量為判斷依據(jù)，決定該子節(jié)點是否進行下一級別的劃分。圖3是劃分終止條件示意圖。

圖3　空間劃分終止條件

判斷條件γ閾值的取值顯得尤為重要，根據(jù)以往試驗結(jié)果得知，如果γ閾值的取值太大，則分割沒有到最優(yōu)化，沒有完美的體現(xiàn)八叉樹劃分的高效存儲管理優(yōu)勢；如果γ閾值的取值過小，則必然使得空間八叉樹產(chǎn)生的級別過深，同樣影響索引速度，導(dǎo)致點云數(shù)據(jù)支離破碎，破壞其連貫性。γ閾值的取值受點云密度的影響，同時也跟八叉樹劃分的深度有一定的關(guān)系。

二、點云幾何特征量解算

1. 加權(quán)平均法求取法矢量

離散點云的法矢量是點在空間分布的重要特征，因此估算點的法向量成為點云分割過程中的一個重要環(huán)節(jié)。一些學(xué)者采用各種擬合算法，將P點鄰域中的K個鄰近點擬合成一個平面或曲面，并將曲面該點處的法向量或曲率作為該點法矢量信息的估算值；也有些學(xué)者利用最小二乘法將相鄰點局部進行平面擬合，得到P點的一個微分切平面，由此切平面得到該點的法向量估算值。如圖4—圖7所示，以上方法所得出的點的法線方向具有任意性，有些指向曲面內(nèi)側(cè)，有些指向外側(cè)，對后續(xù)的法矢量的計算應(yīng)用產(chǎn)生影響[9]。本文改進一種方法，通過三角網(wǎng)格頂點排序的方法將法線方向歸一化，然后通過加權(quán)平均方法來估算單點的法向量。

圖4　三角面片法向量

圖5　三角面片頂點排序

圖6　調(diào)整后的三角面片法向量

2. 基于歐氏距離的局部二次曲面

局部地區(qū)點云的二次參數(shù)曲面表達(dá)形式如下

(1)

為了便于數(shù)學(xué)算法的表達(dá)與運算，將其轉(zhuǎn)為矩陣表達(dá)式

圖7　單點法向量估算

(2)

已知目標(biāo)點P及其局部逼近的K個鄰近點坐標(biāo)(xi，yi，zi)，0

(3)

根據(jù)以上公式，方程r(u，v)的分量即可表示為

x=WTa，y=WTb，z=WTc

(4)

為了擬合出微分曲面S，對目標(biāo)點P及其鄰近點進行插值，使得已知坐標(biāo)的K+1個點到該擬合曲面的歐氏距離的絕對值E取得最小值，數(shù)學(xué)表達(dá)方式如下

E=Z-MQ

(5)

(6)

根據(jù)最小二乘原理的思想，可將式(6)表達(dá)的空間距離取平方值，使得這K+1個點到擬合曲面S的歐氏距離的平方和最小，此時，得到基于歐氏距離最優(yōu)的曲面表達(dá)式(如圖8所示)。

圖8　歐氏距離示意圖

該方法是將目標(biāo)點P及其鄰近的總共K+1個點分別投影到曲面S上，也就是計算這些點到曲面S的歐氏距離，然后將投影線段長度求平方和，根據(jù)最小二乘法求平方和的最小值，取得最佳的曲面系數(shù)，即為基于歐氏距離的局部最優(yōu)二次曲面。

三、特征點云的分割

1. 建立規(guī)則點云的約束條件

(1) 平面點云分割約束條件

平面點云分割約束條件為

(7)

1) 平面點云數(shù)據(jù)集中的點的法矢量應(yīng)該具有一致的指向，考慮到系統(tǒng)誤差及外界因素的影響，任何點與點之間法矢量的指向之間的夾角應(yīng)該不超過一定的閾值。

2) 平面點云數(shù)據(jù)集中的所有點應(yīng)該處在同一個平面模型中，并且一個點云集中點與其相鄰點之間的距離不能超過一定的閾值。

3) 平面點的曲率理論值(Gauss曲率和平均曲率)等于零，在實際點云數(shù)據(jù)中應(yīng)該趨近于零。

(2) 圓柱面點云分割約束條件

圓柱面點云分割的約束條件式如下

(8)

由圓柱體的空間數(shù)學(xué)模型表達(dá)式(8)，反推圓柱面點云的特征，得出如下結(jié)論：

1) 圓柱體側(cè)表面點云的法矢量指向在空間上垂直于圓柱體的中心線，將一個圓柱體側(cè)面的法矢量平移到同一個起點時，它的法向量會形成一個以平移到的點為圓心，以法向量的單位長度為半徑的單位圓。

2) 圓柱體側(cè)表面點云的曲率值為常數(shù)。其Gauss曲率值等于零，最大主曲率值為圓柱體的半徑的倒數(shù)，是一個常數(shù)，最小主曲率值為零。

(3) 球面點云分割約束條件

球面點云的分割約束條件如下

(9)

由式(9)反推球面點云數(shù)據(jù)的特征，得出如下結(jié)論：

1) 球體表面的點云的法矢量在空間指向上都經(jīng)過同一個點，將球體表面所有點的法矢量都平移到球體球心處，它的法矢量會形成一個以法矢起點為球心，以法矢量長度為半徑的單位球體。

2) 球面點云數(shù)據(jù)的曲率值為一個常數(shù)。其最大主曲率值等于最小主曲率值，且該常數(shù)等于該球體模型的半徑的倒數(shù)。

2. 基于法矢量信息的平面點的識別與分割

經(jīng)過基于鄰近三角面片法矢量方向調(diào)整后的加權(quán)平均，得到了三維點的法向量，根據(jù)法向量特性，可以設(shè)置一定的限制條件來對平面點云進行分割。如圖9所示，由平面的基本特征可知，平面點云必須滿足以下兩個條件：

1) 散亂點的法向量指向必須一致或在角度差一定的閾值區(qū)間內(nèi)，即同向性。

2) 散亂點的局部擬合平面之間距離必須小于一定的閾值，即共面性。

圖9　平面點云約束條件

3. 球面與柱面點的識別與分割

離散點的單個特征往往不足以用來區(qū)分一類曲面點云，需要將多方面的信息相結(jié)合來歸納曲面的特征。三維點云的曲率信息主要包含某點的最大主曲率、最小主曲率及高斯曲率。曲率的計算，采用基于歐氏距離擬合曲面方法進行。

結(jié)合球面與圓柱面點云的曲率特征，采用合理的識別與分割條件，將兩類曲面分割步驟總結(jié)如下：

1) 由空間八叉樹劃分構(gòu)建索引，并獲取種子點的K個鄰近點坐標(biāo)。

2) 采用局部二次曲面的參數(shù)方程式來表示該K+1個點所表達(dá)的空間曲面，根據(jù)基于歐氏距離擬合的判斷條件，將方程轉(zhuǎn)變成K+1個點到曲面歐氏距離的平方和最小的誤差方程，利用最小二乘原理，K+1個坐標(biāo)點為已知條件，來進行平差計算，得到最優(yōu)的擬合曲面方程式，并解算各種曲率值。

3) 統(tǒng)計分析點云數(shù)據(jù)的最大主曲率、最小主曲率及高斯曲率值，采用K均值聚類的方式，選定一個合適的種子點，對K個鄰近點進行均值聚類分析，將曲率特征一致的點匯集到屬性一致的集合中，反復(fù)執(zhí)行聚類操作，直至劃分結(jié)束(見表1)。

表1　兩種規(guī)則曲面的曲率特征

四、試　驗

1. 點云空間劃分試驗

采用徠卡地基激光掃描儀，獲取某工廠車間的點云數(shù)據(jù)，對其進行空間八叉樹結(jié)構(gòu)劃分，形成的空間網(wǎng)格結(jié)構(gòu)如圖10所示。根據(jù)空間八叉樹網(wǎng)格結(jié)構(gòu)劃分算法流程，設(shè)定空間劃分的終止閾值為50，然后將立方體內(nèi)點云數(shù)量為空的網(wǎng)格刪除掉，得到最精簡的八叉樹空間結(jié)構(gòu)(如圖11所示)。

圖10　工廠車間點云的八叉樹空間劃分

采集校圖書館部分點云數(shù)據(jù)，進行空間劃分試驗，試驗結(jié)果如圖11所示。

圖11　圖書館點云的八叉樹空間劃分

2. 規(guī)則點云分割試驗

根據(jù)上述理論方法，采用相關(guān)數(shù)據(jù)進行試驗，檢驗規(guī)則點云分割方法的可行性和試驗效果。采用徠卡 Scanstation 2型激光掃描設(shè)備分別獲取某個工廠車間的點云和某圖書館建筑的部分?jǐn)?shù)據(jù)來進行試驗。采用PointCloud軟件對其進行數(shù)據(jù)處理，分別進行法矢量提取、規(guī)則點集分割與提取等處理，處理效果如圖12—圖16所示。

圖12　點云法矢量

圖13　工廠車間規(guī)則點集的分割和提取

圖14　工廠車間規(guī)則點云提取后效果

圖15　圖書館規(guī)則點集的點云的分割和提取

圖16　圖書館規(guī)則點集提取后效果

對兩組數(shù)據(jù)分割后的不同類型面片進行統(tǒng)計，找出各類型數(shù)據(jù)中識別出的點云集數(shù)量，并逐一進行人工對比判斷，統(tǒng)計分割出現(xiàn)錯誤的點集，結(jié)果見表2，相應(yīng)對象的點云分割正確率曲線如圖17所示。

表2　兩個點云分割結(jié)果對比

圖17　不同類型點云分割正確率檢驗

對不同類型數(shù)據(jù)的分割結(jié)果進行分析可知，平面點云的分割效果較好，圓柱面和球面兩種曲面點云的分割效果較差。縱向?qū)Ρ瓤梢园l(fā)現(xiàn)，圖書館數(shù)據(jù)的分割結(jié)果普遍比較差，這與數(shù)據(jù)的質(zhì)量有關(guān)。圖書館數(shù)據(jù)采集中，由于其建筑結(jié)構(gòu)復(fù)雜，激光掃描設(shè)備架站，以及外界人流與地物干擾等使得數(shù)據(jù)質(zhì)量不高，而工廠車間數(shù)據(jù)較為規(guī)則、理想，結(jié)構(gòu)簡單。

五、結(jié)　論

以三維點云數(shù)據(jù)的分割為切入點，研究基于典型幾何特征的激光點云分割方法，并進行了相應(yīng)的試驗。得到如下研究結(jié)論：

1) 研究了三維激光離散型點云數(shù)據(jù)的空間索引方法，針對激光點云數(shù)據(jù)的離散性、空間無拓?fù)?、呈表面分布等特征，借鑒八叉樹空間網(wǎng)格劃分的形式，根據(jù)點云的密度選取合適的分割終止條件，將離散型數(shù)據(jù)有序組織可以有效提高數(shù)據(jù)的查找與調(diào)用，并用八進制數(shù)的編碼對立方網(wǎng)格命名。利用八叉樹的索引，對點云進行鄰近值搜索，便于局部點云特征計算。

2) 采用加權(quán)平均的方法求解法矢量，該方法所估算的頂點法矢量精度可以滿足要求，可以作為平面點云分割的法矢量依據(jù)，以局部點到擬合曲面的歐氏距離平方和最小為擬合條件，平差得出的曲面最能反映局部的曲面形狀，所得出的曲率值效果最好。

3) 針對常見的幾種面片形式，提出了基于幾何特征的不同類型點云識別與分割的約束條件。以徠卡Scanstation 2型掃描儀獲取的點云數(shù)據(jù)為試驗對象，證明了法矢量和曲率信息在數(shù)據(jù)分割中的重要性。

[1]詹慶明,周新剛,肖映輝, 等.從激光點云中提取古建筑線性和圓形特征的比較[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2011，31(6):674-677，682.

[2]魏征,楊必勝,李清泉.車載激光掃描點云中建筑物邊界的快速提取[J].遙感學(xué)報，2012，16(2):286-296.

[3]李必軍,方志祥,任娟.從激光掃描數(shù)據(jù)中進行建筑物特征提取研究[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2003，28(1):65-70.

[4]鄧非,張祖勛,張劍清.利用激光掃描和數(shù)碼相機進行古建筑三維重建研究[J].測繪科學(xué)，2007,32(2):29-30.

[5]莫堃,尹周平.基于3D活動輪廓模型的缺陷點云分割方法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2011，39(1):82-85.

[6]李清泉,李德仁.八叉樹的三維行程編碼[J].武漢測繪科技大學(xué)學(xué)報，1997，22(2):12-16.

[7]權(quán)毓舒,何明一.基于三維點云數(shù)據(jù)的線性八叉樹編碼壓縮算法[J].計算機應(yīng)用研究，2005(8):70-71，129.

[8]楊客,張志毅,董艷.基于自適應(yīng)八叉樹分割點云的表面模型重建[J].計算機應(yīng)用與軟件，2013，30(6):83-87.

[9]姜壽山,Eberhard P.多邊形和多面體頂點法矢的數(shù)值估計[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2002，14(8):763-767.

[10]張量,王敏.基于k鄰域離散擴張的點云數(shù)據(jù)分割[J].軟件導(dǎo)刊，2009，8(12):7-9.

The Segmentation of Regular Laser Point Cloud Based on Geometry Feature

FANG Jun，LI Chaokui，ZHANG Xinchang，ZHANG Qiang，LIAO Mengguang，BU Pu

2015-10-29；

2016-06-24

國家自然科學(xué)基金(41271390；41571374)；國土資源部公益性行業(yè)科研專項(201511079-04)；空間信息智能感知與服務(wù)深圳市重點實驗室開放基金資助(2015C11508)；特殊環(huán)境道路工程湖南省重點實驗室開放基金(kfj150502)

方軍(1985—)，男，博士，研究方向為遙感信息提取與三維GIS應(yīng)用。

李朝奎。E-mail：616059644@qq.com

P208

B

0494-0911(2016)08-0047-06

引文格式：方軍，李朝奎，張新長，等.顧及幾何特征的規(guī)則激光點云分割方法[J].測繪通報，2016(8)：47-52.DOI:10.13474/j.cnki.11-2246.2016.0254.