地理信息系统空间数据处理省公开课金奖全国赛课一等奖微课获奖课件

第五章空间数据处理空间数据坐标变换；空间数据结构转换；矢量数据图形编辑；拓扑关系自动建立；空间数据压缩与重分类空间数据内插方法；数字高程模型生成1/128空间数据变换即空间数据坐标系变换,其实质是建立两个平面点之间一一对应关系，包含几何纠正和投影转换，它们是空间数据处理基本内容之一。对于数字化地图数据，因为设备坐标系与用户确定坐标系不一致，以及因为数字化原图图纸发生变形等原因，需要对数字化原图数据进行坐标系转换和变形误差消除。有时，不一样起源地图还存在地图投影与地图百分比尺差异，所以还需要进行地图投影转换和地图百分比尺统一。§5.1空间数据坐标变换2/1281、百分比尺变换：乘系数2、变形误差更正：经过控制点利用高次变换、二次变换和仿射变换加以更正3、坐标旋转和平移即数字化坐标变换，利用仿射变换更正。4、投影变换：三种方法。几何变换返回§5.1空间数据坐标变换3/1285.1.1几何纠正：为了实现数字化数据坐标系转换和图纸变形误差更正，现有GIS软件普通含有仿射变换、相同变换、二次变换等几何纠正功效。§5.1空间数据坐标变换4/128

其中A、B代表二次以上高次项之和。上式是高次曲线方程，符合上式变换称为高次变换。式中有12个未知数，所以在进行高次变换时，需要有6对以上控制点坐标和理论值，才能求出待定系数。1、高次变换2、二次变换当不考虑高次变换方程中A和B时，则变成二次曲线方程，称为二次变换。二次变换适合用于原图有非线性变形情况，最少需要5对控制点坐标及其理论值，才能解算待定系数。

§5.1空间数据坐标变换5/128

3、仿射变换：实质是两坐标系间旋转变换。设图纸变形引发x,y两个方向百分比尺不一样，当x,y百分比尺相同时，为相同变换。特征：

·直线变换后仍为直线；·平行线变换后仍为平行线；·不一样方向上长度比发生改变。求解上式中6个未知数，需不在一直线上3对已知控制点，因为误差，需多出观察，所以，用于图幅定向最少需要四对控制点。§5.1空间数据坐标变换6/128仿射变换举例它主要特征为：同时考虑到x和y方向上变形，所以纠正后坐标数据在不一样方向上长度比将发生改变。7/1288/128三、地图投影变换1、解析变换法

1）反解变换法(又称间接变换法)假定原图点坐标为x,y(称为旧坐标)，新图点坐标为X，Y(称为新坐标)，则由旧坐标变换为新坐标基本方程式为：2）正解变换法(又称直接变换法)§5.1空间数据坐标变换9/1282、数值变换法

利用若干同名数字化点（对同一点在两种投影中均已知其坐标点），采取插值法、有限差分法或多项式迫近方法，即用数值变换法来建立两投影间变换关系式。

比如，采取二元三次多项式进行变换:经过选择10个以上两种投影之间共同点，并组成最小二乘法条件式，进行解算系数。§5.1空间数据坐标变换10/1283、数值解析变换法当已知新投影公式，但不知原投影公式时，可先经过数值变换求出原投影点地理坐标φ，λ，然后代入新投影公式中，求出新投影点坐标。即：§5.1空间数据坐标变换11/128投影变换：投影A（x，y）投影B（X，Y）正解变换：解析函数关系X=f(x,y)，Y=g(x,y)反解变换：经纬度B=f(x,y),L=g(x,y)X=F(B,L),Y=G(B,L)数值变换：数学方法12/128墨卡特投影摩尔魏特投影地图投影转换13/128地图投影转换等面积伪圆锥投影14/128地图投影转换斜轴等面积方位投影15/128栅格、矢量结构相互转换矢量结构与网格结构相互转换，是地理信息系统基本功效之一，当前已经发展了许多高效转换算法；不过，从栅格数据到矢量数据转换，尤其是扫描图像自动识别，依然是当前研究重点§5-2空间数据结构转换16/128对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构相互转换基本上只是坐标精度变换问题，不存在太大技术问题。线实体矢量结构由一系列坐标对表示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需依据栅格精度要求，在坐标点之间插满一系列栅格点，这也轻易由两点式直线方程得到。线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相同，所以以下重点讨论多边形（面实体）矢量结构与栅格结构相互转换。§5-2空间数据结构转换17/1285.2.1矢量格式向栅格格式转换矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示多边形边界内部全部栅格点上赋以对应多边形编码18/128例：矢量到栅格转换19/128矢量格式向栅格格式转换算法内部点扩散算法：该算法由每个多边形一个内部点（种子点）开始，向其八个方向邻点扩散，判断各个新加入点是否在多边形边界上，假如是边界上，则该新加入点不作为种子点，不然把非边界点邻点作为新种子点与原有种子点一起进行新扩散运算，并将该种子点赋以该多边形编号。重复上述过程直到全部种子点填满该多边形并碰到边界停顿为止。

特点：扩散算法程序设计比较复杂，而且在一定栅格精度上，假如复杂图形同一多边形两条边界落在同一个或相邻两个栅格内，会造成多边形不连通，这么一个种子点不能完成整个多边形填充。20/128矢量格式向栅格格式转换算法复数积分算法：对全部栅格阵列逐一栅格单元地判断该栅格归属多边形编码，判别方法是由待判点对每个多边形封闭边界计算复数积分。对某个多边形，假如积分值为2

i，则该待判点属于此多边形，赋以多边形编号，不然在此多边形外部，不属于该多边形。

特点：算法可靠，但极费机时。21/128矢量格式向栅格格式转换算法射线算法：射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形全部边界相交总次数，如相交偶数次，则待判点在该多边形外部；如为奇数次，则待判点在该多边形内部（如图）。

