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