張 強(qiáng)，李 朝 奎，李 俊 曉，嚴(yán) 雯 英

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

?

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

張 強(qiáng)，李 朝 奎*，李 俊 曉，嚴(yán) 雯 英

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

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

點(diǎn)云；三角面片；法向量；分割

0 引言

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

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

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

1 改進(jìn)平面點(diǎn)云分割方法原理

1.1 索引建立

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

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

Public class Octree

{

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

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

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

public mTreeNode[] Vertex;//立方體的8個(gè)頂點(diǎn)；

public P3D_struct Midpoint;//立方體的中心點(diǎn)；

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

Public List Pointlist;//立方體包含的點(diǎn)云集合；

};

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

Fig.1 The structure diagram of Octree

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

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

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

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

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

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

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

圖2 三角面片法向量 圖3 三角面片頂點(diǎn)排序 圖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)法矢量估算。本文利用點(diǎn)P與其相鄰點(diǎn)共同構(gòu)建三角面片，則點(diǎn)P的法向量會(huì)受到所有包含頂點(diǎn)P的三角面片的法向量的影響，為了綜合考慮各法矢量對(duì)P點(diǎn)法矢量的貢獻(xiàn)，采取加權(quán)平均各相關(guān)法向量方法對(duì)P點(diǎn)的法向量進(jìn)行估算(圖5)，點(diǎn)P的法向量用np表示，其表達(dá)式如式(1)、式(2)：

(1)

(2)

圖5 單點(diǎn)法向量估算

Fig.5Theestimationofsinglepointnormalvector

1.3 平面點(diǎn)云分割

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

(3)

條件2中，兩個(gè)局部擬合平面間的距離并非這兩個(gè)點(diǎn)間的距離。此處兩個(gè)擬合平面的距離d為：

(4)

圖6 平面點(diǎn)云約束條件

Fig.6Theconstraintconditionsofplanarpointclouds

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

2 實(shí)驗(yàn)與分析

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

圖7 桌面水杯模型實(shí)驗(yàn)效果 圖8 雕塑模型實(shí)驗(yàn)效果

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

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

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

Table 1 Comparison of segmentation experimental results

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

3 結(jié)論

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

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

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

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

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

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

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

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

[8] 張量,王敏.基于K鄰域離散擴(kuò)張的點(diǎn)云數(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] 尹輝增,孫軒,聶振鋼.基于機(jī)載激光點(diǎn)云數(shù)據(jù)的電力線自動(dòng)提取算法[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

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

張強(qiáng)(1989-)，男，碩士研究生，研究方向?yàn)槿S激光點(diǎn)云數(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