VCLib Documentation  6.12.2

Fast Fourier Transform (FFT)

Fast Fourier Transform (FFT)

Functions

I32 vc_fft (image *src, image *dst, I32 *mean, I32 *scale)
 Perform the 2D FFT ( 16 Bit). More...
 
I32 vc_ifft (image *src, image *dst, I32 *mean, I32 *scale)
 Perform the Inverse 2D FFT ( 16 Bit). More...
 
F32 fft_window_hanning (F32 dist, I32 endInterval)
 Returns Grey Values for Generating a Hanning Window. More...
 
I32 draw_fft_window (image *psImgOut, F32(*func)(F32, I32))
 Draw Rotational Invariant Window For FFT Windowing. More...
 
I32 FFTInitTwiddle (I32 size)
 Initialize Twiddle Factor Table for 2D FFT and inverse 2D FFT. More...
 
void FFTDeinitTwiddle ()
 Release Twiddle Factor Memory (2D FFT and inverse 2D FFT). More...
 
I32 GenCplxImg (image *src, image *dst, I32 *mean)
 Copy Image and Change Type to IMAGE_CMPLX16. More...
 
I32 DisplayFFT (image *src, image *dst, I32 log)
 Convert Complex FFT Image to U8. More...
 
I32 DisplayInvFFT (image *src, image *dst, I32 mean, I32 scale)
 Convert Complex IFFT Image to U8. More...
 
I32 FindMaxCplx (image *src, I32 *ix, I32 *iy)
 Find Maximum in Complex Image. More...
 
I32 CalcPolarCoordinates (image *dst, I32 deg)
 Calculate Polar Coordinate Table. More...
 
I32 DeleteFreq (image *src, image *pol, I32 minrad, I32 maxrad)
 Delete Frequency in FFT-Space. More...
 
I32 CalcAngleHisto (image *src, image *pol, I32 mode, I32 minfreq, I32 maxfreq, U32 *AngleHisto, I32 nr)
 Calculate Angular FFT Histogram. More...
 
#define draw_fft_window_hanning(psImgOut)   draw_fft_window(psImgOut,&(fft_window_hanning))
 Draws a Hanning (von Hann) Window. More...
 
#define apply_fft_window(psImgToMask, psImgWindow, psImgOut)   mul2(psImgToMask, psImgWindow, psImgOut, -8)
 Applies a FFT Window at Data. More...
 

Detailed Description

The Fast Fourier Transform Algorithm (FFT) is an efficient algorithm to compute the discrete Fourier transform and its inverse. In the following we have FFT functions for 2D image data as well as 1D vectors.

For the image containing the fourier transform the data type IMAGE_CMPLX16 is used, which uses real and imaginary Values per Pixel. The real and imaginary value of one pixel follow each other directly in memory.

image_cmplx.png

Since each value, real and imaginary, are of type I16, it is best to use an I16 pointer. Image pitch is measured in pixels, so to get on line down at the image add two times the pitch to the I16 pointer since each pixel consists of two values.

Macro Definition Documentation

◆ draw_fft_window_hanning

#define draw_fft_window_hanning (   psImgOut)    draw_fft_window(psImgOut,&(fft_window_hanning))

The macro draws a window as described in the fft_window_hanning() function.

draw_fft_window_hanning() is a macro which calls draw_fft_window() with basic function fft_window_hanning() as an argument.

◆ apply_fft_window

#define apply_fft_window (   psImgToMask,
  psImgWindow,
  psImgOut 
)    mul2(psImgToMask, psImgWindow, psImgOut, -8)

The macro applies a window as described in the draw_fft_window() function to an image. apply_fft_window() is a macro which calls img2() with basic function FL_mul2f() as an argument.

Function Documentation

◆ vc_fft()

I32 vc_fft ( image Src,
image Dst,
I32 Mean,
I32 Scale 
)

This function calculates the 2D FFT of an image. Image src may be one of the following types: IMAGE_GREY, IMAGE_GREY16, IMAGE_CMPLX16. Image dst must be of type IMAGE_CMPLX16. This image type stores two 16-bit values for real and imaginary part in two consecutive memory position aligned on a 32 Bit boundary. Real and imaginary parts for the first pixel are stored as follows:

I16 real, imag, *p;
p = (U16 *)dst->st;
real = p[0];
imag = p[1];

