基于统计预测模型的算术编码及其DSP实现.pdfVIP

基于统计预测模型的 算术编码及其 DSP 实现 华刚 郑南宁 西安交通大学人工智能与机器人研究所 西安交通大学 99119#信箱 710049 ganghua@263.net 摘摘 要：本文针对无损压缩的预测要 -编码以及 DSP 实现的问题，提出一种新的统计预测模型，并将其与算术 摘摘 要要 编码相结合，形成了一种预测-熵编码的压缩方案。该算法具有复杂度小、压缩效果好、易于用 DSP 实现的 特点，并且将其应用于具有较明显的纹理特性的图像的实时无损压缩上，取得了非常好的结果。 关键词：统计预测、算术编码、关键词 DSP、数据压缩、马尔科夫过程 关键词关键词 1 绪论 数据的无损压缩方法，较为常用的有霍夫曼编码、游程编码、算术编码以及各种基于字 典的编码。相对于有损编码，无损编码的特点在于编解码之后信号能够完全的、无误差的恢 复出来，但一般情况下无损压缩的压缩效率比有损压缩的效率要低得多。在工业环境以及一 些医用设备的数据采集、传输中，经常要对数据进行实时的压缩。这类压缩的共同特点是： 1、要求压缩编码是无损的。2、要求对采集数据进行实时的编码。3、对压缩倍数有一定的 要求。但这类系统也存在着专用性强，不易采用统一的硬件系统来实现的特点。 鉴于此，对于这类系统，采用现在流行的多种通用高速 DSP 芯片来进行数据的压缩是一 种非常可取的方案。由于 DSP 芯片的可编程重构性，可以根据信源的特点有针对性的进行算 法的设计而满足不同的需要。而对于用 DSP 实现的压缩算法，根据 DSP 芯片自身的特点，算 法复杂度不能太高，然而，对较为常用的压缩算法而言，算法的复杂度与压缩效率几乎是成 正比的，因此如何在保持较低算法复杂度的情况下达到满足需要的压缩效率，以方便用 DSP 芯片实现，是值得研究的一个问题。 对无损压缩算法的研究表明，单纯的用算术编码对信源进行压缩，对于普通的信源通常 只能达到 1.5~2.5 倍的压缩效率。但是如果能充分的利用信源的统计特性，通过一定的模型 对信源进行预测，然后对预测值与实际值的差值进行编码，能够显著的提高算法的压缩效率。 关于预测，在当前的许多压缩算法和标准如 JPEG 中，使用得很多的是线性预测的方法。本 文提出了一种利用信源本身统计特性进行预测的模型，将其与算术编码相结合，取得了较好 的压缩效果。基于该统计预测模型的压缩算法复杂度小，具有对信源的自适应性，易于用 DSP 实现。 2 统计预测模型 如果将输入信源看成一个一维的随机序列 {xk } ，假设其有 M 种取值,则其中第 L 个符号 的熵满足下式[1]: log M ≥ H (x ) ≥ H (x | x ) ≥ H (x | x , x ) ≥ ⋅⋅ ≥ H (x | x ,x ,⋅⋅,x ) H ...(a) 2 l l l −1 l l −1 l −2 l l−1 l −2 l ∞ 式中 H (•) 表示熵值。 (a) 式说明对于信源序列，如果已经确定的符号值越多，那么下一个 符号的值的自由度越小，即在对下一个符号值进行预测时，预测值与实际值的相似程度越大。 基于此，可以设计如下预测模型，设信源已确定符号为 x 、x 、⋅ ⋅ ⋅ x ，同时设信源的符 1 2 n 号集 A = {X 1 ,X 2 ,⋅ ⋅ ⋅,X m } ，假定对信源进行k 阶统计预测，则根据已经确定的信源符号， 可以计算 P (X i | X j 1 ,X j 2 ,⋅ ⋅ ⋅,X jk }式中 1≤ i, j 1 ~ j k ≤ m 且 X j 1 ,X j 2 ,⋅ ⋅ ⋅,X jk 在信源已确 定的符号中是顺序出现的，对于先验计算出来的 P (X i | X j 1 ,X j 2 ,⋅ ⋅ ⋅,X jk } ，选择使得 P (X i | xn−k +1 ,xn−k +2 ,⋅ ⋅ ⋅,xn }最大的 X i 作为预测值,如下式所示： ˆ xn+1 = X i ,且P (X i | x