On computing the FFT of digital images in quadtree format
This correspondence considers the computation of the two-dimensional fast Fourier transform (2-D-FFT) of images represented by quadtrees of maximum depth k<n, i.e., images that can be subdivided into squares of constant grey value, each consisting of M/spl times/M=2/sup n-k//spl times/2/sup n-k/ pixels. The correspondence shows that such 2-D-FFTs can be computed in terms of the 2-D-DFT of a subsampled version of the original image. As the subsampled image is only of size (N/M)/spl times/(N/M) the proposed procedure is faster than direct computation.