《{广告传媒}四川大学计算机学院多媒体基础变换编码》由会员分享，可在线阅读，更多相关《{广告传媒}四川大学计算机学院多媒体基础变换编码（95页珍藏版）》请在金锄头文库上搜索。
1、变换编码,四川大学 计算机学院 陈 虎 ,原理 为达到目的可以通过不同的路径殊途同归 例如：数学计算机中，经常利用某些数学函数略加转换可以找出一条计算的捷径。 乘法：1000000X100000100000000000 运算时，数据很大，可以变成对数进行加法,1000000 X 100000100000000000,取对数 lg106,取对数 lg105,取指数 1011,6,5, 11,算法变换,基本概念 先对信号进行某种函数变换，从一种域（空间）变换到另一种域（空间），再对变换后的信号进行编码处理 以声音图像为例，由于声音图像大部分信号都是低频信号，在频域中信号较集中，因此将时域信号变换到
2、频域，再对其进行采样、编码,变换编码 (Transform Coding) 是一种函数变换，从一个信号域变换到另一个信号域，将信源输出分解/变换为其组成部分，然后根据每个成分的特性分别进行编码，去除视频信号的空间冗余，使能量集中。,变换去除相关性示例 设有两个相邻的数据样本x1和x2，每个样本 采用3比特编码，则各有8个幅度等级，两个样本的联合事件共有64种可能用右图二维平面坐标表示 考虑到相邻样值的相关性，x1和x2同时出现相近幅度的可能性最大。 因此,合成可能性往往落在阴影区内,0,X1,X2,变换去除相关性示例 如果对数据进行正交变换，从几何上相当于坐标系旋转 45o,变成x1、x2坐标
3、系，则在新坐标系下，任凭x1在较大的范围变化，而x2始终只在相当小的范围内变化，因此通过这样的变化就能得到一组去除大部分，甚至是全部统计相关性的另一种输出样本,0,X1,X2,X1,X2,变换编码过程,变换,量化,译码器,逆变换,编码器,发送端,接收端,G,A,A,G,U,输入,U,输出,U为变换矩阵，A,A:变换系数,U:U的逆变换矩阵,酉（Unitary）变换概念,线性变换 v = Au，系数矩阵 A 称为此变换的基矩阵 如果 A 是一个酉矩阵，则：,且,其中，* 表示对 A 的每个元素取共轭复数，T 表示转置,如果 A 是酉矩阵，且所有元素都是实数，则它是一个正交矩阵，且满足,且,上式表
4、明：当 i=j 时，内积为 1；否则内积为 0，所以，A的各行是一组正交向量,任何两个酉变换之间的差别在于基函数（即 A 的行向量）的选择。 正交矩阵是酉矩阵，但酉矩阵不需要是正交矩阵。,正交矩阵的特点,正交矩阵的特点 每一行元素的平方和等于 1 两个不同行的对应元素乘积之和等于零 上述两条对于列也成立 例如,第一行,第二行,乘积,用前面的正交矩阵定义计算上述例子,正交变换,正交变换,u(m,n) 表示 NN 的原始图象; v(k,l) 表示变换系数; akl(m,n) 是离散正交变换基函数,正变换 (Forward Transform) 矩阵表示：,NN输入信号块，向量排列,N2N2 变换矩
5、阵,NN变换系数,线性：v(k,l) 描述为“基函数 (Basis Function)”的线性组合,可分离的正交变换,酉变换,基函数分解表示为：,可分离的正交变换,可分离的酉变换的正变换,可分离的酉变换的反变换,可分离的正交变换,可分离的酉变换的矩阵表示。,NN 正交变换矩阵,NN变换系数,反变换,重要的实际意义：用 2 个 NN 矩阵乘法代替了 1 个 1N2 矢量和 N2N2 矩阵的乘法，实现变换。使其复杂性 (乘法次数）从 O(N4) 减少为 O(N3)。,NN 输入信号,快速傅里叶变换,根据 DFT 公式，直接计算 N 点一维傅里叶变换需要 N2 次复数乘法，N(N-1) N2 次复数
6、加法运算。 快速傅里叶变换只需要 Nlog2N 次加法， 0.5Nlog2N 次乘法 。 例如 M=1024，直接傅里叶变换需要大约 106 次操作，快速傅里叶变换只需要 104 次操作。 2D-FFT 计算量,可分离的正交变换,二维变换通过 2 个一维变换实现 沿着信号块的行、列方向进行； 先对行进行运算，再对列进行运算，从而达到快速的目的。,正交基分解,A*kl 表示基图象 a*k 表示 A*kl 的第 k 行 a*l 表示 A*kl 的第 l 列,正交基分解,应用：信息传送原理 发端分解：传送 v(k,l)，即将信号向量分解成它的各个基图象，变换系数则规定了原信号中各基图象所占的数量。如
7、果一个信号，或其一部分可以近似地匹配上某一基函数，则在变换后，会产生一个对应于那个基函数的较大的变换系数。由于基函数是正交的，则这个信号对应于其它的基函数将产生较少的系数。 收端合成：通过将一组被适当加权的基图象求和而重构图象，用上面的式子合成。变换系数就是其对应的基图象在求和时所乘的系数。,正交基分解,举例说明以上概念： 给定正交矩阵A和图象矩阵U： 变换系数： 反变换为：,正交基分解,基图象：,分解：,合成：,酉变换特性能量保持与旋转,酉变换信号能量不变 U 矢量长度在 N 维空间中不变 酉变换在 N 维空间简单地旋转 U 矢量 酉变换是基坐标的旋转，V 分量是 U 在在新基坐标中的投影。
8、,1-D,2-D,酉变换特性能量集中与变换系数方差,酉变换：能量转到少数系数上，总能量不变,变换前后平均能量相等：,u、Ru 分别表示 U 矢量的均值和协方差,RV 矩阵对角线元素给出变换系数方差:,最后得：,矩阵的迹，矩阵对角线上元素的总和。,U变换,输入矢量 U 的相关RU,变换系数 V 的相关 RV （非对角系数变小）,酉变换的特性举例：能量集中与去相关,设,其酉变换：,表示 u(0) 和 u(1) 的相关性,酉变换特性去相关,酉变换特性,总能量 22 不变，但 v(0) 上的能量大于 v(1) 的，如 =0.95，则 91.1% 的总能量集中在 v(0) 上。,从 RU 可见：,即总能
9、量相等的分布在 u(0) 及 u(1) 上,从 RV 可见：,能量集中方面,V 的协方差：,酉变换特性,当 = 0.95 ， 说明：97.5% 的能量集中在 V(0) V（0,1) = 0， 说明：V(0) 与 V(1) 不相关,相关方面：u(0) 与 u(1) 间相关为 ；v(0) 与 v(1) 间相关为：,若 =0.95，则 V = 0.83 ，变换系数之间的相关性减弱。,变换矩阵的影响：,若,则,酉变换特性-熵保持性,如果把f(x,y)看作是一个具有一定熵值的随机函数，那么变换系数g(u,v)的熵值和原来图像信号f(x,y)的熵值相等。,变换编码的选择原则,变换编码的种类 K-L变换 K
10、LT 离散傅立叶变换 DFT 离散正弦变换 DST 离散余弦变换 DCT 哈达玛变换 Hadamard Walsh 变换 Haar 变换 Slant 变换 小波变换 Wavelet 去相关，能量集中（例如，KLT、DCT、Wavelat） 计算复杂度低,Karhunen -Love (卡胡南-列夫) 变换,KLT 变换产生去相关的变换系数 KLT 基函数是输入信号协方差矩阵的特征向量，因此，它是以统计特性为基础的，也称为特征向量变换。 最优的正交变换：特征向量矩阵指向数据变化最大的方向，能够达到最优的能量集中。 缺点：计算过程复杂，变换速度慢。 KLT 依赖信号统计特性，但很难实时计算视频的统
11、计特性； KLT 基函数不是固定的，是随图像内容改变的； KLT 对图象块是不可分离； 变换矩阵不能分解为稀疏矩阵。,KLT变换的基核矩阵和定义,协方差矩阵 Ru 的特征向量可以构成一个 N2N2 的矩阵 ， 的共轭转置 *T 称 K-L 变换的核矩阵,KLT 变换的定义：,正变换,反变换,K-L变换基核是随信号而变化的，不是固定的 自适应的。 变换过程为：图像随机变量 u 协方差矩阵 Ru K-L 基核矢量 *T。 事实上，在线性代数中已经学过，K-L变换基核的求法就是先求出图象的协方差矩阵 R 的特征值，然后求出特征向量，从而得到基核。,中心化后图象向量,KLT 变换的特征去相关,去相关
12、最佳的变换编码,KLT 变换系数 v(k), k=0,1,.,N-1 是不相关的，而且具有零均值，即：,证明：,协方差矩阵,KLT 变换的特征去相关,经过 KLT 变换后，所得的变换系数 v 是一个平均向量为零的向量集，其坐标原点移到中心位置。 将 mv =0 代入 Rv 表达式：,*T 矩阵由协方差矩阵 Ru 的 特征向量 i 的转置构成，即,KLT 变换的特征去相关,由于 矩阵是正交矩阵，所以 T = I 同时，矩阵 Ru 与其特征向量 i 应符合以下关系,代入上述 Rv 中,KLT 变换的特征去相关,结论： v 向量的平均向量为 0，直流分量为 0。 v 的协方差矩阵，协方差等于0，方差
13、对角线按减序排列 KLT 的变换系数是由互不相关的随机变量组成的，因此， KLT 变换起到了去除变量间相关性的作用。进而言之，每个 k 都是变换后第 k 个系数的 vk 的方差。,KLT 变换的特征降维,忽略特征值较小的那些特征向量，从而减少 u 的维数。 令 B*T 表示删去 *T 最下面的 N-M （MN) 行后得到的 MN 矩阵，这样，变换生成的向量维数就小一些（M1 大小），由下式生成：,向量 u 仍然可由下式近似重构出来：,这种近似的均方误差等于删去的那些特征向量所对应的特征值之和,KLT变换举例,设 31 随机向量 u 有以下的协方差矩阵：,该矩阵的特征值和特征向量为：,KLT变换
14、举例,对某个均值为 0 的向量 uT(2, 1, -0.1) 有：,变换后的向量 v 的协方差矩阵 Rv 为：,KLT变换举例,降维：因为3 明显比其它两个向量小，因此，假设将矩阵 的第三行去掉从而将 v 变成二维向量。,近似重构的原向量：,可以看到 u 和 u 有微小的差别，近似的均方误差为3 = 0.146，也就是去掉的特征向量所对应的特征值。,KLT变换举例,Lena 原始图象,相邻象素 (x,y)的灰度电平值,相邻象素 x 的直方图,相邻象素 y 的直方图,KLT变换举例,座标旋转后相邻象素 (x,y)的灰度电平值,座标旋转后相邻象素 x 的直方图,座标旋转后相邻象素 y 的直方图,L
15、ena 图象的 KLT 基图象,KLT变换举例,10:1 Lena 图象,失真(PSNR) 和比特率的关系,Fourier变换,所有实际信号都有起点和终点，时宽T在时域的作用和带宽B在频域的作用相同。对于0tT的信号，我们若希望知道信号的能量分布，须对信号做傅里叶变换，即研究其频率特性。 “频率”是我们在工程和物理学乃至日常生活中最常用的技术术语之一。截至目前我们在信号（平稳信号）的分析和处理中，当我们提到频率时，指的是Fourier变换的参数-频率f和角频率，它们与时间无关。然而对于非平稳信号， Fourier变换不再是合适的物理量。原因：非平稳信号的频率是随时间变化的，所以不再简单地用Fo
16、urier变换做分析工具。因此需要提供能给出瞬时频率的变换工具-时频分析。,Fourier变换,分析和处理平稳信号的最常用也是最主要的方法是Fourier分析。Fourier变换建立了信号从时（间）域到频（率）域的变换桥梁，而Fourier反变换则建立了信号从频域到时域的变换桥梁，这两个域之间的变换为一对一的映射，如下式：,Fourier变换,Fourier变换从时域和频域构成了观察一个信号的两种方式。 Fourier变换的局限和算法上的不足： （1）Fourier变换是在整体上将信号分解为不同的频率分量，而缺乏局域性信息。即它不能告诉我们某种频率分量发生在哪些时间内，而这对非平稳信号是十分重要的。 为了分析和处理非平稳信号，人们对Fourier分析进行了推广乃至根本性的革命，提出并发展了一系列新的信号分析理论：短时Fourier变换，分数阶Fourier变换、小波变换、WVD变换等。,Fourier变换,
