周 晨，陳 偉,2，劉 淵,2

基于漸進(jìn)迭代逼近的矢量地圖曲線化簡(jiǎn)方法

周 晨1，陳 偉1,2，劉 淵1,2

(1. 江南大學(xué)人工智能與計(jì)算機(jī)學(xué)院，江蘇 無(wú)錫 214122； 2.江蘇省媒體設(shè)計(jì)與軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室(江南大學(xué))，江蘇 無(wú)錫 214122)

矢量地圖化簡(jiǎn)在地形仿真、制圖綜合等研究中具有重要應(yīng)用。針對(duì)已有算法難以兼顧化簡(jiǎn)曲線的整體形態(tài)和局部特征點(diǎn)精度的問(wèn)題，提出一種基于B樣條曲線漸進(jìn)迭代逼近(PIA)的矢量地圖曲線化簡(jiǎn)方法。首先篩選出能保持曲線輪廓、具有最大信息量的特征點(diǎn)列，將其作為初始控制點(diǎn)列，得到相應(yīng)的非均勻3次B樣條擬合曲線；然后根據(jù)擬合曲線與特征點(diǎn)的誤差進(jìn)行迭代調(diào)整控制點(diǎn)，逐步得到一系列逼近曲線，直至最終滿(mǎn)足精度要求。實(shí)驗(yàn)表明，PIA方法不僅保持了化簡(jiǎn)曲線的整體幾何形態(tài)，而且能在滿(mǎn)足全局誤差要求的情況下，實(shí)現(xiàn)特征點(diǎn)處的高精度逼近。

地圖綜合；曲線；樣條；漸進(jìn)迭代逼近；化簡(jiǎn)

在地理信息系統(tǒng)(geographic information system，GIS)中，地圖要素按照其對(duì)應(yīng)地圖符號(hào)的幾何屬性可以分為點(diǎn)、線、面3類(lèi)，其中線狀要素所占比例最大，如地形等高線、區(qū)域分界線、道路、河系等多種類(lèi)型。對(duì)于面狀要素，比如湖泊、島嶼、植被、居民地、行政區(qū)等，在內(nèi)部勻質(zhì)的情況下，人們也往往更關(guān)注其外圍輪廓線[1]。在GIS矢量空間數(shù)據(jù)中，一條曲線是經(jīng)過(guò)數(shù)字化采樣得到一個(gè)有序點(diǎn)列，線狀要素具有數(shù)據(jù)量大、形態(tài)復(fù)雜的特點(diǎn)。根據(jù)地圖制圖學(xué)的要求，曲線化簡(jiǎn)是在盡量保持曲線關(guān)鍵位置精度及幾何形態(tài)結(jié)構(gòu)的前提下，盡可能多地剔除曲線上冗余或次要的點(diǎn)，以達(dá)到減少數(shù)據(jù)量及適應(yīng)小比例尺地圖顯示的需求[2]。因此，位置精度和形態(tài)結(jié)構(gòu)保持是矢量地圖曲線化簡(jiǎn)中需要考慮的重要因素。所謂關(guān)鍵位置，是指曲線上能夠反映地理特性的點(diǎn)或有特殊含義的地理位置，幾何上一般對(duì)應(yīng)為曲線上的特征點(diǎn)。

矢量地圖曲線化簡(jiǎn)是地圖自動(dòng)綜合領(lǐng)域的研究熱點(diǎn)，也是地圖學(xué)與地理信息科學(xué)界公認(rèn)的一個(gè)難題[1]。國(guó)內(nèi)外學(xué)者提出了多種不同的矢量曲線化簡(jiǎn)方法，主要?dú)w納為2類(lèi)：基于空間幾何化簡(jiǎn)的算法和基于頻域?yàn)V波的算法。

