基于Delaunay三角網的等高線骨架提取算法

魯 剛,王福全

(嘉興市規劃設計研究院有限公司,浙江 嘉興 314050)

基于Delaunay三角網的等高線骨架提取算法

魯 剛,王福全

(嘉興市規劃設計研究院有限公司,浙江 嘉興 314050)

根據等高線數據直接建立不規則三角形網絡模型往往會在山頂、山底、山脊和山谷等特殊地區出現“平三角形”,導致模型失真。文中基于Delaunay三角網,通過對“平三角形”的處理,提取骨架線,并結合地形特征估計其高程值。實驗證明該算法能夠有效地提取各種地形骨架線,對于建立逼真的數字地面模型和進行數字地形分析具有重要應用價值。

Delaunay三角網;平三角形;骨架線;等高線

地形骨架線信息對于地形表面的逼真模擬和數字地形分析如地貌單元劃分和水文分析等具有十分重要的價值[1-2]。傳統地面測量和攝影測量中的選擇性采樣都通過采集骨架線信息來確保地形模擬的質量和提高工作效率。而一般等高線和 Grid形式的數字高程模型(DEM)往往不再記錄這些特征信息[3-4]。如果沒有骨架信息約束,根據等高線數據直接建立不規則三角形網絡模型往往會在山頂、山底、山脊和山谷等特殊地區出現“平三角形”,導致模型失真。

消除這種“平三角形”導致的模型失真,一種最有效的方法就是增加輔助信息[5-6]。而從等高線數據中自動提取出骨架線和特征點等則是主要的途徑[5-6]。隨著大量已有等高線數據的廣泛應用,從等高線中提取骨架線的研究日益重要。

1 基于Delaunay三角網的等高線骨架提取算法

Delaunay三角形廣泛用于地圖綜合、鄰近關系處理、分布范圍搜尋等[7]。將等高線作為約束線段建立Delaunay三角網是從等高線生成 TIN模型的常用方法[1]。為了消除平三角形,首先根據等高線生成的Delaunay三角網,從平三角形出發,利用三角形的相鄰關系,跟蹤出彎曲部分骨架所要經過的三角形,取其經過邊的中點作為骨架點,最后將這些點連接骨架線,進而估算獲得這些骨架點的高程值,最后再補充到原始數據中重新建立約束Delaunay TIN。基于Delaunay三角網提取骨架線的算法流程如圖1所示:①等高線數據生成約束Delaunay三角網;②三角形初始化,提取葉骨架;③提取中間骨架、鞍部骨架和環形骨架,確定主骨架;④骨架線高程估計。

圖1 基于Delaunay三角網提取骨架線的算法流程

1.1 數據預處理

目前,大量的等高線數據是由現存的地形圖數字化及后處理得到,在對柵格數據進行矢量掃描的過程中難免出現一些錯誤[7-8],為了下一步確定三角形類型的需要,保障算法的穩定,必須對等高線數據進行預處理,將等高線上除起始點外的重復數據剔除。然后將等高線作為約束線段建立Delaunay三角網。

1.2 三角形初始化

首先在初始三角網中根據平三角形三個頂點高程值相同的特點搜索平三角形,并根據三角形的連通性即骨架線穿越的三角形邊的條數確定三角形的類型。三角形連通性判斷標準如下:①骨架線不可能與等高線相交,所以三角形的邊若位于等高線上,則該邊不可能有骨架線通過。②三角形某條邊鄰接的三角形為平三角形,在滿足標準①的條件下,該邊必定有骨架線通過。

由此將初始三角網內的三角形分為四類:第一類:一條邊有骨架線通過的三角形,這類三角形為骨架線的起始或終止三角形。其中的平三角形,被稱為葉子三角形,是葉骨架的起始三角形;而非平三角形可能是鞍部骨架的起始三角形或者骨架的終止三角形。第二類:兩條邊有骨架線通過的三角形。第三類:三條邊都有骨架線通過的三角形,即分支三角形,骨架線匯合與此類三角形。最常出現的情況是兩段骨架線在該類三角形匯合,然后骨架線從第三條邊相鄰的三角形延伸;在山頂或山谷最內圈等高線區域內,分支三角形是骨架線的終止三角形,即有三條不同方向的骨架線終止于該三角形的三邊。第四類:其他的三角形沒有骨架線通過,這類三角形所在區域地形表面模擬較為準確,因此本文不考慮這類三角形所在區域的骨架提取。