22/128矢量格式向栅格格式转换算法射线算法优缺点：运算量大；射线与多边形边界相交时，有一些特殊情况会影响交点个数，必须给予排除（如图）。

23/128矢量格式向栅格格式转换算法扫描算法：是射线算法改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相同。扫描算法省去了计算射线与多边形边界交点大量运算，大大提升了效率。特点：占用内存较大；扫描线与多边形相交各种特殊情况依然存在。24/128矢量格式向栅格格式转换算法边界代数算法（BAF-BoundaryAlgebraFilling）：是一个基于积分思想矢量格式向栅格格式转换算法，它适合于统计拓扑关系多边形矢量数据转换为栅格结构。

25/128单个多边形转换由多边形边界上某点开始顺时针搜索边界限，当边界上行时（图a），位于该边界左侧含有相同行坐标全部栅格被减去a；当边界下行时（图b），该边界左边（前进方向看为右侧）全部栅格点加一个值a，边界搜索完成则完成了多边形转换。矢量格式向栅格格式转换算法26/128多个多边形转换实际上，每幅数字地图都是由多个多边形区域组成，假如把不属于任何多边形区域（包含无穷远点区域）看成编号为零特殊多边形区域，则图上每一条边界弧段都与两个不一样编号多边形相邻，按弧段前进方向分别称为左、右多边形，能够证实，对于这种多个多边形矢量向栅格转换问题，只需对全部多边形边界弧段作以下运算而不考虑排列次序：当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号—右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号—左多边形编号）。矢量格式向栅格格式转换算法27/128两个多边形转换上行：左—右下行：右—左

28/128边界代数法特点：与前述其它算法不一样之处，在于它不是逐点判断与边界关系完成转换，而是依据边界拓扑信息，经过简单加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式高速转换，而不需要考虑边界与搜索轨迹之间关系，所以算法简单、可靠性好，各边界弧段只被搜索一次，防止了重复计算。

29/1285.2.2栅格格式向矢量格式转换多边形栅格格式向矢量格式转换就是提取以相同编号栅格集合表示多边形区域边界和边界拓扑关系，并表示由多个小直线段组成矢量格式边界限过程。30/128从栅格单元转换为几何图形过程为矢量化；（一）要求（矢量化过程应保持）：1）

栅->矢转换为拓扑转换，即保持实体原有连通性、邻接性等；2）

转换实体保持正确外形。（二）方法方法一：实际应用中大多数采取人工矢量化法，如扫描矢量化(该法工作量大，成为GIS数据输入、更新瓶颈问题之一)。方法二，程序转化转换（全自动或半自动）过程为：分类图遥感影象图栅格分类图边界提取二值化编辑矢量跟踪数据压缩原始线划图二值化细化扫描预处理拓扑化1、边界提取2、二值化3、二值图像预处理

4、细化:1）剥皮法2)骨架法5、跟踪6、拓扑化5.2.2栅格格式向矢量格式转换31/128方法二，程序转化转换（全自动或半自动）栅格格式向矢量格式转换通常包含以下四个基本步骤：多边形边界提取：采取高通滤波将栅格图像二值化或以特殊值标识边界点；边界限追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向其它7个方向搜索下一个边界点，直到连成边界弧段；拓扑关系生成：对于矢量表示边界弧段数据，判断其与原图上各多边形空间关系，以形成完整拓扑结构并建立与属性数据联络；去除多出点及曲线圆滑：因为搜索是逐一栅格进行，必须去除由此造成多出点统计，以降低数据冗余；搜索结果，曲线因为栅格精度限制可能不够圆滑，需采取一定插补算法进行光滑处理，惯用算法有：线形迭代法；分段三次多项式插值法；正轴抛物线平均加权法；斜轴抛物线平均加权法；样条函数插值法。栅格格式向矢量格式转换32/128多边形栅格转矢量双边界搜索算法

（DBDF-DoubleBoundaryDirectFinding）(1)边界点和结点提取：边界点6种情形:假如窗口内四个栅格有且仅有两个不一样编号，则该四个栅格表示为边界点.结点8种情形:假如窗口内四个栅格有三个以上不一样编号，则标识为结点（即不一样边界弧段交汇点），保持各栅格原多边形编号信息。33/128双边界搜索算法（2）边界限搜索与左右多边形信息统计：边界限搜索是逐一弧段进行，对每个弧段由一组已标识四个结点开始，选定与之相邻任意一组四个边界点和结点都必定属于某一窗口四个标识点之一。首先统计开始边界点两个多边形编号，作为该弧段左右多边形，下一点组搜索方向则由进入当前点搜索方向和该点组可能走向决定，每个边界点组只能有两个走向，一个是前点组进入方向，另一个则可确定为将要搜索后续点组方向。栅格格式向矢量格式转换34/128双边界搜索算法（3）多出点去除：多出点去除基于以下思想：在一个边界弧段上连续三个点，假如在一定程度上能够认为在一条直线上（满足直线方程），则三个点中间一点能够被认为上多出，给予去除。多出点是因为栅格向矢量转换时逐点搜索边界造成（当边界为直线时），多出点去除算法可大量去除多出点，降低数据冗余。双边界搜索算法优点双边界结构能够唯一地确定搜索方向，从而大大地降低搜索时间，同时形成矢量结构带有左右多边形编号信息，轻易建立拓扑结构和与属性数据联络，提升转换效率。

35/128图形编辑是一交互处理过程，GIS具备图形编辑功效要求是：1）含有友好人机界面，即操作灵活、易于了解、响应快速等；2）含有对几何数据和属性编码修改功效，如点、线、面增加、删除、修改等；3）含有分层显示和窗口操作功效，便于用户使用。第五章空间数据处理图形编辑又叫数据编辑、数字化编辑，是指对地图资料数字化后数据进行编辑加工，其主要目标是在更正数据差错同时，对应地更正数字化资料图形。5.3矢量数据图形编辑36/128数据检验与清理数据检验：指拓扑关系检验。包含检验结点是否匹配、是否存在悬挂线（线段过长或过短；伪结点；线段断裂）；多边形是否闭合（多边形裂口）等。数据清理： 用自动方法去除空间数据错误。5.3矢量数据图形编辑37/128一、常见问题线段过长或过短5.3矢量数据图形编辑38/128矢量图形编辑

