栅格数据结构.pptx

《栅格数据结构.pptx》由会员分享，可在线阅读，更多相关《栅格数据结构.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、GISGIS空间数据结构分类示意图随着GISGIS技术的发展，空间数据结构有了新的内容(张超)返回返回休息休息第1页/共51页4 4-5 5 栅 格 数 据 结 构本节重点：栅格数据结构的优缺点及各种数据编码的特点。四叉树数据结构的编码方法。(P(P102-113102-113)本节难点：四叉树数据结构的编码方法。返回返回休息休息第2页/共51页 1.叙述四种栅格数据存储的压缩编码方法。（2001武大）作业第3页/共51页思考题 1.采用十进制Morton码分别用线性四叉树和二维行程编码表示下图。（2000武大）ABBBAABBBAABBBAA第4页/共51页4 4-5 5 栅 格 数 据 结

2、 构(P(P9292)返回返回休息休息 基于栅格模型的数据结构简称为栅格数据结构,指将空间分割成有规则的网格,在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式。第5页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第6页/共51页4 4-5 5 栅 格 数 据 结 构三、空间目标的分层表示方法(P(P9393)在栅格文件中，每个栅格只能赋予唯一的值，因此，某一个栅格若有不同的值，则要分别存贮于不同的文件。例如，对于某个区域来说，其土壤和森林覆盖类型就要分别存贮为土壤和森林数据文件。返回返回休息休息第7页/共51页4 4-5 5 栅 格 数 据 结 构三、空间目标的分

3、层表示方法 可以有三种可能的数据组织方法：a a、以象元为记录的序列。不同层上同一象元位置上的不同属性值表示为一个列数组；b b、以层为基础，每一层又以象元为序记录它的坐标和属性值，每一层记录后再记录下一层；c c、以层为基础，但每一层则以多边形为序记录多边形的属性值和充满多边形的各象元的坐标。返回返回休息休息第8页/共51页地理信息系统原理三、空间目标的分层表示方法 第9页/共51页4 4-5 5 栅 格 数 据 结 构三、空间目标的分层表示方法 上述三种方法中：节省了许多存储空间，因为N N层实际上只存储了一层的象元坐标；方法节省了许多用于存储属性值的空间，同一属性的制图单元的几个象元排列

4、在一起，使地图分析和制图处理较为方便；方法每层每个象元一一记录，它的形式最为简单。返回返回休息休息第10页/共51页4 4-5 5 栅 格 数 据 结 构 在栅格单元中每个代码本身明确地代表了实体的属性或属性的编码。四、特点 返回返回休息休息第11页/共51页4 4-5 5 栅 格 数 据 结 构五、决定栅格单元代码的方法 通常在一个栅格单元上会对应几种不同的属性值，而每一个单元只能取一个值，为了尽量保持地表的真实性，保证最大的信息容量。在这种情况下有不同的取值方法：中心点法、面积占优法、重要性法、百分比法。返回返回休息休息第12页/共51页4 4-5 5 栅 格 数 据 结 构五、决定栅格单

5、元代码的方法 返回返回休息休息第13页/共51页4 4-5 5 栅 格 数 据 结 构五、决定栅格单元代码的方法 返回返回休息休息第14页/共51页4 4-5 5 栅 格 数 据 结 构五、决定栅格单元代码的方法 返回返回休息休息第15页/共51页4 4-5 5 栅 格 数 据 结 构五、决定栅格单元代码的方法 返回返回休息休息第16页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第17页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第18页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第19页/共51页4 4-5 5 栅 格 数 据 结

6、构返回返回休息休息第20页/共51页4 4-5 5 栅 格 数 据 结 构分辨率与存储单元示意图 (1)(1)在高分辨率的情况下将占据更多的像元或存储单元；(2)(2)栅格模型是通过同样颜色或灰度像元来表达具有相同属性的面状区域的。因此有许多栅格单元或像元与其邻近的若干像元都具有相同的属性值。为了节省存储空间，对栅格数据进行压缩。下面，将介绍四种常用的数据压缩方法。返回返回休息休息第21页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第22页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第23页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息

7、第24页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第25页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第26页/共51页4 4-5 5 栅 格 数 据 结 构 对下一图像的块状编码如下：(1,1,1,0)，(1,2,2,4)，(1,4,1,7)返回返回休息休息第27页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第28页/共51页4 4-5 5 栅 格 数 据 结 构返回返回休息休息第29页/共51页四叉树编码分为：(P(P102-113102-113)（1 1）常规四叉树编码 （2 2）线性四叉树编码4 4-5 5 栅格数据结构第3

8、0页/共51页4 4-5 5 栅 格 数 据 结 构常规四叉树编码常规四叉树的生成方法有两种：(1)(1)自顶向下(top-down)(top-down)的分割方法:先检查全区域，内容不完全相同再四分割，往下逐次递归。(2)(2)从底向上(down-top)(down-top)的合并方法：首先对栅格数据按一定的顺序检查四个相邻栅格单元的属性值，如果相同，则进行合并，逐次往上递归。返回返回休息休息第31页/共51页常 规 四 叉 树 编 码 的 过 程返回返回休息休息第32页/共51页4 4-5 5 栅 格 数 据 结 构常规四叉树编码常规四叉树的特点如下：(1)(1)运算量较大。因为，大量数据

9、需要重复检查才能确定划分；（如7 7、8 8、9 9、1010等格网需要检查4 4次）(2)(2)占用的存储空间较大。每个结点需要六个变量才能加以表达：一个变量表示父结点指针，四个变量代表四个子结点指针，一个变量代表本结点的灰度或属性值。返回返回休息休息第33页/共51页4 4-5 5 栅 格 数 据 结 构线性四叉树编码：为了克服常规四叉树占用存储空间大的缺点，人们提出了线性四叉树的算法。线性四叉树只存储最后叶结点的信息，即结点的位置、大小和灰度。叶结点位置采用基于四进制或十进制的MortonMorton码表示（加拿大学者MortonMorton于19661966年提出）；叶结点的大小用结点

10、的深度或层次表示。MortonMorton码又称为M M码。返回返回休息休息第34页/共51页M M码的特点：1 1、每一位字数都是不大于3 3的四进制数；2 2、每经过一次分割，增加一位数字；3 3、分割的次数越多，所得的子区域越小，相应的MortonMorton码位数越大；第35页/共51页（一）基于四进制的MortonMorton码步骤:1):1)将十进制的行列号转换成二进制数 2)2)按M MQ Q码的计算公式 M MQ Q=计算对应的M MQ Q码 分别为栅格单元行列号的二进制数。下表为8 8行8 8列研究区域的基于四进制的M MQ Q码计算成果。返回返回休息休息第36页/共51页例

