DCT快速变换

核心提示：一、引言DCT变换是数字图像处理中重要的变换，很多重要的图像算法、图像应用都是基于DCT变换的，DCT快速变换，如JPEG图像编码方式，对于大尺寸的二维数值矩阵，只要开始DCT变换之前计算一次，DCT变换中就可以只查找而无需计算系数，倘若采用普通的DCT变换来进行，其所花费的时间将是让人难以忍受甚至无法达到实用

一、引言

DCT变换是数字图像处理中重要的变换，很多重要的图像算法、图像应用都是基于DCT变换的，如JPEG图像编码方式。对于大尺寸的二维数值矩阵，倘若采用普通的DCT变换来进行，其所花费的时间将是让人难以忍受甚至无法达到实用。而要克服这一难点，DCT变换的快速算法无非是非常吸引人的。

就目前而言，DCT变换的快速算法无非有以下两种方式：

1．由于FFT算法的普便采用，直接利用FFT来实现DCT变换的快速算法相比来说就相对容易。但是此种方法也有不足：计算过程会涉及到复数的运算。由于DCT变换前后的数据都是实数，计算过程中引入复数，而一对复数的加法相当于两对实数的加法，一对复数的乘法相当于四对实数的乘法和两对实数的加法，显然是增加了运算量，也给硬件存储提出了更高的要求。

2．直接在实数域进行DCT快速变换。显然，这种方法相比于前一种而言，计算量和硬件要求都要优于前者。

鉴于此，本文采用第二种方法来实现DCT变换的快速算法。

二、理论推导

限于篇幅，在此不能罗列，具体推导过程可参见《DCT快速新算法及滤波器结构研究与子波变换域图像降噪研究》华南理工大学博士论文。

三、程序实现

DCT快速变换

考虑到DCT变换中的系数要重复计算，可使用查找表来提高运行的效率，只要开始DCT变换之前计算一次，DCT变换中就可以只查找而无需计算系数。

void initDCTParam(int deg)
{
　　　// deg 为DCT变换数据长度的幂
　　　if(bHasInit)
　　　{
　　　　　　 return; //不用再计算查找表
　　　}
　　　int total, halftotal, i, group, endstart, factor;
　　　total = 1 << deg;
　　　if(C != NULL) delete []C;
　　　C = (double *)new double[total];
　　　halftotal = total >> 1;
　　　for(i=0; i < halftotal; i++)
　　　　　　 C[total-i-1]=(double)(2*i+1);
　　　for(group=0; group < deg-1; group++)
　　　{
　　　　　　 endstart=1 << (deg-1-group);
　　　　　　 int len = endstart >> 1;
　　　　　　 factor=1 << (group+1);
　　　　　　 for(int j = 0;j < len; j++)
　　　　　　　　　　C[endstart-j-1] = factor*C[total-j-1];
　　　}
　　　for(i=1; i < total; i++)
　　　　　　 C[i] = 2.0*cos(C[i]*PI/(total << 1)); ///C[0]空着，没使用
　　　bHasInit=true;
}