Rate-distortion optimized tree based coding algorithms

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper addresses the problem of efficient coding of an important class of signals, namely piecewise polynomials. For this signal class, we develop a coding algorithm, which achieves oracle like rate-distortion (R-D) behavior in the high bit rate regime and with a reasonable computational complexity. For the 1-D case, our scheme is based on the binary tree segmentation of the signal and an optimal bit allocation strategy among the different signal segments. The scheme further encodes the similar neighbors jointly to achieve the right exponentially decaying R-D behavior (D(R) ~ CO2-C1R ). We have also shown that the computational cost of the scheme is of the order O(N log N). We then show that the scheme can be easily extended to the 2-D case, as the quadtree based coding scheme, with the similar R-D behavior and computational cost. Finally, we conclude with some numerical results.

Original languageEnglish (US)
Title of host publicationProceedings of the 2002 IEEE Information Theory Workshop, ITW 2002
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages4
ISBN (Electronic)0780376293, 9780780376298
StatePublished - 2002
Externally publishedYes
Event2002 IEEE Information Theory Workshop, ITW 2002 - Bangalore, India
Duration: Oct 20 2002Oct 25 2002

Publication series

NameProceedings of the 2002 IEEE Information Theory Workshop, ITW 2002


Other2002 IEEE Information Theory Workshop, ITW 2002

ASJC Scopus subject areas

  • Information Systems
  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Rate-distortion optimized tree based coding algorithms'. Together they form a unique fingerprint.

Cite this