A Caltech Library Service

Optimization of Multi-Resolution Source Codes


Dugatkin, Diego G. (2004) Optimization of Multi-Resolution Source Codes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/RZ2Y-1Z78.


This thesis studies the optimization of multi-resolution source codes. A multi-resolution source code is a data compression algorithm that generates a bit-stream that can be truncated at any point to reconstruct low-resolution representations of the original data. By progressively refining the description, these codes allow the receiver to get representations of progressively increasing quality from a single file.

The optimization methods presented here are based on the minimization of a Lagrangian performance measure, which is a weighted sum of rates and distortions at the different resolutions of the multi-resolution code. The Lagrangian coefficients are the weights that parameterize the priorities assigned to the resolutions. The relative value of these parameters can be set according to the user's preferences regarding which rates are more important, the probability of decoding the file at each possible rate, or any other prioritization rationale. We present a method for converting design constraints into the corresponding Lagrangian parameters.

We also use a Lagrangian analysis to investigate optimality properties of multi-resolution codes. Specifically, we explore the characterization of the theoretically optimal output density functions of a two-resolution source code for any arbitrary set of priorities over the resolutions.

Once the priority function has been identified, the goal is to design the multi-resolution code that yields the best rate-distortion trade-off for those priorities. The minimization of the multi-resolution Lagrangian is somewhat specific to the framework and type of multi-resolution code. We pursue this goal in several coding frameworks.

The first framework is the multi-resolution vector quantizer (MRVQ) framework. Prior work on the topic described optimal MRVQ design for both fixed- and variable-rate systems but implemented only fixed-rate codes. The earliest portion of this thesis began with the implementation of the earlier described algorithm for variable-rate MRVQ for use as a testbed for understanding the important question of how to choose the Lagrangian parameters for multi-resolution codes to meet a collection of desired constraints.

Armed with a new understanding of parameter choice in the MRVQ framework, we moved next to the more sophisticated coding framework of wavelet-based embedded bit-plane coders. New results in this framework include improvements on the Set Partitioning in Hierarchical Trees (SPIHT) and the Group Testing for Wavelets (GTW) algorithms that apply the lessons learned from MRVQ theory in these more sophisticated wavelet coding frameworks. Experimental results demonstrate the performance benefits associated with this approach.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Lagrangian parameter choice; optimization of wavelet-based image coders; practical MRVQ design; Rate-distortion optimization; reproduction alphabet size; successive refinement of information
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Effros, Michelle
Thesis Committee:
  • Effros, Michelle (chair)
  • Bruck, Jehoshua
  • Vaidyanathan, P. P.
  • McEliece, Robert J.
  • Chan, Tony F-C
Defense Date:27 October 2003
Record Number:CaltechETD:etd-06022004-013457
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2381
Deposited By: Imported from ETD-db
Deposited On:02 Jun 2004
Last Modified:03 Feb 2021 20:01

Thesis Files

PDF (Diego_Dugatkin_Thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page