基于空間幾何化簡(jiǎn)算法中，絕大部分通過(guò)對(duì)曲線上點(diǎn)的取舍使曲線得到簡(jiǎn)化，同時(shí)保持曲線的整體形態(tài)。1973年，DOUGLAS和PEUCKER[3]提出的一種矢量地圖數(shù)據(jù)的折線簡(jiǎn)化法，即DP算法，具有保留最大信息量點(diǎn)的特征[4]。幾乎同時(shí)，RAMER[5]于1972年、DUDA和HART[6]于1973年分別獨(dú)立提出同樣的算法。另外，也有文獻(xiàn)提出基于曲線上彎曲結(jié)構(gòu)的取舍的化簡(jiǎn)算法[7-9]，但目前在彎曲的定義與處理上還不能協(xié)調(diào)一致[4]。文獻(xiàn)[10]對(duì)常見(jiàn)的化簡(jiǎn)算法進(jìn)行性能比較后發(fā)現(xiàn)，DP算法具有最優(yōu)的整體形態(tài)和關(guān)鍵點(diǎn)保持能力，不足之處是不能得到光滑彎曲的化簡(jiǎn)曲線，給人以生硬的視覺(jué)效果。

而基于頻域?yàn)V波的曲線化簡(jiǎn)算法，是將原始曲線經(jīng)Fourier和小波變換等操作，在頻域空間中保留曲線的重要特征系數(shù)，再通過(guò)反變換得到化簡(jiǎn)后的曲線。文獻(xiàn)[11-12]將閉型地圖曲線經(jīng)Fourier變換轉(zhuǎn)換到頻率空間，從而實(shí)現(xiàn)了從粗糙到精細(xì)地重構(gòu)原始曲線。為了兼容開(kāi)型地圖曲線的化簡(jiǎn)，文獻(xiàn)中首先對(duì)原始曲線作鏡像對(duì)稱(chēng)復(fù)制，得到封閉曲線后再作Fourier變換。文獻(xiàn)[12-17]將小波分析理論應(yīng)用到地圖矢量曲線的化簡(jiǎn)及壓縮中。需要指出的是，雖然小波具有多分辨率分析的內(nèi)在屬性，可以生成信號(hào)的多尺度表達(dá)模型。但是在地圖曲線化簡(jiǎn)的特定應(yīng)用中，曲線上的特征點(diǎn)一般具有特殊含義，在對(duì)原始曲線化簡(jiǎn)或壓縮過(guò)程中，要求這些點(diǎn)不產(chǎn)生移位，即保證這些位置處的擬合精度[11]。而根據(jù)時(shí)頻變換理論可知，將地圖曲線經(jīng)時(shí)頻變換后，空間特征點(diǎn)的信息已經(jīng)被散播在各頻段系數(shù)中，若要精確重構(gòu)特征點(diǎn)位置，則需大量增加頻域重構(gòu)項(xiàng)數(shù)，而這又與曲線化簡(jiǎn)的目標(biāo)發(fā)生內(nèi)在矛盾。文獻(xiàn)[13-14]通過(guò)多種后處理的方法進(jìn)行特征點(diǎn)誤差修正，但同時(shí)又帶來(lái)算法復(fù)雜，適應(yīng)性不強(qiáng)等問(wèn)題。

綜上所述，在地圖矢量曲線化簡(jiǎn)問(wèn)題中，已有方法很難兼顧化簡(jiǎn)結(jié)果的全局形態(tài)與局部精度。因此，可將地圖矢量曲線的化簡(jiǎn)看作一個(gè)B樣條曲線擬合問(wèn)題，引入近年來(lái)在計(jì)算機(jī)輔助設(shè)計(jì)(computer aided geometric design，CAGD)領(lǐng)域流行的漸進(jìn)迭代逼近方法，使化簡(jiǎn)曲線既能保持原始地圖曲線的整體形態(tài)，又能滿(mǎn)足局部擬合精度的要求。

1 相關(guān)工作

1.1 Douglas-Peucker(DP)算法

DP算法是比較經(jīng)典且廣為引用的算法，本文對(duì)該算法做簡(jiǎn)要介紹。

對(duì)于開(kāi)型曲線(圖1)，起點(diǎn)0和終點(diǎn)P為地理目標(biāo)的起訖點(diǎn)，其具有重要的地理意義和結(jié)構(gòu)意義，因此是不可移動(dòng)的特征點(diǎn)。首先將0和P連成直線段，其是該曲線的極限化簡(jiǎn)狀態(tài)。計(jì)算所有中間點(diǎn)到該直線段的距離，找到最大距離max對(duì)應(yīng)的點(diǎn)P，其對(duì)于確保曲線的特征有不可替代的重要性。也就是說(shuō)，相比其他中間點(diǎn)而言，保留P將使曲線變形最小。

