一種改進的基于法矢方向調(diào)整的平面點云分割方法

張 強，李 朝 奎，李 俊 曉，嚴 雯 英

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

?

一種改進的基于法矢方向調(diào)整的平面點云分割方法

張 強，李 朝 奎*，李 俊 曉，嚴 雯 英

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

智慧城市的蓬勃發(fā)展和快速推廣，使得三維建模成為當(dāng)前熱點研究方向。平面點云分割是三維點云建模中數(shù)據(jù)處理的關(guān)鍵環(huán)節(jié)。該文提出一種三角面片法向量方向調(diào)整方法，通過后續(xù)對鄰近法向量進行加權(quán)平均估算實現(xiàn)平面點云的分割。首先采用八叉樹的空間劃分方法將無序的點云建立索引，利用K緊鄰搜索獲取參考點的K個鄰近點，然后將該局部點構(gòu)建不規(guī)則三角網(wǎng)并且得到包含參考點的所有三角面片以及三角面片的法向量，并通過將三維點投影到二維平面，利用平面三角形兩邊向量叉乘的方法，判斷并調(diào)整各三角面片的頂點排列順序，使三角面片的法向量一致化，最后對包含參考點的所有三角面片的法向量加權(quán)平均，估算參考點的法向量，根據(jù)點云法矢一致、共面的原則將平面點云分割出來。以徠卡Scanstation 2 型掃描儀獲取點云數(shù)據(jù)，對該方法進行檢驗，結(jié)果顯示其能較好地實現(xiàn)對點云法矢量方向的調(diào)整與估算，并對平面點云數(shù)據(jù)進行分割提取。

點云；三角面片；法向量；分割

0 引言

隨著激光掃描技術(shù)的不斷升級，三維激光掃描儀能夠快速、方便地獲取目標(biāo)物的高精度點云數(shù)據(jù)，利用點云數(shù)據(jù)建模即可得到相應(yīng)的三維模型，該技術(shù)方法已滲透到智慧城市建設(shè)、機械制造、逆向工程等多個行業(yè)[1]。鑒于點云數(shù)據(jù)格式簡單，方便存儲，并且能夠突出復(fù)雜物體的細節(jié)部分，點云模型的應(yīng)用備受關(guān)注，點云轉(zhuǎn)變成模型的處理過程已成為當(dāng)前研究的重點[2]。由于激光點云散亂無章、曲面性質(zhì)異同[3]，對海量的點云數(shù)據(jù)統(tǒng)一建模處理會加大算法的難度和數(shù)學(xué)表示的復(fù)雜性，因此首先要對點云進行分割分類，區(qū)分對待處理。

當(dāng)前實用的點云分割方法主要有[4]：1)基于邊緣檢測的分割通過檢測算法查找特征產(chǎn)生差異的分界點，然后將其連接成為一個曲面，該方法提取邊界效果較好，但點云曲率或法矢量對雜點敏感度高，提取輪廓容易斷裂；2)基于區(qū)域生長的分割將點云幾何特性一致的相鄰空間點劃定為一個集合，可以有效地克服噪聲的影響，但其邊界點識別差，不夠準(zhǔn)確；3)基于激光反射特性差異的分割。

本文采用八叉樹的空間劃分方法將無序的點云建立索引，利用K緊鄰搜索獲取參考點P的K個鄰近點，將k+1個點構(gòu)建不規(guī)則三角網(wǎng)并得到包含參考點P的所有三角面片及三角面片法向量，并通過調(diào)整三角面片的頂點排列順序，使三角面片法向量一致化，通過對相鄰面片的法向量加權(quán)平均的方法估算參考點法向量，最后根據(jù)點云法矢一致、共面的原則將平面點云分割出來。該方法對點的法矢量能夠較為準(zhǔn)確地進行調(diào)整和估算，有效提取平面點云。

1 改進平面點云分割方法原理

1.1 索引建立

三維激光掃描儀所獲取的點云數(shù)據(jù)是一系列散亂、無序的空間點，點與點之間沒有直接的拓撲關(guān)系[5]，要對大量的點對象進行處理會大大影響其效率，因此必須對點云建立一個空間索引，加強空間關(guān)聯(lián)性。本文主要利用八叉樹空間網(wǎng)格方法劃分點云空間[6]，從而快速提取離散點的K鄰域。

