多分辨率小波分析在GIS線狀要素簡化中的應(yīng)用

黃 娟,程耀東

(蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院,蘭州 730070))

多分辨率小波分析在GIS線狀要素簡化中的應(yīng)用

黃 娟,程耀東

(蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院,蘭州 730070))

線要素化簡一直是自動(dòng)制圖綜合中的重要研究內(nèi)容。利用小波分析的多分辨率原理和Douglas算法,對(duì)線狀要素進(jìn)行平滑和綜合,實(shí)現(xiàn)了線狀要素的空間多尺度表達(dá)。并對(duì)實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn),結(jié)果表明,此方法不僅能夠達(dá)到曲線化簡的目的,而且能夠保持化簡前后的視覺效果和原始數(shù)據(jù)的特征。

小波分析;小波多分辨率分析;Douglas算法;線狀要素

0 引言

空間數(shù)據(jù)的多尺度表達(dá)問題是GIS研究的重點(diǎn),也是地圖自動(dòng)綜合的瓶頸。地圖矢量數(shù)據(jù)都可用線狀圖形來表達(dá),這就使得多尺度研究的焦點(diǎn)主要集中在線要素自動(dòng)簡化模型的建立。許多學(xué)者已經(jīng)對(duì)此問題做了大量的研究,Li Zhi-lin和Openshaw(1992)提出的基于客觀綜合的自然規(guī)律的線劃要素化簡的方法[1];VisvaLingam和Whyatl(1993)提出的基于最小面積的重復(fù)式點(diǎn)刪除方法[2];Salfeld(1999)提出的基于邏輯一致的Douglas算法[3];郭慶勝(2002)提出的漸進(jìn)式化簡算法[4];武芳(2002)提出的基于遺傳算法的線要素化簡算法[5]等。線化簡的算法雖然很多,但很多都不能有效保留原始曲線的形態(tài)結(jié)構(gòu)特征且曲線的光滑度差,造成化簡前后曲線形態(tài)歪曲。本文在研究小波分析的多分辨率分析原理的基礎(chǔ)上,將小波分解后的頻域分析和Douglas算法相結(jié)合,建立一種線要素簡化的新模型,并對(duì)實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn),對(duì)簡化前后的數(shù)據(jù)作比較,結(jié)果表明,該方法適合于線狀要素?cái)?shù)據(jù)簡化,能夠很好的保持原始數(shù)據(jù)的結(jié)構(gòu)特征。

1 線狀要素的化簡原則

線狀要素是地圖上大量存在的最基本的地圖要素,它的綜合主要包含兩個(gè)方面:數(shù)量的選取和形狀的化簡。在手工制圖的情況下,形狀的化簡主要依靠人的大腦和感官的作用,來把握它的形狀結(jié)構(gòu)特征,從而根據(jù)線劃化簡的基本原則對(duì)其進(jìn)行綜合處理。

在大比例尺的地圖綜合中,線要素的化簡作為同一線劃在不同尺度下圖形的再表達(dá),在選取一個(gè)有效的化簡算法的同時(shí),還要遵循地圖制圖的一些基本原則。其基本原則為:①保持彎曲形狀的基本特征,即總的圖形的相似性;②保持彎曲的特征轉(zhuǎn)折點(diǎn)的精確性;③保持不同彎曲程度的對(duì)比。

2 多分辨率小波分析原理與 GIS圖形數(shù)據(jù)的多尺度表達(dá)

2.1 多分辨率小波分析原理[67]

定義:設(shè)L2(R)是一平方可積函數(shù)空間,{Vj,j∈Z}是L2(R)的一列函數(shù)子空間,R是實(shí)數(shù)集,Z是整數(shù)集,若{Vj,j∈Z}滿足

(1)單調(diào)性:對(duì) Πj∈Z,有Vj

(3)獨(dú)立性:∩Vj={0};

(4)縮放性:f(x)∈VjΖf(2x)∈Vj+1;

