多媒体技术之变换编码.ppt

第6章 变换编码,本章之前一直认为冗余度是数据所固有的。但实际上数据冗余往往跟不同的表示方法有很大的关系。,6.1变换编码的基本思想,预测编码希望通过对信源建模尽可能精确地预测数据。变换编码的思路：将原始数据“变换”到一个更为紧凑的表示空间，从而得到比预测编码更高效率的数据表示（压缩）。预测编码消除相关性的能力有限，变换编码是一种更高效的压缩编码。变换编码的思想：将初始数据从时间域或者空间域变换到另一个更适合于压缩的抽象域，通常为频域。,变换编码的通用模型如下图：,变换编码：利用映射变换来实现对数据的建模表达。变换：将原始信号的个样本值从一个表示域变换到另一个表示域。,映射变换,量化,编码,解码,反量化,反映射变换,原始数据,信道,恢复数据,输入图像G经正交变换T变换到频域空间,象素之间相关性下降，能量集中在变换域中少数变换系数上。对变换系数A中那些幅度大元素予以保留，对幅度小的变换系数，全部当作零处理，不予编码，再辅以非线性量化，进一步压缩图像数据。由于量化器存在，量化后变换系数A和A间必然存在量化误差，从而引起输入图像G和输出图像G间存在误差。,变换编码数据压缩主要是去除信源的相关性,设信源序列为,协方差矩阵就是用来表征相关性的统计特性的,表示关于xi 的数学期望概率平均值。方差就表示xi偏离行均值的程度及xj偏离列均值的程度。,因此协方差矩阵描述了矩阵元素间的相关性，即表达了在行列两个方向上偏离均值的情况,为了有效压缩，希望变换后的协方差矩阵为对角矩阵，并且主对角线元素随i,j增加尽快衰减。已知X的条件下，可以根据协方差矩阵去寻找一种正交变换T，使变换后的协方差矩阵满足或接近为一对角阵。K-L变换(Karhunen-Loeve变换)即是这样一种变换，又称为最佳变换。它能使变换后协方差矩阵为对角阵，并且有最小均方误差。,映射变换的方法很多，一般指函数变换，常用的有正交变换。比如，傅立叶变换：利用复数域的正交变换（酉变换），将一个函数从时域描述变为频域的频谱展开使得函数的某些特性变得很明显，使问题得到简化。例如，在理想情况下，为表示单一频率的正弦波，电工学上只需要知道振幅、频率和初相角。当在频域展开是，若不考虑相位特性，谱线只有一条。而在时域描述中往往需要两倍以上的频率的奈奎斯特速率采样。造成这个特例的条件是傅立叶变换的特性和信号的特性相吻合。（适合于如语音信号中的浊音，心电图、脑电图等具有周期性的信号）,预测编码消除相关性的能力有限，变换编码是一种更高效的压缩编码。变换编码的思想：将初始数据从时间域或者空间域变换到另一个更适合于压缩的抽象域，通常为频域。,变换编码示意图,变换编码的分类 KL变换离散傅立叶变换（DFT）沃尔什-哈达玛变换（WHT）哈尔变换（HRT）离散余弦变换（DCT）离散正弦变换（DST）离散小波变换（DWT）等等。,背 景,任何周期函数都可以表示为不同频率的正弦和/或余弦和的形式.甚至非周期函数(曲线有限)也可以用正弦和/或余弦乘以不同的系数.,傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。傅里叶变换是一种解决问题的方法，一种工具，一种看待问题的角度。理解的关键是：一个连续的信号可以看作是一个个小信号的叠加，从时域叠加与从频域叠加都可以组成原来的信号，将信号这么分解后有助于处理。,我们原来对一个信号其实是从时间的角度去理解的，不知不觉中，其实是按照时间把信号进行分割，每一部分只是一个时间点对应一个信号值，一个信号是一组这样的分量的叠加。傅里叶变换后，其实还是个叠加问题，只不过是从频率的角度去叠加，只不过每个小信号是一个时间域上覆盖整个区间的信号，但他确有固定的周期，或者说，给了一个周期，我们就能画出一个整个区间上的分信号，那么给定一组周期值（或频率值），我们就可以画出其对应的曲线，就像给出时域上每一点的信号值一样，不过如果信号是周期的话，频域的更简单，只需要几个甚至一个就可以了，时域则需要整个时间轴上每一点都映射出一个函数值。,6.2 傅立叶理论基础傅立叶级数,三角级数定义由周期为2的正弦和余弦函数的线性组合而成的无穷级数,基本函数族组成：1，cos(nx)，sin(nx)性质：任意两个在一个周期上的积分等于0，称为正交性；,傅立叶展开傅立叶展开定理：周期为2的函数f(x)可以展开为三角级数，展开式系数为,狄利克雷收敛定理 收敛条件在一个周期内连续或只有有限个第一类间断点；在一个周期内至多只有有限个极值点。收敛结果当x是连续点时，级数收敛于该点的函数值；当x是间断点时，级数收敛于该点左右极限的平均值。,展开举例对称函数对奇函数：,对偶函数：,典型周期函数(周期为2),傅立叶展开的意义：理论意义：把复杂的周期函数用简单的三角级数表示；应用意义：用三角函数之和近似表示复杂的周期函数。例如：对称方波的傅立叶展开,重要推广推广1：问题：把周期为T=2L的函数f(t)的展开：方法：对基本公式作变换xt/L，,推广2问题：把定义在-L,L 上的函数 f(t)展开；方法：先把它延拓为周期函数(即把它当成是一个周期 为2L的函数的一部分)，再按推广1展开；注意：所得到的级数仅在原定义范围中与f(t)一致。延拓前 延拓后,推广3问题：把定义在 0,L 上的函数 f(x)展开；方法：先把它延拓为-L,L上的奇函数或偶函数，再按推广2把它延拓为周期函数，最后按推广1展开；注意：所得到的级数仅在原定义范围中与f(x)一致。公式：,傅立叶级数,展开的复数形式展开公式：,基本函数族：,正交性：,展开系数：,傅立叶变换,非周期函数的傅立叶展开问题：把定义在（，）中的非周期函数 f(x)展开；思路：把该函数定义在（L，L）中的部分展开，再令L；实施：展开公式,展开系数：,困难展开系数 cn 为无穷小；幂指数 nx/L 不确定。,傅立叶变换,解决方法：把 n/L 作为新变量，即定义n=n/L；把 cnL/作为新的展开系数，即定义F(n)=cnL/.公式的新形式：展开公式：,展开系数：,取极限：傅立叶变换：,傅立叶积分：,从欧拉公式中得到:,(4.2.7),其中:,例题1矩形函数的定义为,求矩形脉冲 x(t)=rect(t/2T1)的傅立叶变换。解：,例题2将矩形脉冲 f(t)=h rect(t/2T)展开为傅立叶积分。解：先求出 f(t)的傅立叶变换,代入傅立叶积分公式，得,一维离散傅里叶变换及其反变换,单变量离散函数f(x)的傅里叶变换F(u)定义为:,反变换为:,(4.2.5),(4.2.6),二维变换和反变换为:,二维DFT及其反变换,一个图像尺寸为M*N的函数f(x,y)的离散傅里叶变换由下列等式给出:,反变换由下列等式给出:,傅里叶谱,相角和频率谱:,(4.2.16),(4.2.17),离散傅立叶变换的计算举例,x,f(x0)=f(x0+x),0,1,2,3,1,2,3,4,F(0)=1/4f(x)exp0=1/4f(0)+f1(1)+f(2)+f(3)=1/4(2+3+4+4)=3.25F(1)=1/4f(x)exp-j2x/4)=1/4(2e0+3e j21/4+4e j22/4+4e j23/4)=1/4(-2+j)F(2)=-1/4(1+j0)F(3)=-1/4(2+j),离散傅立叶变换的计算举例因为，函数f(x,y)的傅立叶变换是f(x,y)积分的函数因此，计算每一个傅立叶变换值，原函数f(x,y)的每一个点都需要参与,二维DFT及其反变换,二维DFT及其反变换,Lena的傅里叶变换:,快速傅立叶变换FFT算法思想递推公式推导逆向FFT算法算法实现,FFT算法基本思想 FFT算法基于一个叫做递推加倍的方法。通过推导将DFT转换成两个递推公式 N-1F(u)=1/N f(x)exp(-j2ux/N)x=0 F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu),FFT算法基本思想 F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)其中：N=2MFeven(u)、Fodd(u)是1/2N个点的傅立叶值,FFT算法基本思想通过一个实例来体会一下FFT算法：设：有函数f(x)，其 N=23=8 有：f(0),f(1),f(2),f(3),f(4),f(5),f(6),f(7)计算：F(0),F(1),F(2),F(3),F(4),F(5),F(6),F(7),FFT算法基本思想首先分成奇偶两组：有：f(0),f(2),f(4),f(6)f(1),f(3),f(5),f(7)为了利用递推特性，再分成两组：有：f(0),f(4)，f(2),f(6)f(1),f(5)，f(3),f(7),f(0),f(4)f(2),f(6)f(1),f(5)f(3),f(7)F2(0),F2(4)F2(2),F2(6)F2(1),F2(5)F2(3),F2(7)F4(0),F4(4),F4(2),F4(6)F4(1),F4(5),F4(3),F4(7)F8(0),F8(1),F8(2),F8(3),F8(4),F8(5),F8(6),F8(7),分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始 表达 式分成两个部分来计算（2）通过计算两个（N/2）个点的变换。得到 Feven(u)和 Fodd(u)（3）奇部与偶部之和得到F(u)的前(N/2)个值。（4）奇部与偶部之差得到F(u)的后(N/2)个值。且不需要额外的变换计算。,归纳快速傅立叶变换的思想：1）通过计算两个单点的DFT，来计算两个点的DFT，2）通过计算两个双点的DFT，来计算四个点的DFT，以此类推3）对于任何N=2m的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT,傅立叶变换的幅值和相角,f（t）的傅立叶变换结果常常是虚数，可用复数形式表示为：,则其幅值为：,其相位为：,幅值和相角的应用,f（t）的能量谱:,用幅值和相位来表示傅立叶变换:,傅里叶变换简单通俗理解就是把看似杂乱无章的信号考虑成由一定振幅、相位、频率的基本正弦（余弦）信号组合而成，傅里叶变换的目的就是找出这些基本正弦（余弦）信号中振幅较大（能量较高）信号对应的频率，从而找出杂乱无章的信号中的主要振动频率特点。如减速机故障时，通过傅里叶变换做频谱分析，根据各级齿轮转速、齿数与杂音频谱中振幅大的对比，可以快速判断哪级齿轮损伤。,离散傅立叶变换的 Matlab实现,Matlab 函数 fft、fft2 和 fftn 分别可以实现一维、二维和 N 维 DFT 算法；而函数 ifft、ifft2 和 ifftn 则用来计算反 DFT。这些函数的调用格式如下：Afft(X,N,DIM)其中，X 表示输入图像；N 表示采样间隔点，如果 X 小于该数值，那么 Matlab 将会对 X 进行零填充，否则将进行截取，使之长度为 N；DIM 表示要进行离散傅立叶变换。例对声音的分析,Afft2(X,MROWS,NCOLS)其中，MROWS 和 NCOLS 指定对 X 进行零填充后的 X 大小。别可以实现一维、二维和 N 维 DFTAfftn(X,SIZE)其中，SIZE 是一个向量，它们每一个元素都将指定 X 相应维进行零填充后的长度。函数 ifft、ifft2 和 ifftn的调用格式于对应的离散傅立叶变换函数一致。别可以实现一维、二维和 N 维 DFT例子：图像的二维傅立叶频谱,图像傅立叶变换,图像傅立叶变换,原图像,幅度谱,相位谱,图像傅立叶变换,幅度谱告诉我们图像中某种频率的成份有多少相位谱告诉我们频率成份位于图像的什么位置通常我们只关心幅度谱下面两个图对应的幅度谱是一样（这里只显示了其幅度谱，当然相位谱是不一样的）,图像傅立叶变换,从幅度谱中我们可以看出明亮线反映出原始图像的灰度级变化，这正是图像的轮廓边,图像傅立叶变换,从幅度谱中我们可以看出明亮线和原始图像中对应的轮廓线是垂直的。如果原始图像中有圆形区域那么幅度谱中也呈圆形分布,图像傅立叶变换,图像中的颗粒状对应的幅度谱呈环状，但即使只有一颗颗粒，其幅度谱的模式还是这样。,图像傅立叶变换,这些图像没有特定的结构，左上角到右下角有一条斜线，它可能是由帽子和头发之间的边线产生的两个图像都存在一些小边界,