【教学课件】第8章正交变换.ppt

第 8 章 正交变换,8.1 正交变换；8.2 KL 变换8.3 离散余弦（正弦）变换（DCT,DST）8.4 离散 Hartley 变换（DHT）8.5 离散 W 变换8.6 DCT、DST、DWT快速算法（略）8.7 关于图像压缩及国际标准（讲座1）8.8 重叠正交变换（LOT）（讲座2）,一、信号的分解,设空间 是由 N 维空间一组向量,概念：,8.1 正交变换,对任一，都可作如下分解：,所张成，即,信号的离散表示,或信号的分解,是分解系数或信号的变换,设想另有一组向量,Step1:,满足：,例如：,Step2:做内积,对,注意：满足双正交关系的两组基向量各自并不满足正交关系，只是相互之间满足正交关系。,如果：,几点说明：,用向量 表示信号，会出现几 种不同的情况，取决于 的性质：,如果空间 中的任一元素 都可由 来分解，则称该向量是“完备（complete）”的；,2.如果 完备且线性相关，则对 的表 示必然存在信息冗余，且对偶向量不唯一。可能构成一个“标架（Frame)”;,如果 是完备的，且是线性无关的，则它构成 中的一组基向量，这时其对偶 向量存在且唯一，即存在前述的双正交关系；这时的基称为 Riesz 基。,二、信号的正交变换,给定数据向量：,及算子,作变换,若：,则上述变换即为正交变换，或保范（数）变换,矩阵 的行（列）向量即是前面的向量,实际上是正交矩阵，,以上正交变换是从线性代数的角度来定义。,正交变换的性质：,2.正交变换在计算上最为简单。如果是离 散信号，且 N 是有限值，那么变换只是简单的矩阵与向量运算：,1.若正变换存在，那么反变换一定存在，且变换是唯一的；,性质2：展开系数是信号在基向量上的准确投影,非正交基的情况下，“基向量”称为“标架（Frame)”,这时，展开系数不是准确投影。,性质3：正交变换保证变换前后信号的能量不变，此性质又称为“保范(数)变换”。,此性质实际上是 Parsevals 定理，即信号变换前后能量保持不变。注意，只有正交变换才有此性质。,性质4：信号正交分解具有最小平方近似性质。,最小的条件：,傅立叶级数的截短、第7章的FIR滤波器设计等，均要用到该性质。,性质5：正交变换的系数具有去除相关和集 中能量的性质。,数据压缩的理论基础。后面即将讨论。,给定一个实对称矩阵，一定可以找到一个正交阵，使得：,正交基的选择 原则：具有所希望的物理意义或实用意义；正交基函数应尽量简单，计算量小；最大限度浓缩信号能量，去除相关性；基函数应能同时具有频域和时域的定位功能,正交变换的实例：FS，FT,DTFT,DFS,DFT DCT，DST,DHT Walsh-Hadamard,Haar 变换，SLT(斜变换）,正弦类正交变换,非正弦类正交变换,8.2 KL 变换,数据向量：,协方差阵：,对称阵,体现了信号各元素之间的相互关系,KL 变换的思路：,寻找正交矩阵，做变换，使 的协方差阵 为对角阵。,这样,之间彻底去除了相关性。,1.由,求 的特征值,2.求 的 个特征向量,3.将 归一化，即令,步骤：,4.由归一化的,构成正交阵,5.由 实现对 的 KL 变换:,这样，信号 中的各个元素之间彻底去除了相关性！,KL 变换的应用数据压缩：,的 KL 展开,欲使均方误差：,为最小,应是 的特征向量。,最小,这时,注意：对正交变换,不是时域序列，而是 的变换系数（即），如 DFT 的。正交变换后，信号的能量一般集中在少数的变换系数上，所以可以舍去绝大部分系数，这并不明显损失信号的能量。由剩下的少量系数，如，通过反变换 可以很好的恢复出原信号。从而达到数据压缩的目的。,KL 变换：去相关性最彻底，在此意义上是最佳正交变换；,8.3 离散余弦变换（DCT）,给定：,定义：,DCT的 定义,DCT的核函数，DCT矩阵,DCT 的特点 DCT 是实变换；DCT 是正交变换；在一定条件下，DCT近似 K-L 变换；DCT有快速算法。正因为DCT有上述特点，因此，DCT在语音和图像压缩中已获得广泛应用。,例：8 点 DCT：,DCT 反变换,在DCT中，正变换矩阵和反变换矩阵是一样的，都是实矩阵。特别有利于实时实现及硬件实现。,重点讨论：DCT如何近似 K-L?,一阶马尔可夫过程（Markov-1):语音和图象处理中常用的数学模型。一个随机信号，若其pdf满足如下关系：,则称 为一阶马尔可夫过程。该式的含意是:已知过程在现在时刻的状态，那么，下一个时刻的状态只和现在的状态有关，而和过去的状态无关。,令 是Markov-1 随机序列相邻两元素之间的相关系数，则该序列的协方差矩阵有如下关系：,按 KL 变换的思路，现需要求 的特征值及特征向量，以形成变换的正交矩阵。但对Markov-1 过程，协方差阵 的特征向量可以解析的给出，因此正交变换的矩阵也可解析的得到：,是 的特征值,是方程,的根,现考虑 时的情况：,有：,由：,必有：,将,结论：当 时，对Markov-1过程做KL变换的正交矩阵正是DCT变换的变换矩阵，也即：此时的DCT近似KL变换。因为DCT有快速算法，另外，Markov-1过程可作为一大类信号（语音、图象）的数学模型，因此 DCT在图象、语音压缩中起到了关键性的作用，成为国际上许多标准（如 JPEG,MPEG）的重要工具。,下图是 时 KL变换矩阵、DCT 变换矩阵、DST 变换矩阵的行向量。,给定：,定义：,反变换：,离散正弦变换（DST）,变换矩阵,DST也是正交变换,可以证明，DST在一定条件下也是对KL变换的近似。如何评判近似的好坏,？,正弦类变换：,变换前相关矩阵非对角线上元素的和；,变换后相关矩阵非对角线上元素的和；越小越好,：反映了变换后能量集中的程度。若 越小、越大，则能量越集中。,8.4 Hartley 变换,FT:,定义,偶部,奇部,离散Hartley 变换矩阵也是正交阵，且是周期的，周期为。DHT可用来实现DFT的几乎所有功能，而这些实现都是在实数域进行的。,有关DHT的性质及用于卷积运算的讨论见书8.4节，此处不再详细讨论。,8.5 离散 W 变换,无穷多种,？,DFT的定义有一种，DWT有四种。四种DWT都是正交变换,它们分别对应两种形式的抽样，即 的整数抽样和 的半整数抽样。若用它作谐波分析，可以得到分数倍谐波（基波的奇数倍/2)。,即是Hartley 变换矩阵。四种 DWT 矩阵有着密切的关系，由它们可引导出四种类型的 DCT 和四种类型的 DST。,DCT-,四种形式的DCT,DCT-,DCT-,DCT-,DST-,DST-,DST-,DST-,已定义过,四种形式的DST,四种形式的 DCT、DST是由不同的学者在不同的文献上提出的，它们在不同的条件下对KL变换有着不同的近似。如：,DCT-对KL 变换的近似最好；,DST-对KL 变换的近似最好；,DCT-优于DCT-；,DCT-对KL 变换的近似极坏；,使用DCT-要比DCT-安全。,实际上，用的最多的还是DCT-!,8.6 DCT、DST、DWT快速算法,DCT、DST、DWT基本上都可以通过FFT来实现，当然也可发展其他适合它们特点的算法。对DCT-:,其他有关内容见教材,8.6 图象压缩及其国际标准-DCT应用讲座(1),一、图像的基本概念,彩色图像：,二、图像压缩的基本概念,必需进行有效的图像压缩！,2.重建图象质量，包括客观度量和主观度量。客观度量：即图象的逼真度，可考虑为原图象与重建图象的差值。令波形编码器的输入波形为X，解码器的输出波形为Y，则较为常用的两个参数为：,三、图像压缩的指标,编码效率：包括图象压缩比（CR）、每象素用的 比特数（bpp）、每秒所需的传输比特数（bps）；,均方误差：峰值信噪比：,主观度量：即通过人们的主观测试来评价系统的质量，包括二元判决（即“接受”和“不可接受”）、主观PSNR、平均判分、等偏爱度曲线、多维计分（MDS）等。,3.算法的运算量和硬件实现的复杂程度；4.算法的适用范围；5.算法的抗信道噪声干扰能力等。,四、图像压缩的途径,对于单幅图像消除帧内冗余度,对于序列图像消除帧间差别,帧内压缩，或静态图象压缩,帧间压缩，或动态图象压缩,静态图像的冗余度,空间冗余：规则物体和规则背景的表面物理 特性具有相关性，结构冗余：图像中存在强的纹理结构，考虑 其纹理特性，可有效压缩图像；知识冗余：图像的理解和某些基础知识有相 当大的相关性 视觉冗余：运动的前后图像间存在着相关性，人眼对部分图像信息不敏感。,序列图像的帧间差别,物体运动；运动物体之间及物体与背景间的遮挡和显露；光照条件或物体表面反光特性的变换；物体的变形。,以上原因引起序列图象帧与帧之间的变化，但帧与帧之间也有着很大的相似，因此有压缩潜力。图象运动越慢，压缩潜力越大。,五、图像压缩算法综述,静态图像压缩,静态图像压缩无损压缩,无损压缩,静态图像压缩DPCM,对一个特定域内的象素x1xN进行加权求和：,求得上述结果和待预测象素值的差值：,对差值量化后的指数进行熵编码。,静态图像压缩去除相关,静态图像压缩量化的概念,原88图像，点与点之间有相关性,经2DDCT后，能量集中在左上角，64个数据之间的范围太大，不利于编码。,是JPEG推荐的量化矩阵。将矩阵 的元素除以矩阵 的元素后再取整，从而将动态范围缩小，得,数据小,数据大,量化后的矩阵，压缩了动态范围，大部分数据为零。,原图像,经量化编码及DCT反变换后的图像,静态图像压缩编码的概念,电报用“莫尔斯”码 e 概率 0.1031.t 0.0796-a 0.0642.-z 0.0005-.,静态图像压缩Huffman编码,1 将信源符号出现的概率按递减顺序排列；2 将两个最小概率相加，继续之，大的在上 部，小的在下部；3 每一对组合中，上面为1，下面为零；或反之；4 画出每个信源符号概率到1的路径，记下路径 的 1 和 0；5 由右到左，写下这些符号，即为Huffman码。,静态图像压缩Huffman编码,静态图像压缩游程编码,若沿某一特定方向上的一串m个象素具有相 同的灰度值 p，则只要传输(p,m)即可。,23，23，23，23，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1 可以表示为：(23,4),(0,15),静态图像压缩有损压缩,静态图像压缩变换编码,静态图像压缩K-L变换,KL变换是最佳变换，将原始信号中 相关性很强的空域变换到相关性彻底 去除的变换域；无快速算法而难以实现。,静态图像压缩DCT变换,在统计意义上达到最接近KL变换的结果 以DCT为基础的JPEG编码标准广泛应用,压缩比可以达到3355:1；缺点：传统的块效应，压缩比受限制；,静态图像压缩DCT变换,DCT:要分成88，或1616的块来做，这样才最接近K-L变换，当然，也 就产生了“块效应”。,静态图像压缩JPEG标准,JPEG：Joint Photographic Experts Group,JPEG标准框图：,JPEG图例：,原图,压缩9.2倍,JPEG图例：,压缩18.4倍,原图,JPEG图例：,压缩27.6倍,原图,JPEG图例：,压缩55.2倍,原图,静态图像压缩Gabor变换,Gabor变换具有对信号进行时频分析的功能；较好地与人类视觉系统（HVS）的接收野相 符合，可以利用视觉系统的信息处理机制和 图像性质的一致性达到“视觉无损”和“信息 保持”的一致性。结合熵编码，可达到8:1的无损压缩。,静态图像压缩DWT变换,小波变换编码步骤：,精确重建（Perfect Reconstruction）：,静态图像压缩DWT变换,二维DWT变换：,原始图像,列变换,行变换,三层DWT分解后的结果：,静态图像压缩DWT变换,三层DWT分解的结果：,静态图像压缩DWT变换,自相似性：无论几何尺度怎样变化，物体任 何组成部分的形状都以某种方式与整体相似。在于引入了局部与全部相关去冗余的思想。压缩效率与物体本身性质有关。,静态图像压缩分形方法,核心思想：利用码书（Code Book）进行信息的传 递和存储。编码思路：码书就是一种人为制定的映射，按照一定的准则把n维空间划分为若干子空间，然后把图像各象素的输入值分配到各组中，每组用一个n维矢量来表示。这组矢量和相应的序号构成码书；工作时码书在发送端和接收端各有一本，每输入一个象素数据就根据距离最小原则确定重建矢量，查出相应的序号送出，达到压缩的目的。特点：压缩效率较高；码书的训练非常重要。,静态图像压缩向量量化方法,动态图像压缩,动态图像压缩帧间预测编码,动态图像压缩运动估计与补偿,动态图像压缩自适应帧内/帧间预测,根据活动情况进行自适应的帧内/帧间编码，提高编码效率！,物体本身活动时：帧内相关性降低，帧间相关性增强；,摄像机活动时：帧内相关性增强，帧间相关性降低。,动态图像压缩BMA方法,匹配准则：归一化互相关函数（NCCF）均方误差（MSE）帧间绝对差（MAD）,传统的JPEGISO（International Organization for Standardization）和CCITT（International Telephone and Telegraph Consultative Committee）于1986年底成立了“联合图片专家组”（Joint Photographic Experts Group，简称JPEG），致力于研究静止图像压缩算法的国际标准。传统JPEG标准，要点如下：,六、图像编码标准,1.基本系统：DCT为主的算法，根据视觉特性 设计自适应量化器，用Huffman编码，输出压缩码流；,2.扩展系统（Extended System）是基本系 统的 扩展，可选用算术编码作熵编码，还可以 选用“渐现重建”（Progressive Build-up）的工作方式，即图像由粗而细地显示；,3.独立的lossless压缩，采用预测编码及Huffman 编码或算术编码，可保证失真率为0。,基于小波变换的图像压缩标准JPEG2000国际标准。1.低码率压缩效率。传统的JPEG使用DCT，需将图像分块，限制了图像的压缩倍数；小波是基于整幅图像处理，可实现高压缩比，避免了“分块”效应；嵌入式编码：在解码端无论获得多少码流，都能在当前码率下最优地将图像重建；3.引入“视觉权重”概念。根据视觉特性模型，对小波系数进行调整；4.实现“区域”编码策略，即对图像中感兴趣的部分进行单独的编、解码，而无需将整幅图像完全重建出来；5.开放性结构，可随时加入新的算法模块；,H.261：第一个高效视频编码标准算法。图像编码的其他几个国际标准（如JPEG、MPEG、CCIR723等）都是由它演变而来。1984年12月，CCITT第15研究组成立了“可视电话编码专家组”，并在1988年提出了视频编码器的H.261建议。它的目标是P64K（P=130）码率的视频编码标准，以满足ISDN日益发展的需要。主要应用对象是视频会议的图像传输。,要点是：用运动补偿进行帧间预测，以去除时域的相关性；幀内以88，1616进行DCT变换，以去除图像在空域上的相关性；对DCT变换系数设置自适应量化器，以利用人们的视觉特性；再采用Huffman熵编码，获得压缩码流。,H.263：是一种低码率的视频编码标准，码率可达H.261的一半，是对H.261标准的很好的改进。它仍然以MC/DCT为核心算法，与H.261不同的是，它采用半像素精度进行运动补偿，传送的符号采用变长编码。除了这些基本编码算法外，H.263还包括下面四个可选的编码方法。所有这些算法可以通过某种组合使用，也可以单独使用。无约束运动矢量模式；基于句法的算术编码模式；先进预测模式；PB帧模式。,MPEG系列：为适应有声音的运动图像压缩的需要，1988年5月，CCITT和ISO成立了“运动图像专家组”（Motion Picture Experts Group，MPEG），研究运动图像的编码标准。MPEG的帧内编码采用了JPEG推荐的DCT技术，此外引入了帧间MC技术，因此，MPEG是JPEG的延续，同时尽量与H.261标准兼容，但比H.261要复杂的多。MPEG标准包括MPEG视频、MPEG音频和MPEG系统三个部分。它采用了MC、DCT、可变长编码（VLC）等多种技术。MPEG1标准于1993年8月正式通过，用于对连续传送码率为 1.5Mbits/s 存储和传输媒体进行操作，CD、硬盘和光盘驱动器；,MPEG2 1994年提出，码率在310Mbits/s之间。应用：数字电视、数字通信、其他数字媒体等。MPEG4 1999年提出，为多媒体数据压缩编码提供了更为广阔的平台，它定义的是一种格式、一种框架，而不是具体的算法，它希望建立一种更自由的通信与开发环境。于是，MPEG4的目标就定义为：支持多种多媒体的应用，特别是多媒体信息基于内容的检索和访问，可根据不同的应用需求，现场配置解码器。编码系统也是开放的，可随时加入新的高效的算法模块。,MPEG7：“多媒体内容描述接口”（Multimedia Content Description Interface），它将为各种类型的多媒体信息规定一种标准化的描述，这种描述与多媒体信息的内容本身一起，支持用户对其感兴趣的各种“资料”的快速、有效地检索。各种“资料”包括：静止图像、图形、音频、动态视频，以及如何将这些元素组合在一起的合成信息。MPEG7标准将用于以下领域：数字化图书馆；多媒体目录服务；广播式媒体选择；多媒体编辑。,MPEG21：目前，MPEG组织正在酝酿制定MPEG21。1999年8月MPEG主席Leonardo Chiariglione提出了“Techinologies for E-Content”的报告，引起了各国代表团的关注，1999年10月日本代表团在MPEG国际会议上提出了制定MPEG21标准的提案，以支持电子内容传输和电子贸易，1999年12月MPEG会议通过了征集Multimedia Framework技术报告的议案，2000年3月，MPEG会议成立了MPEG21工作组。,图像编码标准,标准 用途 码率 通过时间JPEG 静止图像 压缩比50 1991.3MPEG-1 VCD，MP3 1.5Mb/s 1992MPEG-2 DVD、HDTV4-10Mb/s 1994.11H.261 电视电话、会议电话 P64Kb/s 1990.12H.263 低码率传输业务 H.261一半 1995MPEG-4 甚低码率视频业务 1998.11JPEG2000 静止图像2000MPEG-7、21 多媒体2000.5,8.7 重叠正交变换（LOT）(Lapped Orthogonal Transform）-DCT应用讲座（2）,DCT已广泛应用于语音和图像的压缩。用DCT做压缩时,将一幅图像分成88或1616的子图像分别实现，由于各个变换块之间的不连续性就产生了块效应（block effect)。块效应将导致重建图像上出现较明显的方格，或是在重建的语音信号中掺杂可以听到的周期性的噪声。LOT就是为克服块效应而引入的，是一种改进的DCT。,DCT：,LOT：,实质：增加了滤波器的长度，由8变成16；但要保 证变换后的数据长度不变；关键：因为 P 是长方阵，所以无法要求其是正交阵，但要求,LOT示意图,关键问题：找到矩阵，使其列向量构成正交基。（具体构造方法见教材）,与本章有关的MATLAB文件：,1.dct.m 一维DCT。调用格式是：y=dct(x),或 y=dct(x,N)。x是原始信号，y是x的DCT，N是变换数据的长度，若x的长度小于N，则在后面补零，反之，则给以截短；2.dct2.m 二维DCT。调用格式是：Y=dct2(X),或 Y=dct(X,M,N)。X是待变换的图像，Y是X的2D DCT，M,N是变换图像的大小，若X的尺寸小于M、N，则在后面补零，反之，则给以截短；3.idct 一维DCT反变换；4.idct2 二维DCT反变换；,