一、图像卷积：

二、DFT---离散傅里叶变换（Discrete Fourier Transform）

      1、傅里叶级数（DFS）：表示一个周期信号可以用一族正交完备的正弦波通过线性组合得到。

                                                建立时频关系。

                                 

      2、离散傅里叶变换（DFT）

           1）为何使用Dirac（）函数：

      3、快速傅里叶变换（FFT）:加速多项式乘法         

/************FFT***********/  #include   
      
         #include   
       
          #include   
        
           #define   N   1000  typedef   struct  {  double   real;  double   img;  }complex;  void   fft(); /*快速傅里叶变换*/   void   ifft(); /*快速傅里叶逆变换*/   void   initW();  void   change();  void   add(complex   ,complex   ,complex   *);   /*复数加法*/     void   mul(complex   ,complex   ,complex   *);   /*复数乘法*/     void   sub(complex   ,complex   ,complex   *);   /*复数减法*/     void   divi(complex   ,complex   ,complex   *);/*复数除法*/     void   output(); /*输出结果*/  complex   x[N],   *W;/*输出序列的值*/  int   size_x=0;/*输入序列的长度，只限2的N次方*/  double   PI;  int   main()  {  int   i,method;  system("cls");  PI=atan(1)*4;  printf("Please   input   the   size   of   x:\n");  /*输入序列的长度*/  scanf("%d",&size_x);  printf("Please   input   the   data   in   x[N]:(such as:5 6)\n");  /*输入序列对应的值*/  for(i=0;i
         
          0   )     {     j=j<<1;     j|=(k   &   1);     k=k>>1;     }     if(j>i)     {     temp=x[i];     x[i]=x[j];     x[j]=temp;     }     }     }         void   output()   /*输出结果*/  {     int   i;     printf("The   result   are   as   follows\n");     for(i=0;i
          
           =0.0001)     printf("+%.4fj\n",x[i].img);     else   if(fabs(x[i].img)<0.0001)     printf("\n");     else       printf("%.4fj\n",x[i].img);     }     }     void   add(complex   a,complex   b,complex   *c)     {     c->real=a.real+b.real;     c->img=a.img+b.img;     }         void   mul(complex   a,complex   b,complex   *c)     {     c->real=a.real*b.real   -   a.img*b.img;     c->img=a.real*b.img   +   a.img*b.real;     }     void   sub(complex   a,complex   b,complex   *c)     {     c->real=a.real-b.real;     c->img=a.img-b.img;     }     void   divi(complex   a,complex   b,complex   *c)     {     c->real=(   a.real*b.real+a.img*b.img   )/(    b.real*b.real+b.img*b.img);     c->img=(   a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img);     }
          
         
        
       
      

      4、2d加速图像卷积

           将2d核拆分成行向量与列向量乘积的形式 

