直接精簡密集點云的三角網(wǎng)格重建

董天琪　張志毅

(西北農(nóng)林科技大學信息工程學院　陜西 楊凌 712100)

?

直接精簡密集點云的三角網(wǎng)格重建

董天琪張志毅*

(西北農(nóng)林科技大學信息工程學院陜西 楊凌 712100)

摘要為解決快速傳輸需求，從稠密點云直接生成精簡的三角網(wǎng)格模型，提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元的三角網(wǎng)格重建過程。首先以各點無差異的宏觀估測方法獲得立體柵格的邊長，將點云數(shù)據(jù)分割為柵格單元。然后選取基本單元中數(shù)據(jù)點為種子點，設定三角形邊長以近似正6鄰域為約束，構建初始三角網(wǎng)格，再逐層外擴完成三角網(wǎng)格重建。該方法的優(yōu)點在于可將簡化和重建過程融為一體。實驗結果表明所提方法速度較快，魯棒性較好。

關鍵詞精簡密集點云網(wǎng)格重建外擴

0引言

點云數(shù)據(jù)是對現(xiàn)實世界物體形狀最自然的表示方法之一，但是它不能表示物體的拓撲信息。近些年來已經(jīng)有多種成熟的測量設備能夠高速獲取現(xiàn)實場景的三維點云數(shù)據(jù)。表面重建是從點云重構出忠實于原始曲面的三角形網(wǎng)格過程。其在逆向工程、數(shù)據(jù)可視化、機器視覺、虛擬現(xiàn)實、醫(yī)療技術等領域中都具有廣泛的應用。文獻[1]回顧了國內(nèi)外的研究現(xiàn)狀及商業(yè)軟件開發(fā)情況，對目前逆向工程研究與應用存在的問題及解決的對策提出了討論。目前也出現(xiàn)了文獻[2]這種針對性較強的研究成果。散亂點云曲面重建的關鍵在于拓撲結構的正確建立，而由于數(shù)據(jù)信息的不完整性，這也成為曲面重建的難點所在。根據(jù)現(xiàn)有算法的特點，可以將它們分為以下幾類：隱式曲面算法、參數(shù)曲面算法、基于學習的方法、Delaunay三角剖分算法等。隱曲面方法[3]重建效果良好，但模型較難選定。Delaunay方法研究成果眾多，文獻[4,5]中的Crust方法最為廣泛。Cocone方法[6]也是備受關注的方法之一。Crust方法較為復雜，而Cocone方法則需要針對不同點云數(shù)據(jù)進行相應的方法的變化。對于大規(guī)模的數(shù)據(jù)來講，Delaunay方法重建速度慢。文獻[7]提出一種基于Delaunay三角化區(qū)域增長式的曲面重建方法。較以往方法具有人為參與更少、適用范圍更廣的優(yōu)點，但算法效率有待提高。外擴方法容易理解和實現(xiàn)，但將三角形添加進已三角化的區(qū)域是其難點。其他方法[8-10]有的通過Voronoi圖，有的利用平面投影線加快建模速度，有的基于多視圖的三維模型進行重建。

隨著激光掃描設備的發(fā)展，包含被測物體更多細節(jié)的大量數(shù)據(jù)的獲取成為可能。針對高密度點云數(shù)據(jù)，文獻[11]中提出首先采用基于密度聚類的方法篩選三維點云，然后進行網(wǎng)格重建。浙江大學的藺宏偉等人[12]提出了根據(jù)點云內(nèi)在屬性進行重建的方法。文獻[13]提出了對數(shù)據(jù)進行柵格化的方法，但沒有給出一個合適的柵格規(guī)則。文獻[14]采用自適應八叉樹分割點云的方法進行表面模型重建，提高了模型重建的效率，也能夠體現(xiàn)點云模型的細節(jié)特征，但與傳統(tǒng)的三角網(wǎng)生長法相比，有一定的冗余網(wǎng)格。本文提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元實現(xiàn)三角網(wǎng)格重建的實現(xiàn)過程，解決了快速傳輸需求。對于高密度的點云精簡重建速度快，并且具有可將簡化和重建過程融為一體的優(yōu)點。

