邬伦_第7章 空间数据管理.ppt

第七章空间数据管理,1空间数据库2栅格数据结构及其编码3矢量数据结构及其编码4矢栅结构的比较及转换算法5空间索引机制6空间信息查询,1空间数据库,1.1地理信息系统与一般管理信息系统比较1.2空间数据库1.3数据与文件组织1.4GIS内部数据结构矢量结构和栅格结构,1.1地理信息系统与一般管理信息系统比较,两者的区别1）在硬件上专用的图形输入输出设备模数转换设备硬件性能要求2）在软件上图形图像数据的分析和处理软件3）在信息处理的内容和采用目的方面,两者共同之处,都是人机系统数据规模大、数据关系复杂都是为管理和决策提供支持和手段,1.2空间数据库,1.2.1数据库的概念1.2.2空间数据库特点1.2.3数据库管理系统,1.2.1数据库的概念,概念空间数据库是一种应用于地理空间数据处理与信息分析领域的具有工程性质的数据库，它所管理的对象主要是地理空间数据（包括空间数据和属性数据），是某一区域内关于一定地理要素及其特征的数据集合。,空间数据库能做什么,空间数据库典型实例卫星影像存储要求（时间序列，大存储量）（NASA,QuickBird,GoogleEarth,GoogleMap）车辆GPS监管土地部门规划管理传统数据库列出长沙市销售额最高的十家蔬果店空间数据库列出中南林附近1000范围内的所有超市找出长沙市内附近500m内有小学的所有售房,1.2.2空间数据库特点,1）数据量特别大2）空间数据和属性数据结合紧密3）数据应用广泛,1.2.3数据库管理系统,采用标准DBMS存储空间数据的主要问题：空间数据记录是变长的关联、连通、包含、叠加等基本操作难以实现不能支持复杂的图形功能地理实体表达复杂，需要跨表、跨文件数据的安全性、一致性、完整性要求高,GIS数据管理方法,开发独立的基于文件的数据管理服务开发一个附加软件用于存储和管理空间数据和空间分析，使用DBMS管理属性数据。（混合模型）对系统的功能进行必要扩充，空间数据和属性数据在同一个DBMS管理之下。（扩展模型）重新设计一个具有空间数据和属性数据管理和分析功能的数据库系统目前大多数商品化的GIS软件都不采取传统的某种单一的数据模型，也不是抛弃传统的数据模型，而是采用建立在关系数据库管理系统(RDBMS)基础上的综合的数据模型。,13数据与文件组织,1.3.1数据组织的分级1.3.2数据间的逻辑联系1.3.3常用数据文件,1.3.1数据组织的分级,1）数据项2）记录3）文件4）数据库,1.3.2数据间的逻辑联系,数据间逻辑联系主要是指记录与记录之间的联系逻辑联系主要有三种：一对一的联系；一对多的联系；多对多的联系。,1.3.3常用数据文件,1）顺序文件2）索引文件3）直接文件（随机文件）4）倒排文件,1.4矢量结构和栅格结构,描述地理实体的数据本身的组织方法，称为内部数据结构。空间数据结构是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。内部数据结构基本上可分为两大类：矢量结构和栅格结构（也可以称为矢量模型和栅格模型）。两类结构都可用来描述地理实体的点、线、面三种基本类型。空间数据编码是空间数据结构的实现。,栅格和矢量数据的主要编码方法,在地理信息系统的空间数据结构中，栅格结构的编码方式主要有直接栅格编码、链码、游程长度编码、块码、四叉树码等；矢量结构主要有坐标序列编码、树状索引编码和二元拓扑编码（如，DIME）等编码方法。,1.4.1矢量模型,矢量模型将现实世界的要素位置和范围用点、线或面表达，每一个实体的位置是用它们在坐标参考系统中的空间位置（坐标）定义。地图空间中的每一位置都有唯一的坐标值。优点：矢量模型中的空间实体与要表达的现实世界中的空间实体具有一定的对应关系。,1.4.2栅格模型,栅格模型将空间规则地划分为栅格（通常为正方形）。地理实体的位置和状态是用它们占据的栅格的行、列来定义的。每个栅格的大小代表了定义的空间分辨率。由于位置是由栅格行列号定义的，所以特定的位置由距它最近的栅格记录决定。栅格模型最小单元与它表达的真实世界空间实体没有直接的对应关系。,栅格数据结构的特点,栅格数据结构结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便。特别适合于FORTRAN、BASIC、C等高级语言作文件或矩阵处理，这也是栅格结构易于为多数地理信息系统设计者接受的原因之一。,2栅格数据结构及其编码,2.1栅格数据结构2.2决定栅格单元代码的方式2.3编码方法,2.1栅格数据结构,定义以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。特点栅格结构的显著特点是：属性明显，定位隐含，即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为相应的坐标。,栅格数据的形状、尺寸及相关问题,栅格结构表示的地表是不连续的，是量化和近似离散的数据。栅格尺寸越小，其分辨率越高，数据量也越大,栅格数据的形状、尺寸及相关问题,栅格数据单元格经常是矩形（主要是正方形）的，但并不是必须如此。其单元格形状可以随应用的需要进行具体设定，比如设置为三角形。,栅格数据的形状、尺寸及相关问题,栅格尺寸较大，则会造成较大的误差，同时由于在一个栅格的地表范围内，可能存在多于一种的地物，而表示在相应的栅格结构中常常只能是一个代码。这类似于遥感影像的混合像元问题例如landsatMSS卫星影像单个像元对应地表7979m2的矩形区域，影像上记录的光谱数据是每个象元所对应的地表区域内所有地物类型的光谱辐射的总和效果,栅格数据的形状、尺寸及相关问题,栅格数据在转换和重新采样时，应尽可能保持原图的数据精度，通常的方法：在保持栅格单元大小不变的情况下，采用不同的方法提取栅格单元代码缩小单个栅格单元的面积，即增加单元的总数，行列数也相应增加,2.2栅格单元代码的取值方式,中心点法面积占优法重要性法百分比法,2.3编码方法,直接栅格编码,压缩编码方法,1）链码（ChainCodes）2）游程长度编码（Run-LengthCodes）3）块码4）四叉树,常见栅格数据压缩编码总结,链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难。游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易。但对破碎数据处理效果不好。块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，但运算效率是其瓶颈。其中四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。,压缩编码的相关问题,同所有的数据结构问题一样，压缩编码过程的主要矛盾也是数据量压缩和运算时间之间的矛盾：为了更有效地利用空间资源，减少数据冗余，不得不花费更多的运算时间进行编码。好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实现,3矢量数据结构及其编码,3.1矢量数据结构3.2编码方法,3.1矢量数据结构,定义：通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体。特点：定位明显、属性隐含，其定位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特定的位置上。,矢量数据结构的基本概念,前导概念：矢量（起点终点）矢量数据结构：通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。在一般情况下，其精度比栅格数据结构高得多。其精度仅受数字化设备的精度和数值记录字长的限制。,矢量数据结构的基本概念,几何体的类型,矢量数据结构的基本概念,矢量数据的类型,矢量数据结构的特点,矢量数据结构图形运算的算法总体上比栅格数据结构复杂的多，在叠加运算、邻域搜索等操作时比较困难，有些甚至难以实现。但其也有便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度。,3.2编码方法,点实体线实体多边形1）坐标序列法（Spaghetti方式）2）树状索引编码法3）拓扑结构编码法,点实体,点是空间上不能再分的地理实体，可以是具体的或抽象的，如地物点、文本位置点或线段网络的结点等，由一对x、y坐标表示。对于点实体，矢量结构中只记录其在特定坐标系中的坐标和属性代码。,点实体数据编码组织方式,线实体,对于线实体，在数字化时即进行量化，就是用一系列足够短的直线首尾相接表示一条曲线，当曲线被分割成多而短的线段后，这些小线段可以近似地看成直线段，而这条曲线也可以足够精确地由这些小直线段序列表示，矢量结构中只记录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认为是以直线段相连，在一定精度范围内可以逼真地表示各种形状的线状地物。,线实体数据编码组织方式,唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找,多边形实体,“多边形”在地理信息系统中是指一个任意形状、边界完全闭合的空间区域。其边界将整个空间划分为外部和内部。多边形数据是描述地理信息的最重要的一类数据。在区域实体中，具有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等。,多边形实体编码,多边形矢量编码不但要表示位置和属性，更为重要的是要能表达区域的拓扑性质，如形状、邻域和层次等，以便使这些基本的空间单元可以作为专题图资料进行显示和操作，由于要表达的信息十分丰富，基于多边形的运算多而复杂，因此多边形矢量编码比点和线实体的矢量编码要复杂得多，也更为重要。,矢量数据结构编码方法,坐标序列法（Spaghetti方式）（实体式）索引式双重独立式链状双重独立式,坐标序列法（Spaghetti方式）（实体式）,由多边形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码。,实体式编码方法示例,实体式编码方法,实体式编码优缺点,优点文件结构简单，易于实现以多边形为单位的运算和显示缺点多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；岛只作为一个单个的图形建造，没有与外包多边形的联系；不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中。,索引式编码方法,索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。,索引式编码方法示例,索引式编码方法示例,线与多边形之间的树状索引,索引式编码方法示例,点与线之间的树状索引,索引式编码方法示例,形成的文件记录,索引式编码方法优缺点,树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错,双重独立式编码,简称DIME(DualIndependentMapEncoding)，是美国人口统计系统采用的一种编码方式，是一种拓扑编码结构。,1、点文件,2、线文件:线文件是以线段为记录单位,3、面文件,关联,邻接,关联,连通,拓扑关系明确,在DIME中做如下改进：将以线段为记录单位改为以弧段为单位,链状双重独立式编码,链状双重独立式编码(拓扑数据结构),链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。,链状双重独立式编码四个文件,1、弧段坐标文件：,2、弧段文件：链面，链结点关系,3、多边形文件,4、点拓扑文件：结点链关系,在拓扑结构中，多边形（面）的边界被分割成一系列的线（弧、链、边）和点（结点）等拓扑要素，点、线、面之间的拓扑关系在属性表中定义，多边形边界不重复。,Map,链状双重独立编码实例,弧段文件弧段号起始点终结点左多边形右多边形a51OAb85EAc168EBd195OEe1519ODf1516DBg115OBh81ABi1619DEj3131BC弧段坐标文件弧段号点号a5,4,3,2,1b8,7,6,5c16,17,8d19,18,5e15,23,22,21,20,19f15,16,g1,10,11,12,13,14,15h8,9,1i16,19j31,30,29,28,27,26,25,24,31,多边形文件多边形号弧段号周长面积中心点坐标Ah,b,aBg,f,c,h,-jCjDe,i,fEc,i,d,b,链状双重独立式编码的特点,拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空间分析时却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象.被一些成熟的商品化软件采用，如ARC/INFO软件。例：ARC文件：二进制文件:弧段号点数坐标串在GIS数据输入中，建拓扑是指给图形数据（点、线、面）增加拓扑结构，如ARC/INFO中，在ARCEDIT中输入图形后，需用BUILD建图形拓扑，具体生成许多文件，如AAT，PAT等.INFO：属性表如AAT（ArcAttributeTable）,用户标识码，表明地物类型当图形数据修改、删除、增加点、线、面要素后，其拓扑关系也发生改变，所以，需重新建拓扑。,4矢栅结构的比较及转换算法,4.1栅格结构与矢量结构的比较4.2相互转换算法,4.1栅格结构与矢量结构的比较,4.2相互转换算法,4.2.1矢量格式向栅格格式的转换4.2.2栅格格式向矢量格式的转换,4.2.1矢量格式向栅格格式的转换,矢量数据直接用于多种数据的复合分析等处理将比较复杂，特别是不同数据要在位置上一一配准，寻找交点并进行分析。相比之下利用栅格数据模式进行处理则容易得多。加之土地覆盖和土地利用等数据常常从遥感图象中获得，这些数据都是栅格数据，因此矢量数据与它们的叠置复合分析更需要把其从矢量数据的形式转变为栅格数据的形式。矢量格式向栅格格式转换要考虑点线面的转换,矢量点的变换,其中X，Y为矢量点位坐标；X，Y分别表示元素的二个边长；Xmin，Xmax表示全图X坐标的最小值和最大值；Ymin，Ymax表示全图Y坐标的最小值和最大值；I，J分别表示全图网格的行数和列数，则它们之间的关系可以表示成:,矢量格式（面）向栅格格式的转换的几个算法,1）内部点扩散算法2）复数积分算法3）射线算法和扫描算法4）边界代数算法,边界代数法、内部点扩散算法和射线法的应用,边界代数法并不可以完全替代其它算法，在某些场合下，还是要采用种子填充算法（内部点扩散算法）和射线算法，前者应用于在栅格图像上提取特定的区域；后者则可以进行点和多边形关系的判断。,4.2.2栅格格式向矢量格式的转换,栅格向矢量转换处理的目的，是为了将栅格数据分析的结果，通过矢量绘图装置输出，或者为了数据压缩的需要，将大量的面状栅格数据转换为由少量数据表示的多边形边界，但是主要目的是为了能将自动扫描仪获取的栅格数据加入矢量形式的数据库。,栅格格式向矢量格式转换的步骤和算法,1）步骤多边形边界提取边界线追踪左右多边形信息记录去除多余点2）多边形栅格转矢量的双边界搜索算法,5空间索引机制,5.1索引概念5.2索引类型,5.1索引概念,空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。比较有代表性的包括BSP树、K-D-B树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。,空间索引的意义,空间索引是对空间图形集合做的一个“目录”，提高在这个图形集合中查找某个图形对象的效率。比如说，我们在一个地图图层上进行矩形选择，确定这个图层上哪些图元被这个矩形所完全包含呢，在没有”空间索引“的情况下，我们会把这个图层上的所有图元，一一拿来与这个矩形进行几何上的包含判断，以确定到底哪些图元被完全包含在这个矩形内。比如我们对一个点图层作了网格索引，判断哪些点在这个矩形选择框内，是不需要把这个图层里所有的点都要与矩形进行几何包含运算的，只对少数几个点做运算。,5.2索引类型,格网型空间索引BSP树空间索引(BinarySpacePartition)KDB树空间索引（K-dimensionsB+树）R树和R+树CELL树,6空间信息查询,6.1基于属性特征查询6.2基于空间关系和属性特征的查询（SQL）6.3一种空间扩展SQL查询语言GeoSQL,6.1基于属性特征查询,利用SQL，我们可以在属性数据库中很方便地实现属性信息的复合条件查询，筛选出满足条件的空间实体的标识值，再到空间数据库中根据标识值检索到该空间实体。,6.2基于空间关系和属性特征的查询（SQL：SpatialQueryLanguage）,在实际应用中，需要地理信息系统提供一些能直接计算空间实体关系的功能。例如：A在某条铁路的东部；（方向关系）B距离该铁路不超过30公里；（度量关系）C城市人口大于70万；（属性）D选择城市在特定的多边形区域内。（拓扑关系）提出了（SpatialQueryLanguage）“空间查询语言”作为解决计算空间实体关系的方案,6.3一种空间扩展SQL查询语言GeoSQL,相对于一般SQL，空间扩展SQL主要增加了空间数据类型和空间操作算子，以满足空间特征的查询。空间特征包含空间属性和非空间属性，空间属性由特定的“Location”字段来表示。空间数据类型除具有一般的整型、实型、字符串外，还具有下列空间数据类型：点类型、弧段类型、不封闭的线类型、（Polygon）多边形类型、图像类型、复杂空间特征类型。,GeoSQL的实现过程,栅格、矢量数据结构,返回,栅格数据的点线面表示示例,点,线,面,返回,中心点法,处理方法：用处于栅格中心处的地物类型或现象特性决定栅格代码常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。,例如：中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C,返回,面积占优法,处理方法：以占栅格区域面积比例最大的地物类型或现象特性决定栅格单元的代码面积占优法常用于分类较细，地物类别斑块较小的情况,例如：所示的例子中，B类地物所占面积最大，故相应栅格代码定为B,返回,重要性法,处理方法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物,例如：假设A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A,返回,百分比法,处理方法：根据栅格区域内各地理要素所占面积的百分比数确定栅格单元的代码适用于地物面积具有重要意义的分类体系,例如：可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字,返回,链式编码(ChainCodes),它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。,链式编码(ChainCodes),线状地物链式编码1，5，3，2，2，3，3，2，3面状地物链式编码5，8，3，2，4，4，6，6，7，6，0，2，1链式编码的前两个数字表示起点的行、列数，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以07的整数代表。,链式编码(ChainCodes),优点：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，比较适于存储图形数据。缺点：对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余。,返回,游程长度编码（run-lengthcode）,编码方案：只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。,游程长度编码示例,(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)用40个整数表达了原始数据中的64个栅格。,游程长度编码（run-lengthcode）,优点压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。缺点对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。,返回,块码（ChainCodes）,块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。,块状编码示例,(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),块码（ChainCodes）的优缺点,一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。,返回,四叉树编码(quad-treecode),四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n2n的栅格阵列，n为极限分割数，n+1为四叉树的最大高度或最大层数，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n2n的图像。,四叉树编码示例,美国马里兰大学地理信息系统的四叉树编码,记录叶子结点的地址和值地址用32位记录，分为层数和路径两部分层数用最右边4位表示路径用左边28位表示，每条路径用两位二进制表示路径编码：SW:00（0）;SE:1（01）;NW:2（10）;NE:3（11）路径位二进制按位交错得到的两个十进制数对应的是以左下角为原点的栅格的行列数,以左图为例，红色的9所在的栅格最右边的4位为：0011（3）左边28位为：0000000(22位)101100（6位）按位交错：110（6行）和010（2列）,四叉树对点状和线状地物的编码,对于只有点状地物或只有线状地物的图件，为了提高效率，设计了略有不同的划分终止条件和记录方法，称为点四叉树和线四叉树。点四叉树对子象限的划分直到每个子象限不含有点或只含有一个点为止，叶子的值则记录是否有点和点在子象限的位置；线四叉树划分子象限直到子象限不含线段或只含有单个线段，对线的结点则划分到单个象素，其叶子值记录更为复杂。,四叉树编码,由上而下的方法运算量大，耗时较长。因而实践中可以采用从下而上的方法建立四叉树编码。对栅格数据按如下的顺序进行检测：如果每相邻四个栅格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。,四叉树编码优缺点,优点：容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；多边形中嵌套异类小多边形的表示较方便。并支持拓扑“洞”（嵌套多边形）的表达，是优秀的栅格压缩编码之一。缺点：其最大不足是其不稳定性，即同样的原始数据应用不同的算法进行编码可能会得到不同的编码结果。不利于数据分析。,四叉树编码结构方式,常规四叉树：除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用,四叉树编码结构方式,线性四叉树：只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于