一、常见问题伪结点由且仅有两个线目标相关联结点成为假结点。AB39/128未吻合结点多边形裂口矢量图形编辑

一、常见问题多边形问题40/128“碎屑”多边形或“条带”多边形（SliverPolygon）：普通因为重复录入引发，因为前后两次录入同一条线位置不可能完全一致，造成了“碎屑”多边形。另外，因为用不一样百分比尺地图进行数据更新，也可能产生“碎屑”多边形。矢量图形编辑

41/128不正规多边形是因为输入线时，点次序倒置或者位置不准确引发，在进行拓扑生成时，一样会产生“碎屑”多边形。矢量图形编辑

42/128二、编辑操作1）结点吻合(Snap)或称结点匹配、结点咬合，结点附和。方法：A、

结点移动，用鼠标将其它两点移到另一点；B、

鼠标拉框，用鼠标拉一个矩形，落入该矩形内结点坐标经过求它们中间坐标匹配成一致；C、

求交点，求两条线交点或其延长线交点，作为吻合结点；D、自动匹配，给定一个吻合容差，或称为咬合距，在图形数字化时或之后，将容差范围内结点自动吻合成一点。普通，若结点容差设置合理，大多数结点能够吻合在一起，但有些情况还需要使用前三种方法进行人工编辑。1、结点编辑5.3矢量数据图形编辑43/1282）结点与线吻合编辑方法：A、

结点移动，将结点移动到线目标上。B、

使用线段求交；C、

自动编辑，在给定容差内，自动求交并吻合在一起。在数字化过程中，常碰到一个结点与一个线状目标中间相交。因为测量或数字化误差，它不可能完全交于线目标上，需要进行编辑，称为结点与线吻合。3）需要考虑两种情况A、

要求坐标一致，而不建立拓扑关系；如高架桥（不需打断，直接移动）B、

不但坐标一致，且要建立之间空间关联关系；如道路交叉口（需要打断）ABDCE无结点有结点5.3矢量数据图形编辑44/1284）去除假结点（伪结点）有些系统要将这种假结点去除掉（如ARC/INFO），即将目标A和B合并成一条，使它们之间不存在结点;但有些系统并不要求去除假结点，如Geostar,因为它们并不影响空间查询、分析和制图。由且仅有两个线目标相关联结点成为假结点。AB5.3矢量数据图形编辑45/1282、图形编辑包含用鼠标增加或删除一个点、线、面实体，移动、旋转一个点、线、面实体。1）删除和增加一个顶点删除顶点，在数据库中不用整体删除与目标相关数据，只是在原来存放位置重写一次坐标，拓扑关系不变。增加顶点，则操作和处理都要复杂。不能在原来存放位置上重写，需要给一个新目标标识号，在新位置上重写，而将原来目标删除，此时需要做一系列处理，调整空间拓扑关系。2）移动一个顶点移动顶点只包括某个点坐标，不包括拓扑关系维护，较简单。3）删除一段弧段复杂，先要把原来弧段打断,存放上原来弧段实际被删除，拓扑关系需要调整和改变.jkjkabL3L1L25.3矢量数据图形编辑46/1283、数据检验与清理数据检验指拓扑关系检验，结点是否匹配，是否存在悬挂弧段，多边形是否封闭，是否有假结点。要求系统能将有错误或不正确拓扑关系点、线和面用不一样颜色和符号表示出来，方便于人工检验和修改。数据清理则是用自动方法去除空间数据错误.比如给定一个结点吻合容差使该容差范围内结点自动吻合在一起，并建立拓扑关系。给定悬挂弧段容差，将小于该容差短弧自动删除。在Arc/info中用DataClean命令，在Geostar中选择整体结点匹配菜单。4、撤消与恢复编辑Undo,Redo功效是必要。但功效实现是困难。当撤消编辑，即恢复目标，要恢复目标标识和坐标、拓扑关系。这一处理过程相当复杂.所以，有些GIS不在图形编辑时实时建立和维护拓扑关系，如Arc/Info等，而在图形编辑之后，发Clean或Build命令重新建立拓扑关系。这么，在每次进行任何一次编辑，都要重新Clean或Build，对用户不便。N1N2A2N1N2A25.3矢量数据图形编辑47/128三、关键算法可设一捕捉半径D(通常为3～5个象素，这主要由屏幕分辩率和屏幕尺寸决定)。1、点捕捉设光标点为S(x,y)，某一点状要素坐标为A(X，Y)若S和A距离d小于D则认为捕捉成功，即认为找到点是A，不然失败，继续搜索其它点。乘方运算影响了搜索速度，所以，把距离d计算改为：捕捉范围由圆改为矩形，这可大大加紧搜索速度。5.3矢量数据图形编辑48/1282、线捕捉设光标点坐标为S(x,y)，D为捕捉半径，线坐标为(x1,y1),(x2,y2),…(xn,yn)。经过计算S到该线每个直线段距离d。.若min(d1,d2,…dn-1)＜D，则认为光标S捕捉到了该条线，不然为未捕捉到。加紧线捕捉速度方法：1）在实际捕捉中，可每计算一个距离di就进行一次比较，若di＜D，则捕捉成功，不需再进行下面直线段到点S距离计算了。2）把不可能被光标捕捉到线，用简单算法去除。3）对于线段也采取类似方法处理。4）简化距离公式：点S(x,y)到直线段(x1,y1),(x2,y2)距离d计算公式为：

简化为：49/1283、面捕捉实际上就是判断光标点S(x,y)是否在多边形内，若在多边形内则说明捕捉到。判断点是否在多边形内算法主要有垂线法或转角法。

