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

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

?

矢量地圖數(shù)據(jù)簡化研究進(jìn)展

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

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

摘要：從傳統(tǒng)矢量數(shù)據(jù)簡化算法及基于并行技術(shù)的矢量數(shù)據(jù)簡化算法兩方面進(jìn)行分析，將當(dāng)前傳統(tǒng)的矢量數(shù)據(jù)簡化算法：Douglas-Peuker的簡化算法及演化、Li-OpenShaw簡化算法及演化、漸進(jìn)式的簡化算法及演化、基于小波理論的簡化算法及演化和簡化質(zhì)量的評價，在基于并行技術(shù)簡化算法研究的基礎(chǔ)上，指出矢量數(shù)據(jù)并行簡化和簡化算法的智能化、感知化、自動化是矢量數(shù)據(jù)簡化研究發(fā)展的趨勢。

關(guān)鍵詞：矢量數(shù)據(jù)；簡化；算法；并行

矢量數(shù)據(jù)是GIS領(lǐng)域一種重要的數(shù)據(jù)[1]，尤其是ESRI公司推出shapefile格式的文件后，矢量數(shù)據(jù)的應(yīng)用性和普及性越來越廣泛。對矢量數(shù)據(jù)的可視化是地理信息科學(xué)領(lǐng)域研究的一個重要方向[2]，矢量數(shù)據(jù)的可視化關(guān)系到矢量數(shù)據(jù)應(yīng)用的廣度與深度、關(guān)系到?jīng)Q策者的決策能力、關(guān)系到科研成果的優(yōu)劣。矢量數(shù)據(jù)的簡化又是矢量數(shù)據(jù)可視化中的一個重要研究方向[3]。

從矢量數(shù)據(jù)簡化的實現(xiàn)方式上看，矢量數(shù)據(jù)簡化可分為基于并行計算模式和串行計算模式2種，隨著計算機技術(shù)的提高及計算機計算能力的增強，以前基于串行的數(shù)據(jù)處理算法已不能滿足科研和應(yīng)用的需要，因此，基于并行技術(shù)的數(shù)據(jù)處理算法應(yīng)運而生[4]。本文先對當(dāng)前傳統(tǒng)的、基于串行計算的國內(nèi)外矢量數(shù)據(jù)簡化算法研究現(xiàn)狀進(jìn)行總結(jié)，再對國內(nèi)外矢量數(shù)據(jù)并行簡化研究現(xiàn)狀進(jìn)行論述，通過本文的研究，可初步獲得國內(nèi)外關(guān)于矢量數(shù)據(jù)簡化的研究進(jìn)展情況，對矢量數(shù)據(jù)可視化的研究有一定的參考價值。

1傳統(tǒng)的矢量數(shù)據(jù)簡化算法

由于計算機發(fā)展水平的限制，傳統(tǒng)的矢量數(shù)據(jù)簡化算法大多基于串行計算模式。

1.1Douglas-Peuker簡化算法及其演化

對矢量地圖的簡化研究最早開始于1973年，Douglas與Peuker提出了Douglas-Peuker折線簡化法，即先將矢量折線首、尾點相連，再計算其他點到該線段的距離，取距離中的最大值，若最大距離不大于閾值，則將該線段中間曲線的其他點舍去，以該條線段代表曲線；若最大距離大于閾值，則將該點與首、尾點各自相連，形成兩條新的線段，再以各新形成的線段為基線，遞歸搜索，直到所有線段間曲線上所有點的距離都在閾值范圍內(nèi)[5]。該算法效率較高，且可保持線要素的重要幾何特征。但在簡化過程中會導(dǎo)致拓?fù)潢P(guān)系發(fā)生改變，造成簡化后的線要素出現(xiàn)拓?fù)潢P(guān)系不一致，容易導(dǎo)致自相交[6]。Guibas等證明如何在避免自相交的情況下保留盡可能少的點是一個NP-hard問題[7]。Saalfeld在Douglas-Peuker簡化算法的基礎(chǔ)上，提出拓?fù)湟恢滦员３值氖噶繑?shù)據(jù)簡化算法[8]。Mustafa等提出一種基于Douglas-Peuker算法和ε-Voronoi圖的簡化方法，即通過模板深度緩存，將Voronoi區(qū)域渲染到模板緩存中，再通過模板測試，剔除ε-Voronoi區(qū)域外的點，保證每個要素簡化結(jié)果都位于ε-Voronoi區(qū)域中，能夠一定程度上避免要素間的相交，但不能避免要素內(nèi)部的自相交，由于ε固定，不具有靈活性和自適應(yīng)性，簡化的區(qū)域受地物分布密集程度的限制[9]。

