面向移动用户的矢量地图数据压缩方法

陈志荣，尹天鹤，徐财江，周 峰（．宁波工程学院理学院，浙江宁波3506；．宁波市国土资源信息中心，浙江宁波35040）



面向移动用户的矢量地图数据压缩方法

陈志荣1，尹天鹤1，徐财江2，周 峰1
（1．宁波工程学院理学院，浙江宁波315016；2．宁波市国土资源信息中心，浙江宁波315040）

摘 要：随着第4代移动通信技术（4G）的普及以及4核和8核CPU手机的出现，无线网络数据传输能力大幅提升，移动终端性能大为改善．移动用户的广泛参与使得地理信息的采集和上传下载数据巨量，致使有限的带宽传输速率与海量信息传输需求不匹配．针对移动用户对空间数据的高压缩率和高失真度容忍率的需求，提出了一种新的矢量地图数据压缩方法，通过去除冗余点、平移坐标轴和转换数据类型3个步骤，可2次压缩数据．测试结果显示，该方法的综合压缩率接近70%，可有效降低无线网络数据传输负荷，节约移动终端的存储空间．

关 键 词：数据压缩；移动用户；矢量地图数据；位置服务

0 引 言

位置服务（location－based service，LBS）是指采用定位技术获取用户终端的位置信息，通过移动通信网络，在电子地图平台的支持下为用户提供定位、导航、查询和识别等与空间位置相关的增值服务业务［1］．位置服务是高速移动互联网技术与地理空间信息技术相结合的产物，它以移动通信技术为承载平台，通过移动终端为广大移动用户提供信息类业务（如旅游、天气、交通、问路、黄页、广告）、娱乐类业务、车辆调度业务、跟踪类业务和急救类业务等各种基于位置的空间信息服务，被全球许多移动运营商和咨询机构视为下一代移动网络的核心业务．相对于普通电脑客户端，移动终端是指借助无线网络技术接入网络的具有有限计算资源的设备［2］．在利用移动地理信息服务时，移动用户不仅受到无线网络带宽窄和稳定性差的限制，也受到移动设备存储空间小、显示屏小且分辨率低和CPU计算能力弱的限制，从而对海量空间数据的存储、传输、显示和分析存在困难［3］．为使移动空间数据尽可能简洁，空间数据的压缩显得尤为重要．

当前位置服务中的基础地图数据由道路、行政区划、房屋、公交站点等点状、线状及面状矢量数据构成．对移动空间信息服务中空间数据的压缩，主要是对其中的矢量数据的压缩．点状图形要素可以看成是特殊的线状图形要素，面状图形要素的基础也是线状图形要素，由一条或多条线状图形要素围成［4］．因此，线状图形要素的压缩就成为矢量数据压缩中最重要的问题．一般而言，矢量数据压缩是从组成曲线的点集合A中抽取一个子集B，用这个子集B在一定的精度范围内尽可能地反映原数据集合A，而这个子集B的点数应尽可能少［5］．当前矢量数据压缩方法主要有距离控制类方法（如垂距限值法和曲线多边形逼近算法，后者通常也称Douglas－Peucker方法［6－8］）、角度控制类方法（如角度限值法［9］）以及基于小波技术的压缩方法［10］等．近年来，矢量地图数据压缩方面的研究主要集中在Douglas－Peucker方法的完善和改进上，如尹路等［11］将空间对象间的拓扑关系因素添加到算法中，李帅等［12］提出一种改进的矢量曲线特征点提取方法．部分学者提出了一些新的矢量数据压缩思路，如谭国律等［13］利用动态规划思想，讨论单实体和多实体矢量数据的压缩方法；余先川等［14］利用整数小波变换方式处理坐标数据，实现了较高压缩比的空间矢量数据无损压缩；李青元等［15］提出了利用int甚至short型代替float和double型来存储空间坐标点的方法，以取得较高压缩比例．这些方法主要面向传统的空间数据管理需求，对压缩后的数据精度要求较高．随着WebGIS（网络地理信息系统）的广泛应用和移动位置服务的逐渐深入，提出了有限带宽场景下的矢量数据压缩新需求，如赵艳伟等［16］提出因受到互联网带宽的限制，WebGIS数据传输效率低的问题；柯敏毅等［17］对主流的矢量地图数据压缩技术在移动GIS中应用的优缺点进行了分析与比较；秦斌等［18］针对移动GIS压缩存储和传输的要求，改进了Douglas－Peucker算法；陈涛等［19］针对嵌入式设备硬件条件的限制，对矢量和栅格地图数据进行了LOD分层、压缩、分块和建立索引等一系列处理．这些方法虽部分解决了有限带宽带来的问题．然而，专门针对移动位置服务的空间数据压缩方法的研究仍较少．

