一種用于等值線數(shù)據(jù)重建目標(biāo)三維模型的算法

李玉潮,黃培之,陳 玲

(1.鄭州測繪學(xué)校,河南鄭州 450005;2.深圳大學(xué),廣東深圳 518060; 3.深圳市騰訊計(jì)算機(jī)系統(tǒng)有限公司,廣東深圳 518057)

一種用于等值線數(shù)據(jù)重建目標(biāo)三維模型的算法

李玉潮1,黃培之2,陳 玲3

(1.鄭州測繪學(xué)校,河南鄭州 450005;2.深圳大學(xué),廣東深圳 518060; 3.深圳市騰訊計(jì)算機(jī)系統(tǒng)有限公司,廣東深圳 518057)

利用等值線數(shù)據(jù)重建目標(biāo)三維模型在實(shí)際工程中有著廣泛的應(yīng)用。在研究現(xiàn)有的利用等值線數(shù)據(jù)重建目標(biāo)三維模型的方法后,提出一種基于等值線圖形形狀相似性變換的三維表面重建方法。試驗(yàn)結(jié)果表明,該方法比現(xiàn)有的利用等值線數(shù)據(jù)重建目標(biāo)三維模型的方法能更好地實(shí)現(xiàn)三維表面重建。

等值線;三維模型;相似性;勢能場

一、引 言

利用等值線數(shù)據(jù)重建目標(biāo)三維模型是計(jì)算機(jī)圖形學(xué)的一個(gè)研究內(nèi)容,它在實(shí)際工程中有著廣泛的應(yīng)用。如醫(yī)學(xué)圖像處理中利用人體器官的 CT圖像輪廓線重建該器官的三維模型,以幫助診斷該器官的病變;在測繪工程中利用等高線數(shù)據(jù)建立數(shù)字地面模型(DEM),以幫助規(guī)劃、設(shè)計(jì)、軍事等部門解決各自領(lǐng)域的問題。

傳統(tǒng)的利用等值線數(shù)據(jù)重建目標(biāo)三維模型的方法主要包括數(shù)據(jù)點(diǎn)的采集和內(nèi)插點(diǎn)的獲取兩個(gè)內(nèi)容。前者以分析等值線形態(tài)變化獲取能夠描述該等值線形狀的特征點(diǎn)作為采樣點(diǎn)數(shù)據(jù);后者用與內(nèi)插點(diǎn)相鄰近的采樣點(diǎn)建立局部函數(shù),獲得描述目標(biāo)表面的局部函數(shù),從而得到內(nèi)插點(diǎn)數(shù)據(jù)[1]。分析現(xiàn)有三維目標(biāo)表面重建內(nèi)插點(diǎn)獲取的算法可以知道,這些內(nèi)插算法在獲取內(nèi)插點(diǎn)時(shí)大多是只采用與該點(diǎn)相鄰近的少數(shù)采樣點(diǎn)進(jìn)行內(nèi)插計(jì)算,而沒有顧及采樣點(diǎn)數(shù)據(jù)的整體特性和內(nèi)在聯(lián)系。這樣所獲得的內(nèi)插點(diǎn)只能夠顧及地形變化的局部規(guī)律,而忽略了地形變化的整體規(guī)律。它使得重建后的目標(biāo)三維模型的質(zhì)量和準(zhǔn)確性難以得到保障,甚至有時(shí)會出現(xiàn)錯誤[2]。因此,需要對利用等值線數(shù)據(jù)重建目標(biāo)三維模型這一問題進(jìn)行深入研究。

二、利用等值線數(shù)據(jù)重建目標(biāo)三維模型的方法

常用的利用等值線數(shù)據(jù)重建目標(biāo)三維模型的方法有不規(guī)則三角網(wǎng)方法 (triangulated irregular network,T IN)和局部函數(shù)法[1]。

T IN是根據(jù)原始等值線上的采樣點(diǎn)構(gòu)建不規(guī)則三角網(wǎng),其實(shí)質(zhì)是將相鄰等值線上相近的三點(diǎn)構(gòu)成最佳三角形,使每個(gè)數(shù)據(jù)點(diǎn)都成為三角形頂點(diǎn)。這樣就可以用這些三角形片面擬合相鄰等值線之間的三維表面。相鄰等值線之間的任意一點(diǎn) P(Xp, Yp,Zp)的內(nèi)插值可由式 (1)根據(jù)該點(diǎn)所在的三角形片面的 3個(gè)三角形頂點(diǎn)的坐標(biāo) (Xi,Yi,Zi,i=1,2, 3)計(jì)算獲得。

