分形在空间数据压缩中的应用研究

中文题目：分形在空间数据压缩中的应用研究AbstractInrecentyears,therapiddevelopmentofcomputertechnology,multimediainformationsurroundspeople'slives,butthehugeamountofdatainthedisseminationandstorageismoredifficult,butalsohinderthefurtherdevelopmentofnetworkinformationtechnology,theproblemistroublingpeople.Inorderforcomputerstoprocess,store,anddisseminateinformationmoreefficiently,compressingdatabecomesverynecessary.Fractaltheoryisanimportantbranchofnonlinearscienceandanimportanttoolinscientificresearch.Itisappliedtovariousdisciplineswithitsuniqueself-similaritycharacteristics,includingitsapplicationinimagecompression.Thispaperintroducesthethreestagesoffractaltheorydevelopment,expoundsthetheoreticalbasisoffractalimagecompression,givestwosimplifiedcompressionmethods,respectively,POINT_REMOVEandBEND_SIMPLIFY,andusestwomethodstosimplifycompressionofindividualgraphicsandcompositegraphics,andthenstatisticsusetwomethodstosimplifythechangespreeofthecompressedgraphics.Next,thecomplexcurvessurroundingthesegraphsarecalculatedbyprofessionalfractalcalculationsoftware,andtheunsimplifiedgraphicsandthetwosimplifiedgraphsareoperatedseparately.Thecloserthearea,perimeter,andboxdimensionsofthepost-graphicsmallerintwoways,thebetterthesimplifiedcompressionmethod.Finally,thebroadapplicationprospectoffractaltheoryisforecasted.Keywords:fractaltheory;；imagecompression;；boxdimension目录专用术语注释表 IV1绪论 11.1选题背景与意义 11.2分形的发展历程 11.3分形的定义 31.4典型分形图像 31.4.1Koch曲线 31.4.2均匀康托集（Cantorset） 41.4.3维尔斯特拉斯（Weierstress）函数 52分形的相关理论 72.1分形的基本概念 72.1.1测度和维数 72.1.2Hausdorff测度和Hausdorff维数 72.1.3自相似维数 82.1.4计盒维数 92.2分形图像压缩理论基础 92.2.1度量空间 92.2.2压缩映射定理 102.2.3迭代函数系统（IteratedFounctionSystem，IFS） 112.2.4拼贴定理（CollageTheorem） 113两种数据压缩方法 133.1数据压缩原理 133.2两种简化算法 133.2.1POINT_REMOVE 133.2.2BEND_SIMPLIFY 133.3两种方法中的注意事项 143.4用POINT_REMOVE简化图形 153.4.1单个图形的简化 153.4.2复合图形的简化 163.5用BEND_SIMPLIFY简化图形 173.5.1单个图形的简化 173.5.2复合图形的简化压缩 184两种简化压缩方法的比较 214.1简化后图形的面积周长。 214.2简化后图形的盒维数 245总结与展望 35参考文献 37致谢 39专用术语注释表符号说明：lim求极限sup上确界inf下确界i=1mA缩略词说明：IFSIteratedFounctionSystem迭代函数系统山西大同大学建筑与测绘工程学院2020届本科生毕业设计1绪论1.1选题背景与意义随着网络技术的发展，多媒体信息包围了人们的生活，正满足了人们对信息的需求，但是计算机在对数据进行各种处理时，对数据本身也有着一定的要求，如果数据量太大的话，不管是在处理、存储还是传输上都会增加操作的难度。所以，为了提高存储处理和传输数据的效率，就要对数据进行压缩。图像压缩之所以能够进行，是因为原始图像的各像素间高度相关的，也就是说它们之间存在很多的冗余信息，也正是这些冗余信息为图像压缩提供了依据，而各种图像压缩也是围绕如何减少图像存在的冗余信息进行的，从压缩图像的各个步骤进行研究，实现对图像进行压缩的目的，从而可以有效减轻图像处理、存储和传输的负担，实现图像信息的快速传输[1]。最近几年，随着非线性理论的不断发展和完善，非线性科学开始逐渐应用到各个各个领域中，其中也包括以非线性理论为指导的图像信息表示，解决了线性方法长期以来无法攻克的难点，也是该领域的主要发力点之一。分形理论是非线性科学中自成一家的新兴学科，是近20年来迅速发展起来的新学科。随着分形理论日趋成熟，其在图像压缩方面的应用也受到了极大关注。与传统的图像压缩方法相比，基于图像自身特征的分形压缩具有明显的优势和广阔的前景。它的发展创立为图像信息的表达提供了一种新思路、新方法。1.2分形的发展历程分形理论的发展创立基本上可以分为三个阶段［2-4］。第一阶段大致为1875年至1925年，这一阶段学者们已经开始认识到一些典型的分形集，经过大量的研究他们发现这些图形与经典几何图形之间存在一定的差异，并且致力于将它们之间的差异进行描述和分类。1872年，Weieratrass发现了一种特殊函数，该函数在任意一点均不具有有限或无限导数，将其命名为Weieratrass函数；1883年，德国数学家Cantor证明了Cantor三分集——一类全不连通的紧集；1890年，意大利数学家Peano构造出填充平面的曲线[5]，该曲线能够通过一个正方形的所有点，称为Peano曲线；1904年，瑞典数学家Koch构造出了处处不可微的类似于海岸边缘和雪花的曲线，称其为Koch曲线，并研究其性质；1910年，德国数学家豪斯道夫提出分数维概念，开始对一些奇特的集合进行研究；1913年，Perrin深入研究了布朗运动的轨迹图，并提出布朗运动作为运动曲线不具有导数的结论，在他的研究基础上，1920年Wiener建立了很多布朗运动的概率模型。由于以上介绍的集合都非常复杂，所以传统的长度、面积已经难以描述其特征长度。为了更加准确的描述这些集合，1901年，Minkowski提出了闵可夫斯基容度；1919年Hausdorff提出了豪斯道夫测度和豪斯道夫维数。这些研究，为分形几何奠定了基础。综上所述，在分形理论的萌芽时期，学者们已经认识到典型的分形对象，并且做了一些相关的基本工作。第二阶段大致为1926年到1975年，学者们在分形集的性质和维数理论上的研究取得了巨大的进展。他们研究了曲线的维数、分形集的性质及其结构以及S-集的分析与几何性质等。1928年，Bouligand提出了Bouligand维数，并将闵可夫斯基容度应用到非整数维，这样做可将螺旋线更好的分类；1932年，Pontrjagin与Schnirelman提出了覆盖维数，也称为盒维数；1959年，Kolmogorov与V.Tikhomirov提出体维数。维数对于从不同角度刻画集合的复杂性起到了至关重要的作用。尽管该阶段关于分形研究的进展巨大，但仍然具有局限性，此处的局限性主要是指纯数学理论的研究难以回答分形研究的疑问，从而使得分形理论没有与其他学科发生联系。再者就是，物理、生物和地质等众多学科出现了大量与分形几何相关的问题，迫切需要新的理论来指导。伴随着多个学科诸如此类问题的出现及研究，美籍法国数学家曼德尔布罗特自20世纪60年代以来，深入的研究了海岸线的结构、银河系中星体的分布、月球的表面等自然界的各种分形现象，并取得了重要的成果。第三阶段为1975年至今，分形理论逐渐应用于各个领域并越来越广泛，逐步形成一个独立的学科。1977年，曼德尔布罗特发表了(分形：形，机遇与维数)(Fractal：Form，ChanceandDimension)[6]，把分形理论推进到一个新阶段。1982年，他的另一部著作《自然界的分形几何学》(TheFractalGeometryofNature)[7]出版了，这两部著作的发表标志着一个新的独立的学科正式诞生，即分形几何，至此分形理论初步形成，从此进入一个深入开拓应用的发展阶段。1.3分形的定义分形(Fracta1)一词，是1973年曼德布罗特(B．B．Mandelbrot)[8]根据拉丁语Frangere一词创造出来的，其原意具有不规则、支离破碎等含义，分形不管是在理论上还是在各个领域的应用上，都已经有了一定的发展，但分形到现在为止还没有一个确切的定义。曼德布罗特曾经提出，以分形维数作为定义的标准，将分形定义为豪斯道夫(Hausdorf)维数严格大于其拓扑维数的集合。但是这个定义不具有唯一性，Peano曲线属于分形图形但不符合这个定义，经过研究他又提出分形是具有自相似性性质的集合，但是这个说法也不全面，直线不属于分形却也满足这个定义。后来，随着分形理论的一步步发展，学者们认为，分形具有分形维数，但维数仅仅只能说明几何对象在数量上的复杂性，他们不但不能唯一的刻画一个分形集，而且也不能具体描述怎样去构造一个分形集。慢慢的人们想到总结的方法，就是采用罗列分形集所具有的一系列性质的方法来定义分形，其中使用最广泛的就是英国数学家Falconer总结分形的一些特征，1990年他在《FractalGeometry-MathematicalFoundationsandApplication》一书中提出了如下分形的一种定义［9］。称集合F是分形，如果它具有如下的一些特征：1.F具有精细的结构，即在任意小的尺度下，它总具有复杂的细节。2.F是如此的不规则，以至于它的整体与局部都不能用传统的几何语言来描述。3.F通常具有某种自相似性，可能是近似的或统计的。4.一般地说，F的分形维数大于它的拓扑维数。5.在大多数令人感兴趣的情况下，F以非常简单的方法定义，如由迭代产生。1.4典型分形图像1.4.1Koch曲线1949年由瑞典数学家科赫(H．Von．Koch)首次提出，它属于典型的规则分形。生成它的方法是把一条直线三等分，把中间那一条直线从其中点处呈60度角折起，得到第一个生成元，具有5个节点，然后用生成元替换掉第一个生成元的每条直线段，这样就获得第二个生成元，具有17个节点。按照这个规律一直迭代下去，可以得到一条Koch曲线，下面的图形就是生成Koch曲线的三次迭代过程，按照这样的方法迭代下去，我们就可以得到一条曲折的海岸线。值得注意的是，Koch曲线被认为是第一个构造的具有自相似，也就是整体与局部相似的曲线。N=0N=1N=2N=5图1-1Koch曲线的迭代1.4.2均匀康托集（Cantorset）康托集也是一个典型的规则分形的例子，它的生成方法是：把一条单位长的直线段平均分成三份，将中间的一份去掉，留剩下的两段，得到第一个生成元，然后对第一个生成元的两条直线段平均分成三份，各去除其中间1/3长度的线段，剩下更短的四段，得到第二个生成元，按照此规律迭代下去，就得到康托集[02]。下面的图形就是了构造康托集的三次迭代过程。N=0N=1N=2N=3图1-2Cantor集的迭代1.4.3维尔斯特拉斯（Weierstress）函数以上两种都是典型的规则分形，生活中以及自然界中还存在着大量的不规则分形，如海岸线[10]，山脉，云朵，波浪，心电图，雪花等等。各种各样的不规则或病态的集合和图形被构造出来，数学家们对其作出研究，而且试图描述、分类和区分这类集合与经典集合之间的差别。19世纪60年代，人们逐步认识到了存在连续但不可微曲线，而且认为这种现象是极少见的。在1827年，维尔斯特拉斯(Weierstress)证明了一种连续函数，是一类处处连续而处处不可导的实值函数，称为Weierstress函数[01]（如下图）。这一结论曾引起极大的震动，推翻了常规的认知，此函数被构造出来之前，学者们认为连续函数在每一点处都可导，少数特殊点除外。数学家们对连续函数的看法因此改变了，具有非常重要的意义。虽然人们认为Weierstress函数是“病态”的函数，但仍从不同方面推广它，并对它特殊的性质作了深入研究。在实际分析中，凡具有和Weierstress函数的原始定义相似的构造与性质的函数，都可称为Weierstress函数。图1-3Werestress函数2分形的相关理论2.1分形的基本概念2.1.1测度和维数维数是几何图形的一个特征量，一般来说，维数表明一个集合占据空间的大小。我们都知道，点是零维的，直线是一维的，平面是二维的，立体是三维的，如果用单位面积的正方形来测直线段的长度，那么测出的结果为零，说明所采用的尺度太大，同理，如果采用单位长度的线段来测量圆面积，那么测量结果为无穷大，说明所用的尺度太小[11]。这就意味着，在测量几何图形时，测量所采用的尺度影响着测量的结果。对分形图形维数进行测量时，如果用一维的尺度来测，得到的结果为无穷大，如果用二维的尺度来测，得到的结果为零，这样看来，只能用介于一维和二维之间的分数维来测量它，才能准确刻画分形的性质。2.1.2Hausdorff测度和Hausdorff维数在在各种各样的“分形维数”中，最先被提出来的维数就是由Hausdorff定义的Hausdorff维数。Hausdorff维数优点是具有对任何集合都有定义，缺点是计算比较困难，即使是典型的图形也不容易，所以在实际应用中不太常用，但它在理论上非常重要[12]。它的定义基于相对容易处理的测度的基础上，Hausdorff测度[13]和Hausdorff维数[13]都是分形几何中的理论基础。设U是n维欧式空间Rn中的任何非空子集，U的直径定义为|U|=sup{|x−y|:x,y∈U}即U内任何两点的最大值，对于集F∈Rn，如果F可被有限个直径不超过δ的集构成的集类{Ui}所覆盖，即：F⊂则称{Ui}为F的一个δ-覆盖。Hausdorff测度[1]定义：设F是Rn中的任何一个子集，s为一非负实数，对任何ε>0，有：HδS=inf{i=1∞U对于给定的F和s，Hsε(F)是ε的一个减函数，关于ε取极限，有H称Hs(F)为F的s维Hausdorff测度。Hausdorff维数[1]定义：对于给定的集合F，把F的Hausdorff测度Hs(F)作为s的一个函数，通过数学分析可知，F的Hausdorff维数DH是使得Hs(F)从跳跃到0的一个临界点，集F的Hausdorff维数为：D则有：，当s<DH时;HS(F)=c，当s=DH时;0，当s>DH时.显而易见，DH取值范围是非负实数，但是既可能是整数，也可能是分数，所以是一种分数维。2.1.3自相似维数自相似包含两种，一种是部分和整体严格的相似，另一种指的是统计上的相似[14]，比如海岸线。通俗的说，图像中局部或整体在不同尺度下含有很多相似的地方，可以用一个局部图像通过一些基本操作如旋转、缩放、平移等从而来表示多个相似的部分。自相似是分形的重要特征。相似维数是从分形的自相似对称性出发而定义的一种分形维数。一般来讲，给定一个自相似结构，缩减因子s与该结构可划分的子块数目a之间存在如下关系：Ds=DS就是自相似维数[15]。2.1.4计盒维数接下要说的计盒维数[16,17]和上面所介绍到的自相似维数这两种典型的分形维数都是由Mandelbrot所提出来的。计盒维数又称为盒维数，具有很多优点，首先其在数学计算中较为简便，其次容易在记算机中实现，能够通过实验近似的计算，再者就是它既适用于自相似的形状，又适用于非自相似的形状，所以是实际应用最广泛的。事实上，规则图形的盒维数和Hausdorff维数是相同的。许多情况下，一个分形集的盒维数是等于它的Hausdorff维数的。盒维数实际上是Hausdorff维数的推广，它的计算方法称为盒子计数法（Box-countingmethod）。定义：设A为Rn的一个紧子集，用尺度为ε的n维盒子来覆盖A，记Nε(A)是覆盖A的最少盒子数，集合A的Box维数DB(A)定义为D当ε充分小时，DB(A)可以近似的看成集合A的盒维数。分形维数可以反映出分形图形的复杂程度和基本特征，它是衡量分形图形非常重要的指标。从不同的方面进行研究和判定，可以得到多种定义，除了上述所介绍的几种常见分形维数外，还有容量维数，质量维数，拓扑维数，谱维数，模糊维数等。其他维数的定义见[18-20]。2.2分形图像压缩理论基础分形图像压缩的理论基础包括压缩映射定理，迭代函数系统，和拼贴定理等。2.2.1度量空间德国数学家G.康托尔经过大量的分析研究在19世纪末创立了集合论，集合论的提出为后来建立各种抽象空间奠定了一定的基础，具有重要的意义。法国数学家M.R.弗雷歇以更抽象的观点来看许多涉及到函数间距离关系的分析成果并在20世纪初提出度量空间[21]的概念。定义2.1：设X为一个集合，一个映射d:X×X→R。若对于任何x,y,z属于X，有 （正定性）d(x,y)≥0，且当且仅当x=y时，d(x,y)=0。⑵ （对称性）d(x,y)=d(y,x)。⑶ （三角不等式）d(x,z)≤d(x,y)+d(y,z)。则称d为集合X的一个度量（或距离）。称偶对（X，d）为一个度量空间，或者称X为一个对于度量d而言的度量空间。定义2.2：如果度量空间中（X，d）的一个点序列xnn=1∞收敛于x∈X，则x定义2.3：如果X中每个Cauchy序列都有极限x∈X，则度量空间(X，d)称为完备度量空间。记B(x,ε)={y∈X:dx,y<ε表示中心在x，半径为ε>0的开球，对于收敛序列来说，当n大于某个N后，该球将包含所有的点{x2.2.2压缩映射定理定义2.2：变换W：R2→RWxy=abcd其中a，b，c，d，e，f，g为实数，则称为一个二维仿射变换。数学式中含有具体几何意义的仿射变换有四种，他们分别为：缩放变换As，As伸长变换At，At=1剪切变换Au，Au旋转变换Aθ，Aθ定义2.3：度量空间（X，d）上的映射ℎ:X→X称为压缩映射，如果存在实数k∈[0,1]，使得d(ℎ(x),ℎ(y))≤kd(x,y)，定义2.4：度量空间（X，d）上的映射ℎ:X→X，如果有xℎ∈X，使得ℎ(x)=x定理（压缩映射定理[22]或Banach不动点定理（Banach’sFixedPointTheorem））：设（X，d）是完备度量空间，g：H(X)→H(X)是压缩因子为k∈[0,1]的压缩映射，则压缩变换g存在唯一的不动点x0，且x0=2.2.3迭代函数系统（IteratedFounctionSystem，IFS）巴恩斯利（M.FBarnsley）系统研究[23-26]并且在1985年正式提出迭代函数系统理论[27]，迭代函数系统是以仿射变换为基础，根据几何对象的整体与局部具有自相似的性质，将一定比例的整体形状按不同的仿射变换迭代下去，直至得到满意的分形图形为止。迭代是一种常用的构造方法，在很多图形构造和算法设计中都会用到它。随着计算机技术的发展，计算机已经拥有了强大的迭代功能，因此也推动了计算机图形的发展，如今，可以在计算机系统的支持下，以分形理论的特性，即自相似性为基础构造大量具有无穷细节的图形。定义（迭代函数系统）：设一个完备度量空间（X，d），gi：X→X为度量空间中（X，d）的一组压缩映射，其压缩因子分别为k1，k2，k3，…，kn，则称为迭代函数系统（IFS），记作{X；g1，g2，…，gn；k}，k=max{k1，k2，…，kn}称为IFS的压缩因子。2.2.4拼贴定理（CollageTheorem）拼贴定理[28,29]是M.F.Barsley在1988年提出来的，它回答了这样一个问题，对于一个给定的分形，如何求得以它为吸引子的IFS[04]。定理：设一个完备度量空间（X，d），集合L∈H(X)。如果存在一个IFS：{X；h1，h2，…，hn；k(0≤k≤1）}，使得h(L，ℎ(L,i=1ngiℎ(L,其中，x0为IFS的不动点，h是hausdorff拼贴定理所表达的物理意义可以表述为：给定一幅图像，如果试图寻找一个吸引子与给定的图像相似或相近的IFS，那么必须在给定的空间中找一组压缩仿射变换系数，使得对各个压缩映射变换后的结果能够拼成一副图像，并且使该图像在hausdorff距离下尽量接近原给定图像，这样就可以用一组仿射变换系数作为给定图像的编码。拼贴定理可以理解为集合合并的过程，而IFS吸引子与原给定集合之间的误差由拼贴的过程定量给出[30]。3两种数据压缩方法3.1数据压缩原理3.2两种简化算法3.2.1POINT_REMOVEPOINT_REMOVE可以移除多余的折点，这种方法多用于数据压缩或较粗糙的简化，尤其是用于确定的数据，容差逐渐增大，生成的面中有棱角的部分（尖锐拐角）随着其增加，因此，经过简化后的图形在视觉上美观度下降。POINT_REMOVE方法保留图形的基本几何形状的关键点并移除所有其他点。算法基本思想该算法是基于道格拉斯-普克（Dauglas-Peucker）算法，该方法原理是以较小的比例显示经过识别并删除相对多余的折点从而简化的数据。它将保留构成线要素的基本形状的所有关键点而移除非关键点。该算法首先将线要素的端点与趋势线连接起来，然后测量每个端点到趋势线的垂直距离，与趋势线的距离小于容差的端点将被删除。线要素首先在距趋势线最远的端点处断开，从而形成两条新的趋势线。然后测量其余端点与两条线之间的垂直距离。整个过程将继续进行，直到与趋势线之间的距离小于容差的所有端点都被删除为止。这种算法对于数据压缩和消除冗余细节非常有效，但是生成的线条可能包含不必要的尖角和锯齿，从而降低线条绘制的质量，用来实现相对较少的数据压缩或缩减。3.2.2BEND_SIMPLIFYBEND_SIMPLIFY相较于POINT_REMOVE来说较慢，但通常会生成与原始几何形状更为接近的图像，因此相较于POINT_REMOVE的图像更加美观，它的原理是消除图像边界上不太重要的弯曲。此方法常用于少量的，更为精细的简化。BEND_SIMPLIFY保留图形的主要几何形状并移除边界中多余的弯曲。算法基本思想该算法使用形状识别技术来查找折弯并分析其特征，并且消除不重要且非特征性的折弯。可以将线状要素看作由一系列折弯组成，其中每个折弯在其连续折点处具有相同的拐角符号。可以将每个折弯的几何属性与直径等于指定简化容差的参考半圆的相应属性进行比较，这些测量值用于确定是保留还是消除折弯，如果要是消除，则将折弯替换为基线。这种简化是反复进行的，也就是迭代进行的，因此，在较早的迭代过程中可以消除较小的弯曲，从而导致较大的折弯。这种算法生成的线条十分接近原始线条的大致形状，并且制图的质量较高。但需要更多的处理时间，因为速度较慢。3-1两种方法的处理的图像3.3两种方法中的注意事项一、最小面积参数仅适用于简化的面，在简化过程完成之后，任何小于最小面积的面都将从输出面中移除，且该参数适用于共享公共边的一组相邻面的总面积。二、多部分（Multipart）可简化为单部分。三、在处理拓扑错误时，有三条种途径，可能是在处理时引入的这些拓扑错误，其中包括相交的线、重叠的线和折叠为零长度的线。：⑴NO_CHECK:对简化过程所引入的拓扑错误不做检查，这样会加快其处理过程，一般只有在保证数据的拓扑性是正确的时候才会选用此选项。⑵FLAG_ERRORS:检查并标记在简化过程中所引入的拓扑错误。当标识拓扑错误的重要性大于解决错误的重要性时，使用此选项。⑶RESOLVE_ERRORS:修复简化过程中所引入的拓扑错误，处理时间将会更长。⑷在使用了NO_CHECK和FLAG_ERRORS时，它们会自动修复在简化过程中可能创建自相交的几何形状。3.4用POINT_REMOVE简化图形3.4.1单个图形的简化图3-22号地块现将图3-2用POINT_REMOVE进行简化，由于图形单一，拓扑方式既可以是NO_CHECK也可以是RESOLVE_ERRORS。图3-3是简化后的图形与未简化图形的对比，可以看到对图形边界起伏较大的折线进行了取舍，相较于原始图像细碎弯折线减少，但简化后的图形线条很尖锐，不够圆滑。图3-3用POINT_REMOVE简化后的2号地块与未简化2号地块的对比3.4.2复合图形的简化图3-4乡镇图图3-4是某个乡镇辖区图，现在用POINT_REMOVE对该乡镇辖区图进行简化处理，此次处理中，先不处理拓扑问题，选择NO_CHECK。简化后的图形均保留了简化前每个多边形的所有属性。图3-5是简化后的多边形与未简化多边形的对比，将图3-5放大得到图3-6，可以看出，多边形边界得到简化，但是两个相邻多边形的边界不完全重合，内部有空隙或交叉，有些线的走向比较尖锐、生硬。图3-5用POINT_REMOVE简化后的乡镇图与未简化乡镇图的对比（含拓扑错误）图3-6放大后的图4-4现在，再次进行简化处理，此次主要解决拓扑错误，所以采用RESOLVE_ERRORS。图3-7是处理完拓扑错误的图像。可以看到，内部多边形的边界变得重合了，但图形边界折线仍较尖锐。图3-7用POINT_REMOVE简化后的乡镇图与未简化乡镇图的对比(不含拓扑错误)3.5用BEND_SIMPLIFY简化图形3.5.1单个图形的简化现将图3-4用BEND_SIMPLIFY进行简化，拓扑方式既可以是NO_CHECK也可以是RESOLVE_ERRORS，图3-8是用BEND_SIMPLIFY简化后的图形与未简化图形的对比，图3-9是用BEND_SIMPLIFY简化后的图形与用POINT_REMOVE简化后的图形的对比。图3-8用BEND_SIMPLIFY简化后的2号地块与未简化2号地块的对比图3-9用BEND_SIMPLIFY简化后的2号地块与用POINT_REMOVE简化后的2号地块的对比3.5.2复合图形的简化压缩将图3-4用BEND_SIMPLIFY进行处理，拓扑处理中的NO_CHECK与上一种方法类似，就不再进行列举了，此处选用RESOLVE_ERRORS进行拓扑处理来验证。图3-10是用BEND_SIMPLIFY简化后的乡镇图与未简化乡镇图（图3-4）的对比，图3-11是用BEND_SIMPLIFY简化后的乡镇图与用POINT_REMOVE简化后乡镇图的对比。图3-10用BEND_SIMPLIFY简化后的乡镇图与未简化乡镇图的对比图3-11用BEND_SIMPLIFY简化后的乡镇图与用POINT_REMOVE简化后乡镇图的对比这两种方法中，POINT_REMOVE按偏移量尽可能缩减折线的点数，在简化中，会忽略脚非常细小的弯曲，从而达到更简洁的结果和更小的数据量，如果要求精细一点的简化结果，POINT_REMOVE就不适用了。BEND_SIMPLIFY主要将过分弯曲的部分去除，在简化的过程中尽量多的保留线元素的原有走向和原有特征，可以较好的对线元素进行简化。从制图效果上来看，POINT_REMOVE产生的线形某些部位比较平直，另一些部位比较尖锐；BEND_SIMPLIFY产生的线形走向相对蜿蜒、平缓，其简化效果更符合原线的走向。在简化容差较大时，数据不太复杂时，两者差距并不明显，随着简化容差的减小，两者差距逐渐增大。简化容差相同的情况下，BEND_SIMPLIFY算法较POINT_REMOVE算法更为精细，更加拟合于原始图像。4两种简化压缩方法的比较4.1简化后图形的面积周长。因为单个面的图形是乡镇图形中的一部分，是编号为2的图形，因此单个图形经两种方法简化压缩后，面积、周长变化的数据就含于复合图形面积周长变化的数据中了。在此用复合图形面积周长数据进行说明。表4-1用POINT_REMOVE简化后各个地块周长面积变化表表4-2用BEND_SIMPLIFY简化后各个地块周长面积变化表abcdef图4-1对未简化和用两种方法简化后乡镇图总面积总周长的统计表4.3对未简化和用两种方法简化后乡镇图总面积总周长的统计表简化前面积总和（Town_Area）（㎡）801706863.7POINT_REMOVE简化后面积总和（㎡）801517497.3BEND_SIMPLIFY简化后面积总和（㎡）802033649.3简化前周长总和（Town_Perim）（ｍ）722443.1POINT_REMOVE简化后周长总和（ｍ）618494.9BEND_SIMPLIFY简化后周长总和（ｍ）613487.8图4-2用两种方法简化与未简化图形的面积对比图4-3用两种方法简化与未简化图形的周长对比表4-1、表4-2是乡镇辖区分别用POINT_REMOVE和BEND_SIMPLIFY简化后各个地块面积周长的变化，其中，Town_Area、Town_Perim分别指未简化图形的面积和周长，Area、Perim分别是用POINT_REMOVE简化后图形的面积和周长；AREA、PERIMETER分别是用BEND_REMOVE简化后图形的面积和周长。由上可知，在15个地块中，用POINT_REEMOVE简化后图形的面积更接近未简化图形的有5个，周长更接近未简化图形的有10个；用BEND_SIMPLIFY简化后图形的面积更接近未简化图形的有10个，周长更接近与未简化图形的有5个。4.2简化后图形的盒维数计盒维数又被称为Bouligand维数，它是描述集合复杂程度的重要参数，不管在理论上还是在实际应用中都有重要的意义。值得一提的是，它可以通过计算格点数来进行数值计算，相较于其他方法更容易计算，所以在实际中应用广泛。具体定义请参见第二章。计盒维数是一种常用的计算二维图像分形维数的方法，即可以计算曲线又可以计算曲线围成的面，几乎与图像物理意义没关系。具体来讲，就是将图像A用尺度为ε的网格进行覆盖，然后计算出覆盖图像所用的网格个数Nε，根据前面介绍盒维数的公式：DB可求出图形的分形维数DB(A)。所以对于序列εi，可以在双对数坐标系中拟合数据点（-lnεi，lnNεi），其斜率即是A的分形维数的近似值。可以看出，采用计盒维数计算图像的分形维数时，首先需要将图像中的处理区域从图像中提取出来，以数字形式来表现一幅二维图像时，易于对图形进行灰度调整、几何运算、特征检测、频谱分析以及模式识别等处理，这建立在现代信息处理技术和数字图像技术发展的基础上。先将整幅图片或者提取处理区域进行二值化，转化为单色位图，即黑白位图。这一预处理可强化图像所反映的研究对象的信息。经过网格划分与统计，得到一系列“网格大小”与对应的“网格数”的数据对，在双对数坐标系下进行线性回归分析，若能得到一条线性相关的直线，直线斜率就是所求图像的计盒维数DB(A)。下面我们以单个图形举例进行说明。图1图12a图2bcdef图4-4以不同尺度的网格覆盖2号地块图4-5未简化2号地块的计盒维数图4-4所展示的一系列图像就是以不同尺度的网格覆盖2号地块的结果，按照顺序依次是以尺度分别为1、2、4、8、16、32、64、128、256、512、1024、2048的网格覆盖图形的图像，通过上图可以看出，网格的尺度越大，个数越少。表4-4给出不同网格的尺度对应网格的数目。表4-4不同网格的尺度和对应网格的数目表（未简化2号地块）网格尺度网格数目1208272805443503815741676032341641501286725631512161024620482知道网格的尺度和数目，通过上面介绍的计算盒维数的方法就可以计算出该图形的盒维数，图4.13就是该图形的盒维数，显而易见，DB(A)=1.171。以上是未经简化的原图形的计盒维数，接着让我们看一下分别用POINT_REMOVE和BEND_SIMPLIFY图4-6用POINT_REMOVE压缩过2号地块的尺度为32的网格覆盖图像图4-7用POINT_REMOVE压缩过2号地块的计盒维数表4-5不同网格尺度和对应网格数目表（用POINT_REMOVE压缩的2号地块）网格尺度网格数目1179442712443055813921666732311641441286625634512151024620482图4-8用BEND_SIMPLIFY压缩过图形的尺度为32的网格覆盖图像图4-9覆盖用BEND_SIMPLIFY压缩过2号地块的计盒维数表4-6不同网格尺度和对应网格数目表（用BEND_SIMPLIFY压缩的2号地块）网格尺度网格数目1171902685742908813381665332314641461286525633512151024620482通过上述图像，可以知道用POINT_REMOVE方法简化后2号地块的盒维数DB(A)=1.147（如图4-7），用BEND_SIMPLIFY简化后的2号地块的盒维数DB(A)=1.14（如图4-9），未经过简化2号地块的盒维数D表4-7未简化和用两种方法简化后各地块的计盒维数FID未简化地块的计盒维数POINT_REMOVE简化地块计盒维数BEND_SIMPLIFY简化地块计盒维数11.1341.1081.11421.141.1281.12231.1711.1471.1441.1411.1181.12151.1421.1221.12461.1681.1451.14471.1451.1231.12681.1391.1121.10991.1331.1061.105101.1411.1181.115111.1671.1471.147121.1491.1221.121131.141.1261.12141.1221.1041.102151.1311.1061.099整个乡镇图是由15个地块组成，我们分别对其用两种方法处理，然后计算它们的计盒维数，并与未简化地块的计盒维数进行对比，结果如表4-7，其中FID是指地块编号。可以看出，15个地块中，用POINT_REMOVE简化后更接近原图形计盒维数的有10个地块，用BEND_SIMPLIFY简化后更接近原图形计盒维数的有4个地块，还有1个地块，用两种方法处理完计盒维数相同。以上介绍的是单个图形的盒维数，接下来看一下复合图形的盒维数。图4-10未压缩乡镇图的尺度为32的网格覆盖图像图4-11未压缩乡镇图的计盒维数表4-8不同网格尺度和对应网格数目表（未压缩乡镇图）网格尺度网格数目1506452194244820183652161636327506434512814125654512191024620482图4-12用POINT_REMOVE压缩后乡镇图的尺度为32的网格覆盖图像图4-13用POINT_REMOVE压缩后乡镇图的计盒维数表4-9不同尺度的网格和对应网格数目表（用POINT_REMOVE压缩的乡镇图）网格尺度网格数目1436032170554735383357161566327266434412814225654512191024620482图4-14用BEND_SIMPLIFY压缩后乡镇图的尺度为32的网格覆盖图像图4-15用BEND_SIMPLIFY压缩后乡镇图的计盒维数表4-10不同网格尺度和对应网格数目表（用BEND_SIMPLIF压缩的乡镇图）网格尺度网格数目1433272169514731283338161565327266434012814025654512191024620482显而易见，未压缩乡镇图的盒维数DB(A)=1.291（如图4-11），用POINT_REMOVE压缩后乡镇图的计盒维数DB(A)=1.27（如图4-13），用BEND_SIMPLIFY压缩后的乡镇图的盒维数DB(A)=1.269图4-16乡镇图的上半部分和下半部分表4-11乡镇图的上半部分和下半部分的计盒维数乡镇图上半部分乡镇图下半部分未经压缩图形的盒维数1.2371.26经POINT_REMOVE压缩1.2181.238经BEND_SIMPLIFY压缩1.2171.235将这两种方法进行对比，从盒维数上说，通过以上一系列实验，可以看出，不论是单个图形还是复合图形，使用POINT_REMOVE压缩后图形的盒维数与使用BEND_REMOVE压缩后图形的盒维数相比，要更接近原图形的盒维数，但两者的差别并不是很大。通过以上一系列试验，用POINT_REMOVE和BEND_SIMPLIFY两种方法简化后的单个图形和复合图形图形与未压缩的单个图形和复合图形在面积、周长和计盒维数以及拟合程度上一系列的比较，可以总结出来，使用BEND_SIMPLIFY来简化图形，会更好一点，尤其是对简化结果要求较高的和数据量较大的数据。5总结与展望在l9世纪初期到20世纪中期期间，一些数学家、生物学家、物理学家等曾经研究了大自然中物体和现象的几何形状，大自然中的物体和现象举不胜举，但是这些物体和现象普遍具有复杂的不规则形状，传统的欧氏几何学在描述这样的自然现象时显然不再适用。因此，分形应运而生。分形理论以其独特的性质，在多个领域进行研究和发展，对许多难题做出独特的解释，其中，就包括其在数据压缩方面的应用，通过运用分形理论，可以以更加少的比特数来表示一幅图像，从而便于高效的处理、存储和传输数据。本文的主要工作如下：阐述了分形理论的研究背景和意义、分形理论的三个发展阶段，分形的特征性定义以及三种经典的分形图形，包括Koch曲线、均匀康托尔集和维尔斯特拉斯函数。介绍了分形维数常见的几种定义，包括测度和维数、Hausdorff维数、自相似维数和计盒维数；还有分形图像压缩的理论基础，包括度量空间、迭代函数系统、压缩映射定理和拼贴定理。给出了两种简化压缩方法，分别是POINT_REMOVE和BEND_SIMPLIFY，分别用两种方法对单个图形和复合图形进行简化压缩，然后统计用两种方法进行简化压缩后图形的面积和周长的变化。用专业分形计算软件对围成这些图形的复杂曲线计算它们的计盒维数，对未简化的图形和用两种方法简化的图形分别进行操作。用两种方法简化后图形的面积、周长和盒维数越接近未简化的图形，说明该简化压缩方法越好。分形图像压缩既研究了局部与局部，又研究了局部与整体之间的相关性，适用于自相似的图像压缩。分形图像压缩解码时，既能放到任意大的尺寸又能保持精细的结构。在高压缩比的情况下，分形图像自动编码具有很高的信噪比。所以分形图像压缩拥有很大的发展潜力。虽然有很多优势，但也存在着很多难关有待攻破。把分形图像压缩的理论更多的应用到实际中，在实践中推动分形理论的发展。综合分析当前的压缩算法，创新其与其他算法的相互结合，从而提高编码解码速度。提高压缩后图像的质量。随着互联网的高速发展，推动分形图像压缩与计算机的深度结合是大势所趋，使用计算机来实现复杂的算法。将分形理论在静态图像中的应用进一步推广到动态视频中，这是分形压缩的一个重要方向。参考文献[1] 常康康.基于分形理论的图像压缩算法的改进[D].南京邮电大学,2014.[2] B.B.Mandelbrot.Fractal:Form,chanceanddimension[M].Freeman,SanFrancisco,1977.[3] B.B.Mandelbrot.Thefractalgeometryofnature[M].Freeman,NewYork,1983.[4] Y.Fisher.Fractalimagecompressiontheoryandapplication[J].Springer-Verlag,NewYork,1995,34-47.[5] 管廷禄.PEANO曲线的连续性的又一证明[J].辽宁教育行政学院学报,2003(09):15.[6] MANDELBROTBB．Fractal：Form，ChanceandDimension[i]．SanFrancisco：Freeman，1977．[7] MANDELBROTBB.TheFractalGeometryofNature[M].SanFrancisco：Freeman，1982.[8] MandelbortBB．TheFractalGeometryofNature[M]NewYork：Freeman，1983．[9] 谢和平，薛秀谦.分形应用中的数学基础与方法[M].北京:科学出版社，1997:1-10.[10] MANDELBROTBB．HowlongisthecoastofBritain?Statisticalself-similarityandfractionaldimension[J]．Science，1967，155：636—638．[11] 孙洪军,赵丽红.分形理论的产生及其应用[J].辽宁工学院学报,2005(2):113-117.[12] PEITGENHO，JURGENSH，SAUPED．ChaosandFractals：NewFrontiersofScience[M]．BetlinSpringer，1993.[13] 张济忠．分形（第二版）[M]．北京：清华大学出版社，2011．[14] 谢和平.分形几何及其在岩土力学中的应用[J].岩土工程学报,1992(1):14-24.[15] 华苏.广义自相似集的维数研究[J].应用数学学报,1994(4):551-558.[16] 李克.对分形集及相关维数的讨论[J].山东科学,1996(4):12-14.[17]沈晓华.地表分形