二维DCT的优化算法讲解.docx

摘要离散余弦变换（DCT）是一种正交变换，它本身并不会改变信息源的熵值，因而是一种无损的变换。但是由于离散余弦变换（DCT）变换能够给量化和编码等过程创造很好的条件，因而在数字信号处理领域，特别是语音和图像压缩领域有着很广泛的应用。对于语音信号与图像信号这样相关性很强的信号而言，离散余弦变换（DCT）接近于最优的KL变换(Karhunen-Loeve Transform)。传统的2-D离散余弦变换（DCT）变换过程是行-列变换，这种方法直观简单但是效率低下，在有些实时性要求较高的图像压缩领域并不能满足要求。从离散余弦变换（DCT）的数学表达式上可以看出，其具有很高的对称性，利用这种对称性可以极大地降低算法的复杂度。本次课程报告在总结前人研究的基础上，展示并实现了一种快速变换和反变换算法，并在MATLAB平台上进行了实现与测试。结果表明，这种算法具有高效、简单、易于实现的特点。关键词：快速离散余弦变换，快速离散余弦反变换，快速算法，图像压缩2-D DCT算法优化引言研究背景在本次的课程报告中，DCT的优化算法主要是针对于2维输入数据，因而此算法主要针对的是图像处理。在图像处理领域中，图像压缩编码依据原理可以分为熵编码、预测编码、变换编码和混合编码。DCT属于其中的变换编码，变换编码还包括傅里叶变换和沃尔什变换等等。变换编码是一种数学变换对，通常是将2维空间域上的图像经过正交变换映射到另一个空间域上（例如频域），并且使得变换后的系数之间的相关性降低。就变换本身而言，它是一种在数学上无损的变换，通过反变换可以恢复原信号。但是这种变换的特点在于，变换后图像的大部分能量只集中在少数几个变换系数上，这就为量化编码和熵编码带来了很大的便利，在对系数进行编码后就能实现图像的压缩。在理论上，K-L变换是最优的正交变换，它能够完全消除图像块内像素间的线性相关性，经过K-L变换后各个系数在统计上不相关，其协方差矩阵是对角阵，因而K-L变换能够大大的减小原数据的冗余度。如果在K-L变换之后丢弃数值娇小的系数，所造成的均方误差是所有正交变换中最小的。但是K-L变换有一个很大的缺点，它的基向量是图像的协方差矩阵的特征向量。这就意味着对于不同的图像，它的基向量是不相同的，为了对图像进行K-L变换，就需要先计算每一幅图像的相关矩阵，再对相关矩阵作特征分解，取特征向量作为变换的基向量。这就使得K-L变换的使用变得很麻烦，甚至是难以实现。DCT变换的性能仅次于K-L变换，被认为是一种准最佳变换，对于图像这种相关性较大的数据，DCT的性能接近于K-L变换。此外，DCT的变换矩阵是固定的，与图像无关。而且它是构造成对称的数据序列，避免了子图像边界处的跳跃和不连续现象。傅里叶变换是应用最早的变换之一，并且也有快速算法。但是傅里叶变换存在一个很明显的缺陷，恢复出来的边界会存在不连续现象，这使得恢复的图像存图1离散余弦变换（DCT）效果图在明显可见的方格，影响图像质量。沃尔什变换比DCT简单，实时性更高，但是性能比DCT略差。基于以上的特点，DCT具有广泛的应用，在常见的JPEG静态图像编码以及MJPEG、MPEG动态图像编码等标准中都有应用。这种应用的广泛也对DCT的算法效率提出了更高的要求，对DCT快速算法也有着更加迫切的需求。前人研究由于DCT在语音和图像压缩领域的广泛应用，已经有人提出了许多快速算法和快速计算DCT的VLSI架构。DCT的传统计算方法是行-列法，先对行计算1-D DCT，再对列计算1-D DCT。对于大小的图像而言，这种算法需要计算2N个1-D DCT，算法的复杂度为。因而为了更加高效地进行DCT运算，有人提出了直接对整个2维矩阵做DCT运算。目前，最为高效的DCT算法是由Duhamel和Guillemot在1990年的一篇论文中提出的多项式变换计算方法。在这种方法中，2-D DCT运算的乘积运算相对于传统的方法而言减小了50%。还有人提出基于FFT的算法，这种算法的复杂度在传统方法的50%到75%之间。此外，Cho和Lee提出了专门针对于矩阵大小为快速DCT算法，这种算法仅仅局限于大小为的变换，如果要进行扩展更大的维数，则需要与迭代算法相结合，但是如果维数很大，这种迭代算法这会大大增加整体算法的复杂度。在本次的课程报告中所展示的是一种有别于以上快速算法的方法，这种方法和Cho与Lee提出的算法有异曲同工之处，本质上来说是对他们算法的一种扩展。这种算法对于大小为的矩阵而言，仅仅需要计算N个1-D DCT，但是要求。算法需要的乘积运算次数仅仅为传统算法的50%，与Duhamel和Guillemot的算法有着相同复杂度。但是相比于Duhamel和Guillemot的算法而言，这种算法的结构有着更高的对称性，更加简单直观，同时能够更加容易的应用到硬件的并