地理信息系统算法.ppt

《地理信息系统算法.ppt》由会员分享，可在线阅读，更多相关《地理信息系统算法.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第第八八章章 空间数据压缩算法GISGIS的内部数据结构的内部数据结构矢量结构和栅格结构矢量结构和栅格结构 内部数据结构：描述地理实体的数据本身的组织方法。内部数据结构基本上可分为两大类：矢量结构和栅格结构（也可以称为矢量模型和栅格模型）（右图所示）。两类结构都可用来描述地理实体的点、线、面三种基本类型。空间数据编码是空间数据结构的实现，即将根据地理信息系统的目的和任务所搜集的、经过审核了的地形图、专题地图和遥感影像等资料按特定的数据结构转换为适合于计算机存储和处理的数据的过程。由于地理信息系统数据量极大，一般采用压缩数据的编码方式以减少数据冗余。一、柵格数据结构及其压缩栅格结构是最简单最直

2、接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。在栅格结构中：点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元 在线上；面或区域用记有区域属性的相邻栅格单元的集 合表示，每个栅格单元可有多于两个 的相邻单元同属一个区域。（a）点 （b）线 （c）面点、线、区域的格网栅格数据的获取栅格数据的获取 1.遥感方法获取(航天与航空)；2.图片扫描获取(纸介质的地图等扫描)；3.矢量数据转换而来；4.由平面上行距,列距固定的点抽

3、样而来主要包括:(1)中心归属法(2)长度占优法 (3)面积占优法栅格数据（栅格数据（栅格数据（栅格数据（1 1）栅格数据（栅格数据（2）栅格数据（栅格数据（3）上海东方明珠电视塔上海东方明珠电视塔故宫故宫栅格数据（栅格数据（4）SPOT XS 20m*20m 牡丹水庫band G,R,IR網格資料關於衛星影像栅格数据结构栅格数据结构栅格数据的组织数据文件像元1I坐标J坐标层1属性值层2属性值层N属性值像元2像元N数据文件层1像元1I坐标J坐标属性值层2层N像元2数据文件层1多边形1属性值像元1坐标像元N坐标层2层N多边形N节省空间节省空间形式简单形式简单方便制图方便制图柵格数据的压缩算法栅格

4、数据文件记录有3个基本方式：基于像元、基于层和基于面域。这三种方式都离不开对像元坐标和属性的记录。因此基于柵格的空间数据压缩的实质是研究柵格数据的编码，通过编码尽量减少像元数量的存储。其方法有三大类：（1）从减少记录像元的数量入手；（2）从减少像元的记录信息量入手；（3）前两者的结合。柵格数据的压缩分为无损压缩技术和有损压缩技术。（1）无损压缩技术是指压缩过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息；（2）信息有损压缩是指为了提高压缩效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。柵格数据的压缩1.直接栅格编码直接栅格编码 这是最简单直观

5、而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序。下图为一些常用的柵格排列顺序。一些常用的栅格排列顺序 2.2.链式编码（链式编码（Chain CodesChain Codes）链式编码又称为弗里曼链码Freeman或边界链码。多边形边界可以表示为：由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可以定为：东=

