冈萨雷斯版_图像压缩

1、图像压缩图像压缩北京理工大学北京理工大学 光电学院光电学院王岭雪王岭雪 BMP格式格式 203KB (560*368) JPEG格式格式 23.5K图像压缩图像压缩 image compression图像大小：图像大小： 576 * 720持续时间：持续时间：15秒秒文件大小：文件大小：1.4M字节字节无压缩时：无压缩时：576*720*2*25*15300M字节字节三种数据冗余三种数据冗余1. 编码冗余编码冗余2. 空间和时间冗余空间和时间冗余3. 不相关的信息（心理视觉冗余）不相关的信息（心理视觉冗余）编码冗余编码冗余 编码冗余编码冗余- 不考虑灰度级出现的次数，给每个灰度级都采用不考虑灰

2、度级出现的次数，给每个灰度级都采用相同位相同位(比特比特)数的存储空间所带来的数据冗余。数的存储空间所带来的数据冗余。如：如： 8位位BMP灰度图像灰度图像 8位位- 解决办法：变长编码，出现概率大的灰度级解决办法：变长编码，出现概率大的灰度级 尽尽量少的位数。量少的位数。 计算计算Code 2的平均码长的平均码长Lavg压缩率压缩率CR 冗余度冗余度RD定义为定义为压缩率压缩率CR = 源代码长度源代码长度压缩后代码长度压缩后代码长度RDCR11空间和时间冗余空间和时间冗余 变长编码减少对像素进行统一长度的编码变长编码减少对像素进行统一长度的编码(自然二进自然二进制编码制编码)带来的编码冗余

3、，但没有考虑到像素之间的带来的编码冗余，但没有考虑到像素之间的相关性相关性空间和时间空间和时间冗余：冗余：空间冗余、空间冗余、帧间冗余、帧间冗余、几何冗余几何冗余行行程程编编码码传真图像的行程编码举例传真图像的行程编码举例心理视觉冗余心理视觉冗余 对视觉处理过程不重要的信息，如人眼无法区分的对视觉处理过程不重要的信息，如人眼无法区分的高频信息高频信息 在不影响视觉感知的前提下，除去人眼无法区分的在不影响视觉感知的前提下，除去人眼无法区分的高频信息，适当减少灰度级高频信息，适当减少灰度级(量化量化)IGS编码编码1)用当前的用当前的8位灰度级值加上前面和的灰度级值低位灰度级值加上前面和的灰度级值

4、低4位，位，并将并将4个最高有效位作为个最高有效位作为IGS的编码值；的编码值；2)如果当前值的如果当前值的4位最高有效位为位最高有效位为1111，则用，则用0000与之与之相加。相加。保真度准则保真度准则1) 客观评价：客观评价： 原图像定义为原图像定义为f(x,y)，压缩图像为，压缩图像为 ，均方，均方根误差根误差 erms为为圴方信噪比圴方信噪比1010210102ms),(),(),(SNRMxNyMxNyyxfyxfyxf),(yxf2) 主观评价主观评价2110102rms),(),(1MxNyyxfyxfMNe电视图像的等级量表电视图像的等级量表图像压缩系统的模型图像压缩系统的模

5、型1. 图像图像f(x,y)输入到编码器输入到编码器(Encoder)中，编码器可以根中，编码器可以根据输入数据生成一组符号据输入数据生成一组符号2. 通过信道通过信道(Channel)进行传输进行传输3. 编码后的表达符号送入解码器编码后的表达符号送入解码器(Decoder)，经过重构，经过重构就生成了输出图像就生成了输出图像),(yxf 某个事件某个事件x的的信息量信息量I用事件发生概率用事件发生概率p(x)的倒数的对数表示的倒数的对数表示中国举重队夺得奥运冠军！中国举重队夺得奥运冠军！中国男子足球队勇夺奥运冠军！中国男子足球队勇夺奥运冠军！信息量与熵信息量与熵(Entropy)(log)

6、(1log)(xpxpxI 能够产生信息的事物称为能够产生信息的事物称为信源信源 若信源若信源X产生的信息是产生的信息是x1, xn, 出现概率分别为出现概率分别为p1, pn, 信源信源X的平均信息量为的平均信息量为iniiiniippxIpXHlog)()(00信源信源X的熵的熵 对数以对数以2底时，信息量表示记录信息所用的最小位底时，信息量表示记录信息所用的最小位数数 设一图像的灰度级集合为设一图像的灰度级集合为(W1,W2,WM)，出现概率分别，出现概率分别为为p1, p2pM，图像熵定义为，图像熵定义为MkkkppH12log 描述：描述：1) 熵总是非负的熵总是非负的2) 当所有像

