紀(jì)志浩,于明旭

(1.徐州市三聯(lián)測(cè)繪服務(wù)有限公司,江蘇 徐州 221116；2.江蘇建筑職業(yè)技術(shù)學(xué)院,江蘇 徐州 221116)

基于點(diǎn)云數(shù)據(jù)三維重建方法的研究

紀(jì)志浩1,于明旭2

(1.徐州市三聯(lián)測(cè)繪服務(wù)有限公司,江蘇 徐州 221116；2.江蘇建筑職業(yè)技術(shù)學(xué)院,江蘇 徐州 221116)

由于三維激光掃描儀采集的點(diǎn)云數(shù)據(jù)是離散的，這些離散的點(diǎn)云數(shù)據(jù)由于分辨率有限，缺少靈活性，導(dǎo)致無(wú)法滿足對(duì)實(shí)際場(chǎng)景重建出具有幾何精確性的模型。為解決上述問(wèn)題，用Delaunay三角化方法構(gòu)造網(wǎng)格逼近物體的三維表面模型，把離散的點(diǎn)云數(shù)據(jù)連續(xù)化生成表面模型來(lái)模擬場(chǎng)景，實(shí)驗(yàn)證明該方法有效。

點(diǎn)云數(shù)據(jù);Delaunay三角化;Voronoi圖;曲面模型;三維重建

依據(jù)離散點(diǎn)云數(shù)據(jù)集與重建三維曲面之間關(guān)系，三維重建分為逼近法和插值法兩大類。依據(jù)重建曲面的表現(xiàn)形式，可將重建分為以下幾種：網(wǎng)格重建、參數(shù)重建、隱式重建、變形重建和細(xì)分重建。

離散點(diǎn)云數(shù)據(jù)重建實(shí)際場(chǎng)景三維表面模型就是將離散點(diǎn)連續(xù)化，其本質(zhì)是進(jìn)行插值。利用離散點(diǎn)數(shù)據(jù)構(gòu)建網(wǎng)格有不規(guī)則三角網(wǎng)和不規(guī)則四邊形，不規(guī)則三角網(wǎng)TIN與四邊形格網(wǎng)模擬表面相比具有如下優(yōu)點(diǎn)：一是在分辨率相同的情況下，TIN模型占用存儲(chǔ)空間少，構(gòu)網(wǎng)時(shí)間短，且表示復(fù)雜曲面精細(xì)度好。二是通過(guò)離散點(diǎn)組成的三角形，其幾何算法最可靠，并且絕大部分軟件、硬件的圖形真實(shí)感反映系統(tǒng)運(yùn)算的基本單元都是以TIN作為基礎(chǔ)?；谏鲜鎏攸c(diǎn)，模擬場(chǎng)景表面模型最常用的方法是構(gòu)建三角形網(wǎng)格，目前，Delaunay三角剖分方法是構(gòu)建三角形網(wǎng)格中最為常用的方法。

1 Delaunay三角剖分

本文通過(guò)離散點(diǎn)集的Delaunay三角剖分實(shí)現(xiàn)重建實(shí)際場(chǎng)景的三維模型。為更好了解Delaunay三角剖分，首先介紹Voronoi圖和三角剖分概念。

1.1 Voronoi圖

Voronoi圖是一個(gè)廣泛應(yīng)用的圖結(jié)構(gòu)。它是由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形，是Delaunay三角剖分的基礎(chǔ)，Voronoi三角形是Delaunay圖的對(duì)偶圖。

Voronoi圖定義：對(duì)于平面上離散點(diǎn)集p={pi,0≤i≤n,i∈N}，pi是該點(diǎn)集內(nèi)任意一點(diǎn)，通過(guò)pi可以定義一個(gè)局部點(diǎn)集Vi，任意一點(diǎn)R∈Vi，有d(R,pi)

圖1 Voronoi圖

1.2 Delaunay三角剖分定義

Delaunay(Delaunay Triangulation,DT)三角剖分是指點(diǎn)集V的一個(gè)三角剖分T只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分。

1.3 Delaunay三角剖分特性

Delaunay三角剖分組成的三角網(wǎng)格性質(zhì)如下：

1) 在所有的三角剖分中，Delaunay三角剖分中三角形的最小內(nèi)角之和是最大的，即最小內(nèi)角最大性質(zhì)。

2) 不論從區(qū)域何處開(kāi)始構(gòu)網(wǎng)，最終都將得到一致的結(jié)果，即構(gòu)網(wǎng)具有唯一性。

