二维DCT地优化算法

《二维DCT地优化算法》由会员分享，可在线阅读，更多相关《二维DCT地优化算法（28页珍藏版）》请在装配图网上搜索。

1、word某某：学号： 院系： 电子与信息工程学院指导教师：音视频编码技术课程报告2-D DCT算法优化摘要离散余弦变换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变换能够大大的减小原数据的冗余度。如果在K-L变换之后丢弃数值娇小的

4、系数，所造成的均方误差是所有正交变换中最小的。但是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在语音和图像压缩领域的广泛应用，已经有人提出了许多快速算法和快速计算DCT的VLSI架构。DCT的传统计算方法是行-列法，先对行计算1-D DCT

6、，再对列计算1-D DCT。对于大小的图像而言，这种算法需要计算2N个1-D DCT，算法的复杂度为。因而为了更加高效地进展DCT运算，有人提出了直接对整个2维矩阵做DCT运算。目前，最为高效的DCT算法是由Duhamel和Guillemot在1990年的一篇论文中提出的多项式变换计算方法。在这种方法中，2-D DCT运算的乘积运算相对于传统的方法而言减小了50%。还有人提出基于FFT的算法，这种算法的复杂度在传统方法的50%到75%之间。此外，Cho和Lee提出了专门针对于矩阵大小为快速DCT算法，这种算法仅仅局限于大小为的变换，如果要进展扩展更大的维数，如此需要与迭代算法相结合，但是如果维

7、数很大，这种迭代算法这会大大增加整体算法的复杂度。在本次的课程报告中所展示的是一种有别于以上快速算法的方法，这种方法和Cho与Lee提出的算法有异曲同工之处，本质上来说是对他们算法的一种扩展。这种算法对于大小为的矩阵而言，仅仅需要计算N个1-D DCT，但是要求。算法需要的乘积运算次数仅仅为传统算法的50%，与Duhamel和Guillemot的算法有着一样复杂度。但是相比于Duhamel和Guillemot的算法而言，这种算法的结构有着更高的对称性，更加简单直观，同时能够更加容易的应用到硬件的并行处理中，也更加适合VLSI的实现。(三) 报告的章节安排本次报告的主要内容和章节安排如下：1.

8、快速DCT算法的理论分析从数学上对算法进展理论分析，相关公式推导，总结出最终的算法结构。2. 相应的快速IDCT算法的理论分析基于前面的理论推导，总结出快速IDCT算法的结构。3. 与其他快速算法的复杂度比拟将此算法与传统的算法、其他算法的复杂度作数值上的比拟。4. 算法的实现与测试在前面理论分析的根底上，在MATLAB平台上实现的快速算法，并对图像做DCT和IDCT变换，检验算法的有效性，同时与MATLAB自带的DCT和IDCT函数的运算时间进展比拟。5. 总结与展望分析此算法的优缺点与可改良的空间。二、 理论分析(一) 2-D DCT理论分析对于一个给定的大小为的二维矩阵X假设二维DCT矩

9、阵为DCT变换公式为： (2.1)其中，定义为对做归一化得到的变量(2.2.a)(2.2.b)利用积化和差公式，可以进展如下的变换， (2.3)将2.3带入到2.2.a中，得到 (2.4)同时，我们定义两个新的变量(2.5.a)(2.5.b)所可以表示为 (2.6)从2.5与2.6中，可以发现，二维的DCT变换可以分解为两个分量的叠加，并且这两个分量与的形式类似于一维DCT的形式。那么下面的目标就在于如何将与转换成一维DCT的形式。从而达到对于的矩阵而言，只需要计算N次一维DCT就可以获得二维DCT。一维DCT的表达式为与2.5.a和2.5.b比照可以发现，如果可以转换为的形式，那么就可以将与

