A Truncation method for computing slant transforms withapplications to image processing

A truncation method for computing the slant transform is presented. The slant transform truncation (STT) algorithm uses the divide and conquer principle of hierarchical data structures to factorize coherent image data into sparse subregions. In one dimension with a data array of size N=2ⁿ, the truncation method takes a time between O(N) and O(Nlog₂N), degenerating to the performance of the fast slant transform (FST) method in its worst case. In two dimensions, for a data array of size N×N, the one-dimensional truncation method is applied to each row, then to each column of the array, to compute the transform in a time between O(N²) and O(N²log₂N). Coherence is a fundamental characteristic of digital images and so the truncation method is superior to the FST method when computing slant transforms of digital images. Experimental results are presented to justify this assertion     

Quadtree and symmetry in FFT computation of digital images

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

Quadtrees, Transforms and Image Coding

Transforms and quadtrees are both methods of representing information in an image in terms of the presence of information at differing length scales. This paper presents a mathematical relationship between these two approaches to describing images in the particular case when Walsh transforms are used. Furthermore, both methods have been used for the compression of images for transmission. This paper notes that under certain circumstances, quadtree compression produces identical results to Walsh transform coding, but requires less computational effort to do so. Remarks are also made about the differences between these approaches.