圖1 Douglas-Peucker算法

若max小于預(yù)設(shè)限差，則該曲線用該段基線代替；否則，P作為新的特征點(diǎn)將原曲線作進(jìn)一步的劃分，直到所有子曲線段的最大偏移量均小于為止。將保留下來(lái)的所有特征點(diǎn)按序連成折線即為最終的化簡(jiǎn)結(jié)果。通過(guò)DP算法保留下來(lái)的特征點(diǎn)，均是為確保相應(yīng)子曲線段的輪廓特征具有最大貢獻(xiàn)的點(diǎn)，這是DP算法具有最大信息量的主要原因，從而被廣泛地應(yīng)用[18-22]。

對(duì)于閉型曲線，首先用恰當(dāng)?shù)姆椒▽?duì)其一分為二，然后再分別用上述算法進(jìn)行化簡(jiǎn)，不再贅述。

1.2 漸進(jìn)迭代逼近(PIA)算法

漸進(jìn)迭代逼近(progressive-iterative approximation，PIA)，又稱(chēng)為幾何迭代法，是一種具有明顯幾何意義的曲線曲面逼近方法。從一條初始混合曲線開(kāi)始，迭代地調(diào)整其控制頂點(diǎn)位置，即可使這條曲線收斂到一條插值給定數(shù)據(jù)點(diǎn)列的曲線。PIA方法肇始于1975年由齊東旭等[23]提出的均勻3次B樣條曲線擬合的盈虧修正算法；1979年，DE BOOR[24]也獨(dú)立提出了這一算法；近年來(lái)，國(guó)內(nèi)學(xué)者對(duì)PIA方法做了深入的理論推廣及廣泛地應(yīng)用研究[25-29]。

本文對(duì)插值型PIA方法做簡(jiǎn)要介紹。

給定空間中的一個(gè)有序型值點(diǎn)列{Q，=0,1,···,}，其中每個(gè)型值點(diǎn)Q賦予一個(gè)參數(shù)值{t，=0,1,···,}，滿(mǎn)足

以該型值點(diǎn)列為初始控制多邊形頂點(diǎn)，構(gòu)造一組初始混合曲線

為了生成第+1次迭代后的曲線，首先計(jì)算每個(gè)型值點(diǎn)Q與(k)()上對(duì)應(yīng)參數(shù)點(diǎn)的差向量

然后，將()加到曲線(k)()的相應(yīng)的控制頂點(diǎn)上，得到第+1次迭代生成曲線的控制頂點(diǎn)

從而得到第+1次迭代后生成的曲線

由此可見(jiàn)，這個(gè)迭代過(guò)程將產(chǎn)生一個(gè)曲線序列

文獻(xiàn)[25]證明了，只要調(diào)配基函數(shù)是全正基函數(shù)，那么這個(gè)曲線序列就收斂到一條插值給定型值點(diǎn)列{Q，=0,1,···,}的曲線，即

需要指出的是，雖然選擇3次非均勻B樣條基函數(shù)作為調(diào)配基函數(shù)，從理論上保證了曲線序列收斂到型值點(diǎn)列。但是在地圖曲線化簡(jiǎn)應(yīng)用中，并不過(guò)分強(qiáng)調(diào)化簡(jiǎn)曲線的插值性。實(shí)驗(yàn)結(jié)果表明，一般情況下，只需作較少次數(shù)迭代(3次左右)即可滿(mǎn)足實(shí)際化簡(jiǎn)要求，與PIA方法在某些高精度曲線逼近應(yīng)用領(lǐng)域(如等距線逼近、工業(yè)產(chǎn)品設(shè)計(jì)等)具有不同之處。

2 矢量地圖曲線化簡(jiǎn)的PIA方法

以DP算法獲取的地圖曲線特征點(diǎn)為基礎(chǔ)，通過(guò)引入B樣條曲線擬合中的漸進(jìn)迭代逼近方法，得到一種兼顧全局形態(tài)與局部精度的曲線化簡(jiǎn)方法。

