离散余弦变换原理

1、1离散余弦变换的原理 视频编码和图像编码的对象主要是自然视频信号、图像信号或其预测残差(包括帧内和帧间)信号。号在空间域上的相关性己部分减弱，但是统计数据表明，在某些情况下残差数据之间仍有其较强的相关性。所以类似于图像信号和视频信号，残差信号也需要进行一定的处理。这种去除相关性的处理过程就是变换编码过程。变换编码的基本思路是将在空间域中描述的视频信号、图像信号或残差信号变换到另一个正交向量空间(变换域)中。如果该正交向量空间的基向量与图像本身的特征向量很接近，那么经过正交变换后，系数间的相关性基本消除，能量主要集中在直流和少数低频的变换系数上。因此，对频率域变换系数编码的效率远远高于直接对空间

2、域像素编码，从而达到图像压缩的目的。1.1 K一L变换的基本原理自然图像信号或视频信号在空间上存在的相关性可以用协方差矩阵来表示。协方差矩阵是图像统计特性的重要反映。令NxN的编码图像块的协方差矩阵为C:，根据正交变换的性质，在对NxN像素块作变换的同时，对其协方差矩阵C、作同样的变换就可以得到变换系数块的协方差矩阵Cy。理想的变换能使变换后的变换系数块中各个系数互不相关，让Cy成为对角阵，即变换系数块中的各个系数只是自相关系数非零，而互相关系数全为零。K一L变换就是在这种基本思路下产生的。它根据C、的特征值求出的特征矢量作为变换矩阵的基向量，得到变换矩阵A，然后用A对C、实施下式变换，即:

3、由矩阵理论可知，上式变换的结果是典型的对角阵。可见，经过K一L变换可以将空间域的相关性完全消除。如果取特征值前面k个绝对值较大者，则还原后的空间域信号的均方误差最小，换言之还原图像的逼真度最佳。但是，K一L变换的难点在于要根据图像的统计特性来决定变换矩阵，即变换矩阵与输入数据有关，需要求出C:的特征向量矩阵作为变换矩阵。严格地说，C、并不是一个固定的矩阵，因而它反映的特征向量矩阵和参数设计的不确定性是制约它实际应用的关键。而且至今为止K一L变换没有快速算法，用实际电路来完成是十分困难的。1.2离散余弦变换的基本原理鉴于K一L变换的缺点，视频编码和图像编码中需要有一个算法相对简单，而变换矩阵与K

4、一L变换矩阵相似的正交变换来实现去相关处理。而在斜变换(slantTransform)、沃尔什一哈达马变换(HadamardTransform)、哈尔变换(HaarTransform)、傅里叶变换(Fourier介ansform)等众多离散正交变换中，离散余弦变换与K一L变换最接近。离散余弦变换是N.Ahmed、T.Natarajan以及K.R.Rao在1974年提出的l2。对于一个MxN的像素块，其二维离散余弦变换(DCT)定义为:  而二维离散余弦逆变换(IDCT:InverseDisereteCosineTransform)定义为:  上述两式中的

5、变量气，c、定义如下:    对于自然图像信号和视频信号，其空间域各个像素之间的递变特性一般可以近似等效为1阶Markov过程，协方差矩阵C、具有近似ToePlitz矩阵的形式: 研究表明，构成K一L变换矩阵的向量也就是ToePhtz矩阵的特征向量。与此同时，离散余弦变换矩阵逼近于ToePutz矩阵的特征向量矩阵，所以离散余弦变换矩阵与自然图像的K一L变换矩阵十分相似。经过离散余弦变换后的变换系数块的协方差矩阵Cy非常接近对角阵，即除了对角线元素以外，其它很多元素都近似为0，并且在左上角集中了主要能量。这反映了自然图像大部分区域变化不大，亮度突

6、变只占少数，即图像能量以低频成分为主的特性。通过变换后的量化，舍弃对视觉效果影响较小的次要信息，可达到进一步的压缩效果。虽然从去相关性能的意义上讲，DCT是一种次于K一L变换的准最佳变换，但是从算法实现的角度来看，DCT则远远优于K一L变换。首先，当图像的分块大小确定后，DCT的变换矩阵也就随之确定了，不随输入信号的统计特性变化而变化;其次，二维DCT能够分解成两次一维DCT，有利于硬件实现。同时，DCT有很多公开的快速算法，这些快速算法的相继提出进一步推动了其快速发展和应用，使得DCT己经成为了H.261、MPEG一1、MPEG一2、H.263、MPEG4、JPEG等国际图像视频压缩标准的基

7、本算法。1.3离散余弦变换的实现实现DCT的方法很多，最直接的是根据DCT的定义来计算。以二维8xSDCT为例，需要作4096次乘法和3584次加法。这种算法的实现需要巨大的计算量，不具有实用价值。在应用中，需要寻找快速而又精确的算法。较为常用的方法是利用DCT的可拆分特性，同样以二维8xSDCT为例，先进行8行一维DCT需要64xs次乘法和56xs次加法，再进行8列一维DCT要64xs次乘法和56xs次加法，共需要64x8xZ二1024次乘法和56x8xZ二896次加法，计算量减少为直接浙江大学硕士学位论文离散余弦变换的设计与实现计算的1/4。除此之外，DCT还有很多公开的快速算法。快速算法

8、主要是通过减少运算次数而减少运算时间，这对于设计快速的硬件系统非常有效。二维DCT的快速算法则一般采用行列分离DCT算法，即转换为两次一维变换，其间通过转置矩阵连接。最为经典和常用的快速算法是由Arai等人于1988年提出的AAN算法l3以及由Loeffier等人于1989年提出的LLM算法14。这里值得一提的是，需要运算次数最少的算法是l习中提出的二维直接计算算法。但是，由于行列分离DCT算法能够重复使用一维变换结构，因此在实际实现上，尤其在硬件上比二维直接计算算法更有优势。对于一维8点IX二T来说，AAN算法通过将最后的缩放和(反)量化合二为一，因此共只需要5次乘法和29次加法。此算法主要缺点是在固定精度的定点运算中，由于缩放和量化相结合导致计算结果不精确。原始的量化值越小，精度越差，所以对高质量图像的影响比低质量图像要大。二维8xs点DCT采用AAN算法需要16xs一80次乘法和16x29=464次加法(不考虑缩放)，是从一维DCT计算二维DCT运算量最小的方法。相比之下，使用LLM算法实现一维8点D