Rate distortion theory was created by Claude Shannon in his founding work on information theory.

Table of contents |

2 Rate-Distortion Functions 3 Performance of Practical Compression Systems |

In rate distortion theory, the *rate* is usually understood as the number of bits per data sample to be stored or transmitted. The notion of *distortion* is a subject of on-going discussion. In the most simple case (which is actually used in most cases), the distortion is defined as the variance of the difference between input and output signal (i.e., the mean-squared error of the difference). However, since we know that most lossy compression techniques operate on data that will be perceived by humans (listen to music, watch pictures and video) the distortion measure preferebly should include some aspects of human perception. In audio compression perceptual models, and therefore perceptual distortion measures, are well developed and routinely used in compression techniques such as MP3 or Vorbis, but often not easy to include in rate-distortion theory. In image and video compression, the human perception models are less well developed and inclusion is mostly limited to the JPEG and MPEG weighing (quantization, normalization) matrix.

subject toHere is the condition probability density function (PDF) of the communication channel output (compressed signal)

where *H(Y)* and *H(Y|X)* are the entropy of the output signal *Y* and the conditional entropy of the output signal given the input signal, respectively:

The mutual information can be understood as a measure for * a priori* uncertainty the receiver has about the sender's signal (*H(Y)*), deminished by the uncertainty that is left after receiving information about the sender's signal (*H(Y|X)*). Of course the decrease in uncertainty is due to the communicated amount of information, which is *I(Y;X)*.

As an example, in case there is *no* communication at all, then *H(Y|X)=H(Y)* and *I(Y;X)=0*. Alternatively, if the communication channel is perfect and the received signal *Y* is identical to the signal *X* at the sender, then *H(Y|X)=0* and *I(Y;X)=H(Y)=H(X)*.

In the definition of the rate-distortion function, and are the distortion between *X* and *Y* for a given and the prescribed maximum distortion, respectively. When we use the mean-squared error as distortion measure, we have (for amplitude continuous signals):

As the above equations show, calculating a rate-distortion function require the stochastic description of the input

Unfortunately, solving this minimization problem can be done only for few cases, of which the following two are the most well known ones. However, although exact solutions are only available in a few cases, measured rate-distortion functions in real life tend to have very similar forms.

If we assume that is Gaussian with variance , and if we assume that successive samples of the signal *X* are stochastically independent (or, if your like, the source is *memoryless*, or the signal is *uncorrelated*), we find the following analytical expression for the rate-distortion function:

The following figure shows what this function look like

Rate distortion theory tell us that *no compression system exists that performs outside the green dotted area*. The closer a practical compression system is to the red (lower) bound, the better it performs. It should be emphasized that this rate-distortion function holds only for Gaussian memoryless sources. The performance of a practical compression system working on -- say -- images, may well below the *R(D)* lower bound shown.

*to be written*

To calculate practical *R(D)* curves on images (for instance, your own bmp or tif images) using a variety of compression techniques, download the *VcDemo Image and Video Compression Learning Tool* from http://www-ict.its.tudelft.nl/vcdemo.