7-基于Morton码的一种二维游程编码方法

基于Morton码的一种二维游程压缩编码方法

孟庆武1孟露2伊海波3

(1. 黑龙江工程学院测绘工程学院，黑龙江哈尔滨150050；2. 东北林业大学林学院，黑龙江哈尔滨150086；3.黑龙江第一测绘工程院，黑龙江哈尔滨150086)

摘要：在分析常规二维游程压缩编码方法缺陷的基础上，提出了一种基于Morton码的二维游程压缩编码方法。该方法按Morton码由小到大顺序扫描栅格数据，对于由2×2个像元组成的格网窗口由Morton码生成格网窗口左上角像元的行列号，并且用动态线性表通过对比像元的属性值，存储压缩结果，建立二维游程编码。实验表明，该编码方法在运行时间和内存占用方面都好于常规二维游程压缩编码方法。

关键词：栅格数据；Morton码；二维游程；线性四叉树；压缩编码

A Method of Dynamic Compressing Code Using 2D Run-Length Based on Morton Code

MENG Qing-wu1, WANG Wen-fu1, MENG Lu2, YI Hai-bo3

（1. Technology Institute of Surveying and Mapping,Heilongjiang Institute of Technology,Harbin 150050,China;2. Forecast Institute,Northeast Forestry University,Harbin 150086,China,3.Heilongjiang First T echnology Institute of Surveying and Mapping,150086,China）

Abstract:On base of analysing some disadvatages of the traditional 2D run-length compressing code,a method of dynamic compressing code using 2D run-length is put forward in this paper.The method scans raster data by Morton code from small to large and uses a 2×2 pixels to extract row and column numbers of the left-up pixel by Morton code from the original raster data. It uses a dynamic linear table through comparing among attribute values of the pixels,saves compressing results and makes dynamically 2D run-length code.This experiments show that this method is better than the traditional 2D run-lenth compressing code in the running speed and memory requirement.

Key word:raster data; Morton code;two dimensional run-lenth;linear quadtree;compressing code

栅格数据结构是将地球表面按照一定的大小即分辨率划分为均匀的紧密的相邻的格网单元，每一个格网单元只具有唯一属性值，一个格网代表地球表面的一个小区域，这个格网单元称为像元，其地理位置由其所在的行列号确定，像元的属性值是所表达的空间对象的灰度值，其实质在计算机中栅格数据结构是一个能表达空间对象及其灰度值的二维矩阵。与矢量数据结构相比，用栅格数据结构表达地理要素比较直观，容易实现叠加操作。作为地理信息系统的一种常用的数据结构，栅格数据得到了广泛应用。如用扫描仪扫描的地图数据、遥感数据与数字高程模型数据等，都属于这种数据结构。但栅格数据的缺点也很突出，其数据精度取决于分辨率即像元的大小，当像元由大变小时，像元的数量即个数呈几何级数增加，造成计算机内存占用的急剧增加，同时，根据地理对象的空间自相关性原理，用栅格数据结构所表达的地理对象，其栅格数据的相邻像元属性值具有较强的相关性，这样造成栅格数据的冗余加大。为了提高海量栅格数据的存储和传输的效率，有必要研究高效的栅格数据压缩编码方法。栅格数据压缩编码方法有很多种，如哈夫曼编码法、块式编码法、四叉树编码法和常规游程编码法等，本文主要探讨基于Morton码的一种动态二维游程压缩编码方法。

1 常规二维游程压缩编码法

二维游程压缩编码法是在对传统一维游程压缩编码法的二维扩展,结合了线性四叉树(linearquadtree,LQT)及其Morton码技术。它通过对已经具有的Morton码的栅格图像数据的各个像元进行扫描,其数据结构是先记录起始像元的Morton码地址和属性值;然后依次扫描

具有Morton码地址的下一个像元的属性值并作出判断。若具有Morton码地址的后一个像元的属性值与前一个像元的属性值不同，则记录后一个像元的Morton码地址及其相应的属性值;若后一个像元的属性值与前一个像元的属性值相同，则不作记录，直到最后，并记录最后一个像元的Morton码地址和属性值。这种二维游程编码虽利用了线性四叉树的地址码，然而它比四叉树具有更高的压缩效率，而且对于以后的插入、删除和修改等操作，因不必保持完整的四叉树结构而变得相当简单。而且，线性四叉树和二维游程编码采用了相同的地址码，它们之间的相互转换非常容易和快速。因此,二维游程编码在栅格数据压缩方面得到了广泛应用。

