《无边界游程编码及其矢栅直接相互转换算法》由会员分享，可在线阅读，更多相关《无边界游程编码及其矢栅直接相互转换算法（11页珍藏版）》请在金锄头文库上搜索。
1、无边界游程编码及其矢栅直接相互转换算法无边界游程编码及其矢栅直接相互转换算法地理信息系统论坛(GIS Forum)-学术论文 论坛 BBS 学术论文 技术资料 文件格式 GIS 标准化 共享软件 GIS链接 测绘学报ACTA GEODAETICA et CARTOGRAPHICA SINICA1998 年 第 27 卷 第 1 期 No.1 farbary 1998无边界游程编码及其矢栅直接相互转换算法* 吴华意 龚健雅 李德仁(湖北大学区域规划研究所，武汉，430062)(武汉测绘科技大学测绘遥感与信息国家重点实验室，武汉，430070)NON-BOUNDARY RUN-LENGTH ENC
2、ODING SYSTEM FOR RASTER AND ITS RELEVANT ALGORITHMSWu Huayi Gong Jianya Li Deren(Institute of Regional Planning, Hubei University, Wuhan， 430062)(LIESMAS, WTUSM, Wuhan, 430070)Abstract A new run-length encoding system for compression of raster data, Non-Boundary Run-Length(NBRL) encoding system, tog
3、ether with algorithms for direct transformation between vector data and compressed raster, are proposed in this paper. The code eliminates the limitation of rectangle boundary, which makes it easy for two raster of different size to fulfill various combination operations. The algorithm of directly e
4、xtracting polygon from the compressed raster, taking the advantage of to label on run-length freely, leaves out the step of restoring NBRL to non-compressed format and gains high efficiency.Keywords Run-length encoding system, Data transformation, Geographic information system摘 要 本文提出了无边界游程(NBRL)编码的
5、栅格压缩格式及其与矢量格式之间直接相互转换的算法。无边界游程编码具有无矩形边框限制的特点，可随意扩展而无须改变整体参数，特别适合范围不同的两个栅格的各种组合运算。提出的提取多边形算法，可直接在游程上作标记，而不必先还原成非压缩格式，从而节省了内存，提高了速度。关键词 游程编码 数据转换 地理信息系统分类号 TP 309.121 引 言栅格和矢量数据格式是二维地理信息系统中最常用的两种基本数据格式，它们之间的相互转换是基础地理信息系统的必备功能。栅格数据实际上是一个二维数组，数组的数据表示属性，下标隐式地表达了空间位置，下标是机械的，为了照顾空间位置的完全表达，有许多冗余。因此，在存贮、使用栅格
6、数据时，往往采用压缩格式，常见的压缩格式有链码、游程编码、块码、四叉树等。一般说来，压缩的方法越复杂，压缩的效率越高，但压缩和解压缩算法所用的时间越多。在实际系统中，往往取其折中。游程编码具有直观，算法简单的特点，对于面域数据具有较高的压缩效率，被部分系统采用，但普通的游程编码是对矩形区域进行编码，对一般的面域图形，先得到一个能框住所有多边形的矩形，再进行编码。如要将两张不同矩形范围的栅格图进行逻辑或代数运算，则十分复杂，而且耗费内存，影响效率。通过对普通游程编码的分析，这里提出了一种改进的游程编码，它无须预先给定栅格范围，可以向四周任意扩张而不改变整体参数，同时设计了与矢量格式直接相互转换的
7、算法，由于不必通过非压缩格式作为中间格式，提高了运算效率。2 无边界游程编码一个游程实际上包括三个数据：初始点，终止点和属性索引值。由于终止点总是下一个游程的初始点，因此，普通的游程编码只记录终止点和属性索引值，并且先给出一个整体参数，即外框矩形，位置用相对于外框矩形的相对数据表示。默认 0 为第一个游程的初始点，最后一个游程的终止点必定与矩形的右边界相等。栅格的行数与矩形的高度相同。我们对上述方案进行改进。首先，把栅格看成是铺满整个平面的，尽管有意义的部分总是在一个有界的多边形内；其次，规定属性索引值 0(或其他特殊值)表示格点无意义，即该格点、不属于栅格所表示的某个多边形；再次，位置用绝对
8、数值表示，可正可负；最后，对于每个行，第一个游程的初始点，即行的起点，为该行的第一个有意义的点，而不是 0，因此，两个行的起点不一定相等。改进后的游程编码具有两个特点。一是水平方向，每一行都从有意义的格点开始，到有意义的格点结束，与其他行独立，一行改变了，其他行不受影响，因此每一行可以独立地左右任意延伸。二是竖直方向，若栅格中的某一行没有有意义的格点，则编码时，该行不用任何记录，当栅格上下扩张或收缩时，只要添加或删除相应的行即可。这样定义的游程编码，其多边形边界已经隐含在游程中，没有也无需矩形边框作为整体参数，因此，我们称之为无边界游程编码。图 1 所示栅格的两种游程编码如表 1 所示(其中无
9、边界游程编码中的游程记录起始点，而不是终止点)：图 1 一个栅格的例子Fig.1 An example of raster data表 1 两种游程编码的比较Tab.1 Comparison of two run-length encoding systems一般的游程编码 无边界游程编码 矩形边界 -6，-6，6，6 游程数据 11 12，0 10 5，0，6，1，12，0 -1，1，0，0 9 4，0，6，1，7，0，9，2，12，0 -2，1，0，0，1，2，3，0 8 3，0，7，1，12，2 -3，1，1，2，6，0 7 2，0，5，1，7，0，9，2，12，0 -4，1，-1，0，
10、1，2，3，0 6 3，0，4，1，10，2，12，0 -3，1，-2，2，4，0 5 12，0 4 5，2，7，1，10，2，12，0 -6，2，-1，1，1，2，4，0 3 2，0，5，2，7，1，9，2，12，0 -4，2，-1，1，1，1，3，0 2 4，0，8，2，12，0 -2，2，2，0 1 6，0，7，1，12，0 0，2，1，0 0 12，0 比较两种游程编码的数据量，一般情况下，无边界游程编码的每一行比普通游程编码少两个数据。无边界游程编码的更重要的优点在于它的行之间的独立性，图 1 所示的栅格，如果某一行的有效格点延伸以至超出矩形框，或者矩形框以外的区域添加了一个新的多边
11、形，一般的游程编码将做很大的变动，首先，矩形框要变，然后，每一行都要重新编码，但对于无边界游程编码，则只要改变相应的行就行了，其它行则不用做任何改动。特别地，当两个栅格进行组合运算时，无边界游程编码不受边界的限制，可以直接对压缩编码进行任意操作，且运算前后的数据结构一致，非常方便。以下两节，给出无边界游程编码与矢量格式之间直接相互转换的算法。算法中的面状地物定义为多个圈的集合，圈即单个多边形，顺时针表示内部属于该面状地物，称为外圈，逆时针表示挖去的“洞” ，称为内圈，有时也称圈为多边形，圈由孤段组成。3 矢量直接转化为无边界游程编码从矢量到栅格的转换方法有平行线扫描法、铅垂线射线法、内部点扩散
12、法、边界代数法等 。这些算法都需要逐个栅格点进行判断和处理，比较费时。这里，用改进的边界代数法 ，直接将矢量转换为游程，一次操作就完成一排栅格，所有的操作都以游程为单位进行。图 2 边界跟踪Fig.2 Tracing of boundary算法要点：(1) 边界跟踪。按圈弧段直线段的层次循环跟踪。对每个直线段，以斜向上(其它方向对称处理)的线段 AB 为例，如图 2 所示，跟踪步骤如下： a. 计算离开线段 AB 的始点 A(XA,YA)和终点 B(XB,YB)的最近的格网交叉点 PA（XA,YA）和 PB（XB，YB） 。b. PA 是栅格中跟踪的始点。计算 P离开线段 AB 的距离(已经乘
13、上一个常系数，即 AB 的长度)：0(yA-YA)*(XB-XA)-（xA-XA）*（YB-YA）D00 表示点 PA 在 AB 的左边，00 向上 加游程(nCol,0) 减游程(0，nCol) 向下 减游程(nCol,0) 加游程(0，nCol) (2)游程的叠加。在边界跟踪的过程中，若跟踪方向为向上或向下，按表 2 的方式进行游程的叠加操作，游程的叠加操作包括游程属性值的加减代数运算和位置参数的操作，如游程的分裂、合并、平移、挤压等。表 2 中的 nCol 为当前跟踪点的列位置， “加(减)游程(nFromCol，nToCol)”指在相应的行，从 nFromCol 到 nToCol，所有
14、栅格点的属性索引值加上(减去)正在跟踪的多边形的属性索引值。如果 nFromCol 落在原来的某个游程中间，则要先将原来的游程在nFromCol 处分裂，再在分裂出来的后一个游程加减属性值。nToCol的情形类似处理。若跟踪方向向左或向右，或 nCol=0，则不对游程进行操作。图 3 以属性索引值为 1 的矢量多边形 abc 为例，示意直接将矢量多边形栅格化为无边界游程编码的过程。依次跟踪 ab,bc,ca,跟踪的每一步，若为向上或向下，按表 2 的规定加上或减去 1，最后得到无边界游程编码表示的栅格。注意，图中的行都是以游程为单位进行操作的。图 3 矢量多边形直接转化为无边界游程编码表示的栅
15、格Fig.3 Direct transformation of polygon from vector to NBRL(3) 简化。通过上述方法得到的无边界游程栅格，可能会产生连续的两个游程具有相同的属性索引值。此时，将两个游程合并，即将后一个游程删除，也可以在游程叠加的同时进行简化。4 直接从无边界游程编码提取多边形栅格向矢量转化的直观算法是在二维数组上跟踪弧段并作标记，然后用弧段构造多边形及其拓扑关系。标记是在跟踪的过程中作的，预先不能确定标记作在哪一个格点上，相邻格点上的标记并无相关或一致的关系，而压缩总是利用相邻格点的相关性，因此，试图直接从压缩栅格获得矢量数据，如何作标记，是问题的关
16、键。算法要点：(1) 标记位。为了在跟踪多边形时作标记，在游程的属性值一项中保留两位用于作标记，即将原来的属性项用结构表示：typedef struct tagATTRint nLeftFlag:1; / 左标记int nRightFlag:1;/ 右标记int nAttr;/ 属性索引值 ATTR；其中的标记位用 1 表示已作标记，用 0 表示未作标记。左标记表示游程的初始位置(左边)已经跟踪，右标记表示游程的终止位置(右边)已经跟踪。(2) 跟踪入口点和第一步。在无边界游程编码的栅格中，按从下到上、从左到右的顺序，搜索栅格中的第一个还没有完全标记的游程。若游程没有作左标记，这个游程的初始端点是一个还没有提取的外圈的跟踪入口点，跟踪的第一步为向上(图 4)，跟踪的结果为一个顺时针的圈。若游程作过左标记，没有作右标记，这个游程的终止端点是一个还没有提取的内圈的跟踪入口点，跟踪的第一步为向右(图 5)，跟踪的结果为一个逆时针的圈。圈的属性为这个游程的属性值。图 4 外圈跟踪的入口点 图 5 内圈跟踪的入
