45 栅格数据结构search read.pudn.com.ppt

,第四章 空间数据的表达,4-4 矢量数据结构(重点、难点)4-5 栅格数据结构(重点、难点)4-6 混合数据结构和一体化数据结构(重点、难点)5-8 栅格与矢量数据结构的选择与转换(重点、难点),休息,按“ESC”键返回,GIS空间数据结构分类示意图,随着GIS技术的发展，空间数据结构有了新的内容(张超),返回,休息,4-5 栅格数据结构,本节重点：,栅格数据结构的优缺点及各种数据编码的特点。四叉树数据结构的编码方法。(P102-113),本节难点：,四叉树数据结构的编码方法。,返回,休息,1.叙述四种栅格数据存储的压缩编码方法。（2001武大）,作业,思考题,1.采用十进制Morton码分别用线性四叉树和二维行程编码表示下图。（2000武大）,4-5 栅格数据结构,(P92),返回,休息,基于栅格模型的数据结构简称为栅格数据结构,指将空间分割成有规则的网格,在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式。,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,三、空间目标的分层表示方法(P93),在栅格文件中，每个栅格只能赋予唯一的值，因此，某一个栅格若有不同的值，则要分别存贮于不同的文件。例如，对于某个区域来说，其土壤和森林覆盖类型就要分别存贮为土壤和森林数据文件。,返回,休息,4-5 栅格数据结构,三、空间目标的分层表示方法,可以有三种可能的数据组织方法：a、以象元为记录的序列。不同层上同一象元位置上的不同属性值表示为一个列数组；b、以层为基础，每一层又以象元为序记录它的坐标和属性值，每一层记录后再记录下一层；c、以层为基础，但每一层则以多边形为序记录多边形的属性值和充满多边形的各象元的坐标。,返回,休息,地理信息系统原理,三、空间目标的分层表示方法,4-5 栅格数据结构,三、空间目标的分层表示方法,上述三种方法中：节省了许多存储空间，因为N层实际上只存储了一层的象元坐标；方法节省了许多用于存储属性值的空间，同一属性的制图单元的几个象元排列在一起，使地图分析和制图处理较为方便；方法每层每个象元一一记录，它的形式最为简单。,返回,休息,4-5 栅格数据结构,在栅格单元中每个代码本身明确地代表了实体的属性或属性的编码。,四、特点,返回,休息,4-5 栅格数据结构,五、决定栅格单元代码的方法,通常在一个栅格单元上会对应几种不同的属性值，而每一个单元只能取一个值，为了尽量保持地表的真实性，保证最大的信息容量。在这种情况下有不同的取值方法：中心点法、面积占优法、重要性法、百分比法。,返回,休息,4-5 栅格数据结构,五、决定栅格单元代码的方法,返回,休息,4-5 栅格数据结构,五、决定栅格单元代码的方法,返回,休息,4-5 栅格数据结构,五、决定栅格单元代码的方法,返回,休息,4-5 栅格数据结构,五、决定栅格单元代码的方法,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,分辨率与存储单元示意图,(1)在高分辨率的情况下将占据更多的像元或存储单元；(2)栅格模型是通过同样颜色或灰度像元来表达具有相同属性的面状区域的。因此有许多栅格单元或像元与其邻近的若干像元都具有相同的属性值。为了节省存储空间，对栅格数据进行压缩。下面，将介绍四种常用的数据压缩方法。,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,对下一图像的块状编码如下：(1,1,1,0)，(1,2,2,4)，(1,4,1,7),返回,休息,4-5 栅格数据结构,返回,休息,4-5 栅格数据结构,返回,休息,四叉树编码分为：(P102-113)（1）常规四叉树编码（2）线性四叉树编码,4-5 栅格数据结构,4-5 栅格数据结构,常规四叉树编码常规四叉树的生成方法有两种：(1)自顶向下(top-down)的分割方法:先检查全区域，内容不完全相同再四分割，往下逐次递归。(2)从底向上(down-top)的合并方法：首先对栅格数据按一定的顺序检查四个相邻栅格单元的属性值，如果相同，则进行合并，逐次往上递归。,返回,休息,常规四叉树编码的过程,返回,休息,4-5 栅格数据结构,常规四叉树编码常规四叉树的特点如下：(1)运算量较大。因为，大量数据需要重复检查才能确定划分；（如7、8、9、10等格网需要检查4次）(2)占用的存储空间较大。每个结点需要六个变量才能加以表达：一个变量表示父结点指针，四个变量代表四个子结点指针，一个变量代表本结点的灰度或属性值。,返回,休息,4-5 栅格数据结构,线性四叉树编码：,为了克服常规四叉树占用存储空间大的缺点，人们提出了线性四叉树的算法。线性四叉树只存储最后叶结点的信息，即结点的位置、大小和灰度。叶结点位置采用基于四进制或十进制的Morton码表示（加拿大学者Morton于1966年提出）；叶结点的大小用结点的深度或层次表示。Morton码又称为M码。,返回,休息,M码的特点：1、每一位字数都是不大于3的四进制数；2、每经过一次分割，增加一位数字；3、分割的次数越多，所得的子区域越小，相应的Morton码位数越大；,（一）基于四进制的Morton码步骤:1)将十进制的行列号转换成二进制数 2)按MQ码的计算公式 MQ=计算对应的MQ码 分别为栅格单元行列号的二进制数。下表为8行8列研究区域的基于四进制的MQ码计算成果。,返回,休息,例如：,线性四叉树编码,在MQ码的基础上生成线性四叉树的方法有两种：(1)自顶向下(top-down)的分割方法:按常规四叉树的方法进行，并直接生成M码；(2)从底向上(down-top)的合并方法：首先按MQ码的升序排列方式依次检查四个相邻M码对应的属性值，如果相同，则合并为一个大块，否则，存储四个格网的参数值（MQ码、深度、属性值）。第一轮合并完成后，再依次检查四个大块的值（此时，仅需检查每个大块中的第一个值），若其中有一个值不同或某子块已存储，则不作合并而记盘。通过上述方法，直到没有能够合并的子块为止。,返回,休息,自上而下的线性四叉树编码过程,返回,休息,（二）基于十进制的Morton码,方法1:将四进制的MQ码转换成十进制的MD例如：,（二）基于十进制的Morton码,方法2:按位操作 步骤:1)将十进制的行列号转换成二进制数 2)行列交叉得到二进制的Morton码 3)将二进制的Morton码转换成十进制的Morton码,（二）基于十进制的Morton码,例如：已知行列号I=5,J=7，求十进制的Morton码,4-5 栅格数据结构,四叉树编码的优点：1）阵列各部分的分辩率是可变的，边界复杂部分四叉树较高即分级多，分辩率也高，而不需表示许多细节的部分则分级少，分辩率低，因而既可精确表示图形结构又可减少存贮量；2）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易，由于记录结点地址，能直接在四叉树中的走向路径，也可以换算出它在整个栅格区域中行列位置；,返回,休息,二维行程编码(P111),在生成的线性四叉树中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，即得到二维行程编码。这种二维行程编码利用了线性四叉树的地址码，但没有结构规则的四叉树，甚至已失去了四叉树的概念。然而它比规则的四叉树更省存储空间，而且对以后的插入、删除和修改等操作，因不必保持完整的四叉树构形而变得相当简便。,返回,休息,二维行程编码,返回,休息,八叉树数据结构(P115),八叉树数据结构是从四叉树数据结构直接发展而来的，其原理是将空间区域不断地分解为八个同样大小的子区域（即将一个六面的立方体分解为八个相同的大小的小立方体）分解的次数越多，子区域就越小，一直到同一区域的属性单一为止。,按从上到下合并的方式来说，就是将研究区域先按一定的分辨率将三维空间划分为三维栅格网格，然后按规定的顺序每次比较八个相邻的栅格单元，如果其属性值相同则合并，否则就记盘，依次递归运算，直到每个子区域均为单值为止。,八叉树同样分为常规八叉树和线性八叉树，常规八叉树的结点要记录十个值，即八个指向子节点的指针，一个指向父结点的指针和一个属性值。而线性八叉树只需记录叶结点的地址码和属性值。,八叉树的构成方法亦可按线性四叉树的构造原理。首先计算扩展的Morton码，将二维自变量I，J扩展为三维自变量I，J，K，按位操作运算，很容易得到八进制或十进制的Morton码。,例：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,