11、如：第37页/共51页线性四叉树编码在M MQ Q码的基础上生成线性四叉树的方法有两种：(1)(1)自顶向下(top-down)(top-down)的分割方法:按常规四叉树的方法进行，并直接生成M M码；(2)(2)从底向上(down-top)(down-top)的合并方法：首先按M MQ Q码的升序排列方式依次检查四个相邻M M码对应的属性值，如果相同，则合并为一个大块，否则，存储四个格网的参数值（M MQ Q码、深度、属性值）。第一轮合并完成后，再依次检查四个大块的值（此时，仅需检查每个大块中的第一个值），若其中有一个值不同或某子块已存储，则不作合并而记盘。通过上述方法，直到没有能够合并的

12、子块为止。返回返回休息休息第38页/共51页自 上 而 下 的 线 性 四 叉 树 编 码 过 程返回返回休息休息第39页/共51页（二）基于十进制的MortonMorton码 方法1:将四进制的MQ码转换成十进制的MD例如：第40页/共51页（二）基于十进制的MortonMorton码 方法2:按位操作 步骤:1)将十进制的行列号转换成二进制数 2)行列交叉得到二进制的Morton码 3)将二进制的Morton码转换成十进制的Morton码第41页/共51页（二）基于十进制的MortonMorton码 例如：已知行列号I=5,J=7，求十进制的MortonMorton码 第42页/共51页4

13、 4-5 5 栅 格 数 据 结 构四叉树编码的优点：1 1）阵列各部分的分辩率是可变的，边界复杂部分四叉树较高即分级多，分辩率也高，而不需表示许多细节的部分则分级少，分辩率低，因而既可精确表示图形结构又可减少存贮量；2 2）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易，由于记录结点地址，能直接在四叉树中的走向路径，也可以换算出它在整个栅格区域中行列位置；返回返回休息休息第43页/共51页二维行程编码(P(P111111)在生成的线性四叉树中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，即得到二维行程编码。这种二维行程编码利

14、用了线性四叉树的地址码，但没有结构规则的四叉树，甚至已失去了四叉树的概念。然而它比规则的四叉树更省存储空间，而且对以后的插入、删除和修改等操作，因不必保持完整的四叉树构形而变得相当简便。返回返回休息休息第44页/共51页二维行程编码返回返回休息休息第45页/共51页八叉树数据结构(P115)八叉树数据结构是从四叉树数据结构直接发展而来的，其原理是将空间区域不断地分解为八个同样大小的子区域（即将一个六面的立方体分解为八个相同的大小的小立方体）分解的次数越多，子区域就越小，一直到同一区域的属性单一为止。第46页/共51页 按从上到下合并的方式来说，就是将研究区域先按一定的分辨率将三维空间划分为三维

15、栅格网格，然后按规定的顺序每次比较八个相邻的栅格单元，如果其属性值相同则合并，否则就记盘，依次递归运算，直到每个子区域均为单值为止。第47页/共51页 八叉树同样分为常规八叉树和线性八叉树，常规八叉树的结点要记录十个值，即八个指向子节点的指针，一个指向父结点的指针和一个属性值。而线性八叉树只需记录叶结点的地址码和属性值。第48页/共51页 八叉树的构成方法亦可按线性四叉树的构造原理。首先计算扩展的Morton码，将二维自变量I，J扩展为三维自变量I，J，K，按位操作运算，很容易得到八进制或十进制的Morton码。第49页/共51页 例：I=1 0 0 1 J=4 1 0 0 K=3 0 1 1二进制的Morton码=010 001 101八进制的Morton码=2 1 5十进制的Morton码=2X82+1X81+5X80=141第50页/共51页感谢您的欣赏第51页/共51页