10、转换成一维DCT的形式。由于，那么的值要么等于整数倍除以的余数，要么等于除以的余数。(2.7.a)或者(2.7.a)其中，如果超过这个X围，这会得到一样的的值。将2.7进展化简，就可以得到(2.8.a)或者(2.8.a)其中。从2.8中可以发现，如果取0到的不同值，那么对应得到的的序列是不一样的，这样就得到了个不同的组合，这说明，依据2.8的公式可以遍历矩阵内的所有元素。此外每一个的值都对应着一个的序列，这意味着，依据2.8可以对输入数据分成N组，每一个组内元素的下标都满足2.8，每一个分组表示为(2.9.a)或者(2.9.a)其中，二维输入数据通过2.9就可以分成N个一维数据或者用和来表示每

11、一组数据(2.10)为了进一步进展简化，假设除以N的商为，于是2.10可以化简为(2.10)按照2.10中的分组，与可以表达为， (2.11.a) (2.11.b)其中 (2.12.a) (2.12.b) (2.12.c) (2.12.d)把2.11带入到2.6中，可以得到， (2.13)为了把表示为一维DCT的和的形式，需要将转换成一维DCT的形式。把2.10带入到2.12.a中，可以得到，将上面的式子拆分为n为奇数和偶数两种情况：当n为奇数时当n为偶数是那么以同样的方式，可以获得的表达式，把2.14-2.17带入到2.13中，可以得到的新表达式，可以发现，2.19.a和2.19.b分别是序

12、列的一维DCT变换序列的第和个元素；2.19.c和2.19.d分别是序列的一维DCT变换序列的第和个元素。定义两个量：和那么2.19.a和2.19.b就分别对应着；2.19.c和2.19.d就分别对应着。这就意味着，大小为矩阵的二维DCT只需要先计算出N个一维DCT。从2.18可以看出，要计算出，可以先计算出和，然后再将相对应的和进展线性叠加，得到最终结果。，n为偶数时，如果把表达为:那么把2.22带入就可以得到，同样的方式，当n为奇数时，上面的两个式子意味着，总是会以的形式出现。同样，会以的形式出现。基于以上的分析，假设输入矩阵的大小为，那么这个算法就可以用以下的图来表示，图 2 8X8 D

13、CT算法结构图，O表示相加，虚线表示取反图2续8X8 DCT算法结构图，O表示相加，虚线表示取反(二) 2-D IDCT理论分析对于正交变换而言，如果不考虑系数的影响，那么其相对应的反变换就直接是正变换的反过程而已。那么可以利用这个来推导出快速IDCT算法。如果在DCT变换中不考虑2.1中前面的系数，那么反变换的算法结构就仅仅是正变换算法结构的取反。例如对于8X8的IDCT变换而言，如果不考虑系数，那么其算法结构如图3所示。可以看到，相对于图2而言，图3仅仅是将图2某某号的流向做了取反，相当于是反向做运算，然后做N个一维IDCT，其运算量与一中分析的DCT的运算量相当，相对于传统的IDCT算法

14、而言也仅仅需要50%的一维DCT变换次数。图 3 8X8 IDCT算法结构图，O表示相加，虚线表示取反图 4续 8X8 IDCT算法结构图，O表示相加，虚线表示取反但是如果将系数考虑进来，就需要做一些额外的调整，调整的过程如下：1) 对于初始输入数据对相对应的DCT系数做归一化处理2) 将第一步得到的数据乘以系数3) 每个一维IDCT的第一个输入数据需要再乘以系数经过以上三个步骤，处理后就可以得到相对应的IDCT数据。(三) 算法的复杂度分析从一和二局部的内容中可以看到对于为的DCT变换，仅仅需要计算N个一维的DCT。我们在本小节中以需要的乘法运算的次数和加法运算次数来作为算法复杂度比拟的标准

15、。由于大小的二维DCT变换仅仅需要N次一维的DCT变换，那么相对于传统的二维DCT算法而言，本报告中的算法所需要的乘法运算量就仅仅是传统方法的50%。而对于一维DCT的算法复杂度，目前比拟高效的算法需要的乘法运算量为如果在二维DCT变换中使用这个一维DCT算法，那么所需乘法运算量为，表格 1 所需乘法运算次数比拟4X432241616168X8192144104969616X16102476856851251232X3251203840274025602560表格 2 所需加法运算次数比拟4X472727068748X846446446248446616X1625922592255825312

