矢量曲线

关键词： 仪器 观测 曲线 记录

矢量曲线（精选三篇）

矢量曲线 篇1

20世纪90年代以前, 受到技术条件和仪器测量手段的制约, 气象、水文、地质、地震、生物医学等多个领域的观测数据都是以记录曲线的形式记录在自记纸上, 有些观测仪器目前依然在使用。这些坐标图纸记录曲线详细记录了我国自然资源环境状况的诸多要素, 是研究我国自然资源及生态环境特征、能源和资源开发的宝贵资料。然而, 由于缺乏坐标图纸资料的数字化手段, 这些宝贵的数据一直没有得到充分的利用和开发。

21世纪是以电子计算机为主体的信息时代, 数字化技术和手段日新月异, 数字图像处理技术也日趋成熟, 使得坐标图纸记录曲线数字化成为可能。将自记纸扫描成数字图像保存到计算机, 然后通过图像处理和模式识别手段提取坐标图纸上自记曲线所表征的数据并保存, 是坐标图纸记录曲线数字化的主要手段。目前, 只有中国气象局率先组织技术人员开发了降水和风自记纸的数字化系统, 并取得了良好的效益[1,2]。

1解决的关键问题及研究现状

坐标图纸记录曲线智能识别并进行数字化处理需要解决的关键问题就是坐标图纸记录曲线的矢量化。由于有关坐标图纸记录曲线的矢量化方法研究很少, 因此, 只能借鉴图像处理和模式识别技术, 结合坐标图纸记录曲线的特点来实现。

图像中, 图形的矢量化算法通常有两种, 一种是基于细化算法, 即先分离扫描图像的图形图像和背景, 然后对所得图形图像作细化处理, 再跟踪单像素宽的细化图像, 得到图形的矢量描述。细化处理可以在保持图形拓扑结构不变的前提下得到图形的形态表示, 但是细化处理需要反复迭代, 工作量很大, 而且容易丢失图像中的有用信息, 造成图形的失真和畸变;另一种是非细化算法, 直接跟踪像素点来直接矢量化图形, 诸如正交方向搜索法[3]、块邻接图法[4]、轮廓匹配法[5]等。

由于坐标图纸记录曲线具有连续性和单调性的特点, 所以坐标图纸记录曲线的矢量化不同于图形图像的矢量化, 本文针对坐标图纸记录曲线的这一特点, 提出了一种基于灰度投影的分段线性插值算法对坐标图纸记录曲线进行矢量化, 此方法也可以应用于图形图像的矢量化方法研究中。

2基于灰度投影的分段线性插值算法的实现

2.1分段插值的概念[6]

坐标图纸记录曲线具有连续性和单调性的双重特征, 其实质就是一个自变量为x, 因变量为y的函数关系曲线y=f (x) , 只是由于此函数曲线的复杂性而无法写出其函数表达式。直接研究其函数的数学表达式非常困难, 如果设法将所考察的函数f (x) 简单化, 也就是构造某个简单函数p (x) 作为f (x) 的近似, 然后通过处理p (x) 获得关于f (x) 的结果。如果要求近似函数p (x) 取给定的离散数据, 则近似函数p (x) 称之为f (x) 的插值函数。

选用不同类型的插值函数, 与原函数逼近的效果就不同。如果使用代数插值, 会使插值多项式的次数随着节点个数的增加而升高, 同时高次插值与原函数的逼近效果也会受到影响, 这就是所谓的龙格现象。

另一方面, 如果缩小插值的范围, 也就是在被插值函数的某个局部运用低次插值, 插值函数与被插值曲线逼近效果较好。对于一个被插值函数f (x) , 如果在X轴上将其分为若干个子段, 对每个子段上运用线性插值, 用联结相邻节点的折线来逼近所考查的曲线, 就能保证一定的逼近效果。这种化整为零的处理方法称为分段插值法。

分段插值方法的处理过程分为两步, 先将所考查的区间[a, b]作一划分:

Δ:a=x0<x1<…<xn=b