1.2Li-OpenShaw簡化算法及其擴(kuò)展

Li-OpenShaw算法是一種基于自然現(xiàn)實的自適應(yīng)化簡算法，可以得到較好的化簡結(jié)果，這種方法借助于滑動圓，使滑動圓在曲線上滑動，通過對曲線上的節(jié)點重采樣，得到簡化后的采樣點，達(dá)到矢量數(shù)據(jù)簡化的目的[10]。通過控制滑動圓的大小，來達(dá)到不同尺度下的簡化結(jié)果，這種方法具有多尺度的靈活性，但該方法未考慮極大值的曲線點與多條曲線相交的問題。針對上述問題，朱鯤鵬等提出Li-OpenShaw算法的改進(jìn)方法，主要解決多條線相交于一條曲線的極大值點問題[11]。Raposo在基于自然原則的Li-Openshaw簡化算法基礎(chǔ)上，在Nyquist-Shannon采樣理論的控制下，生成六邊形來完成矢量數(shù)據(jù)簡化，與基于四邊形的簡化方法相比，這種方法在保持簡化目標(biāo)的形狀特征方面有著明顯優(yōu)勢，但六邊形的生成與處理需要消耗一定時間，在大規(guī)模數(shù)據(jù)的簡化方面有一定的限制[12]。

1.3漸進(jìn)式的簡化算法及其演變

郭慶勝提出一種基于線特征的漸進(jìn)式化簡算法，通過查找線結(jié)構(gòu)的極值點、拐點、凸點及單調(diào)區(qū)間等建立線數(shù)據(jù)的分層結(jié)構(gòu)特征進(jìn)行簡化[13]。Poorten提出利用Delaunay三角形進(jìn)行曲線綜合簡化，利用三角形之間的連通關(guān)系，維護(hù)曲線簡化前后的拓?fù)湟恢滦訹14]。艾廷華等提出一種曲線彎曲程度的二叉樹表達(dá)方法，提出曲線彎曲層次的概念，以曲線為約束構(gòu)建三角網(wǎng)，依據(jù)三角形與頂點、曲線的關(guān)系對三角形進(jìn)行分類；依據(jù)三角形的類型，通過剝皮算法，根據(jù)剝皮過程，將曲線劃分為二叉樹組織結(jié)構(gòu)，再根據(jù)彎曲的層次結(jié)構(gòu)，將曲線化簡[15]。杜維等提出一種基于組合優(yōu)化策略的多邊形簡化方法[16]。操震洲等利用預(yù)先存儲的節(jié)點偏移量化簡曲線，利用單調(diào)鏈求交的方式實現(xiàn)多分辨率下化簡曲線，從而維護(hù)拓?fù)湟恢滦?達(dá)到漸進(jìn)式曲線化簡的目的[17]。

1.4基于小波分析的矢量數(shù)據(jù)簡化算法

