图像压缩基本概念

1、关于图像压缩的基本概念第1页，共52页，2022年，5月20日，5点12分，星期四第四章 图像压缩4.1 图像压缩的基本概念4.2 无损压缩4.3 有损压缩4.4 压缩标准第四章 图像压缩第2页，共52页，2022年，5月20日，5点12分，星期四第一节 图像压缩的基本概念4.1.1 数据冗余4.1.2 保真度标准4.1.3 图像压缩模型第四章 图像压缩 第一节图像压缩基本概念第3页，共52页，2022年，5月20日，5点12分，星期四4.1.1 图像压缩基本概念:数据冗余图像压缩的基本概念 设：n1和n2是在两个表达相同信息的数据集中，所携 带的单位信息量。压缩率（压缩比）：CR = n1

2、/ n2其中，n1是压缩前的数据量，n2是压缩后的数据量相对数据冗余：RD = 1 1/CR例：CR=20; RD = 19/20第四章 图像压缩 第一节图像压缩基本概念第4页，共52页，2022年，5月20日，5点12分，星期四4.1.1 图像压缩基本概念:数据冗余三种数据冗余：编码冗余像素冗余视觉心理冗余第四章 图像压缩 第一节图像压缩基本概念第5页，共52页，2022年，5月20日，5点12分，星期四4.1.1 图像压缩基本概念:数据冗余编码冗余： 如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。例：如果用8位表示该图像的像素，我们就说该图像存在着编码冗

3、余，因为该图像的像素只有两个灰度，用一位即可表示。第四章 图像压缩 第一节图像压缩基本概念第6页，共52页，2022年，5月20日，5点12分，星期四4.1.1 图像压缩基本概念:数据冗余像素冗余： 由于任何给定的像素值，原理上都可以通过它的邻居预测到，单个像素携带的信息相对是小的。 对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。例：原图像数据：234 223 231 238 235 压缩后数据：234 11 8 7 -3第四章 图像压缩 第一节图像压缩基本概念第7页，共52页，2022年，5月20日，5点12分，星期四4.1.1 图像压缩基本概念:数据冗余视

4、觉心理冗余： 一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。第四章 图像压缩 第一节图像压缩基本概念第8页，共52页，2022年，5月20日，5点12分，星期四4.1.2 图像压缩基本概念:保真度标准保真度标准评价压缩算法的标准客观保真度标准主观保真度标准第四章 图像压缩 第一节图像压缩基本概念第9页，共52页，2022年，5月20日，5点12分，星期四4.1.2 图像压缩基本概念:保真度标准客观保真度标准 如果信息丢失的级别,可以表示为原始或输入图像与压缩后又解压缩输出的图像的函数，这个函数就被称为客观保真度标准。一般表示为： e(x,y) = f(x,

5、y) - f(x,y) f(x,y)是输入图像， f(x,y) 是压缩后解压缩的图像， e(x,y)是误差函数第四章 图像压缩 第一节图像压缩基本概念第10页，共52页，2022年，5月20日，5点12分，星期四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第四章 图像压缩 第一节图像压缩基本概念第11页，共52页，2022年，5月20日，5点12分，星期四4.1.2 图像压缩基本概念:保真度标准主观

6、保真度标准 通过视觉比较两个图像，给出一个定性的评价，如很粗、粗、稍粗、相同、稍好、较好、很好，这种评价被称为主观保真度标准。第四章 图像压缩 第一节图像压缩基本概念第12页，共52页，2022年，5月20日，5点12分，星期四4.1.3 图像压缩基本概念:图像压缩模型源数据编码：完成原数据的压缩。通 道 编 码：为了抗干扰，增加一些容错、校验 位，实际上是增加冗余。通 道：如Internet、广播、通讯、可移 动介质源数据编码通道编码通道通道解码源数据解码第四章 图像压缩 第一节图像压缩基本概念第13页，共52页，2022年，5月20日，5点12分，星期四4.1.3 图像压缩基本概念:图像压

7、缩模型源数据编码与解码的模型源数据编码的模型源数据解码的模型符号解码器反向映射器映射器量化器符号编码器第四章 图像压缩 第一节图像压缩基本概念第14页，共52页，2022年，5月20日，5点12分，星期四4.1.3 图像压缩基本概念:图像压缩模型源数据编码与解码的模型映射器 ：减少像素冗余，如使用RLE编 码。或进行图像变换。量化器 ：减少视觉心理冗余，仅用于有 损压缩。符号编码器：减少编码冗余，如使用哈夫曼 编码第四章 图像压缩 第一节图像压缩基本概念第15页，共52页，2022年，5月20日，5点12分，星期四第二节 无损压缩4.2.1 基于字典的压缩4.2.2 统计编码4.2.3 无损预

