图像二维整数离散余弦变换（DCT）变换算法.doc

光电图像处理综合课程设计图像二维整数离散余弦变换（DCT）变换算法和DSP实现 20 13年 10 月 23 日目录摘要、关键词-1一. 背景-1二课程设计的目的和任务-1三. 离散余弦变换原理-1四整数离散余弦变换原理-2五采用蝶形快速算法实现整数DCT-36 程序设计流程图-4七. C语言程序设计-4八结论-8九心得-8参考文献-8I摘 要 为了更有效地计算二维离散余弦变换DCT,提出了一种直接作用于二维数据集的快速算法,分析了该算法的运算特点。并用C语音程序实现了一个44和88点的整数DCT变换。关键词 离散余弦变换 二维 快速算法 一. 背景离散余弦变换（简称DCT）自从1974年提出后，在图像和视频编码领域得到了广泛的应用，其变换性能在所有次优变换中非常显著，能极大地去除图像元素在变换域中的相关性，为高效率的图像压缩奠定了基础。因此不断有新的DCT的快速算法提出。二维DCT的常规算法是行、列法，对于计算NN DCT，需要计算2N个一维DCT。为了更有效地计算二维DCT,在这里提出了一种直接作用于二维数据集的快速算法 该算法对于计算NN DCT（N=）只需计算N个一维DCT（N=）因此,本算法的目的是减少运算次数,即所需乘法次数只是常规算法的一半。本算法的计算结构具有高度的规则性,并只要求用实数进行运算。二. 课程设计的目的和任务目的：1.理解离散余弦变换和逆变换的原理；2.理解整数离散余弦变换原理；3.掌握4*4点的整数DCT变换，8*8点的整数DCT变换。任务：1.阐述离散余弦变换和逆变换的原理、整数离散余弦变换原理；2.画出程序设计流程图；3.C语言程序设计：4*4点的整数DCT变换；4.DSP程序调试（基于实验现有图像处理程序）；5.完成课程设计报告撰写。三.离散余弦变换原理离散余弦变换(DCT for Discrete Cosine Transform)是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(DFT f),但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)。二维离散余弦变换正变换（公式1）：2逆变换（公式2）：其中： 44变换系数矩阵如下：更为简洁的定义方法是采用矩阵式定义。根据以上公式定义可知，离散余弦变换的系数矩阵可以写成如下：四.整数离散余弦变换原理由于DCT的变换矩阵式是用浮点数表示，浮点运算量较大，占用较多的系统资源。为了提高变换效率，DCT有发展出用定点计算或者较大的整型变换逼近浮点运算，由于存在精度误差，即使没有经过量化，反变换后也不能完全恢复图像数据，也就是编码的可逆性不强。整数变换的产生，同时解决了计算精度误差大和编码效率低的问题，其特点是用整数变换矩阵代替DCT的浮点数变换矩阵，这样变换过程完全是整数运算，不存在精度误差，保证了编码的可逆性;同时整数乘法可用加减法和位移代替，因此变换过程可以完全通过加减法和位移实现，运算量大幅度减少。以44的图像块为例进行变换操作，则相应的44变换矩阵为：相应的矩阵显示的二维DCT定义为等效： 其中, d =c/b(01414). 为了简化计算, 取d =1/2,再经过加减和左移就可实现。整数DCT的变换与通常DCT运算结果近似,但因为b和c的值有所变化,所以结果有差别五.采用蝶形快速算法实现整数DCT观察公式（1），会发现F(u,v)可以通过两次一维整数DCT变换来实现，先对矩阵的每行进行一维整数DCT变换，在对所得矩阵的每列应用一维整数DCT进行变换，这样每次一维整数DCT就可以采用蝶形快速算法进行运算，可以节省运算时间，如下图所示：蝶形快速算法利用了矩阵乘法中的重复单元，将这些冗余计算储存起来，很大程度上减少了运算次数，易于在DSP处理器上实现。六.程序设计流程图由于NN二维离散函数f(x,y)的DCT变换为F(u,v),从公式（1）可看出其存在可分离性质：根据可分离性原理，一次二维DCT变换，可以通过二次一维DCT正变换完成，其算法流程如下所示：Error! No bookmark name given.NN二维离散序列f(x,y)F(x,v)F(u,v)按行进行一维DCT变换按列进行一维DCT变换七.C语言程序设计4*4与8*8点的整数DCT变换只是数组的不同，两者算法的本质是一样的，这里以8*8为例，用C语言实现DCT变化，代码如下：#include stdio.h#include math.h#define PI 3.14159262#define N 8 /指定N的大小void origdata(int aNN) /输出8*8的原始数据int i,j;for(i=0;iN;i+)for(j=0;jN;j+)printf(%d ,aij);if(j=7)printf(n);void DCT(int fNN,float mNN) /DCT变换子程序int x,y,i,j,l;float coffNN,doffNN,DNN=0;for(y=0;yN;y+) /计算变换系数矩阵coffcoff0y=(sqrt(2.0/N)*(sqrt(1.0/2.0);for(x=1;xN;x+) for(y=0;yN;y+)coffxy=(sqrt(2.0/N)*cos(2*y+1)*x*PI/(2*N); printf(COFF: n); /输出变换系数矩阵for(i=0;iN;i+)for(j=0;jN;j+)printf(%f ,coffij);if(j=7)printf(n); for(x=0;xN;x+) /求coff的转置矩阵dofffor(y=0;yN;y+)doffxy=coffyx;for(i=0;iN;i+) /矩阵coff和f矩阵相乘，结果为矩阵D for(l=0;lN;l+)Dil=0;for(j=0;jN;j+)Dil=Dil+ coffij*fjl; printf(n); for(i=0;i N;i+) /矩阵D和矩阵doff相乘,结果为矩阵m，即经过DCT变换得到的矩阵for(l=0;lN;l+)mil=0;for(j=0;jN;j+)mil=mil+ Dij* doffjl;printf(输出DCT矩阵n);for(i=0;i N;i+) /输出经过DCT变换的结果矩阵mfor(l=0;lN;l+)printf( %f ,mil);if(l=7) printf(n); printf(n); void sch(int teNN,float mNN,int nNN) /量化子程序int x,y;int trNN;for(x=0;xN;x+)for(y=0;yN;y+)trxy=(int)(mxy/texy); /除量化系数，取整数nxy=trxy;printf( %d ,trxy);if(y=7)printf(n);int bianma(int n88,int c) /一维行程编码子程序int k64,a128,i,j,t=0,e=1,d=0,l;for(i=0;i=7;i+) /把二维的编码数组转换成一维数组for(j=0;j=7;j+)kt+=nij;for(i=0;i=63;i+) /计算编码后的数据,将其存在数组a中l=i+1;if(ki=kl) e+;elsead+=e;ad+=ki;e=1;printf(编码输出:n);for(i=0;i=127;i+) /输出编码后的数据printf(%d ,ai);ci=ai;/把得到的编码后的数组a的值复制到数组c中printf(n);return d;/返回数组c的长度void main() /*8*8图像块数据如下*/float m88,b88;int s, number,n88,c52,data; int a88=139,144,149,153,155,155,155,155,144,151,153,156,159,156,156,156,150,155,160,163,158,156,156,156,159,161,162,160,160,159,159,159,159,169,161,162,162,155,155,155,161,161,161,161,160,157,157,157,162,162,161,163,162,157,157,157,162,162,161,161,163,159,158,158;int Fy88=16,11,10,16,24,40,51,61,/量化系数矩阵Fy12,12,14,19,26,58,60,55,14,13,16,24,40,57,69,56,14,17,22,29,51,87,80,62,18,22,37,56,68,109,103,77,24,35,55,64,81,104,103,77,49,64,78,87,103,121,120,101,72,92,95,98,112,100,103,99;printf(8*8图像块数据:n);/输出需要处理的图象数据块数据origdata(a); /调用原始图像模块程序printf(变换系数矩阵:n);DCT(a,m); /调用DCT变换函数printf(输出量化后的矩阵:n); sch(Fy,m,n); /调用量化函数 number=bianma(n,c); /调用编码函数printf(原始数据量：n);printf(%d n,s=8*64); /输出原始数据量printf(编码后的数据总量:n);data=number/2*3+number/2*8; printf(%d n,data); /输出编码后的数据总量printf(压缩率: n);printf(%f% n,data*1.0/s*100); /输出压缩率（在此，我用一个8*8数组来代表一张图片，对其进行DCT变换后）八.结论将二维DCT变换分离成两次一维整数DCT变换来实现，使乘法次数减少，降低运算次数，达到快速运算的目的。九.心得万事开头难。的确，没有做之前总觉得很难，不知如何下手。做功课的第一步是先查资