电子科技大学光电信息学院 ，二教106，沙河校区

Presentation on theme: "电子科技大学光电信息学院 ，二教106，沙河校区"— Presentation transcript:

1 电子科技大学光电信息学院 2017.05.09，二教106，沙河校区
第六章 图像编码与压缩 Chapter06 Image coding and compression 彭真明 电子科技大学光电信息学院 ，二教106，沙河校区

2 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

3 一、编码及信息论概述 1.图像压缩的必要性 一幅512×512的灰度图像的比特数为： 512×512×8 = 2,097,152 bit
= 262,144 byte = 256 k。 可见，数字图像通常要求很大的比特数，这给图像的传输和存储带来一定的困难。要占用很多的资源，花很高的费用。

4 一、编码及信息论概述 1.图像压缩的必要性 一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R、G、B三分量分别占8 bit，总比特数为： 90×60×24×3×512×512×8bit = 97,200 (M) 若一张CD光盘可存600兆字节数据，这部电影图像（不包括声音）就需要160张CD光盘用来存储。

5 一、编码及信息论概述 编码 用符号数码元素表示信号、消息或事件的过程。 图像编码
研究图像数据的编码方法。期望用最少的码字表示信源发出的图像信号，使数据得到压缩，减少图像数据占用的信号空间和能量，降低信号处理的复杂程度。 信号空间 物理空间—存储器、磁盘等数据存储介质； 时间空间—传输给定消息集合所需要的时间； 频谱空间—传输给定消息集合所需要的带宽。

6 一、编码及信息论概述 2.图像压缩的可能性 图像中像素灰度出现的不均匀性，造成图像信息冗余，即用同样长度比特表示每一个灰度，则必然存在冗余。
图像能量在变换域内分布的不均匀性，比如大部分能量集中在低频部分，而小部分能量集中在高和较高的频率部分。 图像像素灰度在时间和空间上的相关性造成信息冗余。

7 一、编码及信息论概述 数据冗余 空间冗余，邻近像素灰度分布的相关性很强； 频间冗余，多谱段图像中各谱段图像对应像素之间灰度相关性很强；
时间冗余，序列图像帧间画面对应像素灰度的相关性很强。

8 例析1： 如果用8 bit表示下面图像的像素，可以说该图像存在着编码冗余。 因为该图像的像素只有两个灰度，用1 bit即可表示。

9 例析2： 对于一幅图像，很多单个像素对视觉的贡献是冗余的。这可以建立在对邻域值预测的基础上。 例如： 原图像数据：
压缩后数据： 40bit 14bit

10 一、编码及信息论概述 应用环境允许图像有一定程度失真 (1) 接收端图像设备分辨率较低，则可降低图像分辨率；
(2) 根据人的视觉特性，对不敏感区进行降分辨率编码（视觉冗余）； (3) 应用方关心图像区域有限，可对其余部分采用空间和灰级上的粗化； (4) 对于识别，图像特征抽取和描述也是数据压缩。

11 例析1： 视觉心理冗余 一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。 33K 15K

12 一、编码及信息论概述 3. 图像编码分类 无失真编码（无损压缩、可逆压缩）是一种经编、解码后图像不会产生失真的编码方法。可重建图像，但压缩比不大； 有失真编码（有损压缩、不可逆压缩）解码时无法完全恢复原始图像，压缩比大但有信息损失。 失 真：原图像与解码输出图像之间的随机误差； 压缩比：原图像比特数与压缩后图像比特数之比。

13 一、编码及信息论概述 图像压缩方法 统计编码 预测编码 变换编码 行程编码 ＬＺＷ编码 哈夫曼编码 算术编码 其他 无损预测 有损预测 其他
ＫＬＴ编码 ＤＣＴ变换 其他 无损压缩 有损压缩

14 一、编码及信息论概述 信源的定义 信源即能够产生信息的事物。 数学上，信源是一概率场。
若信源可能产生的信息是　　　 ，这些信息出现的概率分别是　　　　　 。 则该信源可表示为：

15 一、编码及信息论概述 4. 信息量和熵 信息量：从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为信息量。
例如：要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量(二进制位)。 这里共需5次，因此所需的信息量为：

16 一、编码及信息论概述 信息量的计算 熵的计算 从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。
设信源符号表为s={s1, s2, … , sq}，其概率分布为P(s)={p(s1), p(s2), … , p(sq)}，则信源的熵为：

