顧 騰, 陳曉勇， 劉成強(qiáng)

(1.東華理工大學(xué) 測繪工程學(xué)院，江西 南昌 330013；2.中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083)

一種Douglas-Peucker與Li-Openshaw結(jié)合改進(jìn)的曲線化簡方法

顧 騰1, 陳曉勇1， 劉成強(qiáng)2

(1.東華理工大學(xué) 測繪工程學(xué)院，江西 南昌 330013；2.中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083)

Douglas-Pecuker算法能夠很好的保證對線的特征彎曲點(diǎn)保留和對點(diǎn)其它非特征點(diǎn)的壓縮，但化簡出來的結(jié)果過于生硬且在特征點(diǎn)處產(chǎn)生尖角，不能夠在地圖綜合中普遍使用。Li-Openshaw算法能很好地圓滑線的尖角且不會顯得過于生硬，但也會對線的特征點(diǎn)圓滑。提出了將兩者結(jié)合的改進(jìn)型算法，做到特征點(diǎn)保留且做到在其它處化簡。并將該改進(jìn)型算法與另外兩種算法進(jìn)行實(shí)驗(yàn)驗(yàn)證對比。實(shí)驗(yàn)結(jié)果表明，兩者結(jié)合的改進(jìn)型算法展現(xiàn)出了兩者的優(yōu)點(diǎn)，且能夠在自動制圖中得到應(yīng)用，優(yōu)化地理線要素和面要素的化簡。

Douglas-Peucker；Li-Openshaw；線化簡

地圖由以前的多年更新一次到現(xiàn)在的一年一次，甚至半年一次。這對制圖工作者帶來巨大的工作量，迫切需要一種能夠代替人機(jī)交互制圖的軟件。在地圖綜合中線要素占了很高的比例，比如道路、河流這些也是極其重要的地理要素。對于這類線要素的化簡已經(jīng)有Douglas-Peucker (Douglas et al., 1973)、Li-Openshaw( Li et al.,1994)、弦比弧算法(Nako et al.,2003)，每種算法都有自身的優(yōu)缺點(diǎn)，比如：Douglas-Peucker算法能夠很好的保留曲線特征，但缺點(diǎn)是不能對曲線做到很好的自然概括；Li-Openshaw算法可以對曲線進(jìn)行自然融合概括但缺點(diǎn)也對曲線特征進(jìn)行概括；弧比弦算法具有對曲線彎曲處概括的優(yōu)點(diǎn)，但可能產(chǎn)生連續(xù)的節(jié)點(diǎn)剔除 而使局部曲線形狀有較大的變形。如何做到能夠在實(shí)際制圖中得到應(yīng)用這才是最重要的。

1 Douglas-Peucker和Li-Openshaw的結(jié)合

1.1 Douglas-Peucker算法(簡稱D-P算法)

D-P算法主要是對曲線上的點(diǎn)進(jìn)行壓縮，并且保留線的主要特征。該類算法在很對線的壓縮中應(yīng)用廣泛，其原理簡單，效率高且不會產(chǎn)生多余的點(diǎn)，這是一類較早出現(xiàn)的算法，亦是一類非常經(jīng)典的算法，目前很多算法在結(jié)果對比的時候都會與之做比照。

D-P算法原理如圖1a，先將折線ABCDEFG兩端AG連接成一條線。首先計算出折線上到線AG的垂直距離d最大的點(diǎn)C；如果d < threshold，則將線段AG作為該折線近似。如果d > threshold，則用點(diǎn)B將該折線分為CA，CG兩個部分；繼續(xù)重復(fù)以上步驟。最后依次連接各個分割點(diǎn)形成的折線，即可以作為原折線的近似。ACEG為原折線化簡后的折線。如圖對比使用D-P算法化簡前后的線段。

圖1 Douglas-Peucker與Li-Openshaw算法Fig.1 Dougals-Peucker and Li-Openshaw algorithma.Douglas-Peucker算法；b.Li-Openshaw算法圖

1.2 Li-Openshaw算法(簡稱L-D算法)

L-O算法的基本思想：

(1)按照目標(biāo)比例尺和原比例尺來估算出圓形SVO的尺寸R。

(1)

