Programming the WFTA (Winograd Fourier Transform Algorithm) for Two-Dimensional Data

摘要

Among the reasons that discrete Fourier transform (DFT) techniques play a smaller role in image processing than they do in one-dimensional signal processing is that two-dimensional DFTs are computationally expensive. For this reason, DFT implementation using the Winograd Fourier transform algorithm (WFTA) appears to be attractive. Techniques for programming the WFTA in two dimensions are introduced, and necessary transposes of the Winograd 'small-n' algorithms are enumerated. Results indicate that, for certain computer environments, a WFTA implementation of the DFT can save appreciable CPU time.