7、素出现的概率相等时，熵取到最大当所有像素出现的概率相等时，熵取到最大 3) 对数以对数以2底，熵的单位是：位底，熵的单位是：位/像素像素 物理意义：物理意义：表示对各灰度级编码时的所需位数的统计平均值表示对各灰度级编码时的所需位数的统计平均值图像熵图像熵平均码字长度平均码字长度 设设 k为数字图像第为数字图像第k个码字个码字Ck的长度的长度(二进制二进制代码的位数代码的位数)，该码字的出现概率为，该码字的出现概率为pk，则，则平均码字长度平均码字长度R定义为定义为bit1MkkkpR 最佳编码的定义：使平均码字长度尽量接近图像熵，最佳编码的定义：使平均码字长度尽量接近图像熵，既不丢失信息，又占

8、用最小的位数既不丢失信息，又占用最小的位数压缩率压缩率CR 冗余度冗余度RD定义为定义为压缩率压缩率CR = 源代码长度源代码长度压缩后代码长度压缩后代码长度RDCR11编码效率编码效率 H为熵，为熵，l为平均码长为平均码长 如果编码效率如果编码效率 100%，说明有冗余度，说明有冗余度%100lH42. 205. 0log05. 010. 0log10. 015. 0log15. 020. 0log20. 025. 0log25. 025. 0log25. 0log)(222222612kkkppXH例子例子 一个信源一个信源X的霍夫曼编码表为右表，计的霍夫曼编码表为右表，计算其信源的熵、平

9、均码长、编码效率：算其信源的熵、平均码长、编码效率：码字码字 信息信息概率概率01u10.2510u20.2511u30.20000u40.150010 u50.100011 u60.05熵熵平均码长平均码长45. 210. 0415. 0320. 0225. 0225. 02)(61kkkpXR编码效率编码效率%8 .98%10045. 242. 2%100)()(XRXH计算图像的熵计算图像的熵 (P348例例8.10) 一阶估计的信源熵一阶估计的信源熵灰度级灰度级 二阶估计的信源熵二阶估计的信源熵灰度级对灰度级对数据压缩的分类数据压缩的分类 按数学理论和计算方法分类：按数学理论和计算方法

10、分类：统计编码统计编码(Statistical Coding)、预测编码、预测编码(Predictive Coding)、变换编码变换编码(Transform Coding) 按压缩过程的可逆性分类：按压缩过程的可逆性分类：1) 无误差压缩：无误差压缩： 去除原数据中的重复和冗余部分，不丢失任何有用信息去除原数据中的重复和冗余部分，不丢失任何有用信息 还原后与压缩前的原数据完全一致，又称无失真编码还原后与压缩前的原数据完全一致，又称无失真编码 主要用于文本、程序文件，不允许出现任何数据失真主要用于文本、程序文件，不允许出现任何数据失真2) 有误差压缩：有误差压缩： 不可逆，损失部分信息，又称率

11、失真编码或限失真编码不可逆，损失部分信息，又称率失真编码或限失真编码 丢弃信息造成的失真应限制在规定范围内丢弃信息造成的失真应限制在规定范围内 主要用于图像和语音数据的压缩主要用于图像和语音数据的压缩无误差压缩之一：变长编码无误差压缩之一：变长编码 码字长度是变化的、不均匀的码字长度是变化的、不均匀的 出现概率较大的信源符号出现概率较大的信源符号 较短的字长较短的字长 出现概率小的信源符号出现概率小的信源符号 较长的字长较长的字长霍夫曼霍夫曼(Huffman)编码编码 Huffman编码完全依据信源字符出现的编码完全依据信源字符出现的概率进行编码概率进行编码 Huffman编码有时也称为最佳编