利用小波理論也可對矢量數(shù)據(jù)進(jìn)行化簡。小波分析理論具有多分辨率分析數(shù)據(jù)的特性，可用于數(shù)據(jù)的多分辨率分析與表達(dá)，且具有正交性、對稱性、短支撐性和高階消失矩等特性[18]。吳紀(jì)桃等建立小波理論與矢量數(shù)據(jù)多尺度簡化的關(guān)系模型，并從數(shù)學(xué)角度給出該模型的適用情況[19-20]。一些學(xué)者將其他一些理論同小波理論結(jié)合協(xié)調(diào)進(jìn)行矢量數(shù)據(jù)簡化。Saux將B-spline理論與小波理論結(jié)合，對一些待平滑的區(qū)域進(jìn)行平滑簡化[21]。吳凡利用小波理論，結(jié)合Mallat[22]算法，通過建立尺度一致性約束模型，忽略兩個整數(shù)尺度間的次要因素，實現(xiàn)任意兩個整數(shù)比例尺度下線狀數(shù)據(jù)的近視簡化[23]。朱長青等基于小波分析理論，針對等高線數(shù)據(jù)，論述不同尺度下的矢量數(shù)據(jù)簡化、綜合的方法，采用Douglas-Peuker簡化算法，提取小波變換后的邊界特征點，再在數(shù)據(jù)簡化完成后恢復(fù)特征點，保持矢量數(shù)據(jù)間的拓?fù)湟恢滦訹24-25]。王明常等基于小波理論，利用線狀要素的極角變化，以達(dá)到平滑的方式進(jìn)行簡化，突出簡化前后的視覺效果和精度[26]。

1.5矢量數(shù)據(jù)簡化質(zhì)量評估研究現(xiàn)狀

關(guān)于矢量數(shù)據(jù)的簡化精度包括兩個方面：幾何精度和屬性精度[27]。武芳等基于化簡后曲線幾何特征及單點位置變化的特點，提出評價簡化質(zhì)量的方法。幾何特征評價指標(biāo)包括線的長度比、曲折度；點位置變化評價包括位移標(biāo)準(zhǔn)差、位置誤差和緩沖區(qū)限差等[28]。劉鵬程等提出一種基于對偶面傅立葉形狀描述子的相似性評價指標(biāo)，以傅立葉形狀描述子作為一個向量，以向量的歐式距離來度量簡化前后向量的相似程度[29]。Weibel研究矢量數(shù)據(jù)簡化中約束條件，包括幾何約束(如寬度、長度等)、拓?fù)浼s束(如簡化前后實體間的拓?fù)潢P(guān)系一致性等)、結(jié)構(gòu)約束(如簡化后道路不要壓到實體等)、Gestalt約束(如需要保持平滑的線性地物化簡前后要保持平滑一致性等)[30]。朱鯤鵬等在Weibel提出的約束條件基礎(chǔ)上，提出一種滿足約束條件的矢量數(shù)據(jù)簡化質(zhì)量評估方法，通過比較簡化前后的光滑性、位置和點位位移，定量地得到簡化效果的評價指標(biāo)[31]。

2基于并行計算的矢量數(shù)據(jù)可視化

基于并行計算的矢量數(shù)據(jù)簡化主要將傳統(tǒng)矢量數(shù)據(jù)簡化算法與多核計算機或計算機集群相結(jié)合，通過對負(fù)載均衡、任務(wù)均衡的設(shè)計來完成快速并行簡化的目的。并行計算的方式包括：基于共享內(nèi)存的并行方式、基于消息傳遞的并行方式和數(shù)據(jù)并行的方式等[32]。

2.1基于共享內(nèi)存的矢量數(shù)據(jù)簡化算法

隨著計算機多核技術(shù)的提高，基于共享內(nèi)存方式的并行越來越普及，與基于消息傳遞的并行方式相比，基于共享內(nèi)存的矢量數(shù)據(jù)簡化方法實現(xiàn)效率較高[4]。馬勁松等采用單機多核的方式進(jìn)行Douglas-Peucker簡化算法的并行實現(xiàn)研究，并在此基礎(chǔ)上完成地圖線要素的實時綜合，該研究得出，采用多核并行的方式，Douglas-Peucker算法的效率大幅度提高[33]。張立強等基于OpenMP和GPU并行手段，通過對數(shù)據(jù)加載、數(shù)據(jù)簡化及數(shù)據(jù)顯示的并行策略設(shè)計，研究大規(guī)模矢量數(shù)據(jù)的并行可視化方法[34]。

2.2基于消息傳遞的矢量數(shù)據(jù)簡化算法