其中St為需要化簡后的目標(biāo)比例尺，Sf為原比例尺。D是一個參數(shù)，為化簡后地圖上的SVO的參數(shù)。Muller則認(rèn)為在地圖上D取0.4mm為能保證視覺分辨的最小值。

(2)如圖1b所示，首先確定圓形SVO的起始位置，一般設(shè)為第一端點(diǎn)A，當(dāng)在R1處，以R1為圓心，R為半徑畫圓與原折線交于R2處。

(3)選擇R1R2連線的中點(diǎn)F為綜合后的選取點(diǎn)。

(4)從R2點(diǎn)開始重復(fù)2、3步驟，直到末端點(diǎn)D不在SVO圓內(nèi)結(jié)束。

在圖1b中，折線ABCD為原化簡前線段，AEFGHID為綜合化簡后的結(jié)果。

1.3 Douglas-Peucker與Li-Openshaw結(jié)合改進(jìn)型算法

基于以上的分析可以發(fā)現(xiàn)，單獨(dú)應(yīng)用D-P算法會使線要素化簡結(jié)果粗糙、僵硬，單獨(dú)應(yīng)用L-O算法則會出現(xiàn)保留點(diǎn)混亂、曲線整體形狀變形等情況，基于線化簡的目的，以盡量保持線要素特征點(diǎn)、保證線要素形狀特征、線要素化簡結(jié)果圓滑美觀為原則，本文提出一種Douglas-Peucker與Li-Openshaw結(jié)合的簡單曲線化簡方法，對線化簡算法進(jìn)行改進(jìn)。其基本原理如圖2：

圖2 D-P與L-O結(jié)合改進(jìn)算法Fig.2 Combined Douglas-Peuceker with Li-Openshaw improved algorithm

(1)對進(jìn)行綜合化簡的曲線采用D-P算法計算出折線上的滿足垂直距離大于距離閾值的拐點(diǎn)，如圖2所示，B，C，D，F(xiàn)為滿足條件的拐點(diǎn)。

(2)使用L-O算法從起點(diǎn)A為圓心，R為半徑的圓形SVO對該折線進(jìn)行化簡。對于拐點(diǎn)聚集處(如圖2中拐點(diǎn)B處)，以B點(diǎn)為圓心，畫一個半徑為R1(R1=R)的圓O，如果B點(diǎn)前后有拐點(diǎn)(C、D)在圓O范圍內(nèi)，則記錄C，D，視情況對C，D兩點(diǎn)進(jìn)行處理。如果需要處理C，D兩點(diǎn)，則以B點(diǎn)為圓心，更改SVO半徑(如1/2 R)重新畫圓對C，D圓滑概括；如果不需要則不做圓滑處理。對于拐點(diǎn)稀疏處(如圖2中拐點(diǎn)F處)，處理如下：以F點(diǎn)為圓心，畫一個半徑為R1(R1=R)的圓O進(jìn)行圓滑處理。

順序處理直至到達(dá)末端的I結(jié)束。圖2中，ABCEFI為原曲線，ABCDEGHI為化簡后曲線。

2 實(shí)驗(yàn)及分析

2.1 改進(jìn)算法結(jié)果

由于本文是借鑒NewMap軟件底層平臺，采用C++語言編程進(jìn)行算法實(shí)現(xiàn)。本文算法是Douglas-Peucker與Li-OpenShaw結(jié)合改進(jìn)算法，因此綜合化簡之后與這兩種算法進(jìn)行比較分析。本文采用了這三種算法在參數(shù)一定(1∶1萬到1∶10萬化簡)的情況下，對南方某城市地圖1：1萬道路與水系數(shù)據(jù)綜合化簡(圖3、4)。

按照本次算法的綜合化簡思路，綜合化簡后的結(jié)果應(yīng)該加貼切原始曲線相比另外兩種算法，從目視上看，結(jié)果與原思路結(jié)果一致。圖3a中，D-P算法在對道路化簡時保留住原始特征點(diǎn)，而且對線要素也做到了一個很好的壓縮，但是在制圖綜合中適用性不是很強(qiáng)，很多情況下需要對地理線要素做圓滑處理；圖3b道路線是采用L-O算法化簡前后的對比圖，從圖中可以看出L-O算法在綜合化簡中對道路線做到了圓滑過濾，但在現(xiàn)實(shí)制圖綜合中不光要求圓滑，還要求保留原有的特征彎曲不作處理或者是細(xì)微處理；圖3c采用本文介紹的兩者結(jié)合改進(jìn)算法對道路線綜合前后的對比圖，從圖中可以明顯看出其綜合化簡后的結(jié)構(gòu)由于前兩者的化簡結(jié)果，不僅在對道路線要素化簡中做到了圓滑，而且還能夠保留原有的特征彎曲，這極大的增加了該算法在制圖綜合過程中適用性。

