栅格数据结构研究综述:什么是栅格数据结构
电子商务
栅格数据结构研究综述
◆高建勇 山西省地质测绘院
【摘 要】栅格数据结构是GI S 的最基本的数据结构, 本文从栅格单元的形状和大小、多级栅格结构和区域对象栅格结构几个方面, 对近年来国
内外该方面的研究工作进行归纳和分析, 并对变精度的栅格数据结构的表达等问题进行了分析。 【关键词】栅格数据结构 GI S 一、引言
空间数据结构是便于计算机处理的空间数据的组织方式(陈述彭等, 1999) 。栅格数据结构是一种最基本的数据组织方式, 它具有适合表达空间上连续分布的现象, 能对点、线、面和表面进行统一的存储, 分析流程简单, 快速执行表面分析和距离分析, 以及对复杂数据的叠置效率高等优点。合理的数据结构能对信息进行合理有效的表达, 并有效地提高计算速度。随着遥感技术的迅速发展, 高分辨率的遥感影像数据的获取已日益方便, 这也使得数据量更加庞大、数据更为复杂, 采用何种方式对这些海量的栅格数据进行有效地组织, 就显得极为重要。虽然已有一些相对成熟的栅格数据结构, 如完全栅格结构、游程编码结构、四叉树结构等, 但这方面的研究仍具有重要的意义。 二、国内外研究现状
1. 栅格单元形状和大小的研究。常用的栅格单元都是正方形, 林辉等(2001) 通过几何分析和证明, 指出在正三角形、菱形、圆形、矩形、正六边形几种图形中, 用正六边形作为栅格单元更为优越, 六边形可以在相同数据量下, 提高数据的精度, 情况下, 减少数据量. , 大的误差这样的假设. , 所产生的误差就越小, . , 随, 情况并不尽然, 甚至可能栅格单元的周长越短, 它所包含的地理要素更多。
2. 多级(层次) 栅格结构的研究。层次栅格结构是将地理空间划分为若干个较大的子单元, 如果其中的某些块内的类型仍有多种, 再将其细分成若干个子单元块, 依次类推, 直到单元内的类型值单一或者达到所需要的精度要求为止. 四叉树结构就是一种流行的层次结构, 它是一次将空间四等分, 通过树状结构来记录这种划分, 并通过四叉的树状结构实现查询、修改和分解. 四叉树结构具有可变的分辨率(邬伦, 2001, Renliang Zhao 等, 2002) , 对于数据的操作和运算效率较高。基于四叉树的结构目前已在空间建模、空间查询、空间分析、空间推理、生成Vor onoi 图等方面都有应用(D. Papadias, Y . Theodoridis, 1999; Renliang Zhao 等, 2002; Sabine Ti m pf, Andre w, 2000; U . Frank, G . P . Patil, J. Balbus, 1997) 。
Ant oniMoore (2002) 所提出的四叉圆形树结构, 是另外一种四叉树结构, 通过优化和递归的方法, 用尺寸不断减小的圆来划分空间. 对于不规则的边界(如海岸线等) , 通过这种圆形树结构可以达到较好的光滑效果, 但这种方法不能对空间进行完全划分, 在相邻的圆之间存在着缝隙, 这样就很可能会漏掉一些地理要素. 虽然也可以通过一定的方法进行改进, 如将相邻的两个圆通过切线连接, 但还会存在一定的误差。
徐璐等(2005) 采取了对数据进行分块和分层的思想。首先, 利用金字塔分级结构存放多种空间分辨率的栅格数据, 将相同分辨率的栅格数据组织在一个层上, 越靠近顶层的栅格数据精度越小, 数据量也越小, 而越靠近底层, 数据的精度越大, 数据量也越大. 再在每一层上, 将整个空间按照一定的大小分成若干个大小相等且互不重叠的块, 对每一个块编号, 并建立索引。
仉天宇等(2003) 在研究海洋GI S 时, 提出了适合海洋GI S 水体的多级化栅格型数据结构-一种综合空间尺度和空间分辨率的多级格网系统. 其思想是加大局部格网的分辨率, 只在研究的区域内采用比较密集的网格, 而在其它地区, 采用比较稀疏的网格. 该方法可以减少因海洋中尺度的空间量级差大而带来的大量的数据冗余, 同时能满足不同的分辨率需求. 但只是给出了方法的大体思路, 而没有给出详细的数据结构形式。
3. 区域对象栅格结构。澳大利亚的塔斯马尼亚大学的人工智能和空间系统研究组(R. N. W illiam s and J. S . Hartnett, 1998) 提出了最小栅格(m ini -raster ) 的空间数据结构, 通过图像分割技术, 把卫星影像分割成一个个空间对象, 每个对象用它的最小栅格来表示。最小栅格是指
354
每个对象的外接矩形在影像中所覆盖的范围。利用最小栅格生成一个二值的模板来精确定义对象的空间范围, 模板中用1表示栅格单元在对象的外接矩形内, 0表示在外接矩形之外。最小栅格数据结构可以完整地存储影像中所定义的空间对象的信息, 对象的属性值以及小的对象集合之间的关系可以很方便地获得。尽管这种数据结构在存储效率上不比矢量数据结构及一些较复杂的栅格结构(如四叉树结构) 高效, 但这种结构可以简单的二维二进制数组的形式进行存储和操作, 因此其计算的速度很快。同时这种方法只能解决在空间上没有重叠的空间对象, 对具有模糊边界的空间对象也没有提出好的解决方案。
三、结语
数据结构问题是GI S , 一直以来, 国内外的许多学, :
1. , 即整个区域内的栅格栅格单元的形状一般是采用规则的正方形。
2. 层次(分级) 结构中四叉树结构是一种比较成熟且应用广泛的结构, 该结构也有许多不同的形式, 如线性四叉树、规则四叉树、圆形四叉树等, 这些类型都有各自的优缺点和适用范围, 在具体的应用中应该根据数据的特点和应用目的选择适宜的结构。
3. 对于在空间上分辨率(尺度) 发生变化的情况, 目前还没有很好的解决方案。如在海洋、海岸线和大陆交界的地方, 海岸线需要用很高的分辨率来描述, 而海洋和大陆则可以用比较低的分辨率描述, 同时还可以根据研究的目的, 把海洋和大陆也用不同的分辨率进行描述, 由于对于海洋的研究, 一般都涉及到很大的空间范围, 因此数据量都相当庞大, 但采用变分辨率(变精度) 的方法就既可以对需要详细表达的局部信息进行详细的描述, 又不会造成太大的数据冗余。
4. 通过对现有的栅格数据结构的分析、总结和思考, 对变精度的栅格数据结构的表达采用这样的方法:根据不同的分辨率需求, 采用分块的方法把空间分成不同的块, 每一块具有相同的空间分辨率。在同一块内再采用四叉树结构, 逐次将空间四等分, 以此来减少数据冗余, 并保证数据操作的高效。
参考文献:
[1]林辉, 彭长辉. The Role of Raster P ixel Size and Shape in Geo 2graphic I nfor mati on Syste m [J ].遥感信息, 2001(1)
[2]邬伦, 刘瑜, 张晶, 马修军, 韦中亚, 田原. 地理信息系统原理、方法和应用北京:科学出版社, 2001
[3]陈述彭, 鲁学军, 周成虎. 地理信息系统导论[M].北京:科学出版社, 1999
[4]朱凌, 秦其明, 孙家. 基于树结构的数字遥感图像存储方法与应用[J ]地理与地理空间信息, 2003, (4)
[5]仉天宇, 周成虎, 邵全琴. 海洋GI S 数据模型与结构[J ].地球信息科学, 2003(4)
[6]徐璐. 栅格数据在数据库中的存储和优化[J ].现代计算机, 2005(4) [7]C・R ・Valenzuela,M ・F ・Baumgardner . 对专题图合适栅格尺寸的选择[J ].I TC JOURNAL, 1990(3)
[8]Ka m SP, Hoanh C, A lvaran A. A rea rep resentati on err ors ass ociat 2
ed with rasterizati on [J ].I n Pr oceedings of 4th I nternati onal Sy mposium on Spatial Accuracy A ssess ment in Natural Res ources and Envir onmental Sci 2ences . AMSTERDAM, NETHERLANDS, JUL 12-14, 2000
[9]A.M. SHORTR I D GE . Geometric variability of raster cell class as 2signment[J ].I nternati onal Journal of Geographical I nf or mati on Science . VOL. 18, NO. 6, SEPTE MBER 2004, 539–558
1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.