基于消息傳遞的矢量數(shù)據(jù)簡化方式主要采用MPI(Message Passing Interface)[35]并行的方式，基于MPI并行簡化的優(yōu)點是程序移植性好、擴(kuò)展性高，缺點是開發(fā)人員需要控制計算任務(wù)的分配與傳輸，并行實現(xiàn)成本較高。沈婕等基于消息傳遞方式，采用多種簡化方式，對等高線簡化的適宜性進(jìn)行研究，構(gòu)建基于MPI的等高線并行簡化處理過程，論述數(shù)據(jù)的分發(fā)及合并、通信方式與計算過程3個重要問題[36]。

2.3基于數(shù)據(jù)并行方式的矢量數(shù)據(jù)簡化算法

數(shù)據(jù)并行即通過對數(shù)據(jù)的分區(qū)，在每個區(qū)域內(nèi)同時執(zhí)行相同的操作，以完成并行處理的目的[37]。由于這種并行方式需要從數(shù)據(jù)的本身劃分出發(fā)，需要考慮劃分的均衡性和一致性，大部分?jǐn)?shù)據(jù)不適用于這種方式并行實現(xiàn)，因此，相關(guān)研究較少。張棟海等利用MapReduce在計算機集群上進(jìn)行Douglas-Peuker算法的并行實驗，算法的核心是數(shù)據(jù)的劃分，通過MapReduce將劃分的結(jié)果分配到集群的各個節(jié)點上。該研究得出，在大數(shù)據(jù)量、高復(fù)雜度情況下利用集群并行簡化效率更高[38]。

3矢量數(shù)據(jù)簡化的未來發(fā)展方向探討

3.1矢量數(shù)據(jù)簡化的實時性和實效性不斷提高

矢量數(shù)據(jù)簡化中的實時性和實效性是矢量數(shù)據(jù)可視化優(yōu)劣的一個重要指標(biāo)[39-40]。隨著數(shù)據(jù)采集能力的日漸提高，數(shù)據(jù)量日益增大。對矢量數(shù)據(jù)可視化對科學(xué)研究和工程應(yīng)用尤為重要[41]。并行技術(shù)與矢量數(shù)據(jù)簡化的結(jié)合，不僅體現(xiàn)在簡化過程的并行，而且還體現(xiàn)在數(shù)據(jù)輸入、處理和輸出的并行[34]。通過對并行模式下矢量數(shù)據(jù)簡化的研究，極大地提高了矢量數(shù)據(jù)可視化的質(zhì)量與效率，基于并行技術(shù)的矢量數(shù)據(jù)簡化難點在于合理、高效的并行方案的設(shè)計與實現(xiàn)。基于并行計算的矢量數(shù)據(jù)簡化是矢量數(shù)據(jù)簡化實時性和實效性提高的突破口和途徑。

3.2矢量數(shù)據(jù)的簡化與綜合向一體化方向發(fā)展

矢量數(shù)據(jù)綜合是指根據(jù)表達(dá)的詳細(xì)程度，恰當(dāng)?shù)厣釛壊恢匾脑兀Ａ糁匾氐倪^程[42]。矢量數(shù)據(jù)的簡化、綜合要以數(shù)據(jù)表現(xiàn)的尺度而定，對不同比例尺下的簡化，簡化模型要與綜合模型相適應(yīng)，達(dá)到簡化與綜合一體化的表達(dá)空間數(shù)據(jù)的效果，解決這個問題的關(guān)鍵在于研制健全的、多尺度的、基于語義信息和拓?fù)湫畔⒌暮喕Ｐ?，使其不僅能夠由復(fù)雜數(shù)據(jù)得到分層次的簡化數(shù)據(jù)，而且能夠由簡化數(shù)據(jù)還原回的多層次的較復(fù)雜數(shù)據(jù)，同時，還應(yīng)探究矢量數(shù)據(jù)綜合程度與簡化程度之間的關(guān)系。

3.3矢量數(shù)據(jù)的簡化更加智能化、感知化

