We address the best basis problem--or, more generally, the best representation problem: Given a signal, a dictionary of representations, and an additive cost function, the aim is to select the representation from the dictionary which minimizes the cost for the given signal. We develop a new framework of multitree dictionaries, which includes some previously proposed dictionaries as special cases. We show how to efficiently find the best representation in a multitree dictionary using a recursive tree-pruning algorithm. We illustrate our framework through several examples, including a novel block image coder, which significantly outperforms both the standard JPEG and quadtree-based methods and is comparable to embedded coders such as JPEG2000 and SPIHT.

We use the framework of multitree dictionaries (Huang et al. (2003)) to design a novel DCT-based image coder which significantly outperforms both the standard JPEG and the quadtree-based approach of Ramchandran et al. (1993).

We generalize our results of [Y. Huang et al, 2005 and 2003] and propose a new framework of multitree dictionaries which include many previously proposed dictionaries as well as many new, very large, tree-structured dictionaries. We present an efficient, globally optimal algorithm to find the best tree in such a dictionary. We describe a novel block image coder based on our framework, which is an improvement over our image coder presented in Y. Huang et al, (2005).

We build a multitree dictionary of local cosine bases and develop a novel image coder that extracts the best basis in such a dictionary with respect to a rate-distortion cost. This dictionary is much larger than standard quadtree-based dictionaries, and therefore, our algorithm needs more overhead bits to encode the basis selection. Despite this, we show that the resulting algorithm outperforms an existing quadtree local cosine image compression algorithm. We also show that our multitree local cosine coder outperforms both SPIHT and a multitree block-DCT method previously developed by us, on several textured images.

We propose a best basis search algorithm for local cosine dictionaries. We improve upon the classical best local cosine basis selection based on a dyadic tree (Coifman, R.R. and Wickerhauser, M.V., IEEE Trans. Inf. Th., vol.38, no.2, p.713-18, 1992), by considering a larger dictionary of bases. This results in more compact representations, lower costs, and approximate shift-invariance. We also provide a version of our algorithm which is strictly shift-invariant.