張振鑫,張 維,劉 嬪,寇一丹,鄧 浩
(1.北京師范大學(xué) 地理學(xué)與遙感科學(xué)學(xué)院遙感科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100087;2.中南大學(xué) 地球科學(xué)與信息物理學(xué)院,湖南 長(zhǎng)沙 410083;3.中南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙 410083)
?
矢量地圖數(shù)據(jù)簡(jiǎn)化研究進(jìn)展
張振鑫1,張維2,劉嬪3,寇一丹1,鄧浩2
(1.北京師范大學(xué) 地理學(xué)與遙感科學(xué)學(xué)院遙感科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100087;2.中南大學(xué) 地球科學(xué)與信息物理學(xué)院,湖南 長(zhǎng)沙 410083;3.中南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙 410083)
摘要:從傳統(tǒng)矢量數(shù)據(jù)簡(jiǎn)化算法及基于并行技術(shù)的矢量數(shù)據(jù)簡(jiǎn)化算法兩方面進(jìn)行分析,將當(dāng)前傳統(tǒng)的矢量數(shù)據(jù)簡(jiǎn)化算法:Douglas-Peuker的簡(jiǎn)化算法及演化、Li-OpenShaw簡(jiǎn)化算法及演化、漸進(jìn)式的簡(jiǎn)化算法及演化、基于小波理論的簡(jiǎn)化算法及演化和簡(jiǎn)化質(zhì)量的評(píng)價(jià),在基于并行技術(shù)簡(jiǎn)化算法研究的基礎(chǔ)上,指出矢量數(shù)據(jù)并行簡(jiǎn)化和簡(jiǎn)化算法的智能化、感知化、自動(dòng)化是矢量數(shù)據(jù)簡(jiǎn)化研究發(fā)展的趨勢(shì)。
關(guān)鍵詞:矢量數(shù)據(jù);簡(jiǎn)化;算法;并行
矢量數(shù)據(jù)是GIS領(lǐng)域一種重要的數(shù)據(jù)[1],尤其是ESRI公司推出shapefile格式的文件后,矢量數(shù)據(jù)的應(yīng)用性和普及性越來(lái)越廣泛。對(duì)矢量數(shù)據(jù)的可視化是地理信息科學(xué)領(lǐng)域研究的一個(gè)重要方向[2],矢量數(shù)據(jù)的可視化關(guān)系到矢量數(shù)據(jù)應(yīng)用的廣度與深度、關(guān)系到?jīng)Q策者的決策能力、關(guān)系到科研成果的優(yōu)劣。矢量數(shù)據(jù)的簡(jiǎn)化又是矢量數(shù)據(jù)可視化中的一個(gè)重要研究方向[3]。
從矢量數(shù)據(jù)簡(jiǎn)化的實(shí)現(xiàn)方式上看,矢量數(shù)據(jù)簡(jiǎn)化可分為基于并行計(jì)算模式和串行計(jì)算模式2種,隨著計(jì)算機(jī)技術(shù)的提高及計(jì)算機(jī)計(jì)算能力的增強(qiáng),以前基于串行的數(shù)據(jù)處理算法已不能滿足科研和應(yīng)用的需要,因此,基于并行技術(shù)的數(shù)據(jù)處理算法應(yīng)運(yùn)而生[4]。本文先對(duì)當(dāng)前傳統(tǒng)的、基于串行計(jì)算的國(guó)內(nèi)外矢量數(shù)據(jù)簡(jiǎn)化算法研究現(xiàn)狀進(jìn)行總結(jié),再對(duì)國(guó)內(nèi)外矢量數(shù)據(jù)并行簡(jiǎn)化研究現(xiàn)狀進(jìn)行論述,通過(guò)本文的研究,可初步獲得國(guó)內(nèi)外關(guān)于矢量數(shù)據(jù)簡(jiǎn)化的研究進(jìn)展情況,對(duì)矢量數(shù)據(jù)可視化的研究有一定的參考價(jià)值。
1傳統(tǒng)的矢量數(shù)據(jù)簡(jiǎn)化算法
由于計(jì)算機(jī)發(fā)展水平的限制,傳統(tǒng)的矢量數(shù)據(jù)簡(jiǎn)化算法大多基于串行計(jì)算模式。
1.1Douglas-Peuker簡(jiǎn)化算法及其演化
對(duì)矢量地圖的簡(jiǎn)化研究最早開(kāi)始于1973年,Douglas與Peuker提出了Douglas-Peuker折線簡(jiǎn)化法,即先將矢量折線首、尾點(diǎn)相連,再計(jì)算其他點(diǎn)到該線段的距離,取距離中的最大值,若最大距離不大于閾值,則將該線段中間曲線的其他點(diǎn)舍去,以該條線段代表曲線;若最大距離大于閾值,則將該點(diǎn)與首、尾點(diǎn)各自相連,形成兩條新的線段,再以各新形成的線段為基線,遞歸搜索,直到所有線段間曲線上所有點(diǎn)的距離都在閾值范圍內(nèi)[5]。該算法效率較高,且可保持線要素的重要幾何特征。但在簡(jiǎn)化過(guò)程中會(huì)導(dǎo)致拓?fù)潢P(guān)系發(fā)生改變,造成簡(jiǎn)化后的線要素出現(xiàn)拓?fù)潢P(guān)系不一致,容易導(dǎo)致自相交[6]。Guibas等證明如何在避免自相交的情況下保留盡可能少的點(diǎn)是一個(gè)NP-hard問(wèn)題[7]。Saalfeld在Douglas-Peuker簡(jiǎn)化算法的基礎(chǔ)上,提出拓?fù)湟恢滦员3值氖噶繑?shù)據(jù)簡(jiǎn)化算法[8]。Mustafa等提出一種基于Douglas-Peuker算法和ε-Voronoi圖的簡(jiǎn)化方法,即通過(guò)模板深度緩存,將Voronoi區(qū)域渲染到模板緩存中,再通過(guò)模板測(cè)試,剔除ε-Voronoi區(qū)域外的點(diǎn),保證每個(gè)要素簡(jiǎn)化結(jié)果都位于ε-Voronoi區(qū)域中,能夠一定程度上避免要素間的相交,但不能避免要素內(nèi)部的自相交,由于ε固定,不具有靈活性和自適應(yīng)性,簡(jiǎn)化的區(qū)域受地物分布密集程度的限制[9]。
1.2Li-OpenShaw簡(jiǎn)化算法及其擴(kuò)展
Li-OpenShaw算法是一種基于自然現(xiàn)實(shí)的自適應(yīng)化簡(jiǎn)算法,可以得到較好的化簡(jiǎn)結(jié)果,這種方法借助于滑動(dòng)圓,使滑動(dòng)圓在曲線上滑動(dòng),通過(guò)對(duì)曲線上的節(jié)點(diǎn)重采樣,得到簡(jiǎn)化后的采樣點(diǎn),達(dá)到矢量數(shù)據(jù)簡(jiǎn)化的目的[10]。通過(guò)控制滑動(dòng)圓的大小,來(lái)達(dá)到不同尺度下的簡(jiǎn)化結(jié)果,這種方法具有多尺度的靈活性,但該方法未考慮極大值的曲線點(diǎn)與多條曲線相交的問(wèn)題。針對(duì)上述問(wèn)題,朱鯤鵬等提出Li-OpenShaw算法的改進(jìn)方法,主要解決多條線相交于一條曲線的極大值點(diǎn)問(wèn)題[11]。Raposo在基于自然原則的Li-Openshaw簡(jiǎn)化算法基礎(chǔ)上,在Nyquist-Shannon采樣理論的控制下,生成六邊形來(lái)完成矢量數(shù)據(jù)簡(jiǎn)化,與基于四邊形的簡(jiǎn)化方法相比,這種方法在保持簡(jiǎn)化目標(biāo)的形狀特征方面有著明顯優(yōu)勢(shì),但六邊形的生成與處理需要消耗一定時(shí)間,在大規(guī)模數(shù)據(jù)的簡(jiǎn)化方面有一定的限制[12]。
1.3漸進(jìn)式的簡(jiǎn)化算法及其演變
郭慶勝提出一種基于線特征的漸進(jìn)式化簡(jiǎn)算法,通過(guò)查找線結(jié)構(gòu)的極值點(diǎn)、拐點(diǎn)、凸點(diǎn)及單調(diào)區(qū)間等建立線數(shù)據(jù)的分層結(jié)構(gòu)特征進(jìn)行簡(jiǎn)化[13]。Poorten提出利用Delaunay三角形進(jìn)行曲線綜合簡(jiǎn)化,利用三角形之間的連通關(guān)系,維護(hù)曲線簡(jiǎn)化前后的拓?fù)湟恢滦訹14]。艾廷華等提出一種曲線彎曲程度的二叉樹(shù)表達(dá)方法,提出曲線彎曲層次的概念,以曲線為約束構(gòu)建三角網(wǎng),依據(jù)三角形與頂點(diǎn)、曲線的關(guān)系對(duì)三角形進(jìn)行分類;依據(jù)三角形的類型,通過(guò)剝皮算法,根據(jù)剝皮過(guò)程,將曲線劃分為二叉樹(shù)組織結(jié)構(gòu),再根據(jù)彎曲的層次結(jié)構(gòu),將曲線化簡(jiǎn)[15]。杜維等提出一種基于組合優(yōu)化策略的多邊形簡(jiǎn)化方法[16]。操震洲等利用預(yù)先存儲(chǔ)的節(jié)點(diǎn)偏移量化簡(jiǎn)曲線,利用單調(diào)鏈求交的方式實(shí)現(xiàn)多分辨率下化簡(jiǎn)曲線,從而維護(hù)拓?fù)湟恢滦?達(dá)到漸進(jìn)式曲線化簡(jiǎn)的目的[17]。
1.4基于小波分析的矢量數(shù)據(jù)簡(jiǎn)化算法
利用小波理論也可對(duì)矢量數(shù)據(jù)進(jìn)行化簡(jiǎn)。小波分析理論具有多分辨率分析數(shù)據(jù)的特性,可用于數(shù)據(jù)的多分辨率分析與表達(dá),且具有正交性、對(duì)稱性、短支撐性和高階消失矩等特性[18]。吳紀(jì)桃等建立小波理論與矢量數(shù)據(jù)多尺度簡(jiǎn)化的關(guān)系模型,并從數(shù)學(xué)角度給出該模型的適用情況[19-20]。一些學(xué)者將其他一些理論同小波理論結(jié)合協(xié)調(diào)進(jìn)行矢量數(shù)據(jù)簡(jiǎn)化。Saux將B-spline理論與小波理論結(jié)合,對(duì)一些待平滑的區(qū)域進(jìn)行平滑簡(jiǎn)化[21]。吳凡利用小波理論,結(jié)合Mallat[22]算法,通過(guò)建立尺度一致性約束模型,忽略兩個(gè)整數(shù)尺度間的次要因素,實(shí)現(xiàn)任意兩個(gè)整數(shù)比例尺度下線狀數(shù)據(jù)的近視簡(jiǎn)化[23]。朱長(zhǎng)青等基于小波分析理論,針對(duì)等高線數(shù)據(jù),論述不同尺度下的矢量數(shù)據(jù)簡(jiǎn)化、綜合的方法,采用Douglas-Peuker簡(jiǎn)化算法,提取小波變換后的邊界特征點(diǎn),再在數(shù)據(jù)簡(jiǎn)化完成后恢復(fù)特征點(diǎn),保持矢量數(shù)據(jù)間的拓?fù)湟恢滦訹24-25]。王明常等基于小波理論,利用線狀要素的極角變化,以達(dá)到平滑的方式進(jìn)行簡(jiǎn)化,突出簡(jiǎn)化前后的視覺(jué)效果和精度[26]。
1.5矢量數(shù)據(jù)簡(jiǎn)化質(zhì)量評(píng)估研究現(xiàn)狀
關(guān)于矢量數(shù)據(jù)的簡(jiǎn)化精度包括兩個(gè)方面:幾何精度和屬性精度[27]。武芳等基于化簡(jiǎn)后曲線幾何特征及單點(diǎn)位置變化的特點(diǎn),提出評(píng)價(jià)簡(jiǎn)化質(zhì)量的方法。幾何特征評(píng)價(jià)指標(biāo)包括線的長(zhǎng)度比、曲折度;點(diǎn)位置變化評(píng)價(jià)包括位移標(biāo)準(zhǔn)差、位置誤差和緩沖區(qū)限差等[28]。劉鵬程等提出一種基于對(duì)偶面傅立葉形狀描述子的相似性評(píng)價(jià)指標(biāo),以傅立葉形狀描述子作為一個(gè)向量,以向量的歐式距離來(lái)度量簡(jiǎn)化前后向量的相似程度[29]。Weibel研究矢量數(shù)據(jù)簡(jiǎn)化中約束條件,包括幾何約束(如寬度、長(zhǎng)度等)、拓?fù)浼s束(如簡(jiǎn)化前后實(shí)體間的拓?fù)潢P(guān)系一致性等)、結(jié)構(gòu)約束(如簡(jiǎn)化后道路不要壓到實(shí)體等)、Gestalt約束(如需要保持平滑的線性地物化簡(jiǎn)前后要保持平滑一致性等)[30]。朱鯤鵬等在Weibel提出的約束條件基礎(chǔ)上,提出一種滿足約束條件的矢量數(shù)據(jù)簡(jiǎn)化質(zhì)量評(píng)估方法,通過(guò)比較簡(jiǎn)化前后的光滑性、位置和點(diǎn)位位移,定量地得到簡(jiǎn)化效果的評(píng)價(jià)指標(biāo)[31]。
2基于并行計(jì)算的矢量數(shù)據(jù)可視化
基于并行計(jì)算的矢量數(shù)據(jù)簡(jiǎn)化主要將傳統(tǒng)矢量數(shù)據(jù)簡(jiǎn)化算法與多核計(jì)算機(jī)或計(jì)算機(jī)集群相結(jié)合,通過(guò)對(duì)負(fù)載均衡、任務(wù)均衡的設(shè)計(jì)來(lái)完成快速并行簡(jiǎn)化的目的。并行計(jì)算的方式包括:基于共享內(nèi)存的并行方式、基于消息傳遞的并行方式和數(shù)據(jù)并行的方式等[32]。
2.1基于共享內(nèi)存的矢量數(shù)據(jù)簡(jiǎn)化算法
隨著計(jì)算機(jī)多核技術(shù)的提高,基于共享內(nèi)存方式的并行越來(lái)越普及,與基于消息傳遞的并行方式相比,基于共享內(nèi)存的矢量數(shù)據(jù)簡(jiǎn)化方法實(shí)現(xiàn)效率較高[4]。馬勁松等采用單機(jī)多核的方式進(jìn)行Douglas-Peucker簡(jiǎn)化算法的并行實(shí)現(xiàn)研究,并在此基礎(chǔ)上完成地圖線要素的實(shí)時(shí)綜合,該研究得出,采用多核并行的方式,Douglas-Peucker算法的效率大幅度提高[33]。張立強(qiáng)等基于OpenMP和GPU并行手段,通過(guò)對(duì)數(shù)據(jù)加載、數(shù)據(jù)簡(jiǎn)化及數(shù)據(jù)顯示的并行策略設(shè)計(jì),研究大規(guī)模矢量數(shù)據(jù)的并行可視化方法[34]。
2.2基于消息傳遞的矢量數(shù)據(jù)簡(jiǎn)化算法
基于消息傳遞的矢量數(shù)據(jù)簡(jiǎn)化方式主要采用MPI(Message Passing Interface)[35]并行的方式,基于MPI并行簡(jiǎn)化的優(yōu)點(diǎn)是程序移植性好、擴(kuò)展性高,缺點(diǎn)是開(kāi)發(fā)人員需要控制計(jì)算任務(wù)的分配與傳輸,并行實(shí)現(xiàn)成本較高。沈婕等基于消息傳遞方式,采用多種簡(jiǎn)化方式,對(duì)等高線簡(jiǎn)化的適宜性進(jìn)行研究,構(gòu)建基于MPI的等高線并行簡(jiǎn)化處理過(guò)程,論述數(shù)據(jù)的分發(fā)及合并、通信方式與計(jì)算過(guò)程3個(gè)重要問(wèn)題[36]。
2.3基于數(shù)據(jù)并行方式的矢量數(shù)據(jù)簡(jiǎn)化算法
數(shù)據(jù)并行即通過(guò)對(duì)數(shù)據(jù)的分區(qū),在每個(gè)區(qū)域內(nèi)同時(shí)執(zhí)行相同的操作,以完成并行處理的目的[37]。由于這種并行方式需要從數(shù)據(jù)的本身劃分出發(fā),需要考慮劃分的均衡性和一致性,大部分?jǐn)?shù)據(jù)不適用于這種方式并行實(shí)現(xiàn),因此,相關(guān)研究較少。張棟海等利用MapReduce在計(jì)算機(jī)集群上進(jìn)行Douglas-Peuker算法的并行實(shí)驗(yàn),算法的核心是數(shù)據(jù)的劃分,通過(guò)MapReduce將劃分的結(jié)果分配到集群的各個(gè)節(jié)點(diǎn)上。該研究得出,在大數(shù)據(jù)量、高復(fù)雜度情況下利用集群并行簡(jiǎn)化效率更高[38]。
3矢量數(shù)據(jù)簡(jiǎn)化的未來(lái)發(fā)展方向探討
3.1矢量數(shù)據(jù)簡(jiǎn)化的實(shí)時(shí)性和實(shí)效性不斷提高
矢量數(shù)據(jù)簡(jiǎn)化中的實(shí)時(shí)性和實(shí)效性是矢量數(shù)據(jù)可視化優(yōu)劣的一個(gè)重要指標(biāo)[39-40]。隨著數(shù)據(jù)采集能力的日漸提高,數(shù)據(jù)量日益增大。對(duì)矢量數(shù)據(jù)可視化對(duì)科學(xué)研究和工程應(yīng)用尤為重要[41]。并行技術(shù)與矢量數(shù)據(jù)簡(jiǎn)化的結(jié)合,不僅體現(xiàn)在簡(jiǎn)化過(guò)程的并行,而且還體現(xiàn)在數(shù)據(jù)輸入、處理和輸出的并行[34]。通過(guò)對(duì)并行模式下矢量數(shù)據(jù)簡(jiǎn)化的研究,極大地提高了矢量數(shù)據(jù)可視化的質(zhì)量與效率,基于并行技術(shù)的矢量數(shù)據(jù)簡(jiǎn)化難點(diǎn)在于合理、高效的并行方案的設(shè)計(jì)與實(shí)現(xiàn)。基于并行計(jì)算的矢量數(shù)據(jù)簡(jiǎn)化是矢量數(shù)據(jù)簡(jiǎn)化實(shí)時(shí)性和實(shí)效性提高的突破口和途徑。
3.2矢量數(shù)據(jù)的簡(jiǎn)化與綜合向一體化方向發(fā)展
矢量數(shù)據(jù)綜合是指根據(jù)表達(dá)的詳細(xì)程度,恰當(dāng)?shù)厣釛壊恢匾脑?,保留重要元素的過(guò)程[42]。矢量數(shù)據(jù)的簡(jiǎn)化、綜合要以數(shù)據(jù)表現(xiàn)的尺度而定,對(duì)不同比例尺下的簡(jiǎn)化,簡(jiǎn)化模型要與綜合模型相適應(yīng),達(dá)到簡(jiǎn)化與綜合一體化的表達(dá)空間數(shù)據(jù)的效果,解決這個(gè)問(wèn)題的關(guān)鍵在于研制健全的、多尺度的、基于語(yǔ)義信息和拓?fù)湫畔⒌暮?jiǎn)化模型,使其不僅能夠由復(fù)雜數(shù)據(jù)得到分層次的簡(jiǎn)化數(shù)據(jù),而且能夠由簡(jiǎn)化數(shù)據(jù)還原回的多層次的較復(fù)雜數(shù)據(jù),同時(shí),還應(yīng)探究矢量數(shù)據(jù)綜合程度與簡(jiǎn)化程度之間的關(guān)系。
3.3矢量數(shù)據(jù)的簡(jiǎn)化更加智能化、感知化
矢量數(shù)據(jù)的簡(jiǎn)化向更加智能化、感知化方向發(fā)展[43],該趨勢(shì)與機(jī)器學(xué)習(xí)、人工智能、模式識(shí)別等學(xué)科關(guān)系密切。一方面,讓計(jì)算機(jī)根據(jù)語(yǔ)義信息、尺度信息、拓?fù)湫畔⒌?,判定?jiǎn)化的程度,再根據(jù)語(yǔ)義信息、空間信息、拓?fù)湫畔⒌鹊淖兓?,以滿足人類視覺(jué)認(rèn)知需要為出發(fā)點(diǎn),實(shí)時(shí)地改變簡(jiǎn)化尺度,這種簡(jiǎn)化尺度的變化是線性或非線性的。另一方面,采用機(jī)器學(xué)習(xí)和模式識(shí)別的方式,將每個(gè)線狀要素智能化、可認(rèn)知化,通過(guò)對(duì)用戶使用信息的學(xué)習(xí),得到線狀要素對(duì)象本身的簡(jiǎn)化經(jīng)驗(yàn)參數(shù),將經(jīng)驗(yàn)參數(shù)參與到簡(jiǎn)化中,得到更好的簡(jiǎn)化效果,這種經(jīng)驗(yàn)參數(shù)包括從簡(jiǎn)化質(zhì)量檢查中得到的經(jīng)驗(yàn)(包括錯(cuò)誤元素序號(hào)、位置、錯(cuò)誤元素節(jié)點(diǎn)序號(hào)、錯(cuò)誤類型等),將簡(jiǎn)化結(jié)果以一種打分的定量化形式,被線性實(shí)體所學(xué)習(xí),在下一次的簡(jiǎn)化過(guò)程中,這些經(jīng)驗(yàn)成為約束條件,控制錯(cuò)誤的發(fā)生。
這種智能感知的簡(jiǎn)化方式可以應(yīng)用在未來(lái)的無(wú)人駕駛和無(wú)人機(jī)監(jiān)測(cè)等領(lǐng)域中[44]。如在無(wú)人駕駛研究中,控制智能汽車通過(guò)傳感器[45]獲知道路實(shí)時(shí)信息,這些初始獲得的數(shù)據(jù)是柵格形式的,而智能汽車決策行使路線時(shí),基于矢量的線性數(shù)據(jù),由柵格數(shù)據(jù)提取矢量道路特征。而從柵格數(shù)據(jù)中得到的矢量道路數(shù)據(jù)復(fù)雜度高,包括多個(gè)節(jié)點(diǎn)、拐點(diǎn),為滿足決策效率的需要,需將這些矢量數(shù)據(jù)簡(jiǎn)化,此時(shí),基于智能感知的簡(jiǎn)化是必不可少的,這種簡(jiǎn)化需要根據(jù)智能汽車對(duì)道路實(shí)際空間的認(rèn)知以及已經(jīng)積累的經(jīng)驗(yàn)來(lái)協(xié)同、實(shí)時(shí)地完成。
4結(jié)論
矢量數(shù)據(jù)簡(jiǎn)化的效率與數(shù)據(jù)拓?fù)潢P(guān)系之間的矛盾。當(dāng)前,矢量數(shù)據(jù)的簡(jiǎn)化大都只考慮矢量數(shù)據(jù)集的每個(gè)個(gè)體元素[46],從個(gè)體角度出發(fā),進(jìn)行個(gè)體元素的簡(jiǎn)化,而沒(méi)有考慮矢量數(shù)據(jù)個(gè)體間的拓?fù)潢P(guān)系,但若考慮個(gè)體間拓?fù)涞谋3?,則會(huì)導(dǎo)致簡(jiǎn)化過(guò)程較多時(shí)間的開(kāi)銷,影響簡(jiǎn)化效率。這就需要在簡(jiǎn)化效率與要素間拓?fù)浔3址矫鎸で笃胶猓慈绾卧诤?jiǎn)化效率影響不大的情況下盡可能地保持要素間的拓?fù)潢P(guān)系,解決這個(gè)問(wèn)題,需從算法本身和硬件兩方面著手,算法本身來(lái)說(shuō),研制更加高效合理的簡(jiǎn)化算法;硬件角度來(lái)說(shuō),利用多核計(jì)算機(jī)及計(jì)算機(jī)集群,采用并行計(jì)算的模式加以解決。
雖然很多學(xué)者對(duì)矢量數(shù)據(jù)的簡(jiǎn)化已經(jīng)研究多年,但還不能徹底提出一個(gè)適用于各種類型的矢量數(shù)據(jù)的簡(jiǎn)化方法,原因如下:
1)數(shù)據(jù)的復(fù)雜性與多樣性:矢量數(shù)據(jù)的空間拓?fù)潢P(guān)系異常復(fù)雜,如多條矢量數(shù)據(jù)相交、兩個(gè)地物的多個(gè)部分相交等,而這種現(xiàn)象在各種類型的矢量數(shù)據(jù)中是非常常見(jiàn)的,如立交橋的矢量數(shù)據(jù)等。
2)受計(jì)算機(jī)發(fā)展及應(yīng)用水平的限制:雖然并行技術(shù)已經(jīng)相對(duì)較成熟,但該技術(shù)實(shí)現(xiàn)的難度較大,如需要考慮I/O均衡、負(fù)載均衡等,缺少一種更加方便的技術(shù)模式來(lái)支持并行技術(shù)在矢量數(shù)據(jù)簡(jiǎn)化方面的應(yīng)用。需要研究一種支持串行與并行兼容的數(shù)據(jù)結(jié)構(gòu),減少數(shù)據(jù)通信時(shí)時(shí)間的開(kāi)銷,該數(shù)據(jù)結(jié)構(gòu)需滿足低冗余和低數(shù)據(jù)復(fù)雜性,且該數(shù)據(jù)結(jié)構(gòu)能滿足多層次、實(shí)時(shí)性和易于計(jì)算機(jī)認(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]陳國(guó)良.并行算法的設(shè)計(jì)與分析[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)與評(píng)價(jià)[J].測(cè)繪學(xué)報(bào),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].武漢測(cè)繪科技大學(xué)學(xué)報(bào),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)的二叉樹(shù)表達(dá)[J].測(cè)繪學(xué)報(bào),2001,30(4):343-348.
[16] 杜維,艾廷華,徐崢.一種組合優(yōu)化的多邊形化簡(jiǎn)方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2004,29(6):548-550.
[17] 操震洲,李滿春,程亮,等.適用于網(wǎng)絡(luò)漸進(jìn)傳輸?shù)亩喾直媛是€生成算法[J].計(jì)算機(jī)應(yīng)用,2013,33(3):688-690.
[18] 崔錦泰,程正興.小波分析導(dǎo)論[M].西安:西安交通大學(xué)出版社,1995.
[19] 吳紀(jì)桃,王橋.小波分析在 GIS 線狀數(shù)據(jù)圖形簡(jiǎn)化中的應(yīng)用研究[J].測(cè)繪學(xué)報(bào),2000,29(1):71-75.
[20] 吳紀(jì)桃,王橋.小波理論用于地圖數(shù)據(jù)處理中若干理論問(wèn)題的探討[J].測(cè)繪學(xué)報(bào),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ù)無(wú)級(jí)表達(dá)[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2004,29(6):488-491.
[24] 朱長(zhǎng)青,王玉海,李清泉,等.基于小波分析的等高線數(shù)據(jù)壓縮模型[J].中國(guó)圖像圖形學(xué)報(bào),2004,9(7):841-845.
[25] 王玉海,朱長(zhǎng)青.基于小波分析的線狀要素壓縮優(yōu)化的綜合性研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2007,32(7):630-632.
[26] 王明常,谷蘭英,王宇,等.小波變換理論的線狀要素制圖綜合研究[J].吉林大學(xué)學(xué)報(bào)(地球科學(xué)版),2005(S1).
[27] 史文中.空間數(shù)據(jù)與空間分析不確定性原理[M].北京:科學(xué)出版社,2005.
[28] 武芳,朱鯤鵬.線要素化簡(jiǎn)算法幾何精度評(píng)估[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2008,33(6):600-603.
[29] 劉鵬程,羅靜,艾廷華,等.基于線要素綜合的形狀相似性評(píng)價(jià)模型[J].武漢大學(xué)學(xué)報(bào)(信息科學(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] 朱鯤鵬,武芳,陳波,等.基于約束條件的線要素化簡(jiǎn)算法質(zhì)量評(píng)估[J].測(cè)繪科學(xué),2007,32(3):28-30.
[32] 安虹,陳崚.并行算法實(shí)踐[M].北京:高等教育出版社,2004.
[33] 馬勁松,沈婕,徐壽成.利用 Douglas-Peucker并行算法在多核處理器上實(shí)時(shí)綜合地圖線要素[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2011,36(12):1423-1426.
[34] 張立強(qiáng),徐翔,譚繼強(qiáng).基于并行技術(shù)的大規(guī)模矢量地圖可視化方法[J].地理與地理信息科學(xué),2013,29(4):9-12.
[35] 張武生,薛巍,李建江,等.MPI并行程序設(shè)計(jì)實(shí)例教程[M].北京:清華大學(xué)出版社,2009.
[36] 沈婕,郭立帥,朱偉,等.消息傳遞接口環(huán)境下等高線簡(jiǎn)化并行計(jì)算適宜性研究[J].測(cè)繪學(xué)報(bào),2013,42(4):621-628.
[37] LIN C,SNYDER L.Principles of parallel programming[M].Addison-Wesley Publishing Company,2008.
[38] 張棟海,黃麗娜,劉暉,等.基于MapReduce的多機(jī)并行 DP 算法與實(shí)驗(yàn)分析[J].地球信息科學(xué)學(xué)報(bào),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].北京:測(cè)繪出版社,2004.
[43] 王家耀.地圖制圖學(xué)與地理信息工程學(xué)科發(fā)展趨勢(shì)[J].測(cè)繪學(xué)報(bào),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é)報(bào)(信息科學(xué)版),2010(2):127-132.
[46] 溫永寧,閭囯年,陳旻.矢量空間數(shù)據(jù)漸進(jìn)傳輸研究進(jìn)展[J].地理與地理信息科學(xué),2011,27(6):6-12.
[47] 姚靜.基于ArGIS的大比例尺矢量電子地圖制圖研究[J].測(cè)繪與空間地理信息,2015,38(6):135-136.
[48] 周琛,陳振杰,黃秋昊,等.多核并行環(huán)境中矢量數(shù)據(jù)格式的轉(zhuǎn)換算法[J].測(cè)繪科學(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
中圖分類號(hào):P283;P208
文獻(xiàn)標(biāo)識(shí)碼:A
文章編號(hào):1006-7949(2016)06-0010-05
作者簡(jiǎn)介:張振鑫(1986-),男,博士研究生.
基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(41401532)
收稿日期:2015-03-27;修回日期:2015-08-04