吴华意^① 龚健雅^② 李德仁^②

(^①湖北大学区域规划研究所，武汉，430062)
(^②武汉测绘科技大学测绘遥感与信息国家重点实验室，武汉，430070)

NON-BOUNDARY RUN-LENGTH ENCODING SYSTEM
FOR RASTER AND ITS RELEVANT ALGORITHMS
Wu 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, together 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 extracting 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)编码的栅格压缩格式及其与矢量格式之间直接相互转换的算法。无边界游程编码具有无矩形边框限制的特点，可随意扩展而无须改变整体参数，特别适合范围不同的两个栅格的各种组合运算。提出的提取多边形算法，可直接在游程上作标记，而不必先还原成非压缩格式，从而节省了内存，提高了速度。
关键词　游程编码 数据转换 地理信息系统
分类号　TP 309.12


1 引 言
　　栅格和矢量数据格式是二维地理信息系统中最常用的两种基本数据格式，它们之间的相互转换是基础地理信息系统的必备功能。
　　栅格数据实际上是一个二维数组，数组的数据表示属性，下标隐式地表达了空间位置，下标是机械的，为了照顾空间位置的完全表达，有许多冗余。因此，在存贮、使用栅格数据时，往往采用压缩格式，常见的压缩格式有链码、游程编码、块码、四叉树等。一般说来，压缩的方法越复杂，压缩的效率越高，但压缩和解压缩算法所用的时间越多。在实际系统中，往往取其折中。游程编码具有直观，算法简单的特点，对于面域数据具有较高的压缩效率，被部分系统采用，但普通的游程编码是对矩形区域进行编码，对一般的面域图形，先得到一个能框住所有多边形的矩形，再进行编码。如要将两张不同矩形范围的栅格图进行逻辑或代数运算，则十分复杂，而且耗费内存，影响效率。
　　通过对普通游程编码的分析，这里提出了一种改进的游程编码，它无须预先给定栅格范围，可以向四周任意扩张而不改变整体参数，同时设计了与矢量格式直接相互转换的算法，由于不必通过非压缩格式作为中间格式，提高了运算效率。

2 无边界游程编码
　　一个游程实际上包括三个数据：初始点，终止点和属性索引值。由于终止点总是下一个游程的初始点，因此，普通的游程编码只记录终止点和属性索引值，并且先给出一个整体参数，即外框矩形，位置用相对于外框矩形的相对数据表示。默认0为第一个游程的初始点，最后一个游程的终止点必定与矩形的右边界相等。栅格的行数与矩形的高度相同。
　　我们对上述方案进行改进。首先，把栅格看成是铺满整个平面的，尽管有意义的部分总是在一个有界的多边形内；其次，规定属性索引值0(或其他特殊值)表示格点无意义，即该格点、不属于栅格所表示的某个多边形；再次，位置用绝对数值表示，可正可负；最后，对于每个行，第一个游程的初始点，即行的起点，为该行的第一个有意义的点，而不是0，因此，两个行的起点不一定相等。
　　改进后的游程编码具有两个特点。一是水平方向，每一行都从有意义的格点开始，到有意义的格点结束，与其他行独立，一行改变了，其他行不受影响，因此每一行可以独立地左右任意延伸。鞘狈较颍粽じ裰械哪骋恍忻挥杏幸庖宓母竦悖虮嗦胧保眯胁挥萌魏渭锹迹闭じ裆舷吕┱呕蚴账跏保灰砑踊蛏境嘤Φ男屑纯伞Ｕ庋ㄒ宓挠纬瘫嗦耄涠啾咝伪呓缫丫谟纬讨校挥幸参扌杈匦伪呖蜃魑宀问虼耍颐浅浦薇呓缬纬瘫嗦搿?BR>　　图1所示栅格的两种游程编码如表1所示(其中无边界游程编码中的游程记录起始点，而不是终止点)：

图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，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所示的栅格，如果某一行的有效格点延伸以至超出矩形框，或者矩形框以外的区域添加了一个新的多边形，一般的游程编码将做很大的变动，首先，矩形框要变，然后，每一行都要重新编码，但对于无边界游程编码，则只要改变相应的行就行了，其它行则不用做任何改动。特别地，当两个栅格进行组合运算时，无边界游程编码不受边界的限制，可以直接对压缩编码进行任意操作，且运算前后的数据结构一致，非常方便。
　　以下两节，给出无边界游程编码与矢量格式之间直接相互转换的算法。算法中的面状地物定义为多个圈的集合，圈即单个多边形，顺时针表示内部属于该面状地物，称为外圈，逆时针表示挖去的“洞”，称为内圈，有时也称圈为多边形，圈由孤段组成。

3 矢量直接转化为无边界游程编码
　　从矢量到栅格的转换方法有平行线扫描法、铅垂线射线法、内部点扩散法、边界代数法等^{［１］［２］}。这些算法都需要逐个栅格点进行判断和处理，比较费时。这里，用改进的边界代数法^［３］，直接将矢量转换为游程，一次操作就完成一排栅格，所有的操作都以游程为单位进行。

