-
随着网络地理信息系统的发展和数据获取能力的增强，在满足用户对空间信息的需求的同时，也对地理空间数据的高效存储和传输提出了更高的要求。数据压缩技术能够有效减少数据量、提高数据的存储和传输效率，是提高网络地理信息系统运行效率的有效手段。按照数据结构，地理空间数据压缩可分为矢量数据压缩和栅格数据压缩两大类，栅格数据压缩与图像压缩类似，已有成熟的图像压缩算法可直接利用[1-2]。
矢量地图中矢量数据占了绝大部分数据量，矢量数据中又以坐标数据为主。因此，坐标数据是矢量数据压缩考虑的重点。按照数据压缩原理，矢量数据的压缩可以分为空间域方法和频率域方法。常见的空间域矢量数据压缩方法有Douglas-Peucker算法[3]及其相对应的一系列改进算法[4-6]。在需要对大规模矢量数据实时简化和低压缩率的场合，基于空间域的矢量数据压缩方法存在计算复杂度较高的问题，而频率域算法相对空间域算法有压缩效率高的优势[7-9]。文献[10]结合小波变换并利用关键点修正局部失真过大的区域，提高了数据的压缩效率；文献[11]从空间曲线矢量数据相邻坐标点间坐标值的相关性出发，将整数小波变换用于矢量数据压缩，进一步提高了数据压缩效率；文献[12]验证了离散余弦变换(discrete cosine transform, DCT)用于矢量数据压缩的可行性和优越性；文献[13]将矢量数据划分为若干个大小不等的数据块进行DCT压缩，较好地保持了原始矢量数据所具有的地理形态结构特征；文献[14]和文献[15]利用近似DCT变换分别提出了不同数据块大小的图像压缩方法，与基于DCT的压缩方法相比，压缩效率提高约一倍。另外，已出现基于字典学习、压缩感知、神经网络等技术的图像压缩方法[16-18]。近似DCT变换属于频率域压缩算法，具有计算复杂度低、压缩效率高的特点，目前仍用于图像压缩领域，尚未出现用于矢量数据压缩的研究。
但是，基于频率域变换的压缩方法在量化取整的过程中会造成数据失真，部分较大失真会影响矢量数据的可用性。并且现有的基于频率域变换的矢量数据压缩方法并未充分考虑和利用矩阵变换的正交性，导致变换过程中计算量较大。
鉴于以上问题，本文提出了一种基于近似DCT变换和矩阵稀疏分解的频率域矢量数据压缩方法。一方面，利用近似DCT矩阵正交性和计算复杂度低的特点，改进基于DCT变换的压缩方法，结合矢量数据分层分类的组织方式，简化矩阵运算过程；另一方面，考虑压缩对数据造成的最大绝对误差，给出误差的处理方法。
-
对矢量数据进行分层分块，一方面便于进行近似DCT变换过程中的矩阵运算；另一方面，保持同一要素层集合对象的点序列之间的相关性。
一般地，矢量地图按图层分类组织。因此，可直接按照各要素层矢量数据顺序进行N×N分块。压缩率与分块大小N直接相关，N的增大可使得原始数据的能量集中于更少的系数，从而实现更低的压缩率，但同时也会使得计算量增大，算法时间效率下降[7-8]。为平衡压缩率和计算效率，并保证矢量数据精度，本文采取经典的8×8分块。
文献[8]结合矢量数据文件的存储结构和曲线矢量数据的特性，将浮点型的矢量数据坐标值预处理成整型值，用整数表示坐标值之间的偏移量，降低了数据运算量。本文在文献[8]的基础上，进一步结合矢量数据分层分类的结构特点，对矢量数据进行分块。本文设计的矢量数据分层分块方案如下：
1) 为保证矢量数据拓扑关系不被破坏，分图层对矢量数据进行压缩，以一个地图实体为处理单位(一条曲线或一个多边形)，从第一个点开始，依次记录下排序前后的次序映射号，以保存拓扑关系。
2) 针对矢量地图所包含的矢量数据和属性数据，规定矢量块划分从矢量地图的左下角开始，从左至右、从下到上依次进行。坐标值与其他信息分别进行编码。
3) 在压缩编码前，原始矢量数据的x、y坐标被分成8×8的数据块，再对每个块依次进行二维近似DCT变换。假如最后一个数据块的数量不足8×8个，分情况处理：如果剩余数据量不足32个，则保留第一个数据，计算其余数据与第一个数据的偏差，只保留第一个数据及其与剩余数据的偏差；如果剩余数据量大于32个，计算所有数据的平均值，并用平均值将数据量补充至8×8个。图 1为矢量数据分层分块方法。
图 1 矢量数据分层分块
Figure 1. Vector Data Slicing and Block
-
相对于DCT变换，近似DCT变换避开了矩阵运算中大量的乘法运算，其计算复杂度大大降低，近似DCT变换的转换矩阵形式为：
对角矩阵×低复杂度矩阵
对角矩阵通常包含无理数，如1/$\sqrt{m}$，m表示小正整数。原则上，对角矩阵的无理数会增加计算复杂度。但是，在近似DCT压缩过程中，对转换矩阵进行稀疏分解，使对角矩阵能够被分解后的稀疏矩阵吸收。
压缩过程中一个最重要的参数是变换域的保留系数。在一些压缩算法中，用于重构图像的保留系数数量非常少，文献[14]只考虑前8~16个系数，文献[15]使用10个DCT系数。在人脸识别应用中，文献[9]证明92×112个DCT系数中仅仅0.34%~24.26%是有效的。因此，本文取保留系数数量为10。
根据近似DCT的定义，文献[15]对由{0, ±1, ±2}组成的8×8正交矩阵空间进行搜索，寻找计算复杂度低的候选矩阵，并将搜索条件限制在使用乘法操作最少或者为零的矩阵。这样，搜索最低计算复杂度的过程就转化为最优化问题的求解：
$$ \mathit{\boldsymbol{T}} = \arg \mathop {\min }\limits_\mathit{\boldsymbol{T}} {\rm{cost}}\left( {\mathit{\boldsymbol{T}} * } \right) $$ (1) 式中，T是最优矩阵；cost(T*)是T*的算术复杂度，T*是T的伴随矩阵。另外，根据文献[15]中描述的近似DCT转换矩阵的特点，结合矢量数据8×8分块要求，本文在搜索过程中规定了以下约束条件：
1) 矩阵T的元素必须是{0, ±1, ±2}，以保证乘法复杂度为零。
2) 矩阵T的形式为：
$$ \mathit{\boldsymbol{T}} = \left[ {\begin{array}{*{20}{c}} {{a_3}}&{{a_3}}&{{a_3}}&{{a_3}}&{{a_3}}&{{a_3}}&{{a_3}}&{{a_3}}\\ {{a_0}}&{{a_2}}&{{a_4}}&{{a_6}}&{ - {a_6}}&{ - {a_4}}&{ - {a_2}}&{ - {a_0}}\\ {{a_1}}&{{a_5}}&{ - {a_5}}&{ - {a_1}}&{ - {a_1}}&{ - {a_5}}&{{a_5}}&{{a_1}}\\ {{a_2}}&{ - {a_6}}&{ - {a_0}}&{ - {a_4}}&{{a_4}}&{{a_0}}&{{a_6}}&{ - {a_2}}\\ {{a_3}}&{ - {a_3}}&{ - {a_3}}&{{a_3}}&{{a_3}}&{ - {a_3}}&{ - {a_3}}&{{a_3}}\\ {{a_4}}&{ - {a_0}}&{{a_6}}&{{a_2}}&{ - {a_2}}&{ - {a_6}}&{{a_0}}&{ - {a_4}}\\ {{a_5}}&{ - {a_1}}&{{a_1}}&{ - {a_5}}&{ - {a_5}}&{{a_1}}&{ - {a_1}}&{{a_5}}\\ {{a_6}}&{ - {a_4}}&{{a_2}}&{ - {a_0}}&{{a_0}}&{ - {a_2}}&{{a_4}}&{ - {a_6}} \end{array}} \right] $$ 式中, ai∈ 0, 1, 2，i=0, 1…6；
3) T矩阵的所有行非零。
4) 矩阵TTT必须是一个对角矩阵，以保证近似结果的正交性。
约束条件(2)需要保护近似DCT矩阵结构，8点DCT矩阵为：
$$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{T}} = \frac{1}{2} \cdot }\\ {\left[ {\begin{array}{*{20}{c}} {{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}\\ {{\gamma _0}}&{{\gamma _2}}&{{\gamma _4}}&{{\gamma _6}}&{ - {\gamma _6}}&{ - {\gamma _4}}&{ - {\gamma _2}}&{ - {\gamma _0}}\\ {{\gamma _1}}&{{\gamma _5}}&{ - {\gamma _5}}&{ - {\gamma _1}}&{ - {\gamma _1}}&{ - {\gamma _5}}&{{\gamma _5}}&{{\gamma _1}}\\ {{\gamma _2}}&{ - {\gamma _6}}&{ - {\gamma _0}}&{ - {\gamma _4}}&{{\gamma _4}}&{{\gamma _0}}&{{\gamma _6}}&{ - {\gamma _2}}\\ {{\gamma _3}}&{ - {\gamma _3}}&{ - {\gamma _3}}&{{\gamma _3}}&{{\gamma _3}}&{ - {\gamma _3}}&{ - {\gamma _3}}&{{\gamma _3}}\\ {{\gamma _4}}&{ - {\gamma _0}}&{{\gamma _6}}&{{\gamma _2}}&{ - {\gamma _2}}&{ - {\gamma _6}}&{{\gamma _0}}&{ - {\gamma _4}}\\ {{\gamma _5}}&{ - {\gamma _1}}&{{\gamma _1}}&{ - {\gamma _5}}&{ - {\gamma _5}}&{{\gamma _1}}&{ - {\gamma _1}}&{{\gamma _5}}\\ {{\gamma _6}}&{ - {\gamma _4}}&{{\gamma _2}}&{ - {\gamma _0}}&{{\gamma _0}}&{ - {\gamma _2}}&{{\gamma _4}}&{ - {\gamma _6}} \end{array}} \right]} \end{array} $$ 式中，γk=cos(2π(k+1)/32)，k=0, 1…6。
按照文献[15]所介绍的计算方法，本文对由{0, ±1}组成的正交矩阵进行了遍历，得到计算复杂度最低的矩阵，作为矢量数据块的转换矩阵。为区别转置符号，将其定义为矩阵V，其计算方法为：
$$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{V}} = \mathit{\boldsymbol{D}} \cdot \mathit{\boldsymbol{U}} = \mathit{\boldsymbol{D}} \cdot }\\ {\left[ {\begin{array}{*{20}{c}} 1&1&1&1&1&1&1&1\\ 0&1&0&0&0&0&{ - 1}&0\\ 1&0&0&{ - 1}&{ - 1}&0&0&1\\ 1&0&0&0&0&0&0&{ - 1}\\ 1&{ - 1}&{ - 1}&1&1&{ - 1}&{ - 1}&1\\ 0&0&0&1&{ - 1}&0&0&0\\ 0&{ - 1}&1&0&0&1&{ - 1}&0\\ 0&0&1&0&0&{ - 1}&0&0 \end{array}} \right]} \end{array} $$ $$ \mathit{\boldsymbol{D}} = {\rm{diag}}\left( {\frac{1}{{\sqrt 8 }},\frac{1}{{\sqrt 2 }},\frac{1}{2},\frac{1}{{\sqrt 2 }},\frac{1}{{\sqrt 8 }},\frac{1}{{\sqrt 2 }},\frac{1}{2},\frac{1}{{\sqrt 2 }}} \right) $$ 下面借助转换矩阵V构造矢量数据的近似DCT变换，压缩方法如下。
令Xi, j、Yi, j是矢量数据x和y坐标分块后的8×8数据块，CXi, j和CYi, j是近似DCT变换的转换矩阵。其中，i表示数据层序号，j表示数据块序号，近似DCT正向和反向变换计算方法为：
$$ {\mathit{\boldsymbol{C}}_{{\mathit{\boldsymbol{X}}_{i,j}}}} = \mathit{\boldsymbol{V}}{\mathit{\boldsymbol{X}}_{i,j}}{\mathit{\boldsymbol{V}}^{\rm{T}}} = \mathit{\boldsymbol{D}}\left( {\mathit{\boldsymbol{U}}{\mathit{\boldsymbol{X}}_{i,j}}{\mathit{\boldsymbol{U}}^{\rm{T}}}} \right)\mathit{\boldsymbol{D}} $$ (2) $$ {\mathit{\boldsymbol{C}}_{{\mathit{\boldsymbol{Y}}_{i,j}}}} = \mathit{\boldsymbol{V}}{\mathit{\boldsymbol{Y}}_{i,j}}{\mathit{\boldsymbol{V}}^{\rm{T}}} = \mathit{\boldsymbol{D}}\left( {\mathit{\boldsymbol{U}}{\mathit{\boldsymbol{Y}}_{i,j}}{\mathit{\boldsymbol{U}}^{\rm{T}}}} \right)\mathit{\boldsymbol{D}} $$ (3) 由于量化和反量化应用在变换域的块矩阵，对角矩阵D所需要的乘法可以合并到量化和反量化矩阵中。为保证矢量数据精度，量化过程仍采用无损熵编码。同时，将矩阵U分解为4个稀疏矩阵，即U = U1· U2· U3· U4，以简化量化计算过程。矩阵U稀疏矩阵表示如下：
$$ {\mathit{\boldsymbol{U}}_1} = \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0&0&0&0\\ 0&0&1&1&0&0&0&0\\ 0&0&0&0&1&1&0&0\\ 0&0&0&0&0&0&1&1\\ 1&{ - 1}&0&0&0&0&0&0\\ 0&0&1&{ - 1}&0&0&0&0\\ 0&0&0&0&1&{ - 1}&0&0\\ 0&0&0&0&0&0&1&{ - 1} \end{array}} \right],{\mathit{\boldsymbol{U}}_2} = \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0&0&0&0\\ 1&{ - 1}&0&0&0&0&{ - 1}&0\\ 0&0&1&{ - 1}&0&0&0&0\\ 0&0&1&1&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1 \end{array}} \right] $$ $$ {\mathit{\boldsymbol{U}}_3} = \left[ {\begin{array}{*{20}{c}} 1&0&1&0&0&0&0&0\\ 0&1&0&1&0&0&0&0\\ 1&0&1&0&0&0&0&{}\\ 0&1&0&{ - 1}&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1 \end{array}} \right],{\mathit{\boldsymbol{U}}_4} = \left[ {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0\\ 0&{0.5}&0&1&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&1&0&{ - 0.5}&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1 \end{array}} \right] $$ -
常见的失真准则有均方误差(mean square error，MSE)和最大绝对误差(maximum absolute error，MAE)。MSE是一个平均度量，它从整体上控制失真的大小，但对内部点的失真无法控制；而MAE小于预先给定值时，内部所有点的失真都小于该值。失真在矢量数据压缩中表现为压缩前后点坐标的漂移，带来几何对象之间拓扑关系的变化。因此，将MAE作为矢量数据压缩的失真控制，能够更好地反映局部失真。
假设原始数据由N个点组成，每个点的值为si (xi, yi)，重建的点为s′i (x′i, y′i)，则MAE定义为：
$$ {\rm{MAE}} = \mathop {\max }\limits_{0 \le i \le N - 1} \left\{ {\left| {{x_i} - {{x'}_i}} \right|,\left| {{y_i} - {{y'}_i}} \right|} \right\} $$ (4) 式中，(xi, yi)为点坐标值，i=0, 1, 2…N-1。
由于近似DCT变换系数与DCT变换近似，而DCT变换过程是无损的，因此，需要基于近似DCT变换解压缩后的数据进行判断，对超出最大绝对误差的数据进行处理。解决方法如下：
1) 利用最大绝对误差函数遍历整个矢量数据。
2) 若出现最大绝对误差值超过阈值的矢量数据，判断该矢量数据在近似DCT矩阵中对应的系数值。若系数为0，说明该数据在变换过程中被舍去，并造成较大误差，那么需要对近似DCT矩阵进行修正，将其对应系数置为1，即保留该位置对应的矢量数据；若系数为1，则说明误差是计算过程中引起的，对该位置进行插值。
3) 对误差过大位置利用插值函数增加采样，以修正误差。采用三次样条插值，该方法插值速度快，精度高，能够较好地保持空间数据特征[6]。
为平衡计算量和数据精确度，每个误差过大位置只插值一个点。实验发现，当MAE大于或者等于90时，压缩前后矢量数据的位置发生明显偏移。因此，实验选取的失真判断准则为MAE小于90，三次样条插值方法的详细描述参见文献[6]。
除了对压缩后误差较大的矢量数据进行修正外，还应对近似DCT变换过程中矩阵运算可能带来的误差加以控制，以保持数据的拓扑关系。本文采取的方法为：首先通过计算近似DCT变换与DCT变换函数之间的总能量误差，从总体上确定数据误差，然后对总能量误差较大的数据部分进一步作MAE判断，从而提高查找失真位置的效率。
-
1) 矢量数据分块。读取矢量数据要素层，依次对每一层x和y坐标进行分块，获得由8×8数据块组成的矢量数据。其中，由x、y坐标组成的数据块分别记为Xi, j, Yi, j(i, j∈$\mathbb{Z}$, $\mathbb{Z}$为正整数)，i表示数据层序号，j表示数据块序号。
2) 近似DCT变换。利用近似DCT变换的转换矩阵V，利用式(2)、(3)依次对矢量数据块进行二维近似DCT变换，每块得到64个近似系数。考虑到近似DCT变换能量集中的特性，根据标准Z字形顺序，只保留1~45个初始系数，剩余系数均取0；对矢量数据块进行近似DCT变换过程中，将对角矩阵D稀疏分解；待所有数据块变换结束，根据x和y坐标值近似DCT变换矩阵的稀疏分解，对近似DCT系数进行量化，量化过程与DCT压缩方法相同。
3) 无损熵编码。待所有数据块量化后，采用JPEG图像压缩标准的哈夫曼编码，对量化后的x和y坐标的近似DCT变换系数进行无损熵编码。
4) 误差修正。根据近似DCT变换与DCT变换的转换函数Hm (ω; V)和Hm (ω; ${\mathit{\boldsymbol{\hat{V}}}}$)，计算二者之间的能量误差${{\epsilon }_{m}}$ (V)。其中，$\epsilon $表示能量误差，用来计算总体误差的大小。令V为近似DCT矩阵，${\mathit{\boldsymbol{\hat{V}}}}$为精确DCT矩阵，近似DCT矩阵为矢量数据经过近似DCT变换后的矩阵，精确DCT矩阵为矢量数据经过DCT变换后的矩阵。总误差能量是V和${\mathit{\boldsymbol{\hat{V}}}}$之间距离基于能量的测量。
令给定矩阵V第m行的转换函数为[14]：
$$ \begin{array}{*{20}{c}} {{H_\omega }\left( {\omega ;\mathit{\boldsymbol{V}}} \right) = \sum\limits_{n = 1}^8 {{t_{m,n}}\exp \left\{ { - {\rm{j}}\left( {n - 1} \right)\omega } \right\}} ,}\\ {m = 1,2 \cdots 8} \end{array} $$ (5) 式中，$\text{j=}\sqrt{-1}$；tm, n是V的第(m, n)个元素，矩阵${\mathit{\boldsymbol{\hat{V}}}}$的转换函数与式(5)相同。那么，V和${\mathit{\boldsymbol{\hat{V}}}}$之间行的误差能量为：
$$ {D_m}\left( {\omega ;\mathit{\boldsymbol{V}}} \right) = {\left| {{H_m}\left( {\omega ;\mathit{\boldsymbol{V}}} \right) - {H_m}\left( {\omega ;\mathit{\boldsymbol{\hat V}}} \right)} \right|^2} $$ (6) 式中，ω为样本任意角度频率，ω∈ [0，π]；Dm (ω; V)表示量化近似矩阵V相对于矩阵${\mathit{\boldsymbol{\hat{V}}}}$的差异，m=1, 2…8。这样，一个从精确DCT中分离出的总误差能量为：
$$ {{\epsilon }_{m}}\left( \mathit{\boldsymbol{V}} \right)=\sum\limits_{m=1}^{8}{\int_{0}^{\text{ }\!\!\pi\!\!\text{ }}{{{D}_{m}}\left( \omega ;\mathit{\boldsymbol{V}} \right)\text{d}\omega }} $$ (7) 文献[14]证明，如果该行总能量误差超过30，即${{\epsilon }_{m}}$ (V) >30，说明近似DCT系数与精确DCT系数相差较大，则将该行数据转换到近似DCT变换前所对应的位置，并使用最大绝对误差函数对该位置变换前后数据作进一步判断：若该位置MAE < 90，不作处理；若MAE>90，对该位置进行三次样条插值修复。
由于近似DCT变换为可逆变换，因此解压缩过程为该算法的逆过程，即通过反量化、逆近似DCT变换、块重组进行矢量数据解压缩，恢复矢量数据。
-
为验证本文方法的可靠性，在Windows 7平台上，使用C#实现了本文所述方法。实验选取了7组不同大小shp格式的矢量数据，与非误差修正方法进行了重构数据误差对比，与频率域压缩算法进行了压缩率对比，与空间域、频率域压缩算法进行了压缩时间对比，验证本文算法的效果。
-
对选取的7组实验数据使用本文算法进行压缩，并对顾及最大绝对误差和不顾及最大绝对误差两种情况进行对比。表 1为实验数据大小和两种情况的重构误差。
表 1 有误差修正与无误差修正重构结果对比
Table 1. Reconstruction Results Comparison of Error Correction and No Error Correction
数据量/kB 能量误差$\epsilon $ 最大误差/m 无修正 有修正 35 942 30.12 0.015 7 0.002 3 17 715 30.17 0.014 3 0.002 1 9 900 31.29 0.017 6 0.001 9 6 256 30.05 0.023 1 0.002 8 2 210 31.83 0.031 7 0.005 6 1 080 31.56 0.043 3 0.007 9 684 32.37 0.042 6 0.009 1 由表 1误差对比结果可以看出，有修正算法的误差明显低于无修正算法。这说明对于误差较大的点，采用增加采样点的方法进行误差修正，能够明显改善矢量数据重构效果。
-
为验证本文算法的压缩效率，与频率域具有代表性的压缩算法进行了压缩率和平均压缩时间的比较，每个算法分别进行4次压缩，取平均用时。一方面，与文献[13]精确DCT算法、文献[7]整数小波变换算法以及文献[14]16×16近似DCT算法等频率域压缩进行压缩后的数据大小和压缩率进行对比，表 2为各算法对矢量数据压缩结果；另一方面，与文献[4]Douglas-Peucker算法和文献[6]LZW等空间域压缩算法进行平均压缩用时对比，验证本文算法的改进效果，表 3为各算法平均压缩用时对比结果。
表 2 与相关算法压缩结果对比
Table 2. Comparison of Compression Results with Correlation Algorithms
实验数据 压缩后数据大小/kB 压缩率/% 数据类型 数据大小/kB 本文算法 文献[14] 文献[7] 文献[13] 本文算法 文献[14] 文献[7] 文献[13] Globel Contour.shp 35 942 938 1 516 3 046 2 178 2.6 4.2 8.4 6.1 BOUNT_poly.shp 17 715 466 760 1 553 1 114 2.6 4.3 8.8 6.3 BOUNT_line.shp 9 900 259 434 846 591 2.6 4.4 8.5 5.9 adir_s.shp 6 256 174 289 553 379 2.8 4.6 8.8 6.1 hyd2_4l.shp 2 210 61 93 203 143 2.8 4.2 9.2 6.5 bou1_4l.shp 1 080 31 48 94 79 2.9 4.4 8.7 7.3 xianonecad.shp 684 19 31 63 46 2.8 4.5 9.2 6.7 表 3 不同算法压缩平均用时对比
Table 3. Comparison of Compression Time of Different Algorithms
实验数据 算法用时/ms 数据类型 数据大小/kB 本文算法 文献[14] 文献[7] 文献[13] 文献[4] 文献[6] Globel Contour.shp 35 903 3 507 4 218 4 309 4 429 18 375 17 683 BOUNT_poly.shp 17 638 1 715 2 033 2 336 2 405 9 102 8 745 BOUNT_line.shp 9 775 967 1 548 1 621 1 793 5 072 4 923 adir_s.shp 6 219 614 723 866 959 3 759 3 091 hyd2_4l.shp 2 340 212 269 243 292 1 135 1 092 bou1_4l.shp 1 103 117 141 179 177 559 539 xianonecad.shp 691 69 78 85 91 353 341 由表 2可知，传统基于频率域的压缩算法压缩率处于5.9%~9.2%之间, 未进行误差修正的近似DCT压缩算法压缩率处于4.2%~4.6%之间, 本文压缩算法压缩率处于2.6%~2.9%之间。可见，本文所提出的矢量数据压缩方法相对于传统的频率域压缩算法，有效降低了矢量数据压缩率，降低了矢量数据所需的存储空间。
由表 3中各算法压缩用时结果可以看出，本文算法用时远小于文献[4]Douglas-Peucker算法和文献[6]LZW等空间域压缩算法。而且，相对于文献[13]、文献[7]和文献[14]等频率域压缩算法，本文算法压缩用时也明显降低。这是因为基于矩阵变换的近似DCT算法避免了DCT算法和整数小波算法中较为复杂的乘法运算，降低了计算复杂度。
对文献[13]、文献[7]、文献[14]和文献[6]算法执行过程中所进行的加法、乘法及移位等操作进行了统计，作为计算复杂度对比指标。如表 4所示。
表 4 计算复杂度对比
Table 4. Arithmetic Time Comparison of Different Algorithms
相对于其他4种算法，8×8近似DCT算法的计算复杂度分别降低了63%、78%、81%和82%，有效改善了运算速度。
-
本文基于矢量数据结构特点和近似DCT变换，提出了一种顾及最大绝对误差的矢量数据快速压缩算法。通过矢量数据分块、近似DCT变换与量化以及无损熵编码，实现了矢量数据快速压缩, 并通过判定重构数据最大绝对误差，对过大误差进行了三次样条插值修正。与类似方法相比，本文方法通过最低计算复杂度矩阵求解和变换矩阵系数分解，降低了压缩过程的计算复杂度。并通过实验证明了此算法的有效性。
Vector Map Data Compression of Frequency Domain with Consideration of Maximum Absolute Error
-
摘要: 针对传统的基于离散余弦变换（discrete cosine transform，DCT）的矢量数据压缩算法局部误差较大和计算复杂度高的问题，提出了一种顾及矢量数据最大绝对误差的快速近似DCT压缩方法。首先，结合现有矢量数据拓扑关系，构造矢量数据块；其次，根据近似DCT变换正交性的特点，计算约定矩阵的最优化解，将计算复杂度最低的解设为近似DCT变换的转换矩阵；最后，结合矢量数据近似DCT变换和精确DCT变换的总能量差，计算重构数据的最大绝对误差，对超过误差阈值的数据进行三次样条插值，最大限度地保证矢量数据精度。实验结果表明，该方法计算复杂度较低，压缩速度快，在降低压缩率的同时，能较好地保持空间数据的拓扑关系和数据精度。Abstract: In this paper, taking the maximum absolute error for vector data into account, we propose an approximate DCT compression method, which is designed for controlling the maximum absolute error and the high arithmetic complexity, aimed at traditional local compression algorithm for vector data based on discrete cosine transform. First of all, we construct vector data blocks on the basis of vector data topology. Secondly, we calculate the optimization solution of the agreed matrix in accor-dance with the orthogonality of approximate DCT transform, and then set the solution which has the minimum computational complexity as the conversion matrix for approximate DCT transform to ma-ximally guarantee the precision of vector data. Finally, we combine the total energy between the DCT transform and accurate approximate DCT transform of vector data with maximum absolute error of the reconstructed data, and use three spline interpolation function for data which exceeds thresholds of error to ensure maximum accuracy. Experimental results show that the proposed method has low computational complexity and high speed compression, it can keep the topological relation of the spatial data and the accuracy of the data while reducing the compression rate.
-
Key words:
- approximation DCT /
- vector map data compression /
- sparse decomposition /
- MAE
-
表 1 有误差修正与无误差修正重构结果对比
Table 1. Reconstruction Results Comparison of Error Correction and No Error Correction
数据量/kB 能量误差$\epsilon $ 最大误差/m 无修正 有修正 35 942 30.12 0.015 7 0.002 3 17 715 30.17 0.014 3 0.002 1 9 900 31.29 0.017 6 0.001 9 6 256 30.05 0.023 1 0.002 8 2 210 31.83 0.031 7 0.005 6 1 080 31.56 0.043 3 0.007 9 684 32.37 0.042 6 0.009 1 
下载: 导出CSV
表 2 与相关算法压缩结果对比
Table 2. Comparison of Compression Results with Correlation Algorithms
实验数据 压缩后数据大小/kB 压缩率/% 数据类型 数据大小/kB 本文算法 文献[14] 文献[7] 文献[13] 本文算法 文献[14] 文献[7] 文献[13] Globel Contour.shp 35 942 938 1 516 3 046 2 178 2.6 4.2 8.4 6.1 BOUNT_poly.shp 17 715 466 760 1 553 1 114 2.6 4.3 8.8 6.3 BOUNT_line.shp 9 900 259 434 846 591 2.6 4.4 8.5 5.9 adir_s.shp 6 256 174 289 553 379 2.8 4.6 8.8 6.1 hyd2_4l.shp 2 210 61 93 203 143 2.8 4.2 9.2 6.5 bou1_4l.shp 1 080 31 48 94 79 2.9 4.4 8.7 7.3 xianonecad.shp 684 19 31 63 46 2.8 4.5 9.2 6.7
下载: 导出CSV
表 3 不同算法压缩平均用时对比
Table 3. Comparison of Compression Time of Different Algorithms
实验数据 算法用时/ms 数据类型 数据大小/kB 本文算法 文献[14] 文献[7] 文献[13] 文献[4] 文献[6] Globel Contour.shp 35 903 3 507 4 218 4 309 4 429 18 375 17 683 BOUNT_poly.shp 17 638 1 715 2 033 2 336 2 405 9 102 8 745 BOUNT_line.shp 9 775 967 1 548 1 621 1 793 5 072 4 923 adir_s.shp 6 219 614 723 866 959 3 759 3 091 hyd2_4l.shp 2 340 212 269 243 292 1 135 1 092 bou1_4l.shp 1 103 117 141 179 177 559 539 xianonecad.shp 691 69 78 85 91 353 341
下载: 导出CSV
-
[1] Gray R M, Cosman P C, Oehler K L. Neural Network Implementation of Adaptive Vector Quantization for Image Compression[J]. Global Journal of Computer Science & Technology, 2014, 59(4):91-96 http://dl.acm.org/citation.cfm?id=197770 [2] 陈善学, 郑文静, 张佳佳, 等.变换域离散度排序的高光谱图像快速压缩算法[J].武汉大学学报·信息科学版, 2016, 41(7):868-874 http://ch.whu.edu.cn/CN/abstract/abstract5477.shtml Chen Shanxue, Zheng Wenjing, Zhang Jiajia, et al. Fast Compression Algorithm for Hyperspectral Image Based on Dispersion Sorting in Transform Domain[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7):868-874 http://ch.whu.edu.cn/CN/abstract/abstract5477.shtml [3] 黄伟明, 杨建宇, 陈彦清, 等.基于扇形筛选法的矢量数据压缩方法[J].武汉大学学报·信息科学版, 2016, 41(4):487-491 http://ch.whu.edu.cn/CN/abstract/abstract5419.shtml Huang Weiming, Yang Jianyu, Chen Yanqing, et al. Method of Vector Data Compression Based on Sector Screening[J]. Geomatics and Information Science of Wuhan University, 2016, 41(4):487-491 http://ch.whu.edu.cn/CN/abstract/abstract5419.shtml [4] Sim M S, Kwak J H, Lee C H. Fast Shape Matching Algorithm Based on the Improved Douglas-Peucker Algorithm[J]. KIPS Transactions on Software and Data Engineering, 2016, 5(10):497-502 doi: 10.3745/KTSDE.2016.5.10.497 [5] Lee S H, Hwang W J, Jung J J, et al. Vector Map Data Compression Using Polyline Feature[J]. IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2014, 97(7):1595-1604 http://adsabs.harvard.edu/abs/2014ieitf..97.1595l [6] Chand A K B, Vijender N. Positive Blending Hermite Rational Cubic Spline Fractal Interpolation Surfaces[J]. Calcolo, 2015, 52(1):1-24 doi: 10.1007/s10092-013-0105-5 [7] Gendron M L, Lohrenz M C. Vector Map Data Compression with Wavelets[J]. Journal of Navigation, 2000, 53(3):437-449 doi: 10.1017/S0373463300001089 [8] Huang W, Yang J, Yue Y, et al. Vector Data Compression of Frequency Domain Based on Tolerance of Average Error[J]. Journal of Geo-information Science, 2015, 17(8):883-888 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dqxxkx201508001 [9] Senapati R K, Pati U C, Mahapatra K K. A Low Complexity Orthogonal 8×8 Transform Matrix for Fast Image Compression[C]. 2011 Annual IEEE India Conference, Hyderabad, India, 2011 [10] Im D Y, Jang B J, Lee S H, et al. Hybrid Polyline Simplification for GIS Vector Map Data Compression[J]. Journal of Multimedia Society, 2013, 16(4):418-429 doi: 10.9717/kmms.2013.16.4.418 [11] Chen M, Wen Y, Yue S. A Progressive Transmi-ssion Strategy for GIS Vector Data Under the Precondition of Pixel Losslessness[J]. Arabian Journal of Geosciences, 2015, 8(6):3461-3475 doi: 10.1007/s12517-014-1467-y [12] 廖明生, 吴华意, 李德仁.基于DCT变换的GIS矢量数据压缩技术研究[J].武汉大学学报·信息科学版, 2007, 32(12):1123-1126 http://ch.whu.edu.cn/CN/abstract/abstract2060.shtml Liao Mingsheng, Wu Huayi, Li Deren. DCT-Based GIS Vector Data Compression[J]. Geomatics and Information Science of Wuhan University, 2007, 32(12):1123-1126 http://ch.whu.edu.cn/CN/abstract/abstract2060.shtml [13] 李金凤, 高巍.基于DCT变换矢量数据压缩[J].计算机应用与软件, 2010, 27(11):105-107 doi: 10.3969/j.issn.1000-386X.2010.11.034 Li Jinfeng, Gao Wei. DCT-Based Vector Data Compression[J]. Computer Applications and Software, 2010, 27(11):105-107 doi: 10.3969/j.issn.1000-386X.2010.11.034 [14] Silveira T L T D, Bayer F M, Cintra R J, et al. An Orthogonal 16-Point Approximate DCT for Image and Video Compression[J]. Multidimensional Systems & Signal Processing, 2016, 27(1):1-18 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Arxiv000001331052 [15] Puchala D, Stokfiszewski K. Low-Complexity Approximation of 8-Point DCT for Image Compression[J]. Journal of Computer Science, 2012, 20(2):107-117 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0214879892 [16] Zhan X, Zhang R, Yin D, et al. SAR Image Compression Using Multiscale Dictionary Learning and Sparse Representation[J]. IEEE Geoscience & Remote Sensing Letters, 2013, 10(5):1090-1094 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0229525287/ [17] Baig M Y, Lai K, Punchihewa A. Compressed Sensing-Based Distributed Image Compression[J]. Applied Sciences, 2014(4):128-147 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0230673221/ [18] Gray R M, Cosman P C, Oehler K L. Neural Network Implementation of Adaptive Vector Quantization for Image Compression[J]. Global Journal of Computer Science & Technology, 2014, 59(4):91-96 -
点击查看大图
图(1) / 表(4)
计量
- 文章访问数: 1586
- HTML全文浏览量: 127
- PDF下载量: 202
- 被引次数: 0