在移动位置服务中，由于受到移动终端屏幕尺寸、分辨率和存储空间的限制，对数据压缩的精度要求较低，而对压缩量要求较高．总体而言，用户对空间数据压缩的需求有所变化（见图1）．现有的矢量数据压缩方法在一定程度上还有较大的改进空间．基于此，设计了一种面向移动用户的矢量地图数据压缩方法，并进行了大规模的数据测试分析，验证了该方法的有效性和可行性．

图1　用户对空间数据压缩需求的变化Fig．1 Changes of users demand in the spatial data

1 压缩方法设计

围绕移动用户对空间数据压缩率要求高、失真度容忍率高的新需求，本方法通过去除冗余点、平移坐标轴、转换数据类型3个步骤，分2次压缩数据，尽最大可能提高矢量地图数据的综合压缩率，压缩流程如图2所示．其中，去除冗余数据点和转换数据类型，均为有损压缩．

1．1 去除冗余数据点

空间数据在制作过程中，人工制图或通过智能软件自动提取遥感影像边界时，不可避免会产生一些冗余数据，从而增大了地图数据量．在移动位置服务中，去除冗余点是精简数据的必要步骤．作为优选，本研究采用经典Douglas－Peucker方法进行冗余点去除．Douglas－Peucker方法一般以递归方式实现，为了提高算法效率，本文将采用非递归形式代替递归形式．其算法流程如图3所示．

图2　压缩方法设计Fig．2 Compression method design

图3　Douglas－Peucker算法的非递归形式Fig．3 Non recursive form of Douglas－Peucker algorithm

（1）确定矢量地图数据曲线的始点和终点，按顺序将矢量地图数据中从始点到终点的所有数据点输入数据源，同时确定误差允许范围dmax；

（2）计算经过始点和终点的直线方程y＝kx＋b，计算始点和终点之间各个点到直线y＝kx＋b的距离，选取与直线y＝kx＋b距离最大的点P，得最大距离hmax，其中k为直线的斜率，b为直线在纵坐标轴上的截距；

（3）如果hmax＜dmax，则删除始点和终点之间的数据点，以直线y＝kx＋b代替整条弧线；如果hmax≥dmax，则P为保留点，利用同样的方法对始点与P点之间的曲线、P点与终点之间的曲线上的数据点进行检测，以确定下一批保留点，依此循环，直至两端点之间曲线上的数据点与两端点连线的距离最大值小于dmax为止．

1．2 坐标轴平移

空间数据的坐标值通常采用double精度的（x，y）存储．一般情况下，同一个图斑上的数据点坐标值差别最多从百位开始，如县市行政边界．移动用户常用的位置服务以城市内服务为主，如兴趣点搜索、导航等，这些服务所需用到的地图数据（如居民区图斑），其数据点间坐标值差别通常仅为小数点后面的数值．因此，可在1．1节得到的精简后的线状数据基础上，对数据点进行坐标轴平移，进一步精简数据，为二次压缩做准备．具体步骤如下：

（1）分别比较剩下数据点的横坐标和纵坐标，得到横、纵坐标的最小值为Xmin、Ymin；

（2）以Xmin作为在x轴方向的平移距离，Ymin作为在y轴方向的平移距离，并以点（Xmin，Ymin）作为坐标原点，建立新的坐标系；

（3）计算剩下数据点平移至新坐标系后的新坐标，在该线状数据中新建2个double型参数，分别记录偏移量Xmin和Ymin用于解压缩，double型参数为双精度浮点型参数．

1．3 数据类型转换

double类型采用64位内存空间存储数据，而坐标轴平移之后，数据点的坐标值位数减少，有效位数通常在9位以内，存储空间有较大浪费．作为替代，采用32位存储空间的unsigned int32类型（以下简称int32型）存储数据点坐标，可以实现存储空间的二次压缩，且精度损失不大．

在1．2节得到的平移后的线状数据基础上，首先对各数据点的新坐标值进行放大处理：比较各数据点平移后的新横坐标值X和新纵坐标值Y，得到横纵坐标的最大值Xmax和Ymax，将Xmax乘以10m，补足其为9位数，再将其他数据点的新横坐标值X乘以10m，同理将Ymax乘以10n，补足其为9位数，再将其他数据点的新纵坐标值Y乘以10n；在该线状数据中新建2个int32型参数，分别记录放大量m和n用于解压缩，其中m和n均为正整数，int32型参数为32位整数型参数．

