《图像压缩与编码-20150522》由会员分享，可在线阅读，更多相关《图像压缩与编码-20150522（41页珍藏版）》请在金锄头文库上搜索。
1、图像压缩与编码图像压缩与编码王静远王静远 信息论中的通信过程信息论中的通信过程越编越小越编越大数模转换信息论信息论中的通信过程中的通信过程信源编码：有效性 压缩、扰乱、加密、力求用最小的数目传输最 大的信息信道编码：可靠性 尽量在传输过程中不出错或少出错。图像编码属于信源编码范畴图像编码图像编码信息压缩信息压缩信息压缩技术的起源 比计算机的发明早几千年信息量信息量信息蕴含于不确定性不确定性中，获取信息可以消 除不确定性。 明天太阳从东边升起（100%确定） 投出的硬币是正面（50%确定）信息量：对信息的度量 消除不确定性所需要的数据量。信息量信息量一条消息的信息量：“抛出的硬币是正面” 正面是
2、2种不确定的状态种不确定的状态之一 想要表达这2种不确定性状态，需要的二进制字 段长度为 “抛出的硬币是正面”的信息量是1比特 比特（log2）、奈特（ln）、哈特（lg）log22 = - log2(1/2) = 1 bit信息量信息量信源中信源中每条消息的信息量 每次抛出硬币，正面和反面的概率均为50%抛出硬币是正面，获得信息量： Eh = - log2(1/2)抛出硬币是反面，获得信息量： Eh = - log2(1/2)H= 0.5*Eh+ 0.5*Et = 0.5*- log2(0.5)+ 0.5*- log2(0.5) = 0.5 * 1 + 0.5 * 1 = 1比特比特每次抛硬
3、币的 平均信息量：信息量信息量如果硬币的形状比较奇特正面：0.25 反面：0.25 立起来：0.5E1= log23 =-log2(1/3) E2 = log23 =-log2(1/3) E2= log23 =-log2(1/3)H= 0.25 E1+ 0.25 E2+ 0.5 E3正面出现的概率是0.25，根据单个消息信息量的定义，抛出一个正面只消除了1/4的不确定性，并不是消除了1/3的不确定性。这条消息的信息量为E1= log24 =-log2(1/4)信息量信息量正确的计算方法正面：0.25 反面：0.25 立起来：0.5E1= log24 =-log2(1/4) E2 = log24
4、 =-log2(1/4) E2= log22 =-log2(1/2)H= 0.25 E1+ 0.25 E2+ 0.5 E3 = 0.25 -log20.25 + 0.25 -log20.25 + 0.5 -log20.5 = 0.25 *2 + 0.25 *2 + 0.5 *1 = 1.5 = p1-log2(p1) + p2-log2 (p2) + p3-log2 (p3)信息熵信息熵熵熵来源于来源于40年代由年代由Claude Shannon创立的信息论中的一条创立的信息论中的一条 定理，这一定理借用了热力学中的名词“熵”定理，这一定理借用了热力学中的名词“熵”( Entropy )来表来
5、表 示一条信息中真正需要编码的信息量：示一条信息中真正需要编码的信息量：使用二进制码为为含有n个符号的某条某条信息（信源）信息（信源）进行编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的自信息量自信息量表示为： En= -log2(Pn)那么，整条信息（信源）整条信息（信源）的平均平均自信息量（熵）自信息量（熵）表示为：H = Pn En= Pn -log2(Pn)熵的本质：对信源中一个符号进行编码需要的最小字节数信息熵信息熵自信息量的特点 概率越小的事件信息量越大 告知小概率事件的消息消除的不确定性更大 “太阳从东方升起”的熵是多大？En= -log2(Pn)日出东方：1 日出
6、西方：0 日出南方：0 日出北方：0Ee= log21 = 0 Ew= log20 =NaN Es= log20 = NaN En= log20 = NaNH= p1log2p1 = 1*log2p1= 0信息熵信息熵信息熵（信源平均自信息量）的特点 状态出现的概率越平均熵越大 越随机的系统不确定性越大（谁都有可能）H = Pn En= Pn -log2(Pn)正正，反反 = 0.9, 0.1 H = 0.9*-log0.9 + 0.1-log0.1= 0.136 + 0.332 = 0.468正正，反反 = 0.5, 0.5 H = 0.5*-log0.5 + 0.5-log0.5= 0.5
7、 + 0.5 = 1均匀分布的 信源熵最大信源信源编码编码由N个符号构成的无记忆性信源其中符号uk出现的概率为pk 对符号进行编码的字母集合例如：ABCADCBAE 信源符号序列010101100101 码字符号序列信源编码信源编码的效率信源编码的效率信源的熵： 平均码长：Ni是符号ui的码长 每个码字含有的熵： 编码极限：码字序列熵上的限为 即等概率码字序列生成一个符号等概率分布的新信源ABCADCBAE 信源符号序列010101100101 码字符号序列信源编码真实的 码字平均熵码字平均熵 的上限信源编码的效率信源编码的效率编码效率：冗余度：真实的 码字平均熵码字平均熵 的上限定定长信源编
8、码（十进制）长信源编码（十进制）信源符号和字母集合编码： 信源的熵：平均码长：效率：u0=0, u1=1, u2=2, u3=3 = 7/4 (比特/符号) =1(0.5+0.25+0.125+0.125) = 1定定长信源编码（二进制）长信源编码（二进制）信源符号和字母集合编码： 信源的熵：平均码长：效率：u0=00, u1=01, u2=10, u3=11 = 7/4 (比特/符号) =2(0.5+0.25+0.125+0.125) = 2变变长信源编码长信源编码基本思想：将常用的符号用较短的码字表达u0=00, u1=01, u2=10, u3=11 u0=0, u1=10, u2=11
9、0, u3=111 等长：没有考虑概率变长：考虑了概率分布变变长信源编码长信源编码信源符号和字母集合编码： 信源的熵：平均码长：效率：u0=0, u1=10, u2=110, u3=111 = 7/4 (比特/符号)=10.5+20.25+2(0.125+0.125) = 7/4变长信源编码变长信源编码效率：u0=0, u1=10, u2=110, u3=111 编码后的序列中： 0的数量 = 0.51 + 0.251 + 0.1251 + 0.1250 = 0.875 1的数量 = 0.50 + 0.251 + 0.1252 + 0.1253 = 0.875 u0u1u2u3编码后单位bit
10、的熵为1，即达到了效率上限变长信源编码变长信源编码问题：变长编码能够提高编码效率，是统 计编码的重要方法，如何识别编码是关键。编码基本限制： 单一性：一个有限长的码字序列只有唯一的分 割方法 非续长性：任意编码不是其它编码的前缀。u0=0,u1=10, u2=110,u3=111 哈夫曼编码哈夫曼编码编码方法 (1)信源X中的消息按概率大小排序。 (2)将概率最小的两个消息合并成一个新消息， 新消息的概率为原消息概率之和。 (3)对新消息进行重新排序 (4)重复(1)-(3)直到信源为X1。 (5)对合并的消息分别赋予0和1。 (6)从X1到原始信源的0和1序列即为信源编码。哈夫曼编码哈夫曼编
11、码(1)信源X中的消息按概率大小排序。 (2)将概率最小的两个消息合并成一个新消息，新消息的概率为原消息概率之和。 (3)对新消息进行重新排序0.150.30.5510.45u0u1u2u3u4u5110010101011 01 10 001 0001 0000哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码是最优编码11 01 10 001 0001 0000熵：H = p -log2(p) = 2.42322平均码长：N= p N = 2.45编码效率：98.9%编码后的序列中： 1的数量 = 0.252+0.251+0.21+0.151+0.11+0.050=1.2 0的数量 = 0.
12、250+0.251+0.21+0.152+0.13+0.054=1.25香农香农编码编码编码方法 (1)信源X中的消息按概率大小排序。 (2)按概率排序分为两组，并且满足如下条件： (3)对分组消息分别赋予1和0。 (4)重复(1)-(3)直到信源为X1。 (5)从X1到原始信源的0和1序列即为信源编码。香农编码香农编码香农编码香农编码0 10 1100 1101 1110 1111熵：H = p -log2(p) = 2.14平均码长：N= p N = 2.2编码效率：97.4%编码后的序列中： 1的数量 = 1.14 0的数量 = 1.06香农编码香农编码0.40.60.20.10.060
13、.04预测编码预测编码无记忆信源无记忆信源，符号之间的没有相关性的信源。 统计编码：统计编码：利用符号出现概率的不均等性。有有记忆信源记忆信源，符号之间的有相关性的信源。 预测编码：预测编码：利用符号之间的相关关系。预测编码预测编码预测编码的思想： 信源 n0.nN，为0, 100之间的分布 如果：连续两个符号之间的差小于5 设ek= nknk-1，则ek为-5, 5之间的分布 预测编码：对ek进行编码 信源不确定性从101个符号变为了11个符号预测编码预测编码预测编码的基本原理图像图像编码的技术手段编码的技术手段PCM编码 预测编码 统计编码 正交变换编码 运动检测技术 其它编码 静态图像压
14、缩与动态图像压缩标准均方根误差均方根误差输入图像f(x,y)、输出图g(x,y) 误差 均方误差：均方根误差：均方根信噪比均方根信噪比输入图像f(x,y)、输出图像g(x,y) 噪声n(x,y) ： 均方信噪比：均方根信噪比：D. A. Huffman1952 年发表论文：“最小冗余度代码的构造方法” A Method for the Construction of Minimum Redundancy CodesUNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是Huffman 0 阶自适应编码的具体实现80 年代初，Huffman 编码又在CP/M 和DOS 系统中实现，
15、其代表程序叫SQHuffman时代：时代：60 年代年代、70 年代乃至年代乃至80 年代的早期年代的早期历史综述历史综述 1843年莫尔斯最早的电报码的变长压缩。 1938年里夫斯：脉冲编码调制器（PCM）。 1939年达德利通道声码器：语音压缩系统。 1946年德劳雷恩：增量编码调制器（M） 1948年信息率失真函数。 19 5 2年卡特勒：差分脉冲编码调制器（DPCM） 1952年霍夫曼：最优变长码的构造。 1965年安德鲁斯：二维离散傅立叶变换 沃尔什-哈达码变换、斜变换、KL变换、离散余弦变换 1984年法国数学家Morlet ：小波变换 1988年曼德尔勃罗特：分形压缩技术的分类压缩技术的应用谢谢大家
