Digital Image Processing数字图像处理第七章 数字图像编码数字通信系统模型信源 信源编码 信道编码 调制传输信道噪声解调信道解码信源解码信宿2图像 /视频压缩可行性 “ 冗余 ” 来自哪里 ?统计特性冗余时间空间信息熵心理视觉冗余人眼敏感知识去除冗余主要技术 去除时间冗余帧间预测编码 去除空间冗余帧内预测编码变换编码 去除视觉冗余量化 去除编码冗余熵编码 相对信息率 ： η = H / Hmax 冗余度 ： γ = 1-η冗余度越小，表明 平均每个符号的实际信息荷载量越接近饱和，编码的效率越高mHPPH imii 2m a x21l o gl o g 定义信源的相对信息率和冗余度如下：图像编码基本模型映射器 量化器 符号编码器 映射器 ：减少像素间的冗余，如进行行程编码、 DCT变换等（ MM） 量化器 ：减少视觉心理冗余，仅用于有损压缩（ M S） 符号编码器 ：减少编码冗余，如使用Huffman编码（符号 /符号串 二进制码）8第 7章数字 图像编码(第 2讲 )7.2 无损压缩7.2.1 基于字典的压缩7.2.2 统计编码7.2.3 无损预测编码7.2.1 基于字典的压缩行程编码Run Length Encoding， RLE 概念：行程 ：具有相同灰度值的像素序列 。
编码思想：用行程的 灰度 和 长度 代替行程本身例：设重复次数为 Ci, 重复像素值为 Pi编码为： CiPi CjPj CkPk编码前： aaaaaaabbbbbbcccccccc编码后： 7a6b8c12对下面的图像分别按照行扫描和列扫描顺序进行一维行程编码，哪个效率更高？f(x,y)= [ ]4 4 4 4 4 4 4 45 5 5 5 5 5 5 56 6 6 6 6 6 6 67 7 7 7 7 7 0 06 6 6 6 6 0 0 05 5 5 5 5 5 5 04 4 4 4 0 0 0 00 0 0 0 0 0 0 0 分析：对二维图像数据采用一维行程编码时 ，不同的扫描顺序会影响编码效率对于有大面积色块的图像 ， 压缩效果好对于细节较多的纷杂图像 ， 压缩效果不好 ， 最坏情况下 ， 会加倍数据量7.2 无损压缩7.2.1 基于字典的压缩7.2.2 统计编码7.2.3 无损预测编码 Huffman编码（ 1） 基本思想减少编码冗余基本思想是统计一下符号的出现概率 ， 建立一个概率统计表 ， 将 最常出现 (概率大 )的符号用最短的编码 ， 最少出现 (概率小 )的符号用最长的编码 。
7.2.2 统计编码（ 2） 算法实现可用下述步骤编出霍夫曼码：第一步，把信源Ｘ中的消息按出现的概率从大到小的顺序排列 ;Mpppp 32116第二步 ， 把最后两个出现概率最小的消息合并成一个消息 ， 从而使信源的消息数减少一个 ， 并同时再次将信源中的消息的概率从大到小排列一次 ;17第三步，重复上述步骤，直到信源 的消息数减少到两个 为止第四步，将被合并消息的两个部分分别赋以 1和 0（或 0和 1）180 . 4 0 . 3 0 . 1 0 . 1 0 . 0 6 0 . 0 4a 2 a 6 a 1 a 4 a 3 a 51 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 10.10.20.30.61（ 3） 例子1111100000首先建立概率统计表和编码树符号 概率 1 2 3 4a2 0.4 0.4 0.4 0.4 0.6a6 0.3 0.3 0.3 0.3 0.4a1 0.1 0.1 0.2 0.3a4 0.1 0.1 0.1a3 0.06 0.1a5 0.04符号 概率 编码 1 2 3 4a2 0.4 1 0.4 1 0.4 1 0.4 1 0.4 1a6 0.3 00 0.3 00 0.3 00 0.3 00 0.6 0a1 0.1 011 0.1 011 0.2 010 0.3 01a4 0.1 0100 0.1 0100 0.1 011a3 0.06 01010 0.1 0101a5 0.04 01011然后给二叉树各分支赋值 0/1Huffman码特点 :1. 变长码 ：出现概率越大的符号 ， 码长越短；2. 任一符号的码字 不会是 其他符号码字的 前缀 。
解码过程：010100111100…01010, 011, 1, 1, 00, …a3, a1, a2 ,a2, a6, …a 2 a 6a 1 a 4 a 3 a 51 0 00 1 1 0 1 0 0 0 1 0 1 00 1 0 1 1平均码长 ：各个符号编码使用的 bit数 (码长 )的数学期望(复习 )信息熵：紧致码 ： R 接近 Himii PR 1(4) 编码效率的评价imii PPH 21l o g前面的例子中符号串的信息熵为 :14.2)04.0(l o g04.0)06.0(l o g06.0)1.0(l o g1.0)1.0(l o g1.0)3.0(l o g3.0)4.0(l o g4.0l o g22222221 imiiPPH符号 a2 a6 a1 a4 a3 a5概率 0.4 0.3 0.1 0.1 0.06 0.04平均码长为 :比特20.2)5(04.0)5(06.0)4(1.0)3(1.0)2(3.0)1(4.01 imiiPR 符号 a2 a6 a1 a4 a3 a5概率 0.4 0.3 0.1 0.1 0.06 0.04码字 1 00 011 0100 01010 01011码长 1 2 3 4 5 5 注意：平均码长是用“数学期望 ‖定义的，不是取“平均值 ‖。
Huffman编码得出的码字不是唯一的：（ i） 0/1 赋值规则不同（ ii）存在等概率符号时，合并方法不同0 . 4 0 . 30 . 1 0 . 1 0 . 0 6 0 . 0 40 . 10 . 20 . 30 . 611111100000a 2 a 6a 1 a 4 a 3 a 51 0 10 0 1 0 0 0 1 0 0 0 0 10 0 0 0 0(i) 0/1 赋值不同符号 a2 a6 a1 a4 a3 a5码字 2 1 01 001 0001 00001 00000码长 2 1 2 3 4 5 5码字 1 1 00 011 0100 01010 01011码长 1 1 2 3 4 5 5此时各个符号的码字长度没有变化 此时各个符号的码字长度可能变化 ，例如给下面的符号串编码：―eeabeabeabeabeabeabeabeabecdecdecdecdeee‖，首先统计各符号出现频次a b c d e8 8 4 4 16(ii) 合并规则不同编码 1 编码 2符号 e a b c d出现概率 0.4 0.2 0.2 0.1 0.1编码 1码字 1 000 01 0010 0011码长 1 3 2 4 4均值 =1.8, 平均码长 =2.2编码 2码字 00 10 11 010 011码长 2 2 2 3 3均值 =1.4, 平均码长 =2.2符号 e a b c d出现频次 16 8 8 4 4编码 1码字 1 000 01 0010 0011码长 1 3 2 4 4频次 x 码长 16 24 16 16 16编码 2码字 00 10 11 010 011码长 2 2 2 3 3频次 x 码长 32 16 16 12 12虽然两种编码方法的结果不同，但这两种编码所表达的符号串使用的总 bits数目是相同的 : 16+24+16+16+16+16=32+16+16+12+12=88。
因此，我们认为两种编码方法的编码压缩效能是一样的 5） Huffman编码分类 静态编码在压缩之前就建立好一个概率统计表和编码树 算法速度快 ， 但压缩效果不是最好 动态编码对每一幅图像 ， 临时建立概率统计表和编码树 算法速度慢 ， 但压缩效果好 7.2 无损压缩7.2.1 基于字典的压缩7.2.2 统计编码7.2.3 无损预测编码7.2.3 无损预测编码（ 1） 编码思想 认为相邻像素的信息有较大相关性 当前像素值可用以前的像素值来获得 用当前像素值 fn ， 通过预测器得到一个预测值 fn， 对当前值和预测值求差 ， 对 差值 编码 ， 作为压缩数据流中的下一个元素 由于差值比原数据要小 ， 因而编码要小 ， 可用变长编码 大多数情况下 ， fn的预测是通过 m个以前像素的线性组合来生成的 :即： mfn = round [ i fn-i ]i=1例如 ， 在行预测 (一维线性预测 ) 编码中： mfn(x,y) = round [ i f(x, y-i) ]i=1round为取最近整数 ， i为预测加权系数 (可为1/m)， y是行变量 。
前 m个像素不能预测 ， 可用 Huffman编码(2) 无损预测编码流程第一步：压缩头处理第二步：对每一个符号： f(x,y)， 由前面的值 ， 通过预测器 ， 求出预测值 f(x,y)第三步：求出预测误差e(x,y) = f(x,y) - f(x,y)第四步：对误差 e(x,y)编码 ， 作为压缩值重复二 、 三 、 四步举例： mfn = round [ i fn-i ]i=1F = {154,159,151,149,139,121,112,109,129}m = 2 = 1/2预测值 f3 = 1/2 * (154 + 159) 156 e3 = 151 - 156 = -5f4 = 1/2 * (159 + 151) = 155 e4 = 149 – 155 = -6f5 = 1/2 * (151 + 149) = 150 e5 = 139 – 150 = -11f6 = 1/2 * (149 + 139) = 144 e6 = 121 – 144 = -23f7 = 1/2 * (139 + 121) = 130 e7 = 112 – 130 = -18f8 = 1/2 * (121 + 112) 116 e8 = 109 – 116 = -7f9 = 1/2 * (112 + 109) 110 e9 = 129 – 110 = 19 无损预测编码+ 符号编码预测器压缩图像输入图像enfnfn－(3) 解码第一步：对头解压缩第二步：对每一个预测误差的编码解码 ， 得到预测误差 e(x,y)。
第三步：由前面的值 ， 得到预测值 f(x,y)第四步：误差 e(x,y)， 与预测值 f(x,y)相加得到解码 f(x,y)重复二 、 三 、 四步 无损预测解码+符号解码预测器解压缩图像压缩图像en fnfn7.3 有损编码7.3.1 量化器7.3.2 有损预测编码7.3.3 变换编码7.3.1 量化器 有损压缩是通过牺牲图像的准确率来提高压缩率 ， 容忍解压缩后的结果中有一定的误差 有损压缩方法通常在图像压缩比大于 30：1时仍然能够重构图像 无损压缩的压缩比很少有能超过 3： 1的 这两种压缩方法的 根本差别在于有没有量。