并在每个子段[xi, xi+1]上构造插值多项式, 然后将每个子段上的插值多项式拼接在一起, 作为整个区间[a, b]上的插值函数。这样构造出的插值函数是分段多项式。如果函数Sk (x) 在划分Δ的每个子段[xi, xi+1]上都是k次式, 则称Sk (x) 为具有划分Δ的分段k次式。点xi (i=0, 1, …, n) 称为Sk (x) 的节点。所以, 分段插值就是选取分段多项式作为插值函数。

假设在划分Δ的每个节点xi上给出了数据yi, 或者说, 设已给出了一组数据点 (xi, yi) , i=0, 1, …, n, 联结相邻两点得一折线, 那么, 该折线函数可以看作下述问题的解:

求作具有划分Δ的分段一次式S1 (x) , 使成立S1 (xi) = yi, i=0, 1, …, n, 由于在每个子段[xi, xi+1]上, S1 (x) 都是一次式, 且成立S1 (xi) =yi, S1 (xi+1) =yi+1, 故:

$S{}_1(x)=\phi {}_0(\frac{x-x{}_i}{h{}_i})y{}_i+\phi {}_1(\frac{x-x{}_i}{h{}_i})y{}_{i+1}x{}_i\le x\le x{}_{i+1}$ (1)

式中, hi=xi+1-xi, 而 φ0 (x) =1-x, φ1 (x) =x。

对于取值f (xi) =yi (i=0, 1, …, n) 的被插值函数f (x) , 在子段[xi, xi+1]上有其估计误差为:

$\left|f(x)-S{}_1(x)\right|\le \frac{h{}_i^2}{8}\underset{x{}_i\le x\le x{}_{i+1}}{{\displaystyle \max }}\left|f{}^{″}(x)\right|$ (2)

由此可以看出, 当hi足够小时, S1 (x) 在[a, b]上一致收敛到f (x) 。

2.2插值节点的选取

从上述分段插值函数的概念可知, 插值节点必须是被插值函数上的点, 而且插值节点越密集, 插值函数与被插值函数就越近似。因此, 插值节点的选取必须既准确又密集。但是, 通过大量实验分析, 如果插值子段的步长太小, 会使曲线的搜索容易受到噪声的干扰出现偏差, 这是由于只通过像素点搜索使得搜索程序只关注了曲线的微观部分而忽略了曲线的宏观变化所导致的。所以, 对插值节点的密度选取, 既要保证插值函数拟合曲线不失真, 又要使曲线的插值节点的搜索足够准确, 以下详细介绍插值节点的跟踪算法。

2.2.1 插值子段步长的选取

子段的划分可以通过信号的采样规则来解决, 传统的采样方式都基于采样定理:一个频谱受限的信号y (t) , 如果频谱中集中在 (-fs - fs) 的范围内, 信号y (t) 可以用等间隔的抽样值来唯一的表示, 而最低抽样频率为2fs。这是因为一个频带受限的信号不可能在很短的时间内产生独立的、实质的变化。它的最高变化速度受最高频率分量的限制。采样定理保证了最高频率分量的全部信息。采样定律用公式表示为:

fs≥2f 或 Ts≤T/2

其中f为被采样信号的最高频率。

2.2.2 插值节点的选定与曲线重构

为了能够从宏观上把握坐标曲线的运动轨迹, 减少噪声对曲线搜索的干扰, 本文提出了基于灰度投影的分段搜索法来跟踪坐标曲线并获得插值节点。步骤如下:

Step1 按照一定步长对坐标记录曲线进行分段水平积分投影:

$p(y)={\displaystyle \sum _{i=1}^{{\rm N}}f}(x,y)y=1,2,\cdots ,{\rm M}$ (3)

Step2 根据曲线的宽度确定P (y) 是否存在非空图像的投影, 并确定非空图像投影的Y值坐标。

Step3 根据非空图像投影的位置及其长度确定非空图像投影是否是曲线的。如图1 所示, 左侧图像为原始曲线, 右侧图像为各个分段在水平方向的图像投影。其中, [X0 , X1 ]区间段内存在曲线和污迹的两种非空图像, 有以下几个原则来判别非空图像的投影是否是曲线的:

1) 单调性 由于曲线是连续的, 可以通过右图中投影线段之间的递增或递减单调性来确定曲线的投影。

