package FFT; /** * Diese Klasse realisiert die 2D Fourier-Transformation. * Grundlage des Algorithmus ist die 1d-fft.Die 2D-ft kann auf die 1D-fft zurueckgefuehrt werden. * So kann bei einem 2 dimensionalem Bild erst * Zeilenweise transformiert werden und dann spaltenweise. * Die Struktur des Pseudcodes ist hier zu erkennen: * *Iterative-FFT(a) * * Bit-Reverse-Copy(a,A) Methode siehe unten!!! * n <-- length[a] * for s <-- 1 to lg n * do m <-- 2^s * Wm <-- exp (2*PI/m) * W <-- 1 * for j <-- 0 to m/2-1 * do for k <-- j to n-1 by m "by m" bedeutet k jeweils um m erhohen. * do t <-- W*A[k+m/2] * u <-- A[k] * A[k] <-- u+t * A[k+m/2] <-- u-t * W <-- W*Wm * return A * * * Bit-Reverse-Copy(a,A) * for k <--0 to n-1 * do A[rev(k)]=a[k] * * rev(k) spiegelt dabei die Bits von k: z.B: 001 --> 100 */ public class fft { public void FFT1d(boolean dir, int m, double[] real, double[] imag) // dir geandert....true == alte 1 { long nn,k,i2,l,l1,l2; // i, j und i1 als int bezeichnen int i,j, i1; double c1,c2,tmp,t1,t2,u1,u2,z; /* Calculate the number of points */ nn = 1; for (i=0;i> 1; j = 0; for (i=0;i>= 1; } j += k; } /* Compute the FFT */ c1 = -1.0; c2 = 0.0; l2 = 1; for (l=0;l>(m+1))>0;m++) ; // Transform the rows real = new double[nx]; imag = new double[nx]; if (Vor) { half1=0; half2=nx>>1;} else { half1=nx>>1; half2=0;} for (j=0,ofs=0;j