07栅格数据结构.ppt
第4章 空间数据结构,1,主要内容,4.1 矢量数据结构4.2 栅格数据结构4.3 矢栅一体化数据结构 4.4 镶嵌数据结构4.5 栅格与矢量数据的相互转换,2,4.2 栅格数据结构,3,4.2 栅格数据结构,4.2.1 栅格单元的确定 4.2.2 完全栅格数据结构 4.2.3 压缩栅格数据结构,4,4.2 栅格数据结构,以规则栅格阵列表示空间对象的数据结构，是最简单最直观的空间数据结构，又称为网格结构(raster或grid cell)或像元结构(pixel)。阵列中每个栅格单元上的数值表示空间对象的非几何属性特征；其位置由栅格阵列中每个单元的行列号来确定。栅格数据结构表示的地表是不连续的，是量化和近似离散的数据，一个栅格单元对应于小块地理范围。,5,对于栅格数据结构点：为一个像元线：在一定方向上连接成串的相邻像元集合。面：聚集在一起的相邻像元集合。,6,7,点、线、面数据的矢量与栅格表示,8,Representation of point,line,and area features:raster format on the left and vector format on the right.,栅格数据类型,1卫星影像：像元值代表从地球表面反射或发射的光能，可从中提取各种专题，如土地利用、水文、水质等。2数字高程模型（DEM）：由等间隔海拔数据的排列组成。DEM以点为基础，将海拔高度点置于格网单元中心的方法转成栅格数据。3数字正射影像图（DOQ）：是一种由航片或其他遥感数据制备而得到的数字化影像，其中由照相机镜头倾斜和地形起伏引起的位移已被消除。4二进制扫描文件：是含数值1或数值0的扫描图像。5数字栅格图形：是USGS（美国地质调查局）地形图的扫描图像。6图形文件：如JPG、TIFF、GIF等；7特定地理信息系统软件的栅格数据。,4.2.1栅格单元的确定,1.栅格数据的参数一个完整的栅格数据通常由以下几个参数决定：（1）栅格形状。栅格单元通常为矩形或正方形。特殊的情况下也可以按经纬网划分栅格单元。（2）栅格单元大小。也就是栅格单元的尺寸，即分辨率。栅格单元的合理尺寸应能有效地逼近空间对象的分布特征，以保证空间数据的精度。通常以保证最小图斑不丢失为原则来确定合理的栅格尺寸。（3）栅格原点。栅格系统的起始坐标应将和国家基本比例尺地形图公里网的交点相一致，或者和已有的栅格系统数据相一致。并同时使用公里网的纵横坐标轴作为栅格系统的坐标轴。（4）栅格的倾角。通常情况下，栅格的坐标系统与国家坐标系统平行。,10,1.栅格数据的参数,11,X：列,Y：行,西南角格网坐标（XWS，YWS）,格网分辨率,2.栅格数据单元值确定,12,面积占优,重要性,中心点法,A位于栅格中心处的地物类型决定其取值。常用于连续分布特性的地理现象。,C选取最重要的地物类型为单元值。常用于有特殊意义而面积较小的地理要素,A占区域面积最大的地物类型取值适用于分类较细、地物斑块较小地理要素,为了逼近原始数据精度，除了采用这几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法,13,几何偏差,属性偏差,如ac距离以像元边线计算则为7，以像元个数为单位则为4。三角形的面积为6个平方单位，而右图中则为7个平方单位，这种误差随像元的增大而增加。,中心点法,面积占优法,4.栅格数据的编码方法,4.2.2完全栅格数据结构直接栅格编码4.2.3压缩栅格数据结构游程长度编码链式数据编码四叉树编码分块压缩编码,14,4.2.2完全栅格数据结构,1.直接栅格编码将栅格看做一个数据矩阵，逐行逐个记录代码数据。优点：简单、直观，无压缩缺点：存在大量冗余，精度提高有限制。,15,完全栅格数据的组织,完全栅格数据的组织有三种基本方式：基于像元、基于层（波段）和基于行.bsq（band sequential）基于层（波段）的方式,16,栅格数据文件,波段1,像元1，1,像元1，2,像元1，m,像元m，n,波段2,波段k,.bil（band interleaved by line）基于行的方式,17,栅格数据文件,行1,波段1,行2,像元1n,波段2,像元1n,波段k,像元1n,行m,.bip（band interleaved by pixel）基于像元方式,18,栅格数据文件,像元1，1,像元1，2,波段1,波段k,像元m，n,2.游程长度编码（Run-Length Encoding）,也称为行程编码，将每行中具有相同属性值的连续像元映射为一个游程，每个游程的数据结构为（A，P），A表示属性值，P代表该游程最右端的列号或个数。属性变化越少，压缩比例越大，适合于类型区域面积较大的栅格。,19,原始栅格数据,(9,4),(0,4),(9,3),(0,5),(0,1)(9,2),(0,1),(7,2),(0,2),(0,4),(7,2),(0,2),(0,4),(7,4),(0,4),(7,4),(0,4),(7,4),(0,4),(7,4),2.游程长度编码（Run-Length Encoding）,优点：栅格加密时，数据量不会明显增加，压缩效率高，最大限度保留原始栅格结构，编码解码运算简单，且易于检索、叠加、合并等操作，得到广泛应用。缺点：不适合于类型连续变化或类型区域分散的数据。,20,3.链式数据编码（Chain Encoding，弗里曼Freeman）,链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东0，东南l，南2，西南3，西4，西北5，北6，东北7等八个基本方向。编码过程：起始点的寻找一般遵循从上到下，从左到右的原则；当发现没有记录过的点，且数值不为0时，就是一条线或边界的起点；记下该地物的特征码、起点的行列号，然后按顺时针方向寻迹，找到相邻的等值点，并按八个方向编码。,21,3.链式数据编码（Chain Encoding，弗里曼Freeman）,链式编码表特征码 起点行 起点列 链码 线 1 5 3223323 面 3 6 0213246676,22,链式编码的方向代码,链式编码示意图,优点：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，比较适于存储图形数据。缺点：对边界做合并和插入等修改编辑比较困难；类似矢量结构，不具有区域的性质，对叠置运算如组合、相交等则很难实施；而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。,23,4.四叉树编码（Quad tree Encoding）,四叉树概述：一种可变分辨率的非均匀网格系统。基本思想：将一幅栅格数据层或图像等分为四部分，逐块检查其格网属性值（或灰度）；如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区；这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n2n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度.,24,方法：自上而下 自下而上 A B A A A B A A B B,25,1）常规四叉树,记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值。指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。,26,2）线性四叉树,只记录叶结点的信息，包括叶结点的位置，深度（几次分割）和属性。叶结点的编号遵循一定的规则，这种编号称为地址码，常用的有四进制、十进制Morton码优点：存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的位置和分割次数。线性四叉树可直接寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树。定位码容易存储和执行实现集合相加等组合操作。,27,3）四进制的Morton码,28,方法1（自上而下分割）其始行列号从0计 由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。B、每一个位均是不大于3的四进制数，表达位置。由Morton码找出四叉树叶结点的具体位置。,03,B,A,方法2（自下而上合并的方法）,1）计算二维矩阵每个元素的下标对应的MQ 其始行列号从0计。2)按码的升序排成线性表，放在连续的内存块中。3）依次检查每四个相邻的MQ对应的属性值，相同合并（不同码位去掉），不同则存盘,直到没有能够合并的子块为止。,29,30,4）十进制的Morton码-MD,四进制Morton码直观上符合四叉树分割，但许多语言不支持四进制变量，需用十进制表示Morton码.1、一种按位操作的方法：(1)行、列号转换为二进制 Ib=1 0 Jb=1 1(2)I行J列交叉 1 1 0 1=13(3)再化为十进制.实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。,31,5）线性四叉树的二维行程编码,右图的压缩处理过程为：1.按Morton码读入一维数组。Morton码：0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 象元值：A A A B A A B B A A A A B B B B2.四相邻象元合并，只记录第一个象元的Morton码。0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3.进一步用游程长度编码压缩。0 3 4 6 8 12 A B A B A B,32,四叉树编码法的优点,1）容易而有效地计算多边形的数量特征；2）阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；3）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；4）多边形中嵌套异类小多边形的表示较方便。,33,四叉树编码缺点,此外，目前应用四叉树还存下列问题：1)矢/栅正反变换还不理想。2)建立四叉树耗费机时很多。3)四叉树虽可修改，但很费事4)四叉树未能直接表示物体间的拓扑关系。5)与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别，6)一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性。,34,5.块状编码(block code),采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元代码组成。右图用12个单位正方形，5个4单位的正方形和2个16 单位的正方形就能完整表示，具体编码如下：(1,1,2,9)，(1,3,1,9)，(1,4,1,9)，(1,5,2,0)，(1,7,2,0)，(2,3,1,9)，(2,4,1,0)，(3,1,1,0)，(3,2,1,9)，(3,3,1,9)，(3,4,1,0)，(3,5,2,7)，(3,7,2,0)，(4,4,1,0)，(4,2,1,0)，(4,3,1,0)，(4,4,1,0)，(5,1,4,0)，(5,5,4,7)特点：一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。,35,栅格数据压缩存储的编码方法,36,起点行列号，单位矢量R:(1,5),3,2,2,3,3,2,3,链式编码,游程长度编码,逐行编码数据结构:行号,属性,重复次数A,4,R,1,A,6,.,块状编码,正方形区域为记录单元数据结构:初始位置,半径,属性(1,1,3,A),(1,5,1,R),(1,6,2,A),四叉树编码,
