basics
With
advances in communications media and technologies come corresponding
needs for communication techniques that take full advantage of the
capabilities particular to those technologies. A prime example of
such an area of growth is the medium of internet communications. With
the growth of internet communications comes an increased need for
techniques whereby a single user can simultaneously communicate the
same information to a wide array of other users with vastly varying
bandwidth resources, computational capabilities, and performance requirements.
Along with a variety of other factors, this need has helped inspire
a surge in interest in multiresolution or
progressive transmission source coding.
Multiresolution
source codes are data compression algorithms in which simple, lowrate
source descriptions are embedded in more complex, highrate descriptions.
Use of multiresolution source codes allows users with severe bandwidth
constraints or low performance requirements to achieve a low quality
data representation by only incorporating a fraction of the original
coded bit stream. Users with greater capabilities or needs can achieve
more precise data representations by using larger fractions of the
same bit stream. Further, users uncertain of their precision needs
can progressively reconstruct the data to higher and higher accuracy
 stopping the communication process when the desired accuracy is
achieved. Such coding techniques are extremely valuable in any application
where multiple source descriptions at varying levels of precision
are required.
top
theory
The
distortionrate bound D(R) describes the lowest expected distortion
achievable at expected rate R on a known source. Thus D(0.5)
is the lowest distortion achievable at rate 0.5 bits per symbol and
D(1.5) is the lowest distortion achievable at rate 1.5 bits
per symbol in the above graph. The distortionrate bound does not,
however describe the optimal achievable performance for an Lresolution
code with L > 1. For example, the distortionrate function
does not describe the lowest distortion achievable by adding 1 bit
per symbol to a code achieving point (0.5, D(0.5)) in the above
graph. Similarly, the distortionrate function does not describe the
lowest distortion achievable by reading only the first 0.5 bits per
symbol from a code achieving point (1.5, D(1.5)) in the above
graph. Further, the distortionrate function does not describe all
possible values of distortions D_{1} and D_{2}
such that points (0.5,D_{1}) and (1.5,D_{2})
are achievable by the first and secondresolution descriptions of
a single tworesolution code. Theoretical work in the area of multiresolution
coding has focused on finding the space of rate and distortion vectors
that can be achieved by a single multiresolution code. The
main contribution of this work was to derive equations describing
the optimal performance theoretically achievable by fixedrate multiresolution
source codes and the optimal performance theoretically achievable
for variablerate multiresolution source codes for both stationary
ergodic sources and for stationary nonergodic sources on complete
separable metric spaces (which essentially describes all of the sources
encountered in practical applications).
top
vector
quantizers
Multiresolution
vector quantization is optimal multiresolution source coding.
In this case, the encoder blocks an incoming data stream into contiguous
blocks of dimension n and chooses for each nblock a
collection of ndimensional reproductions. In particular, in
an Lresolution code, the encoder chooses for each data block
L reproductions of increasing resolution. The encoder describes
the chosen collection of reproductions using a fixed or variablerate
binary string such that the first portion of the binary string describes
the resolution1 reproduction, the second portion of the binary string
describes the resolution2 reproduction given the resolution1 reproduction
already described, and so on. The decoder decodes the desired portion
of the binary string, updating its source reproduction as the binary
descriptions for higher and higher resolution reconstructions become
available.
top
waveletbased
codes
While
multiresolution vector quantizers are asymptotically optimal source
codes  that is they achieve performance arbitrarily close to theoretical
limit as the dimension approaches infinity  for practicality reasons,
multiresolution vector quantizers are typically implemented at very
low vector dimensions. Giving up optimal
encoders and decoders for ones that are merely good
(and clever!) yields much of the highdimension advantage without
the computation, memory, and delay costs associated with high dimensional
codes. Wavelets are an especially useful technique for
achieving much of the highdimensional advantage at very low complexity,
and are therefore extremely popular in modern multiresolution data
compression algorithms. Ongoing work aims
to combine the results of multiresolution source coding theory with
the techniques used in practical multiresolution data compression
algorithms like SPIHT, EZW, and their descendants.
top
