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

李玉潮,黃培之,陳 玲

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

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

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

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

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

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

一、引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了驗證和評估本文所述的方法,筆者進行了試驗。

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

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

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

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

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

表1 試驗一結(jié)果統(tǒng)計分析

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

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

圖4 試驗二結(jié)果

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

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

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

[4] LA I POH-CH IN,黃培之.2D幾何圖形整體內(nèi)插的一種方法[J].計算機學報,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)方面的教學和研究工作。