时空数据有损压缩算法.docxVIP

一、背景时间、空间、属性是地理现象的三个基本特征，也是GIS数据库的三种基本数据组成。这里的“空间”是指空间的位置数据及其派生数据。“属性”指与空间位置无派生关系的专题属性数据。“时间”则指时间、空间和属性状态的时变信息。随着近年来以空间数据库为基础的GIS研究和应用的不断深入，随时间而变化的信息越来越受到人们的关注，因而提出了时态GIS（简称TGIS）的概念。时态GIS的组织核心是时空数据库，时空数据模型则是时空数据库的基础。关键字：GIS 有损压缩算法空间数据 Lossy CompressionAlgorithm二、介绍1、需求介绍时空数据库的数据主要来自于一类按照时间周期返回位置及属性数据的传感器，这类传感器通常会被安装在一些移动的个体上，比如车辆或者个人。通过传感器周期传回的位置及属性数据，系统可以完整的记录下个体的移动轨迹以及对应时间属性值（如速度、温度等）。当前的应用发展趋势表明，被监测个体的数目正在呈爆炸性的增长，同时随着技术的进步以及应用的需求，数据回传的周期也越来越短。例如，南京市的私家车保有量大约在100万台左右，如果后台系统想要实时的知道每台车的位置及属性信息，至少需要对每台车进行秒级采样，我们假设每次每台车上传的数据为50字节，其每天的数据增加将达到：4.02T=50byte/条*100万*24*60*60可以想见系统长时间的运行将占用非常庞大的磁盘空间，反之如果针对这些采集数据进行有效的压缩，而且压缩算法具备较高的压缩比，则能够节约大量的磁盘空间，极大的降低系统的建设成本。数据压缩分为有损和无损两大类。有损一般采用线性拟合的方法，而无损则通过各类近似霍夫曼编码的方法压缩数据。有损压缩的精髓主要是如何抽取特征点，以特征点的连线来近似地表示（拟合）原始数据曲线。题目要求实现一套针对单一个体按时序排列的位置数据的有损压缩算法，即将一条基于等间隔时间变化的三维曲线进行压缩，要求能够对这条曲线进行拟合还原，原始点与拟合点的欧式距离之差小于某一给定参数。2、定义、缩写词和符号时空数据struct Data{longlongtime;double x;double y;double z;};其中time代表位于移动个体的采集器上传数据的绝对时间，x，y，z分别代表该个体在当前时刻所在空间位置的三个坐标，因此同一采集器一组按时序排列的Data可以看作是一个个体在一段时间内的位移轨迹。采样率：采样率（也称为采样速度或者采样频率）定义了每秒从连续信号中提取并组成离散信号的采样个数，单位用赫兹（Hz）来表示。VS：Microsoft Visual Studio拟合直线的起点终点距离：如图例所示；三、功能需求根据提供的6000个等时间间隔时空数据，根据时序实现一套有损压缩算法（不能借助任何已有的专利算法），该算法可行性要求可被数学证明，另外该算法需具备极高的效率以及压缩比。若有损压缩阈值设置为x，则还原后的数据与元数据的欧氏距离差不能大于x，6000个事件的压缩应当在500毫秒内完成（不含读取6000个事件所需要的时间），压缩比至少达到6：1，即压缩后至多只保存1000个事件。数据拟合应当在500毫秒内完成（即将1000个事件还原为6000个事件），而拟合后每个拟合值与原始值的误差都必须在有损压缩设置的阈值范围0.1以内，拟合度越高越好。算法接口:压缩接口intcompress (Data data_in[], int count_in, Data data_out[], int count_out, double deadband);参数描述:data_in:需要压缩的数据,时空数据数组 count_in:数组的个数 data_out:压缩过后的数据 count_out:压缩后剩下的数据 deadband:压缩死区 intdecompress (Data data_in [], int count_in, Data data_out [], int count_out, int timeStep) 参数描述：data_in:需要还原的数组 count_in:数组的个数 data_out:还原后的结果 count_out:原数据个数 timeStep:时间的步进值 四、非功能性需求要求以图文结合的方式给出算法的论述与证明。五、运行以及编译环境1、运行环境英特尔?酷睿?2双核处理器E7500 (2.93GHz/1066FSB/3M 二级缓存，32bit OS)2、编译环境代码采用C++方式实现，要求在Windows7平台上Microsoft用Visual Studio 2008能够编译通过。验证方式：将源文件与测试用main.cpp文件放入vs2008项目中。 要求不做任何改动的情况下可以进行编译，链接，执行 判断依据：拟合还