四川大学计算机学院多媒体基础变换编码

变换编码四川大学计算机学院陈虎[e-mail]原理为达到目的可以通过不同的路径——殊途同归例如：数学计算机中，经常利用某些数学函数略加转换可以找出一条计算的捷径。乘法：1000000X100000＝100000000000运算时，数据很大，可以变成对数进行加法1000000X100000＝100000000000取对数lg106取对数lg105取指数10116＋5＝11算法变换基本概念先对信号进行某种函数变换，从一种域（空间）变换到另一种域（空间），再对变换后的信号进行编码处理以声音图像为例，由于声音图像大部分信号都是低频信号，在频域中信号较集中，因此将时域信号变换到频域，再对其进行采样、编码变换编码(TransformCoding)是一种函数变换，从一个信号域变换到另一个信号域，将信源输出分解/变换为其组成部分，然后根据每个成分的特性分别进行编码，去除视频信号的空间冗余，使能量集中。变换去除相关性示例设有两个相邻的数据样本x1和x2，每个样本采用3比特编码，则各有8个幅度等级，两个样本的联合事件共有64种可能用右图二维平面坐标表示考虑到相邻样值的相关性，x1和x2同时出现相近幅度的可能性最大。因此,合成可能性往往落在阴影区内0X1X2变换去除相关性示例如果对数据进行正交变换，从几何上相当于坐标系旋转45o,变成x1’、x2’坐标系，则在新坐标系下，任凭x1’在较大的范围变化，而x2’始终只在相当小的范围内变化，因此通过这样的变化就能得到一组去除大部分，甚至是全部统计相关性的另一种输出样本0X1X2X1’X2’变换编码过程变换量化译码器逆变换编码器发送端接收端GAA’G’U’输入U输出U为变换矩阵，A,A’:变换系数U’:U的逆变换矩阵酉（Unitary）变换概念线性变换v=Au，系数矩阵A称为此变换的基矩阵如果A是一个酉矩阵，则：1*TAA且**TTAAAAI其中，*表示对A的每个元素取共轭复数，T表示转置如果A是酉矩阵，且所有元素都是实数，则它是一个正交矩阵，且满足1TAA且TTAAAAI上式表明：当i=j时，内积为1；否则内积为0，所以，A的各行是一组正交向量任何两个酉变换之间的差别在于基函数（即A的行向量）的选择。正交矩阵是酉矩阵，但酉矩阵不需要是正交矩阵。正交矩阵的特点正交矩阵的特点每一行元素的平方和等于1两个不同行的对应元素乘积之和等于零上述两条对于列也成立例如cossinsincosA第一行22(cos)(sin)1第二行22(sin)(cos)1乘积(cos)(sin)(sin)(cos)0用前面的正交矩阵定义计算上述例子cossincossin10[]sincossincos01TAAI正交变换正交变换u(m,n)表示N×N的原始图象;v(k,l)表示变换系数;akl(m,n)是离散正交变换基函数1100,,,0,1NNklmnvklumnamnklN正变换(ForwardTransform)矩阵表示：VAUN×N输入信号块，向量排列N2×N2变换矩阵N×N变换系数线性：v(k,l)描述为“基函数(BasisFunction)”的线性组合1100,,*,0,1NNklklumnvklamnmnN可分离的正交变换酉变换1100,,,0,1NNklmnvklumnamnklN基函数分解表示为：,,,klklamnambnakmbln,,,AakmBblnaln可分离的正交变换可分离的酉变换的正变换11001100,,,,,,,NNmnNNmnvklumnakmalnakmumnaln11**0011**00,,,,,,,NNklNNklumnvklakmalnakmvklaln可分离的酉变换的反变换可分离的正交变换可分离的酉变换的矩阵表示。TVAUAN×N正交变换矩阵N×N变换系数反变换重要的实际意义：用2个N×N矩阵乘法代替了1个1×N2矢量和N2×N2矩阵的乘法，实现变换。使其复杂性(乘法次数）从O(N4)减少为O(N3)。N×N输入信号**TUAVA快速傅里叶变换根据DFT公式，直接计算N点一维傅里叶变换需要N2次复数乘法，N(N-1)≈N2次复数加法运算。快速傅里叶变换只需要Nlog2N次加法，0.5Nlog2N次乘法。例如M=1024，直接傅里叶变换需要大约106次操作，快速傅里叶变换只需要104次操作。2D-FFT计算量可分离的正交变换二维变换通过2个一维变换实现沿着信号块的行、列方向进行；先对行进行运算，再对列进行运算，从而达到快速的目的。NNN×N象素块行方向N-变换列方向N-变换xAxAxATVAUlkvlnankuUAUnkunmumkaT,,,,,,mnkmknlnlkkn正交基分解1111***0000,,NNNNTklklklklUvklaavklA[A*kl]表示基图象a*k表示[A*kl]的第k行a*l表示[A*kl]的第l列正交基分解应用：信息传送原理发端分解：传送v(k,l)，即将信号向量分解成它的各个基图象，变换系数则规定了原信号中各基图象所占的数量。如果一个信号，或其一部分可以近似地匹配上某一基函数，则在变换后，会产生一个对应于那个基函数的较大的变换系数。由于基函数是正交的，则这个信号对应于其它的基函数将产生较少的系数。收端合成：通过将一组被适当加权的基图象求和而重构图象，用上面的式子合成。变换系数就是其对应的基图象在求和时所乘的系数。正交基分解举例说明以上概念：给定正交矩阵A和图象矩阵U：变换系数：反变换为：11121,11342AU1112114611511122113411221120TVAVA**115111121211211134TUAVA正交基分解基图象：00011011125(1)(2)034VUAAAA合成*0011101111112211001111A*0111011111112211001111A*1011001111112211101111A*1111001111112211011111A分解：合成：0001101112515(1)(2)03420UAAAAV分解酉变换特性－能量保持与旋转酉变换信号能量不变——U矢量长度在N维空间中不变酉变换——在N维空间简单地旋转U矢量酉变换是基坐标的旋转，V分量是U在在新基坐标中的投影。若，则证明：22122***0122*0NTTTkNTnVAUVUVvkVVUAAUUUunU若：则：1111220000,,TNNNNmnklVAUAumnvkl1-D2-D酉变换特性－能量集中与变换系数方差酉变换：能量转到少数系数上，总能量不变变换前后平均能量相等：μu、Ru分别表示U矢量的均值和协方差[][][]VUEVEAUAEUA****[()()]([()()])TVVVTTUUTUREVVAEUUAARARV矩阵对角线元素给出变换系数方差:2*,,TvvukkkkkRARA直流分量1122***00NNTTTvvvuuuknkAAn平均能量112*200NNTvuuuknkTrARATrRn112200NNnkEunEvk最后得：矩阵的迹，矩阵对角线上元素的总和。U变换零均值201,0,111uuuU()R0u311213VU输入矢量U的相关RU变换系数V的相关RV（非对角系数变小）酉变换的特性举例：能量集中与去相关设其酉变换：ρ表示u(0)和u(1)的相关性酉变换特性－去相关酉变换特性总能量2σ2不变，但v(0)上的能量大于v(1)的，如ρ=0.95，则91.1%的总能量集中在v(0)上。2201uu222233011122vva从RU可见：即总能量相等的分布在u(0)及u(1)上从RV可见：231223122TvuRARA能量集中方面V的协方差：酉变换特性当ρ=0.95，说明：97.5%的能量集中在V(0)ρV（0,1)=0，说明：V(0)与V(1)不相关220011101,1101012vTvuvARARA220111vv,2122201/20,1||01314vvvEvv相关方面：u(0)与u(1)间相关为ρ；v(0)与v(1)间相关为：若ρ=0.95，则ρV=0.83ρ，变换系数之间的相关性减弱。变换矩阵的影响：若则酉变换特性--熵保持性如果把f(x,y)看作是一个具有一定熵值的随机函数，那么变换系数g(u,v)的熵值和原来图像信号f(x,y)的熵值相等。变换编码的选择原则变换编码的种类K-L变换KLT离散傅立叶变换DFT离散正弦变换DST离散余弦变换DCT哈达玛变换HadamardWalsh变换Haar变换Slant变换小波变换Wavelet去相关，能量集中（例如，KLT、DCT、Wavelat）计算复杂度低Karhunen--Loève(卡胡南-列夫)变换KLT变换产生去相关的变换系数KLT基函数是输入信号协方差矩阵的特征向量，因此，它是以统计特性为基础的，也称为特征向量变换。最优的正交变换：特征向量矩阵指向数据变化最大的方向，能够达到最优的能量集中。缺点：计算过程复杂，变换速度慢。KLT依赖信号统计特性，但很难实时计算视频的统计特性；KLT基函数不是固定的，是随图像内容改变的；KLT对图象块是不可分离；变换矩阵不能分解为稀疏矩阵。KLT变换的基核矩阵和定义协方差矩阵Ru的特征向量可以构成一个N2×N2的矩阵Φ，Φ的共轭转置Φ*T称K-L变换的核矩阵22222211211122212NNNNNNeKLT变换的定义：*()Tuvumuv正变换反变换K-L变换基核是随信号而变化的，不是固定的——自适应的。变换过程为：图像随机变量u→协方差矩阵Ru→K-L基核矢量Φ*T。事实上，在线性代数中已经学过，K-L变换基核的求法就是先求出图象的协方差矩阵R的特征值，然后求出特征向量，从而得到基核。中心化后图象向量KLT变换的特征－去相关去相关—