将放大后的线状数据点的坐标类型由double型强制转换为int32型，以减少数据点坐标记录所占用的存储空间．最后将int32型数据点集合，以及上述步骤的偏移量Xmin和Ymin、放大量m和n合并记录为压缩后的矢量地图数据．

2 数据压缩测试

2．1 样本数据选取

为了验证所设计的压缩方法的可行性，选取某县市行政区图形作为样本数据进行压缩测试，其空间数据占52．8MB，对应样本数据中的．shp文件．

数据绘制示例如图4所示，从中可以看出，部分数据存在明显冗余．因图4右下角多边形数据量较大，为便于测试，本文将以该图形为例，详细介绍压缩测试过程．该图形由96个数据点构成，每个数据点double精度的（x，y）存储坐标值，始点P1坐标为（636 037．847 235，3 313 442．795 090），终点P96坐标为（636 037．843 345，3 313 442．789 755）．

图4　样本数据绘制示例Fig．4 Examples of sample data plotting

2．2 压缩测试

2．2．1 Douglas－Peucker方法初次压缩

采用Douglas－Peucker方法对矢量数据进行压缩，首先要确定限差dmax的值，其实这也是图形压缩率的一个体现．限差越大，表明允许的误差越大，图形的失真度就越高．本文选取了0．5，1，1．5，2四种不同的限差，分别对样本数据进行压缩测试，结果如图5所示，顶点数分别为原始图形的29．2%，24．0%，20．8%，19．8%．可见压缩过程对于减少原始数据点的数量效果明显．随着限差的不断增大，图形逐渐失真，特别是多边形拐角处．为尽可能保留数据信息，本研究选用的冗余点限差为0．5，对原始数据文件进行压缩，压缩后文件大小为31．3MB，压缩率为40．7%．

2．2．2 坐标轴平移

在初次压缩得到的精简的线状数据基础上，对剩余数据点进行坐标轴平移：

（1）分别比较剩余28个数据点的横坐标和纵坐标，得到横坐标最小值Xmin为635 889．373 510，纵坐标最小值Ymin为3 313 138．687 620；

（2）以635 889．373 510作为x轴方向的平移距离，3 313 138．687 620作为y轴方向的平移距离，并以点（635 889．373 510，3 313 138．687 620）为原点，建立新的坐标轴；

（3）依次计算28个数据点在新坐标轴中的坐标值，记录其新坐标值数据为data X1（double［］）和dataY1（double［］）．

图5　4种限差的压缩效果Fig．5 Compression effects of four kinds of limits

2．2．3 二次压缩

首先，在平移后的线状数据基础上，对各数据点的坐标值进行放大处理：

（1）比较各数据点平移后的横坐标和纵坐标值，得横坐标的最大值Xmax为205．900 290，纵坐标的最大值Ymax为304．107 470；

（2）对横坐标的最大值205．900 290以及纵坐标的最大值304．107 470乘以106补足其为9位数，则放大量m与n为6；

（3）对平移后的各数据点的横坐标和纵坐标值分别乘以106，记录放大后28个数据点的横坐标和纵坐标值分别为data X2（double［］）和dataY2 （double［］）．

其次，将放大后的线状数据点的横坐标data X2 （double［］）和纵坐标值dataY2（double［］）由double型强制转换为int32型dataFX（int32［］）和dataFY （int32［］），从而减少数据占用的存储空间．

最后，将偏移量635 889．373 510以及3 313 138．687 620，放大量6和6，以及最终得到的int32型数据点集合，合并记录到压缩后的矢量地图数据文件中，从而实现对矢量地图数据的压缩．

对初次压缩后的数据文件进行二次压缩，压缩后文件大小为16．0MB，综合压缩率达到了69．7%，压缩效果明显．

2．3 结果分析

为了比较解压缩后图像的失真情况，对解压缩后的图形和原始图形进行叠加分析．如图6所示，蓝色为原始图形，红色为解压缩后的图形．可以看出图形发生错位的地方非常有限，在移动终端屏幕尺寸小、分辨率有限的情况下，已能满足移动用户的需求．

图6　解压缩后的图形与原始图形叠加分析Fig．6 Overlay analysis of the original and decompressed graphics

利用本压缩方法，分别对大小为34．7，79．5，49．8MB的线（面）状数据文件进行压缩测试，综合压缩率分别达到了63．8%，72．1%，66．9%，平均压缩率接近70%．

