栅格数据是按网格单元的行与列排列、具有不同灰度或颜色的阵列数据。每一个单元（象素）的位置由它的行列号定义，所表示的实体位置隐含在栅格行列位置中，数据组织中的每个数据表示地物或现象的非几何属性或指向其属性的指针。，一个优秀的压缩数据编码方案是：在最大限度减少计算机运算时间的基点上进行最大幅度的压缩。

简介

栅格结构的数据组织方法

栅格数据的获取途径与原则(（一）栅格数据的获取途径 （二）栅格像元代码的确定原则)

三、栅格结构的编码方法(编码方法 （一）直接栅格编码 （二）链式编码 （三）游程编码 （四）块式编码 （五）四叉树数据结构 （六）八叉树与十六叉树结构 （七）各种编码的比较分析 总结)

简介

基本知识

栅格数据是按网格单元的行与列排列、具有不同灰度或颜色的阵列数据。栅格结构是大小相等分布均匀、紧密相连的像元（网格单元）阵列来表示空间地物或现象分布的数据组织。是最简单、最直观的空间数据结构，它将地球表面划分为大小、均匀、紧密相邻的网格阵列。每一个单元（象素）的位置由它的行列号定义，所表示的实体位置隐含在栅格行列位置中，数据组织中的每个数据表示地物或现象的非几何属性或指向其属性的指针。对于栅格结构：

点实体由一个栅格像元来表示；线实体由一定方向上连接成串的相邻栅格像元表示；

面实体（区域）由具有相同属性的相邻栅格像元的块集合来表示。

栅格结构的特点

数据直接记录属性的指针或属性本身，而其所在位置则根据行列号转换成相应的坐标给出。也就是说，定位是根据数据在数据集合中的位置得到的。

如图3.1(a)所示，数据1表示属性或编号位的一个点，其位置由所在的第3行、第5列得到。因为栅格结构是按一定的规则排列的，因此所表示的实体位置很容易隐含在网格文件的存储结构中。在网格文件中每个代码本身明确地代表了实体的属性或属性编码，如果为属性编码，则该编码可作为指向实体属性表的指针。图3.1 (a)中表示了代码分别为1，3，6的实体，图3.1 (b)表示了一条代码为8的线实体，图3.1 (c)表示了3个代码分别为4，7，9的面实体。

(a) 点 (b) 线 (c) 区域

0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 4 4 4 4 7 7 7 7

0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 4 4 4 4 4 7 7 7

0 0 0 0 1 0 0 0　0 0 0 0 8 0 0 0 4 4 4 4 9 9 7 7

0 0 0 0 0 0 0 0　0 0 0 0 0 8 0 0 0 0 4 9 9 9 7 7

0 0 0 3 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 9 9 9 7 7

0 0 0 0 0 0 0 0　0 0 0 0 0 8 0 0　0 0 0 9 9 9 9 9

0 0 0 0 0 6 0 0 0 0 0 8 8 0 0 0 0 0 0 0 9 9 9 9

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9

栅格结构的数据组织方法

栅格结构是用有限的网格逼近某个图形，因此用栅格数据表示的地表是不连续的，是近似离散的数据。栅格单元的大小决定了在一个象元所覆盖的面积范围内地理数据的精度 ，网格单元越细栅格数据越精确，但如果太细则数据量太大。尤其按某种规则在象元内提取的值，如对长度、面积等的度量，主成分值、均值的求算等，其精度由象元的大小直接决定。由于栅格结构中每个代码明确地代表了实体的属性或属性值，点实体在栅格结构中表示为一个象元，线实体表示为具有方向性的若干连续相邻象元的集合，面实体由聚集在一起的相邻象元表示，这就决定了网格行列阵列易为计算机存储、操作、显示与维护，因此，这种结构易于实现，算法简单，易于扩充、修改，直观性强，特别是容易与遥感影像的联合处理。

栅格数据的获取途径与原则

（一）栅格数据的获取途径

栅格数据的获取主要由以下几个途径：

⑴ 栅格法：在待输入的图形上均匀划分栅格单元，逐个栅格地决定其属性代码，最后形成栅格数字地图文件。这是人工编码，当数据量太大时，该法费工费时，工作量相当大。

⑵ 转换法：用手扶跟踪数字化或自动跟踪数字化得到矢量结构数据，在转换为栅格结构。由矢量数据向栅格数据转换是理想的方法。

⑶ 扫描数字化：逐点扫描待输入的专题地图，对扫描数据重新采样与再编码，从而得到栅格数据文件。

⑷ 分类影像输入：将经过分类解译的遥感影像数据直接或重新采样后输入系统，这是高效获取数据的方法。

（二）栅格像元代码的确定原则

当依据一定的要求给定单位网格后，而网格中有多种地物类型（或说属性）时，则根据需要采取如下方案之一决定栅格单元的代码。

