lvfft(3)

LIBRARY ROUTINE
lvfft - Computes the two dimensional Fast Fourier Transform (FFT)

LIBRARY CALL
#include "vinclude.h"
int
lvfft(image1, image2, c_flg, o_image1, r_flg, o_image2, i_flg, o_image3, dir)
struct xvimage *image1, *image2, **o_image1, **o_image2, **o_image3;
int c_flg, r_flg, i_flg;
int dir;

INPUT

image1
    pointer to xvimage structure of type FLOAT or COMPLEX.

image2
    pointer to xvimage structure of type FLOAT (optional).

dir integer specifying the direction of the FFT transform. 0 is forward, 1 is inverse.

OUTPUT

c_flg
    is an integer requesting that a complex output image be produiced. Non-zero means produce the image.

o_image1
    is a pointer to the image structure pointer that will receive the complex output image, if it is desired (see above).

r_flg
    is an integer requesting that a real output image be produced. Non-zero means produce the image.

o_image2
    is a pointer to the image structure pointer that will receive the real output image, if it is desired (see above).

i_flg
    is an integer requesting that a imaginary output image be produced. Non-zero means produce the image.

o_image3
    is a pointer to the image structure pointer that will receive the imaginary output image, if it is desired (see above).

Return Value:
    1 on success, 0 on failure.

MODIFICATIONS

16-Jan-91 C.Gage - Modified code to accept either a FLOAT or COMPLEX image and output a COMPLEX image, or the REAL, or IMAGINARY parts. Routine was also modified to perform FORWARD or INVERSE FFT. Added call to powtwo() to check for proper image size.

8-Mar-91 Scott Wilson - Pixels sizes were not being transferred from input to output.

25-Aug-91 Scott Wilson - Added information about scaling and frequency shifting to the man pages.

12-Nov-91 Scott Wilson - Corrected memory leaks in lvfft. Added comment about freeing the input images.

15-Jan-92 Scott Wilson - Fixed routine so it does not free the input images!

DESCRIPTION
lvfft computes the 2 dimensional Fast Fourier Transform of an image. The input image should be square and the number of rows (or columns) MUST be a power of two.

This program will compute either a forward or inverse FFT, depending on the direction requested with the dir argument. A dir value of 0 will result in a forward FFT, and a dir value of 1 will result in an inverse FFT.

The arguments to the library routine include:

image1
    specifies the xvimage structure to either the complex or real component of the input image.

image2
    specifies the optional xvimage structure to the imaginary component of the input image. Designed to work in conjunction with the real component of the input image. If this image is not to be supplied to lvfft, then supply the value NULL for this argument.

c_flg
    is an integer flag specifying whether a complex output image is to be produced. If the c_flg is non-zero, then an image is created which will contain the complex output image.

o_image1
    is a pointer to the optional xvimage structure corresponding to the complex output image. See c_flg. If this argument is unused, supply the value NULL.

r_flg
    is an integer flag specifying whether a real output image is to be produced. If the r_flg is non-zero, then an image is created which will contain the real part of the complex result.

o_image2
    is a pointer to the optional xvimage structure corresponding to the real output image. See r_flg. If this argument is unused, supply the value NULL.

i_flg
    is an integer flag specifying whether an imaginary output image is to be produced. If the i_flg is non-zero, then an image is created which will contain the imaginary part of the complex result.

o_image3
    is a pointer to the optional xvimage structure corresponding to the imaginary output image. See i_flg. If this argument is unused, supply the value NULL.

dir is an integer that specifies the FFT direction. A value of 0 results in a forward FFT, and a value of 1 results in an inverse FFT.

If an input image is of data type COMPLEX, then both the real and imaginary parts of the data are present, however if the data type is FLOAT, then it is assumed that only the real part of the data is present and if the optional second input image representing the imaginary part is not present then the algorithm assumes the imaginary part of the data is zero.

If the imaginary component of the input data is present as the second input image, then the algorithm will use both the real and imaginary parts as input to the FFT.

For a forward FFT, the input data is multiplied by (-1)**(x+y) where (x,y) is the pixel coordinate. This has the effect of shifting the frequency domain result so that the DC component is at (N/2,N/2) rather than (0,0). For the inverse FFT case, the data is multiplied by (-1)**(x+y) AFTER the FFT processing, accounting for the fact that the input frequency domain data was center-shifted by the forward FFT. The center-shifted frequency domain representation is much easier to visualize and filter than it would be if not shifted. For more information on the shifting teqchnique, see R.C. Gonsalez and P. Wintz, "Digital Image Processing, 2nd ed, sec 3.2.2, p. 77. (1987). The center-shifting should really be an option.

For the forward FFT, there is no scaling on the data. For the inverse FFT, the data is scaled by 1/(N*n). Thus, to generate a sinewave of amplitude 1.0 for a 64x64 complex image to be handed to the inverse FFT, there should be two impulses at conjugate locations (symmetric about the center of the image) each with amplitude 0.5/(64*64). Why 0.5? It's because each impulse carries half of the power! The scaling should really be an option, but it currently is not (perhaps in a future patch).

This routine does not modify the input images.

The routine returns a 1 on success or a 0 on failure.

SEE ALSO
vfft(1), intro(3), vipl(3), verror(3), vutils(3) lvfft(3),lvlpf(3),lvspectra(3)

RESTRICTIONS
lvfft will only work on single band images of data type FLOAT or COMPLEX.

AUTHOR
Scott Wilson

COPYRIGHT
Copyright 1991, University of New Mexico. All rights reserved.