第二章-3-栅格编码1

2.3.4栅格数据结构及其编码1栅格数据结构1）栅格数据结构概念2）栅格数据的获取2栅格数据编码方法1）栅格数据结构概念栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地理要素的非几何属性特征。特点：属性明显，定位隐含。注意：栅格数据结构是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的栅格数据单元格经常是矩形（主要是正方形）的，但并不是必须如此。其单元格形状可以随应用的需要进行具体设定，比如设置为三角形。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。栅格尺寸越小，其分辨率越高，数据量也越大。栅格数据的形状、尺寸及相关问题由于栅格结构对地表的离散，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则造成较大的误差。由于栅格单元中存在多种地物，而数据中常常只记录一个属性值，这会导致属性误差。比如，遥感数据中的“混合像元”问题。栅格数据的形状、尺寸及相关问题三角形、方格和六角形划分栅格数据模型图形栅格数据结构表示00002000000200000102033000023333002033330020033002000000000000000000000000002000000000000000000000000000000000000000000000000600000000000066600000000006000000000006000600000060000000000744444477774777444487780840877808800800887888880000888800000888线面点2）栅格数据的获取一、栅格数据的获取途径栅格数据通常可以由下列几种途径得到（1）格网法：在输入图上均匀划分格网，逐个格网地决定其属性代码，形成栅格数字地图文件。（2）由矢量结构数据转化为栅格数据（3）扫描法：经过扫描对数据重采样和再编码得到栅格数据文件（4）遥感影像数据2）栅格数据的获取二、栅格数据的取值方法在确定栅格像元的属性代码时应尽量保持与实地的一致性，保证最大信息量。（1）中心点法：用处于栅格中心处的地物类型或现象特性决定像元的代码。（2）面积占优法：以占栅格面积最大的地物类型或现象特性决定像元的代码。（3）重要性法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格像元代码。BCAO具有连续分布特性的地理要素，如降雨量分布、人口密度图等常用于分类较细、地物类别斑块较小的情况常用于具有特殊意义而面积又较小的地理要素，尤其是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等。在属性代码中应尽量表示这类重要地物。(2)链码(ChainEncoding)(1)直接栅格编码(3)游程长度编码(Run_LengthEncoding)(4)块码(BlockEncoding)(5)四叉树编码(QuadtreeEncoding)2栅格结构编码方法1、直接栅格编码直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。02255555222225550000033322223355002333550033335300033333000033330，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)链码(chainEncoding)链码又称为弗里曼链码[Freeman]或边界链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。由起点位置和一系列在基本方向的单位矢量给出每个后续点相对其前继点的可能的8个基本方向之一表示。8个基本方向自0°开始按逆时针方向代码分别为0，1，2，3，4，5，6，7。单位矢量的长度默认为一个栅格单元。2、链码12345076001076701100(2)链码(ChainEncoding)链码编码：2，2，6，7，6，0，6，5123450760500000000500000000000000500000000550000000500000050000000000000链码编码示例压缩效率较高，接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；(2)链码(chainEncoding)3、游程长度编码①只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数；0225555522222555000003332222335500233355003333530003333300003333沿行方向进行编码：(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_LengthEncoding)3、游程长度编码②逐个记录各行（或列）代码发生变化的位置和相应代码。0225555522222555000003332222335500233355003333530003333300003333沿列方向进行编码：(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_LengthEncoding)在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；但计算期间的处理和制图输出处理工作量都有所增加。(3)游程长度编码(Run_LengthEncoding)4、块码游程编码是在一维情况下（按行或列）记录像元的属性及其位置。现若采用方形区域作为记录单元，则可以将游程编码扩展为二维情况下的编码方式，即块码。采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。0225555522222555000003332222335500233355003333530003333300003333（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）。(4)块码(BlockEncoding)块码与游程编码一样，地理数据的相关性越强，则其压缩效率越高。但随栅格图像复杂程度的提高而降低其效率。所表示的具有代码的图块越大，块码编码的压缩比就越高；反之则低。此外，块码在图像合并、插入、检测延伸性、面积计算等操作是有明显的优越性。但是，在某些情况下，按游程编码或块码编码的栅格数据还须通过解码使其返回到栅格矩阵编码的基本形式。(4)块码(BlockEncoding)5、四叉树编码是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n×2n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n×2n的栅格阵列。n为极限分割次数，n＋1是四叉树最大层数或最大高度(5)四叉树编码(QuadtreeEncoding)0225555522222555000003332222335500233355003333530003333300003333①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南东南西北东北通常每个叶结点的地址编号在计算机中是用二进制数来表示的，在每一层上的象限位置（0、1、2、3）均可用两位二进制数写出。例如，0记作二进制数01，2和3分别记作二进制数10和11。221213013202322编号为213的子象限（叶结点）的地址可用二进制表示为：编号213100111四叉树地址编码这样，记录了各个叶结点的地址，再记上各自相应的属性代码值就记录了整个图像。并在此基础上进行多种图像操作。为了得到四叉树叶结点的地址码可以采用一种被称为Morton码的方法直接得到。Morton码是一种自然数码以图像左下角为原点（0行，0列开始起算）的行列坐标系为基准，它的值与二维栅格阵列的位置相对应。21201716541002322191876321292825241312982313027261514111035352494837363332455545150393835345616057564544414066362595847464342776543210列号M码行号Morton码与行列号的关系Morton码的扩展顺序如同前述对子象限的编号顺序是相似的。每个栅格像元对应着一个Morton码，而每个Morton码又对应着二维栅格阵列的行列号，只要将行列号转化为二进制数，然后将它们按位交叉排列放入Morton码变量中，即可得到四叉树各叶结点的二进制数地址码。如前例中编号为213的叶结点。它对应的Morton码为39，在以左下角为原点的行列坐标系中该叶结点的行列号为（5，3），将其分别化为二进制数为101和011，然后将两数按位交叉排列，即可得到该叶结点的二进制数地址码100111。应用Morton码可以将栅格数据的二维数组形式转化为以Morton码为下标的一维数组。(5)四叉树编码四叉树编码具有可变的分辨率。并且具有区域的特征，压缩数据灵活，许多运算可以在编码数据上直接实现，大大提高了运算效率，是优秀的栅格数据压缩编码之一。其不足之处在于该方法的树状表示变换缺乏不变性，有时，相同形状和大小的两个区域可能表示为截然不同的结构。总结一般来说，对数据的压缩是以增加运算时间为代价的。在这里时间和空间是一对矛盾。为了更有效地利用空间资源，减少数据冗余，有时不得不多费一些机器运算时间进行编码以及进行较为复杂的图形运算。直接栅格矩阵法简单明了可直观地反映栅格图像数据，但是数据冗余太大；链码的压缩率较高，已接近矢量结构，对边界的运算比较方便。但是不具备区域的性质，区域运算较困难；游程编码在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易；块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，使用也日益广泛。再议游程编码a.定义游程编码结构游程指相邻同值