本方法在实现较高压缩率的同时，在实际使用过程中还有一些需要完善的地方，分析如下：

（1）Douglas－Peucker方法剔除了冗余点的限差dmax，其取值应考虑移动用户实际需求的动态比例尺大小，比例尺越大，dmax取值应越小，二者的对应关系尚需深入研究；

（2）在服务器中预生成各常用限差值dmax的金字塔级缓存数据，当位置服务请求地图数据时，可结合移动用户实际需求的比例尺来调用，提高服务效率；

（3）由于int32类型存储值最大为4 294 967 295，因此坐标值最大只能放大为9位数．对于坐标值跨度较大的图斑，如太湖边界，数据类型转换后小数位数据将舍弃较多，精度损失较大；

（4）对于精度要求较高的图层，如国境线，不宜采用本方法．

3 结 论

针对移动用户对地图数据压缩率要求高、失真率容忍度高的特点，设计了一种面向移动用户的矢量地图数据压缩方法．首先利用矢量数据压缩方法有效去除了冗余数据点，获得精简的线状数据，在此基础上对精简后的线状数据进行坐标平移，并放大各数据点的坐标值，进而强制将各数据点的数据类型由double型转换为int32型，实现二次压缩．本方法充分考虑移动用户的需求特点，在移动用户可接受的精度范围内，最大限度地提高了矢量地图数据压缩率，有效减少了无线网络在数据传输时的负荷，节约了移动终端存储空间．

参考文献（References）：

［1］ 李德仁，李清泉，谢智颖，等．论空间信息与移动通信的集成应用［J］．武汉大学学报：信息科学版，2002，27 （1）：l－6．LI Deren，LI Qingquan，XIE Zhiying，et al．The technique integration of the spatial information and mobile communication［J］．Geomatics and Information Science of Wuhan University，2002，27（1）：1－6．

［2］ 成建国，任福．移动环境中空间信息服务模式研究［J］．地理信息世界，2006，6（3）：57－60．CHENG Jianguo，REN Fu．Geographic information service model in mobile context［J］．Geomatics World， 2006，6（3）：57－60．

［3］ 张海堂，张永生，罗睿，等．移动GIS中点要素信息自适应服务技术研究［J］．计算机辅助设计与图形学学报，2005，17（6）：1167－1172．ZHANG Haitang，ZHANG Yongsheng，LUO Rui，et al．Adaptive service of point features in mobile GIS［J］．Journal of Computer Aided Design ＆Computer Graphics，2005，17（6）：1167－1172．

［4］ 陈飞翔．移动空间信息服务关键技术研究［D］．北京：中国科学院遥感应用研究所，2006．CHEN Feixiang．Research on Key Technologies for Mobile Spatial Information Services［D］．Beijing：Institute of Remote Sensing Applications，CAS，2006．

［5］ 黄培之．具有预测功能的曲线矢量数据压缩方法［J］．测绘学报，1995，24（4）：316－320．HUANG Peizhi．Vector data compression with prediction function［J］．Acta Geodaetica et Cartographica Sinica，1995，24（4）：316－320．

［6］ RAMER U．An iterative procedure for the polygonal approximation of plane closed curves［J］．Computer Graphics and Image Processing，1972，1（3）：244－256．

［7］ PAVLIDIS T，HOROWITZ S L．Segmentation of plane curve［J］．IEEE Trans Computers，1974，23：860－870．

［8］ 杨得志，王杰臣，闾国年．矢量数据压缩的Douglas－Peucker算法的实现与改进［J］．测绘通报，2002（7）：18－19，22．YANG Dezhi，WANG Jiechen，LYU Guonian．Study of realization method and improvement of Douglas－Peucher algorithm of vector data compressing［J］．Bulletin of Surveying and Mapping，2002（7）：18－19，22．

［9］ 刘晓红，李树军．矢量数据压缩的角度分段道格拉斯算法研究［J］．四川测绘，2005，28（2）：51－52．LIU Xiaohong，LI Shujun．Study on subsection Douglas algorithm with the goniometry in generalization［J］．Surveying and Mapping of Sichuan，2005，28（2）：51－52．

［10］ 王玉海，朱长青．多进制小波在矢量地图数据压缩中的应用［J］．测绘科学，2003，28（3）：66－68．WANG Yuhai，ZHU Changqing．The vector relief data compression based on the multi－band wavelet［J］．Science of Surveying and Mapping，2003，28（3）：66－68．

