Image Inverse FFT

Overview

Image Inverse FFT implements the inverse Fourier Transform for 2D images, supporting real- and complex-valued outputs. Given a 2D spectrum (frequency domain), it returns the image representation on the spatial domain. It is the exact inverse of Image FFT algorithm.

Input as a magnitude spectrum	Output in spatial domain

Implementation

The inverse Fast Fourier Transform follows closely forward FFT's implementation, except for the sign of the exponent, which is positive here.

\[ I[m,n] = \frac{1}{MN} \sum^{M-1}_{u=0} \sum^{N-1}_{v=0} I'[u,v] e^{+2\pi i (\frac{um}{M}+\frac{vn}{N})} \]

Where:

• \(I'\) is the input image in frequency domain
• \(I\) is its spatial domain representation
• \(M\times N\) is input's dimensions

The normalization factor \(\frac{1}{MN}\) is applied by default to make IFFT an exact inverse of FFT. As this incurs in a performance hit and normalization might not be needed, user can pass the flag VPI_IFFT_DENORMALIZED to vpiSubmitImageIFFT to indicate that output must be left denormalized.

As with direct FFT, depending on \(N\), different techniques are employed for best performance:

• CPU backend
  • Fast paths when \(N\) can be factored into \(2^a \times 3^b \times 5^c\)
• CUDA backend
  • Fast paths when \(N\) can be factored into \(2^a \times 3^b \times 5^c \times 7^d\)

In general the smaller the prime factor is, the better the performance, i.e., powers of two are fastest.

Image IFFT supports the following transform types:

• complex-to-complex, C2C
• complex-to-real, C2R.

Data Layout

Data layout depends strictly on the transform type. In case of general C2C transform, both input and output data shall be of type VPI_IMAGE_TYPE_2F32 and have the same size. In C2R mode, each input image row \((X_1,X_2,\dots,X_{\lfloor\frac{N}{2}\rfloor+1})\) of type VPI_IMAGE_TYPE_2F32 containing only non-redundant values results in row \((x_1,x_2,\dots,x_N)\) with type VPI_IMAGE_TYPE_F32 representing the whole image. In both cases, input and output image heights are the same.

Usage

1. Initialization phase
   1. Include the header that defines the inverse FFT functions.

      #include <vpi/algo/ImageIFFT.h>

   2. Define the stream on which the algorithm will be executed and the input spectrum image. Since we're performing a C2R IFFT, the input width must be \(\lfloor \frac{w}{2} \rfloor+1\), where \(w\) is the output image width. Input and output heights must match.

          VPIStream stream = /*...*/;
          VPIImage input   = /*...*/;

   3. Create the output image. Again, because of C2F IFFT, the output type must be VPI_IMAGE_TYPE_F32. We're passing 0 as flags to make the function return a normalized output.

          VPIImage output;
          vpiImageCreate(w, h, VPI_IMAGE_TYPE_F32, 0, &output);

   4. Create the ImageIFFT payload. Input is complex and output is real. Problem size refers to output size.

          VPIPayload ifft;
          vpiCreateImageIFFT(stream, w, h, VPI_IMAGE_TYPE_2F32, VPI_IMAGE_TYPE_F32, &ifft);

2. Processing phase
   1. Submit the IFFT algorithm to the stream, passing the input spectrum and the output buffer.

          vpiSubmitImageIFFT(ifft, input, output, 0);

   2. Wait until the processing is done.

          vpiStreamSync(stream);

   3. Now display output using your preferred method.

For more details, consult the API reference.

Limitations and Constraints

Constraints for specific backends supersede the ones specified for all backends.

All Backends

• The following input image types are accepted:
  • VPI_IMAGE_TYPE_2F32 - complex input.
• The following output image types are accepted:
  • VPI_IMAGE_TYPE_F32 - real output.
  • VPI_IMAGE_TYPE_2F32 - complex output.

CPU

• If output has type VPI_IMAGE_TYPE_F32, its width must be even.
• Input and output rows must be aligned to 4 bytes.

CUDA

• There can be memory allocation in first call to vpiSubmitImageIFFT and every time the input or output row stride changes with respect to previous call.

PVA

• Not implemented.

Performance

For further information on how performance was benchmarked, see Performance Measurement.

Jetson AGX Xavier

size	type	norm.	CPU	CUDA	PVA
1920x1080	C2R	yes	6.3 ms	0.9757 ms	n/a
1920x1080	C2R	no	6.15 ms	0.8162 ms	n/a
1920x1080	C2C	yes	16.4 ms	1.5193 ms	n/a
1920x1080	C2C	no	14.5 ms	1.2645 ms	n/a
1024x1024	C2R	yes	5.2 ms	0.2779 ms	n/a
1024x1024	C2R	no	4.57 ms	0.1977 ms	n/a
1024x1024	C2C	yes	8.5 ms	0.6150 ms	n/a
1024x1024	C2C	no	7.4 ms	0.4587 ms	n/a
626x626	C2R	yes	34.1 ms	0.466 ms	n/a
626x626	C2R	no	34.1 ms	0.4295 ms	n/a
626x626	C2C	yes	67.5 ms	0.8276 ms	n/a
626x626	C2C	no	66.7 ms	0.774 ms	n/a

Jetson TX2

size	type	norm.	CPU	CUDA	PVA
1920x1080	C2R	yes	17.07 ms	3.05 ms	n/a
1920x1080	C2R	no	16.93 ms	2.485 ms	n/a
1920x1080	C2C	yes	55.8 ms	5.065 ms	n/a
1920x1080	C2C	no	51.9 ms	4.21 ms	n/a
1024x1024	C2R	yes	11.99 ms	1.178 ms	n/a
1024x1024	C2R	no	11.85 ms	0.907 ms	n/a
1024x1024	C2C	yes	41.5 ms	1.888 ms	n/a
1024x1024	C2C	no	39.59 ms	1.51 ms	n/a
626x626	C2R	yes	74.5 ms	1.589 ms	n/a
626x626	C2R	no	74.4 ms	1.454 ms	n/a
626x626	C2C	yes	148.1 ms	3.065 ms	n/a
626x626	C2C	no	147.1 ms	2.89 ms	n/a

Jetson Nano

size	type	norm.	CPU	CUDA	PVA
1920x1080	C2R	yes	34.31 ms	6.964 ms	n/a
1920x1080	C2R	no	34.04 ms	5.723 ms	n/a
1920x1080	C2C	yes	85.5 ms	12.26 ms	n/a
1920x1080	C2C	no	87.5 ms	10.456 ms	n/a
1024x1024	C2R	yes	21.4 ms	2.491 ms	n/a
1024x1024	C2R	no	21.29 ms	1.916 ms	n/a
1024x1024	C2C	yes	70.4 ms	4.068 ms	n/a
1024x1024	C2C	no	63.8 ms	3.062 ms	n/a
626x626	C2R	yes	171 ms	3.602 ms	n/a
626x626	C2R	no	171 ms	3.352 ms	n/a
626x626	C2C	yes	343 ms	6.659 ms	n/a
626x626	C2C	no	342 ms	6.292 ms	n/a