栅格数据编码技术的发展历程
2015.4
南通大学地科院 江浩田
摘要：栅格数据是结构是GIS中最基本的数据结构，本文对栅格数据的属性、小、形状等做出一些系统的描述和分析，其中重点在几种数据结构上做了比较详细的论述和讲解，包括栅格矩阵结构、游程编码结构、四叉树结构，在曲面数据结构中还有TIN的曲面数据结构和规则网格的曲面数据结构，以上的数据结构在不仅在GIS中运用广泛，而且在其他地理数据收集、索引、处理等也发挥着至关重要的作用。 关键词：数据结构、模型、网格、编码、地理处理、顺序、组织
一、栅格数据结构的定义
基于栅格模型的数据结构简称为栅格数据结构，是指将空间分割成有规则的网格，称为栅格单元，在各个栅格单元上给出相应的属性值来表示地理实体的一种数据组织形式。
二、栅格数据的表达方式
(1) 栅格数据是按网格的行与列排列、具有不同或颜色的列阵数据。栅格数据是大小相等分布均匀、紧密相连的像元（网格单元）阵列来表示空间地物或现象分布的数据组织，是最简单、最直观的空间数据结构，它将地球表面划分为大小、均匀、紧密相邻的网格阵列。每一个单元（象素）的位置由它的行列号定义，所表示的实体位置隐含在栅格行列位置中，数据组织中的每个数据表示地物或现象的非几何属性或指向其属性的指针。 (2) 点实体由一个栅格单元来表示；
线实体由一定方向上连接成串的相邻栅格像元表示；
面实体（区域）由具有相同属性的相邻栅格单元的块集合来表示。
(3) 栅格数据结构表示的是二维表面上地理要素的离散化数值，每个网格对应一种属性。网格通常是正方形，有时也采用矩形、等边三角形和正六边形。
(4)格单元的取值方法：
中心点法：取位于栅格中心的属性值为该栅格的属性值。
面积占优法：栅格单元属性值为面积最大者。
重要性法：取重要的属性值为栅格属性值。用于具有特殊意义的较小地物。 长度占优法：每个栅格单元的值由该栅格中线段最长的实体的属性来确定。
三、栅格数据与矢量数据的比较
(1) 栅格数据结构
栅格矩阵结构（直接栅格编码）在计算机中，直接栅格编码文件是以行为记录单位，按行存储地理数据的。由点、线和多边形组成的矢量数据都可以转化成对应的栅格数据。栅格数据结构为一个8*8阶的矩阵，代表空间分辨率为8行*8列的一个栅格数据。如果矩阵的每个元素都计算机里用一个双字节的数值来存储，
则该栅格数据的所需要的存储空间为8*8*2（字节）=128字节。
（2）游程编码结构
游程基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”，程编码因此而得名），使符号长度少于原始数据的长度。 例如：[***********]1111111
行程编码为：（5，6）（7，5）（3，3）（2，4）（l，7）。可见，行程编码的位数远远少于原始字符串的位数。
在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。
行程编码分为定长行程编码和不定长行程编码两种类型。
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。
（3）四叉树结构
GIS中另一种常见的栅格编码为四叉树编码，它是最有效的栅格数据压缩编码方法之一。其基本思想是首先把一幅图像或一幅栅格地图等分成四部分，如果检查到某个子区的所有格网都含有相同的值（灰度或属性值），那么这个子区域就不再往下分割；否则，把这个区域再分割成四个子区域，这样递归地分割，直至每个子块都只含有相同的灰度或属性值为 止。如果栅格数据不是2N×2N 的方阵，则自动补栅格属性值为0的行或列，使得2N大于或者等于行、列数中的大者，取合乎要求的最小的自然数N。分割完成之后则采用一定的机制对分割的结果进行记录，四叉树存储方法：
1.
常规四叉树存储：存储结点（子结点和父结点）指针、结点值；
2.线性四叉树只存储最后叶结点信息，包括叶结点的地址、深度（该结点所处的层）和格网值。
四叉树的叶结点的编码需要遵循一定的规则，隐含了位置信息，称为地址码，常用的编码是Morton码（MD十进制码）。如对以下数据采用记录Morton码、深度、属性值的方法进行记录，如假设有如下栅格数据： 1 1 1 1 2 2 3 3 1 1
1 1 2 2 3 3 1 1 1 1 4 4 5 5 1 1 1 1 4 4 5 5 6 6 7 8 13 13 14 14 6 6 9 10 13 13 14 14 11 11 12 12 15 16 19 19 11 11 12 12 17 18 19 19 进行四叉树编码之后得到如下文件，试进行程序开发实现此过程，结果如图
M码 深度 值 0 1 1 16 2 2 20 2 3 24 2 4 28 2 5 32 2 6 36 3 7 37 3 8 38 3 9 39 3 10 40 2 1 44 2 12 48 2 13 52 2 14 56 3 15 57 3 16 58 3 17 59 3
18 60 2 19
线性四叉树有如下优点：只存储三个值，比常规四叉树节省存储空间；由于记录节点地址，既能直接找到其在四叉树中的走向路径，又可以在换算出它在整个栅格区间内的行列位置；压缩和解压缩比较方便，各部分的分辨率可以不同，既可以精确表示图形结构，又可以减少存储量，易于进行大部分图形操作和运算。 五、栅格数据的应用分析
随着ＲＳ广泛的应用，同时数据压缩技术，计算机性能的提高克服了栅格数据的数据量大等缺点，栅格数据将越来越发挥更大的作用。栅格数据的大规模应用，并将会占具主导地位。主要基于以下优点：
(1) 随ＲＳ技术的发展，并大规模的应用，栅格数据的使用将促使ＲＳ及GIS的
一体化发展。ＲＳ成为空间数据动态更新的重要的数据源。遥感影像是以像元为单元的栅格结构存储的，图像处理技术极大的提高了栅格数据的前期处理能力。这些数据可以直接生成或转换为于GIS 的栅格数据。
(2) 栅格数据可以极大的提高GIS 的时空数据分析能力,栅格数据在图像的代数运算,空间统计分析等具有广泛的应用,可以促成GIS模型的建立。ARCGIS软件的高版本在这一方面以有较突出的表现。
(3) 三维可视化成为动态模拟现实世界的一个新的发展趋势.栅格数据是利用二维图像来模拟地理实体的,可利用栅格数据通过提高维数来实现三维可视化。
(4) 随GIS 的发展,栅格数据数据结构简单,真实感强等特点,可以为大多数程序设计人员和用户理解和使用。图像共享标准(如GIF)的建立,有利于GIS 的栅格数据的共享. 因此,栅格数据在信息共享方面更为实用. 因此,随GIS 发展,栅格数据和矢量数据均具不同程度的发展,但栅格数据要比矢量数据的应用更广泛,更有效。
参考资料：
[1] 高建勇。栅格数据结构研究综述，山西省地质测绘院 2010
[2] 黄杏元、马劲松。地理信息系统概论，高等教育出版社 2014.9
[3] 南京大学研究生院。GIS数据结构第二章
[4] 百度文库 空间数据结构的类型
[5] 陈志泊。GIS中栅格数据时空数据模型及其应用的研究，北京林业大学 2005.5
[6] 周旭光。四叉树空间索引原理及其实现，2013.10
[7] 王结臣、芮一康、刘杰。栅格数据结构的研究及其应用 南京大学 2008.7
[8] 刘锦秀。浅析GIS栅格数据 2012
栅格数据编码技术的发展历程
2015.4
南通大学地科院 江浩田
摘要：栅格数据是结构是GIS中最基本的数据结构，本文对栅格数据的属性、小、形状等做出一些系统的描述和分析，其中重点在几种数据结构上做了比较详细的论述和讲解，包括栅格矩阵结构、游程编码结构、四叉树结构，在曲面数据结构中还有TIN的曲面数据结构和规则网格的曲面数据结构，以上的数据结构在不仅在GIS中运用广泛，而且在其他地理数据收集、索引、处理等也发挥着至关重要的作用。 关键词：数据结构、模型、网格、编码、地理处理、顺序、组织
一、栅格数据结构的定义
基于栅格模型的数据结构简称为栅格数据结构，是指将空间分割成有规则的网格，称为栅格单元，在各个栅格单元上给出相应的属性值来表示地理实体的一种数据组织形式。
二、栅格数据的表达方式
(1) 栅格数据是按网格的行与列排列、具有不同或颜色的列阵数据。栅格数据是大小相等分布均匀、紧密相连的像元（网格单元）阵列来表示空间地物或现象分布的数据组织，是最简单、最直观的空间数据结构，它将地球表面划分为大小、均匀、紧密相邻的网格阵列。每一个单元（象素）的位置由它的行列号定义，所表示的实体位置隐含在栅格行列位置中，数据组织中的每个数据表示地物或现象的非几何属性或指向其属性的指针。 (2) 点实体由一个栅格单元来表示；
线实体由一定方向上连接成串的相邻栅格像元表示；
面实体（区域）由具有相同属性的相邻栅格单元的块集合来表示。
(3) 栅格数据结构表示的是二维表面上地理要素的离散化数值，每个网格对应一种属性。网格通常是正方形，有时也采用矩形、等边三角形和正六边形。
(4)格单元的取值方法：
中心点法：取位于栅格中心的属性值为该栅格的属性值。
面积占优法：栅格单元属性值为面积最大者。
重要性法：取重要的属性值为栅格属性值。用于具有特殊意义的较小地物。 长度占优法：每个栅格单元的值由该栅格中线段最长的实体的属性来确定。
三、栅格数据与矢量数据的比较
(1) 栅格数据结构
栅格矩阵结构（直接栅格编码）在计算机中，直接栅格编码文件是以行为记录单位，按行存储地理数据的。由点、线和多边形组成的矢量数据都可以转化成对应的栅格数据。栅格数据结构为一个8*8阶的矩阵，代表空间分辨率为8行*8列的一个栅格数据。如果矩阵的每个元素都计算机里用一个双字节的数值来存储，
则该栅格数据的所需要的存储空间为8*8*2（字节）=128字节。
（2）游程编码结构
游程基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”，程编码因此而得名），使符号长度少于原始数据的长度。 例如：[***********]1111111
行程编码为：（5，6）（7，5）（3，3）（2，4）（l，7）。可见，行程编码的位数远远少于原始字符串的位数。
在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。
行程编码分为定长行程编码和不定长行程编码两种类型。
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。
（3）四叉树结构
GIS中另一种常见的栅格编码为四叉树编码，它是最有效的栅格数据压缩编码方法之一。其基本思想是首先把一幅图像或一幅栅格地图等分成四部分，如果检查到某个子区的所有格网都含有相同的值（灰度或属性值），那么这个子区域就不再往下分割；否则，把这个区域再分割成四个子区域，这样递归地分割，直至每个子块都只含有相同的灰度或属性值为 止。如果栅格数据不是2N×2N 的方阵，则自动补栅格属性值为0的行或列，使得2N大于或者等于行、列数中的大者，取合乎要求的最小的自然数N。分割完成之后则采用一定的机制对分割的结果进行记录，四叉树存储方法：
1.
常规四叉树存储：存储结点（子结点和父结点）指针、结点值；
2.线性四叉树只存储最后叶结点信息，包括叶结点的地址、深度（该结点所处的层）和格网值。
四叉树的叶结点的编码需要遵循一定的规则，隐含了位置信息，称为地址码，常用的编码是Morton码（MD十进制码）。如对以下数据采用记录Morton码、深度、属性值的方法进行记录，如假设有如下栅格数据： 1 1 1 1 2 2 3 3 1 1
1 1 2 2 3 3 1 1 1 1 4 4 5 5 1 1 1 1 4 4 5 5 6 6 7 8 13 13 14 14 6 6 9 10 13 13 14 14 11 11 12 12 15 16 19 19 11 11 12 12 17 18 19 19 进行四叉树编码之后得到如下文件，试进行程序开发实现此过程，结果如图
M码 深度 值 0 1 1 16 2 2 20 2 3 24 2 4 28 2 5 32 2 6 36 3 7 37 3 8 38 3 9 39 3 10 40 2 1 44 2 12 48 2 13 52 2 14 56 3 15 57 3 16 58 3 17 59 3
18 60 2 19
线性四叉树有如下优点：只存储三个值，比常规四叉树节省存储空间；由于记录节点地址，既能直接找到其在四叉树中的走向路径，又可以在换算出它在整个栅格区间内的行列位置；压缩和解压缩比较方便，各部分的分辨率可以不同，既可以精确表示图形结构，又可以减少存储量，易于进行大部分图形操作和运算。 五、栅格数据的应用分析
随着ＲＳ广泛的应用，同时数据压缩技术，计算机性能的提高克服了栅格数据的数据量大等缺点，栅格数据将越来越发挥更大的作用。栅格数据的大规模应用，并将会占具主导地位。主要基于以下优点：
(1) 随ＲＳ技术的发展，并大规模的应用，栅格数据的使用将促使ＲＳ及GIS的
一体化发展。ＲＳ成为空间数据动态更新的重要的数据源。遥感影像是以像元为单元的栅格结构存储的，图像处理技术极大的提高了栅格数据的前期处理能力。这些数据可以直接生成或转换为于GIS 的栅格数据。
(2) 栅格数据可以极大的提高GIS 的时空数据分析能力,栅格数据在图像的代数运算,空间统计分析等具有广泛的应用,可以促成GIS模型的建立。ARCGIS软件的高版本在这一方面以有较突出的表现。
(3) 三维可视化成为动态模拟现实世界的一个新的发展趋势.栅格数据是利用二维图像来模拟地理实体的,可利用栅格数据通过提高维数来实现三维可视化。
(4) 随GIS 的发展,栅格数据数据结构简单,真实感强等特点,可以为大多数程序设计人员和用户理解和使用。图像共享标准(如GIF)的建立,有利于GIS 的栅格数据的共享. 因此,栅格数据在信息共享方面更为实用. 因此,随GIS 发展,栅格数据和矢量数据均具不同程度的发展,但栅格数据要比矢量数据的应用更广泛,更有效。
参考资料：
[1] 高建勇。栅格数据结构研究综述，山西省地质测绘院 2010
[2] 黄杏元、马劲松。地理信息系统概论，高等教育出版社 2014.9
[3] 南京大学研究生院。GIS数据结构第二章
[4] 百度文库 空间数据结构的类型
[5] 陈志泊。GIS中栅格数据时空数据模型及其应用的研究，北京林业大学 2005.5
[6] 周旭光。四叉树空间索引原理及其实现，2013.10
[7] 王结臣、芮一康、刘杰。栅格数据结构的研究及其应用 南京大学 2008.7
[8] 刘锦秀。浅析GIS栅格数据 2012