第四章图像压缩第三节有损压缩数字图像处理北京大学计算机研究所 陈晓鸥第四章图像压缩第三节有损压缩第三节 有损压缩
4.3.1 有损压缩引言
4.3.2 有损预测编码
4.3.2.1 最优预测器
4.3.2.2 最优量化器
4.3.3 变换编码第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
有损压缩引言
– 有损压缩是：
通过牺牲图像的准确率来达到加大压缩率的目的
如果我们容忍解压缩后的结果中有一定的误差,那么压缩率可以显著提高
– 有损压缩方法的压缩比：
在图像压缩比大于 30:1时,仍然能够重构图像
在图像压缩比为 10:1到 20:1时,重构图像与原图几乎没有差别
无损压缩的压缩比很少有能超过 3:1的
– 这两种压缩方法的根本差别在于有没有量化模块第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
源数据编码与解码的模型（复习）
– 源数据编码的模型
– 源数据解码的模型符号解码器反向映射器映射器 量化器 符号编码器第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器基本思想,
– 减少数据量的最简单的办法是将图像量化成较少的灰度级,通过减少图像的灰度级来实现图像的压缩
– 这种量化是不可逆的,因而解码时图像有损失
s
t
s1 s2 s3
t1
t2
t3
如果输入是 256 个灰度级，对灰度级量化后输出，只剩下 4个层次，
数据量被大大减少 。
第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器的定义
– 阶梯形量化函数 t = q(s),是一个 s的奇函数 （ 即
q(-s) = -q(s)）,它可以通过 L/2,si和 ti来完全描述,从而定义了一个量化器 。
– si 被称为量化器的 决策级 （阈值）；
ti 被称为量化器的 重构级 （代表级）。
L是量化器的级数。
– 由于习惯的原因,si被认为是映射到 ti,如果它在半开区间 (si,si+1]。
第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器的定义
inputs1 s2 S(L/2)-1
output
s
t
t1
t2
t(L/2)
-t(L/2)
S-[(L/2)-1]
t = q(s)
决策级（阈值）
重构级（代表级）
量化的对象可能是负数第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损 预测 编码的基本思想
DM有损预测编码
最优预测器与最优量化器的选择
最优预测器
– 马尔可夫 Markov预测器
最优量化器
– Lloyd-Max量化器第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损预测的基本思想对无损预测压缩的 误差进行量化,通过消除视觉心理冗余,达到对图像进一步压缩的目的 。
– 算法的演变
a) 无损预测压缩的基础是：
原图像值 fn与预测值 ^fn之间的误差 en。 有公式：
en = fn – ^fn
解码与编码使用相同的预测器第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 编码 e
n = fn – fn
+?
-
符号编码预测器 最接近的整数压缩图像输入图像 enfn
fn
m
fn(x,y) = round[i f (x,y-i)]?i=1/m
i=1
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 编码 f
n = en + fn
+?
+
符号解码预测器解压缩图像压缩图像
en fn
fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
– 算法的演变
b) 有损预测编码的演变 ——引入量化：
将 en量化,ên = Q(en); 用
^?f
n = ên + fn
近似 fn fnfn
^
编码,ên = Q( fn - fn)
^解码,?f
n = ên + fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 有损预测编码 ê
n = Q( fn -f
n)
+?
-
符号编码预测器压缩图像输入图像
enf
n
fn
量化器
ên
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 有损预测解码?f
n = ên + fn
+?
+
符号解码预测器解压缩图像压缩图像?fn
f
n
ên
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损预测编码
– 上述方案的 压缩编码 中,预测器的输入是 fn，
而 解压缩中 的预测器的输入是?fn,要使用相同的预测器,编码方案 要进行修改 。
预测器预测器编码
fn
解压
fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
修改后的有损预测编码
^ê
n = Q( fn - fn)
符号编码压缩图像+?
-
en输入图像 fn
量化器
ên
预测器
fn +?+?fn
^
fn = ên + fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 量化器和预测器的定义：
量化器
+? en > 0?是一个正常数
-? 其它?en用 1位编码
预测器
^fn =fn-1
一般是一个小于 1的预测系数
en =
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 量化器设,? = 6.5
+6.5
-6.5
e
‘e
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 举例,? = 1,? = 6.5
计算：两个像素 f0 =14,f1 =15
n= 0 ^f0 = f0 = 14，
n=1,^f1 =? f0 =(1)(14) = 14
（ 预测结果 ）
编码 e1 = 15 – 14 = 1 （ 预测误差 ）
‘ e1 = +6.5 ( 因为 e1 > 0 )
（ 量化误差 ）
解码 ‘ f = ‘e +^f = 6.5+14 = 20.5 （ 重第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 举例,? = 1,? = 6.5
输入 编码 解码 误差
n f ^f e?e?f ^f
f f-?f
0 14 - - - 14.0 -14.0 0.0
1 15 14.0 1.0 6.5 20.5 14.0 20.5-5.5
2 14 20.5 -6.5 -6.5 14.0 20.5 14.00.0
3 15 14.0 1.0 6.5 20.5 14.0 20.5-5.5
.,,,,,
.,,
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析粒状噪音溢出过载第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析
在 n=14到 19变化快的区域,?太小 以至不能表示输入的最大的变化,发生一个被称为 溢出过载 的失真 。
在 n= 0到 7相对平滑的区域,?太大 以至不能表示输入的最小变化,出现了 粒状噪音
在大多数图像中,这两种现象导致,
– 对象边缘的钝化
– 平滑区域表面粒状的失真第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析
在所有有损预测压缩中都会出现误差 。 误差的严重程度取决于使用的 量化方法和预测方法之间的相互作用
尽管存在这种相互作用
– 定义预测函数时仍然假定没有量化误差
– 定义量化函数时仅是尽可能地降低它自身的误差
– 即 量化函数和预测函数是分别定义 的第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
最优预测器 与 最优量化器 的选择
– 使均方预测误差：
最小的预测器和量化器,被称为 最优预测器 和 最优量化器 。
}]?{[}{ 22 nnn ffEeE
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
– 马尔可夫最优预测器第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
1） 最优预测器应该满足两个条件：
<1>误差最小
fn = ên + ^fn? en + ^fn = fn
<2>用前面的值预测后面的
m
^fn =i fn-i
i=1
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2） 最优预测器的基本原理：
预测值可以限制为前 m个点的 线性组合 函数 。 这个限制不是必须的,但它们大大简化了分析,同时减小了预测器的计算复杂度 。 预测编码的结果被称作差分调制脉冲码 （ DPCM）
在以上条件下,最佳预测器的设计问题可以归结为直接选取 m个预测系数,使得下式最小：
}]{[}{ 2
1
2?
m
i
ininn ffEeE?
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2）最优预测器的基本原理：
对上式微分,计算使其等于 0的方程,解方程组,
= R-1r
其中：
}]{[}{ 2
1
2?
m
i
ininn ffEeE?
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
2）最优预测器的基本原理：
R =
E{fn-1 fn-1}
E{fn-2 fn-1}
E{fn-m fn-1}
E{fn-1 fn-2},..
E{fn-m fn-2},.,E{fn-m fn-m}
E{fn-1 fn-m}
r =
E{fn fn-1}
E{fn fn-2}
E{fn fn-m}
=
1
1
m
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2）最优预测器的基本原理：
这样对于任何一个输入图像，使上式的最小系数?,
均可以通过一系列矩阵运算得到。而且这些 系数仅依赖于原始图像中像素之间的关系 。
用这些最优系数产生的预测误差的方差是：
m
2e =?2 -?Tr =?2 -? E{fn fn-i}?i
i=1
其中?2是标准（非最优的）方差第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
3）最优预测器的计算方法：
尽管计算方程组很简单,但在实际应用中根据像素之间的关系 计算 R和 r的过程却很复杂
因而很少使用局部预测,即对每个图像都计算一次预测系数?
大多数情况下,R和 r的计算都是 通过一个简单的模型图像得到的第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想一个二维 Markov源图像具有独立的关系函数,E{f (x,y) f (x-i,y-j)} =σ 2ρ viρ hj
且产生四项线性预测器
^f (x,y) =?1f (x,y-1) +?2f (x-1,y-1) +
3f (x-1,y ) +?4f (x -1,y+1)
可以得到解
1 = ρ h ；?2 =-ρ vρ h；?3 =ρ v；?4 = 0；
其中 ρ v和 ρ h分别是图像竖直和水平的 关系系数
(x-1,y-1)
P
(x-1,y+1)
(x-1,y)
(x,y-1)
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想要求将下式中的预测系数之和,小于等于 1
^ mf
n =i fn-I
i=1
m
即,∑?i?1
i=1
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想
这个限制条件可以保证：
– 预测器的 输出在允许的灰度范围内
– 并 减少传输噪音的影响,避免产生重构图像中的横纹
减少 差分调制脉冲码 DPCM中产生噪声的可能性十分重要,因为某个误差可能被传播到输出的其它部分,使得解码器的输出不稳定第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型
最优 Lloyd_Max量化器第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型预测误差的概率密度函数一般来说在 0点是高尖的,且具有变化范围较小的特征
0 100-100
10
5
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型
事实上预测误差的密度函数,经常是通过 0平均无关拉普拉斯 pdf（ 概率密度函数 ） 来模型化,
p(e) =1/?2?eexp(-?2|e| /?e)
其中,?e是输入值误差 e的标准方差第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
– 量化器 q的设计 目标 是：
如何使由于量化所引起的图像损失达到最小
– 量化器 q的设计 问题 是：
对于特定的优化标准,及输入概率密度函数
p(s)（ 直方图 ）,选择最好的决策级 si和重构级
ti,或量化函数,使均方误差 E{(s – ti)2} 达到最小第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
– Lloyd_Max量化器定义
1） 要达到最小误差的条件有两个：
a） 每个决策级 si正好落在两个相邻重构级 ti,
ti+1的中点 。
0 i = 0
si = (ti + ti+1) / 2 i =
1,2,...,L/2 – 1?
i = L/2
且 s–i = –si t-i = –ti （ q为奇函数）
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
inputs1 s2=6 S(L/2)-1
output
s
t
t1
t2=4
t(L/2)
-t(L/2)
S-[(L/2)-1]
t = q(s)t
3 =8
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
b）每个重构级 ti 落在两个相继决策级 si区间的
p(s)（概率密度函数）的质心上。
si
(s-ti)p(s)ds = 0 i =
1,2,...,L/2
si-1
2） 以上两个条件构成一个方程组,必须通过迭代才能求解决策级 si和重构级 ti。
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
3）对于任何满足两个最小误差条件有的 L,si和 ti，在均方误差意义上是最优的，相应的量化器被称为：
L级 Lloyd_Max量化器
4） 由于对于多数 p(s)，得到一个符合最优量化两个条件的解是困难的,因此这些解可通过数字来产生。
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器拉普拉斯 单位变量概率密度函数的 Lioyd_Max量化器量化级 2 4
8
i si ti si ti si ti
1? 0.707 1.102 0.395 0.504 0.222
2? 1.810 1.181 0.785
3 2.285 1.576
4? 2.994
1.414 1.087 0.731
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
上表给出了三种量化器,分别提供了 1,2,3位 /象素的固定编码输出率
实际的重构级 ti和决策级 si是通过把列表中的值,
与所考虑的概率密度函数的标准方差?e相乘来获得的
表的最后一行列出了步长的尺寸?，它同时满足 达到最小误差的两个条件,且满足附加的约束条件：
ti – ti-1 = si – si-1 =?
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
2级的 Lioyd_Max量化器
用 1位 2进制数编码
t1= 0.707?e
- t1 = -0.707?e
s
t
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
4级的 Lioyd_Max量化器
用 2位二进制编码
inputs1=1.102?e
output
s
t
t1 = 0.395?e
t2 = 1.810?e
-t2
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
8级的 Lioyd_Max量化器
用 3位二进制编码
inputs1 s2 S3
output
s
t
t1
t2
t4
-t3
S-3
t = q(s)t
3
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
变换编码的基本理论
– 变换编码的基本原理
– 变换系数截取模板函数
– 误差评估
实现变换压缩算法的主要问题
– 变换的选择
– 子图尺寸的选择
– 压缩的位分配第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
（ 1） 用一个可逆的,线性的变换 （ 如傅立叶变换 ）,
把图像映射到变换系数集合
（ 2） 然后对该系数集合进行量化和编码
（ 3） 对于大多数自然图像,重要系数的数量是比较少的,因而可以用量化 （ 或完全抛弃 ）,且仅以较小的图像失真为代价 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想 ——举例原始图像 相应的 DCT系数
52 55 61 66 70 61 64 73
63 59 66 90 109 85 69 72
62 59 68 113 144 104 66 73
63 58 71 122 154 106 70 69
67 61 68 104 126 88 68 70
79 65 60 70 77 68 58 75
85 71 64 59 55 61 65 83
87 79 69 68 65 76 78 94
-415 -29 -62 25 55 -20 -1 3
7 -21 -62 9 11 -7 -6 6
-46 8 77 -25 -30 10 7 -5
-50 13 35 -15 -9 6 0 3
11 -8 -13 -2 -1 1 -4 1
-10 1 3 -3 -1 0 2 -1
-4 -1 2 -1 2 -3 1 -2
-1 -1 -1 -2 -1 -1 0 -1
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
– 编码,解码流程符号解码器 逆向变换正向变换 量化器 符号编码器构造 nxn的子图合成 nxn
的子图输入图像 NxN 压缩图像压缩的图像 解压图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
– 构造 nxn的子图
NxN
nxn
nxn
nxnnxn
nxn
nxn
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换编码的基本原理
将傅立叶 逆 变换 表达式进行改写：
N-1 N-1
f(x,y) = F(u,v)exp[j2? (ux+vy) /N]
u=0 v=0
F(u,v) 改为,T(u,v)
exp[j2?(ux+vy)/n]改为,h(x,y,u,v)
n-1 n-1
有,f(x,y) = T(u,v)h(x,y,u,v)
u=0 v=0
变换压缩的基本思想,就是要用等式的右部近似原图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换编码的基本原理进一步改写
n-1 n-1
F = T(u,v)Huv
u=0 v=0
其中,1) F是一个包含了 f(x,y)的象素的 nxn的矩阵 ；
2) Huv的值只依赖坐标变量 x,y,u,v与 T(u,v)和 f(x,y)
的值无关 。 被称为 基图像 。 可以在变换前一次生成 。 对每一个 nxn的子图变换都可以使用 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 基图像 H
h(0,0,u,v) h(0,1,u,v) …
h(0,n-1,u,v)
h(1,0,u,v) h(1,1,u,v) …
h(1,n-1,u,v)
Huv =
h(n-1,0,u,v) h(n-1,1,u,v) … h(n-1,n-
1,u,v)
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换系数截取模板函数通过定义变换系数截取模板函数,消去冗余
0 如果 T(u,v)满足一个特定的截断标准
m(u,v) =
1 否则
n-1 n-1
对于,F = T(u,v)Huv
u=0 v=0
1 1 1 1 0 0 0 01 1 1 1 0 0 0 0
1 1 1 0 0 0 0 01 1 0 0 0 0 0 0
1 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换系数截取模板函数对于 u,v = 0,1,…,n-1,F的一个近似,可以从截断表达式获得：
^ n-1 n-1
F = T(u,v)m(u,v)Huv
u=0 v=0
其中 m(u,v)被构造,用来消去对等式的总合贡献最小的基本图像 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 误差评估,F和近似 ^F之间的均方误差：
ems = E{||F – ^F||2}
n-1 n-1 n-1 n-1
= E{ || T(u,v)Huv - T(u,v)m(u,v)Huv||2}
u=0 v=0 u=0 v=0
n-1 n-1
= E{ || T(u,v)Huv[1 - m(u,v)]||2}
u=0 v=0
n-1 n-1
=2T(u,v)[1 - m(u,v)]
u=0 v=0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 误差评估
^ ^其中,||F –F||是 (F – F)的矩阵范数,
2T(u,v)是变换在 (u,v)位置上的系数方差 。
最后的简化是基于基图像的规范正交,并假设 F的像素是通过一个具有 0均值和已知协方差的随机处理产生的 。 因此,
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 误差评估小结
1） 总的均方近似误差是丢弃的变换系数的方差之和 （ 也即对于 m(u,v) = 0的系数方差之和 ） 。
2） 能把大多数信息封装到最少的系数里去的变换,可得到最好的子图像的近似,同时重构误差也最小
3） 在导致等式成立的假设下,一个 NxN的图像的 (N/n)2个子图像的均方误差是相同的 。 因此,NxN图像的均方误差
（ 是平均误差的测量 ） 等于一个子图像的均方误差第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
实现变换压缩算法的主要问题
– 变换的选择
– 子图尺寸的选择
– 压缩的位分配（编码）
正向变换 量化器 符号编码器构造 nxn的子图输入图像 NxN 压缩图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 变换的选择
（ 1） 可以选择的变换
1） Karhunen-Loeve变换 (KLT)
2） 离散傅立叶变换 （ DFT）
F(u,v) = 1/Nf(x,y)exp[-j2?(ux+vy)/N]
u,v = 0,1,2,...N-1,并且
f(x,y) =F(u,v)exp[j2? (ux+vy)/N]
x,y = 0,1,2,...N-1
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 变换的选择
3） 离散余弦变换 （ DCT）
C(u,v) =?(u)?(v)
f(x,y)cos[(2x+1)u?/2N] cos[(2y+1)v?/2N]
f(x,y) =(u)?(v)
C(u,v)cos[(2x+1)u?/2N] cos[(2y + 1)v?/2N]
4） Walsh-Hadamard变换 （ WHT）
5） 小波变换第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 变换的选择
（ 2） 对变换的评价按信息封装能力排序：
KLT,DCT,DFT,WHT,HaarT
但 KLT的基图像是数据依赖的,每次都要重新计算 Huv。
因而很少使用 。 DFT的块效应严重 。 常用的是 DCT,已被国际标准采纳,作成芯片 。 其优点有：
1） 基本没有块效应
2） 信息封装能力强,把最多的信息封装在最少的系数中第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 子图尺寸的选择子图尺寸的选择有两个原则：
1) 如果 n是子图的维数,n应该是 2的整数次方 。
为便于降低计算复杂度 。
2) n一般选为 8x8或 16x16。 由实践得到：
3) 随着 n的增加,块效应相应减少 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
3.5
3.0
2.5
2.0 Fourier
1.5 Hadamard
1.0 Cosine
0.5
0
2x2 4x4 8x8 16x16 32x32
均方根误差子图像尺寸第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 压缩位的分配定义：截取、量化、系数编码统称为 位分配主要解决 m(u,v)的设计,编码问题截取和量化一般有两种方法：
（ 1） 子带编码
（ 2） 阈值编码 （ 适应性编码 ）
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
基本思想,所有子图像使用相同的编码模板
1 1 1 1 1 0 0 01 1 1 1 0 0 0 0
1 1 1 0 0 0 0 01 1 0 0 0 0 0 0
1 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
消去 87.5%的系数的模板为第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
基本思想：
(1) 大部分的信息应该包含在最大方差的变换系数中
– 每一个 DCT变换系数被认为是一个随机变量
– 该变量的分布可以在所有变换子图像的集合上进行计
(2) 在 (N/n)2个子图找出取最大方差的 m个系数的位置
– 同时确定了系数的坐标 u和 v
– 对所有子图像,这 m个系数的 T(u,v)值是保留的,其他的 T值被抛弃
– m是一个可选常数第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
最大方差的计算：
1） 方差本身可以直接由 (N/n)2个变换子图像数组的集合计算得到 。
2） 或者基于一个假想的图像模型得到 。
3） 根据最大方差的分布情况得到系数截取模板
4） 方差最大的地方置 1,其它地方置 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
算法实现：
1） 计算模板：方差最大的地方置 1,其它地方置 0
2） 量化系数：例如最优 Lloyd-Max量化器
3） 结果编码：有两种分配二进制位的编码方法：
〈 1〉 系数被赋予相同数量的二进制位
〈 2〉 系数之间固定地分配一定的二进制位第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配系数之间固定地分配一定的二进制位的用位模板
8 7 6 4 3 2 1 0
7 6 5 4 3 2 1 0
6 5 4 3 3 1 1 0
4 4 3 3 2 1 0 03 3 3 2 1 1 0 0
2 2 1 1 1 0 0 01 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
基本思想,没有一个消取系数的固定模板 。 不同的子图保留不同的系数 。 通过一个阈值 T,来决定一个系数的去留 。
If a(系数 ) > T(阈值 ) m(u,v) =
1
Else m(u,v) = 0
由于其简单性,阈值编码是实际应用中更常使用的编码方法 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
理论根据：
1） 取值最大的变换系数,在重构子图的质量中起的作用也最重要 。
2） 最大系数的分布随子图的不同而不同 。
1 1 0 1 0 0 0 01 1 1 1 0 0 0 0
1 1 0 0 0 0 0 01 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
算法实现思想：
a.阈值的选取,常有三种取法 。
1) 所有子图使用同一个全局阈值 。
压缩率的大小随图像的不同而不同 。 由超过全局阈值的系数的个数所决定第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
算法实现思想：
a.阈值的选取,常有三种取法 。
2) 对每个子图使用不同的阈值。
每个子图 保留的系数的个数事先确定,
即总保留 N个最大的。称为 N-最大化编码 。对于每个子图同样多的系数被丢弃。因此，每个子图的压缩率是相同的，并且是预先知道的。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
a.阈值的选取，常有三种取法。
3) 阈值作为子图系数位置的函数。
所有子图使用同一个全局阈值模板,但阈值的取值,与系数的位置相关,阈值模板给出了不同位置上系数的相应阈值 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
a.阈值的选取，常有三种取法。
3) 阈值作为子图系数位置的函数
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 6218 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
b.对系数的编码
a） 将系数按 45度对角顺序展开成序列,得到有一个有长串为零的序列 。
例,-19 -20 5 21 6 0 0 0 0 0 0 0 0 0
b） 用 RLE编码对上述序列编码 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
– 对系数编码的展开顺序
0 1 5 6 14 15 27 28
2 4 7 13 16 26 29 42
3 8 12 17 25 30 41 43
9 11 18 24 31 40 44 5310 19 23 32 39 45 52 54
20 22 33 38 46 51 55 60
21 34 37 47 50 56 59 61
35 36 48 49 57 58 62 63
第四章图像压缩第三节有损压缩请提问
4.3.1 有损压缩引言
4.3.2 有损预测编码
4.3.2.1 最优预测器
4.3.2.2 最优量化器
4.3.3 变换编码第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
有损压缩引言
– 有损压缩是：
通过牺牲图像的准确率来达到加大压缩率的目的
如果我们容忍解压缩后的结果中有一定的误差,那么压缩率可以显著提高
– 有损压缩方法的压缩比：
在图像压缩比大于 30:1时,仍然能够重构图像
在图像压缩比为 10:1到 20:1时,重构图像与原图几乎没有差别
无损压缩的压缩比很少有能超过 3:1的
– 这两种压缩方法的根本差别在于有没有量化模块第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
源数据编码与解码的模型（复习）
– 源数据编码的模型
– 源数据解码的模型符号解码器反向映射器映射器 量化器 符号编码器第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器基本思想,
– 减少数据量的最简单的办法是将图像量化成较少的灰度级,通过减少图像的灰度级来实现图像的压缩
– 这种量化是不可逆的,因而解码时图像有损失
s
t
s1 s2 s3
t1
t2
t3
如果输入是 256 个灰度级，对灰度级量化后输出，只剩下 4个层次，
数据量被大大减少 。
第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器的定义
– 阶梯形量化函数 t = q(s),是一个 s的奇函数 （ 即
q(-s) = -q(s)）,它可以通过 L/2,si和 ti来完全描述,从而定义了一个量化器 。
– si 被称为量化器的 决策级 （阈值）；
ti 被称为量化器的 重构级 （代表级）。
L是量化器的级数。
– 由于习惯的原因,si被认为是映射到 ti,如果它在半开区间 (si,si+1]。
第四章图像压缩第三节有损压缩
4.3.1 有损压缩：引言
量化器的定义
inputs1 s2 S(L/2)-1
output
s
t
t1
t2
t(L/2)
-t(L/2)
S-[(L/2)-1]
t = q(s)
决策级（阈值）
重构级（代表级）
量化的对象可能是负数第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损 预测 编码的基本思想
DM有损预测编码
最优预测器与最优量化器的选择
最优预测器
– 马尔可夫 Markov预测器
最优量化器
– Lloyd-Max量化器第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损预测的基本思想对无损预测压缩的 误差进行量化,通过消除视觉心理冗余,达到对图像进一步压缩的目的 。
– 算法的演变
a) 无损预测压缩的基础是：
原图像值 fn与预测值 ^fn之间的误差 en。 有公式：
en = fn – ^fn
解码与编码使用相同的预测器第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 编码 e
n = fn – fn
+?
-
符号编码预测器 最接近的整数压缩图像输入图像 enfn
fn
m
fn(x,y) = round[i f (x,y-i)]?i=1/m
i=1
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 编码 f
n = en + fn
+?
+
符号解码预测器解压缩图像压缩图像
en fn
fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
– 算法的演变
b) 有损预测编码的演变 ——引入量化：
将 en量化,ên = Q(en); 用
^?f
n = ên + fn
近似 fn fnfn
^
编码,ên = Q( fn - fn)
^解码,?f
n = ên + fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 有损预测编码 ê
n = Q( fn -f
n)
+?
-
符号编码预测器压缩图像输入图像
enf
n
fn
量化器
ên
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
^? 有损预测解码?f
n = ên + fn
+?
+
符号解码预测器解压缩图像压缩图像?fn
f
n
ên
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
有损预测编码
– 上述方案的 压缩编码 中,预测器的输入是 fn，
而 解压缩中 的预测器的输入是?fn,要使用相同的预测器,编码方案 要进行修改 。
预测器预测器编码
fn
解压
fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
修改后的有损预测编码
^ê
n = Q( fn - fn)
符号编码压缩图像+?
-
en输入图像 fn
量化器
ên
预测器
fn +?+?fn
^
fn = ên + fn
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 量化器和预测器的定义：
量化器
+? en > 0?是一个正常数
-? 其它?en用 1位编码
预测器
^fn =fn-1
一般是一个小于 1的预测系数
en =
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 量化器设,? = 6.5
+6.5
-6.5
e
‘e
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 举例,? = 1,? = 6.5
计算：两个像素 f0 =14,f1 =15
n= 0 ^f0 = f0 = 14，
n=1,^f1 =? f0 =(1)(14) = 14
（ 预测结果 ）
编码 e1 = 15 – 14 = 1 （ 预测误差 ）
‘ e1 = +6.5 ( 因为 e1 > 0 )
（ 量化误差 ）
解码 ‘ f = ‘e +^f = 6.5+14 = 20.5 （ 重第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 举例,? = 1,? = 6.5
输入 编码 解码 误差
n f ^f e?e?f ^f
f f-?f
0 14 - - - 14.0 -14.0 0.0
1 15 14.0 1.0 6.5 20.5 14.0 20.5-5.5
2 14 20.5 -6.5 -6.5 14.0 20.5 14.00.0
3 15 14.0 1.0 6.5 20.5 14.0 20.5-5.5
.,,,,,
.,,
第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析粒状噪音溢出过载第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析
在 n=14到 19变化快的区域,?太小 以至不能表示输入的最大的变化,发生一个被称为 溢出过载 的失真 。
在 n= 0到 7相对平滑的区域,?太大 以至不能表示输入的最小变化,出现了 粒状噪音
在大多数图像中,这两种现象导致,
– 对象边缘的钝化
– 平滑区域表面粒状的失真第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
DM(Delta modulation)有损 预测编码
– 算法分析
在所有有损预测压缩中都会出现误差 。 误差的严重程度取决于使用的 量化方法和预测方法之间的相互作用
尽管存在这种相互作用
– 定义预测函数时仍然假定没有量化误差
– 定义量化函数时仅是尽可能地降低它自身的误差
– 即 量化函数和预测函数是分别定义 的第四章图像压缩第三节有损压缩
4.3.2 有损压缩,有损预测编码
最优预测器 与 最优量化器 的选择
– 使均方预测误差：
最小的预测器和量化器,被称为 最优预测器 和 最优量化器 。
}]?{[}{ 22 nnn ffEeE
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
– 马尔可夫最优预测器第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
1） 最优预测器应该满足两个条件：
<1>误差最小
fn = ên + ^fn? en + ^fn = fn
<2>用前面的值预测后面的
m
^fn =i fn-i
i=1
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2） 最优预测器的基本原理：
预测值可以限制为前 m个点的 线性组合 函数 。 这个限制不是必须的,但它们大大简化了分析,同时减小了预测器的计算复杂度 。 预测编码的结果被称作差分调制脉冲码 （ DPCM）
在以上条件下,最佳预测器的设计问题可以归结为直接选取 m个预测系数,使得下式最小：
}]{[}{ 2
1
2?
m
i
ininn ffEeE?
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2）最优预测器的基本原理：
对上式微分,计算使其等于 0的方程,解方程组,
= R-1r
其中：
}]{[}{ 2
1
2?
m
i
ininn ffEeE?
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
2）最优预测器的基本原理：
R =
E{fn-1 fn-1}
E{fn-2 fn-1}
E{fn-m fn-1}
E{fn-1 fn-2},..
E{fn-m fn-2},.,E{fn-m fn-m}
E{fn-1 fn-m}
r =
E{fn fn-1}
E{fn fn-2}
E{fn fn-m}
=
1
1
m
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
2）最优预测器的基本原理：
这样对于任何一个输入图像，使上式的最小系数?,
均可以通过一系列矩阵运算得到。而且这些 系数仅依赖于原始图像中像素之间的关系 。
用这些最优系数产生的预测误差的方差是：
m
2e =?2 -?Tr =?2 -? E{fn fn-i}?i
i=1
其中?2是标准（非最优的）方差第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 最优预测器的基本思想和原理
3）最优预测器的计算方法：
尽管计算方程组很简单,但在实际应用中根据像素之间的关系 计算 R和 r的过程却很复杂
因而很少使用局部预测,即对每个图像都计算一次预测系数?
大多数情况下,R和 r的计算都是 通过一个简单的模型图像得到的第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想一个二维 Markov源图像具有独立的关系函数,E{f (x,y) f (x-i,y-j)} =σ 2ρ viρ hj
且产生四项线性预测器
^f (x,y) =?1f (x,y-1) +?2f (x-1,y-1) +
3f (x-1,y ) +?4f (x -1,y+1)
可以得到解
1 = ρ h ；?2 =-ρ vρ h；?3 =ρ v；?4 = 0；
其中 ρ v和 ρ h分别是图像竖直和水平的 关系系数
(x-1,y-1)
P
(x-1,y+1)
(x-1,y)
(x,y-1)
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想要求将下式中的预测系数之和,小于等于 1
^ mf
n =i fn-I
i=1
m
即,∑?i?1
i=1
第四章图像压缩第三节有损压缩
4.3.2.1 有损预测编码,最优预测器
– 马尔可夫最优预测器
基本思想
这个限制条件可以保证：
– 预测器的 输出在允许的灰度范围内
– 并 减少传输噪音的影响,避免产生重构图像中的横纹
减少 差分调制脉冲码 DPCM中产生噪声的可能性十分重要,因为某个误差可能被传播到输出的其它部分,使得解码器的输出不稳定第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型
最优 Lloyd_Max量化器第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型预测误差的概率密度函数一般来说在 0点是高尖的,且具有变化范围较小的特征
0 100-100
10
5
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
预测器误差模型
事实上预测误差的密度函数,经常是通过 0平均无关拉普拉斯 pdf（ 概率密度函数 ） 来模型化,
p(e) =1/?2?eexp(-?2|e| /?e)
其中,?e是输入值误差 e的标准方差第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
– 量化器 q的设计 目标 是：
如何使由于量化所引起的图像损失达到最小
– 量化器 q的设计 问题 是：
对于特定的优化标准,及输入概率密度函数
p(s)（ 直方图 ）,选择最好的决策级 si和重构级
ti,或量化函数,使均方误差 E{(s – ti)2} 达到最小第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
– Lloyd_Max量化器定义
1） 要达到最小误差的条件有两个：
a） 每个决策级 si正好落在两个相邻重构级 ti,
ti+1的中点 。
0 i = 0
si = (ti + ti+1) / 2 i =
1,2,...,L/2 – 1?
i = L/2
且 s–i = –si t-i = –ti （ q为奇函数）
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
最优 Lloyd_Max量化器
inputs1 s2=6 S(L/2)-1
output
s
t
t1
t2=4
t(L/2)
-t(L/2)
S-[(L/2)-1]
t = q(s)t
3 =8
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
b）每个重构级 ti 落在两个相继决策级 si区间的
p(s)（概率密度函数）的质心上。
si
(s-ti)p(s)ds = 0 i =
1,2,...,L/2
si-1
2） 以上两个条件构成一个方程组,必须通过迭代才能求解决策级 si和重构级 ti。
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
3）对于任何满足两个最小误差条件有的 L,si和 ti，在均方误差意义上是最优的，相应的量化器被称为：
L级 Lloyd_Max量化器
4） 由于对于多数 p(s)，得到一个符合最优量化两个条件的解是困难的,因此这些解可通过数字来产生。
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器拉普拉斯 单位变量概率密度函数的 Lioyd_Max量化器量化级 2 4
8
i si ti si ti si ti
1? 0.707 1.102 0.395 0.504 0.222
2? 1.810 1.181 0.785
3 2.285 1.576
4? 2.994
1.414 1.087 0.731
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
上表给出了三种量化器,分别提供了 1,2,3位 /象素的固定编码输出率
实际的重构级 ti和决策级 si是通过把列表中的值,
与所考虑的概率密度函数的标准方差?e相乘来获得的
表的最后一行列出了步长的尺寸?，它同时满足 达到最小误差的两个条件,且满足附加的约束条件：
ti – ti-1 = si – si-1 =?
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
2级的 Lioyd_Max量化器
用 1位 2进制数编码
t1= 0.707?e
- t1 = -0.707?e
s
t
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
4级的 Lioyd_Max量化器
用 2位二进制编码
inputs1=1.102?e
output
s
t
t1 = 0.395?e
t2 = 1.810?e
-t2
第四章图像压缩第三节有损压缩
4.3.2.2 有损预测编码,最优量化器
8级的 Lioyd_Max量化器
用 3位二进制编码
inputs1 s2 S3
output
s
t
t1
t2
t4
-t3
S-3
t = q(s)t
3
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
变换编码的基本理论
– 变换编码的基本原理
– 变换系数截取模板函数
– 误差评估
实现变换压缩算法的主要问题
– 变换的选择
– 子图尺寸的选择
– 压缩的位分配第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
（ 1） 用一个可逆的,线性的变换 （ 如傅立叶变换 ）,
把图像映射到变换系数集合
（ 2） 然后对该系数集合进行量化和编码
（ 3） 对于大多数自然图像,重要系数的数量是比较少的,因而可以用量化 （ 或完全抛弃 ）,且仅以较小的图像失真为代价 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想 ——举例原始图像 相应的 DCT系数
52 55 61 66 70 61 64 73
63 59 66 90 109 85 69 72
62 59 68 113 144 104 66 73
63 58 71 122 154 106 70 69
67 61 68 104 126 88 68 70
79 65 60 70 77 68 58 75
85 71 64 59 55 61 65 83
87 79 69 68 65 76 78 94
-415 -29 -62 25 55 -20 -1 3
7 -21 -62 9 11 -7 -6 6
-46 8 77 -25 -30 10 7 -5
-50 13 35 -15 -9 6 0 3
11 -8 -13 -2 -1 1 -4 1
-10 1 3 -3 -1 0 2 -1
-4 -1 2 -1 2 -3 1 -2
-1 -1 -1 -2 -1 -1 0 -1
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
– 编码,解码流程符号解码器 逆向变换正向变换 量化器 符号编码器构造 nxn的子图合成 nxn
的子图输入图像 NxN 压缩图像压缩的图像 解压图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本思想
– 构造 nxn的子图
NxN
nxn
nxn
nxnnxn
nxn
nxn
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换编码的基本原理
将傅立叶 逆 变换 表达式进行改写：
N-1 N-1
f(x,y) = F(u,v)exp[j2? (ux+vy) /N]
u=0 v=0
F(u,v) 改为,T(u,v)
exp[j2?(ux+vy)/n]改为,h(x,y,u,v)
n-1 n-1
有,f(x,y) = T(u,v)h(x,y,u,v)
u=0 v=0
变换压缩的基本思想,就是要用等式的右部近似原图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换编码的基本原理进一步改写
n-1 n-1
F = T(u,v)Huv
u=0 v=0
其中,1) F是一个包含了 f(x,y)的象素的 nxn的矩阵 ；
2) Huv的值只依赖坐标变量 x,y,u,v与 T(u,v)和 f(x,y)
的值无关 。 被称为 基图像 。 可以在变换前一次生成 。 对每一个 nxn的子图变换都可以使用 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 基图像 H
h(0,0,u,v) h(0,1,u,v) …
h(0,n-1,u,v)
h(1,0,u,v) h(1,1,u,v) …
h(1,n-1,u,v)
Huv =
h(n-1,0,u,v) h(n-1,1,u,v) … h(n-1,n-
1,u,v)
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换系数截取模板函数通过定义变换系数截取模板函数,消去冗余
0 如果 T(u,v)满足一个特定的截断标准
m(u,v) =
1 否则
n-1 n-1
对于,F = T(u,v)Huv
u=0 v=0
1 1 1 1 0 0 0 01 1 1 1 0 0 0 0
1 1 1 0 0 0 0 01 1 0 0 0 0 0 0
1 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 变换系数截取模板函数对于 u,v = 0,1,…,n-1,F的一个近似,可以从截断表达式获得：
^ n-1 n-1
F = T(u,v)m(u,v)Huv
u=0 v=0
其中 m(u,v)被构造,用来消去对等式的总合贡献最小的基本图像 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 误差评估,F和近似 ^F之间的均方误差：
ems = E{||F – ^F||2}
n-1 n-1 n-1 n-1
= E{ || T(u,v)Huv - T(u,v)m(u,v)Huv||2}
u=0 v=0 u=0 v=0
n-1 n-1
= E{ || T(u,v)Huv[1 - m(u,v)]||2}
u=0 v=0
n-1 n-1
=2T(u,v)[1 - m(u,v)]
u=0 v=0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 误差评估
^ ^其中,||F –F||是 (F – F)的矩阵范数,
2T(u,v)是变换在 (u,v)位置上的系数方差 。
最后的简化是基于基图像的规范正交,并假设 F的像素是通过一个具有 0均值和已知协方差的随机处理产生的 。 因此,
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换编码的基本理论
– 误差评估小结
1） 总的均方近似误差是丢弃的变换系数的方差之和 （ 也即对于 m(u,v) = 0的系数方差之和 ） 。
2） 能把大多数信息封装到最少的系数里去的变换,可得到最好的子图像的近似,同时重构误差也最小
3） 在导致等式成立的假设下,一个 NxN的图像的 (N/n)2个子图像的均方误差是相同的 。 因此,NxN图像的均方误差
（ 是平均误差的测量 ） 等于一个子图像的均方误差第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
实现变换压缩算法的主要问题
– 变换的选择
– 子图尺寸的选择
– 压缩的位分配（编码）
正向变换 量化器 符号编码器构造 nxn的子图输入图像 NxN 压缩图像第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 变换的选择
（ 1） 可以选择的变换
1） Karhunen-Loeve变换 (KLT)
2） 离散傅立叶变换 （ DFT）
F(u,v) = 1/Nf(x,y)exp[-j2?(ux+vy)/N]
u,v = 0,1,2,...N-1,并且
f(x,y) =F(u,v)exp[j2? (ux+vy)/N]
x,y = 0,1,2,...N-1
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 变换的选择
3） 离散余弦变换 （ DCT）
C(u,v) =?(u)?(v)
f(x,y)cos[(2x+1)u?/2N] cos[(2y+1)v?/2N]
f(x,y) =(u)?(v)
C(u,v)cos[(2x+1)u?/2N] cos[(2y + 1)v?/2N]
4） Walsh-Hadamard变换 （ WHT）
5） 小波变换第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 变换的选择
（ 2） 对变换的评价按信息封装能力排序：
KLT,DCT,DFT,WHT,HaarT
但 KLT的基图像是数据依赖的,每次都要重新计算 Huv。
因而很少使用 。 DFT的块效应严重 。 常用的是 DCT,已被国际标准采纳,作成芯片 。 其优点有：
1） 基本没有块效应
2） 信息封装能力强,把最多的信息封装在最少的系数中第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 子图尺寸的选择子图尺寸的选择有两个原则：
1) 如果 n是子图的维数,n应该是 2的整数次方 。
为便于降低计算复杂度 。
2) n一般选为 8x8或 16x16。 由实践得到：
3) 随着 n的增加,块效应相应减少 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
3.5
3.0
2.5
2.0 Fourier
1.5 Hadamard
1.0 Cosine
0.5
0
2x2 4x4 8x8 16x16 32x32
均方根误差子图像尺寸第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
变换压缩方法主要研究的问题
– 压缩位的分配定义：截取、量化、系数编码统称为 位分配主要解决 m(u,v)的设计,编码问题截取和量化一般有两种方法：
（ 1） 子带编码
（ 2） 阈值编码 （ 适应性编码 ）
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
基本思想,所有子图像使用相同的编码模板
1 1 1 1 1 0 0 01 1 1 1 0 0 0 0
1 1 1 0 0 0 0 01 1 0 0 0 0 0 0
1 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
消去 87.5%的系数的模板为第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
基本思想：
(1) 大部分的信息应该包含在最大方差的变换系数中
– 每一个 DCT变换系数被认为是一个随机变量
– 该变量的分布可以在所有变换子图像的集合上进行计
(2) 在 (N/n)2个子图找出取最大方差的 m个系数的位置
– 同时确定了系数的坐标 u和 v
– 对所有子图像,这 m个系数的 T(u,v)值是保留的,其他的 T值被抛弃
– m是一个可选常数第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
最大方差的计算：
1） 方差本身可以直接由 (N/n)2个变换子图像数组的集合计算得到 。
2） 或者基于一个假想的图像模型得到 。
3） 根据最大方差的分布情况得到系数截取模板
4） 方差最大的地方置 1,其它地方置 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 1） 子带编码
算法实现：
1） 计算模板：方差最大的地方置 1,其它地方置 0
2） 量化系数：例如最优 Lloyd-Max量化器
3） 结果编码：有两种分配二进制位的编码方法：
〈 1〉 系数被赋予相同数量的二进制位
〈 2〉 系数之间固定地分配一定的二进制位第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配系数之间固定地分配一定的二进制位的用位模板
8 7 6 4 3 2 1 0
7 6 5 4 3 2 1 0
6 5 4 3 3 1 1 0
4 4 3 3 2 1 0 03 3 3 2 1 1 0 0
2 2 1 1 1 0 0 01 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
基本思想,没有一个消取系数的固定模板 。 不同的子图保留不同的系数 。 通过一个阈值 T,来决定一个系数的去留 。
If a(系数 ) > T(阈值 ) m(u,v) =
1
Else m(u,v) = 0
由于其简单性,阈值编码是实际应用中更常使用的编码方法 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
理论根据：
1） 取值最大的变换系数,在重构子图的质量中起的作用也最重要 。
2） 最大系数的分布随子图的不同而不同 。
1 1 0 1 0 0 0 01 1 1 1 0 0 0 0
1 1 0 0 0 0 0 01 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
0 0 0 0 0 0 0 00 0 0 0 0 0 0 0
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
算法实现思想：
a.阈值的选取,常有三种取法 。
1) 所有子图使用同一个全局阈值 。
压缩率的大小随图像的不同而不同 。 由超过全局阈值的系数的个数所决定第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
算法实现思想：
a.阈值的选取,常有三种取法 。
2) 对每个子图使用不同的阈值。
每个子图 保留的系数的个数事先确定,
即总保留 N个最大的。称为 N-最大化编码 。对于每个子图同样多的系数被丢弃。因此，每个子图的压缩率是相同的，并且是预先知道的。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
a.阈值的选取，常有三种取法。
3) 阈值作为子图系数位置的函数。
所有子图使用同一个全局阈值模板,但阈值的取值,与系数的位置相关,阈值模板给出了不同位置上系数的相应阈值 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
a.阈值的选取，常有三种取法。
3) 阈值作为子图系数位置的函数
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 6218 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
（ 2）阈值编码（适应性编码）
算法实现思想：
b.对系数的编码
a） 将系数按 45度对角顺序展开成序列,得到有一个有长串为零的序列 。
例,-19 -20 5 21 6 0 0 0 0 0 0 0 0 0
b） 用 RLE编码对上述序列编码 。
第四章图像压缩第三节有损压缩
4.3.3 有损压缩,变换编码
– 压缩位的分配
（ 2） 阈值编码 （ 适应性编码 ）
– 对系数编码的展开顺序
0 1 5 6 14 15 27 28
2 4 7 13 16 26 29 42
3 8 12 17 25 30 41 43
9 11 18 24 31 40 44 5310 19 23 32 39 45 52 54
20 22 33 38 46 51 55 60
21 34 37 47 50 56 59 61
35 36 48 49 57 58 62 63
第四章图像压缩第三节有损压缩请提问