圖4是對南方某城市1∶1萬水系數(shù)據(jù)化簡結(jié)果，比較這三種算法對水系化簡結(jié)果，再次驗(yàn)證了本文算法的結(jié)合了兩種經(jīng)典化簡算法的優(yōu)點(diǎn)，在大彎曲的地方進(jìn)行了特征保留。

實(shí)線是原始地圖數(shù)據(jù)，虛線是化簡后的結(jié)果。

圖3 三種算法對1∶1萬道路要素化簡結(jié)果對比Fig.3 A comparison of three algorithms for 1∶1 million scale road simplification resultsa.Douglas-Peucker算法；b.Li-OpenShaw算法； c.本文改進(jìn)算法

圖4 三種算法對1∶1萬水系要素化簡結(jié)果對比Fig.4 A comparison of three algorithms for 1∶1 million scale river simplification resultsa.Douglas-Peucker算法;b.Li-Openshaw算法;c.本文改進(jìn)算法

2.2 結(jié)果分析

由White提出的地理線要素化簡的兩個評價指標(biāo)：矢量位移，面積位移(White，1985)?；喓蟮那€與原始曲線之間對應(yīng)點(diǎn)位位置偏差稱之為矢量位移。面積位移則指的是化簡后的新曲線與原始曲線之間所圍成部分的面積(劉慧敏等,2011;鄧敏等,2009)。如圖5所示顯而易見，算法化簡結(jié)果的優(yōu)良取決于面積位移和矢量位移，本文采以上兩個定量指標(biāo)進(jìn)行評價。

圖5 評價指標(biāo)Fig.5 The parameters for the evaluationa.矢量位移;b.面積位移

分別對三種算法對道路線和水系線做綜合化簡后的結(jié)果進(jìn)行指標(biāo)評價，做簡單的比較可以發(fā)現(xiàn)改進(jìn)后的算法不光在直接的視覺感官上看效果優(yōu)于其它兩種算法，而且從其中兩項(xiàng)評價指標(biāo)也能看出結(jié)果也是優(yōu)于其它兩種算法。從整體指標(biāo)來看，本文改進(jìn)型算法在參數(shù)一定(1∶1萬至1∶10萬)，化簡各項(xiàng)指標(biāo)下都優(yōu)于其它兩種算法，展現(xiàn)出D-P與L-O算法的優(yōu)點(diǎn)。

表1 道路矢量位移與面積位移評價結(jié)果

表2 水系矢量位移與面積位移評價結(jié)果

由Muller提出的關(guān)于評價位移指標(biāo)的位移標(biāo)準(zhǔn)差(Muller,1987)，該評價指標(biāo)適用于不同方法對同一線要素化簡的結(jié)果評價(Joao E M, 1998; 朱鯤鵬等，2007；武芳等，2008)。具體計算方法：

SMD(%)100(1-(S-D)/S)

(2)

式中的S為算法化簡后，在原始曲線上位移最大的點(diǎn)到原始曲線首末端點(diǎn)連線的距離，D為該點(diǎn)化簡前后的位移值。

當(dāng)然此處只用位移標(biāo)準(zhǔn)差來單獨(dú)評價是不夠，通過分析位移標(biāo)準(zhǔn)差時發(fā)現(xiàn)，該評價指標(biāo)值對局部最大值進(jìn)行了評價，因此評價不夠精確。進(jìn)一步采用位移位置誤差來評價化簡前后的整體位移，使用化簡前后曲線相交圍成的面積與原曲線長度的比值。具體計算方法：

(3)

式中，ΔS表示曲線化簡前后相交圍成的面積；L表示原始曲線的長度。

