張 振 鑫,鄧 浩,寇 一 丹,張 維,劉 嬪

(1.北京師范大學(xué)地理學(xué)與遙感科學(xué)學(xué)院遙感科學(xué)國家重點實驗室，北京 100875；2.中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南 長沙 410083；3.中南大學(xué)信息科學(xué)與工程學(xué)院,湖南 長沙 410083)

基于ε-Voronoi圖的矢量數(shù)據(jù)自適應(yīng)簡化方法

張 振 鑫1,鄧 浩2,寇 一 丹1,張 維2,劉 嬪3

(1.北京師范大學(xué)地理學(xué)與遙感科學(xué)學(xué)院遙感科學(xué)國家重點實驗室，北京 100875；2.中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南 長沙 410083；3.中南大學(xué)信息科學(xué)與工程學(xué)院,湖南 長沙 410083)

針對矢量數(shù)據(jù)簡化的問題，提出一種基于幀緩存和四叉樹索引的自適應(yīng)簡化方法，即采用四叉樹索引對矢量數(shù)據(jù)進(jìn)行區(qū)域劃分，通過評價各個區(qū)域地物實體分布密度的指標(biāo)，判斷各個區(qū)域內(nèi)的矢量數(shù)據(jù)密度、圖幅寬度，得到各區(qū)域ε-Voronoi圖中的ε值，再借助幀緩存技術(shù)，自適應(yīng)地簡化各個區(qū)域內(nèi)的矢量數(shù)據(jù)。實驗表明，該方法一定程度上提高了簡化質(zhì)量，為矢量數(shù)據(jù)可視化應(yīng)用提供一定的基礎(chǔ)。

四叉樹；幀緩存；自適應(yīng)；簡化

0 引言

隨著硬件平臺及相關(guān)技術(shù)的發(fā)展，人們獲取空間數(shù)據(jù)的能力急劇增長，甚至超出計算機(jī)存儲能力的增長速度。這些數(shù)據(jù)包含大量的空間矢量數(shù)據(jù)，對矢量數(shù)據(jù)的可視化是矢量數(shù)據(jù)應(yīng)用的一個重要方面[1]，矢量數(shù)據(jù)簡化又是空間數(shù)據(jù)可視化研究的重要內(nèi)容。

矢量數(shù)據(jù)簡化研究源于Douglas與Peuker提出的Douglas-Peuker折線簡化法[2],該方法效率較高，且可保持線要素的重要幾何特征，但在簡化過程中會導(dǎo)致拓?fù)潢P(guān)系發(fā)生改變，造成簡化后的線要素可能出現(xiàn)自相交等拓?fù)潢P(guān)系不一致錯誤[3]。Guibas等[4]證明:在避免自相交的情況下，保留盡可能少的點是一個NP-hard問題。Estkowski[5]等在Douglas-Peuker算法的基礎(chǔ)上，采用“繞遠(yuǎn)之路(detour)”的方式避免簡化后的自相交，該算法的時間復(fù)雜度最高為O(n3)，且運行速度較慢；Yang 等[6]采用Visvalingam-Whyattt算法，并結(jié)合約束條件的限制，避免了簡化后的自相交，時間復(fù)雜度為O(nlogn)，但多分辨率空間編碼帶有一定的冗余，影響了簡化效率。文獻(xiàn)[7，8]采用矢量數(shù)據(jù)頂點聚類的方式，即選出每個聚類中的一個點來代替每個聚類中的點，但該方法在避免簡化后線段間的自相交方面仍顯不足。Mustafa 等[9]提出了一種基于ε-Voronoi圖的簡化方法，即通過模板深度緩存，將ε-Voronoi區(qū)域渲染到模板緩存中，再通過模板測試，剔除ε-Voronoi區(qū)域外的點，保證每個要素簡化結(jié)果都位于ε-Voronoi區(qū)域中，一定程度上可避免要素間的相交，但不能避免要素內(nèi)部的自相交，因為每個矢量實體的ε值固定，該簡化方法在靈活性和自適應(yīng)性方面略有欠缺，且沒有考慮待簡化區(qū)域地物分布密集程度對簡化的影響。Yang等[10]通過引進(jìn)單調(diào)鏈[11]，提出了一種基于幀緩存和ε-Voronoi圖的簡化方法，通過剔除模板外不合規(guī)線段進(jìn)行簡化，一定程度上避免了簡化后要素間的相交和每個要素內(nèi)部的自相交，但該方法存在以下問題：1)ε值靈活性不夠，導(dǎo)致不同分布密度的矢量數(shù)據(jù)都在相同的ε值下簡化，進(jìn)而導(dǎo)致生成ε-Voronoi圖較困難，甚至一些矢量地物的ε-Voronoi圖將距離較近的其他矢量實體的ε-Voronoi圖完全覆蓋，導(dǎo)致簡化結(jié)果出現(xiàn)拓?fù)溴e誤；2)借助幀緩存剔除違規(guī)線段，當(dāng)待簡化的矢量數(shù)據(jù)數(shù)量較多時，一些矢量數(shù)據(jù)可能映射到較少甚至幾個像素中，會導(dǎo)致剔除違規(guī)線段時出現(xiàn)異常，簡化結(jié)果出現(xiàn)拓?fù)溴e誤。由于地物空間分布多樣性及復(fù)雜性，亟須一種根據(jù)矢量地物分布疏密程度的自適應(yīng)簡化方法以提高簡化質(zhì)量。