設(shè)原始矢量地圖曲線由有序點(diǎn)列{P，=0,1,···,}組成，當(dāng)0=時(shí)為閉型曲線，如等高線、區(qū)域輪廓線等地圖實(shí)體；否則，當(dāng)0≠時(shí)為開(kāi)型曲線，如河流、道路等地圖實(shí)體。在運(yùn)用PIA方法之前，首先需要從原始曲線點(diǎn)列中提取特征點(diǎn)，能較好地反映原始曲線的形狀信息。盡管在CAGD領(lǐng)域中已提出多種方法用于數(shù)字曲線特征點(diǎn)的檢測(cè)及提取[30-31]，一般可通過(guò)計(jì)算數(shù)字曲線上各點(diǎn)處的曲率來(lái)判斷其重要性，從而篩選出特征點(diǎn)。但是在數(shù)字地圖領(lǐng)域，地圖曲線具有復(fù)雜程度高、在多個(gè)尺度上具有振蕩性的特點(diǎn)。因此，基于局部信息的曲率估計(jì)方法很難有效地提取地圖曲線上的特征點(diǎn)。如前所述，DP算法在數(shù)字地圖綜合領(lǐng)域具有持久的生命力，一個(gè)重要的原因是其能夠有效篩選出各種地形曲線的特征點(diǎn)。因此，本文將利用DP算法獲取地圖曲線上的特征點(diǎn)。

當(dāng)0=Q時(shí)，取延拓型值點(diǎn)-1=Q1，Q1=1；當(dāng)0≠Q時(shí)，取延拓型值點(diǎn)-1=0，Q1=Q。于是得到以{Q，=-1,0,1,···,+1}為控制點(diǎn)的3次非均勻B樣條初始曲線

其中，B()為3次非均勻B樣條基函數(shù)。

一般說(shuō)來(lái)，由式(8)得到的初始曲線(0)()能夠刻畫(huà)出原地圖曲線的整體形態(tài)。但由于{Q，=0,1,···,}為原曲線的特征點(diǎn)，往往位于曲線變化比較大的地方，此時(shí)初始曲線(0)()與型值的誤差較大。為了保持特征點(diǎn)在地圖曲線化簡(jiǎn)過(guò)程中的精度，運(yùn)用漸進(jìn)迭代逼近方法，通過(guò)有限次迭代，得到新的3次非均勻B樣條曲線

當(dāng)滿(mǎn)足逼近精度要求時(shí)，(k)()即可作為最終的化簡(jiǎn)曲線。關(guān)于迭代次數(shù)與逼近誤差的關(guān)系，將在下節(jié)內(nèi)容中討論。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)1：地圖曲線化簡(jiǎn)

實(shí)驗(yàn)采用圖2(a)所示的一條由1 577個(gè)點(diǎn)構(gòu)成的地圖曲線數(shù)據(jù)，圖2(b)為通過(guò)DP算法得到的包含85個(gè)特征點(diǎn)({Q，=0,1,···,84}，其中0=84)的化簡(jiǎn)曲線。可以看出，DP算法結(jié)果保留了曲線的特征點(diǎn)，一定程度上保持了原曲線的形狀，但未經(jīng)光滑處理，看上去比較生硬。

圖3為分別通過(guò)Fourier變換和小波變換得到的化簡(jiǎn)結(jié)果。圖4分別為彎曲取舍[32-33]和Li-Openshaw算法[34-35]的化簡(jiǎn)結(jié)果。通過(guò)Fourier和小波變換得到曲線較為光滑。但化簡(jiǎn)曲線在某些特征點(diǎn)的誤差較大，即產(chǎn)生特征位移現(xiàn)象。而彎曲取舍和Li-Openshaw算法得到的曲線可以保持曲線輪廓的基本特征，但光滑度較差并不能保證化簡(jiǎn)曲線在特征點(diǎn)處的精度。

圖5為PIA方法在不同迭代次數(shù)(0次、1次、3次及5次)得到的化簡(jiǎn)曲線。可知，用3次B樣條曲線進(jìn)行擬合時(shí)，其可以反映出原始曲線的整體形態(tài)且具有良好的光滑性，但對(duì)于特征點(diǎn)的保持能力較差。但通過(guò)PIA方法很少的迭代次數(shù)，擬合曲線就會(huì)逼近特征點(diǎn)，當(dāng)?shù)螖?shù)達(dá)到5次時(shí)，對(duì)應(yīng)的3次B樣條曲線(5)()非常接近特征點(diǎn)，幾乎達(dá)到插值的效果。

