第 8 讲 变换编码和矢量量化编码
3.3.3 变换编码
1,变换编码的一般原理
2,DCT变换编码方法
⑴ DCT变换的基本过程
⑵ DCT变换的基本算法
3.3.4 矢量量化编码
1.VQ编码的基本原理
⑴ 总体设计目标
⑵ 量化器设计
⑶ VQ编码器设计
2,码本生成的优化算法
3.3.3 变换编码预测编码：基于时域分析；用于提高压缩速度／实时压缩变换编码：基于频域分析；提高压缩比的最有效方法
DCT是 JPEG,MPEG和 H.261三大压缩标准的核心算法
1.变换编码的一般原理基本思想：
① 原始图像离散化 — 数据分块处理；
典型子块为 8× 8Pixel,块尺寸 n≧ 8
② 子块数据域变换 （ 时域 → 频域；正交变换 — 可逆 ）
a,频带能量高度集中在变换域的少数大幅值变换系数上
b,按能量区高／低分配位码多／少,小幅值元素作零处理
③ 压缩编码在频域上进行组成原理,正变换－编码，逆变换－解码变换方法选择,方法不同，数据压缩比和压缩速度都不一样
① KLT变换：变换后频域能量高度集中,压缩效果明显；
协方差阵可为对角阵且有最小均方误差,因而解压失真最小主要缺点：计算复杂,没有通用的变换核和快速算法
② DCT变换：有接近 KLT的优化性能,
又有通用的变换核和快速算法,且计算复杂性适中,
因此获得广泛应用,现已将快速 DCT算法做成专用压缩芯片
⑴ DCT变换的基本过程正向 DCT（ FDCT） 编码 ； 逆向 DCT（ IDCT） 解码
① 数据块分割：信源图像一般划分成 n× n个 8× 8子块变换单元
a,8× 8像素块的空间相关性,易于带来显著的压缩效率
b,8× 8块的变换计算复杂性适中,易适应 PC机的处理能力
c,8× 8块的存储结构与位模式对应,易于软硬件实现一般要求：块尺寸 n≥ 8；
若 n＜ 8,会因块间不连续而产生边界效应
② 子块正变换,8× 8子块 64个像元 64个 DCT系数
③ 频域系数量化：增加高频分量的零值,
减少非零低频分量的幅值及其表示范围
④ 频域数据编码：采用熵编码算法,改善压缩信号的保真性能
⑵ DCT变换的基本算法设：经 8× 8子块分割的信源图像为
f(x,y) = { Bi,j∣i= 1,2,… n,j=1,2,…,n }
f(x,y)的输入矩阵为 f，
用作变换核的变换矩阵为 C，
C的转置矩阵为 CT，
变换输出的系数矩阵为 F
则 DCT的算法思想可表述为：
① 构造一个正交变换 FDCT,F＝ CfCT
② 由可逆性定义 IDCT,f＝ CTFC
其中,空间域上的 f矩阵和变换域上的 F矩阵都是 n× n方阵；
其 8× 8展开式为：
③ 变换矩阵定义为,C＝ [Ci,j]n× n
讨论：导出变换矩阵 C — 将 DCT变换改写成三角函数形式
FDCT：
IDCT：
变换阵 C：
其中，变换因子 C可分离为,C（ u,v）＝ C（ u） ·C（ v）
其计算值便构成一个 n× n变换矩阵,即 C＝ [Ci,j]nn
要满足最优性能,C应接近一个对角阵,以获得最小均方误差
⑶ DCT快速算法在 JPEG混合编码中,FDCT／ IDCT耗时约占整个编码过程的 45%；
因此,寻求快速算法具有很大的实用价值
① 蝶形算法：利用 FFT变换的核函数 e-iu／ n的周期 （ n） 性,
找到蝶形操作关系,并只进行实部计算；
使得变换运算 F（ i） 的 n次乘法操作减少为 log2n 次再通过代数分解等方法,剔除复数运算
② 稀疏矩阵法：将变换核分解成一些稀疏矩阵的积,
使非 0元素仅包括两类,一是 Cos或 Sin函数,二是 +1
这样在两矩阵相乘时,+1将相关项的乘法转化为加减运算,
从而降低变换计算复杂性稀疏矩阵 Rn由 +1和 0组成
3.3.4 矢量量化（ VQ）编码矢量量化：在对模拟量进行数字化时,一次量化多个对象元点
（ 标量量化：一次量化一个对象元点 ）
VQ编码思想,数据分块 + 最小误差 + 可变字长
（ 变换编码 ） （ 预测编码 ） （ 熵编码 ）
（ HVQ） 过程层次化 寻求最优 VQ结构
80年代以来关注的新技术； HVQ编码的压缩比可高达上千倍
1.VQ编码的基本原理量化的应用,a.信号数字化过程的 A／ D转换
b.数据压缩编码中寻求量化点的数据匹配 — VQ结构设计
⑴ 总体设计目标思想：寻求最优矢量量化器 （ 非线性自适应；最小失真输出 ）
① 寻找量化步长和码本结构的优化算法,实现最小失真量化
② 采用可行的搜索算法使搜索时间最短,实现最快搜索量化具体做法：
① 数据分块：把需要量化的样本输入数据合理进行分组,
每一组定义为含有 n个相关量化点元素的一个矢量；
整幅图像按行 （ 或列 ） 表示为 K维矢量,形成量化输入
② 码本划分：根据量化点的概率密度分布和量化区间划分,
寻求一个与量化步长相匹配的量化器码本及码字表示；
以使整个样本点的量化失真最小
③ 量化编码：按一定步长进行多点量化,并用可变长码字表示
⑵ 量化器设计矢量值集合 R的 N阶矢量量化器可定义为三个部分
① 码本划分：码本 Y是由 N个码字组成的长度为 N的线性表
Y＝ {Yi}； Yi∈ R,i = 1,2,…,N
Yi称码字,表示每次量化的像素块个数,是一个 K维矢量；
N称码本长度,可定位量化步长,即单位时间内量化点个数
② 数据分组：把输入图像分成 K× N个 （ K≤ N） n× n像素块,
每列 （ 行 ） 由 K个 n× n量化点组成,称为矢量 X的 K个分量；
从而把输入图像表示为一个待编码的 K维矢量,即或,x = ( x1,x2,…,xk)
Xi称量化点； K为量化分组个数,即输入矢量 X的分量个数
③ 码字匹配：由输入矢量 X到码本搜索及码字匹配的映射变换过程其中,x为输入矢量 X的取值；
对于每个 x,在 X→Y 中,均能找到一个 Yi与之匹配讨论,K＝ 1,称标量量化器；
K＞ 1,称矢量量化器
⑶ VQ编码器设计
VQ编码器结构的组成原理：与量化器功能相适应,包括
·用于存放码字且具有一定编码数据结构的码本
·用于量化即判断输入矢量 X与码字 Yi相匹配的搜索器
·用于编码即定义 Yi及其输入矢量下标 i的映射关系的索引器
① 码本设计：寻求最优划分的量化步长,以建立最优码字集
Y＝ { Yi|i = 1,2,…,N }； 供比较匹配
② 数据分组：把输入图像 f离散化为 K× N个 n× n像素块,即
f（ x,y） ={ B（ i,j） |i=1,2,…,k； j=1,2,…,N }
再用矢量表示：
③ 搜索器设计：寻求 （ 时间,空间 ） 复杂度最小的搜索算法,
以实现最快搜索量化,搜索器 S用于在码本中寻找与输入矢量 X最接近的码字,并用找到的码字 Yi代替 X；
这一比较搜索与码字匹配的过程,就是矢量量化过程量化误差,q＝ Xi－ Yi
④ 索引器：提供编码查表,索引器 I定义码字 Yi的下标索引
i = I（ Yi） ； Yi∈ Y
2.码本生成的优化算法主要算法：码本学习算法 （ LBG） ；方根网格结构算法 （ SGR）
⑴ LBG算法特点：码本生成过程采用逐次迭代方式；
查找过程采用全搜索方式,时间复杂度为 O（ N）,速度慢
（ SGR算法的下限搜索时间为 O(log2n),支持快速搜索 ）
⑵ LBG算法设计原理设计思想：寻求优化的量化步长 Q（ x,yt）,
使量化器 Q的码本 Ym 得以优化其中,Q（ x,yt） 就是经 m次迭代算法计算所找出的最优码本划分 φ （ ym）
实现过程：以下列图像分割为例
f（ x,y） ={ B（ i,j） |i = 1,2,…,K； j = 1,2,…,N }
① 生成初始码本 Y0：通过图像的量化分组,
找到一个初始的码本划分 Y0,并通过对应的量化器 Q0来优化
F(x,y)= {Yj|j=1,2,…,N}→Y 0 = {y01,y02,…,y0N} Q0
② 生成优化码本 Ym：通过逐次迭代和量化,进行码字匹配；
即寻找与输入矢量 X =（ x1,x2,… xk） T最逼近的码字
Yt（ t=1,2,…,m,t≦k ）,
并用 Yt替代 X作为编码取值,（ Yt＝ M（ xt））,即有：
并且,最大量化失真半径为：
其中,d（ x,yt） 为量化输入 X与码字 yt的距离,
即量化误差 （ x－ yt）
d(x,yt)可用矢量长度（范数）表示为：
物理意义,d（ x,yt） ＝ d（ x,Qt（ x））
最优矢量量化：就是最小失真量化,
即使量化误差 q＝ x－ yt的均方值最小不失一般性,把下标记号 t换成 m，
则量化失真半径 Dt（ Qt） 的均方值为：
进而,最优量化器的均方误差为：
E{(x－ ym )2 }＝ E{(x－ Qm (x))2 }
③ 码本适应性修改与优化验证,LBG算法的一般原理可描述为在信源概率分布已知的情况下,对于给定的码本长度 N和初始码本空间 Y0＝ { y01,y02,…,y0N }：
a,通过 m 次迭代计算,
求出使码字集 Ym＝ { ym1,ym2,…,ymn}获得最优划分的量化失真半径
b,使得对于一个事先给定的最大失真半径及其迭代阀值
,有下式成立则：称量化器 Qm为最优量化器；
这一过程所生成的码本 Ym称最优码字集划分 ф（ ym）,
它实际就是 Qm 的量化步长
3.3.3 变换编码
1,变换编码的一般原理
2,DCT变换编码方法
⑴ DCT变换的基本过程
⑵ DCT变换的基本算法
3.3.4 矢量量化编码
1.VQ编码的基本原理
⑴ 总体设计目标
⑵ 量化器设计
⑶ VQ编码器设计
2,码本生成的优化算法
3.3.3 变换编码预测编码：基于时域分析；用于提高压缩速度／实时压缩变换编码：基于频域分析；提高压缩比的最有效方法
DCT是 JPEG,MPEG和 H.261三大压缩标准的核心算法
1.变换编码的一般原理基本思想：
① 原始图像离散化 — 数据分块处理；
典型子块为 8× 8Pixel,块尺寸 n≧ 8
② 子块数据域变换 （ 时域 → 频域；正交变换 — 可逆 ）
a,频带能量高度集中在变换域的少数大幅值变换系数上
b,按能量区高／低分配位码多／少,小幅值元素作零处理
③ 压缩编码在频域上进行组成原理,正变换－编码，逆变换－解码变换方法选择,方法不同，数据压缩比和压缩速度都不一样
① KLT变换：变换后频域能量高度集中,压缩效果明显；
协方差阵可为对角阵且有最小均方误差,因而解压失真最小主要缺点：计算复杂,没有通用的变换核和快速算法
② DCT变换：有接近 KLT的优化性能,
又有通用的变换核和快速算法,且计算复杂性适中,
因此获得广泛应用,现已将快速 DCT算法做成专用压缩芯片
⑴ DCT变换的基本过程正向 DCT（ FDCT） 编码 ； 逆向 DCT（ IDCT） 解码
① 数据块分割：信源图像一般划分成 n× n个 8× 8子块变换单元
a,8× 8像素块的空间相关性,易于带来显著的压缩效率
b,8× 8块的变换计算复杂性适中,易适应 PC机的处理能力
c,8× 8块的存储结构与位模式对应,易于软硬件实现一般要求：块尺寸 n≥ 8；
若 n＜ 8,会因块间不连续而产生边界效应
② 子块正变换,8× 8子块 64个像元 64个 DCT系数
③ 频域系数量化：增加高频分量的零值,
减少非零低频分量的幅值及其表示范围
④ 频域数据编码：采用熵编码算法,改善压缩信号的保真性能
⑵ DCT变换的基本算法设：经 8× 8子块分割的信源图像为
f(x,y) = { Bi,j∣i= 1,2,… n,j=1,2,…,n }
f(x,y)的输入矩阵为 f，
用作变换核的变换矩阵为 C，
C的转置矩阵为 CT，
变换输出的系数矩阵为 F
则 DCT的算法思想可表述为：
① 构造一个正交变换 FDCT,F＝ CfCT
② 由可逆性定义 IDCT,f＝ CTFC
其中,空间域上的 f矩阵和变换域上的 F矩阵都是 n× n方阵；
其 8× 8展开式为：
③ 变换矩阵定义为,C＝ [Ci,j]n× n
讨论：导出变换矩阵 C — 将 DCT变换改写成三角函数形式
FDCT：
IDCT：
变换阵 C：
其中，变换因子 C可分离为,C（ u,v）＝ C（ u） ·C（ v）
其计算值便构成一个 n× n变换矩阵,即 C＝ [Ci,j]nn
要满足最优性能,C应接近一个对角阵,以获得最小均方误差
⑶ DCT快速算法在 JPEG混合编码中,FDCT／ IDCT耗时约占整个编码过程的 45%；
因此,寻求快速算法具有很大的实用价值
① 蝶形算法：利用 FFT变换的核函数 e-iu／ n的周期 （ n） 性,
找到蝶形操作关系,并只进行实部计算；
使得变换运算 F（ i） 的 n次乘法操作减少为 log2n 次再通过代数分解等方法,剔除复数运算
② 稀疏矩阵法：将变换核分解成一些稀疏矩阵的积,
使非 0元素仅包括两类,一是 Cos或 Sin函数,二是 +1
这样在两矩阵相乘时,+1将相关项的乘法转化为加减运算,
从而降低变换计算复杂性稀疏矩阵 Rn由 +1和 0组成
3.3.4 矢量量化（ VQ）编码矢量量化：在对模拟量进行数字化时,一次量化多个对象元点
（ 标量量化：一次量化一个对象元点 ）
VQ编码思想,数据分块 + 最小误差 + 可变字长
（ 变换编码 ） （ 预测编码 ） （ 熵编码 ）
（ HVQ） 过程层次化 寻求最优 VQ结构
80年代以来关注的新技术； HVQ编码的压缩比可高达上千倍
1.VQ编码的基本原理量化的应用,a.信号数字化过程的 A／ D转换
b.数据压缩编码中寻求量化点的数据匹配 — VQ结构设计
⑴ 总体设计目标思想：寻求最优矢量量化器 （ 非线性自适应；最小失真输出 ）
① 寻找量化步长和码本结构的优化算法,实现最小失真量化
② 采用可行的搜索算法使搜索时间最短,实现最快搜索量化具体做法：
① 数据分块：把需要量化的样本输入数据合理进行分组,
每一组定义为含有 n个相关量化点元素的一个矢量；
整幅图像按行 （ 或列 ） 表示为 K维矢量,形成量化输入
② 码本划分：根据量化点的概率密度分布和量化区间划分,
寻求一个与量化步长相匹配的量化器码本及码字表示；
以使整个样本点的量化失真最小
③ 量化编码：按一定步长进行多点量化,并用可变长码字表示
⑵ 量化器设计矢量值集合 R的 N阶矢量量化器可定义为三个部分
① 码本划分：码本 Y是由 N个码字组成的长度为 N的线性表
Y＝ {Yi}； Yi∈ R,i = 1,2,…,N
Yi称码字,表示每次量化的像素块个数,是一个 K维矢量；
N称码本长度,可定位量化步长,即单位时间内量化点个数
② 数据分组：把输入图像分成 K× N个 （ K≤ N） n× n像素块,
每列 （ 行 ） 由 K个 n× n量化点组成,称为矢量 X的 K个分量；
从而把输入图像表示为一个待编码的 K维矢量,即或,x = ( x1,x2,…,xk)
Xi称量化点； K为量化分组个数,即输入矢量 X的分量个数
③ 码字匹配：由输入矢量 X到码本搜索及码字匹配的映射变换过程其中,x为输入矢量 X的取值；
对于每个 x,在 X→Y 中,均能找到一个 Yi与之匹配讨论,K＝ 1,称标量量化器；
K＞ 1,称矢量量化器
⑶ VQ编码器设计
VQ编码器结构的组成原理：与量化器功能相适应,包括
·用于存放码字且具有一定编码数据结构的码本
·用于量化即判断输入矢量 X与码字 Yi相匹配的搜索器
·用于编码即定义 Yi及其输入矢量下标 i的映射关系的索引器
① 码本设计：寻求最优划分的量化步长,以建立最优码字集
Y＝ { Yi|i = 1,2,…,N }； 供比较匹配
② 数据分组：把输入图像 f离散化为 K× N个 n× n像素块,即
f（ x,y） ={ B（ i,j） |i=1,2,…,k； j=1,2,…,N }
再用矢量表示：
③ 搜索器设计：寻求 （ 时间,空间 ） 复杂度最小的搜索算法,
以实现最快搜索量化,搜索器 S用于在码本中寻找与输入矢量 X最接近的码字,并用找到的码字 Yi代替 X；
这一比较搜索与码字匹配的过程,就是矢量量化过程量化误差,q＝ Xi－ Yi
④ 索引器：提供编码查表,索引器 I定义码字 Yi的下标索引
i = I（ Yi） ； Yi∈ Y
2.码本生成的优化算法主要算法：码本学习算法 （ LBG） ；方根网格结构算法 （ SGR）
⑴ LBG算法特点：码本生成过程采用逐次迭代方式；
查找过程采用全搜索方式,时间复杂度为 O（ N）,速度慢
（ SGR算法的下限搜索时间为 O(log2n),支持快速搜索 ）
⑵ LBG算法设计原理设计思想：寻求优化的量化步长 Q（ x,yt）,
使量化器 Q的码本 Ym 得以优化其中,Q（ x,yt） 就是经 m次迭代算法计算所找出的最优码本划分 φ （ ym）
实现过程：以下列图像分割为例
f（ x,y） ={ B（ i,j） |i = 1,2,…,K； j = 1,2,…,N }
① 生成初始码本 Y0：通过图像的量化分组,
找到一个初始的码本划分 Y0,并通过对应的量化器 Q0来优化
F(x,y)= {Yj|j=1,2,…,N}→Y 0 = {y01,y02,…,y0N} Q0
② 生成优化码本 Ym：通过逐次迭代和量化,进行码字匹配；
即寻找与输入矢量 X =（ x1,x2,… xk） T最逼近的码字
Yt（ t=1,2,…,m,t≦k ）,
并用 Yt替代 X作为编码取值,（ Yt＝ M（ xt））,即有：
并且,最大量化失真半径为：
其中,d（ x,yt） 为量化输入 X与码字 yt的距离,
即量化误差 （ x－ yt）
d(x,yt)可用矢量长度（范数）表示为：
物理意义,d（ x,yt） ＝ d（ x,Qt（ x））
最优矢量量化：就是最小失真量化,
即使量化误差 q＝ x－ yt的均方值最小不失一般性,把下标记号 t换成 m，
则量化失真半径 Dt（ Qt） 的均方值为：
进而,最优量化器的均方误差为：
E{(x－ ym )2 }＝ E{(x－ Qm (x))2 }
③ 码本适应性修改与优化验证,LBG算法的一般原理可描述为在信源概率分布已知的情况下,对于给定的码本长度 N和初始码本空间 Y0＝ { y01,y02,…,y0N }：
a,通过 m 次迭代计算,
求出使码字集 Ym＝ { ym1,ym2,…,ymn}获得最优划分的量化失真半径
b,使得对于一个事先给定的最大失真半径及其迭代阀值
,有下式成立则：称量化器 Qm为最优量化器；
这一过程所生成的码本 Ym称最优码字集划分 ф（ ym）,
它实际就是 Qm 的量化步长