16、53032X321337613376129501257812738至于所需的加法运算量，从前面的分析中可以知道，除了DCT运算的加法运算量，其他地方加法运算量为。而对于一维DCT变换而言，所需的加法运算量为。所以二维DCT算法所需的加法运算量为，依据2.25和2.26和其他参考文献中的快速算法，列出了表格1和表格2，分别展示了各个算法所需的乘法运算次数和加法运算次数。从表格中可以发现，本报告中的算法所需的乘法运算量与文献3中一样，并且比其他算法都要低。同时，加法运算量与其他算法根本一致。三、 实现与测试在本章节中，将根据第二章节中的DCT和IDCT快速算法的理论分析，在MATLAB平台上实现相

17、应的DCT变换算法和IDCT变换算法。然后利用这两个算法对一个实际图像做变换与反变换处理，观察处理的效果。(一) 算法的实现在本小节里面，将会依据第二章节的分析，在MATLAB平台上实现4X4的快速DCT与IDCT算法。从第二章中的分析中可以知道，快速算法可以用流向图很简洁地表示出来。那么依据前面的公式，对于4X4的DCT和IDCT变化可以得到以下的流向图，图 5 4X4算法结构图，aDCTbIDCT那么依据图5，算法的流程图如下：图 6 快速DCT算法流程图图 7 快速IDCT算法流程图(二) 算法的测试测试环境：Dell 商用台式机，MATLAB 2013a，测试图片大小为614x614.

18、图 8 快速DCT与IDCT测试效果图从图8的实际测试结果来看，原图经过了4X4的DCT变换之后，在每个4X4大小的方格内，图像的能量都集中分布于少数几个系数上，这符合正交变换的特点。同时经过了IDCT变换之后，可以完整的恢复图像原来的模样，且不存在失真与格纹现象。这证明了算法的正确性。表格 3 程序运行时间比拟函数名称调用次数运行时间函数名称调用次数运行时间main1main1fdct223716dct223716fidct223716idct223716表格3是MATLAB利用CPU的运行时间计算出来的结果，虽然结果的具体数值并不具有很高的可靠性，但是在一样条件下得出来的结果，相互之间具有

19、可比性。通过比拟可以发现，在一样的调用次数的条件下，无论是fdct2函数还是fidct2函数，其运行时间都比MATLAB已有函数的运行时间减少了将近50%。四、 总结与展望本次课程报告首先分析了离散余弦变换DCT在图像压缩领域的重要性，它本身虽然不具有压缩能力，但是变换给后续的编码和量化操作带来了便利，在多个图像、视频标准中都有应用。DCT的广泛应用也为人们对它的研究增添了动力，由于传统计算方法的效率低下，许多文献提出了相关的DCT快速算法。本次报告就研究、实现和分析了其中一种性能比拟优越的快速算法。这种快速算法的乘法运算量仅仅只有传统算法的50%，而加法运算量和其他方法相当，具有很高的效率，

20、同时，这种算法可以能够用流向图来直观的表示，简单而直观。而且由于这种算法具有比拟好的对称性，它能够很容易地应用到多线程并行处理中，这样效率又可以得到很大的提升，同时这种算法还可以直接用VLSI结构来实现，这说明这种算的应用相对简单。在进展了理论分析之后，基于理论分析在MATLAB平台上实现了此算法，并用实际图片进展了测试，测试结果明确，此算法可以快速地进展DCT变换和IDCT变换，能够完整的恢复出原图。此外，还将此算法与MATLAB自带的DCT变换和IDCT变换函数在一样的条件下进展了运行时间比拟，比拟结果明确，此算法的运行时间相对于MATLAB自带的函数减少了将近50%，具有较高的效率。虽然

21、这种的算法具有很高的效率，但是它依然有它的局限性。这种算法的最大的局限性在于，如果二维矩阵的维数很大，那么这种算法将会难以实现。因为这种算法需要对输入数据进展排列，在进展了一维DCT后还需要进展屡次的线性运算，这种排列与线性运算的组合并不具有很明显的规律性。在算法的实现过程中，对于16X16大小的矩阵，需要列出256个式子；但是对于32X32的矩阵，需要的式子达到了1024个。所以对于大型的矩阵，这种方法是不适合的，比拟适合于16X16以下的矩阵。五、 参考文献1 C.Ma, “A fast recursive two dimension cosine transform, Intellige