［11］ 尹路，周初阳．基于Douglas－Peucker的矢量数据压缩算法［J］．科技创新导报，2014，14：248．YIN Lu，ZHOU Chuyang．Vector data compression algorithm based on Douglas－Peucker［J］．Science and Technology Innovation Herald，2014，14：248．

［12］ 李帅，方源敏，喜文飞．基于无拓扑矢量曲线的快速压缩算法［J］．科学技术与工程，2011，11（18）：4324－4327．

［13］ 谭国律，唐金秀．矢量数据的优化压缩研究［J］．测绘通报，2010（4）：46－48，51．TAN Guolyu，TANG Jinxiu．The study for optimized compression of vector data［J］．Bulletin of Surveying and Mapping，2010（4）：46－48，51．

［14］ 余先川，张君兰，张立保．基于整数小波变换的空间矢量数据压缩方法［J］．中国地质大学学报，2011，36 （2）：381－385．YU Xianchuan，ZHANG Junlan，ZHANG Libao．Spatial vector data compression method based on integer wavelet transform［J］．Journal of China University of Geosciences，2011，36（2）：381－385．

［15］ 李青元，刘晓东，曹代勇．WebGIS矢量空间数据压缩方法探讨［J］．中国图象图形学报，2001（12）：1225－1229．LI Qingyuan，LIU Xiaodong，CAO Daiyong．Research in Web GIS vector spatial data compression methods［J］．Journal of Image and Graphics，2001（12）：1225－1229．

［16］ 赵艳伟，程振林，董慧，等．WebGIS多层次矢量数据压缩方法及仿真实现［J］．系统仿真学报，2012，24（6）：1259－1264．ZHAO Yanwei，CHENG Zhenlin，DONG Hui，et al．Method of multilevel vector data compression for Web GIS［J］．Journal of System Simulation，2012，24（6）：1259－1264．

［17］ 柯敏毅，王国治．移动GIS中的空间矢量数据压缩方法［J］．地理空间信息，2007，5（1）：24－26．KE Minyi，WANG Guozhi．Vector data compression of mobile GIS［J］．Geospatial Information，2007，5（1）：24－26．

［18］ 秦斌．移动GIS中矢量数据压缩及传输问题研究［D］．昆明：昆明理工大学，2010．QIN Bin．Research on Vector Data Compression and Transmission in Mobile GIS［D］．Kunming：Kunming University of Science and Technology，2010．

［19］ 陈涛，翟京生，陈双军，等．嵌入式GIS中基于LOD的地图数据组织模型设计［J］．测绘科学技术学报，2011，28（5）：374－377．CHEN Tao，ZHAI Jingsheng，CHEN Shuangjun，et al．Design of map data model based on LOD in embedded GIS［J］．Journal of Geomatics Science and Technology，2011，28（5）：374－377．

Vector data compression method for mobile users

CHEN Zhirong1，YIN Tianhe1，XU Caijiang2，ZHOU Feng1（1．College of Science，Ningbo University of Technology，Ningbo 315016，Zhejiang Province，China；2．Ningbo Municipal Information Center of Land and Resources，Ningbo 315040，Zhejiang Province，China）

Journal of Zhejiang University（Science Edition），2016，43（1）：045－050

Abstract：With the popularization of fourth generation（4G）mobile communication technology and the four／eightcore mobile phones，the data transmission capacity on the wireless network and the performance of mobile terminal are substantially improved．Mobile users are widely involved in making geographic information acquisition，upload and download．However，the requirements of data transmission will reach an unprecedented level，and are incompatible with the limited bandwidth．To meet with the new requirements of the higher compression rate and precision tolerance for spatial data，a vector data compression method is designed independently．Removing redundant points，parallel moving coordinate axis and data type conversion are used as three steps in the method to realize double compression．The tests reveal that the comprehensive compression rate of this method is close to 70%．It has effectively reduced the data transmission pressure in the wireless network，and has saved the memory space of mobile terminal．

Key Words：data compression；mobile user；vector map data；location－based service

作者简介：陈志荣（1981－），女，博士，副教授，主要从事移动地理信息系统理论与应用研究，E－mail：chenzr29＠foxmail．com．

基金项目：国家自然科学基金资助项目（40901241，Q15D010011）；浙江省自然科学基金资助项目（Y5090377，Q15D010011）；浙江省科技厅／公益技术应用研究项目（2014C31076）．

收稿日期：2014－12－20．

DOI：10．3785／j．issn．1008－9497．2016．01．008

中图分类号：P 208

文献标志码：A

文章编号：1008－9497（2016）01－045－06