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

李玉潮,黃培之,陳 玲

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

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

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

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

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

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

一、引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、試驗結果與分析

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

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

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

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

圖1 試驗一所用數據

圖2 試驗一的結果

表1 試驗一結果統計分析

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

圖3 試驗二所用數據

圖4 試驗二結果

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

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

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

[4] LA I POH-CH IN,黃培之.2D幾何圖形整體內插的一種方法[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—),男,河南南陽人,高級講師,主要從事攝影測量與遙感、數字制圖和地理信息系統方面的教學和研究工作。