图2 边界跟踪
Fig.2 Tracing of boundary

　　算法要点：(1) 边界跟踪。按圈—弧段—直线段的层次循环跟踪。对每个直线段，以斜向上(其它方向对称处理)的线段AB为例，如图2所示，跟踪步骤如下：　　
　　a. 计算离开线段AB的始点A(X_A,Y_A)和终点B(X_B,Y_B)的最近的格网交叉点P_A（X_A,Y_A）和P_B（X_B，Y_B）。
　　b. P_A是栅格中跟踪的始点。计算P_Ａ离开线段AB的距离(已经乘上一个常系数，即AB的长度)：

Ｄ₀＝(y_A-Y_A)_*(X_B-X_A)-（x_A-X_A）_*（Y_B-Y_A）

D₀>0表示点P_A在AB的左边，0_０<0表示P_A在AB的右边。
　　c. 假设已跟踪到点P_i（x_i,y_i）,P_i到AB的距离为D_i，下一个候选点是P_i的上面一点P_u或右边一点P_r，它们离AB的距离D_u和D_r分别用以下递推公式计算：
　　D_u=(y_i+1-Y_Ａ)_*(X_B-X_A)-(x_i-X_A)_*(Y_B-Y_A)＝D_i+(X_B-X_A)
　　D_r=(y_i-Y_Ａ)_*(X_B-X_A)-(x_i+1-X_A)_*(Y_B-Y_A)＝D_i-(Y_B-Y_A)
若|D_u|<|D_r|，则第i+1个点P_i+1=P_u,D_i+1=D_u；反之，P_i+1=P_r,D_i+1=D_r
　　d. 对于第i+1个点，若y_i+1=y_Ｂ，则此线段的跟踪结束，否则转c.

表2 游程的叠加操作

Tab.2 Overlay operation of run-length

nCol<0

nCol>0

向上

加游程(nCol,0)

减游程(0，nCol)

向下

减游程(nCol,0)

加游程(0，nCol)

　

(2)游程的叠加。在边界跟踪的过程中，若跟踪方向为向上或向下，按表2的方式进行游程的叠加操作，游程的叠加操作包括游程属性值的加减代数运算和位置参数的操作，如游程的分裂、合并、平移、挤压等。表2中的nCol为当前跟踪点的列位置，“加(减)游程(nFromCol，nToCol)”指在相应的行，从nFromCol到nToCol，所有栅格点的属性索引值加上(减去)正在跟踪的多边形的属性索引值。如果nFromCol落在原来的某个游程中间，则要先将原来的游程在nFromCol处分裂，再在分裂出来的后一个游程加减属性值。nToCol的情形类似处理。
　　若跟踪方向向左或向右，或nCol=0，则不对游程进行操作。
　　图3以属性索引值为1的矢量多边形abc为例，示意直接将矢量多边形栅格化为无边界游程编码的过程。依次跟踪ab,bc,ca,跟踪的每一步，若为向上或向下，按表2的规定加上或减去1，最后得到无边界游程编码表示的栅格。注意，图中的行都是以游程为单位进行操作的。

图3 矢量多边形直接转化为无边界游程编码表示的栅格
Fig.3 Direct transformation of polygon from vector to NBRL

(3) 简化。通过上述方法得到的无边界游程栅格，可能会产生连续的两个游程具有相同的属性索引值。此时，将两个游程合并，即将后一个游程删除，也可以在游程叠加的同时进行简化。

4 直接从无边界游程编码提取多边形
　　栅格向矢量转化的直观算法是在二维数组上跟踪弧段并作标记，然后用弧段构造多边形及其拓扑关系。标记是在跟踪的过程中作的，预先不能确定标记作在哪一个格点上，相邻格点上的标记并无相关或一致的关系，而压缩总是利用相邻格点的相关性，因此，试图直接从压缩栅格获得矢量数据，如何作标记，是问题的关键。
　　算法要点：
　　(1) 标记位。为了在跟踪多边形时作标记，在游程的属性值一项中保留两位用于作标记，即将原来的属性项用结构表示：
　　typedef struct tagATTR
　　{
　　int nLeftFlag:1; // 左标记
　　int nRightFlag:1;// 右标记
　　int nAttr;// 属性索引值
　　} ATTR；
　　其中的标记位用1表示已作标记，用0表示未作标记。左标记表示游程的初始位置(左边)已经跟踪，右标记表示游程的终止位置(右边)已经跟踪。
　　(2) 跟踪入口点和第一步。在无边界游程编码的栅格中，按从下到上、从左到右的顺序，搜索栅格中的第一个还没有完全标记的游程。若游程没有作左标记，这个游程的初始端点是一个还没有提取的外圈的跟踪入口点，跟踪的第一步为向上(图4)，跟踪的结果为一个顺时针的圈。若游程作过左标记，没有作右标记，这个游程的终止端点是一个还没有提取的内圈的跟踪入口点，跟踪的第一步为向右(图5)，跟踪的结果为一个逆时针的圈。圈的属性为这个游程的属性值。