17 一、编码及信息论概述 熵的作用 例：信源 熵表示信源中消息的平均信息量。在不考虑消息间的相关性时，是无失真编码平均长度比特数的下限。
H(s) = 说明：该信源编码平均码长最短情况下为7/4，不能再小，否则就会引起错误。而平均码长比此数大许多时，就表明压缩还有待改进。

18 一、编码及信息论概述 熵的性质 (1) 熵是一个非负数，即总有H(s)≥0。
(2) 当其中一个符号sj的出现概率p(sj)=1时，其余符号si(i≠j)的出现概率p(si) =0，H(s)=0。 (3) 当各个si出现的概率相同时，则最大平均信息量为log2 q。 (4) 熵值总有，H(s) ≤ log2 q。

19 一、编码及信息论概述 图像的熵 (1) s作为灰度，共q级，出现概率均等时，p(si)=1/q，
(2)当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1 ，其熵：

20 一、编码及信息论概述 图像的熵 (3) 对８位图像，s作为灰度，共256级，其熵为：
(4)当图像由单一灰度级组成时（即灰度均匀分布图像）, 其熵为：

21 一、编码及信息论概述 5.信息编码过程 编码器是用符号集中的符号构成输出代码，并建立输入信号单元与输出代码的对应关系。 编码器 输出代码
消息集合 输出代码 符号集 符号(码元) 编码器

22 一、编码及信息论概述 6.无失真编码定理 L=H(s)+ε
Claude Shannon ( ) 6.无失真编码定理 在无干扰条件下，存在一种无失真的编码方法，使编码的平均长度L与信源的熵H(s)任意地接近，即 L=H(s)+ε 其中， ε为任意小的正数。以H(s)为其下限，L≥ H(s)，即香农(Shannon)无干扰编码定理。 

23 一、编码及信息论概述 压缩率 若原始图像的平均比特率为b，编码后的平均比特率为bd，则压缩率(比)C定义为：
由Shannon定理，无失真编码最大数据压缩比为：

24 一、编码及信息论概述 编码效率 冗余度 压缩率(比) or R接近于0，或编码效率接近于1的编码称为高效码。 Next Sect...

25 一、编码及信息论概述 保真度(Fidelity) 主观 客观 总误差(Total error between the two images)
均方差(MSE) 客观 信噪比(SNR) Signals Noises

26 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介 统计编码

27 二、行程编码 1. 概念： 行程：沿行(或列)具有相同灰度值的像素序列。 2. 编码思想：
行程编码(Run Length Encoding，RLE)是一种消除空间冗余的数据压缩方法。 1. 概念： 行程：沿行(或列)具有相同灰度值的像素序列。 2. 编码思想： 去除空间像素冗余。即用行程的灰度和行程的长度代替行程本身。

28 二、行程编码 例：设重复次数为 iC, 重复像素值为 iP，则 编码为：iCiP iCiP iCiP 编码前：aaaaaaabbbbbbcccccccc 编码后：7a6b8c 对于有大面积色块的图像，压缩效果很好。 对于杂乱图像，压缩效果不好；最坏情况，会加倍数据。 Next Sect...

29 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

30 三、LZW编码 1. 简介 1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用较短的符号标记替代冗余字符的概念，即LZ压缩技术。 1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,即LZW压缩技术。 LZW编码又称字串表编码，是一种无损编码。与行程编码类似，也是对字符串进行编码实现压缩，但它在编码的同时还生成了特定字符串及与之对应的索引字符串表。

31 三、LZW编码 2. 基本思想 —去除像素冗余。 (1) 在压缩过程中动态地形成一个字符序列表(字典)。 (2) 具体规则如下：
(a) 每当压缩扫描图像发现一个字典中没有的字符序列，就把该字符序列存到字典中； (b) 用字典的地址（编码）作为这个字符序列的码字，替换原图像中的字符序列； (c)下次再碰到相同的字符序列，就用字典的地址代替字符序列。

32 三、LZW编码 3.基本步骤 步骤1：将词典初始化为包含所有可能的单字 字符，当前前缀P初始化为空(NULL)。
步骤2：当前字符C:=字符流中的下一个字符。

33 三、LZW编码 步骤3：判断P＋C是否在词典中? （1）如果“是”，则用C扩展P，即让P:=P＋C （2）如果“否”，则
令P:=C，现在的P仅包含一个字符C

34 三、LZW编码 步骤4：判断码字流中是否还有码字要译? （1）如果“是”，就返回到步骤2； （2）如果“否”
把代表当前前缀P的码字输出到码字流； 结束。

35 LZW编码例析 如：对字符串“aabcabbbbd” 进行编码 初始化字符串表 字符串 索引(16进制) a 0 H b 1 H c 2 H
LZW_CLEAR（初始化标记） 4 H LZW_EOI （结束标记） 5 H