2) 距离最近原则 每相邻的两个投影段之间的距离都是可以衔接在一起的。

3) 导数值接近原则 由曲线上某一点的导数定义可知, 每一投影段除以步长接近于该时间段的导数值, 如果曲线连续且可导, 每相邻两点的导数值的变化总是很接近。

Step4 以各段的曲线投影来选定插值节点。如图2所示, 将灰度积分投影法求得的纵坐标区域作为一个矩形的竖边, 将沿时间轴X对曲线分段的步长作为横边, 就可以得到若干个按照时间段划分的矩形区域, 这些矩形区域内的一条对角线附近包含了每一时间段内的自记曲线的像素点的集合。为了使线性插值函数与自记曲线有较好的逼近效果, 必须使插值函数位于自记曲线的中轴位置。从图中可以看到, 如果将每一个矩形块的对角线左右两个端点分别编号为Li (x, y) 、Ri (x, y) , i=0, 1, …, n, 则从第1个矩形块开始到第n-1个矩形块, 将第Ri (x, y) 个节点与第Li+1 (x, y) 个节点合并, 合并后的节点的x的值不变, y的值是被合并的两个节点y值的中间值。将最终得到的n-1个节点作为分段线性插值节点。

Step5 增加插值节点。为了减少对曲线拟合带来的失真, 可以再次增加插值节点, 在投影区域较长的时间段内, 以步长的一半再次投影, 再次以Step3、Step4处理, 就能再增加一倍的插值点。

Step6 曲线的细化重构。经过以上步骤的处理, 获得了若干个分段线性插值点, 进行相关的平滑处理后, 将这些点的坐标值代入式 (1) , 就获得了曲线的分段线性插值函数S1 (x) 。

Step7 量化处理。按照横、纵坐标的物理意义, 提取曲线所表征的数据。

3结束语

本文介绍的基于灰度投影的分段线形插值算法是一种用于坐标图纸记录曲线矢量化的处理方法, 该方法的特点在于从曲线的宏观特征入手, 由粗到细、由浅入深, 逐步得到曲线的拟合函数, 其优点在于从宏观上搜索曲线有助于减小噪声对曲线搜索的影响, 提高了曲线拟合细化的准确率。该方法已经应用于气象行业风自记记录的数字化应用中, 并取得了良好的效果。而且该方法也可应用于其他领域的纸质观测记录数字化工作中。

参考文献

[1]王伯民, 吕勇平, 张强.降水自记纸彩色扫描数字化处理系统[J].北京:应用气象学报, 2004 (6) :737-744.

[2]屈志毅.电接风向风速自记纸数字化处理系统的设计与实现[J].北京:应用气象学报, 2008, 19 (2) :227-232.

[3]Dori D, Liang Y, Dowell J, et al.Sparse-piexl recognition of primitivesin engineering drawings.Machine vision and Applications, 1993 (6) :69-82.

[4]Pavlidis T.A Vectorizer and Feature Extractor for Document Recogni-tion.Computer Vision, Graphics and Image processing, 1986, 35:111-127.

[5]Han C C, Fan K C.Skeledon Generation of Engineering Drawings viaContour Marching.Pattern Recognition, 1994, 27 (2) :261-275.

[6]王能超.数值分析简明教程[M].北京:高等教育出版社, 1984:47-51.

[7]朗锐.数字图像处理学.北京:希望电子出版社, 2003:128-161.

矢量曲线 篇2

关键词:数据简化矢量曲线 多波束测深

中图分类号:TB565文献标识码:A文章编号:1674-098X(2011)05(c)-0079-02

1 簡介

多波束测深仪具有几百到上千个波束,一次扇区(ping)扫描能获得成百上千个测深数据,可对水下地形地貌进行大范围、全覆盖的测量,极大地提高了测量的精度和效率,现已广泛应用于河道测量、港湾测量、浅海测量、深海测量等领域[1]。如此巨大的数据在实际应用中,存在很大的冗余性,也为数据的后处理和存储带来庞大负担[3]。因此,在进行数据存储、应用前,有必要在保持测区地形特征的前提下,对数据进行一定的精简。

2 基于ping的简化方法

2.1 ping数据抽取