但是常规二维游程编码压缩算法在形成Morton码过程中有明显不足。一是按像元行列号顺序扫描栅格数据，要把每个像元的行列号都必须转换成Morton码，这一过程要占用较长运行时间；二是读取栅格数据的各个像元的属性值，存储在按照Morton码排序的一维数组中即静态线性表中，这一过程也要占用较多的内存。尤其是当像元数量达到数百万或更多时，其所占用的内存更大，运行时间更长。

2动态的二维游程压缩编码法

2.1编码方法的主要思路

动态的二维游程压缩编码方法的主要思路是按照Morton码顺序扫描栅格数据，而不是按照行列号顺序扫描栅格数据，并将扫描的数据动态地存储在线性表中，而不是静态地存储在线性表中。在按Morton码由小到大顺序提取栅格像元属性值的过程中,开辟2×2的格网窗口,通过Morton码生成像元行列号时，只需转换格网左上角的像元，使运行时间得到减少；而且使用线性表可以动态地分配内存的特征，逐一检测各个对比像元的属性，这样就可以用实现动态地压缩的方法来建立二维游程编码，不必开辟专门的新内存区来存储所压缩的结果，使内存得到节省。当结束对数据的遍历访问以后，动态线性表内记录就是所要求的二维游程编码压缩结果，最后把结果写成文件就完成了整个算法。如图1所示，图1(a)为原始栅格数据(6×8矩阵，后两行为补充的位置，属性值为0)，图1(b)给出了动态二维游程压缩结果。

a b

图1 动态的二维游程压缩编码方法

2.2编码的主要步骤

编码方法主要包括以下两个过程:根据Morton码值用位运算生成像元行列号，根据像元行列号提取整个格网窗口的属性值；用动态线性表比较各个格网窗口的属性值进行动态压缩。

2.2.1 用像元行列号提取整个格网窗口的属性值

从栅格数据图像中以2×2的格网窗口(如图1(a)中栅格数据上的粗线框所示)提取4个像元组成的整个格网的属性值。其具体实现过程如下: 首先，由于Morton码值是由行号和列号的二进制数两两错位交叉组合得到，因此可以由Morton码值的二进制数采用位运算分解出行列号的二进制值，其中奇数位二进制数组合的十进制数为对应的行号I，偶数位二进制数组合的十进制数则为对应的列号J。然后，按照这个行列号生成方法，先将2×2的格网窗口中第1个像元的Morton码值用位运算生成栅格数据的起始像元的行列号，该行列号刚好是格网窗口4个像元中左上角那个像元对应的行列号，其他几个像元的行列号就很容易知道，再根据各个像元的行列号就可以从栅格数据中提取相应像元的属性值。采用位操作运算来生成行列号比基于数学公式计算方法效率高很多。

2.2.2 用动态线性表进行压缩

把按上述方法提取的格网窗口中4个像元的属性值依次与动态线性表中(假设s_linetable)尾部数据元素作对比。若某个像元的属性值与尾部数据元素不相同，则记录当前像元的Morton码地址及其属性值，并把该元素插入动态线性表s_linetable的尾部；若像元的属性值与尾部数据元素相同，则不作记录，循环下一个格网窗口。当循环条件结束时，就遍历所有栅格数据，这时，动态线性表s_linetable中的数据就是压缩结果，把它写成文件,整个动态二维游程压缩编码方法结束。动态线性表的存储结构如下:

struct s_linetable{

intm_MD; ∥M D码

intm_Str;} ∥属性值

2.3编码方法的实现

根据上述动态二维游程压缩编码方法的思路,用编程对该方法进行了具体实现，其程序流程如图2所示。

图2 动态二维游程压缩编码方法实现流程图

3 实验与分析

为了验证算法的有效性,特意选取不同大小和复杂程度的栅格数据进行试验，图3给出了一幅BMP图像采用该方法压缩图，把它和原始BMP图像进行对比,两者属性值的分布完全一致，这就验证了动态二维游程压缩编码方法的正确性。

图3 栅格数据压缩图

为了比较该方法与常规二维游程压缩编码方法在内存占用及运行时间上的差异，笔者分别用两种方法进行了实验测试，其实验测试的结果见表1所示。