本文提出一種基于幀緩存和四叉樹的矢量數(shù)據(jù)自適應(yīng)簡化方法，通過對矢量數(shù)據(jù)建立四叉樹索引，對區(qū)域進(jìn)行劃分，在評價每個子區(qū)域矢量數(shù)據(jù)密集程度的基礎(chǔ)上，確定每個葉子節(jié)點區(qū)域的ε值，使每個葉子節(jié)點區(qū)域簡化與該區(qū)域的矢量實體分布的密集程度相適應(yīng)，提高簡化質(zhì)量。

1 矢量數(shù)據(jù)區(qū)域劃分

通過建立矢量數(shù)據(jù)的四叉樹索引進(jìn)行區(qū)域劃分。首先，設(shè)定四叉樹葉子節(jié)點中矢量地物數(shù)目閾值，而后以每個矢量地物(polyline或polygon)的最小外包矩形(MBR)中心點為四叉樹劃分的基本點，進(jìn)行四叉樹區(qū)域劃分。為更好地評價各個子區(qū)域的分布密度，需要保證每個葉子節(jié)點區(qū)域的范圍一致，因此，本研究采用完全四叉樹的方式進(jìn)行區(qū)域劃分。設(shè)每個葉子節(jié)點中實體數(shù)目的閾值為m， 矢量數(shù)據(jù)完全四叉樹構(gòu)建的步驟如下：1)遍歷矢量數(shù)據(jù)，統(tǒng)計位于各個子節(jié)點矢量數(shù)據(jù)MBR中心點的數(shù)量γ。2)如果位于所有子節(jié)點矢量數(shù)據(jù)的數(shù)目γ都小于m，則完全四叉樹構(gòu)建完畢；反之，四叉樹深度增加，各個子節(jié)點分裂成4個新的子節(jié)點，重復(fù)執(zhí)行步驟1)，直到所有子節(jié)點中矢量實體的數(shù)目都小于m，四叉樹構(gòu)建完畢，將對應(yīng)的矢量實體劃歸到各個四叉樹葉子節(jié)點中。圖1是閾值為2的完全四叉樹的區(qū)域劃分結(jié)果。

圖1 矢量數(shù)據(jù)的四叉樹劃分

Fig.1 Dividing the vector data by Quadtree

2 基于幀緩存簡化

2.1 矢量實體的εi-Voronoi圖定義

εi-Voronoi圖即具有距離約束條件εi的Voronoi圖，每個εi-Voronoi圖內(nèi)的點到其矢量數(shù)據(jù)對象的最小距離不大于εi值。設(shè)矢量數(shù)據(jù)集合G是由n個矢量實體組成，即g1,g2,…,gn∈G，定義gi的εi-Voronoi圖(簡稱εi-V(gi))為所有到gi的距離不大于εi的點的集合，即εi-V(gi)={p|dist(p,gi)≤dist(p,gj),dist(p,gi)≤εi,i≠j,j=1,2,…,n}，則G的εi-Voronoi圖的集合為εi-V(G)={ε1-V(g1),ε2-V(g2),…,εn-V(gn)}，如圖2所示，ε1、ε2、ε3形成3條矢量地物實體的εi-Voronoi圖的集合。