圖2 地圖曲線及其DP算法化簡(jiǎn)結(jié)果((a)原始曲線(1 577個(gè)點(diǎn))；(b)化簡(jiǎn)曲線(85個(gè)點(diǎn)))

為定量分析特征點(diǎn)的逼近誤差，定義化簡(jiǎn)曲線在特征點(diǎn)Q處的逼近誤差為

圖3 基于Fourier變換或小波變換(db4)的化簡(jiǎn)結(jié)果及局部放大((a) Fourier重構(gòu)(50項(xiàng))；(b) Fourier重構(gòu)(100項(xiàng))；(c)小波重構(gòu)(56項(xiàng))；(d)小波重構(gòu)(105項(xiàng)))

Fig. 3 Simplification result and local magnification based on Fourier or wavelet transform (db4) ((a)Reconstruction of Fourier (50 items); (b) Reconstruction of Fourier (100 items); (c) Reconstruction of wavelet (56 items); (d) Reconstruction of wavelet (105 items) )

圖4 基于彎曲取舍或Li-Openshaw算法的化簡(jiǎn)結(jié)果及其局部放大((a)彎曲取舍(70個(gè)點(diǎn))；(b)彎曲取舍(192個(gè)點(diǎn))；(c) Li-Openshaw(54個(gè)點(diǎn))；(d) Li-Openshaw (90個(gè)點(diǎn)))

圖5 基于PIA方法的化簡(jiǎn)結(jié)果及其局部放大((a)迭代0次；(b)迭代1次；(c)迭代3次；(d)迭代5次)

分別計(jì)算以下3種誤差：

(1) 平均誤差為

(2) 最大誤差為

(3) 標(biāo)準(zhǔn)差為

表1列出了上述化簡(jiǎn)方法特征點(diǎn)處的誤差數(shù)據(jù)?？梢钥闯?，PIA方法在提高化簡(jiǎn)曲線在特征點(diǎn)處的精度是有效的。每迭代1次，便可使逼近精度大幅提高，同時(shí)保持了化簡(jiǎn)曲線的整體形態(tài)。但隨著迭代次數(shù)的增加，逼近誤差明顯減小，且特征點(diǎn)數(shù)目始終保持不變。在濾波、彎曲取舍及Li-Openshaw方法中，若要減小其誤差，則必須增加重構(gòu)系數(shù)或綜合后點(diǎn)的數(shù)量，與地圖曲線化簡(jiǎn)的初衷有內(nèi)在矛盾。

此外，表2分別計(jì)算了在已知特征點(diǎn)的情況下，PIA方法及傳統(tǒng)方法對(duì)圖2所示等高線化簡(jiǎn)所需時(shí)間結(jié)果(相同環(huán)境下運(yùn)行1 000次取平均值)。

3.2 實(shí)驗(yàn)2：PIA迭代次數(shù)及全局誤差分析

為進(jìn)一步分析PIA迭代次數(shù)對(duì)化簡(jiǎn)曲線局部及全局誤差的關(guān)系，選擇典型的116條等高線數(shù)據(jù)作化簡(jiǎn)實(shí)驗(yàn)。表3顯示了6條等高線及其相應(yīng)的化簡(jiǎn)結(jié)果，可以看出，PIA方法能夠得到保持原等高線整體形態(tài)的光滑曲線。接下來(lái)將定量分析使用PIA方法所得化簡(jiǎn)曲線的局部及全局誤差。

表1 不同方法的逼近誤差(×0.01)

表2 不同化簡(jiǎn)算法重構(gòu)所需時(shí)間(ms)

表3 116條等高線中6條等高線及PIA方法化簡(jiǎn)結(jié)果

首先計(jì)算PIA方法在不同迭代次數(shù)(1～10次)下全部等高線化簡(jiǎn)結(jié)果在特征點(diǎn)處的平均誤差(表4)?？梢钥闯?，隨著迭代次數(shù)的增加，化簡(jiǎn)曲線在特征點(diǎn)處的誤差逐漸減小，其局部保持能力不斷增強(qiáng)。圖6為迭代次數(shù)與誤差之間的關(guān)系。可以看出，3次迭代后特征點(diǎn)的各逼近誤差僅為初始誤差的10%左右，繼續(xù)增加迭代次數(shù)，誤差將繼續(xù)減少。因此，在實(shí)際化簡(jiǎn)應(yīng)用中，若無(wú)特殊要求，迭代次數(shù)設(shè)為3次即可，或根據(jù)精度要求選擇迭代次數(shù)。

