多分辨率小波分析在GIS線狀要素簡化中的應用

黃 娟,程耀東

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

多分辨率小波分析在GIS線狀要素簡化中的應用

黃 娟,程耀東

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

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

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

0 引言

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

1 線狀要素的化簡原則

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

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

2 多分辨率小波分析原理與 GIS圖形數據的多尺度表達

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

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

(1)單調性:對 Πj∈Z,有Vj

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

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

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

2.2 基于小波分析的GIS圖形數據多尺度表達[8- 10]

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

2.3 多分辨分析與線狀要素的關系

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

設比例尺為1:M的GIS圖形曲線用l=f(x)來表示,對此曲線采用有限點進行逼近,得到離散化表達式{f(xi)}, i=1,2,…,再經過適當的插值和一系列坐標變換,其離散化表達式將變為V0={f(n)},n=1,2,…,2N。

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

又V1=V2+W2,則

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

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

3.1 基于傳統小波分析的線狀要素簡化[11]

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

圖1 曲線分解圖

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

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

(1)利用小波分析對線狀要素進行壓縮優化。

①取三系數的小波基,對原數據L0進行小波分解,得到低頻部分數據 f1(x)和高頻部分數據 g1(x);

②選取適當的閾值ω,如果|g1(x)|>ω,則為特征點,并將特征點插入到 f1(x),否則為冗余點,直接去掉;

③把插入了特征點的低頻部分數據 f1(x),作為一次小波變換后的數據L1。

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

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

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

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

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

若ρi+1<ρm,則 pm就是比pi+1奇異性更大的數據點,在L1中用點 pm代替 pi+1。

小波變換后的數據L1經過上述處理,將會去掉其中的非特征點,補回原數據L0中丟失的特征點,從而使線狀要素得到真正的壓縮優化。

4 實例分析

基于上述算法原理和步驟,結合地圖數據表達的特點,下面對一原始等高線圖形進行試驗,圖2為原始數據,有1 672個點,圖3為經小波分析處理的壓縮數據,有531個數據點,壓縮比為31.76%,圖4為處理前后的疊加數據。

圖2 原始數據

圖3 處理后的數據

圖4 處理前后的疊加數據

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

5 結束語

本文利用小波分析的多分辨率分析原理,給出了小波分析與GIS圖形數據多尺度表達的關系,提出了一種將多分辨率分析,Douglas算法和曲率分析相結合的一種新型算法,實現了線狀數據的壓縮優化。隨著制圖自動綜合理論與技術的不斷完善,多小波的多分辨率分析將在間線狀要素制圖綜合中發揮重要的作用。

[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].武漢測繪科技大學學報,1998,23(1):52-56.

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

[6] 關履泰.小波方法與應用[M].北京:高等教育出版社, 2007.7:54-93.

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

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

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

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

[11] 吳紀桃,王橋.小波分析在 GIS線狀數據圖形簡化中的應用研究[J].測繪學報,2000,29(1):71-75.

(責任編校:李高峰)

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

國家自然科學基金(40871208)

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