2.2 自適應(yīng)參數(shù)εi值的計算

本文的自適應(yīng)簡化方法是通過四叉樹葉子區(qū)域的道路分布密度、葉子節(jié)點區(qū)域?qū)挾群蛥?shù)自適應(yīng)地確定εi-Voronoi圖中εi值實現(xiàn)的，過程如下:

圖2 εi-Voronoi圖示意

Fig.2εi-Voronoi diagram

首先，設(shè)計衡量各個葉子節(jié)點區(qū)域矢量數(shù)據(jù)密度(σi)的方法：

(1)

其中:ki代表第i個葉子節(jié)點包含的所有矢量數(shù)據(jù)映射到幀緩存后各個矢量數(shù)據(jù)對應(yīng)像素的數(shù)目總和；Si代表第i個葉子節(jié)點區(qū)域映射到幀緩存后該區(qū)域所覆蓋的像素數(shù)目；kimax是第i個葉子節(jié)點進(jìn)一步四分后(圖3虛線分割后的區(qū)域)各個子區(qū)域像素數(shù)目的最大值；kimin是第i個葉子節(jié)點四分后，子區(qū)域中地物投影到幀緩存后像素數(shù)目的最小值。

圖3 葉子節(jié)點四分示意

Fig.3 Leaf nodes of the quad-tree

接著，取各個葉子節(jié)點區(qū)域密度的最大值σm,再將每個葉子節(jié)點區(qū)域的密度與σm的比值作為每個葉子節(jié)點區(qū)域的相對密度δi，即:

(2)

這樣，每個葉子節(jié)點中的各矢量元素的εi值為:

εi=δi×di×α

(3)

α表示提前設(shè)定的參數(shù)，di是第i個葉子節(jié)點的圖幅寬度。δi越大，表示地物越密集。圖4是不同葉子節(jié)點下的矢量數(shù)據(jù)分布密度示意圖。

2.3 矢量數(shù)據(jù)的簡化

圖4 葉子節(jié)點矢量地物分布密度示意

Fig.4 The density of vector data in each leaf node

圖5 單調(diào)鏈?zhǔn)疽?/p>

Fig.5 Monotone chain diagram

圖6 εi-Voronoi圖區(qū)域、合規(guī)線段(短虛線)和違規(guī)線段(長虛線)

Fig.6εi-Voronoi diagram,compliance line and irregular line

圖7 線要素的簡化過程

Fig.7 The procedure of line object simplification

3 實驗驗證與分析

3.1 數(shù)據(jù)集

表1是本研究所采用的數(shù)據(jù)集,該數(shù)據(jù)集的空間分布存在一定差異性，要素之間存在著較為復(fù)雜的拓?fù)鋷缀侮P(guān)系。

表1 數(shù)據(jù)集

Table 1 Datesets

數(shù)據(jù)集序號名稱類型要素個數(shù)節(jié)點數(shù)目1中國縣級區(qū)劃圖polyline113336097322北京市交通圖polyline155155955366

3.2 與其他方法對比

采用本文方法得到簡化結(jié)果,并與文獻(xiàn)[10]的方法進(jìn)行對比(圖8、圖9)。本文方法的四叉樹閾值設(shè)為100，α初始值設(shè)為0.005。本方法(圖8b)與采用文獻(xiàn)[10]的方法(圖8c)得到的簡化結(jié)果相比，更好地保持了簡化前的拓?fù)潢P(guān)系，在文獻(xiàn)[10]的方法下，一些較復(fù)雜區(qū)域的簡化出現(xiàn)簡化后相交的拓?fù)溴e誤問題，本文方法可很好地保持原始數(shù)據(jù)的拓?fù)潢P(guān)系。對數(shù)據(jù)集2(圖9a)，在立交橋區(qū)域，與文獻(xiàn)[10]的方法(圖9c)得到的結(jié)果相比，本文方法(圖9b)能夠更好地保持立交橋的原始形態(tài)特征及道路間的連通關(guān)系，得到更高質(zhì)量的簡化結(jié)果。

圖8 數(shù)據(jù)集1的簡化結(jié)果及對比

Fig.8 The result and comparison of simplification about dataset 1

