《《地理信息系统》第五章空间数据处理.ppt》由会员分享，可在线阅读，更多相关《《地理信息系统》第五章空间数据处理.ppt（128页珍藏版）》请在三一办公上搜索。
1、第五章 空间数据的处理,空间数据的坐标变换；空间数据结构的转换；矢量数据的图形编辑；拓扑关系的自动建立；空间数据压缩与重分类空间数据的内插方法；数字高程模型的生成,空间数据的变换即空间数据坐标系的变换,其实质是建立两个平面点之间的一一对应关系，包括几何纠正和投影转换，它们是空间数据处理的基本内容之一。对于数字化地图数据，由于设备坐标系与用户确定的坐标系不一致，以及由于数字化原图图纸发生变形等原因，需要对数字化原图的数据进行坐标系转换和变形误差的消除。有时，不同来源的地图还存在地图投影与地图比例尺的差异，因此还需要进行地图投影转换和地图比例尺的统一。,5.1 空间数据的坐标变换,1、比例尺变换：
2、乘系数2、变形误差改正：通过控制点利用高次变换、二次变换和仿射变换加以改正3、坐标旋转和平移 即数字化坐标变换，利用仿射变换改正。4、投影变换：三种方法。,几何变换,返回,5.1 空间数据的坐标变换,5.1.1 几何纠正：为了实现数字化数据的坐标系转换和图纸变形误差的改正，现有的GIS软件一般具有仿射变换、相似变换、二次变换等几何纠正功能。,5.1 空间数据的坐标变换,其中A、B代表二次以上高次项之和。上式是高次曲线方程，符合上式的变换称为高次变换。式中有12个未知数，所以在进行高次变换时，需要有6对以上控制点的坐标和理论值，才能求出待定系数。,1、高次变换,2、二次变换 当不考虑高次变换方程
3、中的A和B时，则变成二次曲线方程，称为二次变换。二次变换适用于原图有非线性变形的情况，至少需要5对控制点的坐标及其理论值，才能解算待定系数。,5.1 空间数据的坐标变换,3、仿射变换：实质是两坐标系间的旋转变换。设图纸变形引起x,y两个方向比例尺不同，当x,y比例尺相同时，为相似变换。,特性：直线变换后仍为直线；平行线变换后仍为平行线；不同方向上的长度比发生变化。求解上式中的6个未知数，需不在一直线上的3对已知控制点，由于误差，需多余观测，所以，用于图幅定向至少需要四对控制点。,5.1 空间数据的坐标变换,仿射变换举例,它的主要特征为：同时考虑到x和y方向上的变形，因此纠正后的坐标数据在不同方
4、向上的长度比将发生变化。,三、地图投影变换,1、解析变换法1）反解变换法(又称间接变换法),假定原图点的坐标为x,y(称为旧坐标)，新图点的坐标为X，Y(称为新坐标)，则由旧坐标变换为新坐标的基本方程式为：,2）正解变换法(又称直接变换法),5.1 空间数据的坐标变换,2、数值变换法,利用若干同名数字化点（对同一点在两种投影中均已知其坐标的点），采用插值法、有限差分法或多项式逼近的方法，即用数值变换法来建立两投影间的变换关系式。,例如，采用二元三次多项式进行变换:,通过选择10个以上的两种投影之间的共同点，并组成最小二乘法的条件式，进行解算系数。,5.1 空间数据的坐标变换,3、数值解析变换法
5、,当已知新投影的公式，但不知原投影的公式时，可先通过数值变换求出原投影点的地理坐标，然后代入新投影公式中，求出新投影点的坐标。即：,5.1 空间数据的坐标变换,投影变换：,地图投影转换斜轴等面积方位投影,栅格、矢量结构相互转换,矢量结构与网格结构的相互转换，是地理信息系统的基本功能之一，目前已经发展了许多高效的转换算法；但是，从栅格数据到矢量数据的转换，特别是扫描图像的自动识别，仍然是目前研究的重点,5-2 空间数据结构转换,对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度变换问题，不存在太大的技术问题。线实体的矢量结构由一系列坐标对表示，在变为栅格结
6、构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到。线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似，因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换。,5-2 空间数据结构转换,5.2.1 矢量格式向栅格格式的转换,矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码,例：矢量到栅格转换,矢量格式向栅格格式的转换算法,内部点扩散算法：该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界
7、上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。,特点：扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。,矢量格式向栅格格式的转换算法,复数积分算法：对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分。对某个多边形，如果积分值为2i，则该待判点属于此多边形，赋以多边形编号，否
8、则在此多边形外部，不属于该多边形。,特点：算法可靠，但极费机时。,矢量格式向栅格格式的转换算法,射线算法：射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部；如为奇数次，则待判点在该多边形内部（如图）。,矢量格式向栅格格式的转换算法,射线算法的优缺点：运算量大；射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除（如图）。,矢量格式向栅格格式的转换算法,扫描算法：是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。扫描算法省去了计算射线与多边形边
9、界交点的大量运算，大大提高了效率。,特点：占用内存较大；扫描线与多边形相交的各种特殊情况仍然存在。,矢量格式向栅格格式的转换算法,边界代数算法（BAF-Boundary Algebra Filling）：是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。,单个多边形的转换,由多边形边界上某点开始顺时针搜索边界线，当边界上行时（图a），位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时（图b），该边界左边（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。,矢量格式向栅格格式的转换算法,多个多边形的转换,事实上
10、，每幅数字地图都是由多个多边形区域组成的，如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，可以证明，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号左多边形编号）。,矢量格式向栅格格式的转换算法,两个多边形的转换上行：左右下行：右左,边界代数法的特点：与前述其他算法的不同之处，在于它不是逐
11、点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过简单的加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而不需要考虑边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。,5.2.2 栅格格式向矢量格式的转换,多边形栅格格式向矢量格式转换就是提取以相同的编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示由多个小直线段组成的矢量格式边界线的过程。,从栅格单元转换为几何图形的过程为矢量化；（一）要求（矢量化过程应保持）：1）栅-矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；2）转换实体保持正确的外形。（二）
12、方法方法一：实际应用中大多数采用人工矢量化法，如扫描矢量化(该法工作量大，成为GIS数据输入、更新的瓶颈问题之一)。方法二，程序转化转换（全自动或半自动）过程为：,1、边界提取2、二值化 3、二值图像的预处理,4、细化:1）剥皮法 2)骨架法5、跟踪 6、拓扑化,5.2.2 栅格格式向矢量格式的转换,方法二，程序转化转换（全自动或半自动）,栅格格式向矢量格式转换通常包括以下四个基本步骤：多边形边界提取：采用高通滤波将栅格图像二值化或以特殊值标识边界点；边界线追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段；拓扑
13、关系生成：对于矢量表示的边界弧段数据，判断其与原图上各多边形的空间关系，以形成完整的拓扑结构并建立与属性数据的联系；去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余；搜索结果，曲线由于栅格精度的限制可能不够圆滑，需采用一定的插补算法进行光滑处理，常用的算法有：线形迭代法；分段三次多项式插值法；正轴抛物线平均加权法；斜轴抛物线平均加权法；样条函数插值法。,栅格格式向矢量格式的转换,多边形栅格转矢量的双边界搜索算法（DBDF-Double Boundary Direct Finding）,(1)边界点和结点提取：边界点的6种情形:如果窗口内四个栅格有且仅
14、有两个不同的编号，则该四个栅格表示为边界点.,结点的8种情形:如果窗口内四个栅格有三个以上不同编号，则标识为结点（即不同边界弧段的交汇点），保持各栅格原多边形编号信息。,双边界搜索算法,（2）边界线搜索与左右多边形信息记录：边界线搜索是逐个弧段进行的，对每个弧段由一组已标识的四个结点开始，选定与之相邻的任意一组四个边界点和结点都必定属于某一窗口的四个标识点之一。首先记录开始边界点的两个多边形编号，作为该弧段的左右多边形，下一点组的搜索方向则由进入当前点的搜索方向和该点组的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。,栅格格式向矢量格
15、式的转换,双边界搜索算法,（3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上的连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为上多余的，予以去除。多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为直线时），多余点去除算法可大量去除多余点，减少数据冗余。,双边界搜索算法的优点双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率。,图形编辑是一交互处理过程，GIS具备的图形编辑功能的要求是：1）具有友好的人机界面，即操作灵活、易于理解、响应
16、迅速等；2）具有对几何数据和属性编码的修改功能，如点、线、面的增加、删除、修改等；3）具有分层显示和窗口操作功能，便于用户的使用。,第五章 空间数据处理,图形编辑又叫数据编辑、数字化编辑，是指对地图资料数字化后的数据进行编辑加工，其主要目的是在改正数据差错的同时，相应地改正数字化资料的图形。,5.3 矢量数据的图形编辑,数据检查与清理数据的检查：指拓扑关系的检查。包括检查结点是否匹配、是否存在悬挂线（线段过长或过短；伪结点；线段的断裂）；多边形是否闭合（多边形裂口）等。数据清理：用自动的方法清除空间数据的错误。,5.3 矢量数据的图形编辑,一、常见问题线段过长或过短,5.3 矢量数据的图形编辑
17、,矢量图形的编辑,一、常见问题伪结点,由且仅有两个线目标相关联的结点成为假结点。,未吻合的结点,多边形裂口,矢量图形的编辑,一、常见问题多边形问题,“碎屑”多边形或“条带”多边形（Sliver Polygon）：一般由于重复录入引起，由于前后两次录入同一条线的位置不可能完全一致，造成了“碎屑”多边形。另外，由于用不同比例尺的地图进行数据更新，也可能产生“碎屑”多边形。,矢量图形的编辑,不正规多边形是由于输入线时，点的次序倒置或者位置不准确引起的，在进行拓扑生成时，同样会产生“碎屑”多边形。,矢量图形的编辑,二、编辑操作,1）结点吻合(Snap)或称结点匹配、结点咬合，结点附和。方法：A、结点移
18、动，用鼠标将其它两点移到另一点；B、鼠标拉框，用鼠标拉一个矩形，落入该矩形内的结点坐标通过求它们的中间坐标匹配成一致；C、求交点，求两条线的交点或其延长线的交点，作为吻合的结点；D、自动匹配，给定一个吻合容差，或称为咬合距，在图形数字化时或之后，将容差范围内的结点自动吻合成一点。,一般，若结点容差设置合理，大多数结点能够吻合在一起，但有些情况还需要使用前三种方法进行人工编辑。,1、结点的编辑,5.3 矢量数据的图形编辑,2）结点与线的吻合,编辑的方法：A、结点移动，将结点移动到线目标上。B、使用线段求交；C、自动编辑，在给定容差内，自动求交并吻合在一起。,在数字化过程中，常遇到一个结点与一个线
19、状目标的中间相交。由于测量或数字化误差，它不可能完全交于线目标上，需要进行编辑，称为结点与线的吻合。,3）需要考虑两种情况A、要求坐标一致，而不建立拓扑关系；如 高架桥（不需打断，直接移动）B、不仅坐标一致，且要建立之间的空间关联关系；如 道路交叉口（需要打断）,5.3 矢量数据的图形编辑,4）清除假结点（伪结点）,有些系统要将这种假结点清除掉（如ARC/INFO），即将目标A 和B合并成一条，使它们之间不存在结点;但有些系统并不要求清除假结点，如Geostar,因为它们并不影响空间查询、分析和制图。,由且仅有两个线目标相关联的结点成为假结点。,5.3 矢量数据的图形编辑,2、图形编辑,包括用
20、鼠标增加或删除一个点、线、面实体，移动、旋转一个点、线、面实体。1）删除和增加一个顶点 删除顶点，在数据库中不用整体删除与目标有关的数据，只是在原来存储的位置重写一次坐标，拓扑关系不变。增加顶点，则操作和处理都要复杂。不能在原来的存储位置上重写，需要给一个新的目标标识号，在新位置上重写，而将原来的目标删除，此时需要做一系列处理，调整空间拓扑关系。2）移动一个顶点 移动顶点只涉及某个点的坐标，不涉及拓扑关系的维护，较简单。3）删除一段弧段 复杂，先要把原来的弧段打断,存储上原来的弧段实际被删除，拓扑关系需要调整和变化.,j,k,j,k,a,b,L3,L1,L2,5.3 矢量数据的图形编辑,3、数
21、据检查与清理,数据检查指拓扑关系的检查，结点是否匹配，是否存在悬挂弧段，多边形是否封闭，是否有假结点。要求系统能将有错误或不正确的拓扑关系的点、线和面用不同的颜色和符号表示出来，以便于人工检查和修改。,数据清理则是用自动的方法清除空间数据的错误.例如给定一个结点吻合的容差使该容差范围内的结点自动吻合在一起，并建立拓扑关系。给定悬挂弧段容差，将小于该容差的短弧自动删除。在Arc/info中用Data Clean 命令，在Geostar中选择整体结点匹配菜单。,4、撤消与恢复编辑 Undo,Redo功能是必要的。但功能的实现是困难的。当撤消编辑，即恢复目标，要恢复目标的标识和坐标、拓扑关系。这一处
22、理过程相当复杂.因此，有些GIS不在图形编辑时实时建立和维护拓扑关系，如Arc/Info等，而在图形编辑之后，发Clean 或Build命令重新建立拓扑关系。这样，在每次进行任何一次编辑，都要重新Clean 或Build，对用户不便。,5.3 矢量数据的图形编辑,三、关键算法,可设一捕捉半径D(通常为35个象素，这主要由屏幕的分辩率和屏幕的尺寸决定)。,1、点的捕捉,设光标点为S(x,y)，某一点状要素的坐标为A(X，Y),若S和A的距离d小于D则认为捕捉成功，即认为找到的点是A，否则失败，继续搜索其它点。,乘方运算影响了搜索的速度，因此，把距离d的计算改为：,捕捉范围由圆改为矩形，这可大大加
23、快搜索速度。,5.3 矢量数据的图形编辑,2、线的捕捉,设光标点坐标为S(x,y)，D为捕捉半径，线的坐标为(x1,y1),(x2,y2),(xn,yn)。通过计算S到该线的每个直线段的距离d。.若min(d1,d2,dn-1)D，则认为光标S捕捉到了该条线，否则为未捕捉到。加快线捕捉的速度的方法：1）在实际的捕捉中，可每计算一个距离di就进行一次比较，若diD，则捕捉成功，不需再进行下面直线段到点S的距离计算了。2）把不可能被光标捕捉到的线，用简单算法去除。3）对于线段也采用类似的方法处理。4）简化距离公式：点S(x,y)到直线段(x1,y1),(x2,y2)的距离d的计算公式为：,简化为：
24、,3、面的捕捉,实际上就是判断光标点S(x,y)是否在多边形内，若在多边形内则说明捕捉到。判断点是否在多边形内的算法主要有垂线法或转角法。垂线法的基本思想是从光标点引垂线(实际上可以是任意方向的射线)，计算与多边形的交点个数。若交点个数为奇数则说明该点在多边形内；若交点个数为偶数，则该点在多边形外。加快速度的方法：1）找出该多边形的外接矩形，若光标点落在该矩形中，才有可能捕捉到该面，否则放弃对该多边形的进一步计算和判断。2）对不可能有交点的线段应通过简单的坐标比较迅速去除。3）运用计算交点的技巧。,5.3 矢量数据的图形编辑,一、点线拓扑关系的自动建立,a1,a2,N1,N2,N3,N4,a3
25、,a1,a2,N1,N2,N3,a1,a2,N1,N2,N3,N4,a3,a4,(b),(a),(c),结点-弧段表,弧段-结点表,1、在图形采集和编辑中实时建立,2、在图形采集和编辑之后自动建立，其基本原理与前类似。,5-4 拓扑关系的自动建立,二、多边形拓扑关系自动建立,1、链的组织1）找出在链的中间相交的情况，自动切成新链；2）把链按一定顺序存储，并把链按顺序编号。2、结点匹配1）把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。2）对结点顺序编号。3、检查多边形是否闭合通过判断一条链的端点是否有与之匹配的端点来进行.,多边形不闭合的原因：1）由于结点匹配限差的问题，造成应
26、匹配的端点未匹配；2）由于数字化误差较大，或数字化错误，这些可以通过图形编辑或重新确定匹配限差来确定。3）还可能这条链本身就是悬挂链，不需参加多边形拓扑，这种情况下可以作一标记，使之不参加下一阶段拓扑建立多边形的工作。,5-4 拓扑关系的自动建立,4、建立多边形,1）概念a、顺时针方向构多边形：指多边形是在链的右侧。b、最靠右边的链：指从链的一个端点出发，在这条链的方向上最右边的第一条链，实质上它也是左边最近链。a的最右边的链为d,当多边形由顺时针方向构成时，面积为正；反之，面积为负。,二、多边形拓扑关系自动建立,5-4 拓扑关系的自动建立,c、多边形面积的计算,2）建立多边形的基本过程,1
27、顺序取一个结点为起始结点，取完为止；取过该结点的任一条链作为起始链。2 取这条链的另一结点，找这个结点上，靠这条链最右边的链，作为下一条链。3 是否回到起点：是，已形成一多边形，记录之，并转4；否，转2。4取起始点上开始的，刚才所形成多边形的最后一条边作为新的起始链，转2；若这条链已用过两次，即已成为两个多边形的边，则转1。,例：1从P1开始，起始链定为P1P2,从P2点算起，P1P2最右边的链为P2P5；从P5算起，P2P5最右边 的链为P5P1,.形成的多边形为P1P2P5P1。2从P1开始，以P1P5为起始链，形成的多边形为P1P5P4P1。3从P1开始，以P1P4为起始链,形成的多边形
28、为P1P4P3P2P1。4 这时P1为结点的所有链均被使用了两次，因而转向下一个结点P2，继续进行多边形追踪，直至所有的结点取完。共可追踪出五个多边形，即A1、A2、A3、A4、A5。,5-4 拓扑关系的自动建立,5、岛的判断,找出多边形互相包含的情况.1、计算所有多边形的面积。2、分别对面积为正的多边形和面积为负的多边形排序。3、从面积为正的多边形中，顺序取每个多边形，取完为止。若负面积多边形个数为0，则结束。4、找出该多边形所包含的所有面积为负的多边形，并把这些面积为负的多边形加入到包含它们的多边形中，转3。正面积多边形包含的负面积多边形是关键.1、找出所有比该正面积多边形面积小的负面积多
29、边形。2、用外接矩形法去掉不可能包含的多边形。即负面积多边形的外接矩形不和该正面积多边形的外接矩形相交或被包含时，则不可能为该正面积多边形包含。3、取负面积多边形上的一点，看是否在正面积多边形内，若在内，则被包含；若在外，则不被包含。6、确定多边形的属性多边形以内点标识。内点与多边形匹配后,内点的属性常赋于多边形.,单多边形被追踪两次,p1,p2,p3,p1,p2,p3,-p1,-p2,-p3,5-4 拓扑关系的自动建立,一、图形的裁剪-开窗处理,1、方式：正窗：提取窗口内的数据。开负窗：提取窗口外的数据子集。矩形窗和多边形窗。2、算法：包括点、线、面的窗口裁剪-计算机图形学。而不规则多边形开
30、窗-相当于多边形叠置处理。,5-5 图形的裁剪、合并和图幅接边,由于空间数据采集的误差和人工操作的误差，两个相邻图幅的地图的空间数据在结合处可能出现逻辑裂隙与几何裂隙。逻辑裂隙指的是当一个地物在一幅图的数据文件中具有地物编码A，而在另一幅图的数据文件中却具有地物编码B，或者同一物体在这两个数据文件中具有不同的属性信息，如公路的宽度、等高线的高程等。几何裂隙指的是由数据文件边界分开的一个地物的两部分不能精确地衔接。图幅接边：在GIS中，需要把单独数字化的相邻图幅的空间数据在逻辑上和几何上融成一个连续一致的数据体，这就是GIS中的图幅接边（图形拼接）问题。图幅接边包括几何接边和逻辑接边。,二、图幅
31、数据边沿匹配处理,5-5 图形的裁剪、合并和图幅接边,图幅接边形成无缝数据库,几何裂缝：指由数据文件边界分开的一个地物的两部分不能精确地衔接。-几何接边逻辑裂缝：同一地物地物编码不同或具有不同的属性信息，如公路的宽度，等高线高程等。-逻辑接边,2、几何接边,1、识别或提取相邻图幅。-要求图幅编号合理,5-5 图形的裁剪、合并和图幅接边,图形合并 一幅图内的多层数据合并在一起;或将相邻的多幅图的同一层数据合并.涉及到空间拓扑关系的重建。对于多边形，由于同一个目标在两幅图内已形成独立的多边形，合并时，需去除公共边界，属性合并，具体算法，删去共同线段。实际处理过程是先删除两个多边形，解除空间关系后，
32、删除公共边，再重建拓扑。,二、图幅数据边沿匹配处理,3、逻辑接边,1）检查同一地物在相邻图幅的地物编码和属性值是否一致，不一致，进行人工编辑。2）将同一地物在相邻图幅的空间数据在逻辑上连在一起。,图3,图2,图1,总目标文件,a、索引文件，建立双向指针。,b、关键字，空间操作的方法。,逻辑接边,二、图幅数据边沿匹配处理,一、数据压缩,矢量数据的压缩1、DouglasPeucker,5-6 空间数据压缩与重分类,图形显示输出,数据存储,数据压缩,光滑,矢量数据压缩(去冗余/抽稀)栅格数据压缩,压缩效果好，但必须在对整条曲线数字化完成后才能进行，且计算量较大；,2、垂距法,每次顺序取曲线上的三个点
33、，计算中间点与其它两点连线的垂线距离d，并与限差D比较。若dD，则中间点去掉；若dD，则中间点保留。然后顺序取下三个点继续处理，直到这条线结束。,3、偏角法 4、间隔取点法,压缩算法好，可在数字化时实时处理，每次判断下一个数字化的点，且计算量较小；,5-6 空间数据压缩与重分类,二、曲线光滑（拟合）,是假象曲线为一组离散点，寻找形式较简单、性能良好的曲线解析式。,插值方式：曲线通过给定的离散点。如拉格朗日插值，三次样条曲线逼近方式：曲线尽量逼近给定离散点。如贝塞尔和B样条曲线。,5-6 空间数据压缩与重分类,栅格数据的压缩,栅格数据编码栅格数据的直接编码方法栅格数据的压缩编码方法,栅格数据的编
34、码方法,空间数据编码是空间数据结构的实现，即将根据地理信息系统的目的和任务所搜集的、经过审核了的地形图、专题地图和遥感影像等资料按特定的数据结构转换为适合于计算机存储和处理的数据的过程。由于地理信息系统数据量极大，一般采用压缩数据的编码方式以减少数据冗余。,栅格数据的压缩,（一）栅格数据直接编码,这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行从左到右而偶数行从右向左记录
35、，为了特定目的还可采用其他特殊的顺序。,直接编码可分为：显式存储:每个栅格同时储存其行号、列号及属性值。（I1,J1,A1，In,Jn,An,)隐式存储：隐含行、列号，顺序存储栅格属性值。(A1,A2,A3,An,),（二）栅格数据压缩编码,压缩目的：以尽可能少的数据量记录尽可能多的信息压缩类型：信息无损压缩：是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息 信息有损压缩：是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。,栅格数据压缩编码方法之一,链码（Chain Codes）：弗里曼链码Freeman或边界链码，适用
36、于对曲线和多边形边界进行编码。方法：八方向定义：东0，东南l，南=2，西南3，西4，西北5，北6，东北7等八个基本方向。编码：线标号，起始行，起始列，属性码，方位1，方位2，方位n,线标号，起始行，起始列，属性码，方位1，方位2，方位n,弗里曼链码练习1,弗里曼链码练习2,确定原点为像元(10，1)，则该多边形边界按顺时针方向的链式编码为：10，l，7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。,链式编码的特点：链式编码对多边形和线状地物的表示具有很强的数据压缩能力，且具有一定的运算功能，
37、如面积和周长计算等，探测边界急弯和凹进部分等都比较容易；缺点是对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。,栅格数据压缩编码方法之二,游程编码（Run-Length Codes）,基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。,游程：一行（列）中，属性相同的连续栅格，称为一个游程。,根据数据结构的不同，可分为：游程长度编码：Ci属性，Li 游程的连续长度。游程终止编码：Ci属性，Li 游程的终止点列号。,思路：将栅
38、格矩阵中的行序列 x1,x2,x3,xn 映射成整数对序列。即：(c1,l1),(c2,l2),(cn,ln).,游程长度编码练习,游程长度编码游程终止编码,游程编码的优、缺点,游程编码的优点：在对“多对一”的结构，即许多像元同属一个地理属性值的情况下大大改善了传统编码的存储情况。游程长度编码栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索、叠加、合并等操作。这种编码方法最适合于小型计算机，同时也减少了栅格数据库的数据输入量。游程编码的缺点：计算期间的处理和制图输出处理工作量都有所增加。,栅格数据压缩编码方法之三,块码（Block Codes）,块码是游程长度编码扩展到二维的情况，采用
39、方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。即(I1,J1,L1,C1，.，I2,J2,L2,C2，.),块码 示例,(1,1,2,4,1,3,1,4,1,4,2,2,2,3,1,4,3,1,1,4,3,2,1,4,3,3,2,2,3,5,1,2,4,1,2,1,4,5,1,2,5,3,1,3,4,4,1,2,5,5,1,2),压缩率：随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低,块码 的优缺点,块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须将
40、其解码，转换为基本栅格结构才能顺利进行。,栅格数据压缩编码方法之四,四叉树 编码（Quadtree Encoding）,（一）思路：四叉树又称四元树或四分树，四叉树将整个图像区（2n2n）逐步分解为包含单一类型的方形区域，最小的方形区域为一个栅格象元。分割的原则是，将图像区域划分为四个大小相同的象限，而每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。,最上面的那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点分别对应于整个图形的四个象
41、限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶子结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。,四叉树中象限的尺寸是大小不一的，位于较高层次的象限较大，深度小即分解次数少，而低层次上的象限较小，深度大即分解次数多，这反映了图上某些位置单一地物分布较广而另一些位置上的地物比较复杂，变化较大。正是由于四叉树编码能够自动地依照图形变化而调整象限尺寸，因此它具有极高的压缩效率。,采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n2n的栅格阵列，n为极限分割数，
42、n+1为四叉树的最大高度或最大层数，图7-4（c）为2323的栅格，因此最多划分三次，最大层数为4，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n2n的图像。,（二）四叉树的生成方法,1、自上而下（top-down）：四叉树从上而下（形成）（从整体开始）由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。B、由Morton找出四叉树叶结点的具体位置。,03,B,A,2.自下而上（bottom-up）,一种按位操作的方法：如行为2、列为3的栅格的MD(行、列从0开始编号)步骤：(1)行、列号为二进制 Ib=1 0 Jb=1 1
43、(2)I行J列交叉 1 1 0 1=13(3)再化为十进制.实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。,把一幅2n2n的图像压缩成线性四叉树的过程,1、按Morton码把图象读入一维数组。2、相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。循环比较所形成的大块，相同的再合并，直到不能合并为止。3、进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。,右图的压缩处理过程为：1、按Morton码读入一维数组。Morton码：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15象 元 值：A A A B A A B
44、B A A A A B B B B2、四相邻象元合并，只记录第一个象元的Morton码。0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3、由于不能进一步合并，则用游程长度编码压缩。0 3 4 6 8 12 A B A B A B,（三）四叉树的存储方法,1）常规四叉树 记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系。每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值。,指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，常规
45、四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。,2）线性四叉树,记录叶结点的位置，深度（几次分割）和属性。地址码（定位码、Morton码）四进制、十进制优点：存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。线性四叉树可直接寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树。定位码容易存储和执行实现集合相加等组合操作。,四叉树编码具有可变的分辨率（能够自动地依照图形变化而调整象限尺寸），并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。,四叉树编码的优点,八叉树编
46、码,八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，同区域的属性相同。八叉树主要用来解决地理信息系统中的三维问题。,栅格数据压缩编码总结,对数据的压缩是以增加运算时间为代价的。在这里时间与空间是一对矛盾，为了更有效地利用空间资源，减少数据冗余，不得不花费更多的运算时间进行编码，好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实现。链码的压缩效率较高，已接近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始
47、栅格结构，编码解码十分容易；块码和四叉树码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。在此基础上已经开始发展了用于三维数据的八叉树编码等。,按照重分类、边界消除、合并这三个步骤实现依据属性聚合区域的目的。例：希望从一个数据层中得到土壤类型分布图，原始数据层中的多边形是根据更细的类别划分的（从图（a）可见，大写字母表示土壤类型的分类，小写字母表示植被类型的分类，每个多边形中土壤类型和植被类型完全一致。),(1)按照土壤类型这个属性项对原始数据层重分类。(2)如果两相邻多边形具有相同土壤类型，则删除它们间的分界弧段，这就是
48、边界消除。(3)重建拓扑，将没有分界弧段的相邻多边形合成一个。,三、空间数据的重分类,通过已知点或多边形分区的数据，推求任意点多多边形数据的方法，成为空间数据的内插。分类：点的内插区域内插,5-7 空间数据插值,一、点的内插:,内插:在已观测点的区域内估算未观测点的数据的过程；外推:在已观测点的区域外估算未观测点的数据的过程.预测。,（一）边界内插 首先假定任何重要的变化都发生在区域的边界上，边界内的变化则是均匀的、同质的。边界内插的方法之一是泰森多边形法。泰森多边形法的基本原理是，未知点的最佳值由最邻近的观测值产生。,5-7 空间数据插值,（二）整体内插,是一种多项式回归分析技术。多项式回归
49、的基本思想是用多项式表示线或面，按最小二乘法原理对数据点进行拟合，拟合时假定数据点的空间坐标X、Y为独立变量，而表示特征值的Z坐标为因变量。1、当数据为一维时，1）线性回归:,2）二次或高次多项式：,2、数据是二维的：趋势面分析,二元二次或高次多项式,5-7 空间数据插值,（三）局部分块内插,利用局部范围内的已知采样点的数据内插出未知点的数据。,1、线性内插,将内插点周围的3个数据点的数据值带入多项式，即可解算出系数a0、a1、a2。,2、双线性多项式内插,将内插点周围的4个数据点的数据值带入多项式，即可解算出系数a0、a1、a2、a3。,当数据是按正方形格网点布置:,5-7 空间数据插值,3
50、、双三次多项式（样条函数）内插,是一种分段函数,每次只用少量的数据点，故内插速度很快；样条函数通过所有的数据点，故可用于精确的内插；可用于平滑处理。双三次多项式内插的多项式函数为：,将内插点周围的16个点的数据带入多项式，可计算出所有的系数。,5-7 空间数据插值,（四）逐点内插（移动曲面法）：,1、移动平均法：在局部范围（或称窗口）内计算n个数据点的平均值.,二维平面的移动平均法也可用相同的公式，但位置Xi应被坐标矢量Xi代替。窗口的大小对内插的结果有决定性的影响。小窗口将增强近距离数据的影响；大窗口将增强远距离数据的影响，减小近距离数据的影响。,2、加权移动平均法:i是采样点i对应的权值,
