图像压缩的基本概念.ppt

数字图像处理,北京大学计算机研究所 陈晓鸥,第四章 图像压缩,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 图像压缩基本概念:数据冗余,三种数据冗余：编码冗余像素冗余视觉心理冗余,第四章 图像压缩 第一节图像压缩基本概念,4.1.1 图像压缩基本概念:数据冗余,编码冗余：如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。,例：如果用8位表示该图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。,第四章 图像压缩 第一节图像压缩基本概念,4.1.1 图像压缩基本概念:数据冗余,像素冗余：由于任何给定的像素值，原理上都可以通过它的邻居预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。例：原图像数据：234 223 231 238 235 压缩后数据：234 11 8 7-3,第四章 图像压缩 第一节图像压缩基本概念,4.1.1 图像压缩基本概念:数据冗余,视觉心理冗余：一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。,第四章 图像压缩 第一节图像压缩基本概念,4.1.2 图像压缩基本概念:保真度标准,保真度标准评价压缩算法的标准客观保真度标准主观保真度标准,第四章 图像压缩 第一节图像压缩基本概念,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,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 图像压缩基本概念:图像压缩模型,源数据编码：完成原数据的压缩。通 道 编 码：为了抗干扰，增加一些容错、校验 位，实际上是增加冗余。通 道：如Internet、广播、通讯、可移 动介质,源数据编码,通道编码,通道,通道解码,源数据解码,第四章 图像压缩 第一节图像压缩基本概念,4.1.3 图像压缩基本概念:图像压缩模型,源数据编码与解码的模型源数据编码的模型源数据解码的模型,符号解码器,反向映射器,映射器,量化器,符号编码器,第四章 图像压缩 第一节图像压缩基本概念,4.1.3 图像压缩基本概念:图像压缩模型,源数据编码与解码的模型映射器：减少像素冗余，如使用RLE编 码。或进行图像变换。量化器：减少视觉心理冗余，仅用于有 损压缩。符号编码器：减少编码冗余，如使用哈夫曼 编码,第四章 图像压缩 第一节图像压缩基本概念,第二节 无损压缩,4.2.1 基于字典的压缩4.2.2 统计编码4.2.3 无损预测编码,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,基于字典的压缩RLE编码行程编码PCXLZW编码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_RLE1）PCX简介：真彩色图像以行为单位，按色面存放,128字节的文件头,图像数据,调色板,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,RLE 编码Run Length Encoding2）PCX_RLE编码原则：1)图像数据以字节为单位进行编码2)按行进行压缩3)长度在前，灰度值在后4)单像素没有长度值5)以最高两位作为判断是重复数还是原像素。最高两位为1（B0除外），说明是重复数，否则，说明是原像素值,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,RLE 编码Run Length Encoding2）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)/判前两位是否全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)下次再碰到相同的字符序列，就用字典的地址 代替字符序列,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码基本思想：去除像素冗余(3)压缩的结果，除了压缩图像外，不需要保 留压缩过程中形成的字典，而在解压缩时，临时恢复这个字典。问题：字符序列的长度如何确定？字典的长度如何确定？字典满了怎么办？如何查表？,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码字符序列的长度：字符串的长度可能会很长，由于每一个字符串，都是表中一个已经存在的字符串加上一个字符组成，所以可以把字符串以+这样字典元素的长度统一为12+8，20位。字典的长度：对于以字节（8位）为压缩单元，如ASCII码，字典的长度为212=4096，索引的长度为12位，字典的前256个保存单个字符，剩下的3840个的分配给压缩过程中出现的字符串。,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码字典满了的解决办法：在字典满了以后，输出一个清除字典的标记 LZW_CLEAR，清空字典，开始新的编码。查表的方法：可通过Hashing函数（散列、杂凑）的方法来减少查表的次数。输出编码的时机：发现新串时，输出前一个串的编码,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码例子：GIF和TIFF都使用LZW压缩法。下面以GIF为例进行介绍：1）GIF简介（多图像、256色）文件结构：文件头信息：标识（GIF）、版本号屏幕描述：屏幕长、宽、背景色等全局调色板：长度（256x3）/三个256色的调色板,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码图 象 描 述：描述图像块在屏幕上的左上角位 置及宽高/可以有多个局部调色板:长度（256x3）/三个256色的调 色板，每个图像可有一个图像数 据：用LZW方式压缩，用256字节的块来 存放扩充块描述：有四种扩充块文件结尾：字符“；”,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码,文件头信息,LZW压缩图像数据,全局调色板,屏幕描述,图像描述,局部调色板,扩充数据块,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,LZW编码,第四章 图像压缩 第二节 无损压缩,初始化字典,输出清除标记 LZW_CLEAR,Temp=空串,k=从输入流中读一个字符,是结尾标志吗？,Temp+k在字典中吗？,输出Temp的编码,把新串Temp+k加到字典中,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;/用当前读入的字符更新临时tempWriteCode(CodeFromString(temp);/输出新临时串变量的编码WriteCode(LZW_EOI);/输出结束标记,第四章 图像压缩 第二节 无损压缩,4.2.1 无损压缩:基于字典的压缩,编码举例：设字符集a,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)/判断是否是清除标记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）基本思想通过减少编码冗余来达到压缩的目的。基本思想是统计一下符号的出现概率，建立一个概率统计表，将最常出现(概率大的)的符号用最短的编码，最少出现的符号用最长的编码。,第四章 图像压缩 第二节 无损压缩,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）例子：编码过程：符号 概率 编码 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.2.2 无损压缩:统计编码,霍夫曼编码（3）算法实现第一步：建立一系列的原数据缩减量通过对符号的概率排序，把最小概率的符号组成一个符号，以便在下一个原数据缩减量中替换它们。第二步：给每一个缩减的原始数据编码从最少的原数据开始，向后进行到起始原数据。,第四章 图像压缩 第二节 无损压缩,4.2.2 无损压缩:统计编码,霍夫曼编码静态编码在压缩之前就建立好一个概率统计表和编码树。算法速度快，但压缩效果不是最好动态编码对每一个图像，临时建立概率统计表和编码树。算法速度慢，但压缩效果最好,第四章 图像压缩 第二节 无损压缩,4.2.3 无损压缩:无损预测编码,无损预测编码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为取最近整数，i为预测系数(可为1/m)，y是行变量。d.前m个像素不能用此法编码，可用哈夫曼编码,第四章 图像压缩 第二节 无损压缩,4.2.3 无损压缩:无损预测编码,举例：m fn=roundifn-i i=1F=154,159,151,149,139,121,112,109,129m=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 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)编码，作为压缩值。重复二、三、四步,第四章 图像压缩 第二节 无损压缩,4.2.3 无损压缩:无损预测编码,无损预测编码编码,+-,符号编码,预测器,最接近的整数,压缩图像,输入图像,en,fn,fn,第四章 图像压缩 第二节 无损压缩,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,第四章 图像压缩 第二节 无损压缩,请提问,