36 LZW编码例析:“aabcabbbbd”
输入数据S2 S1+S2 输出结果 S1 生成的新字符串及索引 NULL NULL 4H NULL S1+S2在字符表中,S1=S1+S2 a a a S1为NULL,故输出结果为空 a aa 0H a aa <6H> S1+S2不在字符表中,S1=S2=“a” b ab 0H b ab <7H> aa不存在,故输出S1=“a”的索引0H c bc 1H c bc <8H> a ca 2H a S1+S2不在字符表中,S1=S2=“b” ca <9H> ab不存在,故输出S1=“a”的索引0H b ab ab b abb 7H b abb <AH> S1+S2在字符表中,S1=S1+S2 b bb 1H b bb <BH> S1+S2结果已存在,故输出结果为空 bb bb b d bbd BH d 输出S1的索引3H bbd <CH> 3H 输入 结束 5H 输出LZW_EOI标志的索引 Next Sect...

37 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介

38 四、霍夫曼(Huffman)编码 1. 简介 霍夫曼(Huffman)编码是可变字长编码(Variable length coding，VLC)的一种。 该方法由Huffman(1952)提出，它完全依据字符出现概率来构造异字头的平均长度最短的码字，常被称作Huffman编码，有时称之为最佳编码。

39 四、霍夫曼(Huffman)编码 2. 基本思想 通过减少编码冗余来达到数据压缩的目的。 规定：
(b) 建立一个概率统计表。 规定： 将最常出现(概率大的)的符号用最短的编码；最少出现的符号用最长的编码。

40 例析1：Huffman编码 例题：信号源 s={s1, s2, s3, s4, s5, s6}，其概率分布为p1=0.4, p2=0.3, p3=0.1, p4=0.1, p5=0.06, p6=0.04，求最佳Huffman码。 计算步骤： 将信源符号按出现概率从大到小排成一列，然后把最末尾的两个符号的概率相加，合成一个概率。

41 例析1：Huffman编码 把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。
重复上述做法，直到最后剩下两个概率为止。 从最后一步剩下的两个概率开始逐步向前编码，每步只需对两个分支各赋予一个二进制码。例如，对概率大的赋予码元0，对概率小的赋予码元1。

42 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 自然码 000
001 010 011 100 101

43 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4

44 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1

45 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3

46 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4

47 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1

48 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S1 = 1

49 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S2 = 00

50 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S3 = 011

51 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S4 = 0100

52 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S5 = 01010

53 例析1：Huffman编码 输入 S1 S2 S3 S4 S5 S6 概率 0.4 0.3 0.1 0.06 0.04 第①步 0.4
第②步 0.4 0.3 0.2 0.1 第③步 0.4 0.3 第④步 0.6 0.4 1 1 1 1 1 S6 = 01011

54 例析1：Huffman编码 平均码长 自然码长m = 3 信源的熵 压缩结果
L = 0.4×1+0.3×2+0.1×3+0.1×4+0.06× ×5 ≈ 2.2 (bit/像素) 信源的熵 H(s) = -(0.4×log2(0.4)+0.3×log2(0.3)+0.1×log2(0.1) +0.1×log2(0.1) +0.06×log2(0.06)+0.04×log2(0.04)) ≈ 2.14 (bit/像素) 压缩结果 压缩比(C)： = m / L = 3 /2.2 ≈ 编码效率(η)： = H(s) / L = 2.14/2.2 ≈ 97.3% 冗余度(R)： = 1 - η ≈ = 2.7 %

55 例析2：Huffman编码 例如，对下面的一首英文歌词进行Huffman编码：
Because I’m bad, I am bad — come on Bad, bad — really, really bad You know I’m bad, I'm bad — Bad, bad — really, really bad You know I’m bad, I'm bad — come on, you know Bad, bad — really, really bad

56 例析2：Huffman编码 短语及其概率统计表 短语 符号 频率 概率 Because B 1 1/35 = 0.03 I’m I 6
1/35 = 0.03 I’m I 6 6/35 = 0.17 Bad 15 15/35= 0.43 Come on C 2 2/35 = 0.06 It Really R 6/35 = 0.17 You know Y 4 4/35 = 0.11

57 编码过程的树结构表示 (1.00) S6 (0.57) 1 S5 01 (0.23) B/0.43 (Bad) 00 S3 (0.34)
(0.57) 1 S5 01 (0.23) B/0.43 (Bad) 00 S3 (0.34) 010 (0.12) S4 011 S2 0100 001 (0.06) 000 Y/0.11 (You know) 0101 S1 I/0.17 (I’m) R/0.17 (Really) 01000 C/0.06 (Come on) 01001 B/0.03 (Because) I/0.03 (It)

