（矿产普查与勘探专业论文）矢量数据压缩模型与算法的研究.pdf

奎堕堡! ! 叁堂夔主婴窒生堂堡笙塞至6 2 0 王53 矢量数据压缩模型与算法的研究 摘要 矢量数据压缩在地理仿真、地图数据库建设及地理信息研 究中都具有重要的意义。本文针对地图数字化后的各种图形要 素的跟踪结果利用相应的变换分析研究了矢量图形数据压缩 的模型和算法。 本文研究的内容是；根据对以往各种曲线矢量数据压缩模 型与算法的研究，建立了基于b 样条的曲线矢量图形要素的数 据压缩模型和算法；在前人研究的基础上，建立基于主轴模式 的矩形图形要素的数据压缩模型和算法；本文作者将h o u g h 变换应用到折线、圆及椭圆图形要素的矢量数据压缩上，在此 基础上改进了基于h o u g h 变换的折线、圆及椭圆图形要素的数 据压缩模型和算法。 矢量图形数据压缩主要是对存贮图形要素的数据进行处理 研究，首先剔除多余的点，对特征点进行追踪，再对特征点进 行相应的变换，较好地解决了矢量图形的数据压缩问题，具有 太原理l ：火学硕士研究生学位论文 较好的运算效果。 关键词矢量数掘压缩，b 样条曲线，h o u g h 变换 2 太原理：j ：大学硕士研究生学位论文 t h er e s e a r c ho nt h ec o m p r e s s i o nm o d e a n da l g o r i t h mf o rv e c t o r d a ：1 1 a a b s t r a c t v e c t o rd a t a c o m p r e s s i o n c a r r i e s i m p o r t a n ts i g n i f i c a n c e i n s t u d i e ss u c ha sg e o g r a p h ye n v i r o n m e n t s i m u l a t i o n ，m a pd a t a b a s e e s t a b l i s h m e n ta n dg i s t h ep a p e rs t u d i e sm o d e l sa n da l g o r i t h m s o ft h ev e c t o r g r a p h i c d a t a c o m p r e s s i o n w i t h c o r r e s p o n d i n g t r a n s f o r mi nt h e t r a c i n g r e s u l t o fv a r i o u s g r a p h i cf a c t o r s a f t e r d i g i t i z a t i o n t h e s t u d y e s t a b l i s h e st h e c o m p r e s s i o n o fm o d e l sa n d a l g o r i t h m sf o rv e c t o rg r a p h i c sd a t ao nd i f f e r e n tb a s i s ，i n c l u d i n go n t h eb a s i so fv e c t o r g r a p h i c f a c t o r so fb s p l i n e c u r v e si n p r e d e c e s s o r sr e s e a r c h ；o nt h eb a s i so fr e c t a n g l eg r a p h i cf a c t o r si n m a i na x i s m o d e ；o n t h eb a s i so ft h e a p p l i c a t i o n o f h o u g h t r a n s f o r mt o p o l y g o n a ll i n e ，e l l i p s e a n d c i r c l e ，s o t h e s t u d y i m p r o v e st h em o d e l sa n da l g o r i t h m so fc o m p r e s s i o nf o rv e c t o r g r a p h i c d a t a 3 太原玛i ly l ：人学硕士研究生学位论文 t h ec o m p r e s s i o nf o rv e c t o rg r a p h i cd a t am a i n l ys t u d i e st h e d a t ao fs t o r i n g g r a p h i cf a c t o r s f i r s t ，t h e r e d u n d a n tp o i n t sa r e e l i m i n a t e da n dt h ef e a t u r ep o i n t sa r et r a c e d s e c o n d ，t h ef e a t u r e p o i n t sa r et r a n s f o r m e dc o r r e s p o n d i n g l y t h ep a p e r c a nr e s o l v et h e p r o b l e mo fv e c t o rd a t ac o m p r e s s i o nv e r yw e l l a n dt h e s em o d e l s a n da l g o r i t h m sh a v e h i g he f f i c i e n c yo n v e c t o rd a t ac o m p r e s s i o n k e yw o r d s ；v e c t o rd a t ac o m p r e s s i o n ，bs p l i n ec u r v e ，h o u g h t r a n s f o r m 4 太原理工大学硕士研究生学位论文 1 引言 第一章绪论 地形图是用以表达自然地理和人文地理的图纸川。它是以一定的规 则，由点、线、面三种基本要素组成的，含有丰富的自然、社会信息的 特定图形的集合，是人类社会活动的重要工具之一，在社会生活、国民 经济建设、国防事业等领域有着广泛的用途。在信息社会里以纸质地图 来存贮和表示地理信息的方式越来越难以满足人们的需要，其缺点主要 表现在：地球表面包含着无限的各种信息，人们针对不同的用途又需 要测绘不同品种和不同比例尺的地图。尤其是象我国这样幅员辽阔的国 家，地图的数量是十分巨大的，这就给地理信息的保存、管理和使用带 来了很大的困难。随着社会的不断发展，自然地理信息和人文地理信 息也在不断地改变和增长，这就需要对地图进行及时的更新，而纸质地 图不利于对地理信息进行快速的修改和更新。地理信息作为宝贵的信 息资源，在使用中经常要进行用户和地理信息库以及用户和用户之间的 调用，而纸质地图不利于地理信息的快速传输。随着计算机技术的发 展和地理信息应用范围的拓广，人们往往要利用地理信息进行各种空间 分析和辅助决策，而纸质地图难以满足对地理信息的这种高层次的需求 ( 郝向阳，1 9 9 6 ) 。随着计算机技术的发展和各种c a d 技术、g i s 技术 发展的需要，一种由数字贮存代替纸质贮存，由计算机进行控制、管理、 显示、必要时可输出到纸面上的数字地图( 也称为电子地图) 正在逐渐 地成为各种自动化系统中重要的和基本的组成部分。现在地图已经在地 理信息管理、国防建设、环境管理、资源管理等方面得到了广泛的应用， 太原理工大学硕士研究生学位论文 随着现代化发展的需要，它将更广泛、更深入地应用到更多的领域。 地理信息系统( g i s ) 是由计算机、地理信息系统软件、空间数据、 分析应用模型和用户界面及系统人员组成。可对空间数据进行组织、管 理、分析和输出的系统。是随着地理学科、计算机技术、遥感技术和信 息科学的发展而发展起来的一个学科，是信息科学和信息产业的重要组 成部分，受到了国内外各行各业的普遍重视。各种各样的g i s 软件也相 应地开发出来，这些软件在处理数据时为了减少贮存空间和提高处理速 度需要进行数据压缩，对矢量化后的地形图进行压缩处理的过程称之为 地图矢量数据的压缩。近年来，出现的各种矢量化软件大大提高了对地 图的数字化速度，但矢量化后的数字地图还存在数据冗余量大、图形失 真等缺点，这就要对矢量化后的地图进行冗余数据的剔除和数据压缩等 处理，本文针对这些问题进行了研究。 2 矢量数据压缩的意义及必要性 矢量数据压缩是计算机图形学、计算机自动制图和地理信息系统等 学科中的一个常见问题，其实质是一个信息压缩问题。它是从组成曲线 的点序集合a 中提取一个点序子集a ，用这个子集作为一个新的信息源， 在规定的精度范围内该子集从内容上尽可能地反映原集合a ，而数量上 尽可能精简。在空间数据处理领域，曲线矢量数据压缩也可认为是线状 物体的抽样数据的重采样技术。一个线状物体的能力越强随之而来的 是数据量急剧增大对数据管理和分析都带来困难。因此，矢量地图压 缩的任务在于以尽可能少的抽样点来描述原始地物，并保证在容许的误 差范围内，再现地物的形态特征。本文所述的数据压缩是针对各种图形 要素的数据特征，采用较成熟的数据压缩模型和算法用软件实现压缩的 2 太原理工大学硕士研究生学位论文 目的。 在地理环境仿真应用中，要求电子地图的显示能实现从大地幅( 区 域很大，如涉及几个省) 到小地幅( 区域较小，如只涉及一个城市) 的 无级缩放。但在实际应用中的数据根本无法满足这一需求。如在地形图 的放大过程中希望细节能随之增加，但放大到小比例尺地图的细节不够， 而又没有达到大比例尺地图的细节时，就需要有一个中间层次的基于大 比例尺地图的压缩了的数据支持，即通过对矢量地图数据的压缩，使电 子地图无级缩放过程中得到多细节的数据支持。 对于目前我国的地图数据库，其中存在不少深层次的问题，这些问 题在一般性的应用中不易发现或可以忽略。但在大量使用时，就明显的 暴露出来，如：数据冗余问题。由于矢量化过程中不同的作业人员采集 的密度( 主要指线状数据的采集密度) 不同，有的较密，除特征点外大 量的采集非特征点数据，导致出现锯齿状效果，且会增加数据量。这样 的数据需要把冗余的数据点剔除，在数据量上达到压缩的目的。这种压 缩要求特征点得以保留，且不产生位移，线化总体轮廓特征得以保留。 跟踪后的矢量化地图存在大量的冗余信息及大量的重合点，这些冗 余信息和重台点会占据大量的存储空间，并且在作图或浏览图形时处理 速度慢。为了减少存贮空间和加快处理速度，人们对矢量图形数据特别 是曲线压缩算法进行了大量的研究( w i l l i a m s ，1 9 7 8 ；d u n h a n ，1 9 8 6 等) 。 基本方法是在满足某种准则的前提下使曲线的数据量尽可能小，描述物 体形状轮廓线的特征点包含有该物体形状的丰富信息，利用这些特征点 可对矢量数据进行压缩，提取物体形状特征点的方法主要有多边形逼近 法、角点探测法和曲线拟合法。矢量图形要索的跟踪结果是一个坐标对 序列，数据有着很大的冗余度，由此来看，图形的矢量数据压缩是必须 的。 3 太原理工大学硕士研究生学位论文 矢量化后的电子地图的图形要素主要有点、点状符号、折线、等高 线以及多边形等。所以矢量数据压缩是指对各种图形要素的压缩，由于 地形地貌中最多的图形要素是等高线，所以人们把对地图矢量数据压缩 主要精力集中到是对曲线( 等高线) 矢量数据的压缩。 3 矢量数据压缩准则 跟踪矢量化后的图形信息压缩就是从组成图形的数据集合a 中提取 一个子集a ，用这个子集作为一个新的信息源，使a 能够从内容上尽可 能地反映原集合a ，而在数据量上有尽可能大的压缩比。黄培之( 1 9 9 5 ) 讨论了曲线压缩的准则，简述如下： 描述某一图形要素的点序集合a 为 a ：( a j ，a 2 ，a 3 - 一，a ，i ，a 。 等同于折线a a ：，a ：a 3 ，a 。a ，构成。压缩信息时，即从点序集合a 中 抽取一个子集合a 为 a ： a ，a 5 ：，a 以，a 5 。，a 瓦l 等同于折线a s , a a s 2 a 妒，a 札a 瓦代替原来的跟踪后的图形。 曲线压缩的指标主要有极差、离差、面积误差和压缩比。 ( 1 ) 极差：反映在同一比例尺下，被舍去的点距其两端点连线偏差的 最大值。 瓯= f ( 2 ) 离差： 4 太原理工大学硕士研究生学位论文 o p2 式中：n 为点序列a 的点数，为点序列a 中第i 点与压缩后其两端保 留点连线的偏差，以垂距计，显然，保留点的= o 。 该指标描述由于取舍引起的总的偏离程度。它与统计学中的标准差 十分类似，d 。与曲线长度之比称之为相对离差。 ( 3 ) 面积误差：由压缩后的保留点序列中各相邻两点的连线中的所有 舍取点所构成的多边形的面积代数和表示，位于压缩后保留点连线两侧 的多边形的面积符号相反。不难看出，面积误差代数和表示压缩后所得 保留点精度分布的均匀程度。 ( 4 ) 压缩比： 口= 式中：n 为构成曲线点序列a 的点数，k 为压缩后所得保留点序列a 的 点数。 4 地图矢量数据压缩技术与现状 地图矢量数据的压缩主要包括各种图形要素的数据压缩。等高线是 地图中最多的图形要素，所以对矢量化后的地图的数据压缩主要是对曲 线的压缩，目前讨论最多的是曲线矢量数据的压缩，但，由于折线、矩 形、圆及椭圆等图形要素在地形图中占有的比例较小，没有引起人们的 注意，所以国内外对折线、矩形、圆及椭圆的矢量数据压缩模型与算法 的讨论和研究很少。对矢量的数据压缩算法人们进行了大量的研究。 5 厚 太原理工大学硕士研究生学位论文 常用曲线矢量数据压缩算法大体上分为局部和整体两类。局部算法 主要是对曲线的某一局部进行分析，然后得出压缩后的保留点，如： r e u m a n n - - w i t k a m ( 1 9 7 4 ) 方法等 整体算法是先对曲线进行整体分祈 找出起始保留点，然后对相邻保留点间的曲线进行分析，找出下一个保 留点，如此反复进行，直到把曲线上所有保留点都提取下来，如s p l i t t i n g ( 1 9 7 3 ) 方法、s p l i t t i n g - a n d m e r g e ( 1 9 9 1 ) 方法等。目前曲线矢量数 据压缩算法主要有：垂距限值法、角度限值法、d o u g l a s p e u c k e r 算法( 部 分文献称之为s p i r i n g 算法) ，以及黄培之1 9 9 5 年提出的具有预测功能的 曲线矢量数据压缩方法。这些算法按照选点的约束条件总体上可分为距 离控制和角度控制两类。由于距离计算在执行效率方面的优势，使得垂 距限值法和d o u g l a s - p e u c k e r 算法的应用较另一种算法普遍。下面我们详 细介绍各种曲线矢量数据压缩算法。 ( 1 ) 垂距限值法 此法早在1 9 6 7 年就有人提出【2 】。如图1 1 所示，它是从数字化等高 线串的一端点开始，然后利用三点合一的方式计算出第一点和三点合一 的第三点间的直线再计算从直线到三点合一形式的第二点垂直距离。 如果算出的垂直距离比要求的容许值( d t ) 小，那么，在这种情况下， 三点合一式中的第二点数据就要舍弃，否则，三点合一式中的第二点数 据保留。 6 太原理工大学硕士研究生学位论文 图1 - 1 垂距限值法 f i g1 - 1t h em e t h o d o fl i m i t e dv e r t i c a ld i s t a n c e ( 2 ) 角度限值法 角度限值法也是从数字化等高线一端开始，运用三个点一组计算第 一点、第二点之间的连线与第一点、第三点之间连线的夹角，若角度c t 大 于预定限值a ，则第二点保留，否则剔除第二点( 如图1 2 所示) 。 p 笋。一。 v 户： ( a ) 原始线段 ( b ) 口l a ，b 点保留 彦乡彳v ( c ) 口l a ，只点被剔除 ( d ) 化简后线段 图卜2 角度限值法 f i g1 - 2t h em e t h o do fl i m i t e da n g l e ( 3 ) d o u g l a s p e u c k e r 算法 7 太原理工大学硕士研究生学位论文 d o u g l a s p e u c k e r 算法事实上是垂距限值法的改进3 1 ，该算法于1 9 7 3 年前后由多人同时提出，是一种常用的曲线矢量数据压缩方法和曲线多 边形逼近算法。与垂距限值法的不同之处是，该算法同时考虑整个益线， 而不是把曲线数据分配给数据点的三点合一形式，算法的基本思想是： 设曲线由点序只，尸，只构成，取只，只为起始点和终止点，计算所 有内点只( f - 2 , 3 ，n 1 ) 到直线只只的距离d ，选取其中距离最大的点 只，如果d 。小于给定精度限差，则剔除只p ，的全部内点，反之点只为压 缩后的保留点。利用保留点r 将原曲线分为两段：只- 只和只一只，用同 样的方法对位于它们之间的曲线上的离散点进行检测，以确定下一批压 缩后的保留点。依此方法反复进行，直至两端点之间的曲线上的离散点 与两端点连线的距离最大值小于给定的精度限差为止。 从上述可以分析看出，d o u g l a s - p e u c k e r 算法是一个从整体到局部， 即由粗到细的方法来确定曲线压缩后保留点的过程，其优点是具有平移、 旋转的不变性，给定曲线与限差后，抽样结果一致。 在实际应用中，这三种算法并不是孤立进行的而是有机地结合起 来。如，对于高、中山地貌，仅仅采用垂距限值法往往需要很多次试验 才能得到满意的结果。如果采用垂距限值法与d o u 9 1 a s p e u c k e r 算法相 结合，则只需1 次或2 次就可完成数据压缩。因此，将这些算法有机地 结合起来，可提高工作效率。 ( 4 ) 具有预测功能的曲线矢量数据压缩算法，采用的方法如下框图所 不4 一般顾及精度的较长距离边端点的寻求算法是1 4 i ：当给定一起始点 时，如图1 - 4 中的只点，曲线上只点的后续点尸。姐= i + 1 ，f + 2 ，n ) 均可 8 太原理工大学硕士研究生学位论文 以视为其较长距离边的另一端点的备选点。只点与只点所在直线丽的 方程为 ( y 。一y i ) x 一( ，一x i ) y x i y 。+ 工。y j = 0 ( 1 一1 ) 图卜3 具有预测功能的曲线矢量数据压缩算法框图 地1 - 3p r e d i c t e d m e t h o do f c u r v e sv e c t o r d a t ac o m p r e s s i o n 设曲线上只点与只点之间的任一点为 只( = i + l ，i + 2 ，i + 3 ，“一1 ) 。只点到直线只只的距离为 d 。：幽垒三鱼三望丝三兰垫剑 ( 1 0 2 ) “l 一f 2 = = = = = = = = = = = = = = = 一 llzj “ ( 工。一石，) 2 + ( y 。一y i ) 2 用式( 1 - 1 ) 和( 1 2 ) 对各个备选点尸，按曲线走向依次进行检测。如果 9 太原理工大学硕士研究生学位论文 对某一个备选点所有的d ，均小于给定的精度限差，则对该备选点的下一 个后续点进行检测。否则，该备选点的前一个点为所寻求的较长距离边 的另一个端点。如图1 4 所示的曲线，当对备选点只进行检测时以大 于给定的精度限差，则该点的前一个点即p 。点即为所寻求的较长距离 边的另一端点。然后该端点作为新的起始点，用同样的方法确定其下一 个压缩后的保留点。用上述方法反复进行，直到曲线压缩后的所有保留 点得到确定。 户。 图卜4 顾及精度的较长距离边端点的寻求 f i g1 - 4 t h e m e t h o d o fs e e k i n g e n d p o i n to f l o n g e n de d g e 最长距离边端点预测算法包括了最长距离边端点的直接预测算法和 最长距离边端点的间接预测算法。 虽长距离边端点的直接预测算法是：当曲线以某一给定起始点( 如 图l _ 4 中只点) 出发，在满足给定的精度限差的情况下用较长距离边端 点寻求算法对其后续点进行检测时，当进行到其中某一点时( 如图1 4 1 0 太原理工大学硕士研究生学位论文 中的p ，点) 。两端点之间的曲线上的各点到两个端点所在直线的距离最大 值d 。一大于给定的精度限差，此时先把该点的前一点( 如图1 - 4 中的p 。 点) 视为最长距离边端点的初值。然后依次继续对其后续预测区域内的 各个点用同样的算法进行检测，以确定其是否为最长距离边的端点。当 这种检测进行到某点时。其中各点的误差均满足给定的精度限差如图 l 一4 中的p 。点则该点即为所求的最长距离边端点的又一个取值，显然 该点( p + ，点) 优于初值( p 。点) 。用上述方法，反复交替进行，直至 所得到的最长距离边端点的最新取值的预测区域内的所有点都不是最长 距离边端点取值，此时最长距离边端点取值得到确定。 最长距离边端点的间接预测算法是：由于用最长距离边端点的直接 预测算法对预测区域每一个预测点都进行检测，有着计算量大，运行速 度慢之缺点。为了克服上述缺点，可以先用式( t - 3 ) 来对预测区域内的 各个预测点进行估算，找出可能的最长距离边的下一个端点，然后再对 其进行直接检测。 t g t z , ：盟；( “= j + l ，j + 2 ，j + 3 ，j + m ) ( 1 - 3 ) 扎一x i 当t g a 。大于t g a ，时，则只点可能是虽大距离边端点的又一个取值。因为 这时原最大位移点的位移变小。此时再用顾及精度的较长距离边端点的 寻求算法对该点进行检测以确定其是否为最长距离边端点的又一个取 值，若是则继续用顾及精度较长距离边端点寻求算法，对后续点进行 检测，反之，用t g a 。代替t g a 继续对预测区域的下一个预测点用式 ( 1 - 3 ) 进行检测。用此方法反复进行，宜至预测区域内所有预测点都不 是最长距离边端点的取值为止。此时最长距离边端点的取值可以确定。 查堕堡j ：j j ! 三堂塑主竺塑兰堂堡堡苎 但这种方法给定精度要求，尽管上述算法能达到这一给定的要求，由于 要多次计算方位角，效率不是很高。 ( 5 ) 基于小波变换的地图矢量数据压缩模型 根据小波分析理论，我们可以将空间l 2 ( r ) 看成是某地理空间在特定 比例尺下的地图数据模型，( z ) 是其上各图形要素( 如：线状要素 y = ，( 工) ) ，那么帆：l ：则可看成是基于此比例尺下原始数据的多级压缩 模型。 在实际应用中，分辨率是有限的，所以可以认为l 2 ( 尺) = k 。这样， 从k 出发，应用尺度函数可以表示出u ，k ，u ，此过程可以看作是 基于小波多尺度分析的由原始矢量地图数据k 到压缩矢量地图数据 u ，k ，k ，的压缩过程，即地图数据，( 工) 在各个层次上的近似表示。 实际中，地形曲线( 等高线) y = ，( 石) 可以看作离散形式f ( x 。) = c ：， n = 1 , 2 ，3 ，于是，根据小波分解公式 c ? = 击娶一尊1 川2 3 ( 1 - 4 ) d 。i = 去趾扩：。 v z 可以从c ：。得到c ：。 而根据上式，c ：的数据量是c 的一半，由此可得到压缩了的矢量 地图数据c ：( ，= 1 , 2 ，3 ) 。 1 2 太原理工大学硕士研究生学位论文 公式( 1 - 4 ) 即为基于小波分析的矢量地图数据压缩计算公式。而d ? 为从c ：“得到c ：的细节部分，如果我们仅仅以c ! 作为c 的近似- 则 丢掉的是细节d ? ，但是，对矢量地图数据来说，d ? 中包含着原始数据的 特征部分，即特征点的信息。原因是小波本身具有光滑作用，经小波变 换后，原数据在被简化( 压缩) 的同时，也被做了光滑处理，这样有 些特征点就会丢失，这是不允许的。所以，细节部分d ? 不应被随意丢掉， 或者在经小波变换后进行特征点的追踪，以得到“回补”作用。如下面 所述。 一般地，经j 次小波变换后( 不对d ：进行处理) ，即可得j 次压缩 后的矢量地图数据，其数据量为n + 2 ，其中为原矢量地图数据量。 根据上述模型和公式( 1 4 ) 下面对一幅实际矢量地图数据进行试 验。图1 5 为一矢量地图数据，由5 9 4 个坐标点，利用上述模型，对图 1 5 进行小波变换得到图1 - 6 ，剩余2 9 7 个坐标点，压缩比为5 0 。 图1 - 5 原图( 有5 9 4 个坐标点) n gl - 5o r i g i n a lc h a r t ( 5 9 4p o i n t s ) 1 3 太原理工大学硕士研究生学位论文 图1 _ 6 小波压缩图( 有2 97 个坐标占、) f i g1 - 6s m “w a v e l e t c o m p r e s s e dc h a r t ( 2 9 7p o i n 田 由试验可以看出：经小波变换后，原数据得到了压缩简化，数据量 只有原来的一半，并且压缩简化图形( 图l 一6 ) 基本保留了原数据的轮廓 特征虽然还存在一些问题，但效果还是比较好的。这种压缩算法的缺 点是没有对压缩后的曲线进行光滑处理不够充分，特征信息丢失太多。 5 本文研究的主要内容 根据矢量化中存在的数据量大，冗余信息繁多的问题，本文针对地 形图中的各种地形要素研究了相应的压缩模型与算法。并在跟踪矢量化 前设置跟踪方式，每种跟踪方式对应一种图形要素( 即分类跟踪) ，这种 方法在手动跟踪中具有较高效率。将三次b 样条曲线应用予益线( 等高 线) 的矢量数据压缩中。在分析了前人对等高线矢量数据压缩的基础上， 建立了基于三次b 样条的等高线矢量数据压缩模型与算法；h o u g h 变换 作为一门应用数学理论，在众多学科领域取得了许多重要的理论和应用 成果，本文主要利用h o u g h 变换在矢量数据压缩中的应用，对任意折线、 圆及椭圆等图形要素的压缩模型和算法进行了研究与探讨；利用模式主 轴的方法对矩形进行压缩。分析了以往各干叶，曲线矢量数据压缩算法并对 1 4 太原理工大学硕士研究生学位论文 算法进行了简单的分析。上述针对各种图形要素的矢量数据压缩模型与 算法可用图1 7 表示。其中“混合要素”为：如果选择该跟踪方式则要 先判断要跟踪的要素是何种图形要素，根据判断结果选择用何种压缩模 型与算法。 图1 - 7 设置跟踪方式 n g1 7s e tt r a c i n gw a y 1 5 太原理工大学硕士研究生学位论文 第二章基于三次b 样条的等高线矢量数据压缩 1 引言 数字地图自动综合的研究是一个非常艰难的课题。从理论和技术的 角度讲，建立制图综合的数学模型( 数量定额模型、结累模型、过 程模型) 是其必须解决的一个难题。 容各要素综合中最复杂的课题之一。 而地貌等高线的自动综合是地图内 目前这方面的研究虽然不少，但所 取得的实际成果距离实用要求还相差较远。关于地貌等高线的自动综合， 目前常用的方法大致可以概括为三类：曲( 单) 线综合法、曲面综合法 和地貌结构线综合法。其中曲线综合法发展最早，且方法简单，但很难 顾及等高线之间的联系。容易造成对地貌形态的歪曲。曲面综合法和地 貌结构线综合法克服了前者的缺点但其过程过于繁复，信息量损失大， 精度不高。但我们通过分析可以知道，面向单根等高线的曲线简化方法 也有其它方法所不及的长处，如：处理过程简捷、信息量损失小、精度 高等，它的缺点在很大程度上是由于不能有效地保留原曲线的形状结构 特征造成的。因为追貌形态是通过等高线表现出来的，地貌形态的自动 综合最终也表现为对每一根等高线的综合，因此，如综合后能保留原每 根等高线的形状结构特征，那么原有等高线之间的内在联系也会得到 自然的保留，从而，面向单根等高线简化的技术路线是切实可行的。本 章所研究的基于三次口样条曲线的等高线矢量数据压缩算法是在葛永慧 教授提出的曲线特征点提取链码算法的基础上利用提取后的曲线特征点 求出日样条的控制点，进而将跟踪后的曲线转换成三次b 样条曲线，该 方法很好的解决了上述问题。本章科用基于二值凰像八连通跟踪结果的 1 6 太原理工大学硕士研究生学位论文 曲线上特征点的提取算法可以保留原曲线的总体形态特性以及三次b 样 条光滑连续性的特点，研究了地貌形态自动综合中等高线矢量数据的压 缩，并进行了大量的试验。理论和试验结果表明，基于三次b 样条的等 高线矢量数据压缩方法能保留原等高线的形状结构特征，并达到了压缩 与光滑的同步进行具有良好的效果。 在计算机自动制图中应用计算机处理业已得到的数字化资料就不能 不注重计算机的容量和计算机工作量的问题。因此产生了计算机自动制 图中的曲线( 等高线) 压缩问题，本文对等高线进行曲线矢量数据压缩 的算法主要采用了先提取跟踪矢量化后曲线上的特征点( 目标轮廓点) ， 再利用提取后的等高线的特征点作为三次8 样条的型值点求出三次b 样 条的控制点，存贮时只存贮三次b 样条的控制点。这样就大大节省了存 贮空间。 2 三次b 样条的基本概念与性质 以b e r n s t e i n 调和函数构造的b e z i e r 曲线有许多优越性“，但有两点 不足：其一是特征多边形顶点个数决定了b e z i e r 曲线的阶次，并且当, z 较 大时，特征多边形对曲线的控制将会减弱；其二是b e z i e r 曲线不能做局 部修改，即改变某一个控制点的位置对整条曲线都有影响，其原因是调 和函数b 。( f ) 在0 t 1 的整个区间内均不为零。1 9 7 2 年，g o r d o n 、 r i e s e n f e l d 等人拓宽了b e z i e r 曲线用b 样条函数代替b e r n s t e i n 函数， 从而改进了b e z i e r 特征多边形与b e r n s t e i n 多项式次数有关，且是整体逼 近的弱点。 定义和性质 1 7 太原理工大学硕士研究生学位论文 均匀b 样条函数的定义 参照b e z i e r 曲线公式，已知n + 1 个控制点只( f - 0 3 ，n ) 也称之 为特征多边形的顶点，彤阶( k 1 次) b 样条曲线的表达式是： c ( “) = 只( “) i = 0 其中n 。( “) 是调和函数- 也称之为基函数- 按照递归公式可定义为： 。器 。，。、似一 。) i 卜t ( “) 。 f - 。2 筹+ 豁“鱼“ 沼， 堕型型( f 。s 。钆 l i + k - l i + l 其中f 。是节点值，t = 1 0 , 一。】构成了芷阶曰样条函数的节点矢量， 其中的节点是非减序列且l = n k + l 。当节点沿参数轴是不等距分布 时，即t 。- - t i 常数时，则表示非均匀b 样条函数。均匀非周期b 样条 节点的取值有如下规律： t ：= 0当f k l t 。= i k + 1当七蔓i u 当f u 用截断幂函数的差商定义8 样条函数，设t = i t , 】是一个非减实数序列， 关于f 的第i 个b 样条函数定义是： m 蚰( “) = 【f i ，r ，t 】( f 一“) ， | v ( “) = ( f m t i ) m ( “) ， 为非均匀k 阶b 样条函数其中i l r ( 实数域) ，( f h ) ：。为双变量截断 幂函数。在作差商运算时，r 为变量u 为常量；在差商运算以后u 为 变量， f 被节点i i , f 。，f 代替。由定义可见n “( “) 仅与f 中的k + 1 个 节点l i , r 。，t 。有关，而且f ，序列中可能会有重复情况，均匀b 样条函 数只是它的种特殊情况。非均匀b 样条基函数如图2 3 所示。 太原理工大学硕士研究生学位论文 t ( b ) 图2 - 3 非均匀b 样务基函数 n g2 - 3n o n u n i f o r mbs p l i n eb a s ef u n c t i o n b 样条曲线的性质 a ：局部性 因为| m ( “) 仨： r i 。i 或 “l i + kk 。即( “) 在区间( 。t ) 中为 正，在其它地方n 。( “) 为零，这就使得k 阶b 样条曲线在修改时只被相 邻的k 个顶点所控制，而与其他顶点无关。当移动一个顶点时，只对其 中的一段曲线有影响，并不对整条曲线产生影响，如图2 4 所示是一条 均匀口样条曲线。该图表示顶点p 5 变化后曲线变化的情况。由图可见点 p 5 的变化只对其中的一段曲线有影响。 b ：连续性 b 样条曲线在r ，( f + 1 i n ) 处有l 重节点的连续性不低于( k l 一1 ) 阶。整条曲线c ( “) 的连续性不低于( 女一l 。，一1 ) 阶，其中l 。；是在区间 2 1 太原理工大学硕士研究生学位论文 ( f 。，+ ，) 内的最大重节点数。 c ：几何不变性 占样条曲线c ( u ) 的形状和位置与坐标系的选择无关。 d ：变差缩减性 设( n + 1 ) 个控制点e o ，鼻，f ，构成b 样条曲线c ( “) 的特征多边形， 在该平面内的任意一条直线与c ( u ) 的交点个数不多于该直线和特征多 边形的交点个数。 图2 - 4b 样条的局部可控性 f i g2 - - 4l o c a lc o n t r o l - c h a r a c t e ro fbs p l i n e e ：造型的灵活性 用b 样条曲线可构造直线段、尖点、切线等特殊情况。对于四阶( 三 次) b 样条曲线c ( “) 若要在其中得到一条直线段，只要只，只。r ：，和只。 四点位于一条直线上，此时c ( “) 对应的r l + 3 h f 。的曲线既为一段直线 且和只，只。r ：，只+ ，所在的直线重合。为了使c ( h ) 能通过只点只要使 只，只+ 。和只+ 2 三点重合- 此时c ( “) 过只点( 尖点) 。图2 5 表示三次b 样 条曲线在b 处有二重顶点和三重顶点的情况。为了使b 样条曲线c “) 和 某一直线l 相切，只要求b 样条曲线的控制点只，只。只+ ：位于l 上，并且 太原理工大学硕士研究生学位论文 节点和t 。的重节点数不大于2 。这几例说明只要灵活地选择控制点的位 置和节点t ，的重复数，可形成许多特殊情况的b 样条曲线。 图2 - 5 三次b 样条曲线在p 2 点有重节点的情况 f i g2 - 5t h r e e b s p l i n eh a v er e p e a tn o d eo np 2 f 导数 对日样条曲线表达式求导，即为对日样条基函数求导，即 导数 n + 1，i + i n + l c 1 。= 只：。 ) ，c ”( f ) = e e , n i 。( “) ，c ) = 只船( “) ，一阶 n t = n 一l ( u ) + ( i i t i ) m l +坠! 生竺坐二! 竺! 二竺坐! ：! 竺! 其中 当k + l , n i ，知：当k = 2 , n i “f f ) = 等+ 兰 二阶导数， 2 3 太原理工大学硕士研究生学位论文 嘶) = 塾警 丛坠坠 ! ! 竺! ：塑塑二! 竺坐= ! 塑 t i + t t f + l 其中，当k = 1 ，k = 2 时， i ( m ) = i ：m ) = 0 当k = 3 时， 啪阳( 等+ 糍 上式说明b 样条曲线的导数可用其低阶的b 样条基函数和顶点矢量 的差商序列的线性组合表示。也不难证明彤阶8 样条曲线段之间达到 k 一2 次的连续性。 曰样条曲线的矩阵表示 基于占样条函数我们可以较容易地推出b 样条曲线的矩阵表示，本 文采用的是三次均匀b 样条曲线，因此在这里我们只介绍三次8 样条的 矩阵表示。 若从空间n + 1 个顶点只( i = 0 , 1 ，n ) 中每次取相邻的四个顶点，可构 造出一段三次b 样条曲线，其相应的基函数是 。( “) = i n 。( “) n ：。( “) n ( “) n 。( “) j ， l4 ( m ) = ( 1 6 ) ( - u3 + 3 u 2 3 “十1 ) ，n 2 、4 ( “) = ( t 6 ) ( 3 u 3 - 6 u 2 + 4 ) 3 4 ( f ) = ( 1 ，6 ) ( 一3 1 , 3 + 3 u 2 + 3 u + i ) ，4 ，。( “) = ( 1 1 6 ) ( u 3 ) ；“1 0 ，1 】 三次b 样条曲线基函数的矩阵表示为： 。( “) = ( 1 6 ) t , t 3 l l2 “1 j 相邻两段三次口样条曲线可表示为 2 4 一i3 36 30 l4 3l 30 3o lo 太原理工大学硕士研究生学位论文 c “( “) = n l 4 ( “) 只一t + 2 4 ( “) + 3 4 ( “) 只+ t + 只+ ： 故第l c i + t , 4 ( h ) = n i4 ( “) 只+ n 2 4 ) 只+ l + n 3 4 0 ) 只- i - 2 + n 4 4 ( h ) 只+ 3 段三次b 样条曲线可写成：c i 4 ( “) = n ( “) 只巾：，对应的矩阵式是 c i 4 ( “) = ( 1 ，6 ) k 3 l l2 “1 骢 i = 1 , 2 ，n 一2 。三次b 样条曲线有如下几何性质。 “ o ，1 a ：端点位置矢量。 c “( 0 ) = 只一i 6 + 4 9 + ，6 ，c “( 1 ) = 只6 + 4 p i + 1 1 6 + r 2 6 ；曲线起点位 于只一，只瓦中线p , m 的l 3 处，终点位于只只+ ，只+ ：中线只+ 。m 的l 3 处。 b ：端点切矢量。c j 。( o ) = ( 只。一只一) 1 2 ，c ；，。( 1 ) = ( & 2 一p j ) 2 ：曲线 在始点处的切矢量平行于只一。只只+ 。的边只一r 。，其模长为该边长的i 2 ， 终点处的切矢量平行于只只+ 只+ ! 的边只 ：，其模长为该边长的i 2 。由 于前二段曲线的终点就是下一段曲线的起点，而且具有共同的三角形， 所以，从几何上可见两段曲线在节点处具有相同的一阶导数矢量。 c ：端点的二阶导数矢量。 c i 。( o ) = 只一。一2 只+ 只。c 0 ( 1 ) = 只一：只+ + 只+ ：；曲线段在端点处的二 阶导数矢量等于相邻两直线边所形成平行四边形的对角线。由于终点处 的平行四边形和下一段曲线在始点处的平行四边形相同，故三次日样条 曲线在节点处有二阶导数连续，即有：c i 。( 1 ) = c l 。( o ) 。 0 3 3 3 巧o 4o ，o 。 ，。l 太原理工大学硕士研究生学位论文 d ：若只- l 、只、只+ 。三点共线，三次b 样条曲线将产生拐点：若 只小只、只小只+ ：四点共线，则c 。( “) 变成一条直线段：若只小卑气 三点重合，则c j 。( “) 过只点。巧妙地利用三次b 样条中的顶点重合将会 产生应用所需要的多种曲线。 b 样条曲线的分割和节点插入算法 d e b o o r 分割算法 由( 2 1 ) 式可知，k 阶b 样条基函数可由两个相邻的k l 阶日样 条函数线性组合而成，可用d e b o o r 算法计算