上述是從直觀、可視的角度進(jìn)行的對比，為了全面評價兩種方法的簡化結(jié)果，首先，對簡化后的數(shù)據(jù)出現(xiàn)拓?fù)洚惓５那闆r進(jìn)行說明，即簡化后各個簡化實體內(nèi)部或?qū)嶓w間與簡化前不一致，稱之為異常。接著，對簡化后矢量數(shù)據(jù)發(fā)生拓?fù)洚惓５膶嶓w數(shù)目和簡化后的實體節(jié)點數(shù)目總和進(jìn)行統(tǒng)計(表2)。從表2可以看出，本文方法分別對數(shù)據(jù)集1和數(shù)據(jù)集2簡化后出現(xiàn)的拓?fù)洚惓嶓w數(shù)目為33和920，文獻(xiàn)[10]的方法對數(shù)據(jù)集1和數(shù)據(jù)集2簡化后出現(xiàn)的拓?fù)洚惓嶓w數(shù)目為420和3 370，本文方法在保持實體簡化拓?fù)湔_性方面有明顯優(yōu)勢；在簡化后剩余節(jié)點數(shù)方面，本文方法對數(shù)據(jù)集1和數(shù)據(jù)集2簡化后的實體節(jié)點數(shù)目總和分別為423 500和507 873，而文獻(xiàn)[10]的方法對數(shù)據(jù)集1和數(shù)據(jù)集2簡化后的實體節(jié)點數(shù)目總和分別為366 321和429 564，再結(jié)合圖8b和圖9b可以看出，本文方法簡化后保留更多節(jié)點以避免發(fā)生拓?fù)洚惓！?/p>

圖9 數(shù)據(jù)集2的簡化結(jié)果及對比

Fig.9 The result and comparison of simplification for dataset 2

表2 兩種方法簡化結(jié)果的統(tǒng)計對比

Table 2 Statistical comparison of simplification results using two methods

數(shù)據(jù)集本文方法文獻(xiàn)[10]中的方法簡化后拓?fù)洚惓５膶嶓w數(shù)目剩余節(jié)點數(shù)簡化后拓?fù)洚惓５膶嶓w數(shù)目剩余節(jié)點數(shù)13342350042036632129205078733337429564

3.3 算法效率

本算法測試的硬件環(huán)境為：Intel Core i7-4770，cpu ：3.4 GHz和8 G的RAM。軟件環(huán)境：操作系統(tǒng)為32位的Windows 7，集成開發(fā)環(huán)境是Visual C2010。對本方法的效率進(jìn)行了測試，對數(shù)據(jù)集1的簡化時間為143 s，數(shù)據(jù)集2的簡化時間為119 s，以上測試是在單機(jī)串行的環(huán)境下進(jìn)行的。

3.4 參數(shù)的敏感性測試

算法測試采用兩組參數(shù)，第一組：四叉樹劃分閾值分別為50、100、150、200，α為0.005；第二組：四叉樹劃分閾值為100，α分別為0.003、0.005、0.007、0.009。本次測試以簡化后矢量數(shù)據(jù)拓?fù)涞恼_率為測試標(biāo)準(zhǔn)，這里，矢量數(shù)據(jù)出現(xiàn)簡化拓?fù)溴e誤有以下幾種情況：簡化前數(shù)據(jù)間相交，簡化后不相交；簡化前數(shù)據(jù)間不相交，簡化后相交；簡化前數(shù)據(jù)內(nèi)部不相交，簡化后相交；簡化前數(shù)據(jù)內(nèi)部相交，簡化后不相交。從圖10可以看出，當(dāng)四叉樹索引閾值為100時，得到較高的簡化正確率，說明這兩套數(shù)據(jù)在四叉樹索引閾值是100時，簡化效果較好。從圖11可得，隨著α值的增大，簡化后具有正確拓?fù)潢P(guān)系的矢量數(shù)據(jù)逐漸減少，這是由于隨著α值增加，εi值隨之增加，導(dǎo)致較少的線段被判斷為違規(guī)線段，簡化程度較大，出現(xiàn)簡化后拓?fù)溴e誤的矢量數(shù)據(jù)數(shù)目也隨之增加。

圖10 不同四叉樹劃分閾值下的正確率測試

Fig.10 Accuracy rate test in different thresholds of Quadtree construction

圖11 不同α值下的正確率測試