58 例析2：Huffman编码 短语、码长及编码结果统计表 短语 符号 频率 概率 代码长度 编码 Because B 1 0.03 5
01001 I’m I 6 0.17 3 001 Bad 15 0.43 Come on C 2 0.06 4 0101 It 01000 Really R 000 You know Y 0.11 011

59 例析2：Huffman编码 平均码长： 信源的熵： C, η, R =
L = 0.03*5+0.17*3+0.43*1+0.06*4+0.03*5+0.17* *3 = 2.32 信源的熵： H(s) = -(0.03*log2(0.03)+0.17*log2(0.17) +0.43*log2(0.43) + 0.06*log2(0.06)+0.03*log2(0.03) +0.17*log2(0.17) + 0.11*log2(0.11)) = 2.29 C, η, R = 编码前：35×log27 = 98.3, 编码后：81位 压缩比：98.3 /81 ≈ 。 Next Sect...

60 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

61 五、预测编码 预测编码 属于时间域 (Time domain)的编码方法。
基本思路：利用前面已经出现过的符号来预测当前的符号，然后将实际上的符号与预测相减得到预测误差值。 预测编码的好处在于预测误差值的范围比原信号的数字范围小，如果预测足够精确的话。 通常,会对预测误差值进一步编码（Quantization）。 可分为有损和无损预测，但预测本身不会造成失真。

62 五、预测编码 1.无损预测编码(Lossless Predictive Coding) 基本思想 去除像素冗余。
认为相邻像素的信息有冗余。当前像素值可以用先前的像素值来获得。 用当前像素值fn，通过预测器得到一个预测值 ，对当前值和预测值求差。对差编码，作为压缩数据流中的下一个元素。

63 五、预测编码 例如：利用前1个像素进行预测 100 102 101 103 100 2 -1 1 -2 3 -3 原像素值 预测值

64 五、预测编码 预测原理 一般情况下，利用前m个像素的线性组合来预测，即 预测器为：
其中，round为取最近整数，i为预测系数(可为1/m)，y是行变量。 注意：前m个像素不能用此法编码，可用哈夫曼编码。

65 例析：预测编码 预测值：

66 五、预测编码 (2) 编码步骤 如Huffman编码 预测器设计 第①步：压缩头处理。 第②步：预测值。 第③步：求预测误差值。
第④步：对误差e(x,y)编码，作为压缩值。 重复执行 ② 、 ③ 、 ④步。

67 五、预测编码 (3) 编码原理图 预测器 最接近 的整数 + - 符号 编码 压缩图像 输入图像 en fn 

68 五、预测编码 2. 有损预测编码 有损预测编码（Lossy Predictive Coding，LPC） 基本概念 量化器 编码原理

69 五、预测编码 (1) 基本概念 有损压缩： 压缩比： 有损与无损压缩的本质区别在于有没有量化器模块。
通过牺牲图像的准确率来达到增大压缩率的目的。 如果容忍解压后的结果中有一定的误差，那么压缩率可以显著提高。 压缩比： 在图像压缩比大于30:1时，仍然能够重构图像。 在图像压缩比为10:1到20:1时，重构图像与原图几乎没有差别。 无损压缩的压缩比很少有能超过3:1的（Why ?）。 有损与无损压缩的本质区别在于有没有量化器模块。

70 五、预测编码 数据源编/解码的一般模型 编码模型 映射器 量化器 编码器 解码模型 符号 解码器 反向 映射器

71 五、预测编码 (2) 量化器 减少数据量的最简单的办法是将图像量化成较少的灰度级，通过减少图像的灰度级来实现图像的压缩；
(2) 量化器 减少数据量的最简单的办法是将图像量化成较少的灰度级，通过减少图像的灰度级来实现图像的压缩； 这种量化是不可逆的，因而解码时图像有损失。 例如： 如果输入是256个灰度级，对灰度级量化后输出，只剩下4个层次，数据量被大大减少，但这个过程是不可逆的。

72 五、预测编码 量化器的定义 阶梯形量化函数 t = q(s)，是一个s的奇函数（即q(-s) =-q(s)），它可以通过L/2、si和ti来完全描述。 si 被称为量化器的决策级（阈值）； ti 被称为量化器的重构级（代表级）。 L：是量化器的级数。 由于习惯的原因，si被认为是映射到ti，如果它在半开区间(si,si+1]。

