Discrete Fourier Transform And Two-Dimensional Discrete Fourier Transform

发表于   |   分类于   |  

DFT Formula


DFT

N is the size of the sequence. Fundamental Components W = e^[-j*(2pi/N)], W^(-nk) is K subharmonic component.
The relation between Euler Formula and Trigonometric Function is:

e^(it) = cos(t)+i·sin(t)
e^(-it) = cos(t)-i·sin(t)

DFT Code

I deleted my DFT code unconsciously. The code below is downloaded on the Internet. Thanks Calcular

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Author: Calcular
struct complex{  
    double r,i;  
};  
complex multi(complex a,complex b){  
    complex tmp;  
    tmp.r=a.r*b.r-a.i*b.i;  
    tmp.i=a.r*b.i+a.i*b.r;  
    return tmp;  
}  
int fi(double in){  
    if((in-(int)in)>0.5) return (int)in+1;  
    else return (int)in;  
}  
void DFT(int *in,double **out,const int &n)  
{  
    int i,j;  
    complex **W=new complex*[n];  
    for(i=0;i<n;i++){  
        W[i]=new complex[n];  
    }  
    complex *lis=new complex[(n-1)*(n-1)+1];  
    lis[0].r=1;lis[0].i=0;  
    lis[1].r=cos(2.0*PI/n);  
    lis[1].i=-1.0*sin(2.0*PI/n);  
    for(i=2;i<=(n-1)*(n-1);i++){  
        lis[i]=multi(lis[1],lis[i-1]);  
    }  
    for(i=0;i<n;i++){  
        for(j=0;j<n;j++){  
            W[i][j]=lis[i*j];  
        }  
    }  
    complex sum;  
    for(i=0;i<n;i++){  
        sum.r=0;sum.i=0;  
        for(j=0;j<n;j++){  
            sum.r+=in[j]*W[i][j].r;  
            sum.i+=in[j]*W[i][j].i;  
        }  
        out[i][0]=sum.r;  
        out[i][1]=sum.i;  
    }  
    for(i=0;i<n;i++) delete []W[i];  
    delete []W;  
    delete []lis;  
}

2D-DFT Formula




f(x, y) is a matrix of size MxN, the relation between Euler Formula and Trigonometric Function is:

e^(it) = cos(t)+i·sin(t)
e^(-it) = cos(t)-i·sin(t)

2D-DFT Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Author: 围城
typedef struct complex
{
	double real;
	double imagin;
} COMPLEX;
int DFT2D(double *src,COMPLEX *dst,int size_w,int size_h){  
	for(int u=0;u<size_w;u++){  
		for(int v=0;v<size_h;v++){  
			double real=0.0;  
			double imagin=0.0;  
			for(int i=0;i<size_w;i++){  
				for(int j=0;j<size_h;j++){  
					double I=src[i*size_w+j];  
					double x=Pi*2*((double)i*u/(double)size_w+(double)j*v/(double)size_h);  
					real+=cos(x)*I;  
					imagin+=-sin(x)*I;  
				}  
			}  
			dst[u*size_w+v].real=real;  
			dst[u*size_w+v].imagin=imagin;  
		}  
	}  
	return 0;  
}