矢量數(shù)據(jù)的簡化向更加智能化、感知化方向發(fā)展[43]，該趨勢與機器學(xué)習(xí)、人工智能、模式識別等學(xué)科關(guān)系密切。一方面，讓計算機根據(jù)語義信息、尺度信息、拓?fù)湫畔⒌?，判定簡化的程度，再根?jù)語義信息、空間信息、拓?fù)湫畔⒌鹊淖兓?，以滿足人類視覺認(rèn)知需要為出發(fā)點，實時地改變簡化尺度，這種簡化尺度的變化是線性或非線性的。另一方面，采用機器學(xué)習(xí)和模式識別的方式，將每個線狀要素智能化、可認(rèn)知化，通過對用戶使用信息的學(xué)習(xí)，得到線狀要素對象本身的簡化經(jīng)驗參數(shù)，將經(jīng)驗參數(shù)參與到簡化中，得到更好的簡化效果，這種經(jīng)驗參數(shù)包括從簡化質(zhì)量檢查中得到的經(jīng)驗(包括錯誤元素序號、位置、錯誤元素節(jié)點序號、錯誤類型等)，將簡化結(jié)果以一種打分的定量化形式，被線性實體所學(xué)習(xí)，在下一次的簡化過程中，這些經(jīng)驗成為約束條件，控制錯誤的發(fā)生。

這種智能感知的簡化方式可以應(yīng)用在未來的無人駕駛和無人機監(jiān)測等領(lǐng)域中[44]。如在無人駕駛研究中，控制智能汽車通過傳感器[45]獲知道路實時信息，這些初始獲得的數(shù)據(jù)是柵格形式的，而智能汽車決策行使路線時，基于矢量的線性數(shù)據(jù)，由柵格數(shù)據(jù)提取矢量道路特征。而從柵格數(shù)據(jù)中得到的矢量道路數(shù)據(jù)復(fù)雜度高，包括多個節(jié)點、拐點，為滿足決策效率的需要，需將這些矢量數(shù)據(jù)簡化，此時，基于智能感知的簡化是必不可少的，這種簡化需要根據(jù)智能汽車對道路實際空間的認(rèn)知以及已經(jīng)積累的經(jīng)驗來協(xié)同、實時地完成。

4結(jié)論

矢量數(shù)據(jù)簡化的效率與數(shù)據(jù)拓?fù)潢P(guān)系之間的矛盾。當(dāng)前，矢量數(shù)據(jù)的簡化大都只考慮矢量數(shù)據(jù)集的每個個體元素[46]，從個體角度出發(fā)，進(jìn)行個體元素的簡化，而沒有考慮矢量數(shù)據(jù)個體間的拓?fù)潢P(guān)系，但若考慮個體間拓?fù)涞谋３?，則會導(dǎo)致簡化過程較多時間的開銷，影響簡化效率。這就需要在簡化效率與要素間拓?fù)浔３址矫鎸で笃胶?，即如何在簡化效率影響不大的情況下盡可能地保持要素間的拓?fù)潢P(guān)系，解決這個問題，需從算法本身和硬件兩方面著手，算法本身來說，研制更加高效合理的簡化算法；硬件角度來說，利用多核計算機及計算機集群，采用并行計算的模式加以解決。

雖然很多學(xué)者對矢量數(shù)據(jù)的簡化已經(jīng)研究多年，但還不能徹底提出一個適用于各種類型的矢量數(shù)據(jù)的簡化方法，原因如下：

1)數(shù)據(jù)的復(fù)雜性與多樣性：矢量數(shù)據(jù)的空間拓?fù)潢P(guān)系異常復(fù)雜，如多條矢量數(shù)據(jù)相交、兩個地物的多個部分相交等，而這種現(xiàn)象在各種類型的矢量數(shù)據(jù)中是非常常見的，如立交橋的矢量數(shù)據(jù)等。

2)受計算機發(fā)展及應(yīng)用水平的限制：雖然并行技術(shù)已經(jīng)相對較成熟，但該技術(shù)實現(xiàn)的難度較大，如需要考慮I/O均衡、負(fù)載均衡等，缺少一種更加方便的技術(shù)模式來支持并行技術(shù)在矢量數(shù)據(jù)簡化方面的應(yīng)用。需要研究一種支持串行與并行兼容的數(shù)據(jù)結(jié)構(gòu)，減少數(shù)據(jù)通信時時間的開銷，該數(shù)據(jù)結(jié)構(gòu)需滿足低冗余和低數(shù)據(jù)復(fù)雜性，且該數(shù)據(jù)結(jié)構(gòu)能滿足多層次、實時性和易于計算機認(rèn)知的需要。