垂线法基本思想是从光标点引垂线(实际上能够是任意方向射线)，计算与多边形交点个数。若交点个数为奇数则说明该点在多边形内；若交点个数为偶数，则该点在多边形外。

加紧速度方法：1）找出该多边形外接矩形，若光标点落在该矩形中，才有可能捕捉到该面，不然放弃对该多边形深入计算和判断。2）对不可能有交点线段应经过简单坐标比较快速去除。3）利用计算交点技巧。

5.3矢量数据图形编辑50/128一、点线拓扑关系自动建立a1a2N1N2N3N4a3a1a2N1N2N3a1a2N1N2N3N4a3a4(b)(a)(c)结点-弧段表Oid起结点终止点a1a2N1N2N2N3Oid弧段号N1N2N3a1a1,a2a2弧段-结点表1、在图形采集和编辑中实时建立Oid起结点终止点a1a2a3N1N2N2N2N3N4Oid弧段号N1N2N3N4a1a1,a2,a3a2a3Oid起结点终止点a1a2a3a4N1N2N2N4N2N3N4N3Oid弧段号N1N2N3N4a1a1,a2,a3a2,a4a3,a42、在图形采集和编辑之后自动建立，其基本原理与前类似。§5-4拓扑关系自动建立51/128二、多边形拓扑关系自动建立1、链组织1）找出在链中间相交情况，自动切成新链；2）把链按一定次序存放，并把链按次序编号。2、结点匹配1）把一定限差内链端点作为一个结点，其坐标值取多个端点平均值。2）对结点次序编号。3、检验多边形是否闭合经过判断一条链端点是否有与之匹配端点来进行.多边形不闭合原因：1）因为结点匹配限差问题，造成应匹配端点未匹配；2）因为数字化误差较大，或数字化错误，这些能够经过图形编辑或重新确定匹配限差来确定。3）还可能这条链本身就是悬挂链，不需参加多边形拓扑，这种情况下能够作一标识，使之不参加下一阶段拓扑建立多边形工作。§5-4拓扑关系自动建立52/1284、建立多边形1）概念a、顺时针方向构多边形：指多边形是在链右侧。b、最靠右边链：指从链一个端点出发，在这条链方向上最右边第一条链，实质上它也是左边最近链。a最右边链为d当多边形由顺时针方向组成时，面积为正；反之，面积为负。二、多边形拓扑关系自动建立§5-4拓扑关系自动建立c、多边形面积计算53/1282）建立多边形基本过程1°次序取一个结点为起始结点，取完为止；取过该结点任一条链作为起始链。2°取这条链另一结点，找这个结点上，靠这条链最右边链，作为下一条链。3°是否回到起点：是，已形成一多边形，统计之，并转4°；否，转2°。4°取起始点上开始，刚才所形成多边形最终一条边作为新起始链，转2°；若这条链已用过两次，即已成为两个多边形边，则转1°。例：1°从P1开始，起始链定为P1P2,从P2点算起，P1P2最右边链为P2P5；从P5算起，P2P5最右边

链为P5P1,...形成多边形为P1P2P5P1。2°从P1开始，以P1P5为起始链，形成多边形为P1P5P4P1。3°从P1开始，以P1P4为起始链,形成多边形为P1P4P3P2P1。4°这时P1为结点全部链均被使用了两次，因而转向下一个结点P2，继续进行多边形追踪，直至全部结点取完。共可追踪出五个多边形，即A1、A2、A3、A4、A5。§5-4拓扑关系自动建立54/1285、岛判断找出多边形相互包含情况.1°、计算全部多边形面积。2°、分别对面积为正多边形和面积为负多边形排序。3°、从面积为正多边形中，次序取每个多边形，取完为止。若负面积多边形个数为0，则结束。4°、找出该多边形所包含全部面积为负多边形，并把这些面积为负多边形加入到包含它们多边形中，转3°。正面积多边形包含负面积多边形是关键.1°、找出全部比该正面积多边形面积小负面积多边形。2°、用外接矩形法去掉不可能包含多边形。即负面积多边形外接矩形不和该正面积多边形外接矩形相交或被包含时，则不可能为该正面积多边形包含。3°、取负面积多边形上一点，看是否在正面积多边形内，若在内，则被包含；若在外，则不被包含。

6、确定多边形属性多边形以内点标识。内点与多边形匹配后,内点属性常赋于多边形.

单多边形被追踪两次p1p2p3p1,p2,p3,-p1,-p2,-p3,§5-4拓扑关系自动建立55/128一、图形裁剪--开窗处理1、方式：

正窗：提取窗口内数据。

开负窗：提取窗口外数据子集。矩形窗和多边形窗。2、算法：包含点、线、面窗口裁剪---计算机图形学。而不规则多边形开窗------相当于多边形叠置处理。§5-5图形裁剪、合并和图幅接边56/128因为空间数据采集误差和人工操作误差，两个相邻图幅地图空间数据在结合处可能出现逻辑裂隙与几何裂隙。逻辑裂隙指是当一个地物在一幅图数据文件中含有地物编码A，而在另一幅图数据文件中却含有地物编码B，或者同一物体在这两个数据文件中含有不一样属性信息，如公路宽度、等高线高程等。几何裂隙指是由数据文件边界分开一个地物两部分不能准确地衔接。图幅接边：在GIS中，需要把单独数字化相邻图幅空间数据在逻辑上和几何上融成一个连续一致数据体，这就是GIS中图幅接边（图形拼接）问题。图幅接边包含几何接边和逻辑接边。二、图幅数据边缘匹配处理§5-5图形裁剪、合并和图幅接边57/128图幅接边—形成无缝数据库几何裂缝：指由数据文件边界分开一个地物两部分不能准确地衔接。--几何接边逻辑裂缝：同一地物地物编码不一样或含有不一样属性信息，如公路宽度，等高线高程等。---逻辑接边

2、几何接边人工接边接边1、识别或提取相邻图幅。--要求图幅编号合理313233212223111213直接移动，突变回缩2-3个点降低突变§5-5图形裁剪、合并和图幅接边58/128图形合并