73 五、预测编码 s1 s2 t 量化器的定义 t = q(s) t2 t1 s output t(L/2) 重构级(代表级)
S-[(L/2)-1] t1 s s1 s2 S(L/2)-1 input 决策级(阈值) -t(L/2) 注：量化的对象可能是负数

74 五、预测编码 (3)算法演变——无损到有损 基本思想：对无损预测压缩的误差进行量化，通过消除视觉心理冗余，达到对图像进一步压缩的目的。
—— 引入量化 (Quantification)

75 五、预测编码 编、解码原理及过程 无损预测 将en量化： 用： 近似： 编码： 解码：

76 五、预测编码 编码流程 + - 符号 编码 预测器 压缩图像 输入图像 en fn  量化器 ên

77 五、预测编码 解码流程 压缩图像 + + 符号 解码 预测器 解压图像 fn  fn ên

78 五、预测编码 编码方案的修正 fn fn 编码 解码
预测器 预测器 fn fn

79 五、预测编码 编码方案的修正 输入图像 fn + - en ên 符号 编码 压缩图像 量化器 预测器  fn + + fn

80 五、预测编码 DPCM简介 差分脉冲编码调制(Differential Pulse Code Modulation, DPCM)，采用反馈方法预测估值。 1950年，卡特勒申请专利; 1952年，获得批准; 1958年，格雷厄姆（Graham)开始计算机模拟研究编码方法； 1966年，奥尼尔（O’Neal)对电视信号预测编码进行理论分析以及计算机模拟； 1971年投入使用。

81 五、预测编码 DPCM编码原理图 量化器 编码器 解码器 预测器

82 五、预测编码 量化器 预测器 一般是一个小于1的预测系数。

83 例析：DPCM 例如：量化器 设：  = 6.5 ‘e +6.5 e -6.5

84 例析：DPCM 例如： = 1， = 6.5 计算：两个像素 f0 =14、f1 =15，则： (预测结果) (预测误差) (预测误差)
(重构结果) (重构误差)

85 例析：DPCM 输入 编码 解码 误差 n f ^f e e f ^f f f-f
输入 编码 解码 误差 n f ^f e e f ^f f f-f

86 五、预测编码 可以是固定的，也可以是自适应的；可以是线性的，也可以是非线性的。 预测器设计得越好，对输入的数据压缩就越多。
3. 预测器的一般模型 可以是固定的，也可以是自适应的；可以是线性的，也可以是非线性的。 预测器设计得越好，对输入的数据压缩就越多。

87 预测器模型 一维线性预测

88 预测器模型 (1) 最佳线性预测 选ak，使σ2d(n)最小。设x(n)是广义平稳的，且e(n)均值为0，则

89 预测器模型 假设x(n)是各态遍历的，且训练样本数N相当大，则x(n)的自相关函数 上式写成矩阵形式：

90 预测器模型 (2) 自适应线性预测 若x(n)是非平稳的，或是分段近似广义平稳，则可采用边送数据边测量与估计x(n)的自相关函数，求出相应的最佳预测系数。 随之，相应的最佳预测系数随着x(n)的统计特性的变化而变化，这就是自适应线性预测。

91 预测器模型 二维线性预测 原始图像用f (m,n)表示： 预测的差值定义为： 这里Z为对像素f (m,n)进行预测的相关点的集合。

92 预测器模型 方程的解 a1, a2, …, am 是 一组最佳的预测系数。压缩效果可用方差σ2e(n)来衡量，即：
原始序列相关性越强， R(k)越大，σ2e(n)越小，压缩效果越显著；原始序列互不相关，即R(k) =0，k≠0，则，σ2e(n)= σ2x(n)一点也不能压缩。 Next Sect...

93 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

94 六、变换编码 1. 变换编码的基本思想 用一个可逆的、线性的变换(如FFT、DCT)，把图像映射到变换系数集合;
对该系数集合进行量化和编码; 对于大多数自然图像，重要系数的数量是比较少的。因而可以用量化(或完全抛弃)，且仅以较小的图像失真为代价。

95 例析：DCT编码 例如： 原图像 DCT变换系数

96 2018/9/18 例析：DCT编码 DEMO dctdemo.m

97 六、变换编码 编码/解码流程图 输入图像N×N 压缩 图像 构造n×n 的子图 正变换 量化器 符号 编码器 符号 解码器 逆变换
压缩图像 解压图像

98 六、变换编码 构造n×n的子图 N n×n n×n n×n n×n N n×n n×n

