原慶紅， 韓 燮（中北大學 電子與計算機科學技術(shù)學院，山西太原 030051）

0 引言

由于戰(zhàn)場地形仿真往往是大數(shù)據(jù)量的地形，其顯示技術(shù)受到計算機硬件的限制，不能夠?qū)崟r地顯示地形。如分辨率為90m的540×540km2的地形區(qū)域有36M個高程點，約有72M個三角形面元。我們發(fā)現(xiàn)高程數(shù)據(jù)點中一些關(guān)鍵性的特征點能表示曲面的形狀，并且三次準均勻B樣條曲線能自動保持曲面處的二階連續(xù)，采用曲面插值特征點的方法能夠準確擬合地形表面，這種方法計算量也較小。因此本文在對整個大地形的建模過程中，根據(jù)計算機的渲染能力，采用地形變分辨率技術(shù)，整體地形采用分辨率較低，對于重點關(guān)注地域使用三次準均勻B樣條曲線插值特征點，生成高分辨率的地形曲面。

1 數(shù)字地形構(gòu)建

1.1 數(shù)字高程模型

數(shù)字高程模型(Digital Elevation Mode簡稱DEM)是數(shù)字地形研究的主要對象。DEM是區(qū)域地形的數(shù)字表示，由一系列地面點的X，Y坐標及其相聯(lián)系的高程，按一定的結(jié)構(gòu)組織在一起表示實際地形特征的空間分布模型，DEM數(shù)據(jù)是國家基礎(chǔ)地理信息系統(tǒng)數(shù)據(jù)中主要的一部分。本文使用ARC/INFO公司GRID格式的規(guī)則格網(wǎng)DEM數(shù)據(jù)。規(guī)則格網(wǎng)DEM是一種高程矩陣。它的優(yōu)點是：結(jié)構(gòu)簡單，便于存儲，有利于各種分析和計算。該格式包括2部分：第一部分為文件的信息頭，如表1所示。第二部分是數(shù)據(jù)部分，即實際的高程值。自西向東按列記錄DEM點的高程數(shù)據(jù)值，它的橫坐標和縱坐標值可根據(jù)信息頭中起始位置的橫縱坐標和相鄰網(wǎng)格的間隔值計算求得。其中格網(wǎng)點的高程值單位均為度。

表1 ARC/INFO的GRID格式

1.2 三次準均勻B樣條曲線

準均勻B樣條曲線：其節(jié)點矢量中兩端節(jié)點具有重復(fù)度k+1，即u0=u1=…=uk，un+1=un+2=…un+k+1,。定義域u∈[uk,un+1]內(nèi)節(jié)點區(qū)間長度Δi＝常數(shù)＞0(i=k,k+1,…,n) ，所有內(nèi)節(jié)點均勻分布具有重復(fù)度1。用三次準均勻B樣條擬合規(guī)則格網(wǎng)的DEM數(shù)據(jù)，有以下優(yōu)點：(1)第i段k次B樣條曲線僅由V1,V2,…，Vk+1共k+l個頂點所控制，而與其他頂點無關(guān)。因此修改該段曲線，僅需修改相關(guān)的k+1個頂點。(2)該方法生成的曲線、曲面在邊界處自動保持二階連續(xù)性[2]。

2 基于特征點能量優(yōu)化的B樣條插值地形算法

曲線曲面擬合是數(shù)字高程模型重構(gòu)中的一個重要步驟，目前地形重構(gòu)的主要方法有：(1)bezier曲線插值法；(2)最小二乘法；(3)非均勻有理B樣條法；(4)非均勻無理B樣條法。方法(1)擬合的曲線變動一個控制點的位置，將影響到整個曲線的形狀。方法(2)中最小二乘基函數(shù)不容易確定；方法(3)中權(quán)值難以確定，會使曲線的擬合效果很差[2]。本文在方法(4)的基礎(chǔ)上，針對大地形中重點關(guān)注的興趣區(qū)域，應(yīng)用基于線性約束特征點能量優(yōu)化的方法反算控制點。

2.1 算法過程

根據(jù)曲率信息從大量的數(shù)據(jù)點中提取特征點，若將這些特征點當作控制點生成的曲線只能逼近真實地形。為了更準確的表現(xiàn)曲線形狀，不少學者探討了使用最小二乘法反算控制點的方法[2]，但在數(shù)據(jù)量較大時這個方法容易使擬合的曲線波動較大。我們采用了線性約束能量最小化方法反算控制點，該方法能更好地控制曲線的形狀。在曲線形狀細調(diào)方面，找出局部區(qū)間偏差較大的點，通過增加新特征點使生成的曲線更逼真。在二維平面上運用三次準均勻B樣條曲線和線動成面原理生成地形圖。