1.1.1 八叉樹網(wǎng)格結(jié)構(gòu) 在空間數(shù)據(jù)處理中，八叉樹格網(wǎng)結(jié)構(gòu)是一種高效的存儲管理方法。其基本構(gòu)建思想：首先遍歷三維點云數(shù)據(jù)，獲得點集中空間上3個正交方向的最大值和最小值，即Xmax、Xmin、Ymax、Ymin、Zmax、Zmin，從而構(gòu)建點云集的最小外包圍立方體，作為該八叉樹結(jié)構(gòu)模型的根節(jié)點并建立編碼，然后將立方體沿正交方向均勻分割，得到大小一致的8個子立方體并建立下一級編碼(圖1)。同理，分別對8個子立方體進行空間劃分，直至子立方體對象不滿足劃分要求則停止分割，否則繼續(xù)對子立方體進行劃分，直到所有的子立方體都符合最小的空間劃分閾值。基于后續(xù)處理對索引的需求，建立八叉樹格網(wǎng)的結(jié)構(gòu)體如下：

Public class Octree

{

public string RootNode;//父節(jié)點索引；

public string [] LeafNode;//子節(jié)點索引；

public string ID;//立方體所在的編碼;

public mTreeNode[] Vertex;//立方體的8個頂點；

public P3D_struct Midpoint;//立方體的中心點；

public P3D_struct NearMid;//所含的點云中距離立方體距離中心點的最近點；

Public List Pointlist;//立方體包含的點云集合；

};

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

Fig.1 The structure diagram of Octree

本文選擇子立方體中包含的點數(shù)量γ閾值作為劃分條件：1)對子立方體空間包含點數(shù)量γ與γ閾值進行比較；2)當(dāng)子立方體空間包含點γ≤γ閾值時，則停止對該子立方體的空間劃分，并對劃分結(jié)果進行存儲；3)當(dāng)子立方體空間包含點γ>γ閾值時，則繼續(xù)對該子立方體進行空間劃分，成為下一級子立方體，然后重復(fù)步驟1-3，直到所有子立方體都滿足要求且存儲完成。

1.1.2 K鄰近點的搜索 空間上點與點之間是不連續(xù)的，無法體現(xiàn)空間幾何特性[7]，需要結(jié)合鄰近點反映其特征。常用的方法就是尋找該點在空間上與其距離最近的K個點，即K鄰近點搜索[8]。具體搜索步驟如下：首先利用上文所建立的八叉樹網(wǎng)格結(jié)構(gòu)，根據(jù)目標(biāo)點P的三維坐標(biāo)值，反求出其所在子立方體的編碼M(x,y,z)，然后找到子立方體空間上與其相鄰的26個子立方體編碼M(x±1,y±1,z±1)，并將編碼為M(x,y,z)和M(x±1,y±1,z±1)的27個子立方體作為目標(biāo)點P的鄰近點的搜索范圍，最后根據(jù)到P點的空間距離，對搜索范圍內(nèi)所有鄰近點進行排序，取出距P點最近的K個點，存儲到K鄰近數(shù)組中。如果在P點的27個立方體搜索范圍中，點的數(shù)量少于K個，則需要將P點的鄰近立方體擴大一層至125個子立方體，直到能夠找到其鄰近的K點。

1.2 法線方向調(diào)整和估算

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

(1)將參考點P與其K相鄰點建立Delaunay三角網(wǎng)，篩選全部包含參考點P為頂點的三角面片，并存儲三角面片頂點。

(2)計算各三角面片的法向量。由于三角形頂點排序無規(guī)則，所求出法線的指向也不一致，一些法線方向指向外側(cè)，一些指向內(nèi)側(cè)(圖2)，這樣無法對相關(guān)法線進行準(zhǔn)確估算，需調(diào)整法向量方向。

(3)三角面片頂點排序。首先將三維空間的點投影到X-Y平面，將二維三角面片的兩個邊向量叉乘，根據(jù)邊向量叉乘結(jié)果調(diào)整三角面片頂點的順序，將三角面片的頂點按照逆時針方式排列存儲。如圖3所示：包含頂點P的三角形ABP，其存儲的頂點順序為A、B、P(或B、P、A或P、A、B)。通過規(guī)范三角面片頂點順序，將三角面片的法向量指向一致化：指向外側(cè)(或內(nèi)側(cè))，結(jié)果如圖4所示。