99 六、变换编码 2.变换编码的基本原理 将FFT逆变换表达式进行改写： F(u,v) 记为：T(u,v)
exp[j2(ux+vy)/N] 记为：H(x,y,u,v) 变换编码，即要用等式的右部近似原图像。

100 六、变换编码——基本理论 进一步改写： 其中： (1) F是一个包含了f(x,y)的象素的n×n的矩阵；
(2) Huv的值只依赖坐标变量x,y,u,v，与T(u,v)和f(x,y) 的值无关，被称为基图像。

101 六、变换编码——基本理论 基图像Huv Huv可以在变换前一次生成，对每一个 n×n的子图变换都可以使用。

102 六、变换编码——基本理论 变换系数截取模板 通过定义变换系数截取模板函数，消去冗余。 对于： 近似： 1 1 1 1 0 0 0 0
对于： 近似：

103 六、变换编码——基本理论 误差评估 其中，||F –^F||是矩阵范数，2T(u,v)是变换在(u,v)位置上的系数方差。

104 六、变换编码——基本理论 小结 (1) 总的近似均方误差是丢弃的变换系数的方差之和（也即对于m(u,v) = 0的系数方差之和）。
(2) 能把大多数信息封装到最少的系数里去的变换，可得到最好的子图像的近似，同时重构误差也最小。 (3) 在等式成立的假设下，一个N×N的图像的(N/n)2个子图像的均方误差是相同的。因此，N×N图像的均方误差（平均误差的测量）等于一个子图像的均方误差。

105 六、变换编码 3. 几个关键问题 变换的选择 变换的评价 子图尺寸选择 压缩位分配（编码）

106 六、变换编码——基本理论 变换的选择 (1) Karhunen-Loeve变换（KLT） (2) 离散傅立叶变换（DFT）
(3) 离散余弦变换（DCT） (4) Walsh-Hadamard变换（WHT） (5) 离散小波变换（DWT）

107 六、变换编码——几个关键问题 变换的评价 按信息封装能力排序： KLT，DCT，DFT，WHT，HaarT
KLT的基图像是数据依赖的，每次都要重新计算Huv，因而很少使用。 DFT的块效应严重。 DCT最常用，现已被国际标准采纳，作成芯片。其优点有：1) 基本没有块效应；2) 信息封装能力强，把最多的信息封装在最少的系数中。

108 六、变换编码——几个关键问题 子图尺寸选择 一般而言，随着n的增加，块效应相应减少。 选择原则：
如果n是子图的维数，n应是2的整数次方，便于降低计算复杂度； (2) n一般选为8×8或16×16，具 体可由试验得到。 一般而言，随着n的增加，块效应相应减少。

109 六、变换编码——几个关键问题 压缩位分配（编码） 定义：截取、量化、系数编码统称为位分配。 主要解决m(u,v)的设计、编码问题。
截取和量化一般有两种方法： 子带编码（固定模板）； 阈值编码（自适应编码）。

110 六、变换编码——几个关键问题 1) 子带编码 基本思想：所有子图像使用相同的编码模板。 1 1 1 1 1 0 0 0
可消去87.5%的系数的模板

111 六、变换编码——几个关键问题 (a) 大部分的信息包含在方差较大的变换系数中。 (b) 在(N/n)2个子图找出取方差较大的m个系数的位置。
每一个DCT变换系数被认为是一个随机变量； 该变量的分布可以在所有变换子图像的集合上进行计算。 (b) 在(N/n)2个子图找出取方差较大的m个系数的位置。 同时确定系数的坐标u和v； 对所有子图像，这m个系数的T(u,v)值是保留的，其他的T值被抛弃； m是一个可选常数。

112 六、变换编码——几个关键问题 算法的实现 计算模板：方差较大的地方置1，其它地方置0; 量化系数：如最优Lloyd-Max量化器等;
系数编码：有以下2种二进制位分配方法，即 系数被赋予相同数量的二进制位; 系数之间固定地分配一定的二进制位。

113 六、变换编码——几个关键问题 2) 阈值编码(自适应编码) if a(系数) > T(阈值) m(u,v) = 1
else m(u,v) = 0 由于其简单性，阈值编码是实际应用中经常使用的编码方法。

114 六、变换编码——几个关键问题 理论依据 取值较大的变换系数，在重构子图的质量中起的作用也最重要； 较大系数的分布随子图的不同而不同。