算法的總體流程圖如圖1所示。

圖1 基于特征點能量優(yōu)化的大地形重構(gòu)算法流程圖

2.2 提取特征點

提取DEM數(shù)據(jù)特征點的目的是在減少模型數(shù)據(jù)點數(shù)情況下，盡量保持原始模型的形狀。點的曲率在曲線形狀描述方面提供了重要信息。在高程數(shù)據(jù)文件中根據(jù)數(shù)據(jù)點的曲率值，提取出曲率變化較大的點作為特征點。提取特征點的過程同時也去除了不重要的數(shù)據(jù)點。從大數(shù)據(jù)集中提取特征點進行曲線擬合，能使得在曲面地形較平坦的區(qū)域提取的特征點較少，反之在復(fù)雜的區(qū)域中提取的特征點較多。

根據(jù)邊緣有序離散點的曲率值提取極值點[5]。對于規(guī)則格網(wǎng)邊緣數(shù)據(jù)的每個點曲率定義為相鄰3個點所構(gòu)成三角形外接圓半徑的倒數(shù)，如圖2所示。即其中 是向量?i之間的夾角，d是向量i的長度

圖2 邊緣點的曲率值

2.3 用線性約束能量最小化方法反求控制點

物體重建的優(yōu)化設(shè)計通常要求對控制點的權(quán)因子調(diào)節(jié)以便優(yōu)化設(shè)計，最小二乘法是較實用的方法。將提取出的特征點作為節(jié)點，應(yīng)用最小二乘法反算出控制點。然而在實際應(yīng)用中，數(shù)據(jù)點和控制點的數(shù)目是經(jīng)常變化的，當數(shù)據(jù)點和控制點數(shù)目十分接近時，最小化問題系統(tǒng)將變得十分不穩(wěn)定且容易使擬合曲線波動增大。在這種情況下使用最小二乘方法就不太適宜。

故本文使用線性約束的能量最小化方法來反求控制點。曲線能量泛函函數(shù)：

其中，非負系數(shù) ， 分別叫做伸縮系數(shù)、彎曲系數(shù)。一般取經(jīng)驗值： = 1 . 0 , = 0 . 2 ；N(k)表示B樣條基函數(shù)的K階導(dǎo)K稱為曲線C(t)的勁度矩陣，由伸縮形式和彎曲形式的加權(quán)和表示為：

K是 (n+ 1 )*(n+1)的帶狀矩陣，帶寬為2p?1。加入線性約束表達式為：AX=Q，其中Q是數(shù)據(jù)點向量，qi(i= 0 ,1,...m)，x是存儲曲線控制點的列向量，A是一個 (m+ 1 )*(n+1)的基函數(shù)數(shù)量矩陣。我們可以通過求最小二次函數(shù)E(X)的方法來求控制點向量X。即：。通過引入列矩陣，將最小化問題轉(zhuǎn)化成求解下列線性系統(tǒng)的問題：由于線性方程是獨立的，系統(tǒng)矩陣是對稱、正定和非奇異的。因此[XV]T有唯一解。即得到B樣條曲線的控制點向量X。由該方法得出的控制點數(shù)少于最小二乘法控制數(shù)點數(shù)，進而使擬合曲線分段數(shù)較少。

2.4 選擇新特征點

使用三次準均勻B樣條曲線逼近特征點擬合得到一條曲線C(t)，找出數(shù)據(jù)點與該曲線上偏差最大的點pi，即，根據(jù)此點所在的局部曲線段尋找新特征點。誤差最大點所在的曲線段至少包含3個點，如：Sm,n是特征點pm，pn所確定的曲線段，滿足|m-n|＞1。對偏差最大點所在的曲線段進行細分，在其中選擇新的特征點。

Park等提出了考慮數(shù)據(jù)點的幾何信息方法來劃分曲線段，定義Sm,n上的形狀指標：(9)， 式(9)中0≤r≤1，Km,n是 曲 線Sm,n的 全 曲 率，，K0,m是 給 定 數(shù)據(jù)點的全曲率逼近，Lm,n表示曲線Sm,n的弦長，進行估計，L0,m表示給定數(shù)據(jù)點的弦長的逼近。r取經(jīng)驗值0.8最適宜，當數(shù)據(jù)點受噪聲影響越大時，權(quán)重r就應(yīng)該越小。運用式(9)求形狀指標的方法，點pl將曲線段Sm,n分成兩個曲線段Sm,l和Sl,n，使得這兩分段的形狀指標是最相似的，即在曲線段Sm,n上選取使得最小的點pl作為新的特征點，將該特征點加入到已有的特征點序列中。

