栅格数据编码方法-《地理信息系统应用》

为减小栅格数据的存储量，主要有以下几种不同的数据结构和编码方法。

1.直接栅格编码

直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录（图2-16和图2-17），也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。

图2-16　直接栅格编码一

图2-17　直接栅格编码二

2.链式编码（Chain Codes）

链式编码又称为弗里曼链码（Freeman，1961）或边界链码。链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东=0，东南=1，南=2，西南=3，西=4，西北=5，北=6，东北=7等八个基本方向（图2-18）。

链式编码的前两个数字表示起点的行、列数，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以0～7的整数代表。如图2-19所示的地物，其链式编码如表2-16所示。

图2-18　链式编码基本方向

图2-19　链式编码示意图

表2-16　链式编码

链式编码对线状和多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，类似矢量数据结构，比较适于存储图形数据。缺点是对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。

3.游程长度编码（Run-length Codes）

游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数；或逐个记录各行（或列）代码发生变化的位置和相应代码，从而实现数据的压缩。

例如对图2-17所示的栅格数据，可按第一种方式沿行方向进行如下游程长度编码：（0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。也可按第二种方式沿列方向进行如下编码：（1，0），（2，2），（4，0）；（1，2），（4，0）；（1，2），（5，3），（6，0）；（1，5），（2，2），（4，3），（7，0）；（1，5），（2，2），（3，3），（8，0）；（1，5），（3，3）；（1，5），（6，3）；（1，5），（5，3）。

游程长度编码对图2-17只用了44个整数就可以表示，而如果用前述的直接编码却需要64个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。

游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。(www.xing528.com)

4.块状编码（Block Codes）

块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单元的代码组成。根据块状编码的原则，对图2-17所示图像可以具体编码如下：（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。其记录单元见图2-20。

一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。

图2-20　对图2-17进行块码编码的记录单元

5.四叉树编码（Quad-tree Codes）

四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值（或灰度）。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

也就是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n×2 n，且n＞1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下、从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。

为了保证四叉树分解能不断地进行下去，要求图形必须为2n×2n的栅格阵列。n为极限分割次数，n+1是四叉树最大层数或最大高度（图2-21和图2-22）。

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

图2-21　用四叉树表示一个多边形

图2-22　图2-21的树状结构

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

四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。

线性四叉树则只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上，由深度可推知子区的大小。

线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。

6.几种编码方法比较分析

几种编码方法比较分析见表2-17。

表2-17　几种编码方法比较分析