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.

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.7 ms	0.9815 ms	n/a
1920x1080	C2R	no	6.5 ms	0.8172 ms	n/a
1920x1080	C2C	yes	20.9 ms	1.5312 ms	n/a
1920x1080	C2C	no	19.09 ms	1.2582 ms	n/a
1024x1024	C2R	yes	5.08 ms	0.2876 ms	n/a
1024x1024	C2R	no	4.8 ms	0.1979 ms	n/a
1024x1024	C2C	yes	7.8 ms	0.6044 ms	n/a
1024x1024	C2C	no	6.10 ms	0.4698 ms	n/a
626x626	C2R	yes	34.0 ms	0.470 ms	n/a
626x626	C2R	no	33.9 ms	0.4319 ms	n/a
626x626	C2C	yes	66.60 ms	0.833 ms	n/a
626x626	C2C	no	66.2 ms	0.7772 ms	n/a

Jetson TX2

size	type	norm.	CPU	CUDA	PVA
1920x1080	C2R	yes	17.02 ms	3.04 ms	n/a
1920x1080	C2R	no	16.87 ms	2.47 ms	n/a
1920x1080	C2C	yes	49.4 ms	5.07 ms	n/a
1920x1080	C2C	no	47.4 ms	4.18 ms	n/a
1024x1024	C2R	yes	12.14 ms	1.18 ms	n/a
1024x1024	C2R	no	11.90 ms	0.909 ms	n/a
1024x1024	C2C	yes	41.08 ms	1.91 ms	n/a
1024x1024	C2C	no	39.99 ms	1.52 ms	n/a
626x626	C2R	yes	72.67 ms	1.562 ms	n/a
626x626	C2R	no	72.9 ms	1.453 ms	n/a
626x626	C2C	yes	146.0 ms	3.05 ms	n/a
626x626	C2C	no	144.82 ms	2.92 ms	n/a

Jetson Nano

size	type	norm.	CPU	CUDA	PVA
1920x1080	C2R	yes	34.1 ms	6.95 ms	n/a
1920x1080	C2R	no	34.0 ms	5.712 ms	n/a
1920x1080	C2C	yes	86.3 ms	12.28 ms	n/a
1920x1080	C2C	no	87.2 ms	10.46 ms	n/a
1024x1024	C2R	yes	21.3 ms	2.480 ms	n/a
1024x1024	C2R	no	21.11 ms	1.897 ms	n/a
1024x1024	C2C	yes	69.8 ms	4.248 ms	n/a
1024x1024	C2C	no	64.8 ms	3.196 ms	n/a
626x626	C2R	yes	171.7 ms	3.596 ms	n/a
626x626	C2R	no	172 ms	3.354 ms	n/a
626x626	C2C	yes	342 ms	6.662 ms	n/a
626x626	C2C	no	341 ms	6.262 ms	n/a