Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images

Rahul Shukla, Pier Luigi Dragotti, Minh N. Do, Martin Vetterli

Research output: Contribution to journalArticlepeer-review


This paper presents novel coding algorithms based on tree-structured segmentation, which achieve the correct asymptotic rate-distortion (R-D) behavior for a simple class of signals, known as piecewise polynomials, by using an R-D based prune and join scheme. For the one-dimensional case, our scheme is based on binary-tree segmentation of the signal. This scheme approximates the signal segments using polynomial models and utilizes an R-D optimal bit allocation strategy among the different signal segments. The scheme further encodes similar neighbors jointly to achieve the correct exponentially decaying R-D behavior (D(R) ∼ C02-c1R), thus improving over classic wavelet schemes. We also prove that the computational complexity of the scheme is of O(N log N). We then show the extension of this scheme to the two-dimensional case using a quadtree. This quadtree-coding scheme also achieves an exponentially decaying R-D behavior, for the polygonal image model composed of a white polygon-shaped object against a uniform black background, with low computational cost of O(N log N). Again, the key is an R-D optimized prune and join strategy. Finally, we conclude with numerical results, which show that the proposed quadtree-coding scheme outperforms JPEG2000 by about 1 dB for real images, like cameraman, at low rates of around 0.15 bpp.

Original languageEnglish (US)
Pages (from-to)343-359
Number of pages17
JournalIEEE Transactions on Image Processing
Issue number3
StatePublished - Mar 2005


  • Binary tree
  • Bit allocation
  • Coding
  • Neighbor joining
  • Piecewise polynomial functions
  • Pruning
  • Quadtree
  • Rate-distortion
  • Tree-structured segmentation

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 'Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images'. Together they form a unique fingerprint.

Cite this