設(shè)以Wj表示分解中的高頻部分Dj,Vj表示分解中的底頻部分Aj,則Wj是Vj在Vj+1中的正交補(bǔ),即

2.2 基于小波分析的GIS圖形數(shù)據(jù)多尺度表達(dá)[8- 10]

基于小波的特點(diǎn),將平方可積空間L2(R)看成某地理空間,f(x)看成該空間的各種信息,則{Vj,j∈Z}可看成L2(R)在不同比例尺即不同分辨率下的地理空間模型,{Wj, j∈Z}則為相應(yīng)的細(xì)節(jié)信息;也就是說,如果將空間L2(R)看成某地理空間在特定比例尺下的GIS圖形數(shù)據(jù)模型,f(x)是其上圖形要素,{Vj,j∈Z}則可看成在沒有進(jìn)行相應(yīng)的比例尺縮小變換情形下的多比例尺GIS圖形數(shù)據(jù)模型。在應(yīng)用中,設(shè)L2(R)=V0,可把從V0出發(fā),把尺度函數(shù)(X)表示成V1,V2,…,Vj的過程,可以看成是一種比例尺的 GIS圖形數(shù)據(jù)模型V0,派生出多比例尺GIS圖形數(shù)據(jù)模型V1,V2,…,Vj的過程,此過程實(shí)際上是一種基于多分辨率分析的GIS圖形數(shù)據(jù)的表達(dá)過程。在自動(dòng)綜合過程中,一般要分要素或分內(nèi)容進(jìn)行,不失一般性,不妨我們?cè)O(shè)V0只包含一種圖形要素,如線狀要素 y=f(x)。

2.3 多分辨分析與線狀要素的關(guān)系

定義:設(shè)L2(R)是一平方可積函數(shù)空間,{Vm,m∈Z}是L2(R)的一列函數(shù)子空間,R是實(shí)數(shù)集,Z是整數(shù)集,若{Vm, m∈Z}滿足:

設(shè)比例尺為1:M的GIS圖形曲線用l=f(x)來表示,對(duì)此曲線采用有限點(diǎn)進(jìn)行逼近,得到離散化表達(dá)式{f(xi)}, i=1,2,…,再經(jīng)過適當(dāng)?shù)牟逯岛鸵幌盗凶鴺?biāo)變換,其離散化表達(dá)式將變?yōu)閂0={f(n)},n=1,2,…,2N。

式(5)右邊的第一項(xiàng)是曲線l=f(x)在V1中的表達(dá)式,記作A1f(x),第二項(xiàng)是曲線l=f(x)相對(duì)于V1在V0中的細(xì)節(jié)信息,記作W1f(x)。

又V1=V2+W2,則

式(6)右邊的第一項(xiàng)是曲線l=f(x)在V2中的表達(dá)式,記作A2f(x),第二項(xiàng)是曲線l=f(x)相對(duì)于V2在V1中的細(xì)節(jié)信息,記作W2f(x)。因此一般地,有曲線l=f(x)在Vm中的表達(dá)式Amf(x)和其在Vm-1中的細(xì)節(jié)信息Wmf(x),即

3 基于小波分析的線要素簡化

3.1 基于傳統(tǒng)小波分析的線狀要素簡化[11]

用正交小波的分解公式(3),對(duì)一線狀要素 f(x)進(jìn)行小波分解,如圖1,得到低頻部分 f1(x)和高頻部分 g1(x),顯然,f1(x)保留了原始曲線的總體輪廓特征,因此 f1(x)可看做 f(x)的近似逼近,而傳統(tǒng)方法就是把 f1(x)作為 f(x)的壓縮數(shù)據(jù),但此方法將線狀要素的所有點(diǎn)包括特征點(diǎn),發(fā)生了位移的變化,這將使原地性線,地貌形狀結(jié)構(gòu)特征遭到破壞。高頻部分 g1(x)卻包含著 f(x)的主要特征信息,在高頻部分的數(shù)據(jù)中,絕對(duì)值較大的部分對(duì)應(yīng)著原始數(shù)據(jù)中奇異性較大的數(shù)據(jù)點(diǎn),即線狀要素中特征點(diǎn)所在的位置,接近于零的部分對(duì)應(yīng)著原始數(shù)據(jù)中奇異性非常小的數(shù)據(jù)點(diǎn),即線狀要素中一些冗余數(shù)據(jù)點(diǎn)所在的位置,去掉冗余點(diǎn),可達(dá)到壓縮優(yōu)化原曲線的目的。

