FFT Batching and Non-power-of-two Input

[tfarago]

Overall

The interface of fft and ifft should comply with how other packages are doing it, namely numpy. Thus, there will be these scenarios:

• input is power of 2: no change in behavior
• input is not power of two:
  • if shape is specified, it is used (even if auto-zeropadding would do something else) (if it is not a power of 2, chirp-z-based DFT is computed)
  • if shape is not specified and auto-zeropadding=True, it is used
  • if shape is not specified and auto-zeropadding=False, chirp-z-based DFT is computed

There are 2 stages to this:

• [x] make FFT work with all dimensions and batching combinations
• [x] use chirp-z transform to do FFT of non-power-of-two sequences, i.e. compute the DFT

And also:

• [x] add tests
• [x] update the docs
• [x] make tests work with CMake
• [x] check if tofu works with breaks below

Illustration by the Power Spectrum and the Effects of Various Paddings

The left image is the Fourier transform of the input of size 371x371 without padding by the new Chirp-z implementation, the middle is with automatic zero-padding to 512x512 pixels (notice the pronounced horizontal line due to zero-padding), the right one is with padding to 512x512 with mirrored_repeat padding mode (notice how positive and negative frequencies are starting to "blend"). The images were generated by these commands:

ufo-launch read path=boat-cropped-sq-371.tif ! fft dimensions=2 ! power-spectrum ! calculate expression="'log(v)'" ! swap-quadrants ! write tiff-bigtiff=False filename=left.tif
ufo-launch read path=boat-cropped-sq-371.tif ! fft dimensions=2 size-x=512 size-y=512 ! power-spectrum ! calculate expression="'log(v)'" ! swap-quadrants ! write tiff-bigtiff=False filename=middle.tif
ufo-launch read path=boat-cropped-sq-371.tif ! pad width=512 height=512 addressing-mode=mirrored_repeat ! fft dimensions=2 ! power-spectrum ! calculate expression="'log(v)'" ! swap-quadrants ! write tiff-bigtiff=False filename=right.tif

A more pronounced effect of the zero-padding can be observed when we average many power-spectra, the left image below is from Chirp-Z (crop to the central part, hence the size is the same as the right image), the right image from zero-padded FFT (also cropped to the central part).

Commands:

ufo-launch read path=input.tif number=100 ! fft dimensions=2 ! power-spectrum ! average ! calculate expression=log(v) ! swap-quadrants ! write filename=left.tif
ufo-launch read path=input.tif number=100 ! fft dimensions=2 auto-zeropadding=True ! power-spectrum ! average ! calculate expression=log(v) ! swap-quadrants ! write filename=right.tif

Breaks

• It is more straightforward and aligned with other packages (e.g. numpy) to not to zero-padding by default, which I turned off in here
• size-x and so on are by default 0, not 1

Performance Considerations

Chirp-z needs the input sequence to be padded to the next power of two of 2N, where N is the input size, so e.g. for N=4095 it will pad to 8192 pixels. On the top of that, one Chirp-z pass requires computation of two FFTs of that size, so for a 2D problem we may end up being 8x slower compared to auto-zeropad which would do one pass of size 4096.

$ export G_MESSAGES_DEBUG=fft
$ ufo-launch dummy-data width=4096 height=4096 number=100 ! fft dimensions=2 ! null
(ufo-launch:989741): fft-DEBUG: 08:54:18.420: FFT work sizes: input=(w=4096, h=4096, d=1, ND=2), intermediate=(w=4096, h=4096, d=1, ND=2), output=(w=4096, h=4096, d=1, ND=2), parameter=(w=4096 h=4096 d=1 ND=2 batches=1), do_chirp=0
100 items processed ...
Finished in 0.52098s
# Chirp-z, i.e. double the size of the FFT and 2 FFTs needed -> cca. 8x slower
$ ufo-launch dummy-data width=4095 height=4095 number=100 ! fft dimensions=2 ! null
(ufo-launch:989654): fft-DEBUG: 08:54:05.463: FFT work sizes: input=(w=4095, h=4095, d=1, ND=2), intermediate=(w=8192, h=8192, d=1, ND=2), output=(w=4095, h=4095, d=1, ND=2), parameter=(w=8192 h=8192 d=1 ND=2 batches=1), do_chirp=1
100 items processed ...
Finished in 3.87866s

Prerequisites

227

[tfarago]

@sgasilov, @MarcusZuber could you please take a look, especially at the two "Breaks"? There are several places in tofu ez where fft is present, from taking a look this shouldn't break anything as explicit padding takes place, just wanted to double-check.