3) 任何一個(gè)三角形的外接圓都不包含其它的離散數(shù)據(jù)點(diǎn)集中的點(diǎn)，即空外接圓性質(zhì),如圖2所示(圖中三角形的外接圓邊界用虛線表示)。

圖2 DT空外接圓性質(zhì)

以上性質(zhì)可以確保在Delaunay三角剖分中盡可能不出現(xiàn)過(guò)于尖銳的三角形，進(jìn)而保證構(gòu)網(wǎng)的三角形最大限度地接近等邊或等角三角形。所以，對(duì)于平面內(nèi)的離散點(diǎn)集而言，Delaunay三角剖分是構(gòu)建TIN技術(shù)最為常用的方法。

2 構(gòu)網(wǎng)實(shí)現(xiàn)方法

實(shí)現(xiàn)Delaunay三角剖分的算法有多種。由Reifl和Brasse提出以離散點(diǎn)集中的任意一點(diǎn)為起始點(diǎn)，以循環(huán)搜索方式查找任意一點(diǎn)一維排序鏈表中的Dirichlet鄰域點(diǎn)法， Lawson提出的逐點(diǎn)插入法實(shí)現(xiàn)Delaunay三角剖分算法，其中，Bowyer-Wateson的網(wǎng)格剖分算法是公認(rèn)的、使用較廣泛的算法，其基本思想是：構(gòu)造一個(gè)包含所有散亂點(diǎn)的Delaunay三角形，并將此三角形放入三角形鏈表中，向初始化的Delaunay三角形中依次插入散亂點(diǎn)集中的點(diǎn)，根據(jù)上述內(nèi)容中的優(yōu)化方法，完成一個(gè)點(diǎn)在Delaunay三角形鏈表中的插入，依次將所有點(diǎn)插入完畢，然后迭代該過(guò)程，直至點(diǎn)集中所有點(diǎn)處理結(jié)束。該過(guò)程可以用圖3表示。本文選取化石林中的化石點(diǎn)云經(jīng)過(guò)三角化后的結(jié)果，如圖4所示。

圖3 Delaunay三角剖分過(guò)程

圖4 化石Delaunay三角網(wǎng)模型

3 模型重建方法

本文使用Geomagic studio 12所提供的Delaunay三角剖分模塊來(lái)完成散亂點(diǎn)集的三角剖分以及模型重建。在Geomagic studio12中，實(shí)現(xiàn)離散激光點(diǎn)云數(shù)據(jù)三維表面模型重建過(guò)程如下。

3.1 多邊形修整

多邊形修整階段主要任務(wù)是：1)對(duì)點(diǎn)云數(shù)據(jù)構(gòu)建Delaunay三角網(wǎng)；2)對(duì)構(gòu)網(wǎng)后的多邊形修整，包括基于曲率孔填充、邊界修補(bǔ)、光順邊界、特征構(gòu)建、探測(cè)曲線并調(diào)整、多邊形簡(jiǎn)化、多邊形細(xì)化等。圖5為多邊形修整后的化石，5(a)為修補(bǔ)破孔前的數(shù)據(jù)，5(b)為修補(bǔ)破孔后數(shù)據(jù)。

圖5 多邊形修整前后的化石模型

3.2 曲面編輯

曲面質(zhì)量的好壞直接影響到三維模型的精度，曲面編輯主要包括特征線提取、特征識(shí)別、邊界構(gòu)建、面片組織、面片光順等。

1)創(chuàng)建曲面片階段。

2)對(duì)創(chuàng)建后的曲面片劃分。劃分曲面片不能過(guò)大，過(guò)大導(dǎo)致捕捉點(diǎn)云形狀困難，得到曲面質(zhì)量差。劃分曲面片不能過(guò)小，過(guò)小導(dǎo)致曲面太碎，給后續(xù)工作帶來(lái)一定困難。曲面片劃分應(yīng)遵循以下原則：① 較平滑的部位曲面片少而大。特征多的地方曲面片多而細(xì)。② 曲面片的曲率變化盡量保持均勻，這樣可以提高創(chuàng)建曲面質(zhì)量。③ 創(chuàng)建曲面片盡量是四邊域曲面。