圖1 曲線分解圖

3.2 基于小波分析的Douglas算法簡化線狀要素

為了找回原數(shù)據(jù)L0中的特征點(diǎn),去掉壓縮數(shù)據(jù)L1中的非特征點(diǎn),使線狀要素得到真正的壓縮優(yōu)化,可將小波分解后的域頻分析,Douglas算法以及曲率分析相結(jié)合。具體算法如下。

(1)利用小波分析對(duì)線狀要素進(jìn)行壓縮優(yōu)化。

①取三系數(shù)的小波基,對(duì)原數(shù)據(jù)L0進(jìn)行小波分解,得到低頻部分?jǐn)?shù)據(jù) f1(x)和高頻部分?jǐn)?shù)據(jù) g1(x);

②選取適當(dāng)?shù)拈撝郸?如果|g1(x)|>ω,則為特征點(diǎn),并將特征點(diǎn)插入到 f1(x),否則為冗余點(diǎn),直接去掉;

③把插入了特征點(diǎn)的低頻部分?jǐn)?shù)據(jù) f1(x),作為一次小波變換后的數(shù)據(jù)L1。

(2)再次處理L0中的數(shù)據(jù)。

在L1中,把介于間隔數(shù)據(jù) pi,pi+2之間L0中的數(shù)據(jù),用Douglas算法,求出 pi,pi+2中的特征點(diǎn) pm(即 pm為到直線pipi+2距離最遠(yuǎn)的點(diǎn))。

(3)計(jì)算 pi+1,pm的曲率。

首先求出點(diǎn) pi+1,pm到直線pipi+2的距離 di+1,dm,并求出|pipi+2|的長度 d,然后計(jì)算點(diǎn) pi+1,pm的曲率,即

(4)比較曲率 pi+1,pm的大小,篩選特征點(diǎn) pi+1和 pm。

若ρi+1<ρm,則 pm就是比pi+1奇異性更大的數(shù)據(jù)點(diǎn),在L1中用點(diǎn) pm代替 pi+1。

小波變換后的數(shù)據(jù)L1經(jīng)過上述處理,將會(huì)去掉其中的非特征點(diǎn),補(bǔ)回原數(shù)據(jù)L0中丟失的特征點(diǎn),從而使線狀要素得到真正的壓縮優(yōu)化。

4 實(shí)例分析

基于上述算法原理和步驟,結(jié)合地圖數(shù)據(jù)表達(dá)的特點(diǎn),下面對(duì)一原始等高線圖形進(jìn)行試驗(yàn),圖2為原始數(shù)據(jù),有1 672個(gè)點(diǎn),圖3為經(jīng)小波分析處理的壓縮數(shù)據(jù),有531個(gè)數(shù)據(jù)點(diǎn),壓縮比為31.76%,圖4為處理前后的疊加數(shù)據(jù)。

圖2 原始數(shù)據(jù)

圖3 處理后的數(shù)據(jù)

圖4 處理前后的疊加數(shù)據(jù)

