一種Douglas-Peucker與Li-Openshaw結合改進的曲線化簡方法

顧 騰, 陳曉勇， 劉成強

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

一種Douglas-Peucker與Li-Openshaw結合改進的曲線化簡方法

顧 騰1, 陳曉勇1， 劉成強2

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

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

Douglas-Peucker；Li-Openshaw；線化簡

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

1 Douglas-Peucker和Li-Openshaw的結合

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

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

D-P算法原理如圖1a，先將折線ABCDEFG兩端AG連接成一條線。首先計算出折線上到線AG的垂直距離d最大的點C；如果d < threshold，則將線段AG作為該折線近似。如果d > threshold，則用點B將該折線分為CA，CG兩個部分；繼續(xù)重復以上步驟。最后依次連接各個分割點形成的折線，即可以作為原折線的近似。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)按照目標比例尺和原比例尺來估算出圓形SVO的尺寸R。

(1)

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

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

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

(4)從R2點開始重復2、3步驟，直到末端點D不在SVO圓內結束。

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

1.3 Douglas-Peucker與Li-Openshaw結合改進型算法

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

圖2 D-P與L-O結合改進算法Fig.2 Combined Douglas-Peuceker with Li-Openshaw improved algorithm

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

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

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

2 實驗及分析

2.1 改進算法結果

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

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

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

實線是原始地圖數據，虛線是化簡后的結果。

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

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

2.2 結果分析

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

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

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

表1 道路矢量位移與面積位移評價結果

表2 水系矢量位移與面積位移評價結果

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

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

(2)

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

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

(3)

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

表3 道路位移標準差與位置誤差評價結果

表4 水系位移標準差與位置誤差評價結果

對比以上兩種評價指標，改進后的算法都展現出良好的性能。

4 結論與展望

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

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

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

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

朱鯤鵬,武芳,王輝連,等.2007.Li-Openshaw算法的改進與評價[J],測繪學報,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è)科研專項(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

顧騰,陳曉勇，劉成強.2016. 一種Douglas-Peucker與Li-Openshaw結合改進的曲線化簡方法 [J].東華理工大學學報：自然科學版，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.