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