8、测编码第四章 图像压缩 第二节 无损压缩第16页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩基于字典的压缩RLE编码行程编码PCXLZW编码GIF第四章 图像压缩 第二节 无损压缩第17页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding概念：行程：具有相同灰度值的像素序列。编码思想：去除像素冗余。用行程的灰度和行程的长度代替行程本身。例：设重复次数为 iC, 重复像素值为 iP编码为：iCiP iCiP iCiP 编码前：aaaaaaabbbbbbccccc

9、ccc 编码后：7a6b8c第四章 图像压缩 第二节 无损压缩第18页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding分析：对于有大面积色块的图像，压缩效果很好对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像第四章 图像压缩 第二节 无损压缩第19页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding例子：PCX_RLE1）PCX简介：真彩色图像以行为单位，按色面存放128字节的文件头图像数据调色板第四章 图像压

10、缩 第二节 无损压缩第20页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding2） PCX_RLE编码原则：1) 图像数据以字节为单位进行编码2) 按行进行压缩3) 长度在前，灰度值在后4) 单像素没有长度值5) 以最高两位作为判断是重复数还是原像素。 最高两位为1（B0除外），说明是重复数，否则，说明是原像素值第四章 图像压缩 第二节 无损压缩第21页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding2） PCX_

11、RLE编码原则：6) 重复像素长度iC最大值为26-1 = 63，如果遇到iC大于63的情况，则分为小于63的几段，分别处理。7) 如果遇到不重复的单个像素P：如果P 0 xC0（192） 直接存入该像素值，否则先存入长度1，再存入像素值 （192-255之间的单像素图像不减反增）第四章 图像压缩 第二节 无损压缩第22页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩RLE 编码Run Length Encoding（3）PCX_RLE的解码（以解一行为例）1) 读一个字节到 byChar2) if (byChar & 0 xC0) = 0 xC0)

12、 /判前两位是否全1，且前4位为 C0 = 1101 0000iCount = byChar & 0 x3F； /取出后6位的重复数连续读iCount个字节 else 直接读下一个字节3)重复a)，b)直到读完一行。第四章 图像压缩 第二节 无损压缩第23页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码背景：是Lemple、Ziv提出，Welch充实基本思想：去除像素冗余。(1) 在压缩过程中动态地形成一个字符序列表(字典)(2) (a) 每当压缩扫描图像发现一个字典中没有的字符 序列，就把该字符序列存到字典中 (b) 并用字典的地址（编码

13、）作为这个字符序列的 代码，替换原图像中的字符序列 (c) 下次再碰到相同的字符序列，就用字典的地址 代替字符序列第四章 图像压缩 第二节 无损压缩第24页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码基本思想：去除像素冗余(3) 压缩的结果，除了压缩图像外，不需要保 留压缩过程中形成的字典，而在解压缩时， 临时恢复这个字典。问题：字符序列的长度如何确定？字典的长度如何确定？字典满了怎么办？如何查表？第四章 图像压缩 第二节 无损压缩第25页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码

14、字符序列的长度：字符串的长度可能会很长，由于每一个字符串，都是表中一个已经存在的字符串加上一个字符组成，所以可以把字符串以 + 这样字典元素的长度统一为12+8，20位。字典的长度： 对于以字节（8位）为压缩单元，如ASCII码，字典的长度为212 = 4096，索引的长度为12位，字典的前256个保存单个字符，剩下的3840个的分配给压缩过程中出现的字符串。第四章 图像压缩 第二节 无损压缩第26页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码字典满了的解决办法： 在字典满了以后，输出一个清除字典的标记 LZW_CLEAR，清空字典，开始

15、新的编码。查表的方法： 可通过Hashing函数（散列、杂凑）的方法来减少查表的次数。输出编码的时机： 发现新串时，输出前一个串的编码第四章 图像压缩 第二节 无损压缩第27页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码例子：GIF和TIFF都使用LZW压缩法。下面以GIF为例进行介绍：1）GIF简介（多图像、256色）文件结构：文件头信息：标识（GIF）、版本号屏幕描述 ：屏幕长、宽、背景色等全局调色板：长度（256x3）/三个256色的调色板第四章 图像压缩 第二节 无损压缩第28页，共52页，2022年，5月20日，5点12分，星期

16、四4.2.1 无损压缩:基于字典的压缩LZW编码图 象 描 述：描述图像块在屏幕上的左上角位 置及宽高/可以有多个局部调色板: 长度（256x3）/三个256色的调 色板，每个图像可有一个图像数 据：用LZW方式压缩，用256字节的块来 存放扩充块描述：有四种扩充块文件结尾 ：字符“；”第四章 图像压缩 第二节 无损压缩第29页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩LZW编码文件头信息LZW压缩图像数据全局调色板屏幕描述图像描述局部调色板扩充数据块第四章 图像压缩 第二节 无损压缩第30页，共52页，2022年，5月20日，5点12分，星期四

