第三讲 空间数据结构-栅格数据结构

1、第三讲第三讲 栅格数据结构栅格数据结构金毅金毅河南理工大学资源环境学院河南理工大学资源环境学院 454003454003:65585045:65585045电话电话13782806118E_mail: E_mail: 基本概念基本概念p数据结构：数据结构：指数据组织的形式，是适合于计算机存储、指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构管理和处理的数据逻辑结构p空间数据结构：空间数据结构：地理实体的空间排列方式和相互关系地理实体的空间排列方式和相互关系的抽象描述，即地理实体的数据本身的组织方法的抽象描述，即地理实体的数据本身的组织方法p描述内容：描述

2、内容：地理要素和地理现象，包括地理要素和地理现象，包括空间位置空间位置、拓拓朴关系朴关系和和属性属性三个方面三个方面p空间数据结构类型：空间数据结构类型：矢量结构矢量结构和和栅格结构栅格结构矢量矢量/ /栅格数据栅格数据南川市 南川市 李渡区 李渡区 长寿县 长寿县 垫江县 垫江县 渝中区 渝中区 丰都县 丰都县 彭水苗族土家族自治县 彭水苗族土家族自治县 南岸区 南岸区 沙坪坝区 沙坪坝区 江北区 江北区 九龙坡区 九龙坡区 大渡口区 大渡口区 巴南区 巴南区 江津市 江津市 隆昌县 隆昌县 安岳县 安岳县 潼南县 潼南县 大足县 大足县 荣昌县 荣昌县 永川市 永川市 武胜县 武胜县 合川

3、市 合川市 渝北区 渝北区 邻水县 邻水县 石柱土家族自治县 石柱土家族自治县 忠县 忠县 武隆县 武隆县 华蓥市 华蓥市 铜梁县 铜梁县 璧山县 璧山县 北碚区 北碚区 双桥区 双桥区 0.07.5 15.0 22.5 30.0 37.5 km区县区划图区县区划图河流河流机场机场区县界线区县界线主要公路主要公路县区政府驻地县区政府驻地西苑西苑颐和园颐和园西北望西北望玉泉山玉泉山卧佛寺卧佛寺香山香山八大处八大处西郊机场西郊机场黄庄黄庄五里坨五里坨BEIJING1.BMP北京街区铁路水域城区边界Labels of 主要地名主要地名矢量图矢量图 栅格图栅格图 采用一个没有大小的点（坐标）采用一个没

4、有大小的点（坐标）来表达基本点元素时，称为矢来表达基本点元素时，称为矢量表示法。量表示法。 采用一个有固定大小的采用一个有固定大小的 点（面元）来表达基本点（面元）来表达基本 点元素时，称为栅格表点元素时，称为栅格表 示法。示法。矢量矢量/ /栅格数据的显示特点栅格数据的显示特点1 1、栅格数据、栅格数据 p 显式表示：栅格中的一系列像元(点)，为使计算机认识这些像元描述的是某一物体而不是其它物体p 显示特点：属性明显，位置隐含2 2、矢量数据、矢量数据p 隐式显示：由一系列定义了始点和终点的线及某种连接关系来描述，线的始点和终点坐标定义为一条表示地物对象形式的矢量p 显示特点：属性隐含，位置

5、明显矢量矢量/ /栅格数据表现能力的差别栅格数据表现能力的差别p 馒头与包子的区别馒头与包子的区别一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容1. 1. 栅格数据的表示栅格数据的表示p栅格数据结构就是像元阵列的有效组织方法栅格数据结构就是像元阵列的有效组织方法/ /规范，规范，每个像元的行列号确定位置，用像元值表示空间对每个像元的行列号确定位置，用像元值表示空间对象的类型、等级等特征象的类型、等级等特征p每个栅格单元只能存在一个值每个栅格单元只能存在一个值（a a）三角形）三角形（b b） 菱形菱形（c) c) 六边形六边形一一. .栅格数据结构：栅格数据结构

6、：栅格数据主要编码内容栅格数据主要编码内容2. 2. 栅格数据结构的应用模型栅格数据结构的应用模型一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容3. 3. 栅格表征地学对象的规则栅格表征地学对象的规则p点点：用一个相元表示：用一个相元表示p线线：在一定方向上连接成串的相邻像元集合：在一定方向上连接成串的相邻像元集合p面面：聚集在一起的相邻像元集合：聚集在一起的相邻像元集合线线面面点点一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容4. 4. 栅格数据结构：坐标系栅格数据结构：坐标系Y：列：列X：行：行西南角格网坐标西南角格网坐标（X

7、WS，YWS）格网分辨率格网分辨率分辨率越高，则像元的面积分辨率越高，则像元的面积越小，需要像元的数目越多越小，需要像元的数目越多一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容5. 5. 栅格数据取值规则栅格数据取值规则CAB百分比法百分比法面面积积占占优优重重要要性性中心点法中心点法A AC CAABA长度占优法长度占优法一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容5. 5. 栅格数据取值规则栅格数据取值规则ABCD A A C C B A C C B B D C B D D D（1）面积占优法）面积占优法 面积占优法是把栅格

