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.

DOI: 10.1117/3.34917.ch5

SPIE eBooks are new and may not be included in your library’s collection.