115 六、变换编码——几个关键问题 算法实现 ① 阈值选取，一般按以下3种途径： a. 所有子图使用相同全局阈值。
压缩率的大小由大于全局阈值的系数个数所决定。 b. 每个子图使用不同的阈值。 每个子图保留的系数的个数事先确定，即总保留N个最大的，称为N-最大化编码。对于每个子图同样多的系数被丢弃。因此，每个子图的压缩率是相同的，并且是预先知道的。

116 六、变换编码——几个关键问题 例如： c. 阈值作为子图系数位置的函数
所有子图使用同一个全局阈值模板，但阈值的选取，与系数的位置相关，阈值模板给出了不同位置上系数的相应阈值。 例如：

117 六、变换编码——几个关键问题 ② 系数编码 zig-zag排序 0 1 5 6 14 15 27 28
将系数按45度对角顺序展开成序列，得到有一个有长串为零的序列。 例如： 用RLE编码对上述序列编码。 zig-zag排序 Next Sect...

118 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

119 七、压缩标准简介 图像压缩标准 静止帧黑白、彩色压缩(JPEG) 连续帧单色、彩色压缩(MPEG)
JPEG —— Joint Photographic Experts Group MPEG —— Moving Picture Experts Group

120 (1) JPEG压缩标准 有三种压缩系统： (1)基线编码系统：面向大多数有损压缩的应用，采用DCT变换压缩。
(2) 扩展编码系统：面向递进式应用，从低分辨率到高分辨率逐步递进传递的应用。 (3)独立编码系统：面向无损压缩的应用，采用无损预测压缩，符号编码采用哈夫曼或算术编码。 一个产品或系统必须包括对基线系统的支持。

121 JPEG压缩标准 JPEG压缩流程 输入图像 压缩图像 压缩图像 解压图像 构造8x8 的子图 颜色空间 转换 零偏置 转换 DCT 正变换
量化器 符号 编码器 压缩图像 解压图像 符号 解码器 DCT 逆变换 颜色空间 转换 零偏置 转换 合成8x8 的子图

122 MPEG1/2/4/7标准 MPEG1/2/4/7标准由ISO/IEC制定的。
国际标准化组织 (International Organization for Standardization，ISO) 。 国际电工委员会 (International Electrotechnical Commission, IEC) ，正式成立于1906 年，属于非政府性国际组织，是世界上成立最早的专门国际标准化机构。

123 MPEG1/2/4/7标准 简介 MPEG的第一个成果MPEG-1于1992年推出，是VCD的基础。由于有限的352×288像素分辨率，MPEG-1只适用于家庭环境，获得的视频质量及数据率相当低。 1995推出MPEG-2。720×576的像素以及更高的分辨率大大提高了视频质量。 1999年12月发布了MPEG-4。 MPEG-7为多媒体内容描述接口标准。 从MPEG组织成立至今，其任务和方向都发生了很多变化。MPEG-1和MPEG-2已经是成熟的编码标准，现在的热点主要集中在MPEG-4 和 MPEG-7上。

124 MPEG1/2/4/7 MPEG1 编码技术 应用范围： 视频CD_ROM存储、视频消费。 DCT变换 前向、双向运动补偿预测
Zig-zag排序 霍夫曼编码、算术编码 每15帧至少要有一个I帧 编码技术

125 MPEG1/2/4/7 MPEG2 应用范围：数字电视、高质量视频、有线电视、视频编辑、视频存储。 编码技术 DCT变换
前向、双向运动补偿预测 zig-zag排序 霍夫曼编码、算术编码 每15帧至少要有一个I帧 编码技术

126 MPEG1/2/4/7 MPEG4 编码技术 应用范围：互联网、交互视频、移动通信。 DCT变换、小波变换 前向、双向运动补偿预测
zig-zag排序 脸部动画、背景编码 霍夫曼编码、算术编码 每15帧至少要有一个I帧 编码技术

127 MPEG1/2/4/7 MPEG7 1998年10月被提出，它的正式名称是“多媒体内容描述借口”。其用途非常广泛：即可用于存储(在线或离线)，也可应用于流式结构(如广播、将模型假如Internet)。还可用于实时或非实时环境下。

128 MPEG-7的应用领域 音视数据库的存储和检索； 广播媒体的选择（广播、电视节目）； 因特网上的个性化新闻服务； 智能多媒体；
教育领域的应用； 远程购物； 社会和文化服务； 调查服务 遥感； 监视； 生物医学应用； 建筑、不动产及内部设计等。

129 H.261/263/264 H.261/263 H.261/263标准是由CCITT(国际电话与电报咨询委员会)制定的。 CCITT现在被称为 ITU-T(国际标准化组织电讯标准化分部)，是世界上主要的制定和推广电讯设备和系统标准的国际组织.它位于瑞士的geneva。