1概念

已知集合P，對于其中的任一點p，定義該點的r鄰域點為點集P中到p點距離不大于r的點集合，即：

定義該點的環(huán)域點為點集P中到p點距離介于r+σ與r-σ之間的點的集合，即：

2算法描述

2.1獲得長方體包圍盒

要實現(xiàn)對點云的分割，首先要獲得散亂點云的長方體包圍盒。遍歷全部點云，找到x，y，z三個坐標軸方向上最小和最大的共六個點，分別只取它們在對應坐標軸上的分量，組成兩個點，記為兩個點Pmax，Pmin，這兩個點即長方體包圍盒最長對角線的兩個端點。

2.2劃分立方體柵格及立方體邊長選擇策略

長方體包圍盒的長、寬、高，分別除以立方體的邊長，向上取整，即得點云分別在x，y，z坐標方向上立方體的個數(shù)，記為CubeNum(x,y,z)。立方體的編號通過它在x、y、z坐標方向上的編號組成的一個向量Id(x,y,z)來表示，獲取鄰域環(huán)域時需要檢索立方體的編號，為檢索方便，需將此立方體編號轉化為整數(shù)，方法如下：

L=Idx×CubeNumy×CubeNumz+Idy×CubeNumz+Idz

檢索鄰域和環(huán)域受影響的立方體時，實際上使用的是數(shù)字L。

在劃分立方體柵格的過程中，立方體的邊長的選擇尤為重要，它的大小直接影響到模型的重建效果。其具體的選擇策略描述如下。

由于掃描得到的是表面點，而立方體是根據(jù)長方體包圍盒來劃分的，所以在物體的內(nèi)部會有很多空的立方體。因此不能用體積來計算，本文選擇使用表面積進行計算。實際上是利用了長方體包圍盒的表面積近似等于所要重建的模型的表面積。

通過計算可以得出長方體包圍盒的長、寬、高即Pmax-Pmin所得的x、y、z分量，分別記為Px、Py、Pz，長方體包圍盒的表面積近似表示為物體的表面積，即：

(PxPy+PxPz+PyPz)×2

記為S。另外，點云中點的個數(shù)即總點數(shù)記為N。為便于后期對生成的網(wǎng)格進行曲面擬合，每個非空立方體內(nèi)至少要有多個數(shù)據(jù)點存在，一般為滿足三次曲面擬合，至少應有16個點，具體所取數(shù)值記為n，N除以n即可以得出需要立方體的個數(shù)。立方體邊長記為a，綜上所述，得出：

即：

(1)

劃分的立方體，以編號命名文件保存立方體中的點，并非所有連續(xù)編號的立方體都有其對應的文件，沒有點的立方體不會生成文件，所以效率上并沒有多余的浪費。

2.3重建過程

2.3.1初次外擴方法

重建的第一步是獲取種子點。由于是擴展重建，所以適宜從點云的中心開始，本文所有實驗均選取距離長方體包圍盒中心最近的點。根據(jù)2.1節(jié)中得到的Pmax，Pmin計算長方體包圍盒的中心，遍歷所有點得到距離中心最近的點設為初始種子點。

得到種子點后，要根據(jù)種子點進行外擴。對于一次外擴，它的準備工作有以下幾項。

? 第二，根據(jù)鄰域點集計算該鄰域的微切平面，得到微切平面的法向量。目的是為后續(xù)排序工作確定z軸正向。

? 第三，對環(huán)域點集進行排序。排序需要一個值作為排序的標記點。已知種子點O，如果當前生成的三角形是第一個三角形，則當前三角形的第二個頂點可在環(huán)域中隨機選取，如果當前生成的三角形不是第一個三角形，則由于隊列的搜索順序并不可隨機選取。具體的排序方法為：標記點記為A，OA作為微切平面上的x軸正向，z軸正向為微切平面的法向量與O點之差，由此既確定搜索的時針時序，本文采用逆時針搜索。計算環(huán)域點與O點連線與OA夾角的cos值，并計算叉乘結果與z軸正向比較，即知該點與OA的逆時序夾角是否超過180°，如果超過則取負值并減去2，使得cos函數(shù)在0～2π上是變成一個連續(xù)的遞減函數(shù)，由此可以根據(jù)它對環(huán)域點進行排序。

