基于doogles-pecker算法的化简质量研究

基于doogles-pecker算法的化简质量研究

在当今快速通信的信息社会中，为了快速处理和更新信息数据，有必要简化信息数据。Douglas-Peucker算法作为一种代表性的矢量线要素化简算法,在地理信息处理中发挥着重要作用。该算法可称作“数学最优”,对原线要素视觉表示最好,在分级结构、多尺度处理、图像处理、计算几何等多领域广泛应用,使其成为最经典的线要素化简方法。运行Douglas-Peucker算法时只需要指定一个参数值(又称为阈值)。阈值的选择直接影响到化简结果和线要素的最终形态。在实际应用时,线要素化简的最佳阈值通常通过试验来确定。该阈值确定的关键在于对化简结果的评价,人们从视觉感受或经验角度定性分析及评价化简结果的质量,平衡线要素表示质量与数据量间的关系,确定最好的线要素化简结果,进而确定阈值。该评价过程具有很大的不确定性,不同的人可能对同样的化简过程得出差异较大的化简结果。化简过程可以从几何、艺术、传输、技术、表示法等多个方面加以评价,是一个灵活的、多层次的智能加工过程。化简结果是否达到要求,也需要从几何约束、拓扑约束、结构约束、Gestalt约束等多个方面加以衡量。从数学角度就已经提出了许多针对线要素复杂性的测量方法,如应用于单个线要素的“单属性测量”,及应用于线要素化简前后几何对比的“位移或比较测量”,按几何属性还可以细分为长度测量、密度测量、角度测量及弧度测量等。可以说,线要素化简的评价结果“没有最好,只有更好”,利用尽可能少的数据量表示质量尽可能高的线要素信息是判断一个化简算法好坏的最高准则。依据具体的Douglas-Peucker算法实验结果数据,从分析化简算法中阈值与评价化简结果的几个重要几何指标的关系着手,利用曲线拟合法,建立阈值与几何指标的函数关系,通过分析函数曲线特征,确定最优的化简算法阈值。所用试验数据为经过处理的Shape格式全国主要道路线要素数据,采用WGS84坐标系,数据单位为度。Shape数据仅含有简单线要素对象(Polyline),即道路与单路径(SinglePath)线要素对象间属一一对应关系。全部数据共含22629条线性道路,道路总长计约为502741km,总共由366813个基本点要素构成,每条线要素平均长度约22km,平均由16.2个点要素构成。1道路几何属性信息利用迭代方法,规定Douglas-Peucker算法有意义的阈值取值范围和增长步长,依次生成均匀布满整个阈值取值域的线要素化简结果,记录各次化简时所需统计的度量数据值。以下是算法执行的伪函数。/*Douglas-Peucker算法阈值迭代执行函数ptLines-线要素集;dmin,dmax-化简阈值的最小、最大值*/AnalyseDP(ptLines,dmin,dmax,dlnterval){/*阈值的迭代*/for(doubledVal=dmin,dVal<dmax,daVl+=dlnterval){/*遍历线要素集中所有线要素*/foreachptLineinptLines{统计原线要素ptLine的几何属性信息;/*线要素化简算法/*Douglas-Peucker(ptLine,dVal);统计化简后线要素ptLine相应的几何属性信息;}统计线要素集ptLines化简前后的几何属性信息;输出线要素集ptLines化简前后的几何属性信息;}}此处所统计的与阈值取值相关的化简前后道路的几何属性信息包括:道路总长度、构成全部道路总点数、道路的平均长度、构成每条道路的平均点数等信息。因试验用Shape数据由以度为单位的地理坐标值构成,程序运行所取的阈值dThresh范围相对较小,取值区间为[0.0001,0.0700],所取步长为0.0003°,由此共取得235组等阈值间隔统计数据。2do膜拟合优度函数的确定基于最小二乘法曲线拟合是指:对给定的一组数据(xi,f(xi))(i=0,1,…,m),要求在函数类φ=span{φ1,…,φn}中指定一个函数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)。对于函数φ类,根据实际情况可以选择不同的函数类型。最常见的函数有:指数函数y=cebx,线性函数y=ax+b,对数函数y=clnx+b,多项式函数y=b+c0x+c1x2+c2x3+…+cixi+1,以及幂函数y=cxb等。具体拟合时,首先在样本数据中取Douglas-Peucker算法两组(含阈值)相关数据,分别用以上函数加以拟合,取相对简单且曲线拟合优度最佳(优度值最接近1)的函数作为最优拟合函数。在此,分别确定了阈值-长度与阈值-点数间的拟合函数。2.1阈值-长度拟合长度有两类变量,一类是全部线要素长度之和构成的总长度,Douglas-Peucker算法随化简程度的增加,线要素总长度会趋于变短;另一类是全部线要素长度平均值。假定线要素化简前后总长度分别为dOrigTotalLen和dSimpTotalLen,化简前后平均长度分别为dOrigAverLen和dSimpAverLen,线要素总数为lFeatureNum。则它们之间有如下关系:dOrigAverLen=dOrigTotalLen/lFeatureNumdSimpAverLen=dSimpTotalLen/lFeatureNum在线要素数据不变的前提下,线要素的总长度(化简前后)与线要素的平均长度(化简前后)有着确定的正比函数关系。因此,只需求出其中一条拟合函数就可表示阈值与长度的关系。以线要素平均长度为对象,所得阈值-长度散点图及相应的拟合曲线图分别如图1～图4所示。各拟合曲线图中,分别标出了相应的函数关系式,及曲线拟合优度R2的值。从图中可以看出,三次多项式函数与其他函数相比拟合较好。所得三次多项式函数及最优度为y=-5986x3+1010x2-73.17x+22.23,R2=0.999。2.2线要素平均共享Douglas-Peucker化简算法中阈值与线要素点数的关系中,点数的概念既可指全部线要素中全部点数之和,也可指构成线要素的平均点数,两者在Douglas-Peucker算法中有着确定的线性关系,因此只需要任选其中一种点数概念即可。在此分析阈值与全部线要素点数和的关系如图5～图7所示。从曲线优度值可以看出,乘幂函数曲线拟合效果最好。所得最优拟合曲线及其最优度为y=16205x-0.37,R2=0.957。图8给出了最优拟合曲线的局部放大图。2.3阈值-整合性拟合从所建阈值与长度、点数之间的两个曲线拟合函数公式可以看出,点数与阈值呈指数为负的乘幂函数关系,对较小的阈值变化非常敏感。随着阈值的增大,点数变量对阈值变化敏感度逐步减小,并在理论上逐渐接近于恒定值。这在实际情况中对应于阈值足够大时线要素化简为只余首末两点的极值情况;从长度-阈值函数的关系可以看出,试验数据与线性函数曲线的最优度达0.941,长度值的变化对阈值变化相对较稳定,长度值随阈值增加稳步缩短。线要素化简的目的是为了减少数据量,提高线要素表示和处理效率。为了在压缩率与质量间找到最佳平衡点,主要应考虑代表线要素数据量的总点数与阈值间的关系。依据阈值-点数最优拟合曲线,只要找到该曲线快速下降的最大曲率点,该点处的阈值即代表压缩率与质量间的最大平衡点。阈值大于该点后,对数据压缩率影响越来越小,同时还会严重影响到线要素表示质量。对于给定函数y=f(x),曲率计算公式为k=|y″(1+y′2)3/2|将阈值-点数拟合函数代入曲率计算公式可得k=8214.3145x-2.37(1+3595017.2225x-1.8769)3/2其中,阈值的范围取x∈(0,0.06]。对曲率求导数并令其为0,得曲率导数方程,使该方程成立的x的值,即为拟合函数的最大曲率点。由此,x≈0.00103,相应拟合函数值y=205536。由图8可看出,曲线与采样数据在此处的拟合有一定偏差,因此取与函数y值最接近的采样点阈值作为最佳阈值,可得dThreshoptimize=0.0022。此时,点数据量应压缩为原数据量的40.88%,线要素平均长度缩短0.44%。道路数据化简前后局部效果如图9所示。3利用化简阈值进行的数据分析1)在试验基础上建立的化简阈值与长度、点数之间的最优拟合函数,使阈值与化简结果的关系有了定性的、图形化的、更直观形象的认识。通过分析阈值-点数拟合函数的曲率性质,得到了平衡压缩效率与数据质量的压缩算法最佳阈值。从化简对比图(图9)可以看出,在相对中小比例尺条件下,化简对线要素质量影响并不明显。但在较大比例尺下,能够看出线要素发生明显变化。因此,此处的研究方法适合于对海量线要素数据进行分析处理的情况。可以先抽取一定量有代表性的样本数据进行化简阈值的曲线拟合分析,确定最佳阈值,再使用该阈值对海量线要素数据进行分析处理。2)本方法还可将化简结果做一定的改进,改善线要素的显示与输出效果。具体做法是:先用Li-Opensh