栅格数据编码

4.4.3　栅格数据编码

存储栅格数据主要是记录栅格数据中每个像元的行号、列号和编码值，其中行号、列号表示了像元所在的位置，而编码值则代表该像元所具有的含义。我们可以直接将栅格数据看作一个数据矩阵，逐行(或逐列)地记录每个栅格单元的代码，这种直接编码方式可以准确记录栅格数据的所有信息，简单直观，但是对于分辨率高的数据，直接编码的数据存储量将成倍增长，这就会束缚栅格数据在GIS中的广泛使用，因此，栅格数据的压缩存储方法被广泛使用。压缩编码的目的就是用尽可能少的数据量记录尽可能多的信息，其类型分为信息无损编码及信息有损编码，信息无损编码在编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息，信息有损编码则为了提高编码效率，会在压缩过程中损失一部分相对不太重要的信息，解码时这部分信息也难以恢复。在地理信息系统中，压缩编码多采用信息无损编码，目前主要使用的压缩编码方式主要包括以下几种。

1.链式编码(chain codes)

链式编码又称为弗里曼链码(Freeman，1961)或边界链码。链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为由某一起始点开始的栅格单元链。该单元链按其8邻域设定8个方向，这8个方向分别是:东=0，东南=l，南=2，西南=3，西=4，西北=5，北=6，东北=7(如图4-14所示)，基于这8个方向值的确定，该链每向前走一步便记录其所走方向值。在此，链式编码的前两个数字表示起点的行、列数，从第三个数字开始表示栅格前进方向，例如，对如图4-14所示的多边形，其起始点为6行4列，则其链式编码为:6，4，7，6，0，0，1，0，0，0，0，1，0，3，4，5，3，3，2，4，4，6，6，5，3，5。

图4-14　链式编码记录方向及多边形图

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

2.行程编码(run-length code)

行程编码，也叫游程长度编码，是栅格数据压缩的重要编码方法，它的基本思路是在一幅栅格图像中，常常有行(或列)方向上相邻的若干点具有相同的属性代码，在逐行记录时可采取一定方法压缩那些重复内容。行程编码方式有多种，都是沿行进方向进行压缩，原理大同小异，所以在实际操作中都可以采用。

第一种行程编码是变长编码，是在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，如对图4-15所示多边形进行编码，相应的变长编码结果如表4-4(a)所示。

第二种行程编码是值点编码，值点编码是逐个记录各行(或列)代码发生变化的位置和相应代码，从而实现数据的压缩(表4-4(b))。还有一种行程编码，是在各行(或列)数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩(表4-4(c))。利用这三种行程编码方法进行栅格数据存储，分别用54、32、32个整数就表达了原始数据中的64个栅格的位置和属性。

行程编码即可以沿行记录，也可以沿列记录。记录代码的行程位置时，可以记录代码的起始位置，也可以记录代码的结束位置。行程编码压缩数据简便有效，行程编码的压缩比与图形的复杂程度成反比，图件越简单，压缩效率越高。行程编码的优点是在栅格加密时，数据量没有明显增加，且易于检索、叠加及合并等操作，能最大限度地保留原始栅格结构;缺点是对于图斑破碎、属性和边界多变的数据压缩效率较低。

图4-15　多边形栅格图

表4-4　行程编码方法

3.块状编码(block code)

块状编码是行程编码扩展到二维的编码方式，在做块状编码时，首先把栅格图范围内的像元划分成由相同像元值组成的最大正方形，然后对正方形进行编码，数据结构包括初始位置(行、列号)、半径及记录单元的代码(如图4-16所示)。块状编码具有区域性质，又具有可变的分辨率，对大而简单的多边形有较高的压缩效率，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性，只是对某些运算必须转换成简单数据形式时才能顺利进行。

4.四叉树编码(quad－tree code)

四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分，逐块检查其栅格属性值，如果某个子区的所有栅格属性值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次分割，直到每个子块都只含有相同的属性值或灰度为止(如图4-17所示)。为了保证四叉树分解能不断进行下去，要求图形必须为2ⁿ×2ⁿ的栅格阵列，n为极限分割次数，n+1是四叉树最大层数或最大高度。

图4-16　块状编码分块及记录

图4-17　栅格图四叉数划分

四叉树编码由上而下的方法运算量大，耗时较长，因而实践中可以采用从下而上的方法建立四叉树编码，如果每相邻四个栅格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。

四叉树编码一般使用线性四叉树存储方式，线性四叉树只存储最后叶结点的信息，包括叶结点的位置、深度和属性或灰度值。所谓深度是指处于四叉树的第几层上，由深度可推知子区的大小。线性四叉树叶结点的编号遵循一定的规则，也称为地址码，它隐含了叶结点的位置和深度信息。在此，最常用的叶结点编号或地址码是四进制及十进制的Morton码，分别表示为M_q和M_d，它们都可通过行号、列号计算获得。其中，四叉树的四进制Morton码值可按照公式M_q=2I_b+J_b计算获得，其中，I_b和J_b分别以行号和列号的二进制表示。例如对于一个8行8列的栅格图，其每个栅格单元的四进制Morton码如图4-18(a)所示。

而十进制Morton码值也可以利用I_b和J_b获得，在此，首先设I_b和J_b的二进制表示如下所示:

I_b=i_ni_n－1……i₂i₁，

J_b=j_nj_n－1……j₂j₁，

则M_d=i_nj_ni_n－1j_n－1……i₂j₂i₁j₁，这里，i和j为二进制的0或1，因此M_d也为二进制形式，将Md由二进制数据形式转换为十进制数据形式即可获得四叉树十进制的Morton码值，同样对于一个8行8列的栅格图，同样可获得每个栅格单元的十进制Morton码(如图4-18(b)所示)。

图4-18　Morton编码的四进制和十进制表示

在四进制和十进制的Morton码基础上，就可以实现栅格数据的压缩存储，如对图4-17所示多边形，其十进制的四叉树编码如表4-5所示。

表4-5　十进制四叉树编码结果

四叉树编码有许多优点，它编码效率较高，具有可变的分辨率，树的深度随数据的破碎程度而变化，并且有区域性质，压缩数据灵活，许多图形图像运算和转换运算可以在编码数据上直接实现，大大提高了运算效率，并支持嵌套多边形的表达，是优秀的栅格压缩编码之一。四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。