⑴ 中心点法：即用处于栅格中心处的地物类型（属性或量值或属性记录指针）或现象特征决定该栅格单元的代码。对于具有连续分布特征的地理要素，如降水分布、人口密度等问题，中心法是被首要选用的。

⑵ 面积占优法：以占矩形面积最大的地物或现象特性的重要性决定栅格单元的代码，此法常见于分类较细，地物类别斑块较小的情况。

⑶ 长度占优法：当覆盖的栅格过中心位置时，横线占据该格中的大部分长度的属性值定为该栅格单元的代码。

⑷ 重要性法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码。此法常见于具有特殊意义而面积较小且不在栅格中心的地理要素。尤其是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等。

以上4点正确使用，则能较好地保持地表的真实性，尽可能地保持原图或原始数据的精度问题。当然，缩小单个栅格单元面积，使每个栅格单元代表更为精细的地面矩形单元，减少混合单元、混合类型与混合面积，可大大提高量算精度，保持真实形态及更细小的地物类型。但增加栅格个数会使数据多，冗余严重。为解决此问题，产生了一系列各具特色的栅格数据压缩编码方法。

三、栅格结构的编码方法

编码方法

在栅格文件中，每个栅格只能赋予一个唯一的属性值，所以属性个数的总数是栅格文件的行数乘以列数的积，而为了保证精度，栅格单元分得一般都很小，这样需要存储的数据量就相当大了。通常一个栅格文件的栅格单元数以万计。但许多栅格单元与相邻的栅格单元都具有相同的值，因此使用了各式各样的数据编码技术与压缩编码技术。主要的编码技术简介如下：

（一）直接栅格编码

直接栅格编码是将栅格数据看作一个数据短阵，逐行或逐列逐个记录代码。可每行从左到右逐个记录，也可奇数行从左到右，偶数行从右到左记录，为特定目的也可采用其它特殊顺序。通常称这种编码的图像文件为栅格文件，这种网格文件直观性强，但无法采用任何种压缩编码方法。图2.1 (c)的栅格编码为：4，4，4，4，7，7，7，7；4，4，4，4，4，7，7，7；4，4，4，4，9，9，7，7；0，0，4，9，9，9，7，7；0，0，0，9，9，9，7，7；0，0，0，9，9，9，9，9；0，0，0，0，9，9，9，9；0，0，0，0，0，9，9，9。可用程序设计语言按顺序文件或随机文件记录这些数据。

（二）链式编码

链式编码又称弗里曼链码或世界链码。它由某一原始点和一系列在基本方向上数字确定的单位矢量链。基本方向有东、东南、南、西南、西、西北、北、东北等8个，每个后继点位于其前继点可能的8个基本方位之一。8个基本方向的代码可分别用0，1，2，3，4，5，6，7表示，既可按顺时针也可按逆时针表示。栅格结构按逆时针编码上图（2）可记录为：1，3，7，7，7，6，6，5，4。其中前两个数字1与3表示线状物起点的坐标，即在第一行第三列，从第三个数字起表示单位矢量的前进方向。

链式编码有效地压缩了栅格数据，尤其对多边形的表示最为显著，链式编码还有一定的运算能力，对计算长度、面积或转折方向的凸凹度更为方便。比较适于存储图形数据。但对边界做合并和插入等修改编辑工作很难实施，而且对局部修改要改变整体结构，效率较低。

（三）游程编码

游程编码是栅格数据压缩的重要且比较简单的编码方法。它的基本思路是：对于一幅栅格图像，常有行或列方向相邻的若干点具有相同的属性代码，因而可采用某种方法压缩重复的记录内容。方法之一是在栅格数据阵列的各行或列象元的特征数据的代码发生变化时，逐个记录该代码及相同代码重复的个数，从而可在二维平面内实现数据的大量压缩。另一种编码方案是在逐行逐列记录属性代码时，仅记录下发生变化的位置和相应的代码。图2.1 (c)栅格结构按游程编码方法可记录为：

第一行4,47,4

第二行4,57,3

第三行4,49,27,2

第四行0,24,19,37,2

第五行0,39,37,2

第六行0,39,5

第七行0,49,4

第八行0,59,3

在这个例子中，原本64个栅格数据，只用了40数值就完整地表示了出来，可见用游程编码方法压缩数据是十分有效的。

游程编码的编码和解码的算法都比较简单，占用的计算机资源少，游程编码还易于检索、叠加、合并等操作，在栅格单元分得更细时，数据的相关性越强，压缩效率更高，数据量并没有明显增加。因此，该编码适合微型计算机等中央处理器处理速度慢，存储容量小的设备进行图像处理。

（四）块式编码

块式编码是游程编码扩展到二维空间的情况，游程编码是在一维状态记录栅格单元的位置和属性，如果采用正方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由记录单元中左上角的栅格单元的行、列号（初始位置）和记录单元的边长（半径）与记录单元的属性代码三部分组成，这便是块式编码。因此可以说，游程编码是块式编码的特殊情况，块式编码是游程编码的一般形式。图2.1 (c)表示的栅格结构按块式编码方法可记录为：