It is possible to use the function in-place, i.e. source and destination images can be identical. The size of the images must be a power of 2 in x and y dimension or otherwise the FFT will be performed in a smaller subwindow. Reasonable values for dx and dy are between 16 and 2048.

Since the function only uses a 16bit FFT for both directions, a method for best accuracy has been implemented. This includes handling the mean or average value mean separately. The function also calculates a scale factor (scale) depending on the number of bits used during the procedure. mean and scale are results calculated by the function.

The function automatically allocates space for some internal tables. Each time the function is called with a new value for dx or dy, a new table is allocated which will be held in memory until the tables are released calling the function FFTDeinitTwiddle().

Since the function also computes the tables, the first call of vc_fft() with new values for dx or dy may take some processing time. If the user requires constant execution times, it is possible to call the function FFTInitTwiddle() on program start for all sizes dx and dy (powers of 2) of the images that need to be processed. This function allocates and computes all tables necessary for the forward and inverse FFT and will output the standard error code if the system is out of memory.

Return values
StandardError Code.
Memory Consumption
(4*dx*dy) Bytes + Several Tables allocated by FFTInitTwiddle(dx).
See also
vc_ifft().

◆ vc_ifft()

I32 vc_ifft ( image Src,
image Dst,
I32 Mean,
I32 Scale 
)

This function calculates the inverse 2D FFT of an image. Images src and dst must be of type IMAGE_CMPLX16.

See the documentation of vc_fft() for further details, since both functions are almost identical.

◆ fft_window_hanning()

F32 fft_window_hanning ( float  dist,
I32  endInterval 
)

The function returns grey values specified by von Hann for doing a hanning windowing.

The Formula used is

\[ \textrm{max}(0, 127.5 + 127.5 * \cos( \frac{\texttt{dist} * \pi}{\texttt{endInterval}})). \]

Use it with the function draw_fft_window().

Parameters
distRequested Distance from Image Center.
endIntervalDistance from Image Center where Border is Reached.
Returns
Grey Value between 0..255;

◆ draw_fft_window()

