基于Delaunay三角網(wǎng)的等高線骨架提取算法

魯 剛,王福全

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

基于Delaunay三角網(wǎng)的等高線骨架提取算法

魯 剛,王福全

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

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

Delaunay三角網(wǎng);平三角形;骨架線;等高線

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

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

1 基于Delaunay三角網(wǎng)的等高線骨架提取算法

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

圖1 基于Delaunay三角網(wǎng)提取骨架線的算法流程

1.1 數(shù)據(jù)預(yù)處理

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

1.2 三角形初始化

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

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

1.3 骨架線提取

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

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

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

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

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

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

1.4 主骨架線確定

骨架提取過程中需要確定主骨架線,得到骨架線之間的鄰接關(guān)系。主骨架線主要針對線性結(jié)構(gòu)延展十分明顯的區(qū)域,反映的是骨架線的形態(tài)特征和主延伸方向。從分支三角形開始遍歷中間骨架時,如果兩條分支骨架的后續(xù)骨架都為當(dāng)前遍歷的骨架,但當(dāng)前遍歷骨架的前續(xù)骨架只記錄為兩條分支骨架中的一個。于是,這里的問題就是如何確定兩條分支骨架中哪條作為前續(xù)骨架的取舍標(biāo)準(zhǔn)。

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

2 骨架線高程估計算法

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

2.1 基本骨架線插值

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

2.2 局部地形插值

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

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

對于環(huán)形區(qū)域,如果環(huán)形區(qū)域與外界連通,根據(jù)外界骨架點的高程,內(nèi)插環(huán)形骨架點高程;如果環(huán)形區(qū)域封閉,則根據(jù)環(huán)形區(qū)域外臨近的等高線變化趨勢,估計環(huán)形骨架點的高程值。

3 實驗分析

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

圖2 山地區(qū)域等高線、骨架線、TIN透視圖

4 結(jié)束語

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

[1]李志林,朱慶.數(shù)字高程模型[M],2版.武漢:武漢大學(xué)出版社,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數(shù)據(jù)輔助的山脊線和山谷線提取方法的研究[J].測繪科學(xué),2003,28(4):33-36.

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

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

[6]黃培之.提取山脊線和山谷線的一種新方法[J].武漢大學(xué)學(xué)報:信息科學(xué)版,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三角網(wǎng)模型的等高線地形特征提取及谷地樹結(jié)構(gòu)化組織[J].遙感學(xué)報,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-),男,工程師.

[責(zé)任編輯張德福]