一种高效的数字高程模型数据无损压缩的方法

摘要

本发明实现了用最优线性二乘预测模型和自适应算术编码技术来实现数字高程模型的快速无损压缩。在保持数字高程模型数据信息压缩前后无丢失的情况下，实现数字高程模型数据更高的压缩率、压缩时间更短。压缩过程分为两步：第一步，通过最优线性二乘预测模型识别和消除数字高程模型相邻高程间信息冗余，提取独立的空间信息，减小信息熵，即通过最优线性二乘预测模型去相关后，用一个无冗余或冗余度较小的数组代替；下一步，对该数组采用自适应算术编码技术对所提取的信息进行编码，使减少后的信息熵得以具体实现，进一步减少数据量。经过这两步后，得到具有更高压缩比的二进制数据流。

主权项

1.一种高效的数字高程模型数据无损压缩的方法步骤包括：步骤一：建立最优线性二乘预测模型由于数字高程模型(DEM)中任一点(i，j)的高程变量H(i，j)是服从正态分布的随机变量，其预测值误差可以由相邻点高程获得，DEM中(i，j)点的高程误差ν_i，j由公式(1)计算得出。ν_i，j＝H_i，j-κ₁H_i-1，j-κ₂H_i-1，j-1-κ₃H_i，j-1        (1)公式(1)中，κ₁，κ₂，κ₃是实数，k₁+k₂+k₃＝1；ν_i，j组成一个(m-1)×(n-1)的二维矩阵V，衡量误差矩阵V的重要精度指标是数学期望μ和方差σ，σ越小，V的离散度越小，反之，离散程度越大，为了使预测模型最优，应该满足公式(2)：$\left\{\begin{array}{c}u=0\\ \sigma =\min \end{array}\right.,$即$\left\{\begin{array}{c}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{v}_{i,j}=0\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}\left({\alpha }_{i,j}{v}_{i,j}^2\right)=\min \\ v_{i,j}=H_{i,j}-{\kappa }_1{H}_{i,j}-{\kappa }_2{H}_{i-1,j-1}-{\kappa }_3{H}_{i,j-1}\end{array}\right.---\left(2\right)$公式(2)就是最优线性二乘预测模型，其中，α_i，j是相关系数，α_i，j＝1；令ρ为Lagrange乘数，将Φ对κ₁，κ₂，κ₃求一阶导数并令：$\left\{\begin{array}{c}\underset{i,j}{\Sigma }v=0\\ \partial \psi /\partial {\kappa }_1=0\\ \partial \psi /\partial {\kappa }_2=0\\ \partial \psi /\partial {\kappa }_3/=0\\ \partial \psi /\partial \lambda =0\end{array}\right.---\left(3\right)$$\left(\begin{array}{cccc}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}^2& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i,j-1}& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}^2& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}{H}_{i-1,j}& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}{H}_{i,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j-1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}^2& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}& 0\end{array}\right)\left(\begin{array}{c}{\kappa }_1\\ {\kappa }_2\\ {\kappa }_3\\ \rho \end{array}\right)=\left(\begin{array}{c}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i-1,j}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i-1.,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}\end{array}\right)---\left(4\right)$令$A=\left\{a_{\mathrm{ij}}\right\}=\left(\begin{array}{cccc}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}^2& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i,j-1}& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}^2& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}{H}_{i-1,j}& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}{H}_{i,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j-1}{\overset{n}{\Sigma }}{H}_{i-1,j}{H}_{i,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}^2& -\frac{1}{2}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i-1,j-1}& \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j-1}& 0\end{array}\right),$$B=\left\{b_i\right\}=\left(\begin{array}{c}\underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i-1,j}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i-1,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}{H}_{i,j-1}\\ \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{H}_{i,j}\end{array}\right)$其中，i，j＝1，2，3，4。通过Doolittle分解法解上述方程(4)，得到：$\left\{\begin{array}{c}{u}_{\mathrm{kj}}=a_{\mathrm{kj}}-\underset{t=1}{\overset{k-1}{\Sigma }}{l}_{\mathrm{kt}}{u}_{\mathrm{tj}}\\ l_{ik}=(a_{ik}-\underset{t=1}{\overset{k-1}{\Sigma }}{l}_{it}{u}_{\mathrm{tk}})/u_{\mathrm{kk}}\end{array}\right.$k＝1，2，3，4；j＝k，k+1，...，3；i＝k+1，...，n         (5)$\left\{\begin{array}{c}{y}_i=b_i-\underset{t=1}{\overset{i-1}{\Sigma }}{l}_{\mathrm{it}}{y}_t\\ {\kappa }_j=(y_j-\underset{t=j+1}{\overset{n}{\Sigma }}{u}_{it}{\kappa }_t)/u_{\mathrm{jj}}\end{array}\right.$其中i＝1，...，4；j＝3，2，1                           (6)通过上式(5)和(6)，求得κ₁，κ₂，κ₃的值，保留H(i，j)的第一行和第一列的值不变，利用ν_i，j＝int(H_i，j-κ₁H_i-1，j-κ₂H_i-1，j-1-κ₃H_i，j-1)计算高程改正，结果存储在pVar(i，j)，此时1≤i≤n，1≤j≤m。步骤二：自适应算术编码压缩DEM改正误差在自适应算术编码高阶上下文模型的实现中，将0阶上下文表存储在线性链表中，链表中的每个元素包含了指向相应的1阶上下文表的指针，1阶上下文表中又包含了指向2阶上下文表的指针，2阶上下文表中又包含了指向3阶上下文表的指针，由此构成整个上下文树，树中只有出现过的上下文才拥有已分配的结点，没有出现过的上下文不必占用内存空间，只有在该上下文后面出现过的字符才拥有计数值，由此可以最大限度地减少空间消耗，经过该过程后，得到DEM具有高压缩比的二进制数据流。