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) FF T 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] ba sed on the depth of the Quadtree to expedite 2-D FFT computation of co herent digital images. In principle, it establishes that if the Quadtr ee 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 transfor m coding systems and lossy compression of images.