压缩技术实验编码实验一统计编码实验目的1.熟悉统计编码的原理2.掌握r元Huffman编码的方法；3.了解Huffman编码效率及冗余度的计算;二、实验原理霍夫曼编码，又称最佳编码，根据字符出现概率来构造平均长度最短的变长编码。
Huffman编码步骤：(1)把信源符号x i(i=1,2,…按出现概率的值由大到小的顺序排列；(2)对两个概率最小的符号分别分配以“ 0和“ 1,'然后把这两个概率相加作为一个新的辅助符号的概率；(3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列；⑷跳到第2步，直到出现概率相加为1为止；(5)用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号；(6)从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“ 0或“ 1顺序排列起来，就是端点所对应的信源符号的码字。
以上是二元霍夫曼编码。
如果是r元霍夫曼编码，则应该如何做呢？在HUFFMAN 编码方案中，为出现概率较小的信源输出分配较长的码字，而对那些出现可能性较大的信源输出分配较短的码字。
为此，首先将r 个最小可能的信源输出合并成为一个新的输出，该输出的概率就是上述的r 个输出的概率之和。
重复进行该过程直到只剩下一个输出为止。
信源符号的个数q 与r 必须满足如下的关系式：q = (r-1) n + r n 为整数如果不满足上述关系式，可通过添加概率为零的信源符号来满足。
这样就生成了一个树，从该树的根节点出发并将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 码，求出码子的平均长度与编码效率。
注：因为是 码字的平均长度L=2 X 0.1+1 X 0.3+3 X 0.05+3 X 0.09+2 X0.21+1 X 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 实现该编码的方法可用下面的矩阵来说明：20 U 1 0.1① 0.3② 0.3⑤0.3⑤0.3③ 0.45 ①11 U 20.3② 0.25 ⑥0.25 ④ 0.25④ 0.25②0.3③211U 3 0.05 ③ 0.21 ⑤ 0.21 ③ 0.21 ③ 0.45 ① 0.25②20 til 0. 1 0.3 1 u20.30. 25 211u3 0. 05 0.21 川ul 0. 09 0. 1 22 u50.21a 090 u6 ().25 a 05*0.3 *0.25 *0. 21 *0. 14養0. 1 —-3元编码，所以每次3个概率值相加。
0.45 0.3 ・ 0.212 U4 0.09 ④0.1①0.1②0.14①22 U5 0.21 ⑤0.09 ④0.14 ①0.1②0 U6 0.25⑥0.05 ③0.⑦0⑦注：每次3个数加完后，重新按序分配编号，在按概率 值重新排序，再进行下次加数注：m 中每一行为按概率值重新排序后的编号列，一共 三次概率值排序；单箭头表示两次排序中的概率值并未 参加加数，未改变；多箭头表示箭头所指向的多项概率 值相加后得到箭头源的概率值。
注：c 为编码矩阵，从最后一行开始，因为是 3元编码, 故按0、1、2开始编码。
根据m 中的箭头，单箭头不变, 多箭头根据箭头源每上一层则箭头源编码后再加一位， 同一层中加的位数按 0、1、2顺序添加。
m 矩阵第I (1>1 )行中的‘ 1'记录了合并后的信源符号在新信源中的位置实验步骤1. 输入初始概率分布p 和码元数r ;2. 检查是否满足q = (n-1)r + r (q 为输入信源的个 数)，如果不满足则补零使之满足；3.排序得m 矩阵c=7m= 222 0 0211 12 20 2 0 120 222104．根据m 矩阵获得c 矩阵5．从c 矩阵中取出最后的码字矩阵h 并计算平均码长和编码效率。
四、实验仪器1计算机；2MATLAB 程序；3移动式存储器（软盘、U 盘等）；4记录用的笔、纸。
五、实验报告内容1、实验目的2、实验要求3、实验环境4、实验内容（叙述操作过程，提交主要程序段）5、实验结论6、实验总结六、思考题1 什么是霍夫曼编码？在Matlab 中如何实现？2 r 元霍夫曼编码的原理和过程？实验二量化与变换编码一、实验目的1．理解有损压缩和无损压缩的概念；2．理解图像压缩的主要原则和目的；3. 掌握DCT 编码的原理4.了解游程编码的原理二、实验原理1.图像压缩原理图像压缩主要目的是为了节省存储空间，增加传输速度。
图像压缩的理想标准是信息丢失最少，压缩比例最大。
不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。
压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。
信息的冗余量有许多种，如空间冗余，时间冗余，结构冗余，知识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。
高效编码的主要方法是尽可能去除图像中的冗余成分，从而以最小的码元包含最大的图像信息。
编码压缩方法有许多种，从不同的角度出发有不同的分类方法，从信息论角度出发可分为两大类。
（1）冗余度压缩方法，也称无损压缩、信息保持编码或嫡编码。
具体说就是解码图像和压缩编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。
（2）信息量压缩方法，也称有损压缩、失真度编码或烟压缩编码。
也就是说解码图像和原始图像是有差别的，允许有一定的失真。
应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3 类：（1）无损压缩编码种类哈夫曼（Huffman ）编码，算术编码，游程（RLE ）编码，Lempel zev 编码。
（2）有损压缩编码种类预测编码，DPCM ，运动补偿；频率域方法：正交变换编码（如DCT），子带编码；空间域方法：统计分块编码；模型方法：分形编码，模型基编码；基于重要性：滤波，子采样，比特分配，向量量化；（3）混合编码。
有JBIG ，H261，JPEG ，MPEG 等技术标准。
本实验主要利用MATLAB 程序进行离散余弦变换（DCT ）压缩和游程编码（Run Length Encoding ，RLE ）。
1）离散余弦变换（DCT）图像压缩原理离散余弦变换DCT 在图像压缩中具有广泛的应用，它是JPEG 、MPEG 等数据压缩标准的重要数学基础。
和相同图像质量的其他常用文件格式（如GIF（可交换的图像文件格式），TIFF（标签图像文件格式），PCX （图形文件格式））相比，JPEG是目前静态图像中压缩比最高的。
JPEG 比其他几种压缩比要高得多，而图像质量都差不多(JPEG 处理的图像只有真彩图和灰度图)。
正是由于其高压缩比，使得JPEG 被广泛地应用于多媒体和网络程序中。
JPEG有几种模式，其中最常用的是基于DCT 变换的顺序型模式，又称为基本系统(Baseline)。
用DCT 压缩图像的过程为：(1)首先将输入图像分解为8X 8或16X 16的块，然后对每个子块进行二维DCT变换。
(2)将变换后得到的量化的DCT 系数进行编码和传送，形成压缩后的图像格式。
用DCT 解压的过程为：(1)对每个8X 8或16X 16块进行二维DCT反变换。
(2)将反变换的矩阵的块合成一个单一的图像。
余弦变换具有把高度相关数据能量集中的趋势，DCT 变换后矩阵的能量集中在矩阵的左上角，右下的大多数的DCT 系数值非常接近于0。
对于通常的图像来说，舍弃这些接近于0 的DCT 的系数值，并不会对重构图像的画面质量带来显著的下降。
所以，利用DCT 变换进行图像压缩可以节约大量的存储空间。
压缩应该在最合理地近似原图像的情况下使用最少的系数。
使用系数的多少也决定了压缩比的大小。
在压缩过程的第2 步中，可以合理地舍弃一些系数，从而得到压缩的目的。
在压缩过程的第2 步，还可以采用RLE 和Huffman 编码来进一步压缩。
2）游程编码（RLE原理：例如如下这幅的二值图像，如果采用游程编码可以按如下格式保存其中10 和8 表示图像的宽和高。
在这个小例子中游程编码并没有起到压缩图像的作用。
这是由于这个图的尺寸过小，当图像尺寸较大时游程编码还是不错的无损压缩方法。
对于灰度图像和二值图像，用游程编码—般都有很高的压缩率。
游程编码方法实现起来很容易，对于具有长重复值的串的压缩编码很有效，例如：对于有大面积的阴影或颜色相同的图像，使用这种方法压缩效果很好。
很多位图文件格式都采用游程编码，如TIFF，PCX GEM BMF等。
三、实验步骤1打开计算机，启动MATLAB 程序；2调入数字图像，并进行数据的游程（RLE ）编码压缩处理；3将原图像在Photoshop 软件中打开，分别以不同的位图文件格式进行“另保存” ，比较它们的数据量。
4记录和整理实验报告四、实验仪器1计算机；2MATLAB 、Photoshop 等程序；3移动式存储器（软盘、U 盘等）。
4记录用的笔、纸。
五、实验报告内容1 叙述实验过程；2 提交实验的原始图像和结果图像。
六、思考题1．图像中哪些信息是主要的，哪些信息是次要的？2．简述离散余弦变换（DCT ）的原理。