參考文獻(xiàn)：

[1]龔健雅.地理信息系統(tǒng)基礎(chǔ)[M].北京：科學(xué)出版社，2001.

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

[3]Zhang L，Zhang L，Ren Y，et al.Transmission and visualization of large geographical maps[J].ISPRS Journal of Photogrammetry and Remote Sensing，2011，66(1):73-80.

[4]陳國良．并行算法的設(shè)計與分析[M]．北京：高等教育出版社，2002.

[5]Douglas D H，Peucker T K.Algorithms for the reduction of thenumber of points required to rep resent a digitized line or itscaricature[J].The Canadian Cartographer，1973，10(2):112-122.

[6]Zhan H S,Li G X.Progressive transmission of vectormap data basedon polygonal chain simplification[J].Lecture Notes in ComputerScience，2006，4282:908-917.

[7]GUIBAS L J，HERSHBERGER J，MITCHELL J，etal．Approximating polygons and subdivisions with minimum linkpaths[J]．Lecture Notes in Computer Science，1993，3：383—415.

[8]Saalfeld A.Topologically consistent line simplification with the Douglas-Peuckeralgorithm[J].Cartography and Geographic Information Science，1999，26(1):7-18.

[9]Mustafa N，Krishnan S，Varadhan G，etal. Dynamic simplification and visualization of large maps[J].International Journal of Geographical Information Science，2006，20(3):273-302.

[10] Li Z，Openshaw S.Algorithms for automated line generalization based on a natural principle of objective generalization[J].International Journal of Geographical Information Systems，1992，6(5):373-389.

[11] 朱鯤鵬，武芳，王輝連，等.Li-Openshaw算法的改進(jìn)與評價[J].測繪學(xué)報，2007，36(4):450-456.

[12] Raposo P.Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation[J].Cartography and Geographic Information Science，2013 (ahead-of-print):1-17.

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

[14] Poorten P，Jones C B.Customisable line generalization using delaunay triangulation[C]//CD-Rom Proceedings of the 19th ICC，Ottawa，Section.1999，8.

[15] 艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá)[J].測繪學(xué)報，2001，30(4):343-348.

[16] 杜維，艾廷華，徐崢.一種組合優(yōu)化的多邊形化簡方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2004，29(6):548-550.

[17] 操震洲，李滿春，程亮，等.適用于網(wǎng)絡(luò)漸進(jìn)傳輸?shù)亩喾直媛是€生成算法[J].計算機應(yīng)用，2013，33(3):688-690.

[18] 崔錦泰，程正興.小波分析導(dǎo)論[M].西安：西安交通大學(xué)出版社，1995.

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

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

[21] SAUX E.B-spline functions and wavelets for cartographic line generalization[J].Cartography and geographic information science，2003，30(1):33-50.