图4 外圈跟踪的入口点 图5 内圈跟踪的入口点
Fig.4 Trace-into position Fig.5 Trace-into position of outer circle of inner circle

　　(3) 跟踪方向。若跟踪外圈，如图6所示，以当前步的右格为参照格点(格点0)，从参照格点开始沿逆时针方向依次编号。其中格点3的属性肯定和参照格点相异。依次将格点1、格点2与参照格点比较，一旦遇到与参照格点属性相异的格点，即确定了下一步的方向。

图6 外圈的跟踪方向
Fig.6 Tracing direction of outer circle

　　若跟踪内圈，如图7所示，以当前步的左格为参照格点(格点0)，从参照格点开始沿顺时针方向依次编号。其中格点3的属性肯定和参照格点相异。依次将格点1、格点2与参照格点比较，一旦遇到与参照格点属性相异的格点，即确定了下一步的方向。
　　(以跟踪内圈时向左的一步为例)：
　　在(1)、(2)、(3)时，为弧段中间点，在弧段简化时可以删除，其中在情形(2)时，该点是在一条直线上的中间一点，在跟踪时即可删除。在(4)时，为弧段的端点，在弧段简化时不能删除。

图7 内圈的跟踪方向
Fig.7 Tracing direction of inner circle

　　(4) 跟踪点分类。在相邻的四个格点中，若有三种以上(三种或四种)不同的属性值，则该点为弧段的端点，在弧段简化时不能删除。若有两种属性值，如图8，分四种情形

图8 跟踪点的分类
Fig.8 Classification of tracing position

　　(5) 标记。在跟踪的过程中，按表3的规定对当前的游程作标记：
　　图5中的粗竖线表示从图4的入口点开始跟踪，跟踪出外圈时，相关游程上所作的左标记或右标记。

表3 标记方法
Tab.3 Labeling method

跟踪外圈时

跟踪内圈时

向上

左标记

右标记

向下

右标记

左标记

　　　(6) 终止跟踪。按上述方式跟踪外圈或内圈，当跟踪回入口点时，终止当前这个圈的跟踪，搜索新的入口点，继续跟踪，直到搜索不到入口点，结束全部跟踪。此时，所有的多边形都已提取出来。
　　(7) 多边形简化，即去除多余点。通过(2)至(6)的循环，已经得到所有的多边形。根据属性的不同，可以构造面地物，组成一个完整的地物类，相邻的面地物的公共边界总是以同一个弧段分别在左右两个多边形中存贮共两遍，数据一致，但顺序相反。由于此时的弧段是严格按栅格格网的边缘生长的，带有大量的锯齿，一般应进行简化。简化的方法很多，有不同的优化思路^［５］。在这里要求简化后保持拓扑的一致性，即简化前方向相反的同一条弧段，简化后的结果还是同一条弧段，具有相同的端点和内点，只是顺序相反。

5 实验和结论
　　三峡地区的行政区划图(本文略)，包括21个县级行政单位，在微机上将这些多边形直接栅格化到一个1200×800的无边界游程栅格上，花费0.8 s,然后直接从无边界游程栅格提取多边形，花费0.6 s,提取的多边形与原矢量多边形数据相差不到1个像素。
　　综合作者的其它实验，得到如下结论：
　　(1) 无边界游程编码摈弃了矩形边框的限制，给压缩数据的操作更多的灵活性。
　　(2) 无边界游程编码的诸多优点来源于行间编码的独立性。
　　(3) 给出的与矢量数据直接相互转换算法，绕过了非压缩的中间格式，编程实现时，不必开辟大块内存存放非压缩数据，减轻了内存的负担。
　　(4) 无边界流程编码也有它的适用范围。当栅格特别复杂时，无边界游程编码的压缩效率不高，这时因压缩节省下来的内存甚至不足以弥补游程的频繁计算所消耗的内存，此时要寻找其他方法辅助，如分块压缩等。

收稿日期： 1997-07-10， 截稿日期： 1997-10-08。
吴华意，男，33岁，讲师，博士生。
国家杰出青年科学基金项目与国家“九五”重点科技攻关资助项目，编号:49529101及95D0203。

6 参考文献
1 黄杏元，汤勤.地理信息系统概论.北京：高等教育出版社，1989

2 龚健雅.整体GIS的数据组织与处理方法.武汉：武汉测绘科技大学出版社，1993

3 任伏虎.地理信息系统的理论、方法与应用：［博士论文］.北京大学，1989

4 Burrough P. Principles of Geographical Information Systems for Land Resources Assessment.Clarendon Press,1986

5 Pikaz A et. Optimal Polygonal Approximation of Digital Curves. Pattern Recognition,1995,28(3):373~379

上一篇：GML、SVG、VML的比较

下一篇：GIS简介--什么是GIS ？