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.

Original languageEnglish (US)
Pages (from-to)1779-1793
Number of pages15
JournalIEEE Transactions on Image Processing
Issue number7
StatePublished - Jul 2006


  • Best basis
  • Grammar
  • Image compression
  • JPEG

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design
  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'Fast search for best representations in multitree dictionaries'. Together they form a unique fingerprint.

Cite this