资源预览内容
第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
第9页 / 共23页
第10页 / 共23页
亲,该文档总共23页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2016-11-30学号:院系:电子与信息工程学院指导教师:摘要离散余弦变换(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。对于 N N大小的图像而言, 这种算法需要计算 2N 个1-D DCT,算法的复杂度为了直接对整个2 维矩阵做?(?)2 。因而为了更加高效地进行DCT运算,有人提出DCT运算。目前,最为高效的DCT算法是由 Duhamel和Guillemot在1990年的一篇论文中提出的多项式变换计算方法。在这种方法中, 2-D DCT运算的乘积运算相对于传统的方法而言减小了50%。还有人提出基于 FFT的算法,这种算法的复杂度在传统方法的50%到75%之间。此外,Cho 和Lee 提出了专门针对于矩阵大小为4 4 快速 DCT 算法,这种算法仅仅局限于大小为 4 4的变换,如果要进行扩展更大的维数,则需要与迭代算法相结合, 但是如果维数很大,这种迭代算法这会大大增加整体算法的复杂度。在本次的课程报告中所展示的是一种有别于以上快速算法的方法,这种方法和 Cho 与 Lee 提出的算法有异曲同工之处,本质上来说是对他们算法的一种扩展。这种算法对于大小为?的矩阵而言,仅仅需要计算N 个1-D DCT,但是要求 ?= 2?, m?。算法需要的乘积运算次数仅仅为传统算法的50%,与Duhamel 和Guillemot的算法有着相同复杂度。 但是相比于Duhamel 和Guillemot的算法而言, 这种算法的结构有着更高的对称性,更加简单直观, 同时能够更加容易的应用到硬件的并行处理中,也更加适合VLSI的实现。(三)报告的章节安排本次报告的主要内容和章节安排如下:1. 快速 DCT算法的理论分析从数学上对算法进行理论分析, 相关公式推导,总结出最终的算法结构。2. 相应的快速 IDCT算法的理论分析基于前面的理论推导,总结出快速 IDCT算法的结构。3. 与其他快速算法的复杂度比较将此算法与传统的算法、其他算法的复杂度作数值上的比较。4. 算法的实现与测试在前面理论分析的基础上,在 MATLAB平台上实现 4 4的快速算法,并对图像做 DCT和 IDCT变换,检验算法的有效性, 同时与 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()()
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号