局部函數(shù)法是以內(nèi)插點(diǎn)為中心,用與其相鄰的n(n大于局部函數(shù)中的待定參數(shù)的個(gè)數(shù))個(gè)采樣點(diǎn)擬合一個(gè)局部函數(shù),采用最小二乘法原理解求該局部函數(shù)的待定參數(shù),然后根據(jù)這個(gè)局部函數(shù)解算出內(nèi)插點(diǎn)的內(nèi)插值。移動曲面法是一種常用的局部函數(shù)法,它通常采用式 (2)描述的二次多項(xiàng)式來擬合一個(gè)局部函數(shù)。

以上兩種算法皆為單點(diǎn)解求內(nèi)插點(diǎn)的內(nèi)插值,為了提高解求內(nèi)插點(diǎn)的效率和可靠性,研究人員研究出了整體內(nèi)插方法[1]。該方法是以規(guī)則格網(wǎng)點(diǎn)為內(nèi)插點(diǎn),用局部函數(shù)建立相鄰格網(wǎng)點(diǎn)和該格網(wǎng)點(diǎn)內(nèi)的采樣點(diǎn)之間的數(shù)學(xué)關(guān)系,然后對相鄰格網(wǎng)的局部函數(shù)進(jìn)行光滑性約束,建立起相鄰局部函數(shù)之間的數(shù)學(xué)關(guān)系,最后整體求解出所有內(nèi)插點(diǎn) (格網(wǎng)點(diǎn))的內(nèi)插值。該方法常用的局部函數(shù)有雙線性函數(shù)(見式 (3))和雙三次函數(shù) (見式 (4))。

對現(xiàn)有的利用等值線數(shù)據(jù)獲取內(nèi)插點(diǎn)的算法進(jìn)行分析可以知道,這些內(nèi)插算法在獲取內(nèi)插點(diǎn)時(shí)大多是只采用與該點(diǎn)相鄰近的少數(shù)幾個(gè)采樣點(diǎn)進(jìn)行計(jì)算,而沒有顧及采樣點(diǎn)數(shù)據(jù)的特性和內(nèi)在聯(lián)系。這樣所獲得的內(nèi)插點(diǎn)只能夠顧及三維表面變化的局部規(guī)律,而忽略了三維表面變化的整體規(guī)律。它使得重建后的三維表面的質(zhì)量和準(zhǔn)確性難以得到保障,甚至有時(shí)會出現(xiàn)錯誤。

三、基于相鄰等值線形狀相似性的三維表面重建方法

由于等值線是三維實(shí)體目標(biāo)的外輪廓線與一組平行面的交線的集合,可以證明相鄰等值線的形狀具有一定的相似性[3]。這種相似性關(guān)系與等值線之間的三維表面的變化狀況有關(guān),因此它能夠間接地反映等值線之間的三維表面的變化狀況?，F(xiàn)有的利用等值線數(shù)據(jù)進(jìn)行三維目標(biāo)重建的方法在獲取內(nèi)插點(diǎn)時(shí)僅僅采用與該內(nèi)插點(diǎn)較鄰近的少數(shù)采樣點(diǎn),顯然是不合理的。它忽略了相鄰等值線間的三維實(shí)體目標(biāo)表面變化的整體規(guī)律,這一理論上的缺陷制約了這類算法獲取內(nèi)插點(diǎn)的最終結(jié)果的質(zhì)量和準(zhǔn)確性。

為了克服現(xiàn)有的利用等值線數(shù)據(jù)獲取內(nèi)插點(diǎn)算法的缺陷,建立能夠描述相鄰等值線形狀之間的相似性變化規(guī)律的模型具有一定的意義。由物理學(xué)原理知道,某些物理場 (重力場、電勢能場等)的場強(qiáng)度等值線與產(chǎn)生該物理場的場源形狀具有相似性,并且這種相似性隨場強(qiáng)度等值線距場源的平面距離的增加 (減少)而單調(diào)減少 (或增加)。該種關(guān)系反映到場強(qiáng)等值線上就是場強(qiáng)度等值線形狀的差異隨場強(qiáng)度值的增加 (或減少)而單調(diào)減弱(增強(qiáng))。因此可以借助物理學(xué)中的場強(qiáng)度模型來研究分析等值線形狀的變化規(guī)律[4]。具體方法如下：

設(shè)兩相鄰等值線分別為 c和 c′,若將其視為均勻分布著一定數(shù)量電荷的兩個(gè)帶電體,則根據(jù)電學(xué)知識可以知道,在 c和 c′之間的環(huán)形區(qū)域可以形成一個(gè)電勢場。該電勢場中任意一點(diǎn)的場強(qiáng)度可由式(5)獲得。

