photoshop实用教材第十六部.ppt

图像编码 1 图像编码概述 2 信息理论基础与熵编码赫夫曼编码 3 LZW编码 与文字信息不同 图像信息占据大量的存储容量 而且传输的带宽有限 如一幅512 512的黑白图象的比特数为512 512 8 2 097 152bit 256k 为什么进行图像压缩编码 视频数据量 对于电视画面的分辨率640 480的彩色图像 每秒30帧 则一秒钟的数据量为 640 480 24 30 221 12M实时传输 在10M带宽网上实时传输的话 需要压缩到原来数据量的0 045存储 1张CD可存640M 如果不进行压缩 1张CD则仅可以存放2 89秒的数据 可见 单纯依靠增加存储器容量和改善信道带宽无法满足需求 必须进行压缩 图像编码概述 图像编码基本原理 数字化后的图像信息数据量非常大 图像压缩利用图像数据存在冗余信息 去掉这些冗余信息后可以有效压缩图像 数据冗余 压缩率 压缩比 用于描述图像压缩效果CR n1 n2其中 n1是压缩前的数据量 n2是压缩后的数据量相对数据冗余 RD 1 1 CR n1 n2 n2 图像压缩的基本概念 常见图像的冗余类型 空间冗余 一幅图像表面上各点的颜色之间往往 度都是相同的 因此数据有很大的空间冗余 如 在静态图像中有一块表面颜色均匀的 区域 此区域中所有点的光强和色彩以及饱和 存在着空间连贯性 图像内部相邻像素之间的相关性所造成的冗余 时间冗余 视频图像不同帧之间的相关性所造成的冗余 运动图像相邻帧往往包含相同的背景和移动物体 所以后一帧的数据与前一帧的数据有许多共同 之处 只不过移动物体所在的空间位置略有不同 称为时间冗余 视觉冗余 人的眼睛对某些图像特征不敏感 这些特征信息可以不在图像数据中出现 事实上 人眼的分辨能力一般约为26灰度级 而图像的量化采用28灰度级 我们把这种冗余称为视觉冗余 信息熵冗余 编码冗余 如果图像中平均每个像素使用的比特数大于该图像的信息熵 则图像中存在冗余 例 如果用8位表示下面图像的像素 我们就说该图像存在着编码冗余 因为该图像的像素只有两个灰度 用一位即可表示 结构冗余 图像中存在很强的纹理结构或自相似性 知识冗余 由于存在着先验知识和背景知识 图像编码的目的就是尽量减小各种冗余信息 特别是空间冗余 视觉冗余 以少的比特数来表示图像 图像保真度信息无损型 信息损失型描述解码图像相对于原始图像的偏离程度对信息损失的测度主观保真度准则主观测量图像的质量 因人而异 应用不方便客观保真度准则用编码输入图与解码输出图的某个确定函数表示损失的信息量 便于计算或测量 1 客观保真度准则点误差图误差均方根误差均方信噪比 2 主观保真度准则观察者对图像综合评价的平均 电视图像质量评价尺度 2 信息量和信息熵 数据压缩技术的理论基础是信息论 从信息论的角度来看 压缩就是去掉信息 信息 可推知的 中的冗余 即保留不确定的信息 去掉确定的 1 数据压缩的理论极限 信息论中信源编码理论解决的主要问题 2 数据压缩的基本途径 信息量等于数据量与冗余量之差 I D du 数据是用来记录和传送信息的 或者说数据 是信息的载体 数据所携带的信息 信息量与数据量的关系 du 冗余量 I 信息量 D 数据量 真正有用的不是数据本身 而是 信息量 个符号的某条消息编码 En log2 Pn 即表示该符号所需的位数 考虑用0和1组成的二进制数码为含有n 息中重复出现的概率为Pn 假设符号Fn在整条消 则该符号的信息量 输入字符串 aabbaccbaa a b c出现的概率分别为0 5 0 3和0 2 他们的信息量分别为 Ea log2 0 5 1 Eb log2 0 3 1 737 Ec log2 0 2 2 322 总信息量也即表达整个字符串需要的位数为 E Ea 5 Eb 3 Ec 2 14 855位 举例说明 如果用二进制等长编码 需要多少位 20位 如果将信源所有可能事件的信息量进行 Entropy 熵 的概念 平均 就得到了信息熵 entropy 信息熵就是平均信息量 平均码长与熵 如果对字符aj的编码长度为Lj 则信号L的 平均码长为 m 信号中所出现不同字符的个数 平均码长 H X 稍大于H X 平均码长 H X 平均码长 H X 熵值是平均码长的下限 有冗余 不是最佳 不可能 是最佳编码 请计算出该数据流的信息熵及相应编码方式的平均码长 示例 输入数据流 S1S2S1S3S2S1S1S4 H X 1 75L1 2L2 1 75 总结 数据压缩的理论极限是信息熵 只要信源不是等概率分布 就存在着数据压缩的可能性 数据压缩的基本途径之一 使各字符的编码长度尽量等于字符的信息量 图像压缩编码的方法 图像压缩编码分为有损压缩和无损压缩 无损压缩无信息损失 解压缩时能够从压缩数据精确地恢复原始图像 有损压缩不能精确重建原始图像 存在一定程度的失真 根据编码原理将图像编码分为 1 熵编码 无损编码 给出现概率较大的符号赋予一个短码字 而给出现概率较小的符号赋予一个长码字 从而使得最终的平均码长很小 2 预测编码 基于图像数据的空间或时间冗余特性 用相邻的已知像素 或像素块 来预测当前像素 或像素块 的取值 然后再对预测误差进行量化和编码 3 变换编码 将空间域上的图像变换到另一变换域上 变换后图像的大部分能量只集中到少数几个变换系数上 采用适当的量化和熵编码就可以有效地压缩图像 图像编码的方法 1 Huffman编码原理 整体的大部分字符是由较短的编码 从而保证文件 出现频率高低的顺序分别赋以由短到长的代码 先统计数据中各字符出现的概率 再按字符 所构成 7 2哈夫曼编码 编码思想 将信源符号按概率递增顺序排列 将两个最小的概率加起来作为新符号的概率 重复步骤 和 直到概率和等于1 完成上述步骤后沿路径返回进行编码 寻找 从每一信源符号到概率为1处的路径 每层有两个分 支 分别大的概率赋予1和小的概率为0 从而得到每个符号的编码 H X 1 75L1 2L2 1 75 霍夫曼编码举例一 输入数据流 S1S2S1S3S2S1S1S4 1 统计出每级灰度出现的频率 灰度值 010203040出现频率 1 161 167 163 164 16 霍夫曼编码举例二 7 2哈夫曼编码 2 从左到右把上述频率按从小到大的顺序排列 灰度值 010304020出现频率 1 161 163 164 167 16 7 2哈夫曼编码 3 选出频率最小的两个值 1 16 1 16 作为二叉树的两个叶子节点 将频率和2 16作为它们的根节点 新的根节点再参与其它频率排序 2 163 165 167 16 7 2哈夫曼编码 4 选出频率最小的两个值 2 16 3 16 作为二叉树的两个叶子节点 将频率和5 16作为它们的根节点 新的根节点再参与其它频率排序 4 165 167 16 7 2哈夫曼编码 5 选出频率最小的两个值 4 16 5 16 作为二叉树的两个叶子节点将频率和9 16作为它们的根节点 新的根节点再参与其它频率排序 7 169 16 7 2哈夫曼编码 6 最后两个频率值 7 16 9 16 作为二叉树的两个叶子节点 将频率和1作为它们的根节点 7 2哈夫曼编码 7 分配码字 将形成的二叉树的左节点标0 右节点标1 把从最上面的根节点到最下面的叶子节点途中遇到的0 1序列串起来 就得到了各级灰度的编码 7 2哈夫曼编码 各灰度的编码如下 灰度值 204030100哈夫曼编码 01011111011100则图所示的图像哈夫曼编码为 11111010100101100000111111010100共用了32比特 原图像占128比特 压缩比较高 假设某个字符的出现概率为80 该字符只 需要 log2 0 8 0 322位编码 但Huffman 编码一定会为其分配 由此可得知 整个信息的80 在压缩后几 乎相当于理想长度的3倍左右 一位0或一位1的编码 存在问题分析 LZW编码 LZW 发明人 Lempel Ziv Welch 减少像素间冗余无损压缩特点 码字为固定长度不需要符号出现概率的知识是一种字典方法 压缩的数据并与一个字典库 库开始是空的 中 字符串插入字典中 字符串数据在字典库中的位置索引 的字符串对比 LZW压缩使用字典库查找方案 它读入待 如有匹配的字符串 则输出该 否则将该 步骤1 将词典初始化为包含所有可能的单字 步骤2 当前字符C 字符流中的下一个字符 字符 当前前缀P初始化为空 LZW编码算法 令P C 现在的P仅包含一个字符C 步骤3 判断P C是否在词典中 1 如果 是 则用C扩展P 即让P P C 2 如果 否 则 输出与当前前缀P相对应的码字 将P C添加到词典中 步骤4 判断码字流中是否还有码字要译 1 如果 是 就返回到步骤2 2 如果 否 把代表当前前缀P的码字输出到码字流 结束 LZW编码举例 输入数据流 编码过程 1 初始化串表 将A B C单个字符存入串表中 并分别赋予三个码字值1 2 3 并置当前前缀P 下面将输入字符串的字符从左到右逐个输入到编码器 2 输入第一个字符A 即C A 由于P C A已在串表中 所以前缀P P C A 输入第2个字符B 即C B 字符串P C AB 由于串表中没有字符串AB 所以 由于B是字符串AB的扩展字符 A是前缀 将前缀A的码字1输出 将AB加入串表中 并依次赋予AB串的码字为4 令P B 输入第3个字符B 即C B 字符串P C BB 由于串表中没有字符串BB 所以 由于B是字符串BB的扩展字符 B是前缀 将前缀B的码字2输出 将BB加入串表中 并依次赋予BB串的码字为5 令P B 输入第4个字符A 即C A 字符串P C BA 由于串表中没有字符串BA 所以 由于A是字符串BA的扩展字符 B是前缀 将前缀B的码字2输出 将BA加入串表中 并依次赋予BA串的码字为6 令P A 输入第5个字符B 即C B 字符串P C AB 由于串表中有字符串AB 所以前缀P P C AB 输入第6个字符A 即C A 字符串P C ABA 由于串表中没有字符串ABA 所以 由于A是字符串ABA的扩展字符 AB是前缀 将前缀AB的码字4输出 将ABA加入串表中 并依次赋予ABA串的码字为7 令P A 输入第7个字符B 即C B 字符串P C AB 由于串表中有字符串AB 所以前缀P P C AB 输入第8个字符A 即C A 字符串P C ABA 由于串表中有字符串ABA 所以前缀P P C ABA 输入第9个字符C 即C C 字符串P C ABAC 由于串表中没有字符串ABAC 所以 由于C是字符串ABA的扩展字符 ABA是前缀 将前缀ABA的码字7输出 将ABAC加入串表中 并依次赋予ABAC串的码字为8 令P C 最后将前缀C的码字值3输出 根据上述LZW编码算法的规则 LZW编码的解码过程也不难理解了 只要有一张字符串表 由解码器根据编码字串逐一翻译即可 输出码字值串 122473解码后的字串 ABBABABAC LZW是一种通用的压缩方法 可用于任何二值数据文件的压缩 它也是目前最为流行的一种数字图像压缩方法 假设将一幅图像从左向右 从上向下扫描得到的序列为0 255 0 255 255 0 255 0 255 0 0 0 0 0 0 0 用LZW编码得到的输出码字是什么