文档介绍：第十七章第十七章
图像压缩图像压缩
本章概述本章概述
无损压缩技术无损压缩技术
有损编码有损编码
变换编码变换编码
压缩标准压缩标准
数据性质数据性质::
冗余性
不相干性
数据压缩数据压缩:(:(如下图如下图))
压缩类型压缩类型删除内容删除内容恢复程度恢复程度
无损压缩冗余信息精确恢复
有损压缩
22..不相干信
息
无损压缩技术无损压缩技术
基于字典技术基于字典技术
基于统计技术基于统计技术
无损压缩无损压缩--------基于字典技术基于字典技术
行程编码行程编码((RLE)(RunRLE)(Run--LengthLength Encoding)Encoding) ::
只存一个灰度值码,后面为行程长度只存一个灰度值码,后面为行程长度
方式:方式: ①①灰度值灰度值++个数;个数;②②灰度值灰度值++终止列终止列
数。数。
例如:例如: PCXPCX格式格式
无损压缩无损压缩--------基于字典技术基于字典技术
LZWLZW编码:编码:
当表中没有的字符串头一次出现的时候,将当表中没有的字符串头一次出现的时候,将
这个字符串和分配给它的代码同时保存,以这个字符串和分配给它的代码同时保存,以
后该串再次出现时就只存储它的代码。后该串再次出现时就只存储它的代码。
特点:字符串表在压缩中动态生成,不必存特点:字符串表在压缩中动态生成,不必存
在压缩文件里,它可由解压缩算法来重构在压缩文件里,它可由解压缩算法来重构,,降降
低了文件的冗余信息。低了文件的冗余信息。
例如:例如:GIFGIF。。
无损压缩无损压缩--------基于统计技术基于统计技术
消息源出现概率为消息源
消息源{}a 出现概率 p(akk ),=− 1,2,..., K 1, K为消息源
的总数量。的总数量。k
ShannonShannon信息度量标准:信息度量标准:
信息信息a 出现几率的度量为出现几率的度量为。。
k IK=−−1 log[pa (k )]
消息源的熵消息源的熵 H==− EIa{(kkk )}∑ pa ( )log[( pa )]。。
k =0
冗余量冗余量= kw )}({ − HaLER 。。
若若 aL kw = − ap k )](log[)( ,则该编码给予了无损压缩,则该编码给予了无损压缩
字长下限。字长下限。
如如:: aL kw = − 2 ap k )]([log)( ,对二进制编码而言该编码,对二进制编码而言该编码
给予了无损压缩字长下限。给予了无损压缩字长下限。
无损压缩无损压缩--------基于统计技术基于统计技术
哈夫曼编码哈夫曼编码(Huffman(Huffman coding):coding):
是一种无损的统计编码方法是一种无损的统计编码方法,,它用变长的码来使它用变长的码来使
冗余量达到最小。冗余量达到最小。
静态哈夫曼编码静态哈夫曼编码::使用一棵在压缩之前就建好的使用一棵在压缩之前就建好的
编码树,它是根据可能的字符出现的概率表来编码树,它是根据可能的字符出现的概率表来
生成的。生成的。
动态哈夫曼编码动态哈夫曼编码::是在编码过程中建立它的编码是在编码过程中建立它的编码
树。树。
HuffmanHuffman编码属于信息保持编码,又叫做熵保存编码属于信息保持编码,又叫做熵保存
编码,或者叫熵编码。编码,或者叫熵编码。
无损压缩无损压缩--------基于统计技术基于统计技术
HuffmanHuffman编码的具体算法编码的具体算法::
将原数据按照概率大小排列;
取两个最小概率所对应的符号为叶结点,(概率较小者
为左结点,概率较大者为右结点)由此构造其父结点,
父结点的概率等于二者的概率之和;
将新生成的结点按照概率大小插入结点中;
重复2-3直到所有结点全部插入到结点表中;
设所有的结点左结点为0,右结点为1,从根结点开始经
中间结点到达叶结点,其路径代码即是该结点的
Huffman编码。
HuffmanHuffman编码实例编码实例::
信源符 a1a1 a2a2 a3a3 a4a4 a5a5 a6a6
号集
概率概率
编码后编码后::
a1a1 a2a2 a3a3 a4a4 a5a5