第二章3栅格编码1.pptx

1 1）栅格数据结构概念栅格数据结构概念 栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地理要素的非几何属性特征。特点：属性明显，定位隐含属性明显，定位隐含。注意：栅格数据结构是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的l l栅格数据单元格经常是矩形（主要是正方形）的，栅格数据单元格经常是矩形（主要是正方形）的，但并不是必须如此。其单元格形状可以随应用的但并不是必须如此。其单元格形状可以随应用的需要进行具体设定，比如设置为三角形。需要进行具体设定，比如设置为三角形。l l栅格数据的比例尺就是栅格大小与地表相应单元栅格数据的比例尺就是栅格大小与地表相应单元大小之比。大小之比。l l栅格尺寸越小，其分辨率越高，数据量也越大。栅格尺寸越小，其分辨率越高，数据量也越大。栅格数据的形状、尺寸及相关问题l l由于栅格结构对地表的离散，在计算面积、长度、由于栅格结构对地表的离散，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则距离、形状等空间指标时，若栅格尺寸较大，则造成较大的误差造成较大的误差 。l l由于栅格单元中存在多种地物，而数据中常常只由于栅格单元中存在多种地物，而数据中常常只记录一个属性值，这会导致属性误差。比如，遥记录一个属性值，这会导致属性误差。比如，遥感数据中的感数据中的“混合像元混合像元”问题。问题。栅格数据的形状、尺寸及相关问题三角形、方格和六角形划分三角形、方格和六角形划分三角形、方格和六角形划分三角形、方格和六角形划分 栅格数据模型栅格数据模型 图形栅格数据结构表示图形栅格数据结构表示0 00 0 0 00 02 2 0 00 00 00 00 0 0 02 20 0 0 00 00 00 01 1 0 02 20 0 3 33 30 00 00 0 0 02 23 3 3 33 33 30 00 0 2 20 03 3 3 33 33 30 00 0 2 20 00 0 3 33 30 00 02 2 0 00 00 0 0 00 00 0线线线线面面面面点点点点2）栅格数据的获取一、栅格数据的获取途径 栅格数据通常可以由下列几种途径得到栅格数据通常可以由下列几种途径得到 （1）格网法：在输入图上均匀划分格网，逐个格网在输入图上均匀划分格网，逐个格网地决定其属性代码，形成栅格数字地图文件。地决定其属性代码，形成栅格数字地图文件。（2）由矢量结构数据转化为栅格数据 （3）扫描法：经过扫描对数据重采样和再编码得到经过扫描对数据重采样和再编码得到栅格数据文件栅格数据文件 （4）遥感影像数据2）栅格数据的获取二、栅格数据的取值方法 在确定栅格像元的属性代码时应尽量保持与实地的一致性，保证最大在确定栅格像元的属性代码时应尽量保持与实地的一致性，保证最大信息量。信息量。（1 1）中心点法中心点法：用处于栅格：用处于栅格中心处的地物类型或现象特性中心处的地物类型或现象特性决定像元的代码。决定像元的代码。（2 2）面积占优法面积占优法：以占栅格：以占栅格面积最大的地物类型或现象特面积最大的地物类型或现象特性决定像元的代码。性决定像元的代码。（3 3）重要性法重要性法：根据栅格内：根据栅格内不同地物的重要性，选取最重不同地物的重要性，选取最重要的地物类型决定相应的栅格要的地物类型决定相应的栅格像元代码。像元代码。BCAO具有连续分布特性的地理要素，如降雨量分布、人口密度图等常用于分类较细、地物类别斑块较小的情况常用于具有特殊意义而面积又较小的地理要素，尤其是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等。在属性代码中应尽量表示这类重要地物。(2)链码链码(Chain Encoding)(1)直接栅格编码直接栅格编码(3)游程长度编码游程长度编码(Run_Length Encoding)(4)块块 码码(Block Encoding)(5)四叉树编码四叉树编码(Quadtree Encoding)2栅格结构编码方法1 1、直接栅格编码、直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 30，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。(1)直接栅格编码直接栅格编码特点：简单、直观。数据量大，数据冗余严重。是压缩编码方法的逻辑原型。(1)直接栅格编码直接栅格编码(2)链码链码(chain Encoding)链码又称为弗里曼链码链码又称为弗里曼链码Freeman或边界或边界链码，链码可以有效地压缩栅格数据，而链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形度等运算十分方便，比较适合于存储图形数据数据。由起点位置和一系列在基本方向的单位矢量给出每个后续点相对其前继点的可能的8个基本方向之一表示。8个基本方向自0开始按逆时针方向代码分别为0，1，2，3，4，5，6，7。单位矢量的长度默认为一个栅格单元。2 2、链码、链码12345076001 0 767 01 1 0 0(2)链码链码(Chain Encoding)链码编码链码编码：2，2，6，7，6，0，6，5123450760 5 0 0 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 00 5 0 0 0 0 0 00 0 5 5 0 0 0 00 0 0 5 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 0链码编码示例链码编码示例 压缩效率较高，接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；(2)链码链码(chain Encoding)3 3、游程长度编码、游程长度编码只在各行（或列）数据的代码发生变化时依次记录 该代码以及相同代码重复的个数；0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿行方向进行编码沿行方向进行编码：(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）。）。(3)游程长度编码游程长度编码(Run_Length Encoding)3 3、游程长度编码、游程长度编码逐个记录各行（或列）代码发生变化的位置和相应代码。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 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）。）。(3)游程长度编码游程长度编码(Run_Length Encoding)在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；但计算期间的处理和制图输出处理工作量都有所增加。(3)游程长度编码游程长度编码(Run_Length Encoding)4 4、块码、块码 游程编码是在一维情况下（按行或列）记录像元的属性及其位置。现若采用方形区域作为记录单元，则可以将游程编码扩展为二维情况下的编码方式，即块码。采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1 1，5 5，1 1，5 5），），（1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3 3），），（5 5，4 4，2 2，3 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。(4)块块 码码(Block Encoding)块码与游程编码一样，地理数据的相关性越强，则其压缩效率越高。但随栅格图像复杂程度的提高而降低其效率。所表示的具有代码的图块越大，块码编码的压缩比就越高；反之则低。此外，块码在图像合并、插入、检测延伸性、面积计算等操作是有明显的优越性。但是，在某些情况下，按游程编码或块码编码的栅格数据还须通过解码使其返回到栅格矩阵编码的基本形式。(4)块块 码码(Block Encoding)5 5、四叉树编码、四叉树编码 是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n2 n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度(5)四叉树编码四叉树编码(Quadtree Encoding)0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南东南西北东北 l l通常每个叶结点的地址编号在计算机中是用二进制数来表示的，在每一层上的象限位置（0、1、2、3）均可用两位二进制数写出。例如，0记作二进制数01，2和3分别记作二进制数10和11。221213013202322编号为213的子象限（叶结点）的地址可用二进制表示为：编号213100111四叉树地址编码这样，记录了各个叶结点的地址，再记上各自相应的属性代码值就记录了整个图像。并在此基础上进行多种图像操作。l l为了得到四叉树叶结点的地址码可以采用一种被称为Morton码的方法直接得到。Morton码是一种自然数码以图像左下角为原点（0行，0列开始起算）的行列坐标系为基准，它的值与二维栅格阵列的位置相对应。21212020171716165 54 41 10 00 023232222191918187 76 63 32 21 12929282825252424131312129 98 82 2313130302727262615151414111110103 3535352524949484837373636333332324 4555554545151505039393838353534345 5616160605757565645454444414140406 6636362625959585847474646434342427 77 76 65 54 43 32 21 10 0列号M码行号Morton码与行列号的关系l lMorton码的扩展顺序如同前述对子象限的编号顺序是相似的。l l每个栅格像元对应着一个Morton码，而每个Morton码又对应着二维栅格阵列的行列号，只要将行列号转化为二进制数，然后将它们按位交叉排列放入Morton码变量中，即可得到四叉树各叶结点的二进制数地址码。l l如前例中编号为213的叶结点。它对应的Morton码为39，在以左下角为原点的行列坐标系中该叶结点的行列号为（5，3），将其分别化为二进制数为101和011，然后将两数按位交叉排列，即可得到该叶结点的二进制数地址码100111。l l应用Morton码可以将栅格数据的二维数组形式转化为以Morton码为下标的一维数组。(5)四叉树编码四叉树编码 四叉树编码具有可变的分辨率。并且具有区域的特征，压缩数据灵活，许多运算可以在编码数据上直接实现，大大提高了运算效率，是优秀的栅格数据压缩编码之一。其不足之处在于该方法的树状表示变换缺乏不变性，有时，相同形状和大小的两个区域可能表示为截然不同的结构。总结总结 一般来说，对数据的压缩是以增加运算时间为代价的。一般来说，对数据的压缩是以增加运算时间为代价的。在这里时间和空间是一对矛盾。为了更有效地利用空间资在这里时间和空间是一对矛盾。为了更有效地利用空间资源，减少数据冗余，有时不得不多费一些机器运算时间进源，减少数据冗余，有时不得不多费一些机器运算时间进行编码以及进行较为复杂的图形运算。行编码以及进行较为复杂的图形运算。直接栅格矩阵法直接栅格矩阵法简简单明了可直观地反映栅格图像数据，但是数据冗余太大；单明了可直观地反映栅格图像数据，但是数据冗余太大；链码链码的压缩率较高，已接近矢量结构，对边界的运算比较的压缩率较高，已接近矢量结构，对边界的运算比较方便。但是不具备区域的性质，区域运算较困难；方便。但是不具备区域的性质，区域运算较困难；游程编游程编码码在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易；块码和四叉树编码块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，使用也日益广泛。再议游程编码再议游程编码a.a.定义定义定义定义 游程编码结构游程编码结构游程编码结构游程编码结构l l游程指相邻同值网格的数量，游程编码结构是逐游程指相邻同值网格的数量，游程编码结构是逐游程指相邻同值网格的数量，游程编码结构是逐游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并后网格的行将相邻同值的网格合并，并记录合并后网格的行将相邻同值的网格合并，并记录合并后网格的行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，值及合并网格的长度，其目的是压缩栅格数据量，值及合并网格的长度，其目的是压缩栅格数据量，值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。消除数据间的冗余。消除数据间的冗余。消除数据间的冗余。l l游程编码结构的建立方法是：将栅格矩阵的数据游程编码结构的建立方法是：将栅格矩阵的数据游程编码结构的建立方法是：将栅格矩阵的数据游程编码结构的建立方法是：将栅格矩阵的数据序列序列序列序列X1,X2,X3.XNX1,X2,X3.XN，映射为相应的二元序列，映射为相应的二元序列，映射为相应的二元序列，映射为相应的二元序列（AiAi，PiPi），），），），i i1 1，k k，且，且，且，且k=n.k=n.其中，其中，其中，其中，A A为属性值，为属性值，为属性值，为属性值，P P为游程，为游程，为游程，为游程，k k为游程序号为游程序号为游程序号为游程序号2255275577755555序号序号二元组序列二元组序列1（2，2）2（5，2）3（2，1）4（7，1）5（5，2）6（7，3）7（5，5）二元映射二元映射l l这种结构特别适合于这种结构特别适合于这种结构特别适合于这种结构特别适合于二值图数据的表示，二值图数据的表示，二值图数据的表示，二值图数据的表示，如图如图如图如图1111111000001111100001111序号序号二元组序号二元组序号1（1，7）2（0，5）3（1，5）4（0，4）5（1，4）二元映射二元映射l lb.游程编码能否压缩数据量，主要决定于栅游程编码能否压缩数据量，主要决定于栅格数据的性质，通常可通过事先测试，估格数据的性质，通常可通过事先测试，估算图层的数据冗余度算图层的数据冗余度Re e：Re 1Q/(MN)Q：图层内相邻属性值变化次数的累加和：图层内相邻属性值变化次数的累加和M：为图层网格的行数：为图层网格的行数N：为图层网格的列数：为图层网格的列数当的值大于当的值大于1/5的情况下，表明栅格数据的压缩可取得明显的效果的情况下，表明栅格数据的压缩可取得明显的效果c.当栅格数据为数字高程时l l当栅格数据为规则的数字地形高程即当栅格数据为规则的数字地形高程即DEM时，由于这种类型数据的相邻的数据具有时，由于这种类型数据的相邻的数据具有高度的相关性，可通过差分映射进行预处高度的相关性，可通过差分映射进行预处理，然后在采用游程长度压缩编码法。例理，然后在采用游程长度压缩编码法。例如如2468357824682581122223221222223332321223差分d.基于游程编码结构的栅格数据文件的数据组织方式l l为了提高系统对这些数据的访问效率，通为了提高系统对这些数据的访问效率，通常采用索引顺序文件的方法来组织数据。常采用索引顺序文件的方法来组织数据。当由位置参数访问其属性特征时，利用逻当由位置参数访问其属性特征时，利用逻辑顺序和逻辑地址的关系，很快在索引文辑顺序和逻辑地址的关系，很快在索引文件中找到指向数据文件欲访栅格的指针，件中找到指向数据文件欲访栅格的指针，并求出其逻辑地址，就能找到该栅格的属并求出其逻辑地址，就能找到该栅格的属性。性。栅格行序号栅格行序号逐行游程逐行游程累计数累计数01010202.1001003 37 7.572572游程序号编码值0001000200030004.0007.0572R1R2R3R4.R7.R572索引文件数据文件l lGIS中属性数据主要是与各种专题地图有关的数量、类别、等级和描述性信息。l l一般通过相应的图素，如点、弧段、多边形的编号与图形建立联系的。l l属性数据的内容有时直接记录在图形数据中，有时则单独以某种结构存储，通过指针或关键码与图形数据相连接。属性数据编码方法属性数据编码方法属性数据编码方法属性数据编码方法1.1.编码内容编码内容 （1）登录部分：用来标识属性数据的序号，可以是简单的连续编号，也可划分不同层次进行顺序编码 （2）分类部分：用来标识属性的地理特征，可以采用多位代码来反映多种特征 （3）控制部分：通过某些查错算法，对在编码录入和传递过程中的错误进行检查，特别是当属性数据量较大的情况下具有重要意义。2.2.编码原则编码原则 （1）管理效率高 （2）适用性好 （3）接口方便