一种新的地理线要素分形插值方法

一种新的地理线要素分形插值方法第31卷第3期2002年8月测绘ACTAGEODAETICAetCARTOGRAPHICASINICAVo1.31.NO.3Aug.,2002文章编号:10011595(2002)03025507中图分类号:P283.7文献标识码:A一种新的地理线要素分形插值方法张华国,黄韦艮,周长宝(国家海洋局第二海洋研究所,浙江杭州310012)ANewFractalInterpolationApproachforGeographicCurveZHANGHua-guo,HUANGWeigen,ZHOUChang-bao(SecondInstituteofOceanography,StateOceanicAdministration,Hangzhou310012,China)Abstract:Automaticcartographyincludingautomaticmapgeneralizationandexpansionhasbecomeanimportantgeographicresearcharea.Automaticexpansionofthecurvesonthemapcanberealizedthroughinterpolation.However,thetraditionalmethodsforcurveinterpolationcannotdescribethecharacteristicsofthefractalstructure,thescalerelativityandspatialisotropyofthegeographiccurves.Thispaperpresentsanewfractalinterpolation.Itisbasedonthefractaltheory,Douglas-Peukeralgorithmandrandommidpointdisplacementmethod.Acasestudyhasbeendemonstrated.Thecomparisonshowsthatthenewfractalinterpolationhassomeadvantagesoverthetradition.alinterpolationmethods.Keywords:fractalgeometrytheory;Douglas-Peukeralgorithm;randommidpointdisplacementmethod;mapmaking;automaticinterpolation摘要:地图制图自动化已成为地理研究的重要内容,包括自动综合和自动扩充.地图中线要素的自动扩充是要通过插值来实现.传统的曲线插值方法没能反映地理线要素的分形结构,比例尺相关性,空间各向同性等特点.针对地理线要素的特点,基于分形几何理论,将Dou.glas.Peuker算法和随机中点移位法结合起来,提出了一种新的分形插值方法.并通过方法比较和实例分析验证了方法的可行性和有效性.关键词:分形几何理论;D.P算法;随机中点移位法;地图制图;自动插值1引言线状要素是3大地理要素之一,在地图制图,空间分析和信息处理等地理研究中经常需要进行插值运算.曲线插值方法有很多种,不过通常的多项式插值或样条插值等方法强调了光滑性,而没能体现地理线状要素复杂,精细的自相似结构.分形学方法可非常有效地描述地物现象随观测尺度变化的宏观结构动态变化和地物本身细节随观测尺度变化的微结构动态概括2J.分形方法是通过分数维来描述这些结构特点,并据此进行复杂曲线的插值,能够自动顾及到地物或现象的结构特征,具有自适应性,已被证明是一种十分有效的方法J.分形插值法通常利用迭代函数系统(IterativeFunctionSyrstem,简称IFS),通过给定的已知点构造相应的IFS,来拟合曲线或曲面.收稿日期:20010719;修回日期:2001一lll2基金项目:国家高新技术产业发展项目(计高技199912062号);浙江省海洋开发管理专用基金资助项目(0026一l?O2)作者简介:张华国(1977.),男,浙江新昌人,国家海洋局第二海洋研究所硕士研究生,从事海洋遥感与GIS理论及应用研究.256测绘第31卷但在地理研究中,这种方法通常不能反映比例尺变化1和空间变化各向同性的地学特征.本文将给出基于分形理论,综合运用Douglas?Peuk-r算法(简称D.P算法)和随机中点移位法,进行分形插值的新方法.2方法原理曲线插值就是要在不够精细的地方加入描述细节的点,并尽量反映曲线的精细特征.对于满足分形特征的地理线要素,描述的精细程度是随比例尺的不同而不一样的,比例尺越大,细节描述越详细,越能准确地反映实际的地理状况.所以,由小比例尺地图变到大比例尺地图时,就要进行插值.数字化曲线是由一系列坐标点组成的点列来表示的,插值就是根据比例尺的变化情况和原曲线的特征,在每两点问插入一定数量的描述细节特点的点,再按顺序连起来,得到新的数字化曲线.那么如何确定插值点的数量和位置成了其中的关键问题,不同的插值方法有不同的理论和方法来确定插值点.本文的方法基于分形几何理论,利用D.P算法确定插值点的数量,由随机中点移位法确定插值点的位置.2.1D.P算法D.P算法可用来估算曲线的分数维,同时也是一种很好的分形自动综合算法_4J.其原理是先将曲线的首末两点虚连一条直线,求出其余各点到该直线的距离(如图1(a)所示),选其最大者与阈值(也就是尺度,如图1(d)所示)相比较,若大于阈值,则该点保留,否则删去两点间的所有点,然后将原曲线分成两段(如图1(b)所示),各部分仍选距离最大者与阈值相比较,决定取舍,依次类推,直到无点可舍去(如图1(c)所示).图中(a)表示连接首尾两点,计算各点到此连线的距离;(b)表示保留第一个满足条件的点4;(c)表示在临界阈值(d)的情况下的简化曲线;(d)表示临界阈值.把保留下来的点依次连起来就得到了新的曲线.用不同的阈值将得到不同的曲线和长度.根据尺度与相应曲线长度组成的点列,可以求出描述曲线分形特征的分维值D.2.2随机中点移位法随机中点移位法是一种递归算法_2j,计算时先将待插的两点间连一条直线,把直线的中点向上或向下移动一个随机量,作为一个插值点,从而形成两条线段,以此来代替原线段.继续分别对两线段做上述操作,如此下去,就可以得到复杂的,满足自相似性的分形曲线.图2给出了随机中点移位法的不同递归深度(/7,=0,1,2,3)的插值情况.2l46一临界阈fd1图1Douglas-Peuker算法原理Fig.1SchematicofDougmas-Peukermethod一一图2随机中点移位法原理Fig.2Schematicofrandommidpointdisplacement2.3新的插值方法从D.P算法和随机中点移位法的原理中可以看出,D.P算法是把曲线上移位量小于某阈值的点去掉,以简化曲线.随机中点移位法则是加入随机移位量的点.所以这两种方法可以看作是互逆过程,而且几何意义是一致的.本文方法首先用D.P算法来估算曲线的分维值和无标度区,再根据曲线长度随比例尺的变化与曲线分形特征的关系l4j,导出曲线因比例尺放大所需插值点的数量.然后用随机中点移位法确定那些移位量在无标度区内的插值点的位置,再按顺序连起来得到新的曲线,完成插值过程.但由于随机中点移位法的移位方向是固定的,不能反映地理线状要素变化各向同性的特点,所以本方法改变随机中点移位法中的移位方向,使其移位垂直于原线段向左或向右移位.与图2对应,改进后的随机中点移位法的不同递归深度(凡=0,1,2,3)的插值第3期张华国等:一种新的地理线要素分形插值方法257情况如图3所示.一一图3新方法中改进的随机中点移位法原理Fig.3Schematicoftheimprovedrandommidpointdisplacementmethod3算法推导3.1基本概念实现上面讨论的插值方法,关键是要解决以下两个问题:一是每次插入点的移位量是多少?二是两点之间应该插人多少个点?为此在推导算法前,先定义移位系数(d)和递归深度(凡)这两个重要参数:移位系数:垂直移位量r与母线段长度的比值,表示插值点的移位幅度大小.递归深度:插值的最大递归水平,如图3中的凡值.它反映要插入插值点的多少.3.2基本算法对基于分形分析的曲线插值,曲线长度的变化不是线性的,而是满足曲线长度随比例尺变化公式,即推广的Beckett公式【j:(其中,.和分别为插值前后的曲线长度,1和2分别是插值前后的曲线比例尺分母.对于曲线插值,满足M1>M2和L.<L.对于由点列P,i=0,1,2,m组成的曲线,设任意两相邻点间的区间的递归深度为凡(=1,2,m),在第个区间内第k次的插值的移位系数为dj.(k=1,2,凡),则根据随机中点垂直移位法(改进的随机中点移位法)的原理,在第个区间内第k次插值后,两点间曲线的长度由fm一1变为fm,其关系为厂,=2,/(dj,f,一1)+(;)即l=,可(2)因此,当完成第个区间的插值运算后,区间内由直线段变成折线段,其长度由lj,o变为一.,两者问的关系为,=.?完成整条曲线的插值后,曲线的长度为,即M:=m(,.)(3)而插值前曲线的长度为L.=,0(4)将式(3)和(4)代人式(1)得到/1D./(5),o至此,得到了本文插值方法的基本方程(式(5),它完整表达了比例尺变化,曲线的分形特征,递归深度和移位系数等参数之间的关系.3.3算法简化式(5)虽然描述了比例尺变化,曲线的分形特征,递归深度和移位系数等参数之间的关系,但显得比较复杂,数值计算和插值的工作量很大.为此在实际的插值中还得对式(5)进行简化.在本研究中,进行地理曲线插值时,认为对整条曲线的任意两相邻点间插入相同数量的插值点,也就是递归深度凡=1,2,m)取固定值凡.同时,移位系数是表示插值点移位幅度的参量,由于插值是对原曲线细节部分的细化,因此变化幅度不应太大,同时也是为了数值计算的方便,所以对整条曲线的移位系数取定值,即dr.k=d,其中:1,2,m;k=1,2,凡.因此式(5)可简化为D-1:.0因为凡和d都取了固定值,与和m无关,所以式(6)可简化为(:(/1+4d2)n258测绘第31卷由上式可解得一二g一丁n由四舍五入法取正整数.其中比例尺分母和需事先确定,曲线分维值D可由原始曲线通过DP算法求出,因此要确定递归深度n,还要先计算移位系数d.3.4参数d的计算移位系数d表示插值点的移位幅度,为计算和推导方便,移位系数d取固定值.由于插值主要就是插入一些细节部分的信息,要求不能改变曲线的形状特征,也就是插值过程中不产生新的曲线特征点.所以要求插值点到原来两端点的距离小于端点间距,即lj.一l>(8)将式(2)代人式(8)得f一l>吉f,一l1+4d(9)又由于dj.=d,由式(9)可解得d<(10)移位系数d是以经验方法确定,它反映原曲线所有点的移位情况,因此与原曲线的特征有关.我们选用原始曲线的平均移位幅度r.和平均线段长度的比值来作为随机中点垂直移位法的移位系数,即d=Ia多次试验表明,一般这样求得的d满足式(10)的要求.3.5无标度区一个理想的分形体应在所有的尺度上均满足自相似性,即分形维数与尺度无关,.但对于自然事物的图像,理论分析和计算机仿真均表明,图像只在一定范围的尺度上满足自相似,也就是说分形维值只在一定的范围内才具有稳定性.因此研究自然分形体要在某一个范围内进行,那就是无标度区,它反映了分形曲线满足自相似性的尺度范围,也是我们能够进行分形分析的研究区间,.因此分形插值也只有在无标度区内进行才有意义.本研究中的无标度区是一个关于移位量r的范围,可以由原始曲线根据DP算法求得其范围为rmin,rmax.4j,移位量在该范围内取值时才满足分维稳定性.所以插值点的移位量r应该在此区间内,即移位量r小于无标度区的上限,且大于无标度区的下限,即满足rminrrmax,对于插值运算来说,一般都满足rrmax,所以关键是要求满足rrmin又因为r=dl所以,(1111)丁L上式表示,当待插的两点间的距离小于该下限值,就不再在这两点间插点.因此,插值点的多少不仅与递归深度n有关,还与待插两点间距离有关.由式(7)和式(11)可知,插值点的多少与曲线的分维值,放大比例和相邻两点间的距离有关,分维值越大,说明曲线越复杂,插值点就越多;放大倍数越大,插值点越多;距离越大,插值点越多.3.6算法流程通过上述的分析,从Beckett公式出发,运用DP算法和随机中点移位法,推导了递归深度n,同时应用DP算法求出的无标度区间,来限制最小的移位量.由此建立了插值点数量与曲线复杂程度,比例尺放大倍数和两点间距离之间的相关关系,并保持了分形曲线的特征点和特征形状.利用本方法进行地理线要素分形插值的算法流程如下:1.输入原始的数字化地理曲线,为L(P)点列,插值前后的比例尺分母为l和M2;2.根据DP算法求出曲线的无标度区间rmin,rmax和分形分维值D;3.求出曲线的平均移位量r.和线段的平均长度.,并确定系数d=Ia/L.;4.根据式(7)求出递归深度n;5.对原始曲线的每个线段按改进的随机中点移位法进行插值,当前移位量小于或等于rmin时停止本线段的插值,否则直到递归深度达到n;6.插完一个线段,进入下一线段的插值,直到遍历整条曲线;7.输出新曲线.第3期张华国等:一种新的地理线要素分形插值方法2594比较与验证4.1方法比较为说明本方法的特点,与传统的IFS分形插值方法作一比较.常用的IFS分形插值方法假设有一组数据(,F):n=0,1,2,(N是大于1的正整数),且满足0<1<2<<则pk:k=1,2,是数据的相伴概率,R:W:k=1,2,就是相伴这组数据的IFS,表示为()=(兰)()+(),=,2,(12)其中,pk是第k个区间中插值点所占的概率;W是在第k个区间的仿射变换;n,c,是第k个区间的变化系数,由给定的数据确定;d是第k个区间的垂直比例因子,满足IdI<1,为自由参量.IFS分形插值就是由任意初始点开始,按式(12)在相伴概率的约束下,随机地在各个区问中迭代产生一系列插值点,最后把所有点按顺序连起来获得插值曲线.从上述原理可以看出,这种方法与本文研究的插值方法相比存在一些缺陷,它很难直接应用于实际的地图线要素插值运算中.首先,IFS分形插值方法对原始数据有<1<2<<的要求,这在实际的地图线要素中是很难满足的.而本文的方法对此没有限制.这一限制的结果,使得生成的曲线只在垂直方向上有复杂的变化,而在方向上必定是单调的,因此不能反映地理空问线要素变化的各向同性.为此我们用5个已知点1,2,3,4,5,其中点3和点4的取相同值,分别用IFS分形插值方法和本文的方法进行插值比较,结果如图4所示.从图4中可看到两种方法在反映曲线变化方向性上的差异.特别是在点3和点4问,由于两点的值相同,用IFS插值方法得到的曲线在这两点问是线性的(图4(a),而忽略了曲线在方向上可能存在的变化,这是不符合实际地理空问线要素变化情况的.而本文的方法则较好地解决了这一问题,反映了曲线变化的各向同性的特性,如图4(b)所示.图4IFS分形插值与本文方法的比较Fig.4ComparisonbetweenIFSmethodandthemethodsuggestedinthepaper其次,IFS分形插值方法中的自由参量d反映曲线的起伏,控制了曲线的复杂程度.研究表明它是生成曲线分维D的决定性因素,但还没有建立起可靠的关系,通常还是靠经验确定.而本文研究的方法中反映曲线复杂性的递归深度n与分维D有确定,合理的关系.最后,直接用IFS方法进行分形插值,其插值点的数量也是人为给定,然后随机地在各个区间内插值,不能定量反映比例尺的变化情况.而本文中递归深度n与比例尺变化之间建立了明确的数量关系.4.2实例分析为了说明本研究方法在实际地理研究中的应用,对我国南麂列岛海洋自然保护区内的南麂岛海岸线和南麂岛的一段等高线进行了分形插值试验.原始数据为1:200000的南麂岛数字化海岸线和1:10000的数字化等高线.现基于上述方法进行分形插值处理,分别扩充为1:50000和1:5000.插值过程与结果如图5和图6所示(未经光滑处理),相关参数在表1中列出.从图5和图6中可看出,经过插值处理后,曲线的特征点和特征形状没有变化,但细节部分得到细化,而且是符合地理曲线插值的特点和要求的.在表1中,分维值和无标度区问是由原始输人曲线按DP算法求得的,分别反映了待插值曲线的分形特征和分形分析的尺度范围.下面从插260测绘第31卷值点数和曲线长度的变化两个方面分析插值试验的效果.图5插值前(a)和插值后(b)的南麂岛海岸线Fig.5Originalcurve(a)andthecurveafterthefractalinterpolation(b)oftheNanjiislandshoreline图6插值前(a)和插值后(b)的等高线Fig.6Originalcurve(a)andthecurveafterthefractalinterpolation(b)ofthecontourlineofNanjiisland表1分形插值的有关参数Tab.1Parametersandresultsofthefmcmlinterpolation1.0380.101350000l1452703.021.0350.06235000992l568.93根据式(7),递归深度n与比例尺变化倍数,分维值D和移位系数有关,比例尺变化倍数和分维值越大,n值越大,移位系数越大,则n值越小.南麂岛海岸线和等高线的分维值比较接近,但前者的比例尺变化幅度与移位系数都比后者的大,使得n(经过四舍五入处理)值相同,都为3.根据随机中点垂直移位法的原理,在相同的递归深度n=3的情况下,如果不考虑无标度区,坐标点间距和移位系数的影响,插值后坐标点数都应是插值前的8(2)倍.但本文的方法根据分形曲线的要求,考虑了这些因素的限制,认为无标度区的下限是插值的终止条件.同时,坐标点间和移位系数的大小直接决定着移位量收敛于无标度区下限的快慢.因此考虑了无标度区的限制及坐标点间距和移位系数的影响后,插值点的数量必将大大减少.表1中显示南麂岛海岸线和等高线在插值后的坐标点数分别是插值前的4.91和1.98倍,都小于8,符合本文方法的特点.根据2.5节的讨论,无标度区下限越大插值点越少,坐标点间距越小插值点越少,根据移位系数的定义,移位系数大,移位量收敛速度慢,插值点就多,反之亦然.由表1可知,海岸线的无标度区下限和移位系数都比等高线要大一些.但等高线的初始比例尺是海岸线的2O倍,而放大倍数又小,使得等高线的平均坐标点间距(曲线长度与坐标点数的比)远小于海岸线,成了影响插值点数的主要因素,因此使得等高线的坐标点数增大倍数比海岸线小得多.因此插值点的多少是初始比例尺及比例尺变化倍数,曲线分维值,移位系数和无标度区等许多因素共同作用的结果.由表1可见,南麂岛海岸线和等高线的初始长度分别为2578.09In和1532.14In.根据Beckett公式,经插值后,南麂岛海岸线和等高线的理论长度应分别为2717.54In和1571.94m,本文的插值结果(LM)与Beckett公式的理论长度比较,相对误差分别为0.5%和0.2%,很好地反映了地理曲线长度变化.5讨论与结论分形插值方法的实际应用研究还处在起步阶段,理论方法还不够成熟.结合具体应用领域的特点提出新方法,是分形应用的重要方向之一.本文在分形理论的基础上,针对地理线要素插值的特殊要求提出了一种新的分形插值方法.该方法的特点是插值点的数量与比例尺放大倍数和分形维数密切相关,同时插值反映了地图曲线变化的各向同性特征,因此很好地解决了IFS分形插值方法存在的一些问题和缺陷.实际地理线要素的插值试验表明,本文的分形插值方法计算简单,插值精度高,在地图制图自动化,多尺度数据分析和空间数据无级比例尺管理等方面有广泛的应用前景.在今后的研究中,将结合实际应用,在移位系数d的选取,插值质量的评价和相应属性数据扩充调整等方面作进一步的研究,使本文提出的分形插值方法更加完善.参考文献:1wuHe-hai.ResearchonFundamentalTheoryand第3期张华国等:一种新的地理线要素分形插值方法261234TechnicalApproachesofAutomatedMapGeneralizationJ.JournalofWuhanTechnicalUniversityofSurveyingandMapping,2000,25(5):377386.(inChinese)PENTLAND.FractalBasedDescriptionofNaturalSciencesJ.IEEETransonPAMI.1984,6(6):661673.JINYiwen,LUShijie.FractalGeometryTheoryandApplicationM.Hangzhou