[22] MALLAT S G.A theory for multiresolution signal decomposition:the wavelet representation[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1989，11(7):674-693.

[23] 吳凡.基于小波分析的線狀特征數(shù)據(jù)無級表達(dá)[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2004，29(6):488-491.

[24] 朱長青，王玉海，李清泉，等.基于小波分析的等高線數(shù)據(jù)壓縮模型[J].中國圖像圖形學(xué)報，2004，9(7)：841-845.

[25] 王玉海，朱長青.基于小波分析的線狀要素壓縮優(yōu)化的綜合性研究[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2007，32(7):630-632.

[26] 王明常，谷蘭英，王宇，等.小波變換理論的線狀要素制圖綜合研究[J].吉林大學(xué)學(xué)報(地球科學(xué)版)，2005(S1).

[27] 史文中.空間數(shù)據(jù)與空間分析不確定性原理[M].北京：科學(xué)出版社，2005.

[28] 武芳，朱鯤鵬.線要素化簡算法幾何精度評估[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2008，33(6):600-603.

[29] 劉鵬程，羅靜，艾廷華，等.基于線要素綜合的形狀相似性評價模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2012，37(1):114-117.

[30] WEIBEL R.Generalization of spatial data:Principles and selected algorithms[M]//Algorithmic foundations of geographic information systems.Springer Berlin Heidelberg，1997:99-152.

[31] 朱鯤鵬，武芳，陳波，等.基于約束條件的線要素化簡算法質(zhì)量評估[J].測繪科學(xué)，2007,32(3):28-30.

[32] 安虹，陳崚.并行算法實踐[M].北京：高等教育出版社，2004.

[33] 馬勁松，沈婕，徐壽成.利用 Douglas-Peucker并行算法在多核處理器上實時綜合地圖線要素[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2011，36(12):1423-1426.

[34] 張立強，徐翔，譚繼強.基于并行技術(shù)的大規(guī)模矢量地圖可視化方法[J].地理與地理信息科學(xué)，2013，29(4):9-12.

[35] 張武生，薛巍，李建江，等.MPI并行程序設(shè)計實例教程[M].北京：清華大學(xué)出版社，2009.

[36] 沈婕，郭立帥，朱偉，等.消息傳遞接口環(huán)境下等高線簡化并行計算適宜性研究[J].測繪學(xué)報，2013，42(4):621-628.

[37] LIN C，SNYDER L.Principles of parallel programming[M].Addison-Wesley Publishing Company，2008.

[38] 張棟海，黃麗娜，劉暉，等.基于MapReduce的多機并行 DP 算法與實驗分析[J].地球信息科學(xué)學(xué)報，2013(1):55-60.

[39] CORCORAN P，MOONEY P，WINSTANLEY A.Planar and non-planar topologically consistent vector map simplification[J].International Journal of Geographical Information Science，2011，25(10):1659-1680.

[40] 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.

[42] 毋河海.地圖綜合基礎(chǔ)理論與技術(shù)方法研究[M].北京：測繪出版社，2004.

[43] 王家耀.地圖制圖學(xué)與地理信息工程學(xué)科發(fā)展趨勢[J].測繪學(xué)報，2010，39(2):115-119.

[44] BISHOP C M，NASRABADI N M.Pattern recognition and machine learning[M].New York:springer，2006.

[45] 李德仁，龔健雅，邵振峰.從數(shù)字地球到智慧地球[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2010(2):127-132.

[46] 溫永寧，閭囯年，陳旻.矢量空間數(shù)據(jù)漸進(jìn)傳輸研究進(jìn)展[J].地理與地理信息科學(xué)，2011，27(6):6-12.

[47] 姚靜.基于ArGIS的大比例尺矢量電子地圖制圖研究[J].測繪與空間地理信息，2015,38(6)：135-136.

[48] 周琛，陳振杰，黃秋昊，等.多核并行環(huán)境中矢量數(shù)據(jù)格式的轉(zhuǎn)換算法[J].測繪科學(xué)，2015，40(7)：118-122+130.

[責(zé)任編輯：李銘娜]

An overview of vector map data simplification researchZHANG Zhenxin1，ZHANG Wei2，LIU Bin3，KOU Yidan1，DENG Hao2

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

Abstract：Vector data simplification is an important content of its visualization.In this paper，the traditional vector data simplification algorithms and paralleled vector data simplification algorithms are analyzed，and the present traditional vector data algorithms include:Douglas-Peukersimplification algorithm and its evolutionary，Li-OpenShawsimplification algorithm and its evolution，progressive simplification and its evolution，and wavelet-based theory and its evolution and simplification quality value.Based on parallel simplification algorithm，it points out that the parallel simplification and intelligence，perception，and automation of simplification are the tendency of vector data simplification development.

Key words：vector data；simplification；algorithm；parallel

中圖分類號：P283；P208

文獻(xiàn)標(biāo)識碼：A

文章編號：1006-7949(2016)06-0010-05

作者簡介：張振鑫(1986-)，男，博士研究生.

基金項目：國家自然科學(xué)基金資助項目(41401532)

收稿日期：2015-03-27；修回日期：2015-08-04