進(jìn)一步計(jì)算化簡(jiǎn)曲線的全局誤差，定義平均全局誤差為

圖7為116條等高線分別利用5種方法得到化簡(jiǎn)曲線的全局平均誤差?？梢钥闯觯肞IA方法得到的所有化簡(jiǎn)曲線的全局平均誤差中，僅有2條略大于小波變換，其余均小于其他方法。因此，PIA方法在保證局部特征點(diǎn)精度的前提下，并未犧牲化簡(jiǎn)曲線的全局精度。

表4 116條等高線在PIA方法各迭代次數(shù)下的誤差(×0.01)

圖6 PIA方法迭代次數(shù)與誤差的關(guān)系

圖7 等高線化簡(jiǎn)曲線的平均全局誤差

4 結(jié) 論

本文將漸進(jìn)迭代逼近理論首次引入到地圖曲線化簡(jiǎn)領(lǐng)域。針對(duì)地圖曲線化簡(jiǎn)的應(yīng)用需求，本文提出的算法和實(shí)驗(yàn)結(jié)果表明，漸進(jìn)迭代逼近理論能夠有效地解決化簡(jiǎn)曲線的整體幾何形態(tài)和局部特征精度之間的矛盾。

作為一項(xiàng)探索性研究工作，為了將本文提出的方法有效應(yīng)用到地圖數(shù)據(jù)的表達(dá)、分析及處理中，仍有許多問(wèn)題需要解決。包括海量地圖數(shù)據(jù)的高效處理、地圖曲線的拓?fù)浣Y(jié)構(gòu)保持等問(wèn)題，尚需進(jìn)行更深入理論及應(yīng)用研究。

[1] 閆浩文, 王家耀. 地圖群(組)目標(biāo)描述與自動(dòng)綜合[M]. 北京: 科學(xué)出版社, 2009: 1-37.

YAN H W, WANG J Y. Target description and automatic synthesis of map groups (groups)[M]. Beijing: Science Press, 2009: 1-37 (in Chinese).

[2] 王家耀, 李志林, 武芳. 數(shù)字地圖綜合進(jìn)展[M]. 北京: 科學(xué)出版社, 2011: 12-21.

WANG J Y, LI Z L, WU F. Advances in digital map generalization[M]. Beijing: Science Press, 2011: 12-21 (in Chinese).

[3] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[4] 毋河海. GIS與地圖信息綜合基本模型與算法[M]. 武漢: 武漢大學(xué)出版社, 2012: 431-442.

WU H H. Basic models and algorithms in GIS and map generalization[M]. Wuhan: Wuhan University Press, 2012: 431-442 (in Chinese).

[5] RAMER U. An iterative procedure for the polygonal approximation of plane curves[J]. Computer Graphics and Image Processing, 1972, 1(3): 244-256.

[6] DUDA R, HART P. Pattern classification and scene analysis[M]. New York: John Wiley & Sons, 1973: 462-463.

[7] 毋河海. 數(shù)字曲線拐點(diǎn)的自動(dòng)確定[J]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版, 2003, 28(3): 330-335.

WU H H. Automatic determination of inflection point and its applications[J]. Geomatics and Information Science of Wuhan University, 2003, 28(3): 330-335 (in Chinese).

[8] 郭慶勝, 黃遠(yuǎn)林, 章莉萍. 曲線的彎曲識(shí)別方法研究[J]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版, 2008, 33(6): 596-599.