多波束测深数据是沿测线逐ping记录和存储的部分有序、均匀分布数据,因此其数据后处理可以ping为单位进行。每ping中的数据邻点相连,就形成了一条三维曲线段,然后采用基于矢量曲线的简化方法进行简化处理。

ping数据的抽取方法有两种:(1)曲率判定法,根据当前点与前后数据点在x,y平面上相连接的直线曲率差值来确定;(2)距离确定法,通过计算当前点与前一点的平面距离来确定。

2.2 常用的矢量简化方法

常用的曲线简化方法有以下几种:步长法、线段过滤法、垂距限值法、道格拉斯-普克法(Douglas-Peucker,简称DP)等等[4]。在实际的数据简化应用中,使用较为广泛的是垂距限值法和道格拉斯-普克法。

2.2.1 垂距限值法

从第一点开始逐点筛选特征点。首先以第一点为起点,计算第二点到第一、第三点所构直线的距离,若大于某一阈值,则保留第二点,并以该点作为新起点,计算第三点到第二、第四点所构直线的距离;否则,去掉第二点,仍以第一点为起点,计算第三点到第一、第四点所构直线的距离。依此类推,直至曲线上最后一点。该方法的阈值一般取相应地物最大允许误差或更小。

垂距限值法简化结果具有较好的精度、算法简单、易于编程和计算机处理,所以在曲线简化中应用较广。缺点是它没有考虑到曲线各点的斜率,即不能完全保证特征点不被删减。

2.2.2 道格拉斯-普克法

DP算法是一次对整条曲线段进行考虑。首先连接曲线段两端点,计算线段内各点(称中间点)到两端点所构直线的距离。若最大距离值小于某一阈值,则保留两端点,舍去所有中间点;若大于阈值,则保留对应中间点,并以此点将线段分为前后两段,再分别对这两段重复上述过程,直到没有点需要被舍去为止。

DP法在简化精度方面较垂距限值法有显著的提高。但由于DP算法中用到了较多的循环和递归,在编程的难易程度和计算机处理速度方面逊于垂距限值法。

2.3 简化性能评价

数据简化算法的效果可以从三个方面来度量[5]:(1)精度,即利用简化后数据重构的曲面与由原始数据所构曲面之间的误差;(2)简度,也称简化率,即简化前后数据点个数的比值;(3)速度,即计算机进行简化处理的时间。实际上,任何一种简化算法要想同时在以上三个方面都具有优秀的表现是很困难的,很多算法只能达到其中一个或两个要求,对于海量的多波束测深数据来说更是如此。

3 简化实例

对某实测多波束测深数据分别采用垂距限值法和DP法进行简化处理(原始测深数据见图1),垂距限值均选取0.05m。精度评定采用反距离平方加权内插法。两种方法简化效果见图2、图3、图4、图5(图中五角星标定点为简化后保留点),简化性能情况见表1。

由图2、图3、图4、图5及表1可见,经过简化后的数据均较好地保留了原始数据的地形特征点,且数据量得到了较大地减少。从精度上讲,两种算法的简化精度均远小于0.1m,满足《水道观测规范》要求;从简度上看,两种方法在满足精度要求的前提下,都达到了50%以上的简化率,大大地减小了原始数据量;从速度上比较,垂距限值法比DP法快,这是由于DP法的迭代循环增加了处理时间。

4 结语

从文中实例应用分析可得,虽然垂距限值法和DP法在矢量曲线数据简化中均具有较好的简化效果,但因为DP法在编程中采用迭代计算,增加了编程的难度及数据处理时间,因此,综合算法的精度、简度、速度及算法实现难易度,垂距限值法在海量多波束测深数据的简化处理中更具适用性。

参考文献

[1]郑庆涛.多波束与单频测深技术应用比较[J].水利水文自动化,2007,(1):25～29.

[2]Kammerer E.Charlot D.,Guillaudeux S.Michaux P.Comparative study of shallow water multibeam imagery for cleaning bathymetry sounding errors[C].Oceans Conference Record (IEEE), v4,2001:2124～2128.

[3]周绿,林亨,钟约先,等．曲面重构中测量点云的精简方法的研究[J]．中国制造业信息化,2004,33(5):102～104．