一幅图内多层数据合并在一起;或将相邻多幅图同一层数据合并.包括到空间拓扑关系重建。对于多边形，因为同一个目标在两幅图内已形成独立多边形，合并时，需去除公共边界，属性合并，详细算法，删去共同线段。实际处理过程是先删除两个多边形，解除空间关系后，删除公共边，再重建拓扑。pL1pAApL1pAApL1pAA去除公共边界属性合并二、图幅数据边缘匹配处理

59/1283、逻辑接边1）检验同一地物在相邻图幅地物编码和属性值是否一致，不一致，进行人工编辑。2）将同一地物在相邻图幅空间数据在逻辑上连在一起。AA3A1A2Oid…指针A1AOid…指针A2AOid…指针A3AOid指针AA1A2A3图3图2图1总目标文件a、索引文件，建立双向指针。b、关键字，空间操作方法。逻辑接边二、图幅数据边缘匹配处理

60/128一、数据压缩5.6.1矢量数据压缩1、Douglas—Peucker§5-6空间数据压缩与重分类图形显示输出数据存放数据压缩光滑矢量数据压缩(去冗余/抽稀)栅格数据压缩压缩效果好，但必须在对整条曲线数字化完成后才能进行，且计算量较大；61/1282、垂距法每次次序取曲线上三个点，计算中间点与其它两点连线垂线距离d，并与限差D比较。若d＜D，则中间点去掉；若d≥D，则中间点保留。然后次序取下三个点继续处理，直到这条线结束。3、偏角法4、间隔取点法压缩算法好，可在数字化时实时处理，每次判断下一个数字化点，且计算量较小；§5-6空间数据压缩与重分类62/128二、曲线光滑（拟合）是假象曲线为一组离散点，寻找形式较简单、性能良好曲线解析式。插值方式：曲线经过给定离散点。如拉格朗日插值，三次样条曲线迫近方式：曲线尽可能迫近给定离散点。如贝塞尔和B样条曲线。§5-6空间数据压缩与重分类63/1285.6.2栅格数据压缩栅格数据编码栅格数据直接编码方法栅格数据压缩编码方法64/128栅格数据编码方法空间数据编码是空间数据结构实现，即将依据地理信息系统目标和任务所搜集、经过审核了地形图、专题地图和遥感影像等资料按特定数据结构转换为适合于计算机存放和处理数据过程。因为地理信息系统数据量极大，普通采取压缩数据编码方式以降低数据冗余。5.6.2栅格数据压缩65/128（一）栅格数据直接编码这是最简单直观而又非常主要一个栅格结构编码方法，通常称这种编码图像文件为网格文件或栅格文件，栅格结构不论采取何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐一统计代码，能够每行都从左到右逐一象元统计，也能够奇数行从左到右而偶数行从右向左统计，为了特定目标还可采取其它特殊次序。66/128直接编码可分为：显式存放:每个栅格同时储存其行号、列号及属性值。（I1,J1,A1，…，In,Jn,An,…)隐式存放：隐含行、列号，次序存放栅格属性值。(A1,A2,A3,…,An,…)67/128（二）栅格数据压缩编码压缩目标：以尽可能少数据量统计尽可能多信息压缩类型：信息无损压缩：是指编码过程中没有任何信息损失，经过解码操作能够完全恢复原来信息信息有损压缩：是指为了提升编码效率，最大程度地压缩数据，在压缩过程中损失一部分相对不太主要信息，解码时这部分难以恢复。68/128栅格数据压缩编码方法之一链码（ChainCodes）：弗里曼链码[Freeman]或边界链码，适合用于对曲线和多边形边界进行编码。方法：八方向定义：东＝0，东南＝l，南=2，西南＝3，西＝4，西北＝5，北＝6，东北＝7等八个基本方向。编码：线标号，起始行，起始列，属性码，方位1，方位2，…，方位n,…线标号，起始行，起始列，属性码，方位1，方位2，…，方位n,………69/128弗里曼链码——练习1000000600006060606606006000000604404000600404000000040400000040070/128弗里曼链码——练习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。

71/128链式编码特点：链式编码对多边形和线状地物表示含有很强数据压缩能力，且含有一定运算功效，如面积和周长计算等，探测边界急弯和凹进部分等都比较轻易；缺点是对叠置运算如组合、相交等则极难实施，对局部修改将改变整体结构，效率较低，而且因为链码以每个区域为单位存放边界，相邻区域边界则被重复存放而产生冗余。72/128栅格数据压缩编码方法之二游程编码（Run-LengthCodes）基本思绪：对于一幅栅格图像，经常有行（或列）方向上相邻若干点含有相同属性代码，因而可采取某种方法压缩那些重复统计内容。73/128游程：一行（列）中，属性相同连续栅格，称为一个游程。依据数据结构不一样，可分为：游程长度编码：Ci—属性，Li—游程连续长度。游程终止编码：Ci—属性，Li—游程终止点列号。思绪：将栅格矩阵中行序列x1,x2,x3,…,xn映射成整数对序列。即：(c1,l1),(c2,l2),…,(cn,ln).74/128游程长度编码——练习游程长度编码游程终止编码75/128游程编码优、缺点游程编码优点：在对“多对一”结构，即许多像元同属一个地理属性值情况下大大改进了传统编码存放情况。游程长度编码栅格加密时，数据量没有显著增加，压缩效率较高，且易于检索、叠加、合并等操作。这种编码方法最适合于小型计算机，同时也降低了栅格数据库数据输入量。游程编码缺点：计算期间处理和制图输出处理工作量都有所增加。76/128栅格数据压缩编码方法之三块码（BlockCodes）块码是游程长度编码扩展到二维情况，采取方形区域作为统计单元，每个统计单元包含相邻若干栅格，数据结构由初始位置（行、列号）和半径，再加上统计单位代码组成。即(I1,J1,L1,C1，….，I2,J2,L2,C2，….)77/1284442244422442221122211322块码示例(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)压缩率：伴随图形复杂程度提升而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低

