（计算机应用技术专业论文）基于striptree的矢量地图渐进式传输的研究.pdf

西南交通大学硕士研究生学位论文第一卜页 摘要 随着地理信息系统应用领域的不断扩展，人们对矢量地图的需求越来越大。 但是矢量地图数据一般都比较大，而网络带宽又是有限的，如何提高地图数据 的发布效率已经成为一个亟待解决的问题。渐进式传输是一种新型的网络数据 传输方式，它在基于栅格、t i n 、d e m 结构的地图数据的网络传输中得到了广泛 的应用，但是要实现矢量地图数据的渐进式传输还是相当复杂的。这是因为矢 量数据不能像栅格结构的地图数据那样通过简单的行列内插实现渐进传输，矢 量地图数据在渐进式传输过程中还必须考虑到它的空间拓扑关系 本文旨在维护地图质量的前提下，提高矢量地图数据网络发布的效率。基 于此目的，本文重点研究了矢量地图数据渐进传输的关键技术、渐进式传输系 统的设计与实现。主要内容包括：介绍了矢量地图渐进式传输的基本概念，并 分析了其产生的根本原因；回顾并总结了国内外关于此课题的研究现状，指出 尚且值得改进的地方；详细介绍了线要素化简算法及其改进算法，结合本文的 应用目的对各算法的优缺点进行了分析；重点阐述了基于s t r i p - t r e e 的线要素图 层压缩与重构算法，该算法能快速有效的对曲线图层进行压缩，理论上能输出 任意压缩比例的地图数据并且不会产生相交和自相交现象；分析和研究了渐进 式传输控制策略，重点研究了在网络带宽波动的情况下，服务器和客户端如何 自适应调整传输速率，从而来达到较好的传输效果；应用上述研究成果，实现 了一种基于c s 模式的矢量地图渐进式传输原型系统。 实验结果表明，本文实现的基于s t r i p - t r e e 的线要素图层压缩与重构算法和 在此基础上设计并实现的矢量地图渐进式传输原型系统能在满足用户需求、维 护地图质量的前提下，减少用户的等待时间，提高矢量地图数据网络发布的效 率。 关键词：s t r i p t r e e ；线要素图层压缩与重构；矢量地图；渐进式传输 西南交通大学硕士研究生学位论文 第一i 卜页 a b s t r a c t a l o n gw i t hg e o g r a p h i ci n f o r m a t i o ns y s t e ma p p l i c a t i o n se x p a n s i o n ，g r e a t e r d e m a n d sf o rv e c t o gm a p sa r en e e d e d h o w e v e r , t h eg e n e r a lv e c t o rm a pd a t ai sa l m o s t l a r g ea n dn e t w o r kb a n d w i d t h i sl i m i t e d h o wt oi m p r o v et h ee f f i c i e n c yo fm a pd a t a d e l i v e r yh a sb e c o m eas e r i o u sp r o b l e m p r o g r e s s i v et r a n s m i s s i o ni san o wt y p eo f n e t w o r kd a t at r a n s m i s s i o n , t h em a pd a t at r a n s m i s s i o nb a s e do ng r i d ，t i n ，d e m s t r u c t u r eh a sb e e nw i d e l yu s e d h o w e v e r , v e c t o rm a pd a t a sp r o g r e s s i v et r a n s m i s s i o n i sc o m p l e x b e c a u s et h ev e c t o rd a t a sp r o g r e s s i v et r a n s m i s s i o nd o e sn o tl i k er a s t e r m a pd a t a sp r o g r e s s i v et r a n s m i s s i o no n l yb yl i n e c o l u n mi n t e r p o l a t i o n v e c t o rd a t a s p r o g r e s s i v et r a n s m i s s i o nm u s tt a k ei n t oa o c o o n t i t st o p o l o g y t h i sp a p e ra i m st oi m p r o v et h ee f f i c i e n c yo fs p a t i a ld a t ad e l i v e r yo nt h ep r e m i s e o ft h ep r o t e c t i o no ft h em a p s q u a l i t y - f o rt h i sp u r p o s e , t h i sp a p e rf o c u s e so nk e y t e c h n o l o g i e so fv e c t o rm a pd a t a sp r o g r e s s i v et r a n s m i s s i o na n dt h ed e s i g na n d i m p l e m e n t a t i o no fp r o t o t y p es y s t e m m a i nc o n t e n t si n c l u d e ：i n t r o d u c i n gt h eb a s i c c o n c e p t so fv e c t o rm a pd a t a sp r o g r e s s i v et r a n s m i s s i o na n da n a l y z i n g i t sr o o tc a u s e s ； r e v i e w i n ga n ds u m m a r i z i n gt h es t a t u so fr e s e a r c ha th o m ea n da b r o a da n dp o i n t i n g o u tt h ew o r t h i n e s so fi m p r o v e m e n ta r e a s ；d e t a i l e d l yi n t r o d u c i n gt h ea l g o r i t h mo f l i n es i m p l i f i c a t i o na n di t si m p r o v e da l g o r i t h m s t h e na n a l y z et h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h ea l g o r i t h m sf o rt h ea p p l i c a t i o no fp r o t o t y p es y s t e m ；f o c u s i n go n t h el i n el a y e rc o m p r e s s i o na n dr e c o n s t r u c t i o na l g o r i t h mb a s e do ns t r i pt r e e , t h e a l g o r i t h mc a n , e f f e c t i v e l yc o m p r e s s a n dr e c o n s t r u c tt h ec u r v p l a y e r ，n o s e l f - i n t e r s e c t i o na n di n t e r s e c t i o na p p e a r i n g ；a n a l y z i n ga n ds t u d y i n gt h ec o n t r o l s t r a t e g yo fp r o g r e s s i v et r a n s m i s s i o n ；f o c u s i n go ns e r v e ra n dc l i e n th o w t oa d a p tt h e t r a n s m i s s i o nr a t ei nt h ec i r c u m s t a n c e so fn e t w o r kb a n d w i d t hf l u c t u a t i o n s ，s ot h a ti t c a na c h i e v eb e h e rr e s u l t so ft r a n s m i s s i o n b a s e do nt h e s er e s e a r c h e s ，i m p l e m e n t e da v e c t o rm a p sp r o g r e s s i v et r a n s m i s s i o np r o t o t y p es y s t e mb a s e de l lc sm o d e l e x p e r i m e n t a lr e s u l ts h o w st h a tt h ep r o t o t y p es y s t e mo fv e c t o rm a pd a t a p r o g r e s s i v et r a n s m i s s i o nc a nr e d u c et h eu s e r sw a i t i n gt i m ea n di m p r o v et h ed e l i v e r y e f f i c i e n c yo fs p a t i a ld a t ao nt h ep r e m i s eo fm e e t i n gu s e r sn e e da n dp r o t e c t i n gt h e q u a l i t yo ft h em a p s g d yg o r d s ：s t r i p - t r e e ，l i n el a y e rc o m p r e s s i o na n dr e c o n s t r u c t i o n ，v e c t o rm a p ， p r o g r e s s i v et r a n s m i s s i o n 西南交通大学硕士研究生学位论文第一1 一页 1 1 研究背景及意义 第1 章绪论 1 1 1 什么是矢量地图渐进式传输 渐进式传输是一种新型数据传输方式，它是将连续的数据信息经过特殊的 压缩方式分成一个个压缩包，由媒体服务器向用户计算机连续、实时地传送， 这样用户就可以边下载边使用，而不需要等待全部数据下载完才能使用。 渐进式传输一个典型的应用是在线收看或者收听网络节目。通常用户向媒 体服务器发出一个特定节目请求后，等待十几秒钟或者更短的时间就可以开始 收看或者收听该节目，而在用户收看或者收听该节目的同时，媒体服务器则在 继续传输余下的数据，这样用户就不必等待整个媒体文件下载完成才能收看或 者收听。与传统传输方式相比，渐进式传输大大缩短了用户的等待时间，提高 了传输效率。 矢量地图数据的渐进式传输是在网络环境下矢量地图数据多分辨率表达的 应用，即空间数据从低分辨率下的概略表达向高分辨率下详细表达的转变过程， 也就是制图综合的逆过程。将制图综合的中间过程做完整的记录，即将每一次 压缩的细节信息记录下来。这样原始矢量地图数据就可以组织为某一概略表达 和一系列细节增量的集合。通过在概略表达的基础上，按一定规律对细节增量 的叠加，即可实现矢量地图数据的渐进式传输【1 】。 1 1 2 为什么要渐进式传输 随着w e bg i s 的发展，通过互连网来传输空间数据已经越来越普遍。与此 同时，基于位置的服务( 1 0 c a t i o n - b a s e ds e r v i c e s ，l b s ) 也逐渐兴起，成为最具市 场潜力的移动通讯增殖业务之一。然而，一方面空间数据文件通常都比较大， 并且文件的大小会随着地理特征的不同而显著变化。另一方面虽然现在网络带 宽有所提高，但相对于日益膨胀的空间数据来说，其作用是微乎其微的，低效 率的空间数据网络发布成为阻碍空间信息发展的一个瓶颈问题。虽然提高网络 传输速度( 如使用宽带网络) 可以在一定程度上解决这个问题，但是现在的网 络空间数据库通常都是某一特定( 精细) 比例尺的数据库，用户为了使用它们 往往需要下载所有的数据，但实际上用户只会用到其中很小的一部分。所以， 西南交通大学硕士研究生学位论文第一2 一页 为了从根本上解决该问题，需要建立新型的服务器客户端机制的数据组织和网 络传输方式。 1 1 3 为什么要传输矢量数据 地理信息系统中常采用的空间数据模型主要有矢量和栅格两类。目前，基 于栅格模型的地图数据在网络渐进式传输中已得到了比较好的实现。最简单的 方法是对栅格图像地图的像素按一定的规律进行抽样并分批传送到客户端，在 客户端首先得到一个由少量像素构成的模糊图像，随着在客户端积累的像素越 来越多，图像效果就变得越来越清晰。而且极为重要的一点就是矢量栅格相互 转换已经是一件非常容易的事，那么为什么还需要传输矢量数据呢? 分析可知， 主要是基于以下几个方面的考虑：第一个方面，矢量数据通常比栅格数据文件 小，精确度也比栅格数据高。这样就可以为实时系统伪 城市1 1 0 、1 2 0 系统) 提 供及时、准确的数据。第二方面，虽然目前矢量栅格相互转换已非常成功，但 是，在栅格数据的矢量化过程中，还是会引入不可预料的误差和不确定性，并 且具有拓扑特征的点在栅格化的过程中可能转移或者消失。所以研究矢量数据 的传输是有必要的t “。 1 1 4 渐进式传输的优点 矢量地图数据的渐进式传输是一种新型的数据传输方式，它利用地图数据 的多尺度特征，实现地图表达从粗糙到精细的渐进式传输与可视化。与传统的 传输方式相比，渐进式传输的优点在于： 1 实现了“边传输，边显示”，大大缩短用户的等待时间。渐进式传输首 先传输研究区域的概略表达数据，然后逐步叠加细节数据。和完整表达的数据 量相比，概略表达的数据量是非常小的，在概略表达的数据被下载之后，客户 端即可以进行显示，这样就大大缩短了用户的等待时间，提高了传输效率。 2 渐进式是自适应的传输。它可以根据客户端的比例尺和分辨率决定传输 的数据量，比如在小比例尺低分辨率下，只传输概略数据，如果用户进一步对 某区域放大，再传输该区域的细节数据，在原概略数据的基础上叠加，用户可 以得到与比例尺相匹配的地图表达。 3 实现了传输过程与用户的交互。在传输过程中，一旦用户发现显示的数 据已经可以满足自己的需求，可以随时停止传输。这样就避免了传输不必要的 数据而浪费时间和网络资源。 4 尊重了由粗到细的空间信息认知规律，起到了信息导航的作用。人们对 西南交通大学硕士研究生学位论文第一3 页 空间现象的认知表现为从总体到局部、从概略到细微、从重要到次要的层次顺 序，在传统地图技术表达中，通常通过概略图、区位图、索引图等方式配予主 地图内容实现地物目标的搜索和空间信息的查询。渐进式传输展示了从大范围 主体信息内容到局部区域细微信息内容的动态表达，从而引导用户对感兴趣的 区域进行认知转移，辅助用户截取其感兴趣的局部区域，并沿着该路径深入到 细节内容，具有信息导航的作用i 暑】。 2 已有研究成果 1 1 1 国外研究成果 制图综合领域的学者一直试图从制图综合的角度出发去解决渐进式传输的 阅题。然而由于制图综合理论本身的不完善性和方法的不完整性使得制图综合 领域中的“和并”、“收缩”、“目标移动”、“删除”等方法在实际的运用 中很难实施。对于矢量地图数据的渐进式传输，文献 3 - 6 都是关于此的研究 下面详细介绍。 美国的b e r t o l o t t o 和e g e n h o f e r 在2 0 0 t 年从制图综合的角度首先提出 了渐进式传输一个概念性的框架。然而，由于自动制图综合方法的复杂性和不完 善性，使得该框架很难予以开发和实际应用。b u t t c n f i c l d 于2 0 0 2 年提出了服务器 上对空间数据依据重要性的有序化组织策略，从数据层、目标、细部特征三个 层次着手，其中绍部特征渐进化传输需要寻求有效的树结构描述细节的层次化。 h a n 和b c r t o l o t t 在2 0 0 3 年根据制图综合操作的原则提出了一种用于矢量地图数 据渐进式传输的原型系统，然而在他们的论文中并没有给出实验结果和系统表 现。上述研究成果还处于基础性阶段的研究，很多研究还处于概念探索性阶段。 已有的系统也只适用单一类型、小数据量的空闯数据传输，不具备实时传输的能 力，而且在维护地图质量方面所做的贡献有限。 b i s h c n gy a n g 于2 0 0 5 年提出了一种真正能用于矢量地图数据渐进式传输的 方法，因为它不仅能处理曲线还可以直接处理曲面，而以往的算法多是处理曲 线。作者的做法是定义一些数学法则给地图数据中的顶点加权，然后根据阈值 抽取一定数量顶点作为原始地图一个近似表示，没有被选取到的顶点则存放到 一个数组里并且记录它们与其他顶点的关系。初始时，先传送权值最大的顶点 到客户端，然后按权值从大n , n 顿序陆续将后续顶点分批进行传输，这样就可 以实现矢量地图数据的渐进式传输但该策略给顶点加权的约束规则缺乏严密 的数学理论来论证，并且在维护地图质量方面，还有待进一步提高。 西南交通大学硕士研究生学位论文第一4 - 页 1 2 2 国内研究成果 在国内，关于矢量地图在网上进行渐进式传输的直接研究还处于初步阶段， 但探讨g i s 数据多分辨率、多尺度表达，为渐进式传输提供技术支撑的研究已 引起有关专家的兴趣。王艳慧、陈军从概念上讨论了地理目标多分辨率表达的 基本问题，李军、周成虎对不同时间、不同专业地理数据集成过程中的尺度匹 配问题进行了研究，王家耀等基于地图综合方法提出了空间数据多尺度表达的 技术策略，王晏民、李德仁建立了一种基于基础空间数据库导出多尺度用户视 图数据的数据模型。 艾廷华2 0 0 4 年在多尺度空间数据库建立中的关键技术与对策一文中提 出了建立多尺度空间数据库的四种技术策略，其中“初级尺度变化积累模型” 适用于矢量空间数据流媒体传输在服务器端的数据组织，详细介绍可以参考文 献i 刀。 艾波2 0 0 5 在其硕士论文网络地图矢量数据流媒体传输的研究一文中根 据艾廷华教授提出的“初级尺度变化积累模型”的服务器端数据组织策略，对 曲线和树状河网进行层次化数据组织，在o r a c l es p a t i a l 中对其进行存储，建 立多尺度空间数据库，并基于此实现了曲线和树状河网的流媒体传输。但是文 中并没有谈到如何解决流媒体传输过程产生的相交与自相交问题。关于此文的 详细论述可以参考文献【8 】。 1 3 关键技术策略 一般而言，为了实现矢量地图的渐进式传输，必须考虑以下几个方面的问 题：传输的粒度：数据的压缩与重构；数据的传输策略。 其中，传输的粒度是基础，只有选择好传输的粒度，才能构建相应的地图 数据压缩与重构算法。而数据的压缩与重构最为重要，这不仅是因为压缩算法 的实现本身有一定的难度，而且数据的压缩和重构算法效率直接影响渐进式传 输的效率。传输策略也是比较重要的，因为好的传输方式可以从传输底层提高 数据传输的效率。 1 3 1 传输的粒度 根据文献【8 】，地图数据可看作是在三个水平上的层次结构：主题层、要素 层、几何细节层。主题是具有相同特征( 语义、几何) 的要素集；要素是具有独立 地理意义的表达实体，是构成主题的基本单位：几何细节是几何表达上的划分的 西南交通大学硕士研究生学位论文 第一5 一页 结构体，是构成要素的基本单位，如构成道路目标的“弯曲”特征，构成面状 目标的三角形剖分单元， 在渐进式的传输过程中，数据表达发生变化的主体对象可以有三个层次： 主题层、要素层和几何细节，分别对应不同的变化粒度。 1 主题层：主题层上的变化粒度过于粗糙，而且在一般地图中不同主题层 之间难于根据重要性差距进行排序。在专题地图中，可以根据专题确定各主题 的重要性并排序，重要的主题层先传输。 2 要素层：在某一主题层下，要素可根据表达的重要性进行排序，与表达 尺度建立函数关系，在地图综合技术中通过“选取”算子实现，根据客户端的 显示尺度进行判断。满足条件的目标便显示出来，变化的对象以完整的目标图 形出现。 3 几何细节层：此层次上的变化粒度最为细腻，随着数据的叠加，目标的 几何细节有逐步演变的过程，接近于连续式的变化。几何细节层的多尺度数据 组织通过地图综合技术中的“化简”算子实现比如著名的d o u g l a s - p e u c k e r 曲 线化简算法。 主题层和要素层上的变化粒度都比较大，有可能忽略掉用户感兴趣的信息， 并且其实现也有很大的主观性，不利于计算机的自动实现。本文着重于几何细 节层次上的粒度变化，因为它不会忽略掉任何一个要素，并且利用计算机很容 易实现粒度交化的自动化 1 3 2 数据的压缩与重构 目前在矢量地图数据压缩方面主要有两类方法：一是降低坐标点的数据存 储精度；二是过滤掉地图数据中冗余的点( 通常对某一比例尺而言) 。 。 在对数据的精度要求不是很高的情况下，一般采用第一种方法。文献【9 】中 李琦教授等人提出了以下思路来压缩数据：( 1 1 将d o u b l e 型和f l o a t 型的坐标映射 ( 不是强制转换) 为i n t 型坐标；( 2 ) 对每一条弧段( 包括多边形边界和线状地物) 只 用两个i n t 型数据记录其起点坐标( x ，y ) ，其后续点坐标用相邻两点间的x 和y 的偏移量代替。这样就可以将数据量压缩到原来的l 8 左右。 大多数情况下采用第二种方法。而线状要素一般要占地图图形要素的8 0 以上( t h a p a ，1 9 8 8 ) 1 0 l ，所以关于第二种方法，本文主要研究线状要素的压缩算 法。对线状要素进行压缩，其目的是：使存储量最小，且保持线状要素的主要 特征。目前主要用到的压缩算法有：间隔取点法、d o u g l a s - p e u c k e r 算法、垂距 算法、角度算法等。这些都会在本文的第二章中详细加以介绍。 目前已有的研究成果中全部采用第二种方法对地图数据进行压缩，但只有 西南交通大学硕士研究生学位论文 第一6 一页 极少数研究成果能解决压缩后重构过程中产生的自相交问题或者相交问题。所 以需要研究一种算法，该算法能快速对矢量地图进行压缩并且重构后不会产生 自相交和相交现象。研究发现，采用基于s t r i p - t r e e 的线要素压缩和重构算法来 组织矢量地图数据能解决上述问题。本文的第三章会详细介绍基于s t r i p - t r e e 的 线要素压缩与重构算法。 1 3 3 传输方式 渐进式传输是服务器，客户端机制下空间数据多尺度表达的应用。本文第三 章将会详细介绍如何建立空闯数据的多尺度表达，至于传输策略将是本文第四 章研究的重点。关于传输策略的分类从应用层( 高层) 来看，可分为交互式和非交 互式从传输层( f 氐层) 来看，可分为自适应式和非自适应式。 交互式是指在客户端，用户根据已经恢复出来的地图判断是否满足自己的 要求，如果满意用户就可以主动地终止数据的传送，因此要传送的数据量是由 用户主观决定的，可以极大的提高传输效率。 非交互式是指服务器端根据用户当前的网络状况来决定传送的数据量。在 网络带宽比较小的情况下，服务器只需要传送占有地图大部分能量的低频信息。 而在网络带宽比较充裕的情况下，表示地图细节的高频信息也会被传送。 当然，这两种方式也并不是互斥。在交互方式下，如果用户一直没有任何 操作，那么服务器端就会接管，从而转化为非交互式。而在非交互方式下，如 果用户一旦有对地图的操作，那么操作方式将会由非交互式转化为交互式。 自适应式是指服务器和客户端根据当前网络带宽自主调整编码速率和解码 速率。具体而言，当网络带宽发生波动时候，客户端及时将这种波动特征反馈 到服务器，服务器接收到客户端时反馈信息后，按一定算法调整编码速率同时 客户端也调整解码速率和缓冲区的大小。这个调整过程都是自主的，不需要人 为的干涉，这样可以提高数据的传输效率。而在组播情况下，服务器端采用分 层编码技术，客户端根据自身情况选择相应的编码流节点连接，在传输的过程 中，自适应的调整连接的编码流节点。这样客户端可以充分的利用带宽，从而 提高数据的传输效率。本文第四章将会详细介绍这种方式。 非白适应式是指服务器和客户端按固有的速率进行编解码。这种方式实现 简单，适合网络带宽比较稳定的情况下数据的传输。但现实的网络条件是复杂 多样性的，网络带宽是经常发生波动的，这样非自适应方式下数据的传输效率 就大大降低。 西南交通大学硕士研究生学位论文第一7 页 1 4 本文的研究内容 矢量地图数据包括点、线、面三类不同的空间对象。线对象对象是由一系 列有序的点组成；面对象由一系列线对象首尾连接而成的一个闭合区域。因而 一个原始的矢量地图数据( 全分辨率数据) 可以被描述为： m a p u p o i n t i + u l i n e j + u s u r f a c e k l o j o k - o k 一协，弗】 p o i n t 一“) l i n e - v o v l ，啦，l 以以) s u r f a c e - v o v x ，吩吃，l ，v v o 由于面对象实际上也是由线对象组成，而点对象又比较简单，所以在研究 矢量地图数据时，本文侧重于线对象的研究。结合上- - d , 节中所谈到的关键技 术策略，本文所要实现的原型系统其主要功能可以描述为： 膨= 膨觋懒慨+ l 慨 其中m a p 。是全分辨率矢量地图数据，m a p o 是根据网络状况和用户需求所 计算出的最低分辨率的矢量地图数据。m a p o + v m a p l 是第一分辨率地图数据数 据，m a p o + v m a p l + m n a p 2 是第二分辨率地图数据，依次类推，最后可以得到全 分辨率的地图数据。现在的关键问题是如何得到各分辨率的数据，使得它们既 不需要重复存储，而且每一分辨率的地图数据又都是拓扑一致性的。另一方面， 在从m a p o + v m a p l 到m a p o + v m a p l + 、锄4 巩变化中，如何在现有网络条件下，比 较快得到这种增量方式的变化也是本文的一个研究重点。 基于以上考虑，本文的研究内容主要包括：介绍矢量地图渐进式传输的基 本概念，并分析其产生的根本原因；回顾并总结国内外关于此课题的研究现状， 指出尚且值得改进的地方：详细介绍线要素化简算法及其改进算法，结合本文 的应用目的对各算法的优缺点进行分析；重点阐述基于s t r i p - t r e e 的线要素图层 压缩与重构算法，该算法要能快速有效的对曲线图层进行压缩，理论上能输出 任意比例尺的地图数据并且不会产生相交和自相交现象；分析和研究渐进式传 输控制策略，重点研究在网络带宽波动的情况下，服务器和客户端如何自适应 调整传输速率，从而来达到较好的传输效果；应用基于s t i i p _ t k e 的线要素图层 西南交通大学硕士研究生学位论文第一8 一页 压缩与重构算法，实现一种基于c s 模式的矢量地图渐进式传输原型系统。该 系统能在维护地图质量的前提下，提高地图数据的网络发布效率。 1 5 论文的组织结构 本文在维护地图质量、提高空间数据发布效率的宗旨下，研究了矢量地图 渐进式传输的关键技术策略。重点研究矢量地图压缩与重构算法( 矢量曲线图层 压缩与重构算法) 、算法实现以及在此基础上实现的矢量地图渐进式传输原型系 统。本文的组织结构如下： 第一章，介绍了矢量地图渐进式传输的产生背景以及目前国内外关于此课 题的研究现状，详细阐述了矢量地图渐进式传输的重要性和必要性，重点讨论 了课题的关键技术策略和研究内容，最后给出了论文的组织结构 第二章，讨论了常见的线状要素的化简算法及其改进算法，结合课题的研 究目的分析了各线状要素化简算法的优缺点。最后重点介绍了如何解决d p 算 法产生的相交与自相交，该算法采用局部扩充策略消除相交和自相交线段。 第三章，介绍了s t r i p - t r e e 的基本概念，并在此基础上详细阐述了解决相交 和自相交的线状要素及线状要素图层压缩与重构算法。利用该算法可以快速有 效地对矢量地图数据进行压缩与重构，并且能有效地维护数据的质量。 第四章，详细介绍了渐进式传输控制的相关策略，主要包括服务器端的控 制策略和客户端传输控制策略。在介绍r t p 和r t c p 协议的基础上，然后详细 介绍了服务器端的缓升快降传输控制策略和分层编码策略。最后介绍了客户端 传输控制策略的协议实现方式和解码速率调整策略。 第五章，本章首先介绍了实验系统的总体结构，然后详细介绍了数据处理 模块的设计与实现，接着给出了系统的实现。最后重点介绍了实验的结果。实 验结果表明，本章设计与实现的渐进式传输实验系统能在维护地图质量的前提 下，提高地图数据的发布效率。 第六章，总结论文的工作，阐述了论文的不足并对以后矢量地图渐进式传 输的发展方向做出了展望。 西南交通大学硕士研究生学位论文第一9 - 页 第2 章线要素化简及其改进算法 在上一章第三小节中，本文提到为了实现渐进式传输，一个关键问题是如 何将占有地图数据量8 0 的线要素m a p a ，1 9 8 8 ) 1 1 0 】进行压缩具体而言，就是 需要寻找一种算法能对线要素建立树型层次结构，最上层的信息是线要素的一 个概略表示，越向下遍历越能更完整的表示线要素。另一个重要的问题是线要 素数据的重构，也就是说在建立树型层次结构后，当输出到任意一层时，重构 出来的线要素都不会出现自相交现象并且也不会与其他的线要素发生冲突。 基于以上考虑本章将详细介绍线要素化简的基本算法和其改进算法，其中 d - p 算法和避免自相交与相交的d - p 算法是介绍的重点，因为它们是第三章将 要阐述的算法的基础 2 1 线要素化简的基本算法 对线状要素进行化简，其目的是：使存储量最少，且保持线状要素的主要 特征。下面介绍常用的算法：间隔取点法【“、垂距限差法l 竭、角度限差法t 。3 1 和 d o u g l a s p e u c k e r 算法【1 4 1 。在介绍这些基本算法之前，有必要说明一点，在所有 的线状要素化简算法中，曲线数据集的首、末两点作为线状形态的支撑点必须 保留 2 1 1 间隔取点法 间隔取点法也称为n t h 算法，其思想非常简单，即在曲线上每隔n 个点后 取一个点，但首末点一定保留。图2 - 1 为每间隔两点取一点的效果： 图2 - 1 间隅取点法的化简效果( 应申，2 0 0 2 ) 图2 - 1 中虚线表示原曲线，实线表示采用间隔取点法化简后的特征曲线。 西南交通大学硕士研究生学位论文第一1 0 _ 页 这种方法可以大量压缩数据，但往往不能保留曲线关键特征。所以这种方法压 缩出来的数据无法满足本文的需求，故不予考虑。 2 1 2 垂距限差法 垂距限差法是一个比较简单的算法，它的基本思想是：事先给定一个阈值 d ( 限差) ，然后依次对构成曲线的中间点( 首、末点以外的其他点) 计算其到与其 相邻的前后两点连线的距离，若该距离大于阈值，保留该点，否则删除。 以图2 - 2 所示曲线为例，曲线由点列0 , o ，p 1 ，l ，p 9 ) 组成，因点p l 到p 。以连 线的距离大于阈值d ，则矶保留；因巩到p t p 3 连线的距离小于d ，则删除p 2 ； 对儿点，考虑它到p 1 矶连线的距离，因为m 己经被删除，不能用作判断依据； 依次判断各点，直到末点，最终保留点列为0 , o ，p i ，p 3 ，p ，p 6 ，p ，内) 。 图2 - 2 垂匿限差法的简化过程( 郭仁忠。1 9 9 7 ) 图2 2 中虚线为辅助线，实线为原曲线，黑线为采用垂距限差法化简后所 得到的曲线。该算法思想简单，实现也很容易，但是也不能很好的保留曲线的 关键点。并且如果将曲线反向，所得到的化简结果也有可能不同。由于这种方 法不能保留曲线的关键点，无法满足本文的需求，所以也不予考虑。 2 1 3 角度限差法 角度限差法是由m c m a s t e r 提出的，其基本思想是：事先给定一个角度限差 0 ，若n 为最近保留的点，当前点为只+ 1 ，下一个点为a + 2 ，则如果ap j 。和只a + ： 之间的夹角小于口，点p f ，被删除，否则保留。如果只+ ，被保留，下一步计算 a + 盛+ ：和讳+ 。 ，之闯的夹角，以确定只+ ：的取舍；如果p t + ：被删除，则下一步 计算a a + ：和只马+ ，的夹角以确定a + ：的取舍，依椿类推直至曲线终点。如图2 - 3 所示： 西南交通大学硕士研究生学位论文第一1 1 一页 p p i 2p i 图2 3 角度限差法化倚过程( m c m a s t e r , 1 9 8 7 ) 图2 - 3 中，黑线为采用角度限差法化简后得到的曲线。该算法虽然能保证 删去弯曲较小的点，但对于平缓曲线其保形性较差，没有得到广泛应用。 2 1 4d o u g l a s - p e u c k e r d o u g l a s p e u c k e r 算法是由d d o u g l a s 和t p e u c k e r 于1 9 7 3 年提出的，简称 d p 算法，是目前公认的线状要素化简经典算法。该算法的基本思想是：事先 给定阈值d ，在曲线首末两点之间连一条直线，依次计算中间点到该线段的距 离，找出最大距离点，并判断该距离是否小于6 ，若是，则舍去该曲线的所有 中间点；否则，保留该点，并以该点为界，将曲线分为两部分，对这两部分重 复使用上述操作。 以图2 - 4 所示为例，曲线由点列( p 0 ，p 1 ，l ，内) 表示，首先在p o 与p 9 之间连 一直线，计算得到离该直线最远的点( 如图所示为p 3 ) 。如果该点到直线的距离 不大于阙值，则和岛之间的所有点全部删除，用一条直线p 。m 来代替原曲线， 化简结束；如果该点到直线的距离大于阈值，则保留该点，并将曲线以该点为 限分成两段，在图2 - 4 中分为( p o ，a ，l ，办) 和( p 3 ，内，l ，p 9 ) ，将( p o ，a ，l ，乃) 和 ( 乃，p 4 ，l ，p 9 ) 分别作为独立曲线重复上述步骤。 图2 - 4d o u g l a s - p e u c k e r 化简算法( d o u g l a sa n dp e u c k e r , 1 9 7 3 ) 西南交通大学硕士研究生学位论文第一1 2 - 页 从图2 - 4 的化简过程可以看出，d o u g l a s p c u c k e r 算法化简结果具有明显的 层次结构，且随着层数的不断加深，曲线的细节描述越来越详细。通过分析知 道d p 算法能满足本文的需求，所以在对线要素进行压缩的时候，本文采用该 算法。 2 2 基本算法存在的问题 采用线要素基本化简算法对线状图层的曲线进行化简操作时，在某一化简 比例下是可能造成输出弧段自相交以及弧段间的相交，从而产生拓扑错误，而 且，造成这种错误的原因与具体采用的线化简算法以及化简比例的定义方法是 无关的，即原本不自相交的弧段在省略若干节点后总存在自相交的可能，原本 不相交的两条相关弧段在省略若干节点后总存在相交的可能。 p 。、t 。 圈2 - 5 线化简后产生的自相交 如图2 - 5 左侧所示，曲线l ( 见，p 2 ，a ，) 的数据量为1 1 ，采用d - p 算法进 行化简，在某一阈值下输出曲线为l ( p 1 ，见，p 6 ，p 9 ，a 。) ，出现了自相交的拓扑错 误。同样的，这种错误也可能发生在两条线之间，出现相交的现象。 线状要素的相交和自相交问题在地图自动化简体系中是一个极为重要的问 题。在地图中，每一条线都代表现实中的地物，例如铁路线、水系、等高线等， 若在绘制地图时发生相交情况，也就代表在实际中或者铁路线，或者水系在某 点相会，这与实际情况不相符现在我们面临的问题是产生这种错误的原因是 什么? 仅仅是采用d - p 算法才产生这种错误，还是所有的化简算法都会产生争 一旦发生这种错误，如何解决? 通过分析，发现造成这种错误的原因与具体采用的线化简数据结构以及算 法本身无关的。其根本原因在于：线要素化简算法是针对保持线的几何形态设 计的，而没有考虑到它的空间关系。事实上，任何一种化简算法只要在化简过 程中没有考虑到图形的空间关系就必然存在相交的可能，对于单根线而言就有 西南交通大学硕士研究生学位论文第一1 3 - 页 自相交的可能。 2 3 相关改进算法 鉴于基本算法化简后重构容易出现相交与自相交的问题，通过长期的研究， 又出现了许多相关的改进算法。这些算法总体上分为两类：一类是提出新的算 法，从根本上解决相交或者自相交的问题；另类是，对现有的算法加以改进， 从而避免产生相交或者自相交的现象 2 3 1 基于自然规律的综合算法 人们在观察物体时，随着视距的增加，看到的物体越来越小，物体的细节 也越来越少，如果将所看的物体比作是化简的对象，这就是自然界中可以看到 的化衙操作。任意给定一个比例尺，对于地图综合要素而言，必然存在个最 小的范围，在这个范围内所有的细节信息都将失去。例如，如果给出特定的显 示方式，随着地图比例尺的减小，一个较大的多边形会变成小多边形；当达到 某个边界尺寸时会仅剩一个点；更进一步，点也会从视野中消失。正是基于这 种简单的自然规律，z h i l i n i j 和s t a l l o p e n s h a w 提出了基于“客观综合的自然规 律”的线状要素综合算法。 根据文献【1 5 】，在l i o p e m h a w 算法中最关键的是要确定一个最小可视范 围。该范围一般是以某点为中心的圆形区域，其计算公式如下； e = s , x z ) x ( 1 一s 婵) ( 2 - n 式中：e 为实地量测的最小可视范围的直径；墨为化简后的地图比例因子；d 为地图尺寸上的最小可视范围的直径；s ，为化简前的地图比例因子。 按照地图尺寸，通常选择0 4 m m 作为最小可视范围的半径，至于该值是否 是最佳的可视范围不在本文研究范围内，同时也有待于在将来的研究中验证。 该算法如下： ( 1 ) 确定最小可视范围的半径，由公式( 2 1 ) 得到； ( 2 ) 确定最小可视范围的位置。图2 - 6 的a ) 中，a 和b 分别是待化简曲线的 起点和末点，以a 为中心，以最小可视范围的直径为半径，确定一个较大的圆 形区域，该圆与曲线交于点只与p 。，之间，设该点为c ；以a c 为直径，确定 圆形区域，该圆即为要确定的最小可视范围，图中点1 为该圆的中心； ( 3 ) 以最小可视范围的中心表示它所覆盖的区域；点1 的位置由a 和c 的坐 西南交通大学硕士研究生学位论文第一1 4 _ 页 标计算确定； ( 4 ) 沿着曲线顺序继续确定最小可视范围。新确定的相交点总是作为下一轮 较大圆形区域的中心，转( 2 ) ；重复操作，直到整条曲线化简完毕，化简结果如 图3 6 中幻中虚线。 帕曲蛙让俺过程 算珐瓤奢 图2 - 6l i o p e l u h a w 算法t t , l 弛a n ds t a no p e n s h w 。1 9 9 2 ) 该算法可以避免曲线化简产生的自相交情况，但正如i jz h i l i n 在原文中所 述，该算法的一个缺点是：在确定最小可视区域时，曲线可能有好几个部位与 圆相交，特别是在瓶径部位( 例图2 - 6 中b ) 图所示) 。显然我们并不希望取一个交 点，而删除另一个交点。并且该算法也无法解决曲线间的相交问题。 2 3 2 纯几何渐进式化简算法 郭庆胜在对渐进式线状要素化简算法研究的基础上，提出了纯几何的渐进式 化简算法i “，具体步骤如下所示： ( 1 ) 计算构成曲线的点集的所有相邻三个点构造的三角形的面积，并排序； ( 2 ) 判断最小的三角形内是否有当前线的点集的元素，若有，则进行第( ( 3 ) 。步；若无，则删除该三角形，返回第( 1 ) 步，用新的- 点集代替老的点集。若最小 的三角形面积大于阈值，则进行第( 4 ) 步； ( 3 ) 判断能否删除其相邻的两个三角形中的任一个，条件是：两个相邻三角 形中被删除的那一个三角形内无当前线的点，删除面积小的三角形。当条件不 能满足时，此三角形暂时保留，并记录下这三个相邻点号，这些点号都是最原 始的点号，然后把次小的三角形看成最小三角形，返回第( 2 ) 步； ( 4 ) 对已经记录下来的难处理的三角形判断其是否存在，条件是：当前线的 点集中是否还有连续的三个点号完全同记录下来的三角形点号相同，若相同， 则保留这一待处理的三角形，已记录下来的其他三角形已经在化简过程中自动 消失： ( 5 ) 对难处理的三角形进行移位处理； ( 6 ) 判断己化简的线有无自相交现象，若无，则结束；若有，则必须提示自 西南交通大学硕士研究生学位论文第- 1 5 - 页 相交区域，由用户判别并处理，结束化简过程。 该算法虽然优于从整体到局部的综合方法，能较好地控制图形的自相交问 题，但在化简过程中有时会删除某些特征点，且从理论上还没有完全解决因移 位而进一步产生的自相交问题。也就是说，它不能自身完全解决移位后复杂图 形的自相交问题。 2 3 3 再分区式化简算法 该算法于1 9 9 5 年由m a r kd cb c r g ，m a r v 姐k r e v c l d 和s c c f a ns c h i r r a 提出， 他们认为一个算