第四讲-变换技术

第四讲变换技术王荣刚北京大学深圳研究生院数字媒体研究中心2015.10.09内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT2为什么要做变换？将空域信号变换到频域信号，有效地去除了信号的相关性，并使大部分能量集中到低频区域根据变换的这一特点，有选择的编码部分显著的低频域信号，丢弃不显著的高频域信号，可以达到提高压缩效率的目的3变换几个概念线性变换，TNxN为一个矩阵，xNx1,yNx1是一维矢量逆变换正交变换正交变换矩阵的行/列互相正交4问题对于给定的一组信号X，如何将其变换为另一组信号表示Y，使得Y的信息量更集中，更容易被压缩？关键是找到合适的变换矩阵T，Y=TX，使得Y的相关性最低5内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT6最佳变换将输入矢量X={x0,x1,…,xN-1},由N个随机变量构成，经过线性变换T成另一种形式Y={y0,y1,…,yN-1}，使得Y中的各随机变量之间的相关度最低，该线性变换称为最佳变换如何描述随机变量之间的相关性？7自相关矩阵对于N个随机变量，X={x0,x1,…,xN-1}，自相关矩阵为Rxx为对称矩阵如果任意两个随机变量之间是不相关的，则如果xi的均值为0，则Rxx为对角矩阵8问题一个NxN的图像块内的各个像素值是否具有相关性？如何尽量去除这种相关性？设x为NxN图像块像素值构成的随机矢量，找到T，将x变换为y:y=Tx，使得y的随机变量间相关性降低，数学表述：y的自相关矩阵接近为对角矩阵9KLT变换设y=Tx，则如果Ryy为对角矩阵，则T为最佳变换由于Rxx是一个对称矩阵：Rxx有N个互相正交的特征向量xi注意U正交，所以U-1=UT，因此只要T=UT，Ryy即为对角矩阵，y=UTx称为KLT变换10RRRRR给定x,现在已经可以找到最佳的T,使得y=Tx相关性最低，y比x更容易编码x的自相关矩阵的正交特征矢量构成T问题：解码端如何根据y恢复x?11KLT变换的弱点变换矩阵和输入数据相关变换矩阵需要传输到解码端需要求特征矩阵，计算量大变换矩阵没有规律，几乎没有快速算法如何克服以上弱点？对于给定Rxx寻找一个和KLT变换性能类似的简单变换矩阵12内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT13像素相关性模型自然图像在一定邻域内具有相关性，且相关性的大小随着像素间距离的增大而减小一阶自回归模型AR(1)：x(n)为像素值ρ为相关系数e(n)为随机噪声，互不相关且均值为零ρ接近于1的AR(1)模型可以很好的描述自然图像的像素相关性14连续N个像素的自相关矩阵ρ接近1时（0.9）,Rxx的特征矢量和一系列的不同频率的余弦信号相似，在这种情况下DCT可以近似KLT[1]15DCT变换DCT变换矩阵例如，当N=8时16C8*C8T=I8,DCT的变换核是正交的DCT变换的物理解释前向变换y=Tx(x，y是Nx1的矢量)设ti是T的第i行yi=tiT,x(内积)yi描述了x和ti的相似度，x和ti的相似度越大，yi值越大y反映了x与每个周期信号ti的相似度反变换x=TTyx是对ti的加权和，每个ti权重是yi（yi是x和ti的相似度）每个ti称为一个基矢量17二维DCT变换一维DCT变换对二维N×M空间的DCT/IDCT变换定义为：注意：每个变换系数F(u,v)都是由两个N×M矩阵做内积得到的({f(n,m)}和{})18v=0二维DCT物理解释19u=0,…,M-1,v=0,…,N-1v=0DCT性质一可分离性输入数据的二维DCT变换等价于先对输入数据做行(列)变换，然后再做列(行)变换行/列变换：对每行/列N个元素分别与N个不同频率的变换基做内积矩阵表示：20DCT性质二对称性设n的范围从0到N-1，则有因此关于中心点变换矩阵的偶数行对称，奇数行反对称正交性21内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT22快速DCT变换对NxN做二维DCT变换：求每个变换系数都需要N2次乘累加计算，共需要N4次乘法和加法运算。例如：做一次8x8变换，需要4096次乘法和加法利用DCT变换矩阵的特征可以大幅度降低计算量可分离性：将2维DCT变换变为2次1维变换，总共需要2xNxN2=2N3次乘法和加法运算做一次8x8变换，需要1024次乘法和加法对称性：DCT矩阵中很多系数的绝对值相同可以采用合并简化计算，a*b+/-a*c=a*(b+/-c)23快速变换-对称性由对称性：24进一步合并F2和F6的计算总结：计算F2和F6的计算量由16次乘法和16次加法降为4次乘法和8次加法25类似的方法扩展到其他系数，得到8点DCT快速运算蝶形图：8点DCT计算量从64次乘法和64次加法降为20次乘法和26次加法26内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT27整数变换DCT变换的问题变换矩阵系数存在浮点数，浮点运算复杂存在舍入误差，解码端无法精确重建图像（drifterrors）IfX=Hx,u=round(HTX),thenu(n)=x(n)foralln?用于与DCT变换性能类似的整数变换代替DCT方法一：寻找整数变换矩阵使得其和DCT矩阵有类似的对称性，正交性和去相关性[5]（湛伟权,89）方法二：直接对DCT矩阵中的系数进行取整舍入[6]28方法一用一些变量代替8点DCT矩阵中的值，并对每行进行适当缩放，得到如下矩阵：该矩阵正交的充分条件：另外，为了尽量和DCT类似，增加一些额外限制条件：满足上述条件的整数矩阵都可作为候选变换矩阵，选择去相关性能好的作为整数变换矩阵29如何评价变换矩阵T的去相关性能？利用T对自相关矩阵Rxx（ρ接近1）的信号X做变换得到Ryy：去相关性能：30RyyRxx8x8整数变换AVS标准采用了基于这种方法的8x8整数变换31方法二对DCT矩阵H中的系数做缩放，取整例如对于4点DCT矩阵设α=26(同模)，α=2.5（非同模，H.264）32(,)round(,)QknHkn1111111112csscsccsH2cos8c@=2sin8s@=013131313177717round2613131313717177QHD11112112round2.511111221QΗ@=整数变换归一化有些整数变换矩阵不再满足正交性为了使整数变换矩阵满足正交性，需要对整数变换矩阵进行归一化：归一化之后的矩阵满足正交性：33TICTICTI21,[,][,]jICTSSijICTij()()()TTTICTSICTSICTICTSSIICTS归一化与量化合并Cf：整数变换系数，Sf:归一化系数34内容提要为什么要做变换最优变换：KLT实用变换：DCT快速DCT整数变换ABT35ABTABT方法利用不同的变换尺寸具有不同的编码性能这一特点，通过自适应地选择变换尺寸来提高编码器的压缩性能大尺寸变换具有更好的能量集中度和图像细节保持小尺寸变换对于消除ringing效应有利H.264/AVCHighProfile在原有4×4变换的基础上又增加了8×8变换，当前编码块在4×4变换和8×8变换之间，自适应选择最优变换尺寸，可以提高编码效率达0.5dB（相当于码率节省10%）[7]36ringingDirectionalDCT传统DCT先做水平行变换，再做垂直列变换对于斜向纹理传统DCT往往会产生较多的AC系数如果变换的方向和纹理方向一致，则可能产生更少的变换系数[9]37参考文献[1]N.Ahmed,T.Natarajan,K.Rao.DiscreteCosineTransform.IEEETransactionsonComputers,C-32(1),90-93(1974)[3]W.Chen,C.Smith,S.Fralick.AFastComputationalAlgorithmfortheDiscreteCosineTransform.IEEETransactionsonCommunications,25(9),1004-1009(1977)[5]W.Cham,“Developmentofintegercosinetransformsbytheprincipleofdyadicsymmetry,”Proc.Inst.Elect.Eng.,pt.1,vol.136,pp.276–282,Aug.1989.[6]H.S.Malvar,“Low-Complexitylength-4transformandquantizationwith16-bitarithmetic,”inITU-TSG16,Sept.2001,Doc.VCEG-N44[7]M.Wien.VariableBlock-SizeTransformsforH.264/AVC.IEEETransactionsonCircuitsandSystemsforVideoTechnology,13(7),604-613(2003)[8]“VideoCodecDesign”[9]BingZeng;JingjingFu,DirectionalDiscreteCosineTransforms—ANewFrameworkforImageCoding,CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.18,no.3,pp.305,313,March200838