準備工作做好后，接下來就是三角形生成的過程。具體策略如下。

圖1　找到合適點組成三角形狀況圖

依次檢查排序后環(huán)域中的點與A點的距離，找到距A點最接近L的點。對于大部分數(shù)據(jù)來說，不需要搜索整個環(huán)域，只需所求點滿足一定條件即認為已找到。本文設置找到點距A大于0.6L即標記為已找到，0.6L為下限，保證等腰三角形的底角以70°至75°為上限而非過于苛刻得要求正三角形。由于搜索的環(huán)域已經(jīng)排序，當搜索到距1.4L(1.4L為上限，即保證等腰三角形的底角以45°為下限。)的位置，會判斷是否已經(jīng)找到合適的點。如果沒有找到，則進行分類討論：若當前點已滿足與隊頭的位置關系，則直接處理；若不合適則將當前點而非點A作為新三角形的第一個點，繼續(xù)向下搜索。如果找到則跳出循環(huán)判斷該點與隊頭的位置關系。判斷點與隊頭位置關系的策略如下。

找到合適點的情形如圖1所示，點J為找到的合適點。

圖1中，B為當前種子點，隊列順序為CDEFGHI。判斷J與隊頭C的關系并做相應處理。本文將其分為以下三種情況：

a.如果JC較大，本文設為大于2L。說明扇形BJC可以容納不止一個三角形，則先生成△BIJ，返回搜索。

b.如果JC非常小，本文設置為小于0.4L，此時本文認為IC接近于1.4L，滿足上文中以45°為等腰三角形底角下限的要求。繼而認為IC≈IJ≈L(由于模型是立體的，圖1顯示為平面效果，所以實際上IC不一定通過B，尤其在JC非常小的前提下)，則生成三角形△BIC。種子點變?yōu)镃。

c.如果JC中等大小，本文設置為0.5L至2L，即至少可容納兩個底角最大即70°～75°的等腰三角形，至多容納兩個底角最小即45°的等腰三角形，滿足上文的條件，此時直接生成兩個三角形，△BIJ和△BJC。種子點變?yōu)镃。

2.3.2外擴整體過程及方法

外擴是一個隊列遍歷種子點不斷生成三角形，不斷有新種子點入隊、舊種子點出隊的過程。本文中搜索順序是從隊尾搜索到隊頭，直到隊列中沒有點。由于始終采取逆時針遍歷，每當數(shù)據(jù)點出隊即作為當前種子時，除第一次擴展需特殊處理外(只需設置標記位即可解決此問題)，當前種子的搜索區(qū)域始終是隊尾—當前種子點—隊伍這樣一個扇形區(qū)域，如圖2-圖3所示。

圖2　左側為第一次擴展圖，右側為第二次擴展圖

圖3　第三次擴展圖

圖2左側為第一次擴展圖，種子點為O，此時隊列中點的順序為ABCDEF，右側為進一步進行擴展圖，種子點為A，隊列中點的順序為BCDEFGHI，此時以A為種子點時的搜索區(qū)域正是左側圖對應種子序列從隊頭到隊尾的扇形區(qū)域。

但是這樣并不能保證所有的點都被遍歷，需要在外側再設置循環(huán)，判斷是否所有的點標記為已讀。最終得到三角網(wǎng)格。

3實驗與分析

本文算法采用C語言實現(xiàn)，并在主頻為2.60GHz，內(nèi)存2GB的PC機上進行測試。本文分別對標準試驗數(shù)據(jù)斯坦福兔子和實驗室掃描的實測數(shù)據(jù)進行了測試。

斯坦福兔子數(shù)據(jù)包含數(shù)據(jù)點20 002個，根據(jù)本文介紹的劃分立方體方法計算得到(以下數(shù)值均為取整后數(shù)值)，Pmax=(511,441,508)，Pmin=(200,200,200)，Px、Py、Pz分別為311、241、308，繼而表面積S=489 934，根據(jù)前文所述，n取16，則由式(1)計算得a約為19.7，取整為20。式(1)中S和N都為確定值，所以，有且僅有n的取值影響a。n的取值為滿足三次曲面擬合所取數(shù)值。為測試實驗結果，本文將n取4、8又可得到a=10、a=14兩個值。即最終本文分別取小立方體邊長a為10、14、20進行實驗，得到結果比對如圖4和表1所示。圖4展示了立方體邊長分別取不同數(shù)值的效果及原始數(shù)據(jù)效果。表1列出了重建的詳細信息。

