Practical selection of a basis from a redundant tree structure

Abstract

The problem of selecting a basis within a redundant tree structure naturally arises in the frameworks of wavelet packet transform (WPT) and cosine packet transform (CPT) for signal representation. The "actual" tree has to be consider before performing that selection using suitable information cost functions for the branches. The "actual" redundant tree has many constraints. Among them is the bit overhead for coding explicitly the name of the resulting non redundant (prune) tree. Besides, from computational or real time constraints it is convenient to perform sub-optimal top-down tree computation/search instead of the optimal bottom-up tree search after computing the complete tree. Even when a optimal coding of the tree remains an open join coding problem, a practical selection algorithm is reported here that takes the above and others considerations into account. The algorithm has been implemented an tested in the framework of a wavelet based audio coding system. Variations of the algorithm can be used in many practical situations where a subset from an redundant structure has to be chosen with the constraint of minimal bit cost.