基于doogles-pecker算法的化簡質(zhì)量研究

在當今快速通信的信息社會中，為了快速處理和更新信息數(shù)據(jù)，有必要簡化信息數(shù)據(jù)。Douglas-Peucker算法作為一種代表性的矢量線要素化簡算法,在地理信息處理中發(fā)揮著重要作用。該算法可稱作“數(shù)學最優(yōu)”,對原線要素視覺表示最好,在分級結(jié)構(gòu)、多尺度處理、圖像處理、計算幾何等多領(lǐng)域廣泛應(yīng)用,使其成為最經(jīng)典的線要素化簡方法。運行Douglas-Peucker算法時只需要指定一個參數(shù)值(又稱為閾值)。閾值的選擇直接影響到化簡結(jié)果和線要素的最終形態(tài)。在實際應(yīng)用時,線要素化簡的最佳閾值通常通過試驗來確定。該閾值確定的關(guān)鍵在于對化簡結(jié)果的評價,人們從視覺感受或經(jīng)驗角度定性分析及評價化簡結(jié)果的質(zhì)量,平衡線要素表示質(zhì)量與數(shù)據(jù)量間的關(guān)系,確定最好的線要素化簡結(jié)果,進而確定閾值。該評價過程具有很大的不確定性,不同的人可能對同樣的化簡過程得出差異較大的化簡結(jié)果。化簡過程可以從幾何、藝術(shù)、傳輸、技術(shù)、表示法等多個方面加以評價,是一個靈活的、多層次的智能加工過程?；喗Y(jié)果是否達到要求,也需要從幾何約束、拓撲約束、結(jié)構(gòu)約束、Gestalt約束等多個方面加以衡量。從數(shù)學角度就已經(jīng)提出了許多針對線要素復雜性的測量方法,如應(yīng)用于單個線要素的“單屬性測量”,及應(yīng)用于線要素化簡前后幾何對比的“位移或比較測量”,按幾何屬性還可以細分為長度測量、密度測量、角度測量及弧度測量等?？梢哉f,線要素化簡的評價結(jié)果“沒有最好,只有更好”,利用盡可能少的數(shù)據(jù)量表示質(zhì)量盡可能高的線要素信息是判斷一個化簡算法好壞的最高準則。依據(jù)具體的Douglas-Peucker算法實驗結(jié)果數(shù)據(jù),從分析化簡算法中閾值與評價化簡結(jié)果的幾個重要幾何指標的關(guān)系著手,利用曲線擬合法,建立閾值與幾何指標的函數(shù)關(guān)系,通過分析函數(shù)曲線特征,確定最優(yōu)的化簡算法閾值。所用試驗數(shù)據(jù)為經(jīng)過處理的Shape格式全國主要道路線要素數(shù)據(jù),采用WGS84坐標系,數(shù)據(jù)單位為度。Shape數(shù)據(jù)僅含有簡單線要素對象(Polyline),即道路與單路徑(SinglePath)線要素對象間屬一一對應(yīng)關(guān)系。全部數(shù)據(jù)共含22629條線性道路,道路總長計約為502741km,總共由366813個基本點要素構(gòu)成,每條線要素平均長度約22km,平均由16.2個點要素構(gòu)成。1道路幾何屬性信息利用迭代方法,規(guī)定Douglas-Peucker算法有意義的閾值取值范圍和增長步長,依次生成均勻布滿整個閾值取值域的線要素化簡結(jié)果,記錄各次化簡時所需統(tǒng)計的度量數(shù)據(jù)值。以下是算法執(zhí)行的偽函數(shù)。/*Douglas-Peucker算法閾值迭代執(zhí)行函數(shù)ptLines-線要素集;dmin,dmax-化簡閾值的最小、最大值*/AnalyseDP(ptLines,dmin,dmax,dlnterval){/*閾值的迭代*/for(doubledVal=dmin,dVal<dmax,daVl+=dlnterval){/*遍歷線要素集中所有線要素*/foreachptLineinptLines{統(tǒng)計原線要素ptLine的幾何屬性信息;/*線要素化簡算法/*Douglas-Peucker(ptLine,dVal);統(tǒng)計化簡后線要素ptLine相應(yīng)的幾何屬性信息;}統(tǒng)計線要素集ptLines化簡前后的幾何屬性信息;輸出線要素集ptLines化簡前后的幾何屬性信息;}}此處所統(tǒng)計的與閾值取值相關(guān)的化簡前后道路的幾何屬性信息包括:道路總長度、構(gòu)成全部道路總點數(shù)、道路的平均長度、構(gòu)成每條道路的平均點數(shù)等信息。因試驗用Shape數(shù)據(jù)由以度為單位的地理坐標值構(gòu)成,程序運行所取的閾值dThresh范圍相對較小,取值區(qū)間為[0.0001,0.0700],所取步長為0.0003°,由此共取得235組等閾值間隔統(tǒng)計數(shù)據(jù)。2do膜擬合優(yōu)度函數(shù)的確定基于最小二乘法曲線擬合是指:對給定的一組數(shù)據(jù)(xi,f(xi))(i=0,1,…,m),要求在函數(shù)類φ=span{φ1,…,φn}中指定一個函數(shù)y=s*(x),使誤差平方和最小,即∥δ∥22=m∑i=0δ2i=m∑i=0(s*(xi)-f(xi))2=mins∈φm∑i=0(s(xi)-f(xi))2∥δ∥22=∑i=0mδ2i=∑i=0m(s?(xi)?f(xi))2=mins∈φ∑i=0m(s(xi)?f(xi))2其中,s(x)=a0φ0(x)+a1φ1(x)+…+anφn(x),(n<m)。對于函數(shù)φ類,根據(jù)實際情況可以選擇不同的函數(shù)類型。最常見的函數(shù)有:指數(shù)函數(shù)y=cebx,線性函數(shù)y=ax+b,對數(shù)函數(shù)y=clnx+b,多項式函數(shù)y=b+c0x+c1x2+c2x3+…+cixi+1,以及冪函數(shù)y=cxb等。具體擬合時,首先在樣本數(shù)據(jù)中取Douglas-Peucker算法兩組(含閾值)相關(guān)數(shù)據(jù),分別用以上函數(shù)加以擬合,取相對簡單且曲線擬合優(yōu)度最佳(優(yōu)度值最接近1)的函數(shù)作為最優(yōu)擬合函數(shù)。在此,分別確定了閾值-長度與閾值-點數(shù)間的擬合函數(shù)。2.1閾值-長度擬合長度有兩類變量,一類是全部線要素長度之和構(gòu)成的總長度,Douglas-Peucker算法隨化簡程度的增加,線要素總長度會趨于變短;另一類是全部線要素長度平均值。假定線要素化簡前后總長度分別為dOrigTotalLen和dSimpTotalLen,化簡前后平均長度分別為dOrigAverLen和dSimpAverLen,線要素總數(shù)為lFeatureNum。則它們之間有如下關(guān)系:dOrigAverLen=dOrigTotalLen/lFeatureNumdSimpAverLen=dSimpTotalLen/lFeatureNum在線要素數(shù)據(jù)不變的前提下,線要素的總長度(化簡前后)與線要素的平均長度(化簡前后)有著確定的正比函數(shù)關(guān)系。因此,只需求出其中一條擬合函數(shù)就可表示閾值與長度的關(guān)系。以線要素平均長度為對象,所得閾值-長度散點圖及相應(yīng)的擬合曲線圖分別如圖1～圖4所示。各擬合曲線圖中,分別標出了相應(yīng)的函數(shù)關(guān)系式,及曲線擬合優(yōu)度R2的值。從圖中可以看出,三次多項式函數(shù)與其他函數(shù)相比擬合較好。所得三次多項式函數(shù)及最優(yōu)度為y=-5986x3+1010x2-73.17x+22.23,R2=0.999。2.2線要素平均共享Douglas-Peucker化簡算法中閾值與線要素點數(shù)的關(guān)系中,點數(shù)的概念既可指全部線要素中全部點數(shù)之和,也可指構(gòu)成線要素的平均點數(shù),兩者在Douglas-Peucker算法中有著確定的線性關(guān)系,因此只需要任選其中一種點數(shù)概念即可。在此分析閾值與全部線要素點數(shù)和的關(guān)系如圖5～圖7所示。從曲線優(yōu)度值可以看出,乘冪函數(shù)曲線擬合效果最好。所得最優(yōu)擬合曲線及其最優(yōu)度為y=16205x-0.37,R2=0.957。圖8給出了最優(yōu)擬合曲線的局部放大圖。2.3閾值-整合性擬合從所建閾值與長度、點數(shù)之間的兩個曲線擬合函數(shù)公式可以看出,點數(shù)與閾值呈指數(shù)為負的乘冪函數(shù)關(guān)系,對較小的閾值變化非常敏感。隨著閾值的增大,點數(shù)變量對閾值變化敏感度逐步減小,并在理論上逐漸接近于恒定值。這在實際情況中對應(yīng)于閾值足夠大時線要素化簡為只余首末兩點的極值情況;從長度-閾值函數(shù)的關(guān)系可以看出,試驗數(shù)據(jù)與線性函數(shù)曲線的最優(yōu)度達0.941,長度值的變化對閾值變化相對較穩(wěn)定,長度值隨閾值增加穩(wěn)步縮短。線要素化簡的目的是為了減少數(shù)據(jù)量,提高線要素表示和處理效率。為了在壓縮率與質(zhì)量間找到最佳平衡點,主要應(yīng)考慮代表線要素數(shù)據(jù)量的總點數(shù)與閾值間的關(guān)系。依據(jù)閾值-點數(shù)最優(yōu)擬合曲線,只要找到該曲線快速下降的最大曲率點,該點處的閾值即代表壓縮率與質(zhì)量間的最大平衡點。閾值大于該點后,對數(shù)據(jù)壓縮率影響越來越小,同時還會嚴重影響到線要素表示質(zhì)量。對于給定函數(shù)y=f(x),曲率計算公式為k=|y″(1+y′2)3/2|將閾值-點數(shù)擬合函數(shù)代入曲率計算公式可得k=8214.3145x-2.37(1+3595017.2225x-1.8769)3/2其中,閾值的范圍取x∈(0,0.06]。對曲率求導數(shù)并令其為0,得曲率導數(shù)方程,使該方程成立的x的值,即為擬合函數(shù)的最大曲率點。由此,x≈0.00103,相應(yīng)擬合函數(shù)值y=205536。由圖8可看出,曲線與采樣數(shù)據(jù)在此處的擬合有一定偏差,因此取與函數(shù)y值最接近的采樣點閾值作為最佳閾值,可得dThreshoptimize=0.0022。此時,點數(shù)據(jù)量應(yīng)壓縮為原數(shù)據(jù)量的40.88%,線要素平均長度縮短0.44%。道路數(shù)據(jù)化簡前后局部效果如圖9所示。3利用化簡閾值進行的數(shù)據(jù)分析1)在試驗基礎(chǔ)上建立的化簡閾值與長度、點數(shù)之間的最優(yōu)擬合函數(shù),使閾值與化簡結(jié)果的關(guān)系有了定性的、圖形化的、更直觀形象的認識。通過分析閾值-點數(shù)擬合函數(shù)的曲率性質(zhì),得到了平衡壓縮效率與數(shù)據(jù)質(zhì)量的壓縮算法最佳閾值。從化簡對比圖(圖9)可以看出,在相對中小比例尺條件下,化簡對線要素質(zhì)量影響并不明顯。但在較大比例尺下,能夠看出線要素發(fā)生明顯變化。因此,此處的研究方法適合于對海量線要素數(shù)據(jù)進行分析處理的情況?？梢韵瘸槿∫欢坑写硇缘臉颖緮?shù)據(jù)進行化簡閾值的曲線擬合分析,確定最佳閾值,再使用該閾值對海量線要素數(shù)據(jù)進行分析處理。2)本方法還可將化簡結(jié)果做一定的改進,改善線要素的顯示與輸出效果。具體做法是:先用Li-Opensh