[4]刘彦花,叶国华.矢量曲线抽稀算法分析[J].城市勘测,2001,(4):1～4.

矢量曲线 篇3

对矢量化后的地形图等进行压缩处理的过程称之为空间矢量数据的压缩。地图数字化中矢量数据的压缩主要包括各种地形图要素的数据压缩。等高线是地图中最多的图形要素, 所以对矢量化后的地图的数据压缩主要是对曲线的压缩, 目前讨论最多的也是曲线矢量数据的压缩。在此针对矢量数据的压缩问题进行研究。传统的矢量数据压缩方法的核心思想是从矢量数据的坐标点集中运用一定的算法抽取出最能体现矢量数据特征的子集。这类曲线矢量数据压缩算法主要有:垂距限值法、角度限值法、Douglas-Peucker算法 (Splitnig算法) , 以及黄培之提出的具有预测功能的曲线矢量数据压缩方法等[1,2,3]。近年来, 矢量数据的量化编码压缩算法的研究得到重视。钟尚平等[4]根据平面矢量地图文件的存储特性, 有机结合“无附加码书”字典编码方法, 可逆并显著地压缩了矢量地图。王立胜等[5]基于第二代小波变换理论实现了对空间矢量数据的无损压缩。黄越峰等提出了使用基于整数小波变换和FFEP编码的曲线数据压缩方法[6]。Kolesnikov等提出了链码方法用于矢量数据压缩[7]。本文首次提出结合实际矢量数据文件的存储结构和曲线矢量数据的特性, 将浮点型的矢量数据坐标值预处理成整型值表示的坐标值之间的偏移量。进而引入先进的整数小波变换对整型的偏移量序列进一步处理, 分析变换后的小波系数的幅值, 分布等特征后, 采用了高效的基于模糊c均值聚类和字典法编码方案进行压缩存储。实验结果表明, 本文的压缩方法能够达到较高的无损压缩比。

1 矢量数据的整型化

矢量数据文件一般包括表示数据属性和存储结构的元信息和实际图形的坐标点序列, 其中浮点型坐标点序列占据了文件的绝大部分存储空间。对矢量数据文件进行压缩主要是对坐标点序列进行压缩。

对于二维的平面矢量数据, 坐标点序列由x坐标序列和y坐标序列组成。由于使用浮点型表示, 每个坐标值占用的存储空间为8个字节。本文使用的是基于整数小波变换的压缩方法, 因此首先是将坐标点序列用整型数表示。

由于同一曲线和多边形实体的坐标点序列是密集的和顺序的, 因此相邻点间的坐标值之差的变化范围很小, 可以用整型数来表示。对于由N个点序列 ([Xn, Yn], n=0, 1, 2, …, N-1) 表示的曲线或多边形实体, 坐标值整型化为 ([X′n, Y′n]n=0, 1, 2…N-1) 过程如下:

步骤1: 记录X0, Y0, 令X0 ′ = 0, Y0 ′ = 0。

步骤2: 对于n=1, 2, …, N-1, X′n=Xn-Xn-1Y′n=Yn-Yn-1。

步骤3: 已知Xn的最高精度为10-p, Yn的最高精度为10-q, 则X′n=X′n×10p, Y′n=Y′n×10q。

2 整数小波变换及其在矢量数据压缩中的应用

2.1 整数小波变换

传统的小波变换又称为第一代小波变换, 其变换过程主要是利用小波滤波器组对图像行列分别滤波, 进行卷积运算, 由于都是实数域的变换, 即使待分析信号本身是整数序列, 相应小波变换系数也是实数。由于数字图像一般都是用整数表示, 非常希望有一种“整数-整数小波变换”, 将整数序列映射为整数小波系数, 并且这种映射是可逆的, 具有这种性质的小波变换称为整数小波变换 (IWT) 。Sweldens等提出的提升 (lifting) 小波变换方法是一种新的小波变换工具, 利用它可以不采用傅里叶变换作为主要分析工具, 能够很容易地构造一般的整数小波变换[8]。

2.2 整数小波变换在曲线矢量数据压缩中的应用

