图像压缩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图像压缩基本概念 数据冗余 像素冗余 由于任何给定的像素值 原理上都可以通过它的邻居预测到 单个像素携带的信息相对是小的 对于一个图像 很多单个像素对视觉的贡献是冗余的 这是建立在对邻居值预测的基础上 例 原图像数据 234223231238235压缩后数据 2341187 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 1N 1 f x y f x y x 0y 0均方根误差 rms M 1N 1 erms 1 MN f x y f x y 2 1 2x 0y 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编码 RunLengthEncoding概念 行程 具有相同灰度值的像素序列 编码思想 去除像素冗余 用行程的灰度和行程的长度代替行程本身 例 设重复次数为iC 重复像素值为iP编码为 iCiPiCiPiCiP编码前 aaaaaaabbbbbbcccccccc编码后 7a6b8c 第四章图像压缩第二节无损压缩 4 2 1无损压缩 基于字典的压缩 RLE编码 RunLengthEncoding分析 对于有大面积色块的图像 压缩效果很好对于纷杂的图像 压缩效果不好 最坏情况下 会加倍图像 第四章图像压缩第二节无损压缩 4 2 1无损压缩 基于字典的压缩 RLE编码 RunLengthEncoding例子 PCX RLE1 PCX简介 真彩色图像以行为单位 按色面存放 128字节的文件头 图像数据 调色板 第四章图像压缩第二节无损压缩 4 2 1无损压缩 基于字典的压缩 RLE编码 RunLengthEncoding2 PCX RLE编码原则 1 图像数据以字节为单位进行编码2 按行进行压缩3 长度在前 灰度值在后4 单像素没有长度值5 以最高两位作为判断是重复数还是原像素 最高两位为1 B0除外 说明是重复数 否则 说明是原像素值 第四章图像压缩第二节无损压缩 4 2 1无损压缩 基于字典的压缩 RLE编码 RunLengthEncoding2 PCX RLE编码原则 6 重复像素长度iC最大值为26 1 63 如果遇到iC大于63的情况 则分为小于63的几段 分别处理 7 如果遇到不重复的单个像素P 如果P 0 xC0 192 直接存入该像素值 否则先存入长度1 再存入像素值 192 255之间的单像素图像不减反增 第四章图像压缩第二节无损压缩 4 2 1无损压缩 基于字典的压缩 RLE编码 RunLengthEncoding 3 PCX RLE的解码 以解一行为例 1 读一个字节到byChar2 if byChar 0 xC0 0 xC0 判前两位是否全1 且前4位为C0 11010000iCount 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 theemptystring 临时串变量置空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压缩字典临时串输入串编码0aT temp a1bT a a02cT a b003dT b d0014aaT d a00135abT a a6bdT aa d001347daT d a8aadT da a0013479daaT a0013470 第四章图像压缩第二节无损压缩 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 例子 建立概率统计表和编码树符号概率1234a20 40 40 40 40 6a60 30 30 30 30 4a10 10 10 20 3a40 10 10 1a30 060 1a50 04 第四章图像压缩第二节无损压缩 4 2 2无损压缩 统计编码 霍夫曼编码 2 例子 编码过程 符号概率编码1234a20 410 410 410 410 60a60 3000 3000 3000 3000 41a10 10110 10110 20100 301a40 101000 101000 1011a30 06010100 10101a50 0401011 第四章图像压缩第二节无损压缩 4 2 2无损压缩 统计编码 霍夫曼编码 2 例子 解码过程 010100111100a3a1a2a2a6 第四章图像压缩第二节无损压缩 4 2 2无损压缩 统计编码 霍夫曼编码 3 算法实现第一步 建立一系列的原数据缩减量通过对符号的概率排序 把最小概率的符号组成一个符号 以便在下一个原数据缩减量中替换它们 第二步 给每一个缩减的原始数据编码从最少的原数据开始 向后进行到起始原数据 第四章图像压缩第二节无损压缩 4 2 2无损压缩 统计编码 霍夫曼编码静态编码在压缩之前就建立好一个概率统计表和编码树 算法速度快 但压缩效果不是最好动态编码对每一个图像 临时建立概率统计表和编码树 算法速度慢 但压缩效果最好 第四章图像压缩第二节无损压缩 4 2 3无损压缩 无损预测编码 无损预测编码1 编码思想a 去除像素冗余 b 认为相邻像素的信息有冗余 当前像素值可以用以前的像素值来获得 c 用当前像素值fn 通过预测器得到一个预测值 fn 对当前值和预测值求差 对差编码 作为压缩数据流中的下一个元素 由于差比原数据要小 因而编码要小 可用变长编码 大多数情况下 fn的预测是通过m个以前像素的线性组合来生成的 第四章图像压缩第二节无损压缩 4 2 3无损压缩 无损预测编码 即 mfn round ifn i i 1在一维线性 行预测 预测编码中 预测器为 mfn x y round if x y i i 1round为取最近整数 i为预测系数 可为1 m y是行变量 d 前m个像素不能用此法编码 可用哈夫曼编码 第四章图像压缩第二节无损压缩 4 2 3无损压缩 无损预测编码 举例 mfn round ifn i i 1F 154 159 151 149 139 121 112 109 129 m 2 1 2预测值f2 1 2 154 159 156e2 151