DCT快速变换

作者：陈祖尚 (blog:darnshong)

下载源代码
逆风编程精品

一、引言

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;

}

前向追底：

void dct_forward(double *f,int deg)

{

      // f中存储DCT数据



      int i_deg, i_halfwing, total, wing, wings, winglen, halfwing;



      double temp1,temp2;



      total = 1 << deg;



      for(i_deg = 0; i_deg < deg; i_deg  )

      {

             wings = 1 << i_deg;

             winglen = total >> i_deg;

             halfwing = winglen >> 1;

             for(wing = 0; wing < wings; wing  )

             {

                    for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing  )

                    {

                           temp1 = f[wing*winglen i_halfwing];

                           temp2 = f[(wing 1)*winglen-1-i_halfwing];

                           if(wing%2)

                                  swap(temp1,temp2); // 交换temp1与temp2的值



                           f[wing*winglen i_halfwing] = temp1 temp2;

                           f[(wing 1)*winglen-1-i_halfwing] = 

                                (temp1-temp2)*C[winglen-1-i_halfwing];

                    }

             }

      }

}

 
 
本文章更多内容：1 - 2 - 3 - 4 - 下一页>>