圖2 三角面片法向量 圖3 三角面片頂點排序 圖4 調(diào)整后的三角面片法向量

Fig.2 The normal vector of triangular patch Fig.3 The sequence of triangle vertex Fig.4 The normal vector of triangle after adjustment

(4)法矢量估算。本文利用點P與其相鄰點共同構(gòu)建三角面片，則點P的法向量會受到所有包含頂點P的三角面片的法向量的影響，為了綜合考慮各法矢量對P點法矢量的貢獻，采取加權(quán)平均各相關(guān)法向量方法對P點的法向量進行估算(圖5)，點P的法向量用np表示，其表達式如式(1)、式(2)：

(1)

(2)

圖5 單點法向量估算

Fig.5Theestimationofsinglepointnormalvector

1.3 平面點云分割

經(jīng)過加權(quán)平均，得到了三維點的法向量，根據(jù)法向量特性，可以設(shè)置一定的限制條件對平面點云進行分割。由平面的基本特征可知，平面點云必須滿足兩個條件：1)散亂點的法向量指向必須一致或夾角小于一定的閾值，即同向性；2)散亂點的局部擬合平面之間距離必須小于一定的閾值，即共面性。

(3)

條件2中，兩個局部擬合平面間的距離并非這兩個點間的距離。此處兩個擬合平面的距離d為：

(4)

圖6 平面點云約束條件

Fig.6Theconstraintconditionsofplanarpointclouds

根據(jù)以上分析，本文采取的平面點云分割算法流程如下：1)建立點云索引，得出第i個點的K鄰域。2)將第i個點與其K鄰近點構(gòu)建不規(guī)則三角網(wǎng)，查找并存儲包含i點為頂點的N個三角面片，并得出三角面片的法向量。3)將這N個三角面片從三維空間投影到X-Y平面，然后根據(jù)三角面片其中兩邊的叉乘值，判斷三角面片的頂點排序，如果滿足逆時針排序，則不做調(diào)整，否則，將其調(diào)整為逆時針排序，重新計算該面片的法向量。經(jīng)過該步驟，三角面片法向量指向一致。4)利用式(1)、式(2)，計算第i個點法向量。5)重復(fù)步驟1-4，直到所有點的法向量計算完畢。6)根據(jù)平面點云分割條件同向性、共面性，對點云進行分割，提取出平面點云得到最后結(jié)果。

2 實驗與分析

利用徠卡Scanstation2型激光掃描儀獲取實驗點云數(shù)據(jù)，桌面水杯模型和雕塑模型都包含有平面點數(shù)據(jù)和非平面點噪聲數(shù)據(jù)。通過不斷調(diào)整閾值進行實驗，取閾值數(shù)據(jù)γ閾值=10，向量夾角α=0.12，面片距離d=0.8時分割效果比較理想。從圖7和圖8可以看出：平面點云已經(jīng)被分割出來，但平面上明顯比原數(shù)據(jù)多出一些空斑點，這是由于局部地區(qū)點云并不平坦，而被作為噪聲點排除在外。

圖7 桌面水杯模型實驗效果 圖8 雕塑模型實驗效果

Fig.7 The experimental results of cup model Fig.8 The experimental result of statue model

法矢分割方法將原始數(shù)據(jù)分割成平面點云數(shù)據(jù)集，通過與人工判斷分割的結(jié)果進行對比，定量呈現(xiàn)其分割效果。從表1的實驗數(shù)據(jù)看，兩個模型中被分割出的平面點數(shù)據(jù)與人工分割的平面數(shù)據(jù)比較接近，分割合格率分別達到96.32%和96.49%。實驗表明：本文方法能夠很好地對點的法矢量進行調(diào)整和估算，將平面點與非平面點進行分離，從而保障了以后對平面模型的重建效率。

表1 法矢分割與人工判斷結(jié)果比較

Table 1 Comparison of segmentation experimental results