整数小波变换可以将数据的绝大部分能量压缩到低频系数中, 只有少部分在高频系数中。利用整数小波变换的这个特性可以实现数据的压缩。近年来基于整数小波变换的图像压缩已经成为一个研究热点[9]。

为了直观说明整数小波系数分布的特点, 本文对国家铁路线曲线矢量数据 (SHP格式) 使用第1节中的整型化处理后, 进行了两层整数小波变换分解, 并对小波系数进行统计分析如图1所示。

经过对图2的数据点分布图和图3的整数小波系数分布图进行对比, 可以发现数据点经整数小波变换后得到的小波系数在空间分布上聚集性更强, 大量的幅值分布在零附近, 达到了去相关的目的, 适合于采用高效的编码压缩方法。

3 基于整数小波变换 (IWT) 和模糊k-均值聚类的编码压缩方案

3.1 压缩流程

使用IWT变换压缩曲线矢量数据的原理是通过IWT变换将空间域的坐标串变换为频率域的小波系数序列, 对系数序列进行量化和编码获得压缩数据流。在使用IWT变换前, 将同一条曲线或者多边形实体的矢量数据组成一个待压缩子块。对每个块中的x和y坐标序列使用第一节中整型化方法转化成整型的偏移量序列。对得到的整型偏移 量序列进行整数小波变换, 得到小波系数序列。对小波系数进行编码, 得到压缩后的矢量数据。压缩流程如图4所示。

3.2 整数小波系数编码

由2.2节的统计分析可知, 曲线矢量数据经过整型化和整数小波变换处理后得到的整数小波系数在空间分布上非常集中, 大量的幅值集中在零附近。本文针对这个特点, 提出使用改进的一维模糊c-均值聚类算法对整数小波系数进行聚类, 建立系数字典, 将整数小波系数转换为其所属类均值对应的字典索引, 从而实现快速高效的编码。

3.2.1 模糊c-均值聚类 (FCM)

设{xi, i=1, 2, …, n}是n个样本组成的样本集合, 预定类别数目c, mi, i=1, 2, …, c为每个聚类的中心, μj (xi) 是第i个样本对于第j类的隶属度函数。用隶属度函数定义聚类损失函数Lμ:

$L{}_{\mu }={\displaystyle \sum _{j=1}^c{\displaystyle \sum _{i=1}^n[}}\mu {}_j(x{}_i)]{}^{b}d{}_i{}_j^2(1)$

式中:$d{}_i{}_j=|x{}_i-m{}_j|$为第i个样本与第j个聚类中心间的欧几里得距离;b∈ (1, ∞) 是可以控制聚类结果模糊程度的常数。

模糊c-均值方法[10]要求每个样本对于各个聚类的隶属度之和为1。即要满足:

${\displaystyle \sum _{j=1}^c\mu }{}_j(x{}_i)=1,i=1,2,\cdots ,n(2)$

使用拉格朗日乘数法进行推导, 可以得到使式 (1) 取极小值的必要条件:

$\begin{array}{l}m{}_j={\displaystyle \sum _{i=1}^n[}\mu {}_j(x{}_i)]{}^{b}x{}_i/{\displaystyle \sum _{i=1}^n[}\mu {}_j(x{}_i)]{}^b(3)\\ \mu {}_j(x{}_i)=1/{\displaystyle \sum _{k=1}^c(}d{}_i{}_j/d{}_{ik}){}^{2/(b-1)}(4)\end{array}$

由上述2个必要条件, 模糊c-均值聚类算法是一个简单的迭代过程。算法步骤如下:

步骤1:设定聚类数目c和参数b。

步骤2:初始化各个聚类中心mi。

步骤3:根据式 (4) 计算隶属度函数。如果小于某个确定的阈值, 或相对上次隶属度函数值的改变量小于某个阈值, 算法停止。

步骤4:根据式 (3) 更新各类聚类中心。

3.2.2 使用FCM字典法对整数小波系数编码

分别取出x方向的部分小波系数和y方向的部分小波系数当做做样本集合, 使用3.2.1中的FCM算法分别得到x方向和y方向上的若干个聚类中心。由于整数小波系数是一维的, 因此使用的是计算速度和收敛速度都很快的一维形式的FCM。