表3 道路位移標(biāo)準(zhǔn)差與位置誤差評價結(jié)果

表4 水系位移標(biāo)準(zhǔn)差與位置誤差評價結(jié)果

對比以上兩種評價指標(biāo)，改進(jìn)后的算法都展現(xiàn)出良好的性能。

4 結(jié)論與展望

本文在制圖綜合這樣一個大背景下，結(jié)合實(shí)際要求，對地理線要素化簡算法研究。發(fā)現(xiàn)現(xiàn)有算法的在對線要素化簡實(shí)際應(yīng)用受限。提出了Douglas-Peucker與Li-Openshaw兩者結(jié)合改進(jìn)的算法；該方法既能夠在曲線特征保留，又能對其他非特征化簡；并通過實(shí)驗(yàn)并采用4種不同的定量指標(biāo)進(jìn)行評價，結(jié)果表明本文提出的改進(jìn)算法在1∶1萬至1∶10萬化簡結(jié)果的正確性和有效性。但還需要更深一步的研究內(nèi)容有：考慮綜合前后比例尺跨度太大情況下的一種自適應(yīng)算法；考慮地理面要素，提出能針對面要素的一種能夠自適應(yīng)化簡算法。

鄧敏,陳杰,李志林,等.2009.線目標(biāo)化簡中節(jié)點(diǎn)重要性度量方法比較及垂比弦法的改進(jìn)[J].地理與地理信息科學(xué),25(1):40-43.

劉慧敏,樊子德,徐震,等.2011.曲線化簡的弧比弦算法改進(jìn)極其評價[J],地理與地理信息科學(xué),27(1),45-48.

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

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

Douglas D H，Peucker T K. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or caricature[J].Canadian Cartographer,10(2);112 -122.

Joao E M.1998. Causes and Consequences of Map Generalization[M].London: Taylor and Francis.

Li Z L,Openshaw.1994.基于客觀自然規(guī)律的線狀要素自動綜合的算法[J].武大譯文,(1)：49-58.

Muller J C.1987. Fractal and Automated Line Generalization[J].The Cartographic Journal,24(1):27-34.

Nako B,Mitropoulos V.2003. Local length ratio as a measure of critical point detection for line simplification[A].The Symposium of the 5th ICA Workshop on Progress in Automated Map Generalization.28-30.

White E.1985. Assessment of line generalization algorithms using characteristics points [J].The American Cartographer,12(1):17-27.

A modified Line Simplification Method Combined Douglas-Peucker with Li-Openshaw

GU Teng1, CHEN Xiao-yong1, LIU Cheng-qiang2

(1.School of Geomatics，East China University of Tecnology,Nanchang，JX 330013，China；2.School of Geosciences and info-Physics，Central South University，Changsha,HN 410083，China)

There are two classic line simplification algorithm:Douglas-Peucker and Li-Openshaw.Douglas-Peucker algorithm can remain bending feature points and compress other non-feature points. But the Simplification result too stiff and produces sharp in the feature point.So It can’t be widely used in map generalization.Li-Openshaw algorithm can smooth sharp line and does not seem too stiff,but will also feature a dotted line of sleek. How to combine the two algorithms and to show the advantages of both.This parper presents a modified line simplification algorithm combined the two algorithms.This method can reserve feature points and simplify others.There is a modified algorithm and two other algorithms comparative experiment in this pearper.

Douglas-Peucker；Li-Openshaw；Line Simplify

2016-09-17

測繪地理信息公益性行業(yè)科研專項(xiàng)(201512020，201512027 )

顧 騰(1993—)，男，碩士，主要從事地圖制圖與綜合研究。E-mail:tengku08@163.com

10.3969/j.issn.1674-3504.2016.04.015

O29

A

1674-3504(2016)04-0396-05

顧騰,陳曉勇，劉成強(qiáng).2016. 一種Douglas-Peucker與Li-Openshaw結(jié)合改進(jìn)的曲線化簡方法 [J].東華理工大學(xué)學(xué)報：自然科學(xué)版，39(4)：396-400.

Gu Teng,Chen Xiao-yong,Liu Cheng-qiang.2016. A modified line simplification method combined Douglas-Peucker with Li-Openshaw [J].Journal of East China University of Technology (Natural Science), 39(4)：396-400.