1.3 骨架線提取

本文算法的基本思想是沿起始三角形非等高線邊遍歷平三角形,直到非平三角形或者分支三角形為止。在骨架線中順序記錄經過的每一個三角形,將兩三角形公共邊的中點作為骨架點,完成一條骨架線的三角形遍歷。在這個過程中,除了遍歷三角形提取骨架點之外,還應記錄與其鄰接的骨架線。具體流程如下:

1)處理平三角形,計算當前三角形骨架前進方向所在邊對應角的大小,若角度超過一定閾值如120°,則該三角形不再作為骨架三角形;若角度在閾值范圍內,記錄骨架線起始點,進入其鄰接的三角形:如果當前三角形是第一類三角形,表示一條骨架線已經遍歷完成,記錄骨架線終止點。對于短小骨架,比如其遍歷三角形只有兩個,且無前續、后續骨架線,則剔除該條骨架線;如果當前三角形是第二類三角形,繼續行進的方向就是唯一的,記錄骨架點,進入相應的鄰接三角形;如果當前三角形是第三類三角形,則繼續前進的方向就有兩種可能,這時一條葉骨架遍歷完成。

2)處理分支三角形集中已處理兩次的三角形。確定兩條分支中的主骨架線后,以當前分支三角形為起始三角形。

3)提取鞍部骨架,其起始三角形為第一類三角形中還未處理的非平三角形。

4)最后提取環形骨架,其起始三角形為分支三角形集中只處理過一次的三角形。

經過上述處理,普通平地形骨架線、鞍部骨架線及與外部連通環形骨架線都能得到正確處理,因為在處理分支三角形生成中間骨架線的過程中,新的骨架可能還會在另外的分支三角形處停止,因此,這里總是處理分支三角形集中第一個滿足條件的三角形,循環中間骨架跟蹤過程,直到滿足條件的三角形數目為0。

1.4 主骨架線確定

骨架提取過程中需要確定主骨架線,得到骨架線之間的鄰接關系。主骨架線主要針對線性結構延展十分明顯的區域,反映的是骨架線的形態特征和主延伸方向。從分支三角形開始遍歷中間骨架時,如果兩條分支骨架的后續骨架都為當前遍歷的骨架,但當前遍歷骨架的前續骨架只記錄為兩條分支骨架中的一個。于是,這里的問題就是如何確定兩條分支骨架中哪條作為前續骨架的取舍標準。

本文結合這兩方面考慮,但主骨架的確定屬于空間認知的內容,是一個不確定性問題,選取的標準并不是唯一的,要根據具體的情況來調整。同時,有一些分支骨架長度、寬度都相當,這時選擇其中任何一個都可。根據骨架線順序經過的三角形,依次將骨架點相連,即可得到骨架線。

2 骨架線高程估計算法

要將上述骨架線插入三角網消除平三角形,每個點都應具有正確的高程信息。需要利用骨架線與等高線之間的相互關系來估計高程值。對于兩條等高線之間骨架線高程估計的基本思想是:根據骨架線上起始點及終止點的高程值,線性內插所遍歷的骨架線上的所有點的高程。對于骨架線存在于等高線內部,沒有其他參考點時,例如山頂,往往假設山頂中間一點為最高點,但實際情況中,山頂不一定是中間取極值,有可能偏于某一邊,也有可能存在多處極值。所以,山頂的插值過程最好能由山頂本身的形狀、骨架幾何特性、周圍局部地形來處理。

2.1 基本骨架線插值

內插出主骨架上各點的高程值后,按同樣的方法內插出該主骨架所有分支骨架上各個骨架點的高程,只是骨架線的起始點或終止點為內插得到的點,而非原等高線上存在的離散點。

