Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site islenet.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!lll-crg!well!ptsfa!dual!islenet!bob
From: bob@islenet.UUCP (Bob Cunningham)
Newsgroups: net.graphics
Subject: Re: FFT of image in sections..
Message-ID: <1531@islenet.UUCP>
Date: Sun, 25-Aug-85 18:43:54 EDT
Article-I.D.: islenet.1531
Posted: Sun Aug 25 18:43:54 1985
Date-Received: Thu, 29-Aug-85 23:56:18 EDT
References: <298@ur-laser.uucp>
Organization: Hawaii Institute of Geophysics
Lines: 20

There are two approaches I know of to efficiently get the FFT of a large
2D image.

The simplest approach, assuming you already have in hand an efficient 1D
FFT routine, is to take the FFTs of the original rows (or columns,
depending upon how you happen to be storing the 2D image), transpose the
resulting matrix using a fast transpose algorithm, then FFT those rows.

Depending upon what you want to do with the transformed data, it probably
won't be necessary to transpose that resultant (except in the reverse
process of doing the inverse FFT).

The second approach, more elegant, would be to develop a specialized 2D FFT
algorithm that decimates the 2D array directly, binding both 1D transforms
together (essentially butterflying partitions of original 2D array, where
the size of partitioned sub-arrays coincide with the amount of real memory
you can dedicate to the task).
-- 
Bob Cunningham  {dual|vortex|ihnp4}!islenet!bob
Hawaii Institute of Geophysics