22、nt Robots and puter Visio: Seventh in a Series, David P. Casasent, Ed., in Proc. SPIE 1002, pp.541-548, 1988.2 M. Vetterli, “Fast 2-D discrete cosine transform , in Proc. ICASSP85, Mar. 1985.P. Duhamel and C. Guillemot, “Polynomial transform putation of 2-D DCT, in Proc. ICASSP 90 , pp. 1515-1518, A

23、pr. 1990.3 N. I. Cho and S. U. Lee, “A fast 4X4 DCT algorithm for the recursive 2-D DCT, IEEE Trans. Acoust., Speech, Signal Processing, submitted for publication.4 F. A. Kamangar and K. R. Rao, “Fast algorithm for the 2-D discrete cosine tansform, IEEE Trans, put., vol. C-31, pp. 899-906, Spet. 198

24、2.5B. G. Lee, “A new algorithm to pute the discrete cosine transform , IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-32, pp. 1243-1245, Dec. 1987.7杨帆.数字图像处理与分析.：航空航天大学, 20078全红艳，曹桂涛. 数字图像处理原理与实现方法. ：机械工业，2014六、 附件文案大全(一) 函数fdct2源码function Y = fdct2( X )%快速4X4 DCT变换函数% By 黄跃辉 2016/11/30%检

25、测输入量a,b = size(X);if a = 4 | b = 4 Y = zeros(4,4); return;end%A = zeros(4,4);B = zeros(4,4);A(1,1) = X(1,1)+X(1,4);A(2,1) = X(2,2)+X(2,3);A(3,1) = X(3,3)+X(3,2);A(4,1) = X(4,4)+X(4,1);A(1,2) = X(1,1)-X(1,4);A(2,2) = X(2,2)-X(2,3);A(3,2) = X(3,3)-X(3,2);A(4,2) = X(4,4)-X(4,1);A(1,3) = X(1,2)+X(1,3);A

26、(2,3) = X(2,1)+X(2,4);A(3,3) = X(3,4)+X(3,1);A(4,3) = X(4,3)+X(4,2);A(1,4) = X(1,2)-X(1,3);A(2,4) = X(2,4)-X(2,1);A(3,4) = X(3,1)-X(3,4);A(4,4) = X(4,3)-X(4,2);%获取变换矩阵T=zeros(4);for i=0:3 for j=0:3 T(i+1,j+1)=cos(pi*(j+0.5)*i/4); endend%对A中的每一列做一维DCT,得到Bfor i=1:4 B(:,i) = T*A(:,i);endclear A T%由B元素的