17、4.2.1 无损压缩:基于字典的压缩LZW编码第四章 图像压缩 第二节 无损压缩初始化字典输出清除标记 LZW_CLEARTemp = 空串k = 从输入流中读一个字符是结尾标志吗？Temp+k在字典中吗？输出Temp的编码把新串Temp+k加到字典中Temp = kTemp = Temp+k输出Temp的编码输出结束标记第31页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩（2）GIF_LZW编码InitializeStringTable();/初始化串表WriteCode(LZW_CLEAR);/输出清除标记Temp = the empty st

18、ring;/临时串变量置空For 对输入流中每一个字符/扫描字符的循环k = GetNextCharacter();/读入一个新字符if (temp + k 在串表中) /判断“临时串变量+新字符”是否在表中temp = temp + k;/更新临时串变量第四章 图像压缩 第二节 无损压缩第32页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩else WriteCode(CodeFromString(temp); / 输出新临时串变量的编码AddTableEntry(temp + k); /把新字符串存到串表中Temp = k; /用当前读入的字符更

19、新临时tempWriteCode(CodeFromString(temp); / 输出新临时串变量的编码WriteCode(LZW_EOI); / 输出结束标记第四章 图像压缩 第二节 无损压缩第33页，共52页，2022年，5月20日，5点12分，星期四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=

20、 d +a 8aad T= da +a 001347 9daa T= a 0013470 第四章 图像压缩 第二节 无损压缩第34页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩（3）GIF_LZW解码While (Code = GetNextCode() != LZW_EOI) If (Code = = LZW_CLEAR) /判断是否是清除标记InitializeStringTable(); /初始化串表Code = GetNextCode(); /读入编码If (Code != LZW_CLEAR) /如果不是清除标记 WriteString(

21、StringFromCode(Code); /查串表输出字符OldCode = Code; /保留当前编码 else 第四章 图像压缩 第二节 无损压缩第35页，共52页，2022年，5月20日，5点12分，星期四4.2.1 无损压缩:基于字典的压缩if (IsInTabel(Code) /判编码是否已经在表中WriteString(StringFromCode(Code); /输出字符串 OldCode = Code; /保留当前编码else /不在串表中OutString = StringFromCode(OldCode) + StringFromCode(GetLastChar(Code

22、);/新老组合解码WriteString(OutString);/输出解码AddStringToTable(OutString); /给串表加一项OldCode = Code; /保留当前编码第四章 图像压缩 第二节 无损压缩第36页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码统计编码霍夫曼编码第四章 图像压缩 第二节 无损压缩第37页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码霍夫曼编码（1） 基本思想通过减少编码冗余来达到压缩的目的。基本思想是统计一下符号的出现概率，建立一个概率统计表，将最常出现(概率大的)的

23、符号用最短的编码，最少出现的符号用最长的编码。第四章 图像压缩 第二节 无损压缩第38页，共52页，2022年，5月20日，5点12分，星期四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 第四章 图像压缩 第二节 无损压缩第39页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码霍夫曼编码（2）例子：编码过程

24、：符号 概率 编码 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第四章 图像压缩 第二节 无损压缩第40页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码霍夫曼编码（2）例子： 解码过程： 01010 011 1 1 00 a3 a1 a2 a2 a6第四章 图像压缩 第二

25、节 无损压缩第41页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码霍夫曼编码（3）算法实现第一步：建立一系列的原数据缩减量通过对符号的概率排序，把最小概率的符号组成一个符号，以便在下一个原数据缩减量中替换它们。第二步：给每一个缩减的原始数据编码从最少的原数据开始，向后进行到起始原数据。第四章 图像压缩 第二节 无损压缩第42页，共52页，2022年，5月20日，5点12分，星期四4.2.2 无损压缩:统计编码霍夫曼编码静态编码在压缩之前就建立好一个概率统计表和编码树。算法速度快，但压缩效果不是最好动态编码对每一个图像，临时建立概率统计表和编码树。算法速度慢

26、，但压缩效果最好第四章 图像压缩 第二节 无损压缩第43页，共52页，2022年，5月20日，5点12分，星期四4.2.3 无损压缩:无损预测编码无损预测编码1）编码思想a.去除像素冗余。b.认为相邻像素的信息有冗余。当前像素值可以用以前的像素值来获得。c.用当前像素值fn ，通过预测器得到一个预测值 fn，对当前值和预测值求差，对差编码，作为压缩数据流中的下一个元素。由于差比原数据要小，因而编码要小，可用变长编码。大多数情况下， fn的预测是通过m个以前像素的线性组合来生成的。第四章 图像压缩 第二节 无损压缩第44页，共52页，2022年，5月20日，5点12分，星期四4.2.3 无损压缩

27、:无损预测编码即： m fn = roundifn-i i=1在一维线性(行预测)预测编码中，预测器为： m fn(x,y) = roundif(x, y-i) i=1round为取最近整数，i为预测系数(可为1/m)，y是行变量。d.前m个像素不能用此法编码，可用哈夫曼编码第四章 图像压缩 第二节 无损压缩第45页，共52页，2022年，5月20日，5点12分，星期四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 + 14