其中,r1、r2分別為電勢場中任意一點(diǎn)到場源曲線 c和 c′上點(diǎn)電荷的距離。

分析式 (5)可以知道,由于電勢場強(qiáng)度與距場源的距離 r成反比,因此,由式 (5)計(jì)算出的電勢場強(qiáng)度在距場源的距離 r小于某一閾值 T時(shí),其場強(qiáng)度變化很大;而當(dāng)距場源距離 r大于該閾值時(shí),其場強(qiáng)度變化較為平緩 (見圖 2(c))。顯然,直接用電勢場強(qiáng)度模型式(5)來模擬目標(biāo)三維表面變化是不合適的。對電勢場強(qiáng)度模型和相鄰等值線之間的三維表面變化規(guī)律進(jìn)行研究可以知道,適當(dāng)?shù)剡x擇式(6)中的隨到場源的距離 r而變化的函數(shù) f(r)可以獲得與三維實(shí)體目標(biāo)表面變化規(guī)律大致相同的場強(qiáng)度模型 (見圖 2(d))。

根據(jù)上述原理,筆者通過研究得出選擇指數(shù)函數(shù) f(r)=1/ur(u為常數(shù))可以較好地用來模擬三維實(shí)體目標(biāo)的表面變化規(guī)律[3]。

四、試驗(yàn)結(jié)果與分析

為了驗(yàn)證和評估本文所述的方法,筆者進(jìn)行了試驗(yàn)。

在試驗(yàn)一中,筆者對式 (7)描述的拋物面 (見圖 1(a))分別用 z=0、z=50兩個(gè)水平面截取拋物面得到兩條相鄰等值線 c′、c(見圖 1(b)),其方程為

在這兩條等值線上各取若干點(diǎn)作為采樣點(diǎn)數(shù)據(jù)進(jìn)行試驗(yàn)分析,最大試驗(yàn)區(qū)域?yàn)?200×200(見圖 1(b))。

試驗(yàn)一分別用線性內(nèi)插、三次多項(xiàng)式內(nèi)插、廣義勢能場模型、f(r)=1/ur模型 (其中 u=1.03)對圖 1(b)所示的等值線數(shù)據(jù)進(jìn)行實(shí)體目標(biāo)三維表面重建,圖 2是重建結(jié)果。用試驗(yàn)結(jié)果所得到的目標(biāo)三維表面數(shù)據(jù)與由式 (7)計(jì)算出的理論值 (見圖 1(a))比較可以得到各種方法的誤差數(shù)據(jù) (見表 1)。從表 1中可以看出用 f(r)=1/ur模型進(jìn)行三維實(shí)體目標(biāo)表面重建,其中誤差、平均誤差、最大誤差皆為最小。

圖1 試驗(yàn)一所用數(shù)據(jù)

圖2 試驗(yàn)一的結(jié)果

表1 試驗(yàn)一結(jié)果統(tǒng)計(jì)分析

為了驗(yàn)證 f(r)=1/ur模型的實(shí)用性,筆者用兩條相鄰等值線進(jìn)行試驗(yàn) (見圖 3),試驗(yàn)結(jié)果見圖 4。從試驗(yàn)結(jié)果圖 4可以看出用 f(r)=1/ur模型重建的相鄰等高線之間的地形曲面所含地形信息十分豐富,地形細(xì)部清楚,能夠較好地描述相鄰等高線之間的地形變化情況。

圖3 試驗(yàn)二所用數(shù)據(jù)

圖4 試驗(yàn)二結(jié)果

[1] 張祖勛,張劍清.數(shù)字?jǐn)z影測量學(xué)[M].武漢：武漢測繪科技大學(xué)出版社.1997.

[2] 黃培之.等高線形狀變化規(guī)律的研究[J],中國圖象圖形學(xué)報(bào),2006,11(1)：103-106.

[3] 黃培之.基于等高線特性數(shù)據(jù)的三維表面重建方法的研究[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版,2005,30(8)：668-672.

[4] LA I POH-CH IN,黃培之.2D幾何圖形整體內(nèi)插的一種方法[J].計(jì)算機(jī)學(xué)報(bào),1999,22(2)：165-170.

An Algorithm for Three-d imensional Surface Reconstruction from Contour Data

L I Yuchao,HUANG Peizhi,CHEN Ling

0494-0911(2010)08-0015-03

P23

B

2010-07-01

李玉潮(1956—),男,河南南陽人,高級講師,主要從事攝影測量與遙感、數(shù)字制圖和地理信息系統(tǒng)方面的教學(xué)和研究工作。