array of N data items is represented in binary tree form, the underlying principle of the TWT method is based
The truncation Walsh transform (TWT) method exploits data coherence to advantage to expedite the Walsh transform on the property that the Walsh transform coefficients computation for such data as image data. Hierarchical data W(2 iฯช1 ) to W(2 i ฯช 1) only depend upon the data in the structures aggregate coherent segments of the data achieving binary tree at level i, i ฯญ 0, . . . , n, and not on the the Walsh transform computation of an array of N ุ N (N โซุโฌ data at higher or lower levels of the tree, if in the tree 2 n ) data in time between O(N 2 ) and O(N 2 log 2 N). This paper terminal nodes store data values and nonterminal nodes presents a version of the two-dimensional TWT method which store sums of their child nodes. Thus, if levels j to n uses an inplace quadtree Morton order traversal to linearize of the binary tree are all empty then the Walsh transform and aggregate coherent segments of the N ุ N pixel matrix coefficients W(u) ฯญ 0 for u ี 2 j . This property easily into regular sparse matrices. The Walsh transform is computed generalizes to an N ฯซ N data array. In particular, for from these sparse matrices using a two-dimensional radix 2 an N ฯซ N data array represented by a quadtree with algorithm. The only additional memory required is log 2 N localevels j to n empty, the Walsh transform coefficients tions recursively used to store the sparseness degrees of the W(u, v) ฯญ 0 for u, v ี 2 j . These and other theorems matrices. Analysis of time complexities and performance of relating hierarchical and transform encoding of images this method compared with the fast Walsh transform (FWT) method which takes time O(N 2 log 2 N) confirms its superiority which constitute the fundamental basis of the TWT over the FWT method for coherent data. Finally, experimental method are stated and proved in our earlier work [10].
results conducted on real images are provided to demonstrate
This paper overviews existing one-and two-dimenthe time savings achieved by this method.