A 2-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 a s 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 matri ces. The Walsh transform is computed from these sparse matrices using a two-dimensional radix 2 algorithm. The only additional memory requir ed is log N locations recursively used to store the sparseness degrees of the matrices. Analysis of time complexities and performance of thi s method compared with the fast Walsh transform (FWT) method which tak es time O(N-2 log(2) N) confirms its superiority over the FWT method f or coherent data. Finally, experimental results conducted on real imag es are provided to demonstrate the time savings achieved by this metho d. (C) 1996 Academic Press, Inc.