mhorne@ka7axd.WV.TEK.COM (Michael T. Horne) (10/20/89)
Before I go implement a 2D FFT or adapt my 1D FFT algorithm for the 2D case, does anyone have some C code laying around to do the 2D FFT that I may obtain a copy of? Mike mhorne@ka7axd.wv.tek.com ...tektronix!mhorne%ka7axd.wv.tek.com
toma@hpsad.HP.COM (Tom Anderson) (10/22/89)
> ...does anyone have some C code laying around to do the 2D FFT that I > may obtain a copy of? Please send it to me, too, or better yet, post! Tom Anderson toma@hpsad.hp.com "It's only hardware" Opinions expressed here are not HP's
sdw@hpsad.HP.COM (Steve Warwick) (10/24/89)
Try "Numerical Recipies in C" page 467 for the complete code. (This one was easy..) Steve Warwick
mfinegan@uceng.UC.EDU (michael k finegan) (10/26/89)
sdw@hpsad.HP.COM (Steve Warwick) writes: >Try "Numerical Recipies in C" page 467 for the complete code. >(This one was easy..) >Steve Warwick But don't plan to compile it on a 16 bit machine, and don't mind wasting M+N elements of your N+1 by M+1 array ... Anyone actually translate all the indices from 1 <= j <= N, to 0 <= j < N ? Michael Finegan mfinegan@uceng.uc.edu
malcolm@Apple.COM (Malcolm Slaney) (10/26/89)
In article <2576@uceng.UC.EDU> mfinegan@uceng.UC.EDU (michael k finegan) writes: >>Try "Numerical Recipies in C" page 467 for the complete code. >But don't plan to compile it on a 16 bit machine, and don't mind >wasting M+N elements of your N+1 by M+1 array ... Anyone actually >translate all the indices from 1 <= j <= N, to 0 <= j < N ? No, Numerical Recipies does not waste elements in the array. The vector and the matrix routines all allocate arrays where the first element is indexed by 1, just like Fortran. They do this by carefully subtracting an offset (generally 1) from the value returned by malloc. Then the user (the 2d fft routine, for example) can do things just like Fortran. See the vector() and matrix() routines described in the appendix. If you are going to complain about wasted space you should talk about the double indirection they do for all two dimensional arrays. But, this is a pretty good way to get around the inability to dimension two dimensional arrays at run time in C but it does cost N elements of storage. All in all I recommend the Numerical Recipies book. I wish I had the book back when I was doing my thesis. Malcolm /* nrl is number of rows (low index) nrh is number of rows (high index), etc. */ float **matrix(nrl, nrh, ncl, nch) int nrl, nrh, ncl, nch; { int i; float **m; m = (float **)malloc((unsigned int) (nch-ncl+1)*sizeof(float *)); if (!m) nrerror("Allocation failure in matrix()"); m -= nrl; for (i=nrl;i<=nrh;i++) { m[i] = (float *) malloc((unsigned) (nch-ncl+1)*sizeof(float)); if (!m[i]) nrerror("Allocation failure in matrix()"); m[i] -= ncl; } return m; } void free_matrix(m, nrl, nrh, ncl, nch) float **m; int nrl, nrh, ncl, nch; { int i; for (i=nrh;i>=nrl;i--) free((char *) (m[i] + ncl)); free((char *) (m+nrl)); }
smit@enel.ucalgary.ca (Theo Smit) (10/26/89)
In article <9520007@hpsad.HP.COM> toma@hpsad.HP.COM (Tom Anderson) writes: >> ...does anyone have some C code laying around to do the 2D FFT that I >> may obtain a copy of? > > Please send it to me, too, or better yet, post! > >Tom Anderson toma@hpsad.hp.com "It's only hardware" >Opinions expressed here are not HP's Come on, guys. This is pretty trivial stuff. I don't have a proper shar utility, so here goes: /* Simple 2D fft program. * This program assumes the existence of an in-place 1D FFT routine, * with the prototype * 1D_fft(complex *data, int size) * * size should be an integer power of 2. */ #include <stdio.h> typedef struct {float re, im} complex; main() { int i, j; complex image[y][x]; complex temp[x]; /* Larger of x or y */ read(fileno(stdin),image, sizeof(image)); for (i = 0; i < y; i++) 1D_fft(image[i], x); for (j = 0; j < x; j++) { for(i = 0; i < y; i++) temp[i] = image[i][j]; 1D_fft(temp, y); for(i = 0; i < y; i++) image[i][j] = temp[i]; } write(fileno(stdout), image, sizeof(image)); } And that's it. Since the 2D DFT is separable, it can be computed by taking the 1D DFT of all of the rows, followed by a DFT of all of the columns. Note: I wrote this program as an example. I haven't tested it for syntactic correctness (I'm not sure if 1D_fft(image[i], x) will pass in the correct pointer). For generality I'd declare image to be a pointer to pointer of complex, and allocate a 2D array using malloc(). This gives you flexibility on image size. If you were looking for a true 2D FFT, I can't help you there. Theo Smit (smit@enel.UCalgary.CA)
annala@neuro.usc.edu (A J Annala) (10/29/89)
In article <5047@orca.WV.TEK.COM> mhorne@ka7axd.wv.tek.com writes: >Before I go implement a 2D FFT or adapt my 1D FFT algorithm for the 2D case, >does anyone have some C code laying around to do the 2D FFT that I may obtain >a copy of? > >Mike >mhorne@ka7axd.wv.tek.com >...tektronix!mhorne%ka7axd.wv.tek.com Try anonymous ftp from zaphod.ncsa.uiuc.edu(128.174.20.20):pub/unsupported/viewit/89.9/* this is an hp like calculator for digital signal and image processing that provides 2D fft functions among many other operators. AJ Annala, USC Neuroscience Program p.s. If anyone decides to assume maintenance responsibility for this piece of code I would be very interested in learning about their efforts. I have been able to use small parts of the program ... but it would be nice if the whole program worked correctly.