建立由聚类中心和对应索引组成的字典。编码时, 将小波系数转换成其所属聚类中心对应的字典索引。字典索引的编码长度由聚类数目决定, 若聚类数目为2n, 则索引的编码长度为n位。

4 实 验

实验数据采用了国家基础地理信息中心下载的中国数字地理地图数据SHP文件, 包含中国国境线矢量数据, 中国境内铁路线、公路线、河流分布等矢量数据。采用本文的压缩编码方案和文献11中直接对曲线矢量数据进行聚类法压缩方式[11]进行压缩实验, 得到的实验结果如表1所示。

实验主要对比的性能指标:

(1) 压缩比。原始矢量数据大小与压缩编码后的数据量的比值。

(2) 均方误差 (mean square error, MSE) 和最大绝对误差 (maximum absolute error, MAE) 。假设原始数据由M个点组成, 每个点的值为Pi , 重建后的点为Pi′, 那么MSE和MAE定义为:

$\begin{array}{l}\text{Μ}\text{S}\text{E}=\frac{1}{{\rm M}}{\displaystyle \sum _{i=0}^{{\rm M}-1}(}{\rm P}{}_i-{\rm P}{}_{i^{\prime }}){}^2\\ \text{Μ}\text{A}\text{E}=\underset{0\le i\le {\rm M}-1}{{\displaystyle \max }}\{|x{}_i-x{}_{i^{\prime }}|,|y{}_i-y{}_{i^{\prime }}|\}\end{array}$

实验结果表明, 使用本文的算法相比直接使用矢量数据的聚类算法能够提高压缩比并且能够降低重建后的矢量数据的失真程度。

5 结 语

GIS地图数据中的曲线或多边形矢量数据, 其坐标相邻点间的坐标值之差的变化范围很小, 可以用整型数来表示, 并且坐标点序列内部存在很大的相关性。因此, 可以通过对浮点型的坐标点序列转换成整型偏移量序列, 再进行整数小波变换和采用合适的编码压缩方案进行此类矢量数据的压缩。实验结果表明, 使用本文的基于整数小波变换的曲线矢量数据压缩方案, 可以达到较高的压缩比和较小的失真。在实际GIS系统实时使用中, 对压缩解压缩的速度也有很高的要求, 如何在尽量不减少压缩比的前提下最大化的降低计算的时间消耗有待进一步的研究。

参考文献

[1]黄培之.具有预测功能的曲线矢量数据方法[J].测绘学报, 1995, 24 (4) :316-319.

[2]DOUGLAS D H, PEUCKER T K.Algorithms for the re-duction of the number of points required to represent a digi-tized line or its caricature[J].The Canadian Cartographer, 1973, 10:112-122.

[3]KOLESNIKOV A, AKIMOV A.Distortion-constrainedcompression of vector maps[C]//Proceedings of the 2007ACM Symposium on Applied computing.Seoul:ACM, 2007:8-12.

[4]钟尚平, 高庆狮.一类矢量地图的无损压缩算法[J].系统仿真学报, 2004, 10 (16) :2189-2194.

[5]王立胜, 闵晓瑜.一种面向移动用户的空间矢量数据压缩算法[J].自动化技术与应用, 2004, 12 (23) :20-22.

[6]黄越峰, 钟耳顺, 郭会.移动计算环境中曲线数据实时压缩方法[J].计算机辅助设计与图形学学报, 2009 (21) :88-93.

[7]AKIMOV A, KOLESNIKOV A, FRANTI P.Losslesscompression of map contours by context tree modeling ofchain codes[J].Pattern Recognition, 2007, 40 (3) :944-952.

[8]丁绪星.基于整数小波变换的图像编码研究与实现[D].南京:南京理工大学, 2004.

[9]余先川, 张立保, 朱童, 等.基于整数小波与提升框架的遥感图像压缩[J].光学学报:信息光学专刊, 2009, 29 (12) :221-224.

[10]BEZDEK J C, HATHAWAY R J, SABIN M J, et al.Convergence theory for fuzzy C-means:counter examplesand repairs[J].IEEE Tans.on Systems, Man and Cy-bern, 1987, 17 (5) :873-877.