数字图像处理北京大学计算机研究所 陈晓鸥第四章 图像压缩
4.1 图像压缩的基本概念
4.2 无损压缩
4.3 有损压缩
4.4 压缩标准第四章图像压缩第一节 图像压缩的基本概念
4.1.1 数据冗余
4.1.2 保真度标准
4.1.3 图像压缩模型第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
图像压缩的基本概念设,n1和 n2是在两个表达相同信息的数据集中,所携带的单位信息量 。
– 压缩率 （ 压缩比 ）,——描述压缩算法性能
CR = n1 / n2
其中,n1是压缩前的数据量,n2是压缩后的数据量
– 相对数据冗余,
RD = 1 – 1/CR
例,CR=20; RD = 19/20
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
三种数据冗余：
1,编码冗余
2,像素冗余
3,视觉心理冗余第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
1,编码冗余,
如果一个图像的灰度级编码,使用了多于实际需要的编码符号,就称该图像包含了编码冗余 。
例：如果用 8位表示该图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
2,像素冗余,
由于任何给定的像素值,原理上都可以通过它的邻居预测到,单个像素携带的信息相对是小的 。
对于一个图像,很多单个像素对视觉的贡献是冗余的 。 这是建立在对邻居值预测的基础上 。
例：原图像数据,234 223 231 238 235
压缩后数据,234 11 -8 -7 3
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
3,视觉心理冗余,
一些信息在一般视觉处理中比其它信息的相对重要程度要小,这种信息就被称为视觉心理冗余 。
第四章图像压缩第一节图像压缩基本概念
33K 15K
4.1.2 图像压缩基本概念,保真度标准
保真度标准 ——评价压缩算法的标准
1,客观保真度标准
2,主观保真度标准第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
1,客观保真度标准如果图像压缩过程对图像信息有所损失,
如何用数学形式,表述这种损失？
将信息损失的多少,表示为原始输入图像与压缩后又解压缩输出的图像的函数,这个函数就被称为 客观保真度标准 。 一般表示为：
e(x,y) = f(x,y) - f(x,y)
f(x,y)是输入图像,f(x,y) 是压缩后解压缩的图像,e(x,y)是误差函数第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
离散的描述形式：
两个图像之间的 总误差,
M-1 N-1?
[ f(x,y) - f(x,y)]
x=0 y=0
均方根误差 （ rms）
M-1 N-1?
erms = [1/MN [ f(x,y) - f(x,y)]2]1/2
x=0 y=0
第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
2,主观保真度标准通过视觉比较两个图像,给出一个定性的评价,如很粗,粗,稍粗,
相同,稍好,较好,很好,这种评价被称为 主观保真度标准 。
第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,图像压缩模型
图像压缩模型
1,图像传输环境中图像压缩模型
2,源数据编码与解码的模型第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
图像传输环境中图像压缩模型
– 源数据编码,完成原数据的压缩。
– 通 道 编 码,为了抗干扰，增加一些容错、校验位、
版权保护，实际上是增加冗余。
– 通 道,如 Internet、广播、通讯、可移动介质源数据编码通道编码 通道通道解码源数据解码第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
源数据编码与解码的模型
– 源数据编码的模型
– 源数据解码的模型符号解码器反向映射器映射器 量化器 符号编码器第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
源数据编码与解码的模型
– 映射器,减少像素冗余,如使用 RLE
编 码。或进行图像变换。
– 量化器,减少视觉心理冗余,仅用于有 损压缩。
– 符号编码器,减少编码冗余,如使用哈夫曼编码第四章图像压缩第一节图像压缩基本概念第二节 无损压缩
4.2.1 基于字典的压缩
4.2.2 统计编码
4.2.3 无损预测编码第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
基于字典的压缩
– RLE编码 ——行程编码
PCX
– LZW编码
GIF
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 概念：
行程,具有相同灰度值的像素序列 。
– 编码思想：
去除像素冗余 。
用行程的灰度和行程的长度代替行程本身 。
例：设重复次数为 iC,重复像素值为 iP
编码为,iCiP iCiP iCiP
编码前,aaaaaaabbbbbbcccccccc
编码后,7a6b8c
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 分析：
对于有大面积色块的图像,压缩效果很好
对于纷杂的图像,压缩效果不好,最坏情况下,
会加倍图像第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 例子,PCX_RLE
（ 1） PCX简介：
真彩色图像以行为单位,按色面存放
128字节的文件头图像数据调色板第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
（ 2） PCX_RLE编码原则：
1) 图像数据以 字节 为单位进行编码
2) 按行进行压缩
3) 长度在前,灰度值在后
4) 单像素没有长度值
5) 以最高两位作为判断是 重复数 还是 原像素 。
最高两位为 1,说明是重复数,否则,说明是原像素值第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
（ 2） PCX_RLE编码原则：
6) 重复像素长度 iC最大值为 26-1 = 63,如果遇到 iC
大于 63的情况,则分为小于 63的几段,分别处理 。
7) 如果遇到不重复的单个像素 P：
如果 P < 0xC0（ 192） 直接存入该像素值,
否则先存入长度 1,再存入像素值
（ 注,<1> 192-255之间的单像素图像不减反增
<2> 192-255之间,64个数高两位为 11）
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– （ 3） PCX_RLE的解码 （ 以解一行为例 ）
1) 读一个字节到 byChar
2) if ((byChar & 0xC0) == 0xC0) {
//判前两位是否全 1,C0 = 1100 0000
iCount = byChar & 0x3F；
//取出后 6位的重复数连续读 iCount个字节
}
else { 直接读下一个字节 }
3)重复 1),2)直到读完一行 。
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 背景：是 Lemple,Ziv提出,Welch充实
– 基本思想：去除像素冗余 。
(1) 在压缩过程中动态地形成一个字符序列表 (字典 )
(2) (a) 每当压缩扫描图像发现一个字典中没有的字符 序列,就把该字符序列存到字典中
(b) 并用字典的地址 （ 编码 ） 作为这个字符序列的代码,替换原图像中的字符序列
(c) 下次再碰到相同的字符序列,就用字典的地址第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 基本思想：
(3) 压缩的结果,除了压缩图像外,不需要保留压缩过程中形成的字典,而在解压缩时,临时恢复这个字典 。
– 问题：字符序列的长度如何确定？
字典的长度如何确定？
字典满了怎么办？
如何查字典？
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
字典中字符序列的长度,
字典中字符串的长度可能会很长,由于每一个字符串,
都是表中一个已经存在的字符串加上一个字符组成,所以可以把字符串以
<已有字符串索引 > + <字符 >
这样字典元素的长度统一为 12+8,20位 。
字典的长度,
对于以字节 （ 8位 ） 为压缩单元,如 ASCII码,字典的长度为 212 = 4096,索引的长度为 12位,字典的前 256个保存单个字符,剩下的 3840个的分配给压缩过程中出现的字符串 。
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
字典满了的解决办法,
在字典满了以后 （ 新字符串超过 4096）,输出一个清除字典的标记 LZW_CLEAR,清空字典,开始新的编码 。
查表的方法,
可通过 Hashing函数 （ 散列,杂凑 ） 的方法来减少 查表的次数 。
输出编码的时机,
发现新串时,输出前一个串的编码第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 例子,GIF和 TIFF都使用 LZW压缩法 。 下面以 GIF
为例进行介绍：
（ 1） GIF简介 （ 多图像,256色 ）
文件结构：
文件头信息：标识 （ GIF）,版本号屏幕描述,屏幕长,宽,背景色等全局调色板：长度 （ 256x3） //三个 256色的调色板第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
（ 1） GIF简介 （ 多图像,256色 ）
图 像 描 述：描述图像块在屏幕上的左上角位置及宽高 //可以有多个局部调色板,长度 （ 256x3） //三个 256色的调色板,每个图像可有一个图像数 据：用 LZW方式压缩,用 256字节的块来存放扩充块描述：有四种扩充块文件结尾,字符,；,
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码 文件头信息
LZW压缩图像数据全局调色板屏幕描述图像描述局部调色板扩充数据块第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码第四章图像压缩第二节无损压缩初始化字典输出清除标记 LZW_CLEAR
Temp = 空串
k = 从输入流中读一个字符是结尾标志吗？
把新串 Temp+k加到字典中
Temp = k
输出 Temp的编码输出结束标记
Temp+k在字典中吗？
是
Temp = Temp+k
输出 Temp的编码是
4.2.1 无损压缩,基于字典的压缩
– （ 2） GIF_LZW编码
InitializeStringTable(); //初始化串表
WriteCode(LZW_CLEAR); //输出清除标记
Temp = the empty string; //临时串变量置空
For 对输入流中每一个字符 { //扫描字符的循环
k = GetNextCharacter(); //读入一个新字符
if (temp + k 在串表中 ) { //判断,临时串变量 + 新字符,
是否在表中
temp = temp + k; //更新临时串变量
}
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
else {
WriteCode(CodeFromString(temp));
// 输出新临时串变量的编码
AddTableEntry(temp + k);
//把新字符串存到串表中
Temp = k; //用当前读入的字符更新临时
temp
}}
WriteCode(CodeFromString(temp));
// 输出新临时串变量的编码
WriteCode(LZW_EOI); // 输出结束标记第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩编码举例：设字符集 {a,b,c,d}，
串,aabdaadaa
压缩字典 临时串 输入串 编码
0 a T=temp + a
1 b T= a + a 0
2 c T= a + b 00
3 d T= b + d001
4 aa T= d + a0013
5 ab T= a + a
6 bd T= aa + d00134
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
（ 3） GIF_LZW解码
While ((Code = GetNextCode()) != LZW_EOI) {
If (Code = = LZW_CLEAR) { //判断是否是清除标记
InitializeStringTable(); //初始化串表
Code = GetNextCode(); //读入编码
If (Code != LZW_CLEAR) { //如果不是清除标记
WriteString(StringFromCode(Code));
//查串表输出字符
OldCode = Code; //保留当前编码
} }
else {
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
if (IsInTabel(Code) { //判编码是否已经在表中
WriteString(StringFromCode(Code)); //输出字符串
OldCode = Code; //保留当前编码
}
else { //不在串表中
OutString=
StringFromCode(OldCode)+
StringFromCode(GetLastChar(Code));
//新老组合解码
WriteString(OutString); //输出解码
AddStringToTable(OutString); //给串表加一项
OldCode = Code; //保留当前编码
}
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
统计编码
– 霍夫曼编码第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 1） 基本思想通过减少编码冗余来达到压缩的目的 。
1,基本思想是统计一下符号的出现概率,
2,建立一个概率统计表,
– 将最常出现 (概率大的 )的符号用最短的编码,
– 最少出现的符号用最长的编码 。
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 2） 例子：建立概率统计表和编码树符号 概率 1 2
3 4
a2 0.4 0.4 0.4
0.4 0.6
a6 0.3 0.3 0.3
0.3 0.4
a1 0.1 0.1 0.2
0.3
a4 0.1 0.1 0.1
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
– 霍夫曼编码
（ 2） 例子：编码过程：
符号 概率 编码 1 2 3
4
a2 0.4 1 0.4 1 0.4
1 0.4 1 0.6 0
a6 0.3 00 0.3 00 0.3 00
0.3 00 0.4 1
a1 0.1 011 0.1 011 0.2 010
0.3 01
a4 0.1 0100 0.1 0100 0.1 011
a3 0.06 01010 0.1 0101
a5 0.04 01011
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 2） 例子：
解码过程：
01010 011 1 1 00
a3 a1 a2 a2 a6
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 3） 算法实现
第一步：建立一系列的原数据缩减量通过对符号的概率排序,把最小概率的符号组成一个符号,以便在下一个原数据缩减量中替换它们 。
第二步：给每一个缩减的原始数据编码从最少的原数据开始,向后进行到起始原数据 。
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
– 静态编码
在压缩之前就建立好一个概率统计表和编码树 。
算法速度快,但压缩效果不是最好
– 动态编码
对每一个图像,临时建立概率统计表和编码树 。
算法速度慢,但压缩效果最好第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
1） 编码思想
1,去除像素冗余 。
2,认为相邻像素的信息有冗余 。 当前像素值可以用以前的像素值来获得 。
3,用当前像素值 fn,通过预测器得到一个预测值? fn，
对当前值和预测值求差,对差编码,作为压缩数据流中的下一个元素 。 由于差比原数据要小,因而编码要小,可用变长编码 。 大多数情况下,fn
的预测是通过 m个以前像素的线性组合来生成的第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码即,m
fn = round[ifn-i]
i=1
在一维线性 (行预测 )预测编码中,预测器为,
m
fn(x,y) = round[if(x,y-i)]
i=1
round为取最近整数,?i为预测系数 (可为 1/m),y是行变量 。
4,前 m个像素不能用此法编码,可用哈夫曼编码第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码举例,m
fn = round[ifn-i]
i=1
F = {154,159,151,149,139,121,112,109,129}
m = 2? = 1/2
预测值 f2 = 1/2 * (154 + 159)? 156 e2 = 151 - 156
= -5
f3 = 1/2 * (159 + 151) = 155 e3 = 149 – 155
= -6
f4 = 1/2 * (151 + 149) = 150 e4 = 139 –
150 = -11
f5 = 1/2 * (149 + 139) = 144 e5 = 121 – 144
= -23
f6 = 1/2 * (139 + 121) = 130 e6 = 112 – 130
= -18
第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
（ 2） 编码
第一步：压缩头处理
第二步：对每一个符号,f(x,y),由前面的值,
通过预测器,求出预测值?f(x,y)
第三步：求出预测误差
e(x,y) = f(x,y) -?f(x,y)
第四步：对误差 e(x,y)编码,作为压缩值 。
重复二,三,四步第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码编码预测器 最接近的整数
+?
-
符号编码 压缩图像输入图像
enf
n
f
n
第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
（ 3） 解码
第一步：对头解压缩
第二步：对每一个预测误差的编码解码,得到预测误差 e(x,y)。
第三步：由前面的值,得到预测值?f(x,y)。
第四步：误差 e(x,y),与预测值?f(x,y)相加,
得到解码 f(x,y)。
重复二,三,四步第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码解码预测器符号解码
+?
+
压缩图像
en
解压缩图像
fn
fn
第四章图像压缩第二节无损压缩请提问
4.1 图像压缩的基本概念
4.2 无损压缩
4.3 有损压缩
4.4 压缩标准第四章图像压缩第一节 图像压缩的基本概念
4.1.1 数据冗余
4.1.2 保真度标准
4.1.3 图像压缩模型第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
图像压缩的基本概念设,n1和 n2是在两个表达相同信息的数据集中,所携带的单位信息量 。
– 压缩率 （ 压缩比 ）,——描述压缩算法性能
CR = n1 / n2
其中,n1是压缩前的数据量,n2是压缩后的数据量
– 相对数据冗余,
RD = 1 – 1/CR
例,CR=20; RD = 19/20
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
三种数据冗余：
1,编码冗余
2,像素冗余
3,视觉心理冗余第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
1,编码冗余,
如果一个图像的灰度级编码,使用了多于实际需要的编码符号,就称该图像包含了编码冗余 。
例：如果用 8位表示该图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
2,像素冗余,
由于任何给定的像素值,原理上都可以通过它的邻居预测到,单个像素携带的信息相对是小的 。
对于一个图像,很多单个像素对视觉的贡献是冗余的 。 这是建立在对邻居值预测的基础上 。
例：原图像数据,234 223 231 238 235
压缩后数据,234 11 -8 -7 3
第四章图像压缩第一节图像压缩基本概念
4.1.1 图像压缩基本概念,数据冗余
3,视觉心理冗余,
一些信息在一般视觉处理中比其它信息的相对重要程度要小,这种信息就被称为视觉心理冗余 。
第四章图像压缩第一节图像压缩基本概念
33K 15K
4.1.2 图像压缩基本概念,保真度标准
保真度标准 ——评价压缩算法的标准
1,客观保真度标准
2,主观保真度标准第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
1,客观保真度标准如果图像压缩过程对图像信息有所损失,
如何用数学形式,表述这种损失？
将信息损失的多少,表示为原始输入图像与压缩后又解压缩输出的图像的函数,这个函数就被称为 客观保真度标准 。 一般表示为：
e(x,y) = f(x,y) - f(x,y)
f(x,y)是输入图像,f(x,y) 是压缩后解压缩的图像,e(x,y)是误差函数第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
离散的描述形式：
两个图像之间的 总误差,
M-1 N-1?
[ f(x,y) - f(x,y)]
x=0 y=0
均方根误差 （ rms）
M-1 N-1?
erms = [1/MN [ f(x,y) - f(x,y)]2]1/2
x=0 y=0
第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,保真度标准
2,主观保真度标准通过视觉比较两个图像,给出一个定性的评价,如很粗,粗,稍粗,
相同,稍好,较好,很好,这种评价被称为 主观保真度标准 。
第四章图像压缩第一节图像压缩基本概念
4.1.2 图像压缩基本概念,图像压缩模型
图像压缩模型
1,图像传输环境中图像压缩模型
2,源数据编码与解码的模型第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
图像传输环境中图像压缩模型
– 源数据编码,完成原数据的压缩。
– 通 道 编 码,为了抗干扰，增加一些容错、校验位、
版权保护，实际上是增加冗余。
– 通 道,如 Internet、广播、通讯、可移动介质源数据编码通道编码 通道通道解码源数据解码第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
源数据编码与解码的模型
– 源数据编码的模型
– 源数据解码的模型符号解码器反向映射器映射器 量化器 符号编码器第四章图像压缩第一节图像压缩基本概念
4.1.3 图像压缩基本概念,图像压缩模型
源数据编码与解码的模型
– 映射器,减少像素冗余,如使用 RLE
编 码。或进行图像变换。
– 量化器,减少视觉心理冗余,仅用于有 损压缩。
– 符号编码器,减少编码冗余,如使用哈夫曼编码第四章图像压缩第一节图像压缩基本概念第二节 无损压缩
4.2.1 基于字典的压缩
4.2.2 统计编码
4.2.3 无损预测编码第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
基于字典的压缩
– RLE编码 ——行程编码
PCX
– LZW编码
GIF
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 概念：
行程,具有相同灰度值的像素序列 。
– 编码思想：
去除像素冗余 。
用行程的灰度和行程的长度代替行程本身 。
例：设重复次数为 iC,重复像素值为 iP
编码为,iCiP iCiP iCiP
编码前,aaaaaaabbbbbbcccccccc
编码后,7a6b8c
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 分析：
对于有大面积色块的图像,压缩效果很好
对于纷杂的图像,压缩效果不好,最坏情况下,
会加倍图像第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– 例子,PCX_RLE
（ 1） PCX简介：
真彩色图像以行为单位,按色面存放
128字节的文件头图像数据调色板第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
（ 2） PCX_RLE编码原则：
1) 图像数据以 字节 为单位进行编码
2) 按行进行压缩
3) 长度在前,灰度值在后
4) 单像素没有长度值
5) 以最高两位作为判断是 重复数 还是 原像素 。
最高两位为 1,说明是重复数,否则,说明是原像素值第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
（ 2） PCX_RLE编码原则：
6) 重复像素长度 iC最大值为 26-1 = 63,如果遇到 iC
大于 63的情况,则分为小于 63的几段,分别处理 。
7) 如果遇到不重复的单个像素 P：
如果 P < 0xC0（ 192） 直接存入该像素值,
否则先存入长度 1,再存入像素值
（ 注,<1> 192-255之间的单像素图像不减反增
<2> 192-255之间,64个数高两位为 11）
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
RLE 编码 ——Run Length Encoding
– （ 3） PCX_RLE的解码 （ 以解一行为例 ）
1) 读一个字节到 byChar
2) if ((byChar & 0xC0) == 0xC0) {
//判前两位是否全 1,C0 = 1100 0000
iCount = byChar & 0x3F；
//取出后 6位的重复数连续读 iCount个字节
}
else { 直接读下一个字节 }
3)重复 1),2)直到读完一行 。
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 背景：是 Lemple,Ziv提出,Welch充实
– 基本思想：去除像素冗余 。
(1) 在压缩过程中动态地形成一个字符序列表 (字典 )
(2) (a) 每当压缩扫描图像发现一个字典中没有的字符 序列,就把该字符序列存到字典中
(b) 并用字典的地址 （ 编码 ） 作为这个字符序列的代码,替换原图像中的字符序列
(c) 下次再碰到相同的字符序列,就用字典的地址第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 基本思想：
(3) 压缩的结果,除了压缩图像外,不需要保留压缩过程中形成的字典,而在解压缩时,临时恢复这个字典 。
– 问题：字符序列的长度如何确定？
字典的长度如何确定？
字典满了怎么办？
如何查字典？
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
字典中字符序列的长度,
字典中字符串的长度可能会很长,由于每一个字符串,
都是表中一个已经存在的字符串加上一个字符组成,所以可以把字符串以
<已有字符串索引 > + <字符 >
这样字典元素的长度统一为 12+8,20位 。
字典的长度,
对于以字节 （ 8位 ） 为压缩单元,如 ASCII码,字典的长度为 212 = 4096,索引的长度为 12位,字典的前 256个保存单个字符,剩下的 3840个的分配给压缩过程中出现的字符串 。
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
字典满了的解决办法,
在字典满了以后 （ 新字符串超过 4096）,输出一个清除字典的标记 LZW_CLEAR,清空字典,开始新的编码 。
查表的方法,
可通过 Hashing函数 （ 散列,杂凑 ） 的方法来减少 查表的次数 。
输出编码的时机,
发现新串时,输出前一个串的编码第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
– 例子,GIF和 TIFF都使用 LZW压缩法 。 下面以 GIF
为例进行介绍：
（ 1） GIF简介 （ 多图像,256色 ）
文件结构：
文件头信息：标识 （ GIF）,版本号屏幕描述,屏幕长,宽,背景色等全局调色板：长度 （ 256x3） //三个 256色的调色板第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码
（ 1） GIF简介 （ 多图像,256色 ）
图 像 描 述：描述图像块在屏幕上的左上角位置及宽高 //可以有多个局部调色板,长度 （ 256x3） //三个 256色的调色板,每个图像可有一个图像数 据：用 LZW方式压缩,用 256字节的块来存放扩充块描述：有四种扩充块文件结尾,字符,；,
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码 文件头信息
LZW压缩图像数据全局调色板屏幕描述图像描述局部调色板扩充数据块第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
LZW编码第四章图像压缩第二节无损压缩初始化字典输出清除标记 LZW_CLEAR
Temp = 空串
k = 从输入流中读一个字符是结尾标志吗？
把新串 Temp+k加到字典中
Temp = k
输出 Temp的编码输出结束标记
Temp+k在字典中吗？
是
Temp = Temp+k
输出 Temp的编码是
4.2.1 无损压缩,基于字典的压缩
– （ 2） GIF_LZW编码
InitializeStringTable(); //初始化串表
WriteCode(LZW_CLEAR); //输出清除标记
Temp = the empty string; //临时串变量置空
For 对输入流中每一个字符 { //扫描字符的循环
k = GetNextCharacter(); //读入一个新字符
if (temp + k 在串表中 ) { //判断,临时串变量 + 新字符,
是否在表中
temp = temp + k; //更新临时串变量
}
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
else {
WriteCode(CodeFromString(temp));
// 输出新临时串变量的编码
AddTableEntry(temp + k);
//把新字符串存到串表中
Temp = k; //用当前读入的字符更新临时
temp
}}
WriteCode(CodeFromString(temp));
// 输出新临时串变量的编码
WriteCode(LZW_EOI); // 输出结束标记第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩编码举例：设字符集 {a,b,c,d}，
串,aabdaadaa
压缩字典 临时串 输入串 编码
0 a T=temp + a
1 b T= a + a 0
2 c T= a + b 00
3 d T= b + d001
4 aa T= d + a0013
5 ab T= a + a
6 bd T= aa + d00134
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
（ 3） GIF_LZW解码
While ((Code = GetNextCode()) != LZW_EOI) {
If (Code = = LZW_CLEAR) { //判断是否是清除标记
InitializeStringTable(); //初始化串表
Code = GetNextCode(); //读入编码
If (Code != LZW_CLEAR) { //如果不是清除标记
WriteString(StringFromCode(Code));
//查串表输出字符
OldCode = Code; //保留当前编码
} }
else {
第四章图像压缩第二节无损压缩
4.2.1 无损压缩,基于字典的压缩
if (IsInTabel(Code) { //判编码是否已经在表中
WriteString(StringFromCode(Code)); //输出字符串
OldCode = Code; //保留当前编码
}
else { //不在串表中
OutString=
StringFromCode(OldCode)+
StringFromCode(GetLastChar(Code));
//新老组合解码
WriteString(OutString); //输出解码
AddStringToTable(OutString); //给串表加一项
OldCode = Code; //保留当前编码
}
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
统计编码
– 霍夫曼编码第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 1） 基本思想通过减少编码冗余来达到压缩的目的 。
1,基本思想是统计一下符号的出现概率,
2,建立一个概率统计表,
– 将最常出现 (概率大的 )的符号用最短的编码,
– 最少出现的符号用最长的编码 。
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 2） 例子：建立概率统计表和编码树符号 概率 1 2
3 4
a2 0.4 0.4 0.4
0.4 0.6
a6 0.3 0.3 0.3
0.3 0.4
a1 0.1 0.1 0.2
0.3
a4 0.1 0.1 0.1
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
– 霍夫曼编码
（ 2） 例子：编码过程：
符号 概率 编码 1 2 3
4
a2 0.4 1 0.4 1 0.4
1 0.4 1 0.6 0
a6 0.3 00 0.3 00 0.3 00
0.3 00 0.4 1
a1 0.1 011 0.1 011 0.2 010
0.3 01
a4 0.1 0100 0.1 0100 0.1 011
a3 0.06 01010 0.1 0101
a5 0.04 01011
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 2） 例子：
解码过程：
01010 011 1 1 00
a3 a1 a2 a2 a6
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
（ 3） 算法实现
第一步：建立一系列的原数据缩减量通过对符号的概率排序,把最小概率的符号组成一个符号,以便在下一个原数据缩减量中替换它们 。
第二步：给每一个缩减的原始数据编码从最少的原数据开始,向后进行到起始原数据 。
第四章图像压缩第二节无损压缩
4.2.2 无损压缩,统计编码
霍夫曼编码
– 静态编码
在压缩之前就建立好一个概率统计表和编码树 。
算法速度快,但压缩效果不是最好
– 动态编码
对每一个图像,临时建立概率统计表和编码树 。
算法速度慢,但压缩效果最好第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
1） 编码思想
1,去除像素冗余 。
2,认为相邻像素的信息有冗余 。 当前像素值可以用以前的像素值来获得 。
3,用当前像素值 fn,通过预测器得到一个预测值? fn，
对当前值和预测值求差,对差编码,作为压缩数据流中的下一个元素 。 由于差比原数据要小,因而编码要小,可用变长编码 。 大多数情况下,fn
的预测是通过 m个以前像素的线性组合来生成的第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码即,m
fn = round[ifn-i]
i=1
在一维线性 (行预测 )预测编码中,预测器为,
m
fn(x,y) = round[if(x,y-i)]
i=1
round为取最近整数,?i为预测系数 (可为 1/m),y是行变量 。
4,前 m个像素不能用此法编码,可用哈夫曼编码第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码举例,m
fn = round[ifn-i]
i=1
F = {154,159,151,149,139,121,112,109,129}
m = 2? = 1/2
预测值 f2 = 1/2 * (154 + 159)? 156 e2 = 151 - 156
= -5
f3 = 1/2 * (159 + 151) = 155 e3 = 149 – 155
= -6
f4 = 1/2 * (151 + 149) = 150 e4 = 139 –
150 = -11
f5 = 1/2 * (149 + 139) = 144 e5 = 121 – 144
= -23
f6 = 1/2 * (139 + 121) = 130 e6 = 112 – 130
= -18
第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
（ 2） 编码
第一步：压缩头处理
第二步：对每一个符号,f(x,y),由前面的值,
通过预测器,求出预测值?f(x,y)
第三步：求出预测误差
e(x,y) = f(x,y) -?f(x,y)
第四步：对误差 e(x,y)编码,作为压缩值 。
重复二,三,四步第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码编码预测器 最接近的整数
+?
-
符号编码 压缩图像输入图像
enf
n
f
n
第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码
（ 3） 解码
第一步：对头解压缩
第二步：对每一个预测误差的编码解码,得到预测误差 e(x,y)。
第三步：由前面的值,得到预测值?f(x,y)。
第四步：误差 e(x,y),与预测值?f(x,y)相加,
得到解码 f(x,y)。
重复二,三,四步第四章图像压缩第二节无损压缩
4.2.3 无损压缩,无损预测编码
无损预测编码解码预测器符号解码
+?
+
压缩图像
en
解压缩图像
fn
fn
第四章图像压缩第二节无损压缩请提问