由實(shí)驗(yàn)可知,該方法適合于制圖綜合的線狀要素的處理和應(yīng)用,通過實(shí)驗(yàn)結(jié)果得出,先用小波分析的多分辨率分析將曲線分解為高頻部分和低頻部分,然后判斷高頻部分的數(shù)據(jù)是否為特征點(diǎn),若是,則將特征點(diǎn)插入到低頻部分?jǐn)?shù)據(jù)f1(x),得到壓縮數(shù)據(jù)L1,最后利用Douglas算法對(duì)壓縮數(shù)據(jù)L1進(jìn)行再處理,得到最終的數(shù)據(jù)L0。在處理過程中,為了保證曲線的基本形態(tài)不發(fā)生變化,本文采用保留端點(diǎn)處的信息,僅對(duì)中間的數(shù)據(jù)進(jìn)行處理。通過疊加可以看出簡化后的視覺效果和精度。

5 結(jié)束語

本文利用小波分析的多分辨率分析原理,給出了小波分析與GIS圖形數(shù)據(jù)多尺度表達(dá)的關(guān)系,提出了一種將多分辨率分析,Douglas算法和曲率分析相結(jié)合的一種新型算法,實(shí)現(xiàn)了線狀數(shù)據(jù)的壓縮優(yōu)化。隨著制圖自動(dòng)綜合理論與技術(shù)的不斷完善,多小波的多分辨率分析將在間線狀要素制圖綜合中發(fā)揮重要的作用。

[1] Zhilin Li,Stan Openshaw.Algorithms for automated line generalization based on a natural principle of objective generalization[J].Geographical Information Systems,1992,6(5):373-389.

[2] M.Visvalingam,J.D.Whyatt.Line generalization by repeated elimination of the smallest area[J].The Cartographic Journal,1993,30(1):46-51.

[3] Salfeld A.Topologically consistent line simplification with the douglas-peuker algorithm.Cartography and Geographic Institute Science,26(1):7-18.

[4] 郭慶勝.線狀要素圖形綜合的漸進(jìn)方法研究[J].武漢測繪科技大學(xué)學(xué)報(bào),1998,23(1):52-56.

[5] 武芳,錢海忠,鄧紅艷,等.面向地圖自動(dòng)綜合的空間信息智能處理[M].北京:科學(xué)出版社,2008,164-170.

[6] 關(guān)履泰.小波方法與應(yīng)用[M].北京:高等教育出版社, 2007.7:54-93.

[7] 邸繼佂.小波分析原理[M].北京:科學(xué)出版社,2010: 77-93.

[8] 吳凡,祝國瑞.基于小波分析的地貌多尺度表達(dá)與自動(dòng)綜合[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2001,26(2):170 -174.

[9] 吳紀(jì)桃,王橋.小波理論用于地圖數(shù)據(jù)處理中若干理論問題的探討[J].測繪學(xué)報(bào),2002,31(3):2452-248.

[10] 宋衛(wèi)衛(wèi),朱順剛,歐宗瑛,等.基于形狀相似性和曲線化簡的統(tǒng)計(jì)形狀模型建立[J].光電子·激光,2008, 19(9):1231-1235.

[11] 吳紀(jì)桃,王橋.小波分析在 GIS線狀數(shù)據(jù)圖形簡化中的應(yīng)用研究[J].測繪學(xué)報(bào),2000,29(1):71-75.

(責(zé)任編校:李高峰)

Application of Multi-Resolution Wavelet Analysis in GISL inear Element Simplification

HUANGJuan,CHENG Yao-dong
(School of Mathematics,Physics and Software Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

Simplifying linear elements is always the important research in automatic drawing generalization.With the principle of multi-resolution analysis and Douglas algorithm,linear elements have been smoothed and synthesized and finally linear element spatial multi-scale expression is realized. The results show that this method can not only achieve the purpose of simplifying the curve but also maintain visual effect and the characteristics of linear elements before and after simplification.

wavelet analysis;wavelet multi-resolution fatio analysis;Douglas algorithm; linear element

P208;P283.7

A

1672-349X(2010)06-0013-04

2010-10-15

國家自然科學(xué)基金(40871208)

黃娟(1983-),女,碩士研究生,主要從事多尺度地理空間單線目標(biāo)的相似度描述與計(jì)算模型的研究。