|
摘 要 从与传统方法不同的角度着手，以拓扑关系为指导，研究了一种新的由栅格数据转换为矢量数据的方法。与传统转换方法相比，该方法不需对栅格数据进行预处理，它在转换过程中即形成拓扑关系，只需对图像数据逐行处理一次，故适合于大图像的处理。该方法转换效率高、速度快，并在试验中取得了很好的效果。
关键词 栅格结构，矢量结构，转换，拓扑关系 1 引 言 矢量结构和栅格结构是GIS中两种主要的空间数据结构。由于这2种数据结构有各自的优缺点，因此在目前的GIS系统中这2种结构一般都同时存在。遥感信息是地理信息系统非常重要的信息源，而且随着地理信息系统的发展，对遥感信息的依赖性将越来越强［1］；因此，矢量和栅格之间的相互转换的技术显得非常重要，尤其是栅格结构转换到矢量结构的技术。由于矢量和栅格之间的转换在GIS中属于比较经典的问题，因此积累了比较多的方法。但大多方法都来源于传统的边缘跟踪法，由于边缘跟踪法比较费时，处理结果难以形成拓扑关系及需对一些特殊情况进行预处理等缺点，尤其是它需要标记搜索过程，使之难于处理较大图像，因此用边缘跟踪法难于形成比较实用的方法；一些研究者提出的新的方法，如散列线段聚合法［2］、有向边界法［3］等，尽管对边缘跟踪法有一定的改进，但并未从根本上克服边缘跟踪法的上述缺点。本研究以拓扑关系的原理作为指导思想，从一个新的角度研究栅格转换矢量的方法并取得了很好的结果，根据本研究提出的方法，只需对所需要转换的图像数据逐行处理一次，而且整个转换过程即为拓扑关系的形成过程，因此，利用本方法可以处理非常大的图像，且即时形成拓扑关系，不需预处理和后处理，这在传统的转换方法中尚难于实现。 2 转换方法的实现 本研究根据矢量数据的拓扑关系原理，以识别出栅格数据中的结点和坐标点为突破点，然后根据结点和坐标点的信息形成弧段，进而由弧段形成多边形信息，从而完成整个转换过程。本研究的转换过程分3个阶段进行，首先进行结点和坐标点的提取，然后由结点和坐标点形成弧段，最后由弧段形成多边形。转换过程如下所示：
/*结点和坐标点提取阶段*/
读入图像第1行数据；
提取出第1行数据中的结点和坐标点；
while(图像文件未读完)
{
读入1行图像数据；
提取出2行图像数据间的结点和坐标点；
分别写入结点和坐标点数据库；
｝
提取图像最后一行数据中的结点和坐标点；
关闭图像方法；
/*由结点和坐标点形成弧段*/
打开结点和坐标点数据库；
while(结点数据记录未读完)
｛
根据结点能形成弧段的方向，搜索与之连结的结点或坐标点；
if 搜索到的是另一个结点then结束本弧段的搜索，将该弧段的信息写入弧段数据库，继续搜索下一弧段；
else 根据坐标点的类型，决定该弧段下一个搜索的方向。
｝
/*由弧段形成多边形*/
打开弧段数据库；
while(弧段数据记录未读完)
｛
根据弧段的左右多边形属性和结点号，搜索与之连接的、属于同一个多边形的弧段，直到此多边形搜索结束。
选择起始弧段，继续下一个多边形的搜索；
｝
/*整个转换过程结束*/。 2.1 提取结点和坐标点信息 根据图像中相邻4个栅格单元值的异同，可判别出它们中间是否存在结点或坐标点。由相邻4个单元值的异同的各种排列组合，可以判断出坐标点，根据坐标点连接弧段的方向，经归纳，则只可能存在4种类型的坐标点(图1(a))；同样，根据相邻4个单元值的异同，就能够判别出结点，且根据该结点上连接的弧段数及连接方向可知，只能存在5种类型的结点(图1(b))。
根据图1分析的情况，逐行分析栅格单元之间的情况，就能方便快捷地提取出图像中存在的结点和坐标点，并将坐标点的坐标信息、坐标点类型或结点的结点号、坐标和连接的弧段数及连接弧段的方向、相邻4个栅格值等信息分别写入坐标点和结点数据库，以供形成弧段时使用。
对于图像第1行、第1列及最后一行、最后一列，则如图2，假如在图像的上下各增加一行，左右各增加一列单元值为零的栅格，也就无需作特殊的处理了。
图1 栅格图像中可能存在的坐标点和结点类型 (a) 坐标点类型；(b) 结点类型 Fig. 1 The type of node and vertex that exists in image
(a) 待处理的图像 (b) 假设用于处理的新图象 图2 处理图像四周边缘的方法 Fig. 2 The method for processing the edges of image
2.2 由结点和坐标点形成弧段 由结点数据库中已纪录的搜索出来的结点，作为弧段的始结点，根据结点上连接的弧段的方向，搜索该方向上与之相邻的结点或坐标点，如搜索到的是坐标点，则根据该坐标点的类型和弧段与它连接的方向，决定下一个搜索的方向；如搜索到的是结点，则此结点即为该弧段的终结点，此弧段的生成工作结束，形成组成该弧段的信息，写入弧段数据库，同时在终结点上与该弧段连接的方向作上标记，以避免重复搜索；选择始结点上其它未搜索的方向继续进行下一弧段的搜索，直到该结点上连接弧段的方向全部搜索完成；然后开始下一个结点的搜索工作，就这样，直到结点数据库中所有的结点都完成搜索，就生成了该图像中所有的弧段，其信息都记录在弧段数据库中，以供生成多边形时使用。 2.3 由弧段形成多边形 根据弧段数据库中记录的弧段信息，选择一条弧段作为起始弧段，根据弧段的起始和终结点号、结点类型、弧段的左右多边形属性，通过查询弧段数据库，搜索与之相连的、属于同一多边形的弧段，如此重复搜索，直到搜索到的弧段与起始弧段连接，则结束此多边形的搜索，形成该多边形的信息，将此多边形的信息写入多边形数据库，并给属于该多边形的弧段作上标记，以免重复搜索；寻找下一条符合条件的弧段作为起始弧段，进行下一个多边形的搜索，直到所有满足条件的弧段均已搜索过，则完成多边形的生成，从而完成整个转换过程。
经过上述的3个转换过程，获取了结点、弧段及多边形的信息，从而完成了栅格到矢量的转换过程，且同时也已建立了完整的拓扑关系。图2中图像的转换结果如图3。
图3 由图2中图像转换得到的矢量结果
Fig. 3 The result of figure 2's image processed
by the new method 3 方法的可行性及影响速度的因素 为了检验本方法的可行性，我们将整个转换过程编制成程序，选择不同大小、不同复杂程度的图像进行了试验，并记录各个图像转换所需的时间，从表1可以看出，本方法适应性较广、速度也较快，且转换所需的时间与图像的复杂程度有关；由图像转换后所形成的弧段和多边形结果见图4，可以看到，本研究的方法准确地提取出了结点、弧段和多边形，形成了准确的拓扑关系。
图4 供试图像和用本研究转换得到的弧段
及多边形结果图
Fig. 4 The tested image and the results of arcs and
polygons created by the new method 对于传统的边缘跟踪类方法，当图像复杂度不变，而图像扩大时，其处理所需的时间也将成倍增加(典型情况下， 当图像长宽扩大1倍， 其处理时间将增加到4倍左右)，而对于本研究的方法，表1的试验结果已说明了处理时间长短与图像的复杂程度有关，那么图像大小对其影响如何呢?为了说明这个问题，我们将一个图像的长宽分别扩大为原图像的2，4，8，16，32，64和128倍；并分别测定了其转换所需的时间(表2)，从中可以看到，尽管图像扩大了上百倍，而处理时间仅增加了数倍，因此说明图像的大小对本研究方法的影响不很显著，而与图像的复杂程度有明显的关系，这也说明了本文介绍的方法是比较理想的。 表1 本研究方法处理的一些图像的结果*
Table 1 The processing result of images by the new method
供试图像号 行数 列数 所需时间/s 总结点数／个 总弧段数／个 总多边形数／个 总点数(结点+坐标点)／个
1 172 144 12 529 866 417 1713
2 172 144 12 480 816 347 1476
3 131 131 9 386 568 363 2842
4 512 512 293 6159 8599 6308 45716
5 350 579 482 5847 8836 4671 36243
6 406 510 18 344 544 215 11049
7 438 480 768 6926 11417 5308 30876 *处理时间是在AMD K6/166、32M RAM、Win95的软硬件环境下获得
表2 图像大小对本研究方法的影响*
Table 2 The relationship of image's size and the new method
图像长宽扩大的倍数 行数 列数 图像文件长度/字节 处理时间/s 为原图像所需时间的百分比/%
1(原图) 86 72 6192 11 100
2 172 144 24768 12 109
4 344 288 99072 13 118
8 688 576 396288 16 145
16 1376 1152 1585152 21 191
32 2752 2304 6340608 33 300
64 5504 4606 25362342 55 500
128 11008 9212 101449728 113 1027 *软硬件环境与表1相同
4 讨 论 由于本研究采用了与传统的转换方法完全不同的指导思想，以矢量的拓扑关系原理作为从栅格转换到矢量的指导思想，根据拓扑关系的原理来实现转换过程，使转换过程的实现简单、方便、明了，与传统转换方法相比，表现出了很大的优越性。为了使转换过程实现方便，本研究在编程实现中采用关系数据库存储得到的矢量信息，这大大地减轻了编程工作量；但当图像很复杂，搜索到的结点、弧段和多边形数量很大时，则数据库查找的性能成了提高速度的限制因素。从总体上讲，本研究所阐述的方法，由于是逐行处理图像，因此被处理的图像的行列数可以很大，这在实际应用时很有价值；且在转换过程中即形成拓扑关系，无需额外的前处理和后处理，因此，总的来说，本研究的方法对栅格转换到矢量将会有很高的实用价值。 收稿日期：1998-01-04；收到修改稿日期：1998-09-08 《参 考 文 献》 (References) [1] Yan Tailai. Land information system. Literature of Science and Technology Press, 1993. (In Chinese) [严泰来. 土地信息系统. 科学技术文献出版社，1993.］
[2] Huang Bo, Cheng Yong. New approaches for mutual transferring of vector and rester. Remote Sensing Technology and Application. 1995, 10(3): 61-65. (In Chinese) [黄波. 陈勇. 矢量、栅格相互转换的新方法. 遥感技术与应用,1995, 10(3): 61-65.]
[3] Li Zhangcai, Liu Changyan. An efficient directed boundary method for vectorization of dot matrix images. Computer Applications and Software, 1997, 14(3): 48-51. (In Chinese) [李占才，刘春燕. 点阵图形矢量化的高效方法——有向边界法. 计算机应用与软件，1997, 14(3): 48-51.] 作 者 简 介 沈掌泉，男，1969年生，浙江大学助理研究员，目前主要从事遥感和地理信息系统技术在农业中应用方面的研究工作。已发表论文十余篇。 Study on a New Method for Transferring Grid to Vector
Using the Topological Theory SHEN Zhang-Quan WANG Ren-Chao
(Institute of Agricultural Remote Sensing & Information System
Application, Zhejiang University, Hangzhou 310029) Abstract With the different view of traditional methods, in the light of the topological theory, this paper studies a new method for converting raster data to vector data. Compared with traditional methods, the new method does not need to pro-process the raster image, created topological structure of vector data during the conversion. This method processed raster data row by row just one time, and could fit for large image. It, therefore, has high efficiency high speed, and gives good experimental results.
Key words Raster structure, Vector structure, Transfer, Topological theory
|