Fig.11 Accuracy rate test in differentαvalue

4 結(jié)論

本研究基于矢量數(shù)據(jù)的完全四叉樹索引構(gòu)建子區(qū)域，提出了葉子節(jié)點子區(qū)域的數(shù)據(jù)分布密度評價指標(biāo)，各個葉子節(jié)點區(qū)域根據(jù)各自的密度進(jìn)行自適應(yīng)簡化，并通過與前人的方法對比可以看出，在簡化質(zhì)量上，本文方法有一定的提高，尤其是對空間分布差異較大的數(shù)據(jù)簡化效果更好。后續(xù)工作將考慮采用并行方式，通過對并行簡化框架的設(shè)計，將本方法進(jìn)行并行化實驗，進(jìn)一步提高簡化效率。

[1] GOODCHILD M F.Geographical information science[J].International Journal of Geographical Information Systems,1992,6(1):31-45.

[2] DOUGLAS D H,PEUCKER T K.Algorithms for the reduction of the number of points required to rep resent a digitized line or its caricature[J].The Canadian Cartographer,1973,10(2):112-122.

[3] ZHAN H S,LI G X.Progressive transmission of vector map data based on polygonal chain simp lification[J].Lecture Notes in Computer Science,2006,4282:908-917.

[4] GUIBAS L J,HERSHBERGER J,MITCHELL J,et a1．Approximating polygons and subdivisions with minimum link paths[J]．Lecture Notes in Computer Science,1993(3):383-415.

[5] ESTKOWSKI N,MITCHELL J S B.Simplifying a polygonal subdivision while keeping it simple[A].Proceedings of the 17th ACM Symposium on Computational Geometry[C].2001.40-49.

[6] YANG B,PURVES R,WEIBEL R.Efficient transmission of vector data over the Internet[J].International Journal of Geographical Information Science,2007,21(2):215-237.

[7] RAPOSO P.Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation[J].Cartography and Geographic Information Science,2013,40(5):427-443.

[8] 李進(jìn),馬勁松,沈婕,等.一種基于頂點聚類的線要素簡化算法改進(jìn)[J].測繪科學(xué)技術(shù)學(xué)報,2013,30(5):525-529.

[9] MUSTAFA N,KRISHNAN S,VARADHAN G,et al.Dynamic simplification and visualization of large maps[J].International Journal of Geographical Information Science,2006,20(3):273-302.

[10] YANG L,ZHANG L,MA J,et al.Efficient simplification of large vector maps rendered onto 3D landscapes[J].Computer Graphics and Applications,IEEE,2011,31(2):14-23.

[11] CHANDRU V,RAJAN V T,SWAMINATHAN R.Monotone pieces of chains[J].ORSA Journal on Computing,1992,4(4):439-446.

[12] HOFF III K E,KEYSER J,LIN M,et al.Fast computation of generalized Voronoi diagrams using graphics hardware[A].Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques[C].ACM Press/Addison-Wesley Publishing Co.,1999.277-286.

An Adaptive Simplification Method on Vector Data Based onε-Voronoi

ZHANG Zhen-xin1,DENG Hao2,KOU Yi-dan1,ZHANG Wei2,LIU Bin3

(1.State Key Laboratory of Remote Sensing Science,School of Geography and RS,Beijing Normal University,Beijing 100875;2.School of Geosciences and Info-Physics，Central South University，Changsha 410083;3.School of Information Science and Engineering,Central South University,Changsha 410083,China)

In this paper,an adaptive method that performs simplification of vector data using frame buffer and quad-tree index is presented.Firstly,indicators to evaluate vector data density are proposed,then the tolerance parameter (ε) ofε-Voronoi diagram is gotten by the vector data density and width of each region.In the end,the vector data is adaptively simplified with the technology of frame buffer.The result of experiment indicates that our method improves the quality of simplification quality,and provides some bases for visualization of vector data.

quad-tree;frame buffer;adaptive;simplification

2015-03-20；

2015-10-19

湖南省博士后科研資助專項計劃(2014RS4028);國家自然科學(xué)基金項目(41401532)

張振鑫(1986-),男,博士研究生,從事空間信息可視化算法研究。E-mail:zhenxin066@163.com

10.3969/j.issn.1672-0504.2016.01.006

P283；P208

A

1672-0504(2016)01-0029-05