Quadtree and symmetry in FFT computation of digital images
M.M. Anguh · IEEE Transactions on Signal Processing · 1997
The discrete Fourier transform (DFT) of a real sequence f[x, y] of size N/spl times/N, where N=2/sup n/, can be computed by a two-dimensional (2-D) FFT of size N/4, or smaller if f[x, y] is known to have certain symmetries. This paper presents theorems that identify the symmetry in f[x, y] based on the depth of the quadtree to expedite 2-D FFT computation of coherent digital images. In principle, it establishes that if the quadtree of f[x, y] has maximum depth k