bool convolve2DFast(unsigned char* in, unsigned char* out, int dataSizeX, int dataSizeY,                    float* kernel, int kernelSizeX, int kernelSizeY){    int i, j, m, n, x, y, t;    unsigned char **inPtr, *outPtr, *ptr;    int kCenterX, kCenterY;    int rowEnd, colEnd;                             // ending indice for section divider    float sum;                                      // temp accumulation buffer    int k, kSize;    // check validity of params    if(!in || !out || !kernel) return false;    if(dataSizeX <= 0 || kernelSizeX <= 0) return false;    // find center position of kernel (half of kernel size)    kCenterX = kernelSizeX >> 1;    kCenterY = kernelSizeY >> 1;    kSize = kernelSizeX * kernelSizeY;              // total kernel size    // allocate memeory for multi-cursor    inPtr = new unsigned char*[kSize];    if(!inPtr) return false;                        // allocation error    // set initial position of multi-cursor, NOTE: it is swapped instead of kernel    ptr = in + (dataSizeX * kCenterY + kCenterX); // the first cursor is shifted (kCenterX, kCenterY)    for(m=0, t=0; m < kernelSizeY; ++m)    {        for(n=0; n < kernelSizeX; ++n, ++t)        {            inPtr[t] = ptr - n;        }        ptr -= dataSizeX;    }    // init working  pointers    outPtr = out;    rowEnd = dataSizeY - kCenterY;                  // bottom row partition divider    colEnd = dataSizeX - kCenterX;                  // right column partition divider    // convolve rows from index=0 to index=kCenterY-1    y = kCenterY;    for(i=0; i < kCenterY; ++i)    {        // partition #1 ***********************************        x = kCenterX;        for(j=0; j < kCenterX; ++j)                 // column from index=0 to index=kCenterX-1        {            sum = 0;            t = 0;            for(m=0; m <= y; ++m)            {                for(n=0; n <= x; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += (kernelSizeX - x - 1);         // jump to next row            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        // partition #2 ***********************************        for(j=kCenterX; j < colEnd; ++j)            // column from index=kCenterX to index=(dataSizeX-kCenterX-1)        {            sum = 0;            t = 0;            for(m=0; m <= y; ++m)            {                for(n=0; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        // partition #3 ***********************************        x = 1;        for(j=colEnd; j < dataSizeX; ++j)           // column from index=(dataSizeX-kCenter) to index=(dataSizeX-1)        {            sum = 0;            t = x;            for(m=0; m <= y; ++m)            {                for(n=x; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += x;                             // jump to next row            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        ++y;                                        // add one more row to convolve for next run    }    // convolve rows from index=kCenterY to index=(dataSizeY-kCenterY-1)    for(i= kCenterY; i < rowEnd; ++i)               // number of rows    {        // partition #4 ***********************************        x = kCenterX;        for(j=0; j < kCenterX; ++j)                 // column from index=0 to index=kCenterX-1        {            sum = 0;            t = 0;            for(m=0; m < kernelSizeY; ++m)            {                for(n=0; n <= x; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += (kernelSizeX - x - 1);            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        // partition #5 ***********************************        for(j = kCenterX; j < colEnd; ++j)          // column from index=kCenterX to index=(dataSizeX-kCenterX-1)        {            sum = 0;            t = 0;            for(m=0; m < kernelSizeY; ++m)            {                for(n=0; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++inPtr[t]; // in this partition, all cursors are used to convolve. moving cursors to next is safe here                    ++t;                }            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;        }        // partition #6 ***********************************        x = 1;        for(j=colEnd; j < dataSizeX; ++j)           // column from index=(dataSizeX-kCenter) to index=(dataSizeX-1)        {            sum = 0;            t = x;            for(m=0; m < kernelSizeY; ++m)            {                for(n=x; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += x;            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }    }    // convolve rows from index=(dataSizeY-kCenterY) to index=(dataSizeY-1)    y = 1;    for(i= rowEnd; i < dataSizeY; ++i)               // number of rows    {        // partition #7 ***********************************        x = kCenterX;        for(j=0; j < kCenterX; ++j)                 // column from index=0 to index=kCenterX-1        {            sum = 0;            t = kernelSizeX * y;            for(m=y; m < kernelSizeY; ++m)            {                for(n=0; n <= x; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += (kernelSizeX - x - 1);            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        // partition #8 ***********************************        for(j=kCenterX; j < colEnd; ++j)            // column from index=kCenterX to index=(dataSizeX-kCenterX-1)        {            sum = 0;            t = kernelSizeX * y;            for(m=y; m < kernelSizeY; ++m)            {                for(n=0; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];        }        // partition #9 ***********************************        x = 1;        for(j=colEnd; j < dataSizeX; ++j)           // column from index=(dataSizeX-kCenter) to index=(dataSizeX-1)        {            sum = 0;            t = kernelSizeX * y + x;            for(m=y; m < kernelSizeY; ++m)            {                for(n=x; n < kernelSizeX; ++n)                {                    sum += *inPtr[t] * kernel[t];                    ++t;                }                t += x;            }            // store output            *outPtr = (unsigned char)((float)fabs(sum) + 0.5f);            ++outPtr;            ++x;            for(k=0; k < kSize; ++k) ++inPtr[k];    // move all cursors to next        }        ++y;                                        // the starting row index is increased    }    return true;}