圖4　左上為立方體邊長為10的結果，右上為立方體邊長為14的結果，左下為立方體邊長為20的結果，右下為原始高密度點云的效果

立方體邊長立方體個數(shù)三角形個數(shù)用時(s)102918412122.690141499241014.50120741184312.188

由表1可知，本文對于密集散亂點云的網(wǎng)格數(shù)據(jù)精簡重建速度快，且根據(jù)歐拉公式可算出對應于立方體邊長選10、14、20時的簡化率分別為89.686%，93.966%，95.380%的前提下，本文所提出的方法均能保持基本形狀，有良好的魯棒性。

文獻[15]是一種基于頂點重要度的保形網(wǎng)格簡化方法，其數(shù)據(jù)顯示，當頂點數(shù)為4850時，簡化率達到91.81%時所用時間為8.24s，且簡化率越高，耗時越長。推算該方法當頂點數(shù)大于20 000時，達到同樣簡化率所用時間約為33.979s，而本文方法處理大于20 000點以上數(shù)據(jù)時(如上文斯坦福兔子數(shù)據(jù))，達到精簡率93.966%僅需14.501s，達到精簡率95.380%僅需12.188s，可見本文精簡速度較快。并且本文方法在立方體邊長取值較大時，精簡率越高，重建時間越短，將簡化和重建過程融為一體。

本文還對實驗室掃描的實測數(shù)據(jù)進行了測試。雖然自掃描數(shù)據(jù)存在噪聲大，存在大量重復點等缺點，但本文方法仍取得了良好的實驗結果。第一個實驗數(shù)據(jù)是一個古玩瓶子模型，單面掃描有18 553個點，根據(jù)本文介紹的劃分立方體方法計算得到(以下數(shù)值均為取整后數(shù)值)，Pmax=(214,136,234)，Pmin= (51,38,11)，Px、Py、Pz分別為163、98、223，繼而表面積S=148 354，由于該掃描數(shù)據(jù)為單側面，所以表面積本文取一半即S=74 177，n取16，則由式(1)計算得a約為7。立方體邊長7.0，運行時間9.879s。效果如圖5所示。

圖5　瓶子模型網(wǎng)格重建效果。左上為本文實驗效果，右上為掃描得到的密集數(shù)據(jù)。下側為古玩瓶實物圖

第二個數(shù)據(jù)是本實驗室自掃描兵馬俑模型，側面數(shù)據(jù)點96 780個，根據(jù)本文介紹的劃分立方體方法計算得到(以下數(shù)值均為取整后數(shù)值)，Pmax=(424,76,711)，Pmin= (-129,-135,394)，Px、Py、Pz分別為553、211、317，繼而表面積S=717 742，由于該掃描數(shù)據(jù)為單側面，所以表面積本文取一半即S=358 871，n取16，則由式(1)計算得a約為8。邊長取8，運行時間30.595s。效果如圖6所示。

圖6　兵馬俑模型網(wǎng)格重建效果

由于實測掃描數(shù)據(jù)噪聲較大，所以實驗結果邊緣略顯瑣碎，但仍能保持基本形狀，取得了較為良好的效果。

4結語

本文提出一種自適應立體柵格劃分方法，并給出以立體柵格為基本單元實現(xiàn)三角網(wǎng)格重建的實現(xiàn)過程。首先將點云數(shù)據(jù)分割為柵格單元，然后通過選取基本單元中數(shù)據(jù)點為種子點和設定三角形邊長以近似正6鄰域為約束來構建初始三角網(wǎng)格，再逐層外擴完成三角網(wǎng)格重建。本文方法解決了快速傳輸需求，從高密度點云直接生成精簡的三角網(wǎng)格模型，從實驗結果來看，對于高密度的點云精簡重建速度快，魯棒性較好，并且具有可將簡化和重建過程融為一體的優(yōu)點。