數(shù)據(jù)分割方法實驗數(shù)據(jù)點數(shù)(個)分割后平面點數(shù)(個)剔除的非平面點數(shù)(個)分割合格率(%)桌面水杯模型雕塑模型法矢方法13954811613423414人工判斷13954812056718981法矢方法1652369889535人工判斷1652372429281 96．3296．49

3 結(jié)論

本文將局部鄰近點格網(wǎng)化，通過調(diào)整三角面片頂點將法向量指向一致化，通過加權(quán)平均相鄰三角面片的法矢量，估算出單點的法向量，最后根據(jù)平面點云的同向性和共面性分割提取平面點云數(shù)據(jù)。通過三角面片頂點排序、法向量指向的調(diào)整，估算點的法向量，取得了很好的效果；加權(quán)平均相鄰三角面片的法向量，估算出單點法矢量的精度符合其幾何特征的表達；改進的方法能夠較好地對點法矢量進行估算，并對平面點云進行分割提取，為以后點云數(shù)據(jù)的精細化分割奠定一定的基礎(chǔ)。

[1] 丁延輝,邱冬煒,王鳳利,等.基于地面三維激光掃描數(shù)據(jù)的建筑物三維模型重建[J].測繪通報，2010(3):55-57.

[2] 張會霞,陳宜金,劉國波.基于三維激光掃描儀的校園建筑物建模研究[J].測繪工程,2010,19(1):32-34.

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

[4] 呂德亮.散亂點云分割及特征面片識別研究[D].北京：北京建筑工程學(xué)院；2012.

[5] 王飛，趙季中,傅梁.采用局部凸性和八叉樹的點云分割算法[J].西安交通大學(xué)學(xué)報,2012(10):60-65.

[6] 吳杭彬,李楠,劉春,等.機載激光掃描數(shù)據(jù)分割的三維數(shù)學(xué)形態(tài)學(xué)模型[J].遙感學(xué)報，2011(6):1189-1201.

[7] 周煜,張萬兵,杜發(fā)榮,等.散亂點云數(shù)據(jù)的曲率精簡算法[J].北京理工大學(xué)學(xué)報，2010,30(7):785-789.

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

[9] 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.

[10] 尹輝增,孫軒,聶振鋼.基于機載激光點云數(shù)據(jù)的電力線自動提取算法[J].地理與地理信息科學(xué)，2012,28(2):31-34.

Planar Point Cloud Segmentation Based on the Weighted Average of Adjusted Normal Vector

ZHANG Qiang， LI Chao-kui， LI Jun-xiao，YAN Wen-ying

(NationalandLocalJointEngineeringLaboratoryofGeospatialInformationTechnology,HunanUniversityofScienceandTechnology,Xiangtan411201；HunanProvinceEngineeringLaboratoryofGeospatialInformation，HunanUniversityofScienceandTechnology,Xiangtan411201,China)

With the vigorous development and rapid promotion of wisdom city,3D modeling is becoming the current hot research direction.Planar point cloud segmentation is the key part of three-dimensional point cloud modeling.In this paper,a kind of adjustment method is put forward in the normal vector direction of triangles,then weighted average of the adjacent normal vector is done to realize the plane segmentation of point cloud.Firstly,using Octree space division method to establish an index for the scattered point cloud,using K neighboring algorithm to obtainKneighboring points,then triangular irregular network is established,then to project the 3D point on a two-dimensional plane,according to the product of two edge vectors of triangles,the triangle vertex order is adjusted to make the normal vector point to the same side,and the weighted average of adjusted normal vector is used to estimate the normal vector of a point,finally the planar point is extracted based on the consistence in direction and coplanar condition.Taking the point cloud obtained by Scanstation 2 scanner as an example,the result shows that this method can realize the plane segmentation of point cloud data.

point cloud；triangular patch；normal vector；segmentation

2014-06-26；

2014-09-02

國家自然科學(xué)基金項目(41271390)；湖南省研究生科研創(chuàng)新項目基金(CX2013B405)；湖南科技大學(xué)研究生創(chuàng)新基金項目(S130034)

張強(1989-)，男，碩士研究生，研究方向為三維激光點云數(shù)據(jù)處理。*通訊作者E-mail:chkl_hn@163.com

10.3969/j.issn.1672-0504.2015.01.010

P208

A

1672-0504(2015)01-0045-04