調(diào)整曲面片布局，構(gòu)建曲面片后，通過(guò)對(duì)曲面片的控制點(diǎn)增加、減少、改變方向、拖動(dòng)等方式進(jìn)行調(diào)節(jié)，目的是使各曲面片縱橫方向有序、方向盡量相同。如圖6所示曲面片階段化石的模型。

3)網(wǎng)格線建立。調(diào)整曲面片后，構(gòu)造“網(wǎng)格線”，對(duì)曲面片內(nèi)的網(wǎng)格線做進(jìn)一步調(diào)整，將其調(diào)整到方向一致、均勻的光順曲面網(wǎng)格為止。曲面片內(nèi)的網(wǎng)格線越稀疏，曲面數(shù)據(jù)的精確度相對(duì)較低；點(diǎn)云數(shù)據(jù)文件所占空間較小，數(shù)據(jù)處理速度較快。與之相反，網(wǎng)格線越密集，精確度越高；數(shù)據(jù)處理速度較慢。圖7所示為網(wǎng)格線階段化石的模型。

圖7 化石網(wǎng)格階段模型

4)建立曲面模型。基于上述創(chuàng)建的曲面片和網(wǎng)格線，建立無(wú)紋理屬性的化石表面模型，如圖8所示。

圖8 無(wú)紋理屬性化石模型

圖9 誤差比對(duì)模型

3.3 文件輸出

為了檢查模型是否符合精度標(biāo)準(zhǔn)，需要比較曲面與點(diǎn)云間的誤差(3DCompare)，如圖9所示，其中圖9(a)為化石點(diǎn)云數(shù)據(jù)與化石重建后模型，圖9(b)

為曲面與點(diǎn)云間的誤差比較過(guò)程，圖9(c)為曲面與點(diǎn)云間的誤差比較結(jié)果。

從圖9(c)可以得出，曲面和點(diǎn)云間最大偏差為0.268 mm，平均偏差為0.022 mm，標(biāo)準(zhǔn)偏差為0.051 mm，經(jīng)過(guò)查閱文獻(xiàn)知其精度符合模型重建要求。

4 結(jié)束語(yǔ)

使用三維激光掃描儀獲取點(diǎn)云數(shù)據(jù)進(jìn)行三維場(chǎng)景重建時(shí)，為使模型效果更逼真，可以對(duì)模型進(jìn)行渲染。本實(shí)驗(yàn)驗(yàn)證了三維激光掃描儀在三維模型重建領(lǐng)域有一定的實(shí)用性。

[1]王曉南,鄭順義.基于激光掃描和高分辨率影像的文物三維重建[J].測(cè)繪工程,2009,18(6):53-55.

[2]于明旭,紀(jì)志浩,黃國(guó)斌，等.地面激光掃描和數(shù)碼相機(jī)在化石重建中的應(yīng)用[J].交通科技與經(jīng)濟(jì),2013,15(4):124-126.

[3]胡影峰.逆向工程后處理中基于點(diǎn)線面的曲面重建[J].煤礦機(jī)械，2008,29(6):201-202.

[4]梁振華，王晨，謝宏全．基于萊卡C10獲取校園三維點(diǎn)云數(shù)據(jù)設(shè)計(jì)[J].測(cè)繪工程，2013,22(1):47-50.

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

[6]喜文飛,方源敏,李帥,等.一種新的激光點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[J].測(cè)繪工程，2012,21(4):38-40.

[7] 范劍英.結(jié)構(gòu)光深度圖像獲取和處理與三維重建研究[D].哈爾濱：哈爾濱理工大學(xué)，2012.

Research on 3D reconstruction method based on point cloud

JI Zhi-hao1,YU Ming-xu2

(1.Xuzhou Sanlian Mapping Co.Ltd.,Xuzhou 221116,China; 2.Jiangsu Vocational College of Architecture,Xuzhou 221116,China)

The 3D laser scanning point cloud data is discrete because of the limited resolution and lack of flexibility which lead to be unable to satisfy with the geometric accuracy of the model to the actual scene reconstruction.In order to solve the above problems,the 3D surface model uses Delaunay Triangulation method to construct the grid approximation of an object and the point cloud data of discrete continuous generation of surface model to simulate the scene.The experiments show it is an effective and feasible method to reconstruct the fossil modeling.

point cloud; Delaunay triangulation; Voronoi diagram; surface model; three dimensional reconstruction

2014-02-16

紀(jì)志浩(1986-)，男，助理工程師，研究方向：工程測(cè)量.

P208

A

1671-4679(2014)03-0007-03

郝麗英]