A two-dimensional inplace truncation Walsh transform method

The truncation Walsh transform (TWT) method exploits data coherence to advantage to expedite the Walsh transform computation for such data as image data, Hierarchical data structures aggregate coherent segments of the data achieving the Walsh transform computation of an array of N x N (N = 2(n)) data in time between O(N-2) and O(N-2 log(2) N). This paper presents a version of the two-dimensional TWT method which uses an inplace quadtree Morton order traversal to linearize and aggregate coherent segments of the N x N pixel matrix into regular sparse matrices. The Walsh transform is computed from these sparse matrices using a two-dimensional radix 2 algorithm. The only additional memory required is log N locations recursively used to store the sparseness degrees of the matrices. Analysis of time complexities and performance of this method compared with the fast Walsh transform (FWT) method which takes time O(N-2 log(2) N) confirms its superiority over the FWT method for coherent data. Finally, experimental results conducted on real images are provided to demonstrate the time savings achieved by this method. (C) 1996 Academic Press, Inc.