Quadtree and symmetry in FFT computation of digital images

The discrete fourier transform (DFT) of a real sequence f[x.y] of size N x N, where N = 2(n), can be computed by a two-dimenisional (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 < n, where K = 2(k), then the DFT can be computed by a 2-D FFT of size K/2. An algorithm is given, and its performance analysed. Finally, applications are considered in transform coding systems and lossy compression of images.