78/128块码优缺点块码在合并、插入、检验延伸性、计算面积等操作时有显著优越性。然而在一些操作时，则必须将其解码，转换为基本栅格结构才能顺利进行。79/128栅格数据压缩编码方法之四四叉树编码（QuadtreeEncoding）（一）思绪：四叉树又称四元树或四分树，四叉树将整个图像区（2n×2n）逐步分解为包含单一类型方形区域，最小方形区域为一个栅格象元。分割标准是，将图像区域划分为四个大小相同象限，而每个象限又可依据一定规则判断是否继续等分为次一层四个象限，其终止判据是，不论是哪一层上象限，只要划分到仅代表一个地物时，则不再继续划分，不然一直划分到单个栅格象元为止。80/128最上面那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点分别对应于整个图形四个象限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分结点称为终止结点（又称叶子结点），可能落在不一样层上，该结点代表子象限含有单一代码，全部终止结点所代表方形区域覆盖了整个图形。81/128四叉树中象限尺寸是大小不一，位于较高层次象限较大，深度小即分解次数少，而低层次上象限较小，深度大即分解次数多，这反应了图上一些位置单一地物分布较广而另一些位置上地物比较复杂，改变较大。正是因为四叉树编码能够自动地依照图形改变而调整象限尺寸，所以它含有极高压缩效率。采取四叉树编码时，为了确保四叉树分解能不停地进行下去，要求图像必须为2n×2n栅格阵列，n为极限分割数，n+1为四叉树最大高度或最大层数，图7-4（c）为23×23栅格，所以最多划分三次，最大层数为4，对于非标准尺寸图像需首先经过增加背景方法将图像扩充为2n×2n图像。82/128（二）四叉树生成方法1、

自上而下（top-down）：四叉树从上而下（形成）（从整体开始）由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码位数表示分割次数。B、由Morton找出四叉树叶结点详细位置。

0123AAAAABBBAABBAAABB03BA83/1282.自下而上（bottom-up）一个按位操作方法：如行为2、列为3栅格MD(行、列从0开始编号)步骤：(1)行、列号为二进制Ib=10Jb=11(2)I行J列交叉1101=13(3)再化为十进制.实质上是按左上、右上、左下、右下次序，从零开始对每个栅格进行自然编码。

A0A1A4A5A2

B3B6B7A8A9B12B13A10A11B14B1584/128把一幅2n×2n图像压缩成线性四叉树过程

1°、按Morton码把图象读入一维数组。

2°、相邻四个象元比较，一致合并，只统计第一个象元Morton码。循环比较所形成大块，相同再合并，直到不能合并为止。

3°、深入用游程长度编码压缩。压缩时只统计第一个象元Morton码。A0A1A4A5A2

B3B6B7A8A9B12B13A10A11B14B15右图压缩处理过程为：1°、按Morton码读入一维数组。Morton码：0123456789101112131415象元值：

AAAB

AABB

AAAA

BBBB2°、四相邻象元合并，只统计第一个象元Morton码。

0123

4567

8

12

AAAB

AABB

A

B3°、因为不能深入合并，则用游程长度编码压缩。

03

46812

AB

ABABA0A1A4A5A2

B3B6B7A8A9B12B13A10A11B14B1585/128（三）四叉树存放方法1）常规四叉树

统计这棵树叶结点外，中间结点，结点之间联络用指针联络。每个结点需要6个变量：父结点指针、四个子结点指针和本结点属性值。指针不但增加了数据存放量，还增加了操作复杂性：如层次数（分割次数）由从父结点移到根结点次数来确定，结点所代表图像块位置需要从根节点开始逐步推算下来。所以，常规四叉树并不广泛用于存放数据，其价值在于建立索引文件，进行数据检索。86/1282）线性四叉树统计叶结点位置，深度（几次分割）和属性。地址码（定位码、Morton码）四进制、十进制优点：存贮量小，只对叶结点编码，节约了大量中间结点存放，地址码隐含着结点分割路径和分割次数。线性四叉树可直接寻址，经过其坐标值直接计算其Morton码，而不用建立四叉树。定位码轻易存放和执行实现集合相加等组合操作。

87/128四叉树编码含有可变分辨率（能够自动地依照图形改变而调整象限尺寸），而且有区域性质，压缩数据灵活，许多运算能够在编码数据上直接实现，大大地提升了运算效率，是优异栅格压缩编码之一。四叉树编码优点88/128八叉树编码八叉树结构就是将空间区域不停地分解为八个一样大小子区域(即将一个六面立方体再分解为八个相同大小小立方体)，同—区域属性相同。八叉树主要用来处理地理信息系统中三维问题。

89/128栅格数据压缩编码总结对数据压缩是以增加运算时间为代价。在这里时间与空间是一对矛盾，为了更有效地利用空间资源，降低数据冗余，不得不花费更多运算时间进行编码，好压缩编码方法就是要在尽可能降低运算时间基础上到达最大数据压缩效率，而且是算法适应性强，易于实现。链码压缩效率较高，已靠近矢量结构，对边界运算比较方便，但不含有区域性质，区域运算困难；游程长度编码既能够在很大程度上压缩数据，又最大程度地保留了原始栅格结构，编码解码十分轻易；块码和四叉树码含有区域性质，又含有可变分辨率，有较高压缩效率，四叉树编码能够直接进行大量图形图像运算，效率较高，是很有前途方法。在此基础上已经开始发展了用于三维数据八叉树编码等。90/128按照重分类、边界消除、合并这三个步骤实现依据属性聚合区域目标。例：希望从一个数据层中得到土壤类型分布图，原始数据层中多边形是依据更细类别划分（从图（a）可见，大写字母表示土壤类型分类，小写字母表示植被类型分类，每个多边形中土壤类型和植被类型完全一致。)(1)按照土壤类型这个属性项对原始数据层重分类。(2)假如两相邻多边形含有相同土壤类型，则删除它们间分界弧段，这就是边界消除。(3)重建拓扑，将没有分界弧段相邻多边形合成一个。