參考文獻

[1] 陳建良,童水光.逆向工程技術研究進展[J].中國機械工程,2002,13(16):1430-1436.

[2] 崔漢國,胡懷宇,張濤,等.空間自由管道點云重建方法[J].海軍工程大學學報,2011,23(2):76-79.

[3]HoppeH,DeRoseT,DuchampT,etal.SurfaceReconstructionfromUnorganizedPoints[J].ACMSIGGRAPHComputGraphics,1992,26(2):71-78.

[4]AmentaN,BernM,KamvysselisM.ANewVoronoi-basedSurfaceReconstructionAlgorithm[C]//Proceedingsofthe25thAnnualConferenceonComputerGraphicsandInteractiveTechniques,1998:415-421.

[5]AmentaN,ChoiS,KolluriRK.ThePowercrust[C]//Proceedingsofthe6thACMSymposiumonSolidModelingandApplications,2001:249-260.

[6]DeyTK,GiesenJ,HudsonJ.DelaunayBasedShapeReconstructionfromLargeData[C]//ProceedingoftheIEEESymposiumonParallelandLarge-DataVisualizationandGraphic,2001:19-27.

[7] 袁方,唐杰,武港山.一種基于三維Delaunay三角化的曲面重建算法[J].計算機技術與發(fā)展,2011,21(10):14-18.

[8] 紀志浩,于明旭.基于點云數(shù)據(jù)三維重建方法的研究[J].黑龍江工程學院學報:自然科學版,2014,28(3):7-9.

[9] 陳治睿,官云蘭,楊鵬,等.基于點云數(shù)據(jù)的建筑物快速三維重建方法[J].江西科學,2011,29(5):603-606.

[10] 段春梅.基于多視圖的三維模型重建方法研究[D].山東:山東大學,2009.

[11] 陳曉霞,陳孝威.三維重建中散亂點云的聚類篩選與網(wǎng)格重建[J].計算機系統(tǒng)應用,2011,20(4):141-144.

[12]HongweiLin,ChiewlanTai,GuojinWang.AMeshReconstructionAlgorithmDrivenbyanIntrinsicPropertyofaPointCloud[J].Computer-AidedDesign,2004,36(1):1-9.

[13] 聶建輝,馬孜,胡英,等.針對密集點云的快速曲面重建算法[J].計算機輔助設計與計算機圖形學學報,2012,24(5):574-582.

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

[15] 董艷,張志毅,楊客.基于頂點重要度的保形網(wǎng)格簡化方法研究[J].計算機工程與設計,2013,34(5):1889-1895.

TRIANGULAR MESH RECONSTRUCTION BY DIRECTLY SIMPLIFYINGDENSEPOINTCLOUD

Dong TianqiZhang Zhiyi*

(College of Information Engineering,Northwest A&F University,Yangling 712100,Shaanxi,China)

AbstractTo address the needs of rapid transmission and to generate the streamlined triangular mesh model directly from dense point cloud, this paper presents an adaptive method for three-dimensional grid division, and gives the reconstruction process of triangular mesh which uses the three-dimensional grid as basic unit. First, by using the macro-estimation method of no difference between points the method obtains the side length of three-dimensional grid, and segments the point cloud data into grid units. Then it selects the data points in basic unit as the seed points, and sets the triangle side lengths to be constrained with approximate positive 6 neighbourhoods to build the initial triangle mesh, and then expands outwardly layer by layer to complete the triangular mesh reconstruction. The advantage of this method is that the reconstruction and simplification processes can be integrated as a whole. Experimental results show that the proposed method is faster with better robustness.

KeywordsSimplifyDense point cloudMesh reconstructionOutward expansion

收稿日期：2015-01-14。國家高技術研究發(fā)展計劃項目(2013AA 10230402)；中央高?；究蒲袠I(yè)務費西北農(nóng)林科技大學科技創(chuàng)新項目(QN2013054)。董天琪，碩士生，主研領域：計算機圖形學。張志毅，副教授。

中圖分類號TP391.41

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.063