据表1可知，动态压缩方法的运行效率比常规压缩方法的运行效率提高很大。首先表现在减少了运行时间。在整个编码过程中只一次遍历栅格数据；减少了行列号与Morton码之间的转换次数，该编码法只对格网窗口中左上角的像元进行转换，而不是对每个像元都行列号与Morton码之间的转换。其次表现在减少了内存占用。动态压缩方法利用线性表动态地分配内存空间,在遍历栅格数据的过程中,不断地合并记录属性值相同的相邻像元，不必存储每个像元的Morton码、属性值及其对应关系。而常规压缩方法中，因为栅格数据需要变换成方形矩阵，就必须先开辟2n×2n的一维数组来存储栅格数据。同时动态压缩方法也不需要重新开辟专门的内存区来存储二维游程压缩结果。

4 结束语

通过上面的分析可以看出,动态二维游程压缩编码方法在运行效率和占用内存上都比常规的二维游程压缩编码方法优越。在运行时间上，动态二维游程压缩编码方法比常规二维游程压缩编码方法要快3—4倍，在内存占用量上，动态二维游程压缩编码方法比常规二维游程压缩编码方法要节省2—3倍。动态二维游程压缩编码方法由于采用动态线性表存储技术，在压缩过程中只存储最终压缩结果的格网属性值，不存储所读取每一个像元的属性值，并根据Morton码生成像元行列号，来提取属性值。而常规二维游程压缩编码方法则由于采用静态线性表存储技术，在栅格数据遍历过程中需要将所读取的每一个格网的属性值都要存储，而且还需要由像元行列号生成Morton码。无论动态二维游程压缩编码方法，还是常规二维游程压缩编码方法，都是基于Morton码技术的栅格数据压缩方法，加之二维游程编码比线性四叉树编码具有更高的压缩效率,而且它与线性四叉树编码进行转换也十分方便。因此,动态二维游程压缩编码方法为解决栅格数据的快速压缩存储提供了一种可行的方法。

本文只采用线性表数据结构，对动态二维游程编码方法与常规二维游程编码方法进行了比较，而对采用其他数据结构如堆、栈等以及该方法与其他压缩编码方法如哈夫曼编码法、块式编码法等没有作比较。

参考文献：

［1］王结臣，苪一康，刘杰．GIS中面的游程编码表达、实现与应用[J]．测绘科学，2008,33(4)：26-28．

[2]吴正升，宋玮，王秀莲．基于2维行程的栅格数据快速动态压缩算法[J]．测绘科学技术学报，2007，24（3）：207-209．

[3]谢顺平，都金康，王腊春，顾国琴．基于游程编码的GIS栅格数据矢量化方法[J]．测绘学报，2004，33（4）：323-327．

[4]吴华意，龚健雅，李德仁．无边界游程编码及其矢栅直接相互转换算法[J]．测绘学报，1998，27（1）：63-68．

[5]盛业华，唐宏，杜培军．线性四叉树快速动态编码及其实现[J]．武汉测绘科技大学学报，2000，25（4）：324-328．

[6]杨敏，汪云甲．基于二叉树的栅格数据快速编码及其实现[J]．测绘工程，2001，10（4）：16-18．

[7]梅雪芬，李伟波．基于线性四叉树压缩算法的研究与改进[J]．软件导报，2006，（4）：46-48．

[８]唐宏，盛业华，杜培军．基于十进制Morton码的线性四叉树动态编码方法研究[J]．江苏测绘，1999，22（3）：11-13.

本论文受到“黑龙江省教育厅2010年度（面上）科技研究项目”资助，项目编号：11551411 作者简介：孟庆武，男，1963年9月出生，黑龙江佳木斯人，副教授，硕士，主要从事地理信息系统与大地测量的教学与研究。单位：黑龙江工程学院测绘工程学院地址：哈尔滨市南岗区征仪路298号，和谐家园小区105栋4单元502室，150086，Mqwml126@https://www.wendangku.net/doc/196073789.html,, 136********

孟露，女，1990年5月出生，黑龙江佳木斯人，学生，主要从事地理信息系统研究单位：东北林业大学林学院联系方式：哈尔滨市南岗区和兴路18号，150086

伊海波，男，1963年5月出生，黑龙江鸡西人，高级工程师，学士，单位：黑龙江第一测绘工程院地址：哈尔滨市南岗区测绘路2号，150086.