三、空间数据重分类91/128经过已知点或多边形分区数据，推求任意点多多边形数据方法，成为空间数据内插。分类：点内插区域内插§5-7空间数据插值92/128一、点内插:内插:在已观察点区域内估算未观察点数据过程；外推:在已观察点区域外估算未观察点数据过程.——预测。（一）边界内插首先假定任何主要改变都发生在区域边界上，边界内改变则是均匀、同质。边界内插方法之一是泰森多边形法。泰森多边形法基本原理是，未知点最正确值由最邻近观察值产生。内插外推§5-7空间数据插值93/128（二）整体内插是一个多项式回归分析技术。多项式回归基本思想是用多项式表示线或面，按最小二乘法原理对数据点进行拟合，拟合时假定数据点空间坐标X、Y为独立变量，而表示特征值Z坐标为因变量。1、当数据为一维时，1）线性回归:2）二次或高次多项式：2、数据是二维：趋势面分析二元二次或高次多项式§5-7空间数据插值94/128（三）局部分块内插利用局部范围内已知采样点数据内插出未知点数据。1、线性内插将内插点周围3个数据点数据值带入多项式，即可解算出系数a0、a1、a2。2、双线性多项式内插将内插点周围4个数据点数据值带入多项式，即可解算出系数a0、a1、a2、a3。当数据是按正方形格网点布置:§5-7空间数据插值95/1283、双三次多项式（样条函数）内插是一个分段函数,每次只用少许数据点，故内插速度很快；样条函数经过全部数据点，故可用于准确内插；可用于平滑处理。

双三次多项式内插多项式函数为：

将内插点周围16个点数据带入多项式，可计算出全部系数。16个点§5-7空间数据插值96/128（四）逐点内插（移动曲面法）：1、移动平均法：在局部范围（或称窗口）内计算n个数据点平均值.

二维平面移动平均法也可用相同公式，但位置Xi应被坐标矢量Xi代替。

窗口大小对内插结果有决定性影响。

小窗口将增强近距离数据影响；大窗口将增强远距离数据影响，减小近距离数据影响。2、加权移动平均法:λi是采样点i对应权值

加权平均内插结果随使用函数及其参数、采样点分布、窗口大小等不一样而改变。通常使用采样点数为6—8点。对于不规则分布采样点需要不停地改变窗口大小、形状和方向，以获取一定数量采样点。当观察点相互位置越近，其数据相同性越强；当观察点相互位置越远，其数据相同性越低。§5-7空间数据插值97/1283、克里金（Kriging）法：相关知识

区域化变量：当一个变量展现一定空间分布时，称之为区域化变量，它反应了区域内某种特征或现象。区域化变量与普通随机变量不一样之处于于，普通随机变量取值符合一定概率分布，而区域化变量依据区域内位置不一样而取不一样值。而当区域化变量在区域内确定位置取值时，表现为普通随机变量，也就是说，它是与位置相关随机变量。区域化变量含有两个显著特征：即随机性和结构性。首先，区域化变量是一个随机变量，它含有局部、随机、异常特征；其次，区域化变量含有一定结构特点，即变量在点x与偏离空间距离为h点x+h处值Z(x)和Z(x+h)含有某种程度相同性，即自相关性，这种自相关性程度依赖于两点间距离h及变量特征。除此之外，区域化变量还含有空间不足（即这种结构性表现为一定范围内）、不一样程度连续性和不一样程度各向异性（即各个方向表现出自相关性有所区分）等特征。（四）逐点内插（移动曲面法）：§5-7空间数据插值98/128地统计（Geostatistics）又称地质统计，是在法国著名统计学家G.Matheron大量理论研究基础上逐步形成一门新统计学分支。它是以区域化变量为基础，借助变异函数，研究既含有随机性又含有结构性，或空间相关性和依赖性自然现象一门科学。凡是与空间数据结构性和随机性，或空间相关性和依赖性，或空间格局与变异相关研究，并对这些数据进行最优无偏内插预计，或模拟这些数据离散性、波动性时，皆可应用地统计学理论与方法。地统计学与经典统计学共同之处在于：它们都是在大量采样基础上，经过对样本属性值频率分布或均值、方差关系及其对应规则分析，确定其空间分布格局与相关关系。但地统计学区分于经典统计学最大特点即是：地统计学既考虑到样本值大小，又重视样本空间位置及样本间距离，填补了经典统计学忽略空间方位缺点。§5-7空间数据插值99/128克里金（Kriging）法：克里格方法适用范围为区域化变量存在空间相关性，即假如变异函数和结构分析结果表明区域化变量存在空间相关性，则能够利用克里格方法进行内插或外推；不然反之。其实质是利用区域化变量原始数据和变异函数结构特点，对未知样点进行线性无偏、最优预计。无偏是指偏差数学期望为0，最优是指预计值与实际值之差平方和最小。也就是说，克里格方法是依据未知样点有限邻域内若干已知样本点数据，在考虑了样本点形状、大小和空间方位，与未知样点相互空间位置关系，以及变异函数提供结构信息之后，对未知样点进行一个线性无偏最优预计。（四）逐点内插（移动曲面法）：§5-7空间数据插值100/128

半方差图（P102图3-40）§5-7空间数据插值101/128当前，克里格方法主要有以下几个类型：普通克里格（OrdinaryKriging）；简单克里格（SimpleKriging）；泛克里格（UniversalKriging）；协同克里格（Co-Kriging）；对数正态克里格（LogisticNormalKriging）；指示克里格（IndicatorKriging）；概率克里格（ProbabilityKriging）；析取克里格（DisjunctiveKriging）等。§5-7空间数据插值102/128惯用Kriging方法普通Kriging:该种方法和反百分比加权插值基本相同，只是权重不是一个任意距离函数，而是基于模型变量图。P102-103插值权重之和为1；表面不太光滑。简单Kriging:权重之和不等于1；表面愈加平滑。通用Kriging:离散点平均值不固定；应用一个“漂移”项来模拟离散点平均值；插值残差被加到漂移上来计算预计值103/128不一样克里格方法适用条件:

当数据不服从正态分布时，若服从对数正态分布，则选取对数正态克里格；若不服从简单分布时，选取析取克里格。当数据存在主导趋势时，选取泛克里格。当只需了解属性值是否超出某一阈值时，选取指示克里格。当同一事物两种属性存在相关关系，且一个属性不易获取时，可选取协同克里格方法，借助另一属性实现该属性空间内插。当假设属性值期望值为某一已知常数时，选取简单克里格。当假设属性值期望值是未知，选取普通克里格。

104/128二区域内插

是研究依据一组分区以知数据来推求同一地域另一组分区未知数据内插方法。常采取两种方法叠置法：是将目标区叠置在源区上，首先确定二者面积交集，然后利用公式计算目标区各个分区值。比重法：原理是依据平滑密度函数原理，将源区统计数据从同质性改变为非同质性，而非同质性代表着普通社会经济现象普遍特点。§5-7空间数据插值105/128叠置法：Vt=∑Usats/bs式中：t为目标区各个分区序号s为源区各个分区序号

Us为分区s已知统计数据

ats为t区与s区相交面积

bs为s区面积

s人口面积A357B306C102ABC132024013042源区人口和面积目标区与源区面积交集v1=353/7+302/6=25ABCa源区132b目标区106/1281）在源区上叠加一张格网，格网尺寸大小应确保含有足够内插精度2）将源区各个分区平均人口数赋予对应分区各个格网点3）按公式zi，j=(zi-1，j+zi+1，j+zi，j+1+zi，j-1)/4得到相邻四个格网点平均值4）将各个分区格网点值相加，设为Us’，计算其系数p=Us/Us’，并将各个格网点值乘以p，得到调整后各个分区格网点值。5）依此过程继续下去，直到Us与Us’值很靠近，或者对应分区格网点值比较一致时，便能够计算目标区内插值。比重法107/1285555553.33.35553.35555554.44.254.64.63.9554.24.45554.25.35.34.64.45.34.83.63.05.35.34.53.45.35.35.34.55.55.14.64.05.35.13.53.75.55.24.53.35.55.54.94.5区1内插值为v1=5.5+5.3+5.5+5.2+4.5=26abcd108/1281、DEM含义：

DEM（DigitalElevationModels），是国家基础空间数据主要组成部分，它表示地表区域上地形三维向量有限序列，即地表单元上高程集合，数学表示为：z=f（x，y）。DTM：当z为其它二维表面上连续改变地理特征，如地面温度、降雨、地球磁力、重力、土地利用、土壤类型等其它地面诸特征，此时DEM成为DTM（DigitalTerrainModels）。§5.7空间数据插值2、表示法：三、数字高程模型（DEM)生成109/1282.DEM表示法

1）数学方法用数学方法来表示，能够采取整体拟合方法，即依据区域全部高程点数据，用傅立叶级数和高次多项式拟合统一地面高程曲面。也可用局部拟合方法，将地表复杂表面分成正方形规则区域或面积大致相等不规则区域进行分块搜索，依据有限个点进行拟合形成高程曲面。2）图形方法（1）线模式：等高线是表示地形最常见形式。其它地形特征线也是表示地面高程主要信息源，如山脊线、谷底线、海岸线及坡度变换线等。（2）点模式：用离散采样数据点建立DEM是DEM建立惯用方法之一。数据采样能够按规则格网采样，能够是密度一致或不一致；能够是不规则采样，如不规则三角网、邻近网模型等；也能够有选择性地采样，采集山峰、洼坑、隘口、边界等主要特征点。110/1283.DEM主要表示模型

1）

等高线法等高线通常被存放成一个有序坐标点序列，能够认为是一条带有高程值属性简单多边形或多边形弧段。因为等高线模型只是表示了区域部分高程值，往往需要一个插值方法来计算落在等高线以外其它点高程，又因为这些点是落在两条等高线包围区域内，所以，通常只要使用外包两条等高线高程进行插值。

111/1282）规则格网法(Grid)规则网格，通常是正方形，也能够是矩形、三角形等规则网格。规则网格将区域空间切分为规则格网单元，每个格网单元对应一个数值。

规则格网法是把DEM表示成高程矩阵，此时，DEM起源于直接规则矩形格网采样点或由不规则离散数据点内插产生。

结构简单，计算机对矩阵处理比较方便，高程矩阵已成为DEM最通用形式。高程矩阵尤其有利于各种应用。112/128对于每个格网数值有两种不一样解释。第一个是格网栅格观点认为该格网单元数值是其中全部点高程值，即格网单元对应地面面积内高程是均一高度，这种数字高程模型是一个不连续函数。第二种是点栅格观点，认为该网格单元数值是网格中心点高程或该网格单元平均高程值，这么就需要用一个插值方法来计算每个点高程。计算任何不是网格中心数据点高程值，使用周围4个中心点高程值，采取距离加权平均方法进行计算，当然也可使用样条函数和克里金插值方法。

Grid系统也有以下缺点：地形简单地域存在大量冗余数据；

如不改变格网大小,则无法适用于起伏程度不一样地域；对于一些特殊计算如视线计算时，格网轴线方向被夸大；因为栅格过于粗略，不能准确表示地形关键特征,如山峰、洼坑、山脊等；2）规则格网法(Grid)113/1283）不规则三角网（TIN）法

TIN（TriangulatedIrregularNetwork)表示法利用全部采样点取得离散数据，按照优化组合标准，把这些离散点（各三角形顶点）连接成相互连续三角面（在连接时，尽可能地确保每个三角形都是锐角三角形或是三边长度近似相等--Delaunay）。

114/128TIN模型依据区域有限个点集将区域划分为相连三角面网络，区域中任意点落