3 實驗結(jié)果

本實驗對分辨率為90m的100行×100列數(shù)據(jù)進行了實驗。構(gòu)成的各曲面各片間是以位置、斜率與曲率連續(xù)為條件，故具有C2級連續(xù)性。圖3是直接將高程數(shù)據(jù)點相連，即采樣前的地形圖。圖4是采用基于特征點能量優(yōu)化B樣條插值的大地形重構(gòu)反算控制點后，進行曲線擬合的三維效果圖。

采用特征點能量優(yōu)化的三次B樣條曲線重構(gòu)大地形，可以完成對大地形中重點關(guān)注區(qū)塊的地形重構(gòu)。當?shù)匦螀^(qū)域變化較劇烈時，該方法能更逼真地表現(xiàn)出實際地形的高低起伏狀況。由三次B樣條曲面的局部性，相鄰四個頂點定義了一段曲線的形狀，因此若改變某一個頂點的位置，其影響的僅僅是局部某段范圍，因此可對起伏不平的局部地形進行調(diào)整，能保證得到較滿意的地形精度。從圖4可得出，經(jīng)過特征點能量優(yōu)化的三次B樣條曲面，三角面片數(shù)多于圖3，從而表現(xiàn)的地形圖也更精確。

圖3 采樣地形

圖4 三次準均勻B樣條擬合地形

4 結(jié)束語

本文提出的基于特征點能量優(yōu)化的樣條插值地形算法，首先提取主特征點，用線性約束能量最小化方法反算出插值這些特征點的控制點，用三次準均勻B樣條曲線逼近控制點，即得到插值主特征點的B樣條曲線。彌補了直接使用雙三次B樣條擬合地形時數(shù)據(jù)量過大的問題；另外本文中使用了插值特征點的方法，而直接使用雙三次B樣條擬合地形是逼近所有數(shù)據(jù)點，所以運用該方法擬合的地形圖更精確、更逼真。另外對擬合出的曲線根據(jù)誤差界范圍找出偏差較大點，通過增加新特征點的方法，更好地調(diào)整了曲線的形狀。

通過測量儀器實測大地地面得到的高程數(shù)據(jù)，受測量儀器和測量方法的影響，數(shù)據(jù)點不可避免地存在誤差，同時特征點的選取是通過曲率信息得到的，由于噪聲影響曲率信息難以準確表達實際地形的變化情況。若對選取的特征點進行去噪，使得算法對噪聲的敏感度降低，這樣能更好的表達出地形實際信息。

[1]周紅梅，王燕銘，劉志剛，等. 基于最少控制點的非均勻有理B樣條曲線擬合[J].西安交通大學學報，2008(6)：73-77.

[2]王棟,高成英,梁云,高月芳，等.基于等式約束最小二乘的B樣條曲線擬合[J].中山大學學報，2008(7)：15-18.

[3]洪瑩，王繼周，李昂.地形特征提取的一種簡易算法[J].測繪科學，2009(6)：125-127.

[4]張立民，鄒容平，李一平，等.基于雙三次B-樣條插值的大地形重構(gòu)[J].煙臺大學學報:自然科學與工程版，2007(12)：2093-2097.

[5]施法中.計算機輔助幾何設(shè)計與非均勻有理B樣條[M].北京：高等教育出版社，2001.

[6]Hyungjun Park，Joo-Haeng Lee.B-spline cruve fitting based on adaptive curve Refinement using dominant point[J].Computer-Aided Design，2007（39）：439-451.

[7]Hyungjun Park.Lofted B-spline surface interpolation by linearly constrained energy mimimizafion[J].Computer Aided Design(S0010-4485),2003,35(1):1261-1268.

[8]Wong Xuea,b，Min Sunc，Ainai Mac.On the reconstruction of three-dimensional complex geological objects using Delaunay triangulation[J].Computer Aided Design ,2004，26(20)：1227–1234.

[9]Li W，Xu S，Zhao G，etal.Adaptive knot placement in B-spline curve approximation[J].Computer Aided Design ,2005，37(8)：791-797.