12、码编码有时也称为最佳编码Huffman编码用不同码字代表编码用不同码字代表不同灰度，并非量化灰度值不同灰度，并非量化灰度值首先，将信源符号按出现频率由大到小排列首先，将信源符号按出现频率由大到小排列符号a2a6a1a4a3a5出现概率0.40.30.10.10.060.04将最小的两个概率组合相加，并继续该步骤，将最小的两个概率组合相加，并继续该步骤，直到概率为直到概率为1第一步 0.40.30.10.10.1符号 a2a6a1a4a3a5出现概率 0.40.30.10.10.060.04第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.06

13、0.04第二步0.40.30.20.1 在相加的过程中，始终将较高的概率在相加的过程中，始终将较高的概率分支放在上部分支放在上部第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.00第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.0

14、60.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.0001每对组合的上边指定每对组合的上边指定为为0，下边指定为，下边指定为101010101第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101画出每个信源符号到达概率画出每个信源符号到达概率1.00处处的路径，记下遇到的各个的路径，记下遇到的各个1和和0a2=1第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0

15、.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101a6=00第一步0.40.30.10.10.1符号a2a6a1a4a3a5出现概率 0.40.30.10.10.060.04第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第五步1.000101010101a2=1a6=00a1=011a4=0100a3=01010a5=010111) 计算平均码长和编码效率计算平均码长和编码效率2) 对字符串对字符串010100111100进行解码进行解码Huffman编码是可唯一解码的编码是

16、可唯一解码的算术编码算术编码(Arithmetics Encoding, AE) 用一个算术码字来代替一个符号序列用一个算术码字来代替一个符号序列1) 算术编码没有延用一般数据编码技术中用一个特算术编码没有延用一般数据编码技术中用一个特定的码字代替一个输入符号的做法定的码字代替一个输入符号的做法2) 将要压缩的整段数据映射到实数半开区间将要压缩的整段数据映射到实数半开区间0,1)3) 构成大于等于构成大于等于0且小于且小于1的数值的数值4) 这些数值作为唯一可译代码这些数值作为唯一可译代码5) 源符号和码字间的一一对应关系并不存在，而是源符号和码字间的一一对应关系并不存在，而是用一个算术码字来

17、代替一个符号序列用一个算术码字来代替一个符号序列算法模型算法模型 设信源数据流为设信源数据流为“XYYZ”，出现概率和设定的取，出现概率和设定的取值范围为值范围为字符字符空格空格XYZ概概 率率0.20.20.40.2赋值范围赋值范围 0.0, 0.2 0.2, 0.4 0.4, 0.8 0.8, 1.0 ) 以上赋值范围按出现次序划分，将符号划分到哪个以上赋值范围按出现次序划分，将符号划分到哪个区间，对编码并无影响。区间，对编码并无影响。 如果信源数据流的第一个字符为如果信源数据流的第一个字符为X，已知其取值范，已知其取值范围为围为0.20.4，这确定了代码最高有效位取值的范，这确定了代码最

18、高有效位取值的范围围 后续每读入一个新符号，输出代码的数值范围将进后续每读入一个新符号，输出代码的数值范围将进一步缩小一步缩小 前一个字符编码的上、下限记为前一个字符编码的上、下限记为HIGH和和LOW，RANGE表示表示HIGH与与LOW之差，则之差，则新输入符号的新输入符号的上、下限上、下限计算公式：计算公式： HIGH= LOW + RANGEHIGH_RANCE(CHAR) LOW = LOW + RANGELOW_RANCE(CHAR)新输入符号当前的上、下限新输入符号当前的上、下限前一个符号的下限前一个符号的下限前一个符号上下限之差前一个符号上下限之差 对于数据流对于数据流“XYYZ” HIGH= LOW + RANGEHIGH_RANCE(CHAR) LOW = LOW + RANGELOW_RANCE(CHAR)输入字符输入字符X 0.2, 0.4 Y 0.4, 0.8 空格空格 0.0, 0.2 Z 0.8, 1.0 )LOW0.20.280.280.