Jump to Content
chapter 5, Rate-Distortion Theory and Lossy Compression
)
Table of Contents
- I Background
- 1. Digital Images and Image Compression
- II Information Theory Concepts
- 2. Source Models and Entropy
- III Lossless Compression Techniques
- 6. Bit Plane Encoding
- IV Lossy Compression Techniques
- 9. Lossy Predictive Coding
- 10. Transform Coding
- 13. Subband Coding
Excerpt
The performance bound on the encoding rate of an information source, as defined by the source entropy, pertains only to the lossless encoding of the data. In many practical situations, a certain degree of irreversible image degradation can be tolerated. This level of degradation is usually controlled by the user by adjusting a set of parameters, e.g., quantization intervals. A relevant question is: What is the minimum bit rate required to encode a source while keeping the resulting degradation below a certain level? This fundamental question is addressed by a branch of information theory known as rate-distortion theory [22]. Rate-distortion theory establishes theoretical performance bounds for lossy data compression according to a fidelity criterion. For a broad class of distortion measures and source models, the theory provides a rate-distortion function R(D) that has the following properties:
• For any given level of distortion D, it is possible to find a coding scheme with rate arbitrarily close to R(D) and average distortion arbitrarily close to D.
• It is impossible to find a code that achieves reproduction with distortion D (or better) at a rate below R(D).
It can be shown that R(D) is a convex ∪, continuous, and strictly decreasing function of D. Figure 5.1 shows a typical rate-distortion function for a discrete source with a finite alphabet. The minimum rate required for distortion-free compression of the source is the value of R at D = 0 and is less than or equal to the source entropy, depending on the distortion measure. Also shown is the hypothetical performance of a high-complexity encoder and a low-complexity encoder relative to the R(D) bound.
©1991 Society of Photo-Optical Instrumentation Engineers