130 H.261/263/264 H.261 编码技术 应用范围：ISDN视频会议。 DCT变换 前向运动补偿预测 zig-zag排序
脸部动画、背景编码 霍夫曼编码 编码技术 运动补偿

131 H.261/263/264 H.263 编码技术 应用范围：可视电话。 DCT变换 双向运动补偿预测 zig-zag排序 脸部动画、背景编码
霍夫曼编码 编码技术

132 H.261/263/264 H.264 H.264是ISO/IEC MPEG(运动图像专家组)与ITU-T(视频编码专家组)组成的JVT(联合视频组）提出的新视频编码标准，并于2003年5月确定为国际标准。 同时，还作为MPEG-4的PART10(称为为MPEG4 AVC)。

133 H.261/263/264 H.264 H. 264 视频编解码标准的压缩效率可以达到以往标准(如H. 263 或M PEG-4) 的1.5～2 倍，与H. 263标准相比, H. 264 采用了许多新技术， 如对4×4 点残差数据块进行整数变换L采用4×4 点整数变换, 计算复杂度低, 峰值信噪比(PSNR) 却只降低0. 02dB。 will be over…

134 主要内容 编码及信息论概述 行程编码 LZW编码 霍夫曼编码 预测编码 变换编码 压缩标准简介*

135 Thank you! Open the next … Optoelectronic Image Processing
Curriculum Group

136 本章作业 1、已知符号Ａ,Ｅ,Ｉ,Ｏ,Ｕ,Ｖ其出现的概率分别是0.1, 0.4, 0.06,0.1,0.04,0.3,对其进行霍夫曼编码，给出码字、码字的平均长度和编码效率。 2、考虑如下大小为4 ×8的图像： (1) 计算该图像的熵； (2) 用霍夫曼压缩该图像； (3)计算用霍夫曼编码能达到的压缩率和效率。

137 本章作业 3、编程练习：读取一幅512 ×512 ×8比特的单色Lena图像，完成以下步骤： 统计该图像的概率直方图，并画出直方图；
计算该图像的熵； 对其进行霍夫曼编码； 分别计算压缩率和冗余度。 请使用原图(lena512.jpg)

138 Terms Image compression:图像压缩 Image coding:图像编码 Encoding: 编码
Decoding: 解码，译码 Cryptography: 密码学 Decompression: 解压 Encoder: 编码器 Decoder: 解码器 Redundant: 冗余的 Irrelevant: 不相干的

139 Terms Compression ratio: 压缩比
Dictionary-based encoding techniques: 基于字典的编码技术 Statistical encoding method: 统计编码方法 Lossless image compression: 无损图像压缩 Reversible encoding: 可逆编码 Error-free encoding: 无误差编码 Information preserving encoding: 信息保持编码 Encoding model: 编码模型 Information: 信息

140 Terms Source of messages: 信源，消息源 Memoryless source of messages: 无记忆信源
Memory source of messages: 有记忆信源 Entropy: 熵 Lossy image compression: 有损图像压缩 Fidelity: 保真度 Huffman coding:霍夫曼编码 B code: B码 Shift code: 移位码 Run: 行程

141 Terms Run length encoding (RLE): 行程编码 Contour encoding: 轮廓编码
LZW algorithm: Lemple-Ziv-Welch编码 Isoprefrence curves: 等值线，等优线 Freeman’s chain code: Freeman链码 Mapping: 映射 Scalar quantization: 标量量化 Rate distortion theory: 率失真理论 Date rate: 数据率 Distortion: 失真度

142 Terms Rate distortion function:率失真函数 Reconstruction error: 重构误差
Transform image encoding: 变换图像编码 Block encoding: 块编码 Bit allocation: 位分配，比特分配 Differential encoding:微分编码 Predictive encoding: 预测编码 Predictor: 预测器 Predictive coefficient: 预测系数

143 Terms Differential pulse code modulation (DPCM): 差分脉冲编码调制
Hybrid encoding: 混合编码 Subband coding: 子带编码 Karhunen-Loeve transform: 卡洛变换 K-L transform: 卡洛变换 Singular value decomposition transform: 奇异值分解变换 SVD transform:奇异值分解变换 Eigenvalue: 特征值

144 Terms Eigenvector: 特征向量 Hartley transform: 哈特雷变换 Haar transform: 哈尔变换
Markov process: 马尔科夫过程 Covariance matrix: 协方差矩阵 Hadamard transform: 哈达玛变换 Walsh transform: 沃尔什变换 Slant transform: 斜变换