The 2D Tree Sliding Window Discrete Fourier Transform
This provides a more efficient method for signal and image processing applications that require sliding window Fourier analysis, though it appears to be an incremental improvement over existing algorithms.
The paper tackles the computational inefficiency of the 2D Sliding Window Discrete Fourier Transform (SWDFT) by introducing a new algorithm that uses a tree data-structure inspired by the Cooley-Tukey FFT to avoid redundant calculations in overlapping windows, achieving O(N₀N₁n₀n₁) operations for an N₀×N₁ array with n₀×n₁ windows.
We present a new algorithm for the 2D Sliding Window Discrete Fourier Transform (SWDFT). Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley- Tukey Fast Fourier Transform (FFT). For an $N_0 \times N_1$ array and $n_0 \times n_1$ windows, our algorithm takes $O(N_0 N_1 n_0 n_1)$ operations. We provide a C implementation of our algorithm for the Radix-2 case, compare ours with existing algorithms, and show how our algorithm easily extends to higher dimensions.