2.2 局部地形插值

對于山頂、山谷及鞍部區域,骨架線起始點和終止點高程值會出現相等的情況,即|Zl-Zf|=0,且等高線內部沒有其他參照點。本文算法考慮局部地形變化,利用骨架產生的幾何性質,將這類區域的骨架線高程估計分為如下兩步:

首先,由于地形表面的連續性及山頂性質相似性,局部小區域內可認為地形表面一側幾近于線性變化,因此相鄰近的兩點處地形表面的斜率相近(或者帶有小許偏差α,α可由實際地形狀況決定)。然后,根據上述方法得到山頂或鞍部區域插值結果,判斷出該區域的最高點,以此點為基礎,沿骨架線對其他骨架點進行擬合。上述兩步既考慮到高程估計的合理性,又考慮到地形的連續性,使地形模擬更接近真實情況。

對于環形區域,如果環形區域與外界連通,根據外界骨架點的高程,內插環形骨架點高程;如果環形區域封閉,則根據環形區域外臨近的等高線變化趨勢,估計環形骨架點的高程值。

3 實驗分析

為了驗證上述算法的正確性和有效性,選擇山地類等高線圖進行了實驗,結果分別如圖2所示。可見,由于骨架線信息的正確提取和高程估算,最終的 TIN模型都逼真地表達了實際地形特征。

圖2 山地區域等高線、骨架線、TIN透視圖

4 結束語

將具有高程值的骨架線插入三角網中可以消除原Delaunay三角網中存在的平三角形,改善地形模擬的準確性。而一些明顯不合理的骨架線通常是由等高線的斷裂或賦值錯誤造成的,因此,通過對等高線骨架的處理還可以輔助監測等高線數據中存在的錯誤。

[1]李志林,朱慶.數字高程模型[M],2版.武漢:武漢大學出版社,2003.

[2]GüLGEN F.,G?KG?Z T..Automatic extraction of terrain skeleton lines from digital elevationmodels[J].International A rchieves of Photogrammetry Remote Sensing and Spatial Info rmation Sciences,2004,35(3):372-377.

[3]劉澤慧,黃培之.DEM數據輔助的山脊線和山谷線提取方法的研究[J].測繪科學,2003,28(4):33-36.

[4]陳仁喜,龍毅.顧及三角形處理的 TIN建立算法[J].武漢大學學報:信息科學版,2003,28(5):619-622.

[5]眭海剛,朱慶.一種從DLG生成高質量DEM的混合方式[J].測繪通報,2001(4):16-18.

[6]黃培之.提取山脊線和山谷線的一種新方法[J].武漢大學學報:信息科學版,2001,26(3):247-252.

[7]GOLD C.M.,SNOEYINK J..A one-step crust and skeleton extraction algo rithm[J].Algorithmica,2001,30:144-163.

[8]艾廷華,祝國瑞,張根壽.基于Delaunay三角網模型的等高線地形特征提取及谷地樹結構化組織[J].遙感學報,2003,7(4):292-299.

Skeleton extraction algorithm based on the Delaunay triangulation of contour lines

LU Gang,WANG Fu-quan
(Jiaxing Planning&Resarch Institute Co.,L td.,Jiaxing 314050,China)

By means of the contour lines to construct the triangulated irregular netwo rk(TIN)model,the“flat triangles”are usually generated at the significant topographical areas such as hilltop,ridge,o r valley,w hich results in the distortion of the digital terrainmodeling.In thispaper,aiming at the p rocessing of“flat triangles”,the algorithm for skeleton extraction and elevation evaluation from the contour lines based on the Delaunay triangulation is introduced.Experimental resultsp rove that various skeletons can be correctly extracted,w hich are useful to the realistic digital terrain modeling and corresponding digital terrain analysis.

Delaunay triangulation;flat triangle;skeleton;contour lines

P23;P208

A

1006-7949(2010)06-0013-04

2009-09-28

魯 剛(1978-),男,工程師.

[責任編輯張德福]