The 2D Tree Sliding Window Discrete Fourier Transform
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Discrete Function Bases and Convolutional Neural Networks
We discuss the notion of "discrete function bases" with a particular focus on the discrete basis derived from the Legendre Delay Network (LDN). We characterize the performance of these bases in a delay computation task, …
Discrete Linear Canonical Transform on Graphs
With the wide application of spectral and algebraic theory in discrete signal processing techniques in the field of graph signal processing, an increasing number of signal processing methods have been proposed, such as t…
Sliding DFT-based Signal Recovery for Modulo ADC with 1-bit Folding Information
The modulo analog-to-digital converter (ADC) is a promising solution to resolve the limited dynamic range (DR) issue of conventional ADCs and achieve an enhanced digital resolution given a fixed quantization bit budget. …
QuantizationFast Signal Interpolation Through Zero-padding and FFT/IFFT
Based on the sampling theorem, interpolation should be conducted by employing the sinc functions as the kernels. Inspired by the fact that the discrete Fourier transform (DFT) is sampled from the discrete time Fourier tr…
Mining Recurrent Concepts in Data Streams using the Discrete Fourier Transform
In this research we address the problem of capturing recurring concepts in a data stream environment. Recurrence capture enables the re-use of previously learned classifiers without the need for re-learning while providi…
Meta-Learning