（四）四叉树编码（Quadtree Encoding）

四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将 2ⁿ×2ⁿ 像元阵列的区域，逐步分解为包含单一类型的方形区域， 最小的方形区域为一个栅格像元。图像区域划分的原则是将区域分为大小相同的象限，而每一个象限又可根据一定规则判断是否继续等分为次一层的四个象限。其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的几种地物时，则不再继续划分否则一直分到单个栅格像

元为止。这种分块过程示于图 3－11。而块状结构则用四叉树来描述，习惯上称为四叉树编码（如图 3－12）。

所谓四叉树结构，即把整个 2^ｎ×2^ｎ像元组成的阵列当作树的根结点，n 为极限分割次数，n＋1 为四分树的最大高度或最大层数。每个结点有分别代表西北、东北、西南、东南四个象限的四个分支。四个分支中要么是树叶， 要么是树叉。树叉、树叶用方框表示，它说明该四分之一范围全属多边形范围（黑色）或全不属多边形范围（空心四方块），因此不再划分这些分枝； 树用圆圈表示，它说明该四分之一范围内，部分在多边形内，另一部分在多边形外，因而继续划分，直到变成树叶为止。

为了在计算机中既能以最小的冗余存储与图像对应的四叉树，又能方便地完成各种图形操作，专家们已提出多种编码方式。下面介绍美国马里兰大学地理信息系统中采用的编码方式。该方法记录每个终点（或叶子结点）的地址和值，值就是子区的代码，其中地址包括两个部分，共占有 32 位（二进制），最右边四位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示。0，1， 2，3 分别表示 NW、NE、SW、SE，从右边第五位开始 2n 字节记录这些方向。如图 3－9 第 10 个结点深度为 4，第一层处于 SW 象限记为 1，第四层处于象限 SE，记为 3，表示为二进制为：

20 位 8 位 4 位

0000⋯00100001110100

每层象限位置由二位二进制表示，共八位。上述二进制换算成十进制整数为 2164。这样，记录了各个叶子的地址，再记上相应的代码值，就记录了整个图像，并可在此编码的基础上进行多种图像操作。

四叉树编码有许多优点：①容易而有效地计算多边形的数量特征。②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高，即分级多，分辨率也高，而不需表示的细节部分则分级少，分辨率低。因而既可精确表示图形结构，又可减少存储量。③栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易。④多边形中嵌套不同类型小多边形的表示较方便。

四叉树编码的最大缺点是，树状表示的变换不具有稳定性，相同形状和大小的多边形可能得出不同四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形，即所谓“洞”的结构存在，使越来越多的地理信息系统工作者对四叉树结构很感兴趣。上述这些压缩数据的方法应视图形的复杂情况合理选用，同时应在系统中备用相应的程序。另外，用户的分析目的和分析方法也决定着压缩方法的选取。