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×M=2^n-k×2^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)×(N/M) the proposed procedure is faster than direct computation