压缩技术实验编码(20210427113653)

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

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

3、根节点出发并!1!将0、1分别分配给任何r个来自于相同节点的分支, 生成编码。可以证明用这种方法产生的编码在前向树类 编码中具有最小的平均长度。对于取值为u=ul,u2,u3,u4,u5,u6M相应的概率为p二01, 03, 005, 009, 021，0.25的信源，试设 计一个3元HUFFMAN码，求出码子的平均长度 与编 码效率。201211JH220U10. 1U20.3U30. 05ul0. 09u50.21().250.30.250.21*0. 210. 10. 09a ()50*0.3*0.250注：因为是码密元编码，所以每次3个概率值相加。的平均长度L=2 X 0.1+1 X

4、0.3+3 X 0.05+3 X 0.09+2 X 0.21+1X 0.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实现该编码的方法可用下面的矩阵来说明：20Ui0.1 0.3(2)0.30.30.30.4511U20.3(2) 0.25 0.25 0.25 0.25 0.3211U30.05 0.21 (5)0.21 0.21 0.450.2

5、5 212U40.09 0.10.10.14 22U50.21 0.09 0.14 0.10 Ue 0.25 0.05(3)00注：每次3个数加完后，重新按序分配编号，在按概率 值重新排序，再进行下次加数。3注：m中每一行为按概率值重新排序后的编号列，一共 三次 概率值排序；单箭头表示两次排序中的概率值并未参加加数， 未改变；多箭头表示箭头所指向的多项概率值相加后得到箭头 源的概率值。注：c为编码矩阵，从最后一行开始，因为是3元编码，故按 0、1、2开始编码。根据m中的箭头，单箭头不变，多箭头根 据箭头源每上一层则箭头源编码后再加一位，同一层中加的 位数按0、1、2顺序添加。m矩阵第I (11

6、 )行中的记录了合并后的信源符号在新信源中的位置三、实验步骤1 -输入初始概率分布p和码元数r；2.检查是否满足q = (n-1 )r + r (q为输入信源的个数),如果不满足则补零使之满足;3. 排序得m矩阵4. 根据m矩阵获得c矩阵5从c矩阵中取出最后的码字矩阵h并计算平均码 长和 编码效率。四、实验仪器1计算机；2 MATLAB 程序；3移动式存储器（软盘、U盘等）；4记录用的笔、纸。五、实验报告内容1、实验目的2、实验要求3、实验环境4、实验内容（叙述操作过程，提交主要程序段）5、实验结论6、实验总结思考题1什么是霍夫曼编码？在Matlab中如何实现?2r元霍夫曼编码的原理和过程?实

7、验二量化与变换编码实验目的1理解有损压缩和无损压缩的概念;2理解图像压缩的主要原则和目的；3. 掌握DCT编码的原理4.了解游程编码的原理二、实验原理1 图像压缩原理图像压缩主要目的是为了节省存储空间，增加 传输 速度。图像压缩的理想标准是信息丢失最少，压缩比例 最 大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到 很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比 是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行 编码，希望用更少的数据表示图像。信息的冗余量有许多种，如空间冗余，时间冗余，结构冗余， 知识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。高 效编码的主要

8、方法是尽可能去除图像中的冗余成分，从而以最小 的码元包含最大的图像信息。编码压缩方法有许多种，从不同的角度出发有不同的分类 方法，从信息论角度出发可分为两大类。(1)冗余度压缩方法，也称无损压缩、信息保持编 码 或嫡编码。具体说就是解码图像和压缩编码前的图像严格相 同，没有失真，从数学上讲是一种可逆运算。(2)信息量压缩方法，也称有损压缩、失真度编码 或 烟压缩编码。也就是说解码图像和原始图像是有差别的，允许 有一定的失真。应用在多媒体中的图像压缩编码方法，从压缩编码 算法原 理上可以分为以下3类：（1）无损压缩编码种类哈夫曼（Huffman ）编码，算术编码，游程（RLE ）编码，Lempe

9、l zev编码。（2）有损压缩编码种类预测编码，DPCM ,运动补 偿；频率域方法：正交变换编码（如DCT）,子带编 码；空间域方法：统计分块编码；模型方法：分形编码，模型基编码;基于重要性：滤波，子采样，比特分配,向量量化；（3）混合编码。有JBIG , H261, JPEG , MPEG等技术标准。本实验主要利用MATLAB程序进行离散余弦变换（DCT）压缩和游程编码(Run Length Encoding , RLE )。1）离散余弦变换（DCT）图像压缩原理离散余弦变换DCT在图像压缩中具有广泛的应用，它是JPEG、MPEG等数据压缩标准的重要数学基础。和相同图像质量的其他常用文件格式

10、（如GIF （可交换的图像文件格式）,TIFF（标签图 像文件格式），PCX（图形文件格式）相比，JPEG是目前静态 图像中压缩比最高的。JPEG比其他几种压缩比要高得多，而 图像质量都差不多（JPEG处理的图像只有真彩图和灰度 图）o正是由于其高压缩比，使得JPEG被广泛地应用于多媒体和网络程序中。JPEG有几种模式，其中最常用的是基于DCT变换的顺序型模式，又称为基本系统侣aseline)o用DCT压缩图像的过程为: 首先将输入图像分解为8X8或16X 16的块，然后对每个子块进行二维DCT 变换。(2)将变换后得到的量化的DCT系数进行编码和传送， 形成压缩后的图像格 式。用DCT解压的

11、过程为：(1) 对每个8X8或16X 16块进行二维DCT反变换。(2) 将反变换的矩阵的块合成一个单一的图像。余弦变换 具有把高度相关数据能量集中的趋势，DCT变换后矩阵的能量集中在矩阵的左上角，右下的大多数 的DCT系数值非常接近于0。对于通常的图像来说，舍弃这 些接近于0的DCT的系数值，并不会对重构图像的画面质量 带来显著的下降。所以，利用DCT变换进行图像压缩可以节 约大量的存储空间。压缩应该在最合理地近似原图像的情况下 使用最少的系数。使用系数 的多少也决定了压缩比的大小。在压缩过程的第2步中，可以合理地舍弃一些系数，从而 得到压缩的目的。在压缩过程的第2步，还可以采用RLE 和H

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