8、中占有最大面积占优法是把栅格中占有最大面积属性值定为本栅格元素的值面积属性值定为本栅格元素的值 一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容5. 5. 栅格数据取值规则栅格数据取值规则（2）中心点法）中心点法 中心点法是将栅格中心点的值作为本栅格元素中心点法是将栅格中心点的值作为本栅格元素的值的值ABCD A A C C B A C C B B D C B D D C一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容5. 5. 栅格数据取值规则栅格数据取值规则（3）长度占优法）长度占优法 长度占优法是将网格中心画一横线长度占优法是将

9、网格中心画一横线, ,然后用横然后用横线所占最长部分的属性值作为本栅格元素的值线所占最长部分的属性值作为本栅格元素的值 ABCD A A C C B A C C B B D C B D D C一一. .栅格数据结构：栅格数据结构：栅格数据主要编码内容栅格数据主要编码内容5. 5. 栅格数据取值规则栅格数据取值规则（4）重要性法）重要性法 重要性法往往突出某些主要属性，对于这些属性，只要重要性法往往突出某些主要属性，对于这些属性，只要在栅格中出现，就把该属性作为本栅格元素的值在栅格中出现，就把该属性作为本栅格元素的值 ABCD A A C C B A C C B B C C B D D C一一.

10、 .栅格数据结构：栅格数据结构：数据组织方式数据组织方式栅格数据文件栅格数据文件像元像元1X坐标坐标Y坐标坐标层层2属性值属性值层层1属性值属性值层层n属性值属性值像元像元2像元像元n栅格数据文件栅格数据文件层层1像元像元1层层2X,Y,属性值属性值像元像元2X,Y,属性值属性值像元像元nX,Y,属性值属性值层层n栅格数据文件栅格数据文件层层1 多边形多边形1层层2属性值属性值像元像元1坐标坐标多边形多边形N像元像元n坐标坐标层层n一一. .栅格数据结构：栅格数据结构：数据组织方式数据组织方式栅格数据文件栅格数据文件像元像元1X坐标坐标Y坐标坐标层层2属性值属性值层层1属性值属性值层层n属性值

11、属性值像元像元2像元像元n栅格数据文件栅格数据文件层层1像元像元1层层2X,Y,属性值属性值像元像元2X,Y,属性值属性值像元像元nX,Y,属性值属性值层层n栅格数据文件栅格数据文件层层1 多边形多边形1层层2属性值属性值像元像元1坐标坐标多边形多边形N像元像元n坐标坐标层层n一一. .栅格数据结构：栅格数据结构：数据组织方式数据组织方式栅格数据文件栅格数据文件像元像元1X坐标坐标Y坐标坐标层层2属性值属性值层层1属性值属性值层层n属性值属性值像元像元2像元像元n栅格数据文件栅格数据文件层层1像元像元1层层2X,Y,属性值属性值像元像元2X,Y,属性值属性值像元像元nX,Y,属性值属性值层层n

12、栅格数据文件栅格数据文件层层1 多边形多边形1层层2属性值属性值像元像元1坐标坐标多边形多边形N像元像元n坐标坐标层层n一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法引子引子p无论如何取值，在计算机中，如果矩阵的每个元素无论如何取值，在计算机中，如果矩阵的每个元素用一个双字节表示，则一个图层的全栅格数据所需用一个双字节表示，则一个图层的全栅格数据所需要的存储空间为要的存储空间为m(行行) n(列列) 2(字节字节)如：一个面积为如：一个面积为100km2的区域，如果网格边长取的区域，如果网格边长取为为1m，每个网格用一个双字节表示，则一个图层的要，每个网格用一个双字节表

13、示，则一个图层的要素就占用素就占用 兆字节的存储空间。兆字节的存储空间。200p 因此，栅格数据的压缩是栅格数据结构要解决的重因此，栅格数据的压缩是栅格数据结构要解决的重要任务要任务一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法为何进行压缩编码为何进行压缩编码p当前计算和存储资源是有限的当前计算和存储资源是有限的p随着科学技术的进步，数据的时、空分辨率在逐步随着科学技术的进步，数据的时、空分辨率在逐步提升提升p通过有效的编码方式对相同数据进行存储改良通过有效的编码方式对相同数据进行存储改良一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法压缩编码过程

14、应遵循的原则压缩编码过程应遵循的原则p编码方法必须是有效的编码方法必须是有效的p编码过程必须是可逆编码过程必须是可逆信息的有损和无损之需求信息的有损和无损之需求p编码方法应能或至少不降低对数据的访问速度编码方法应能或至少不降低对数据的访问速度一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3链式编码链式编码游程长度编码