I32 draw_fft_window ( image psImgOut,
float(*)(float, I32 func 
)

The function draws a circular gradient around the image center with gradient colors returned by the function func. Therefore it can be used for removing the huge grey value jumps at the image's borders, since a fourier transform sees the image as repeated infinitely in both directions and huge grey value jumps will generate white vertical or horizontal stripes in the FFT image going through the center.

The resulting window can then be applied to the target image by using the macro mul2().

Operation Call Basic function
Draws Hanning Window draw_fft_window_hanning(psImgOut) fft_window_hanning()
Parameters
psImgOutOutput Image, must be IMAGE_GREY, psImgOut->dx = psImgOut->dy = 2^n.
funcfunction pointer for value routine.
Return values
ERR_PARAMif dx != dy or dx is not a power of 2.
ERR_FORMATif psImgOut is not of Type IMAGE_GREY.
ERR_NONEon Success.

◆ FFTInitTwiddle()

I32 FFTInitTwiddle ( I32  size)

This function allocates and calculates a twiddle factor table used by the functions vc_fft() and vc_ifft(). The function is automatically called by vc_fft() and vc_ifft() for each size of the FFT and requires a little more time for the first call of vc_fft() and vc_ifft() with a new dx or dy size of the window. It is possible to save this time by calling this function with the appropriate sizes dx and dy for the window beforehand. Call function FFTDeinitTwiddle() to release the twiddle memory if no longer used.

See the documentation of vc_fft() for further details, since both functions are almost identical.

Parameters
sizeFFT-size, must be power of 2

◆ FFTDeinitTwiddle()

void FFTDeinitTwiddle ( )

This function frees the memory previously allocated by functions FFTInitTwiddle(), vc_fft() or vc_ifft():

◆ GenCplxImg()

I32 GenCplxImg ( image Src,
image Dst,
I32 Mean 
)

Image src may be one of the following types: IMAGE_GREY, IMAGE_GREY16, IMAGE_CMPLX16. Image dst must be of types IMAGE_CMPLX16. If mean=NULL, the function just copies image src to image dst. If src has type IMAGE_CMPLX16, this will be a 100% copy. In all other cases the real part of dst will consist of the copied values from src, the imaginary part will be set to 0. If mean ≠ NULL, the mean or average value of the source image will be calculated.

◆ DisplayFFT()

I32 DisplayFFT ( image SrcCplx,
image Display8,
I32  DisLog 
)

This function converts the image src of type IMAGE_CMPLX16 into an image of type IMAGE_GREY as the destination image dst. The function is mainly used for the display of FFT images. log=0 will produce a linear, log=1 a logarithmic output. In both cases, the square root of the sum of the squared real and imaginary parts will be used. The function also re-arranges the 4 quarters of the source image to produce the conventional FFT image with the frequency 0 in the middle. The output is also scaled to the maximum value.

Returns
Standard Error Code.
Memory Consumption
None.

◆ DisplayInvFFT()

I32 DisplayInvFFT ( image SrcCplx,
image Dst8,
I32  Mean,
I32  Scale 
)

This function converts the image src of type IMAGE_CMPLX16 into an image of type IMAGE_GREY as the destination image dst. The function is mainly used for the display of IFFT images (IFFT: inverse FFT). The function only takes the real part of image src, mean is added to each pixel. The result is scaled using the value of scale. The image is not re-ordered like in DisplayFFT().

Returns
Standard Error Code.
Memory Consumption
None.

◆ FindMaxCplx()

I32 FindMaxCplx ( image SrcCplx,
I32 ix,
I32 iy 
)

This function finds the maximum of the complex absolute value in image src. The complex absolute value is defined as the square root of the sum of the squares of real and imaginary part. The maximum square root is the return value of the function as well as the position of its maximum (ix, iy).

Returns
Square Root of Maximum, or (Negative) Standard Error Code.
Memory Consumption
None.

◆ CalcPolarCoordinates()

I32 CalcPolarCoordinates ( image dst,
I32  deg 
)

This function calculates a table with polar coordinates necessary for some functions operating in the frequency domain. One quadrant of polar coordinates is stored in dst, an image of type IMAGE_CMPLX16. So, if the original FFT is of size n×m, the size of dst must be n/2×m/2. deg is the number of steps per 180 degrees. A typical value for deg is 180, i.e. one step per degree. deg should be a multiple of 2. The maximum value for deg is 65536. Since the execution time of the function can be considerable depending on the image size, sometimes in the range of several seconds, it is recommended to execute it only once at the beginning of the program and keep the table data as long as necessary.

Returns
Standard Error Code.
Memory Consumption
None.

◆ DeleteFreq()

I32 DeleteFreq ( image src,
image pol,
I32  minrad,
I32  maxrad 
)

DeleteFreq allows the deletion of frequencies f in the FFT-domain with minrad <= f < maxrad. Since the function works in-place, src is source and destination. pol is the quadrant image of polar coordinates. See function CalcPolarCoordinates() for further information. The frequencies are deleted without angular preferences.

The sizes of src and pol must fit, i.e.

  • either ( pol->dx == src->dx/2), ( pol->dy == src->dy/2) and src is full FFT,
  • or ( pol->dx == src->dx/2), ( pol->dy == src->dy) and src is half FFT.

If both conditions do not hold, the function returns ERR_PARAM.

Returns
Standard Error Code.
Memory Consumption
None.

◆ CalcAngleHisto()

I32 CalcAngleHisto ( image src,
image pol,
I32  mode,
I32  minfreq,
I32  maxfreq,
U32 AngleHisto,
I32  nr 
)

This function calculates the angular histogram for the FFT given by src.

The sizes of src and pol must fit, i.e.

  • either ( pol->dx == src->dx/2), ( pol->dy == src->dy/2) and src is full FFT,
  • or ( pol->dx == src->dx/2), ( pol->dy == src->dy) and src is half FFT.

If both conditions do not hold, the function returns ERR_PARAM.

Parameters
srcThe source image, must be type = IMAGE_CMPLX16.
polThe polar coordinate image (type = IMAGE_CMPLX16).
modeoperating mode, 0 = normal, 1 = high frequency enhance
minfreqfrequencies < minfreq are ignored
maxfreqfrequencies >= maxfreq are ignored
AngleHisto[nr]The angular histogram (output)
nrnumber of histogram bins

frequencies are in the range [0.. 1/2 * sqrt(dx*dx + dy*dy)]

Returns
Standard Error Code.
Memory Consumption
None.