压缩技术实验编码

1、压缩技术实验编码实验一统计编码实验目的1. 熟悉统计编码的原理2. 掌握r元Huffman编码的方法；3. 了解Huffman编码效率及冗余度的计算;二、 实验原理霍夫曼编码，又称最佳编码，根据字符出现概率来 构造平均长度最短的变长编码。Huffman编码步骤：(1) 把信源符号x i(i=1,2,按出现概率的值由 大到小的顺序排列；(2) 对两个概率最小的符号分别分配以“ 0和“ 1,然后把这两个概率相加作为一个新的辅助符号的概率；(3) 将这个新的辅助符号与其他符号一起重新按概 率大小顺序排列；跳到第2步，直到出现概率相加为1为止；(5) 用线将符号连接起来，从而得到一个码树，树的 N个端

2、点对应N个信源符号；(6) 从最后一个概率为1的节点开始，沿着到达信源 的每个符号，将一路遇到的二进制码 “ 0或“ 1顺序排列 起来，就是端点所对应的信源符号的码字。以上是二元霍夫曼编码。如果是 r元霍夫曼编码， 则应该如何做呢？在 HUFFMAN 编码方案中，为出现概率较小的信 源输出分配较长的码字，而对那些出现可能性较大的信 源输出分配较短的码字。为此，首先将 r 个最小可能的 信源输出合并成为一个新的输出，该输出的概率就是上 述的 r 个输出的概率之和。重复进行该过程直到只剩下 一个输出为止。信源符号的个数 q 与 r 必须满足如下的 关系式：q = (r-1) n + r n 为整数

3、 如果不满足上述关系式，可通过添加概率为零的信源符 号来满足。这样就生成了一个树，从该树的根节点出发 并将0、1分别分配给任何r个来自于相同节点的分支，生成编码。可以证明用这种方法产生的编码在前 向树类编码中具有最小的平均长度。举例：对于取值为 u=u1,u2,u3,u4,u5,u6 其相应的 概率为 p=0.1 ，0.3，0.05，0.09，0.21，0.25的信源， 试设计一个 3 元 HUFFMAN 码，求出码子的平均长度 与编码效率。20til0. 10.31u20.30. 25211u30. 050.21川ul0. 090. 122u50.21a 090u6().25a 05*0.3

4、*0.25*0. 21*0. 14養 0. 1 -0.450.3 0. 253元编码，所以每次3个概率值相加。注：因为是码字的平均长度L=2 X 0.1+1 X 0.3+3 X 0.05+3 X 0.09+2 X 0.21+1 X0.25=1.59信源的熵H ( u) = (0.1 X Iog2(0.1)+ 0.3X Iog2(0.3)+ 0.05XIog2(0.05)+ 0.09X Iog2(0.09)+0.21 X Iog2(0.21)+ 0.25X Iog2(0.25)=2.3549编码效率Q=0.9345用MATLAB实现该编码的方法可用下面的矩阵来说明：20U10.10.30.30.

5、30.30.45 11U20.30.25 0.25 0.250.250.3211U30.05 0.21 0.21 0.21 0.45 0.25212U40.09 0.10.10.1422U50.21 0.09 0.14 0.10U60.250.05 0.0注：每次3个数加完后，重新按序分配编号，在按概率值重新排序，再进行下次加数7m= 22200注：m中每一行为按概率值重新排序后的编号列，一共 三次概率值排序；单箭头表示两次排序中的概率值并未 参加加数，未改变；多箭头表示箭头所指向的多项概率 值相加后得到箭头源的概率值。c=2111220201202200210注：c为编码矩阵，从最后一行开始

6、，因为是 3元编码, 故按0、1、2开始编码。根据m中的箭头，单箭头不变, 多箭头根据箭头源每上一层则箭头源编码后再加一位， 同一层中加的位数按 0、1、2顺序添加。m矩阵第I (11 )行中的 1记录了合并后的信源符号在新信源中的位置实验步骤1. 输入初始概率分布p和码元数r;2. 检查是否满足q = (n-1)r + r (q为输入信源的个 数)，如果不满足则补零使之满足；3. 排序得m矩阵4 根据 m 矩阵获得 c 矩阵5.从c矩阵中取出最后的码字矩阵h并计算平均码 长和编码效率。四、实验仪器1 计算机；2 MATLAB 程序；3 移动式存储器（软盘、 U 盘等）；4 记录用的笔、纸。五

7、、实验报告内容1、实验目的2、实验要求3、实验环境4、实验内容（叙述操作过程，提交主要程序段）5、实验结论6、实验总结六、思考题1 什么是霍夫曼编码？在 Matlab 中如何实现？2 r 元霍夫曼编码的原理和过程？实验二 量化与变换编码一、 实验目的1. 理解有损压缩和无损压缩的概念；2. 理解图像压缩的主要原则和目的；3. 掌握 DCT 编码的原理4. 了解游程编码的原理二、 实验原理1.图像压缩原理 图像压缩主要目的是为了节省存储空间，增加传输 速度。图像压缩的理想标准是信息丢失最少，压缩比例 最大。不损失图像质量的压缩称为无损压缩，无损压缩 不可能达到很高的压缩比；损失图像质量的压缩称为

8、有 损压缩，高的压缩比是以牺牲图像质量为代价的。压缩 的实现方法是对图像重新进行编码，希望用更少的数据 表示图像。信息的冗余量有许多种，如空间冗余，时间冗余， 结构冗余，知识冗余，视觉冗余等，数据压缩实质上是 减少这些冗余量。高效编码的主要方法是尽可能去除图 像中的冗余成分，从而以最小的码元包含最大的图像信 息。编码压缩方法有许多种，从不同的角度出发有不同 的分类方法，从信息论角度出发可分为两大类。（1）冗余度压缩方法， 也称无损压缩、 信息保持编 码或嫡编码。具体说就是解码图像和压缩编码前的图像 严格相同，没有失真，从数学上讲是一种可逆运算。（2）信息量压缩方法， 也称有损压缩、 失真度编码

9、 或烟压缩编码。也就是说解码图像和原始图像是有差别的，允许有一定的失真。 应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下 3 类：（1）无损压缩编码种类哈夫曼（ Huffman ）编码，算术编码，游程（ RLE） 编码， Lempel zev 编码。（2）有损压缩编码种类预测编码， DPCM ，运动补偿； 频率域方法：正交变换编码 （如 DCT） ，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码；基于重要性： 滤波，子采样， 比特分配， 向量量化；（3）混合编码。有 JBIG ，H261，JPEG ，MPEG 等技术标准。 本实验主要利用 MATLA

10、B 程序进行离散余弦变换（ DCT ）压缩和游程编码 （ Run Length Encoding ， RLE ）。1）离散余弦变换（DCT）图像压缩原理离散余弦变换 DCT 在图像压缩中具有广泛的应用，它 是 JPEG 、MPEG 等数据压缩标准的重要数学基础。和相同图像质量的其他常用文件格式 （如 GIF（ 可交 换的图像文件格式）,TIFF（标签图像文件格式），PCX（图 形文件格式）相比，JPEG是目前静态图像中压缩比最高 的。 JPEG 比其他几种压缩比要高得多，而图像质量都 差不多(JPEG处理的图像只有真彩图和灰度图)。正是由 于其高压缩比，使得 JPEG 被广泛地应用于多媒体和网

11、 络程序中。JPEG有几种模式，其中最常用的是基于DCT 变换的顺序型模式，又称为基本系统 (Baseline)。用 DCT 压缩图像的过程为：(1) 首先将输入图像分解为8X 8或16X 16的块，然 后对每个子块进行二维 DCT变换。(2) 将变换后得到的量化的 DCT 系数进行编码和传 送，形成压缩后的图像格式。用 DCT 解压的过程为：(1) 对每个8X 8或16X 16块进行二维DCT反变换。(2) 将反变换的矩阵的块合成一个单一的图像。余弦变换具有把高度相关数据能量集中的趋势，DCT 变换后矩阵的能量集中在矩阵的左上角， 右下的大 多数的 DCT 系数值非常接近于 0。对于通常的图

12、像来说， 舍弃这些接近于 0 的 DCT 的系数值，并不会对重构图 像的画面质量带来显著的下降。所以，利用 DCT 变换 进行图像压缩可以节约大量的存储空间。压缩应该在最 合理地近似原图像的情况下使用最少的系数。使用系数 的多少也决定了压缩比的大小。在压缩过程的第2步中，可以合理地舍弃一些系数， 从而得到压缩的目的。在压缩过程的第 2步，还可以 采用RLE和Huffman编码来进一步压缩。2）游程编码（RLE原理： 例如如下这幅的二值图像,D000111UOC01110（J0UO01110UUOOCLHOOOODL1.1000OMl L LonoooaiiLCoaooo11LOCOUOOO如果

13、采用游程编码可以按如下格式保存lu807130613a6rr3061rr06130650d1306rr3a5其中10和8表示图像的宽和咼。在这个小例子中游程编码并没有起到压缩图像的作用。这是由于这个图 的尺寸过小，当图像尺寸较大时游程编码还是不错的无 损压缩方法。对于灰度图像和二值图像，用游程编码一 般都有很高的压缩率。游程编码方法实现起来很容易， 对于具有长重复值的串的压缩编码很有效，例如：对于 有大面积的阴影或颜色相同的图像，使用这种方法压缩 效果很好。很多位图文件格式都采用游程编码，如TIFF， PCX GEM BMF等。实验步骤1 打开计算机，启动 MATLAB 程序；2 调入数字图像，并进行数据的游程（ RLE ）编码压 缩处理；3 将原图像在 P