Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!ubc-cs!alberta!calgary!enel!smit
From: smit@enel.ucalgary.ca (Theo Smit)
Newsgroups: comp.dsp
Subject: Re: Looking for 2D FFT code...
Message-ID: <1966@cs-spool.calgary.UUCP>
Date: 26 Oct 89 16:07:17 GMT
References: <5047@orca.WV.TEK.COM> <9520007@hpsad.HP.COM>
Sender: news@calgary.UUCP
Reply-To: smit@enel.UUCP (Theo Smit)
Organization: U. of Calgary, Calgary, Alberta, Canada
Lines: 52
Summary: Get real!

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)