GUO Q S, HUANG Y L, ZHANG L P. The method of curve bend recognition[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 596-599 (in Chinese).

[9] 杜佳威, 武芳, 李靖涵, 等. 采用多元彎曲組劃分的線要素化簡(jiǎn)方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2017, 29(12): 2189-2196.

DU J W, WU F, LI J H, et al. Line simplification method based on multi-bends groups division[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(12): 2189-2196 (in Chinese).

[10] 鄧敏, 樊子德, 劉慧敏. 層次信息量的線要素化簡(jiǎn)算法評(píng)價(jià)研究[J]. 測(cè)繪學(xué)報(bào), 2013, 42(5): 767-773, 781.

DENG M, FAN Z D, LIU H M. Performance evaluation of line simplification algorithms based on hierarchical information content[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 767-773, 781 (in Chinese).

[11] LIU P C, LI X G, LIU W B, et al. Fourier-based multi-scale representation and progressive transmission of cartographic curves on the internet[J]. Cartography and Geographic Information Science, 2016, 43(5): 454-468.

[12] IOUP J W, GENDRON M L, LOHRENZ M C. Vector map data compression with wavelets[J]. Journal of Navigation, 2000, 53(3): 437-449.

[13] 朱長(zhǎng)青, 王玉海, 李清泉, 等. 基于小波分析的等高線數(shù)據(jù)壓縮模型[J]. 中國(guó)圖象圖形學(xué)報(bào), 2004, 9(7): 841-845.

ZHU C Q, WANG Y H, LI Q Q, et al. A model to compress contour data based on wavelet analysis[J]. Journal of Image and Graphics, 2004, 9(7): 841-845 (in Chinese).

[14] 馬伯寧, 冷志光, 湯曉安, 等. 具有誤差修正的線矢量數(shù)據(jù)小波變換[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(11): 1825-1829, 1837.

MA B N, LENG Z G, TANG X A, et al. Wavelet transform with error correction for line vector data[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(11): 1825-1829, 1837 (in Chinese).

[15] SAUX E. B-spline functions and wavelets for cartographic line generalization[J]. Cartography and Geographic Information Science, 2003, 30(1): 33-50.

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

WU J T, WANG Q. A study on automatic cartographic generalization using wavelet analysis in GIS[J]. Acta Geodaetica et Cartographic Sinica, 2000, 29(1): 71-75 (in Chinese).

[17] 陳偉, 齊東旭. 基于Franklin函數(shù)的數(shù)字曲線多邊形逼近[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(7): 980-987.

CHEN W, QI D X. Polygonal approximation of digital curves based on franklin function[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(7): 980-987 (in Chinese).

[18] PALLERO J L G. Robust line simplification on the plane[J]. Computers & Geosciences, 2013, 61: 152-159.

[19] LIU J X, LI H H, YANG Z L, et al. Adaptive Douglas-peucker algorithm with automatic thresholding for AIS-based vessel trajectory compression[J]. IEEE Access, 2019, 7: 150677-150692.

[20] ZHANG S K, LIU Z J, CAI Y, et al. AIS trajectories simplification and threshold determination[J]. Journal of Navigation, 2016, 69(4): 729-744.

[21] ZAREI R, HE J, SIULY S, et al. Exploring Douglas-peucker algorithm in the detection of epileptic seizure from multicategory EEG signals[J]. BioMed Research International, 2019, 2019: 5173589.

[22] ZHAO L B, SHI G Y. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering, 2018, 166: 37-46.

[23] 齊東旭, 田自賢, 張玉心, 等. 曲線擬合的數(shù)值磨光方法[J].數(shù)學(xué)學(xué)報(bào), 1975, 18(3): 173-184.

QI D X, TIAN Z X, ZHANG Y X, et al. Numerical polishing method for curve fitting[J]. Acta Mathematica Sinica, 1975, 18(3): 173-184 (in Chinese).

[24] DE BOOR C. How does agee’s smoothing method work: 79-3[R]. Washingdon D C: Army Research Office, 1979: 299-302.

[25] LIN H W, BAO H J, WANG G J. Totally positive bases and progressive iteration approximation[J]. Computers & Mathematics with Applications, 2005, 50(3-4): 575-586.

[26] 藺宏偉. 幾何迭代法及其應(yīng)用綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(4): 582-589.

LIN H W. Survey on geometric iterative methods with applications[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(4): 582-589 (in Chinese).

[27] LIN H W, MAEKAWA T, DENG C Y. Survey on geometric iterative methods and their applications[J]. Computer-Aided Design, 2018, 95: 40-51.

[28] 鄧少輝, 汪國(guó)昭. 漸進(jìn)迭代逼近方法的數(shù)值分析[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2012, 24(7): 879-884.

DENG S H, WANG G Z. Numerical analysis of the progressive iterative approximation method[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(7): 879-884 (in Chinese).

[29] DENG C Y, LIN H W. Progressive and iterative approximation for least squares B-spline curve and surface fitting[J]. Computer-Aided Design, 2014, 47: 32-44.

[30] LIU G H, WONG Y S, ZHANG Y F, et al. Adaptive fairing of digitized point data with discrete curvature[J]. Computer-Aided Design, 2002, 34(4): 309-320.

[31] PARK H, LEE J H. B-spline curve fitting based on adaptive curve refinement using dominant points[J]. Computer-Aided Design, 2007, 39(6): 439-451.

[32] 羅廣祥, 祝國(guó)瑞, 毋河海, 等. 坐標(biāo)單調(diào)性分析下地圖曲線彎曲識(shí)別模型的研究[J]. 測(cè)繪通報(bào), 2005(10): 21-24.

LUO G X, ZHU G R, WU H H, et al. The study of the model of identifying bends for cartographic linear features based on analysing coordinate monotony[J]. Bulletin of Surveying and Mapping, 2005(10): 21-24 (in Chinese).

[33] 黃博華, 武芳, 翟仁健, 等. 保持彎曲特征的線要素化簡(jiǎn)算法[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2014, 31(5): 533-537.

HUANG B H, WU F, ZHAI R J, et al. The line feature simplification algorithm preserving curve bend feature[J]. Journal of Geomatics Science and Technology, 2014, 31(5): 533-537 (in Chinese).

[34] LI Z L, OPENSHAW S. 基于客觀綜合自然規(guī)律的線狀要素自動(dòng)綜合的算法[J]. 武測(cè)譯文, 1994, (1): 49-58.

LI Z L, OPENSHAW S. Linear feature’s self-adapted generalization algorithm based on impersonality generalized natural law[J]. Translation of Wuhan Technical University of Surveying and Mapping, 1994, (1): 49-58 (in Chinese).

[35] 朱鯤鵬, 武芳, 王輝連, 等. Li-Openshaw算法的改進(jìn)與評(píng)價(jià)[J]. 測(cè)繪學(xué)報(bào), 2007, 36(4): 450-456.

ZHU K P, WU F, WANG H L, et al. Improvement and assessment of Li-openshaw algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456 (in Chinese).

Vector map curve simplification algorithm based on progressive-iterative approximation

ZHOU Chen1, CHEN Wei1,2, LIU Yuan1,2

(1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi Jiangsu 214122, China; 2. Jiangsu Key Laboratory of Media Design and Software Technology, Jiangnan University, Wuxi Jiangsu 214122, China)

Vector map simplification plays an important role in the research on terrain simulation, cartographic generalization, and so on. As it is difficult to balance the overall shape and local feature point accuracy of the simplified curve with the existing algorithms, a vector map simplification method based on progressive iterative approximation (PIA) with B-spline curve was proposed. First, select the feature point sequence that can maintain the contour of the curve with the largest amount of information, and use it as the initial control point sequence to obtain the corresponding nonuniform cubic B-spline curve. Secondly, it obtained a series of curves that were gradually fitting the real one by iteratively adjusting the control points according to the bias between the fitted curve and the feature points until the accuracy requirements were met. The experiments result show that the PIA method can not only keep the overall geometry of the map curve, but also achieve high-precision approximation at feature points while meeting the global bias requirements.

map synthesis; curve; spline; progressive-iterative approximation; simplification

TP 391

10.11996/JG.j.2095-302X.2021060979

A

2095-302X(2021)06-0979-08

2021-01-31；

2021-03-10

國(guó)家自然科學(xué)基金項(xiàng)目(61602213，61772013)；國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2017YFB0202303)

周 晨(1994-)，男，安徽宿州人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：6181611034@stu.jiangnan.edu.cn

陳 偉(1986–)，男，江蘇寶應(yīng)人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)、計(jì)算機(jī)圖形學(xué)等。E-mail：wchen_jdsm@163.com

31 January，2021；

10March，2021

National Natural Science Foundation of China (61602213，61772013); TheNational Key R&D Program of China (2017YFB0202303)

ZHOU Chen (1994-), male, master student. His main research interest covers computer graphics. E-mail：6181611034@stu.jiangnan.edu.cn

CHEN Wei (1986–), male, associate professor, Ph.D. His main research interests cover computer aided geometric design, computer graphics, etc. E-mail：wchen_jdsm@163.com