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

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

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