27、线性组合得到结果Y = zeros(4,4);Y(1,1) = (B(1,1)+B(1,3)*0.25;Y(2,1) = (B(2,1)+B(2,3)*sqrt(2)/4;Y(3,1) = (B(3,1)+B(3,3)*sqrt(2)/4;Y(4,1) = (B(4,1)+B(4,3)*sqrt(2)/4;Y(2,2) = 0.5*(B(3,2)+B(3,4)+B(1,2)*0.5;Y(1,2) = (B(2,2)+B(4,4)*sqrt(2)/4;Y(4,4) = 0.5*(B(1,2)-B(3,2)-B(3,4)*0.5;Y(3,4) = 0.5*(B(2,2)-B(4,4)-B(4,2)

28、-B(2,4)*0.5;Y(3,3) = 0.5*(B(1,1)-B(1,3)*0.5;Y(2,3) = 0.5*(B(2,1)-B(2,3)+B(4,1)-B(4,3)*0.5;Y(1,3) = (B(3,1)-B(3,3)*sqrt(2)/4;Y(4,3) = 0.5*(B(2,1)+B(4,3)-B(2,3)-B(4,1)*0.5;Y(2,4) = 0.5*(B(3,2)-B(1,4)-B(3,4)*0.5;Y(1,4) = (B(4,2)-B(2,4)*sqrt(2)/4;Y(4,2) = 0.5*(B(1,4)+B(3,2)-B(3,4)*0.5;Y(3,2) = 0.5*(B(2,

29、2)-B(4,4)+B(4,2)+B(2,4)*0.5;end(二) 函数fidct2源码function Y = fidct2( X )%快速4X4DCT反变换% By 黄跃辉 2016/11/30%检测输入量a,b = size(X);if a = 4 | b = 4 Y = zeros(4,4); return;end%对X做归一化处理X(1,1) = X(1,1)*4;X(2,1) = X(2,1)*4/sqrt(2);X(3,1) = X(3,1)*4/sqrt(2);X(4,1) = X(4,1)*4/sqrt(2);X(2,2) = X(2,2)*2;X(1,2) = X(1,2

30、)*4/sqrt(2);X(4,4) = X(4,4)*2;X(3,4) = X(3,4)*2;X(3,3) = X(3,3)*2;X(2,3) = X(2,3)*2;X(1,3) = X(1,3)*4/sqrt(2);X(4,3) = X(4,3)*2;X(2,4) = X(2,4)*2;X(1,4) = X(1,4)*4/sqrt(2);X(4,2) = X(4,2)*2;X(3,2) = X(3,2)*2;X = X./8;%对归一化X做线性组合B = zeros(4,4);B(1,1) = 0.5*(X(1,1)+2*X(3,3);B(2,1) = X(2,1)+X(2,3)+X(4,

31、3);B(3,1) = X(3,1)+X(1,3);B(4,1) = X(4,1)+X(2,3)-X(4,3);B(1,2) = X(2,2)+X(4,4);B(2,2) = X(1,2)+X(3,2)+X(3,4);B(3,2) = X(2,2)-X(4,4)+X(2,4)+X(4,2);B(4,2) = X(3,2)-X(3,4)+X(1,4);B(1,3) = 0.5*(X(1,1)-2*X(3,3);B(2,3) = X(2,1)-X(2,3)-X(4,3);B(3,3) = X(3,1)-X(1,3);B(4,3) = X(4,1)-X(2,3)+X(4,3);B(1,4) = X(

32、4,2)-X(2,4);B(2,4) = X(3,2)-X(3,4)-X(1,4);B(3,4) = X(2,2)-X(4,4)-X(2,4)-X(4,2);B(4,4) = X(1,2)-X(3,4)-X(3,2);%一维反DCT变换A = zeros(4,4);%获得变换矩阵T=zeros(4);for i=0:3 for j=0:3 T(i+1,j+1)=cos(pi*(j+0.5)*i/4); endendfor i=1:4 A(:,i) = T*B(:,i); %一维DCT反变换end%由A的线性组合得到结果Y = zeros(4,4);Y(1,1) = A(1,2)+A(1,1);

33、Y(2,2) = A(2,1)+A(2,2);Y(3,3) = A(3,1)+A(3,2);Y(4,4) = A(4,1)+A(4,2);Y(1,4) = A(1,1)-A(1,2);Y(2,3) = A(2,1)-A(2,2);Y(3,2) = A(3,1)-A(3,2);Y(4,1) = A(4,1)-A(4,2);Y(1,2) = A(1,3)+A(1,4);Y(2,1) = A(2,3)-A(2,4);Y(3,4) = A(3,3)-A(3,4);Y(4,3) = A(4,3)+A(4,4);Y(1,3) = A(1,3)-A(1,4);Y(2,4) = A(2,3)+A(2,4);Y

34、(3,1) = A(3,3)+A(3,4);Y(4,2) = A(4,3)-A(4,4);end(三) 主程序源码%主程序% By 黄跃辉 2016/11/30img=imread(F:研究生课程视音频-梁凡课程报告Lena.png);img = rgb2gray(img);img=double(img);img_dct=blkproc(img,4 4,dct2);img_recover=blkproc(img_dct,4 4,idct2);figure(1);imshow(uint8(img);title(原图);figure(2);imshow(uint8(img_dct);title(DCT变换图);figure(3);imshow(uint8(img_recover);title(恢复图);