休息5栅格数据结构线性四叉树编码.ppt

作业 1.叙述四种栅格数据存储的压缩编码方法。（2001武大） 思考题 1.采用十进制Morton码分别用线性四叉树和二维行程编码表示下图。 （2000武大） §4-5 栅格数据结构 四叉树编码分为：(P102-113) （1）常规四叉树编码 （2）线性四叉树编码 M码的特点： 1、每一位字数都是不大于3的四进制数； 2、每经过一次分割，增加一位数字； 3、分割的次数越多，所得的子区域越小，相应的Morton码位数越大； 例如： 八叉树数据结构(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 §4-5 栅格数据结构 常规四叉树编码 常规四叉树的生成方法有两种： (1)自顶向下(top-down)的分割方法:先检查全区域，内容不完全相同再四分割，往下逐次递归。 (2)从底向上(down-top)的合并方法：首先对栅格数据按一定的顺序检查四个相邻栅格单元的属性值，如果相同，则进行合并，逐次往上递归。 返回 休息 常规四叉树编码的过程 返回 休息 §4-5 栅格数据结构 常规四叉树编码 常规四叉树的特点如下： (1)运算量较大。因为，大量数据需要重复检查才能确定划分；（如7、8、9、10等格网需要检查4次） (2)占用的存储空间较大。每个结点需要六个变量才能加以表达：一个变量表示父结点指针，四个变量代表四个子结点指针，一个变量代表本结点的灰度或属性值。 返回 休息 §4-5 栅格数据结构 线性四叉树编码： 为了克服常规四叉树占用存储空间大的缺点，人们提出了线性四叉树的算法。线性四叉树只存储最后叶结点的信息，即结点的位置、大小和灰度。叶结点位置采用基于四进制或十进制的Morton码表示（加拿大学者Morton于1966年提出）；叶结点的大小用结点的深度或层次表示。Morton码又称为M码。 返回 休息 （一）基于四进制的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，求十进制的