（1，1，3，4），（1，4，1，4），（1，5，1，7），（1，6，2，7），（1，8，1，7）；

（2，4，1，4），（2，5，1，4），（2，8，1，7）；

（3，4，1，4），（3，5，2，9），（3，7，2，7）；

（4，1，2，0），（4，3，1，4），（4，4，1，9）；

（5，3，1，0），（5，4，2，9），（5，6，1，9），（5，7，1，7），（5，8，1，7）；

（6，1，3，0），（6，6，3，9）；

（7，4，1，0），（7，5，1，9），

（8，4，1，0），（8，5，1，0）。

从以上论述的块式编码的编码原理可知，一个记录单元所表示的地理数据相关性越强，也即记录单元包含的正方形边长越长，压缩效率越高。而地理数据相关性差时，也即多边形边界碎杂时，块式编码的效果较差。

块式编码的运算能力弱，必要时其编码的栅格数据须通过解码转换成栅格矩阵编码的数据形式才能顺利进行。块式编码在图像合并、插入、面积计算等功能方面较强。

（五）四叉树数据结构

四叉树编码又名四元树编码，可以通俗理解为一个具有四分枝结构的树，它具有栅格数据二维空间分布的特征，这是一种更为有效的编码方法。四叉树编码将整个图形区域按照四个象限递归分割成2n×2n象元阵列，形成过程是：将一个2×2图像分解成大小相等的四部分，每一部分又分解成大小相等的四部分，就这样一直分解下去，一直分解到正方形的大小正好与象元的大小相等为止，即逐步分解为包含单一类型的方形区域（均值块），最小的方形区域为一个栅格单元。这个倒向树状的图中“○”表示可继续分割的方形区域；“□”表示具有同类属性的方形区域；“■”表示不能再分的单个（最小）象元栅格，即所谓的树叶，树叶表示的是具有单一类型的地物或是符合既定要求的少数几种地物，可以在任意层上。

通过以上对四叉树结构的分析，可发现它有以下特点：

⑴ 存储空间小：因为记录的基本单位是块，不是象素点，因此大大地节省了存储空间。

⑵ 运算速度快：因为四叉树结构的图形操作是在数上进行的，比直接在图上运算要快得多。

⑶ 栅格阵列各部分的分辨率可变：不需要表示许多细节的地方，分级较少，因而分辨率低；边界复杂的地方分级较多，分辨率高，因而在减少数据量的基础上满足了数据精度。

⑷ 容易有效地计算多边形的数量特征。

⑸ 与栅格结构之间的转换，比其它压缩方法容易。

⑹ 四叉树编码表示多边形中嵌套其它属性的多边形时比较方便：它允许多边形嵌套多边形的结构，是非常实用的、重要的特点，这点深深得到地理信息系统数据编码设计者的青睐。

⑺ 四叉树编码的不足之处是：转换具有不确定性，对大小相等形状相同的多边形，不同人可能分解为不同的四叉树结构，因而不利于形状分析和模式识别。四叉树编码处理结构单调的图形区域比较适合，压缩效果好，但对具有复杂结构的图形区域，压缩效率会受到很大影响。

（六）八叉树与十六叉树结构

前面的数据结构都是基于二维的，在相当多的情况下，如地下资源埋藏、地下溶洞的空间分布，二维的坐标体系根本无法表达。因此需要有三维数据结构，如果考虑空间目标随时间变化，那还需要4维数据结构。现在较好的表达三维与四维结构是在四叉树基础上发展起来的八叉树（三维）和十六叉树（四维）。

是将空间区域不断地划分为八个同样大小的子区域，

（七）各种编码的比较分析

比较以上各种编码，可得出如下主要结论：

⑴ 直接栅格编码直观简单，但数据出现大量冗余；

⑵ 链式编码对边界的运算方便，压缩效果好，但区域运算较困难；

⑶ 游程编码即较大幅度地保留了原始栅格结构，又有较高的压缩效率，而且编码解码也较容易，但仅局限在一维空间上处理数据；

⑷ 块式编码在图像合并、插入、面积计算等功能方面较强，当所表示的地理数据相关性强时，压缩效率相当高；但地理数据相关性差时，块式编码的效果较差，而且块式编码的运算能力较弱；

⑸ 四叉树编码运算速度快，存储空间小，分辨率可变，压缩效率高，但其转换具有不确定性，难以形成统一算法。

总结

不论任何形式的压缩数据编码，都是以增加了运算时间换取了存储空间，这就要考虑主要矛盾的主要方面，当我们想减少数据的冗余，有效地利用空间资源时，就不得不进行数据压缩编码，而让计算机多进行一些解码和处理复杂图形的运算。因此，一个优秀的压缩数据编码方案是：在最大限度减少计算机运算时间的基点上进行最大幅度的压缩。