6、0，东南=1，南=2，西南=3，西=4，西北=5，北=6，东北=7，8个基本方向。S/2W/4WN/5N/6EN/7E/0WS/3ES/13,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5例子：如果再确定原点为像元(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。S/2W/4WN/5N/6EN/7E/0WS/3ES/1优点：优点：链式边码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运

7、算十分方便，比较适合于存储图形数据。缺点：缺点：对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。3.3.游程长度编码（游程长度编码（Run-Length CodesRun-Length Codes）游程长度编码是栅格数据压缩的重要编码方法。游程指相邻同值网格的数量，游程长度编码结构是逐行将相邻同值的网格合并记录合并后网格的值及合并网格的长度，其目的是压缩柵格数据量，消除数据间的冗余。游程长度编码结构的建立方法是：将柵格矩阵的数据序列X1,X2,Xn，映射为相应的二元组序列（Ai,Pi）

8、,i=1,2,K,且Kn。其中，A为属性值，P为游程，K为游程序号。面域柵格矩阵结构二元映射序号二元组序列1（A，2）2（B，3）3（A，1）4（C，3）5（A，1）6（D，1）7游程长度编码表示柵格矩阵数据游程长度编码表示柵格矩阵数据游程编码能否压缩数据量，主要决定于柵格数据的性质，通常可通过事先测试，估算图层的数据冗余度Re:Re=1-Q/mn 式中，Q为图层内相邻属性值变化次数的累加和；m为图层网格的行数；n为图层网格的列数。当Re的值大于1/5的情况下，表明柵格数据的压缩可取得明显的效果。其压缩效果，可由压缩比S=n/K来表征，即压缩比的值愈大，表示压缩效果愈明显。特点：游程长度编码在

9、栅格压缩时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。4.4.块式编码块式编码(Block Codes)(Block Codes)块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。M M R M M M M MM M R R M R M MM R R R R R R MM R R R R R R MM R R R R R R MM R R R R R R MM M

10、 R R R R R MM M M R R M M MM M R M M M M M1 2 3 4 5 6 7 8M M R R M R M MM R R R R R R MM R R R R R R MM R R R R R R MM R R R R R R MM M M R R M M MM M R R R R R MM M R M M M M M1 2 3 4 5 6 7 8M M R R M R M MM R R R R R R MM R R R R R R MM R R R R R R MM R R R R R R MM M M R R M M MM M R R R R R M1，1

11、，2，M；1，3，1，R；1，4，1，M；1，5，1，M；1，6，1，M；1，7，2，M2，3，2，R；2，5，1，M；2，6，1，R3，1，1，M；3，2，1，R；3，5，3，R；3，8，1，M4，1，1，M；4，2，3，R;4，8，1，M5，1，1，M；5，8，1，M特点：块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高以小块记录区域边界地段，以此达到压缩的目的。因此块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作

12、时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。5.5.差分映射法差分映射法所谓差分映射法，就是选择某一参照值对有关柵格的属性值进行求差运算，根据差值得到一个新的柵格数据层。参照值的选择有多种方式：（1）分行选取：则可选为该行首列的属性值，也可选为该行的 属性平均值；（2）全区选取：则可选为首行首列的属性值，也可选为全区的 属性平均值。如下图所示：12012015015015020020020013013017017017023023023013513513518018018025025014014014020020020020027014514514521021021021021

13、0柵格数据示例120 0 303030808080130 0 404040100 100 100135 0 0454545115 115140 0 060606060130145 0 06565656565数据差分映射结果行号第一列第一列第一列第一列第一列第一列第一列第一列前后前后前后前后前后前后前后前后1112121212121212122221212121212121322212121212121214222121212121212252221212121212121总99105105105105105105106差分映射前后柵格数据记录长度对比结论：由上表可见，所需字节数由原来的79减少

14、为 44，减少44.3%。6.6.四叉树编码四叉树编码(Quadtree Encoding)(Quadtree Encoding)四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。区域分割原则：将欲分解区域等分为四个象限，再根据各个象限的象元值是否单一决定要不要再分。如果单一则不再分割，否则同法再分，直到所有象限的象元属性值相同为止。(a)四叉树分割(a)(a)的的四叉树四叉树编码编码 其中最上面的那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点

15、分别对应于整个图形的四个象限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶子结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号如图所示，共有40个叶子结点，也就是原图被划分为40个大小不等的方形子区，图的最下面的一排数字表示各子区的代码。由上面图形的四叉树分解可见，四叉树中象限的尺寸是大小不一的，位于较高层次的象限较大，深度小即分解次数少，而低层次上的象限较小，深度大即分解次数多，这反映了图上某些位置单一地物分布较广而另一些位置上的地物比较复杂，变

16、化较大。正是由于四叉树编码能够自动地依照图形变化而调整象限尺寸，因此它具有极高的压缩效率。采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为 的栅格阵列，n为极限分割数，n+1为四叉树的最大高度或最大层数，上图为22的栅格，因此最多划分三次，最大层数为4，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为 的图像。为了使计算机既能以最小的冗余存储图像对应的四叉树，又能方便地完成各种图形图像操作，专家们已提出了多种编码方式，下面介绍美国马里兰大学地理信息系统中采用的编码方式，该方法记录了终止结点（或叶子结点）的地址和值，值就是子区的代码，其中地址包括两个部分，共32位（二

17、进制），最右边4位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示，0，1，2，3分别表示SW、SE、NW、NE，从右边第5位开始2n字节记录这些方向。如上图表示的第六个结点深度为3，第一层处于SW象限，记为0；第二层处于NE象限，记为3，第三层处于NW象限，记为2，表示为二进制为：0000 000(22位)；001110（6位）；0011（4位）每层象限位置由两位二进制数表示，共6位，十进制整数为227。这样，记录了各个叶子的地址，再记上相应代码值，就记录了这个图像，并可在此编码基础上进行多种图像操作。事实上，叶结点的地址可以直接

18、由子区左下角的行列坐标，按二进制按位交错得到。如对于6号叶子结点，在以图像左下角为原点的行列坐标系中，其左下角行、列坐标为（3，2），表示为二进制分别为011和010，按位交错就是001110，正是6号地块。特点：四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。u链式编码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；u游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易；u块码和四叉树码具有区域性质，又具有可变的分辨率，有较高

19、的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。几种编码的比较二、矢量数据结构及其压缩定义：通过记录坐标的方式尽可能精确地表示地理实体，即地理实体的形状和位置是由一组所在的坐标参考系中坐标确定的。矢量数据结构是人们较为习惯的一种表示空间数据的方法特点：定位明显、属性隐含，其定位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实现，当然有些地方也有所便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作

20、时则比较困难。在GIS中，地理实体的空间特征首先抽象为点、线、面、体四种基本类型，而这些特征可以用颜色、符号、注记来区分，并由图例、图符和描述性文本来解释。矢量数据（矢量数据（矢量数据（矢量数据（1 1）矢量数据（矢量数据（2）矢量数据（矢量数据（3）矢量矢量+栅格（栅格（1 1）矢量+栅格（2）矢量数据结构获取方法矢量数据结构获取方法 (1)手工数字化法；(2)手扶跟踪数字化法；(3)数据结构转换法。矢量数据基本类型矢量数据基本类型 ；(1)点 (2)线 (3)面 矢量数据基本类型矢量数据基本类型-点点 点点是点状物或者是可以用点是点状物或者是可以用点(由单独一对由单独一对坐标定位）的一切地

21、理或制图实体，坐标定位）的一切地理或制图实体，有特定有特定的位置。图件的比例尺决定了能否把现实世的位置。图件的比例尺决定了能否把现实世界的现象表示为点特征界的现象表示为点特征。它它有有可可能能是是点点状状地地物物、面面状状地地物物的的中中心心点点、线线状状地地物的交点、定位点、注记等。物的交点、定位点、注记等。例子：水基准点、建筑物、井、观测点、高程点例子：水基准点、建筑物、井、观测点、高程点 在在GISGIS中点有几种类型。线的起点、终点、交点（三条中点有几种类型。线的起点、终点、交点（三条以上坐标链的交汇点）、面的首尾点我们称之为结点以上坐标链的交汇点）、面的首尾点我们称之为结点（node

22、node），而线的中间部分称为中间点（角点），而线的中间部分称为中间点（角点vertexvertex）。）。实体点实体点(Entity point)(Entity point)：用来代表一个实体；：用来代表一个实体；注记点注记点(Text point)(Text point)：用于定位注记；：用于定位注记；内点内点(Label point)(Label point)：用于记录多边形的属性，存在：用于记录多边形的属性，存在于多边形内；于多边形内；结点结点(Node)(Node)：表示线的终点和起点、：表示线的终点和起点、交点交点；中间点中间点(角点，角点，VertexVertex)：表示线段和弧

23、段的内部点。：表示线段和弧段的内部点。矢量数据基本类型矢量数据基本类型-点点线有方向，线有方向，两个结点之间的线又叫弧段（两个结点之间的线又叫弧段（arcarc）。）。弧段特征可用来定位和描述两点之间连线的地理弧段特征可用来定位和描述两点之间连线的地理信息信息。线线是对线状地物或地物运动轨迹的全部或部分的是对线状地物或地物运动轨迹的全部或部分的描述，可以定义为由直线元素组成的各种线性要素，描述，可以定义为由直线元素组成的各种线性要素，直线元素由两对以上的坐标定义。最简单的线实体只直线元素由两对以上的坐标定义。最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。存储它的起止点坐标、属性、

24、显示符等有关数据。矢量数据基本类型矢量数据基本类型-线线由一系列坐标点表示，有以下特征：由一系列坐标点表示，有以下特征：实体长度：从起点到终点的总长；实体长度：从起点到终点的总长；弯曲度：用于表示象道路拐弯时弯曲的程度；弯曲度：用于表示象道路拐弯时弯曲的程度；方向性：如水流从上游到下游，公路则有单双向之方向性：如水流从上游到下游，公路则有单双向之分；分；线实体包括：线段、边界、链、网络、多边形线等。线实体包括：线段、边界、链、网络、多边形线等。矢量数据基本类型矢量数据基本类型-线线复杂的多边形内可以有复杂的多边形内可以有“岛（洞）岛（洞）”（一种特殊的弧（一种特殊的弧段，这种弧段坐标链头尾相接

25、，独立围成一个封闭的段，这种弧段坐标链头尾相接，独立围成一个封闭的区域。弧段的端点总是结点，而岛弧段端点并非是三区域。弧段的端点总是结点，而岛弧段端点并非是三条或三条以上坐标链的交汇点，这种端点称为岛结点）。条或三条以上坐标链的交汇点，这种端点称为岛结点）。面（多边形面（多边形polygonpolygon）是对面状地理实体的表示，）是对面状地理实体的表示，由一个封闭的坐标点序列外加内点表示。但由一个封闭的坐标点序列外加内点表示。但多边形矢多边形矢量编码，不但要标识位置和属性，更重要的是表达拓量编码，不但要标识位置和属性，更重要的是表达拓扑特征扑特征,如形状、邻域和层次结构等。多边形由一条如形状

26、、邻域和层次结构等。多边形由一条或一条以上首尾相连的弧段组成。一个弧段总是被两或一条以上首尾相连的弧段组成。一个弧段总是被两个而且只被两个多边形所共有。个而且只被两个多边形所共有。矢量数据基本类型矢量数据基本类型-面（多边形）面（多边形）多边形有以下特征：多边形有以下特征：面积范围；面积范围；周长；周长；独立性或与其它地物相邻：如北京及周边省市；独立性或与其它地物相邻：如北京及周边省市；内部区域内部区域简单多边形简单多边形复杂多边形复杂多边形 矢量数据基本类型矢量数据基本类型-面（多边形）面（多边形）矢量数据的压缩矢量数据的压缩包括两个方面的内容：(1)在不扰乱拓扑关系的前提下，对采样点数据进

27、行合理的抽稀；(2)对矢量坐标数据重新进行编码，以减少所需要的存储空间。注注:矢量数据的压缩往往是不可逆的，数据压缩后数据量变小了，但数据的精度降低了。矢量数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，加快后继处理的速度。下面介绍几种常用的矢量数据的压缩算法，以及它们之间的异同点。1.1.间隔取点法：间隔取点法：每隔K个点取一点，或舍去那些离已选点比规定距离更近的点，但首、末点一定要保留。如下图所示。特点：这种方法可大量压缩数字化仪用连续方法获取的点列中的点、曲率显著变化的点，但不一定能恰当地保留方向上曲率显著变化的点。由(a)舍去每两点中一点得(a)和由(b)的仅仅保留与已选

28、点距离超过临界值的点得(b)(a)(a)临界值(b)(b)2.2.垂距法和偏角法垂距法和偏角法这两种方法都是按垂距或偏角的限差，选取符合或超过限差的点，其过程如图所示。垂 距 算 法4123123412341234124原来的线对点2测试距离大于规定的限差2点保留对点3测试距离大于规定的限差3点舍去化简后的线限差4123123412341234124原来的线对点2测试角度大于规定的限差2点保留对点3测试角度大于规定的限差3点舍去化简后的线限差偏 角 算 法这两种方法虽然不能同时考虑相邻点间的方向和距离，且有可能舍去不该舍去的点，但较前一种方法有进步。3.3.道格拉斯道格拉斯普克法普克法(Dou

29、glasPeucker)(DouglasPeucker)道格拉斯普克法示意图 基本思路是：对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax，用dmax与限差D相比：若dmaxD，这条曲线上的中间点全部舍去；若dmaxD，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法。4.4.光栏法光栏法 光栏法原理图示 光栏法的基本思想是：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为pi，i1，2，n，光栏口经为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：1、连接p1和p2点，过

30、p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p2a2p2d2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。2、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p1的垂线，该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1p3b2d2，若b1或b2点落在原扇形外面，则用c1或c2取代。此时用p1b1和p1c2定义一个新的扇形，这

31、当然是口径(b1c2)缩小了的“光栏”。3、检查下一节点，若该点在新扇形内，则重复第(2)步；直到发现有一个节点在最新定义的扇形外为止。4、当发现在扇形外的节点，如p4，此时保留p3点，以p3作为新起点，重复13。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。曲线压缩算法的比较如果某种矢量数据的压缩算法既能精确地表示数据，又能最大限度地淘汰不必要的点，那就是一种好的算法。具体可以依据简化后曲线的总长度、总面积、坐标平均值等与原始曲线的相应数据的对比来判别。通过分析可以发现，大多数情况下道格拉斯普克法的压缩算法较好，但必须在对整条曲线数字化完成

32、后才能进行，且计算量较大；光栏法的压缩算法也很好，并且可在数字化时实时处理，每次判断下一个数字化的点，且计算量较小；垂距法算法简单，速度快，但有时会将曲线的弯曲极值点p值去掉而失真。面域的数据压缩算法面域的空间数据压缩过程可以看成是组成其边界的曲线段的分别压缩，每段边界曲线的压缩过程如前所述。但有两个问题需要注意。1.1.封闭曲线的数据压缩封闭曲线的数据压缩面域由首尾相连的封闭曲线组成。可以人为地将该封闭线分割为首尾相连的两段曲线，然后可以按前面的方法进行压缩。曲线的分割的原则是：(1)原节点是分割点之一；(2)离原节点最远的下一节点是分割点之二。如右图所示，多边形P的边界曲线可以分割为AMP和BNA两段，进而对曲线段AMB、BNA分别进行压缩。MANBP2.2.公共节点的取舍问题公共节点的取舍问题为了防止产生数据冗余，当前后曲线段过渡时很平缓，曲线段公共节点可以不成为特征点，即该点前后的两段曲线可以直接用该点前后的两个特征点的连线来代替。因此，在处理面域空间数据压缩时，可以在边界曲线分段压缩的基础上，增加一个步骤，即对边界曲线的端点进行可删性检验：如果前一曲线最后提取的中间特征点与后一曲线最先提取的中间特征点之间的曲线满足级差控制条件，则两条曲线的连接节点可以删减；否则，不可删减。注意：注意：在处理公共节点的取舍时要慎重！在处理公共节点的取舍时要慎重！APB123