15、游程长度编码逐行编码逐行编码数据结构数据结构: 行号行号, 属性属性, 重复次数重复次数1, A, 4, R, 1, A, 3块状编码块状编码正方形区域为记录单元正方形区域为记录单元数据结构数据结构: 初始位置初始位置, 半径半径, 属性属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树编码四叉树编码一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801

16、234567起点行列号，单位矢量起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3链式编码链式编码游程长度编码游程长度编码逐行编码逐行编码数据结构数据结构: 行号行号, 属性属性, 重复次数重复次数1, A, 4, R, 1, A, 3块状编码块状编码正方形区域为记录单元正方形区域为记录单元数据结构数据结构: 初始位置初始位置, 半径半径, 属性属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树编码四叉树编码一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法AAAAARAAARAAARAARAAA

17、AAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3链式编码链式编码游程长度编码游程长度编码逐行编码逐行编码数据结构数据结构: 行号行号, 属性属性, 重复次数重复次数1, A, 4, R, 1, A, 3块状编码块状编码正方形区域为记录单元正方形区域为记录单元数据结构数据结构: 初始位置初始位置, 半径半径, 属性属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树

18、编码四叉树编码一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3链式编码链式编码游程长度编码游程长度编码逐行编码逐行编码数据结构数据结构: 行号行号, 属性属性, 重复次数重复次数1, A, 4, R, 1, A, 3块状编码块状编码正方形区域为记录单元正方形区域为记录单元数据结构数据结构: 初始位置初始位置, 半径半

19、径, 属性属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树编码四叉树编码一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3链式编码链式编码游程长度编码游程长度编码逐行编码逐行编码数据结构数据结构: 行号行号, 属性属性, 重复次数重复次数1, A, 4,

20、 R, 1, A, 3块状编码块状编码正方形区域为记录单元正方形区域为记录单元数据结构数据结构: 初始位置初始位置, 半径半径, 属性属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树编码四叉树编码一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法1.1.栅格矩阵法栅格矩阵法pRaster数据是二维表面上地理数据的离散量化值，数据是二维表面上地理数据的离散量化值，对某层而言，对某层而言，pixel值组成像元阵列（即二维数组），值组成像元阵列（即二维数组），其中行、列号表示它的位置。其中行、列号表示它的位置。p在

21、计算机内是一个在计算机内是一个4*4阶的矩阵阶的矩阵。但在外部设备上，。但在外部设备上，通常是通常是以左上角开始逐行逐列存贮以左上角开始逐行逐列存贮。如上例存贮顺。如上例存贮顺序为：序为：AAAAABBBAABBAAABp当每个像元都有唯一一个属性值时，一层内的编码当每个像元都有唯一一个属性值时，一层内的编码就需要就需要m行行n列列3(x,y和属性编码值和属性编码值)个存储单元个存储单元一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法2.2.链式编码法链式编码法p又称为弗里曼链码又称为弗里曼链码(Free-man)或边界链码或边界链码p基本方向可定义为：基本方向可定义为：

22、p如确定原点为像元如确定原点为像元(10，1)，则该多边形边界按顺时针则该多边形边界按顺时针方向的链式编码为方向的链式编码为01234567（10，l），7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法3.3. 游程长度编码法游程长度编码法p又称为又称为Run-Length编码编码p基本原理：基本原理：只在各行只在各行(或列或列)数据的代码发生变数据的代码发生变化时一次记录该代码以及相同代码化时一次记录该代码以及相同代码重

23、复的个数，从而实现数据压缩重复的个数，从而实现数据压缩一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法4.4. 块状编码法块状编码法p块状编码是块状编码是游程长度编码游程长度编码扩大到二维的情况，把多扩大到二维的情况，把多边形范围划分成由像元组边形范围划分成由像元组成的成的正方形正方形，然后对各个，然后对各个正方形进行编码正方形进行编码。p块状编码的数据结构由块状编码的数据结构由初初始位置始位置( (行号，列号行号，列号) )和半和半径，径，再加上记录单元的属再加上记录单元的属性代码组成性代码组成9 99 9990 00 00 00 09009907 77 70 00 0

24、00000 0 0 00 0 0 00 0 0 00 0 0 07 7 7 77 7 7 77 7 7 77 7 7 7(1,1,2,9), (1,3,1,9), (1,4,1,9)(1,5,2,0),(1,7,2,0),一一. .栅格数据结构：栅格数据结构：栅格数据编码方法栅格数据编码方法5.5.四叉树编码法四叉树编码法p又称为四分树、四元树编码。它是一种更有效的压又称为四分树、四元树编码。它是一种更有效的压编数据的方法。它将编数据的方法。它将2n2n像元阵列连续进行像元阵列连续进行4等分，等分，一直分到一直分到小正方形的大小正好与象元的大小相等小正方形的大小正好与象元的大小相等/或或已满足精度要求为止已满足精度要求为止999900009909000090097700000077000000777700007777000077770000777799990000000999990070700000077777700