Chapter 21

State of the Art of Compression Methods

2.1. Introduction

The development of new techniques in the fields of IT and communications has a great impact on our daily lives. In parallel to the constant evolution of information systems, the increase of bandwidths allows us to access and share huge quantities of data proposed by innovative services and uses. Exciting scientific problems arise concerning multimedia content, network architecture and protocols, services and uses, information-sharing and security issues. In this context, data compression remains an essential step both for transmission and for archiving.

Since the 1980s, a wide community of researchers has been working on compression techniques. Their work has led to significant advances: the broadcasting of digital television at home using a reduced bandwidth ADSL; the archival of high quality digital images on the reduced memory of a digital camera; the storage of hours of music in MP3 format on a flash drive player. To give a well known example, the JPEG standard for the compression of still images is the result of the efforts of a large scientific community between 1987 and 1993, when the standard was set. The work that led to the creation of this standard was instigated even earlier, with the proposal of a discrete cosine transform in 1974 by [AHM 74].

The collaboration of the international research community has continued with developments of quite interesting techniques for the compression of video, audio and 3D files. All these compression methods attempt to find an optimal compromise: minimize the bitrates whilst retaining the maximum visual or audio quality. In parallel to these developments, the community of researchers working on network protocols has proposed specific protocols for multimedia. These protocols, called RTP and RTCP, allow for the real-time transmission of data with a guaranteed quality of service. The Internet is a very good example of the convergence of data, image and video applications on networks.

Among the numerous compression techniques suggested in the literature, some aim for a perfect reconstruction of the original data. These methods are described as lossless. However, such techniques lead to relatively small compression ratios and are used in some delicate application domains such as for medical or satellite images, as well as the compression of computer files. Examples are entropic coding such as Huffman coding, arithmetic coding or LZW coding (the encoding of computer files such as ZIP, PDF, GIF, PNG, etc.). The general aim of these coding techniques is to get as close as possible to the real entropy of a given image. To learn more about these lossless methods, see section 2.3.

When an application requires limited bitrates, we use methods which enable a supervised loss of information (a loss often so small that it cannot be detected by the human eye). These so-called “lossy” methods combine high compression ratios with an acceptable visual quality (a rate of 8-10 for the JPEG standard and 20-30 for the JPEG 2000 standard). These losses can take the form of blocking effects, reduced color quality, blurriness, or step effect around the contours, oscillations in the transition areas, etc. We can see why the levels of loss and/or distortion need to be limited for certain applications.

In this chapter, which looks at the current state of compression techniques, we will focus mainly on the methods which have led to the accepted standards. Section 2.2 presents an outline of a generic compression technique and summarizes some information theory, quantization and coding tools which are required to understand the existing standards. The standards for compressing 2D still images and video are presented in detail in sections 2.3 and 2.4 respectively. We also give useful references regarding the techniques applied to 1D signals (audio, spoken word) in section 2.5, and those applied to 3D objects in section 2.6. The chapter ends with a conclusion and some thoughts on the evolution of the techniques, as well as the evolving nature of their usages. For a more detailed analysis, we refer you to [BAR 02], which looks at the compression and coding of images and video, and also the section “multimedia in computer systems” in the encyclopaedia [AKO 06].

2.2. Outline of a generic compression technique

A generic compression method can easily be represented in the form of a functional scheme composed of three blocks: reducing redundancy, quantization, and coding (see Figure 2.1). These three blocks are not always distinct or independent from each other. For example, in the case of a fractal method, the fractal model incorporates all the elements: the reduction of redundancy by detection and modeling the autosimilarity in the image, the implicit quantization using the compact fractal model and the coding of the model‘s parameters.

Figure 2.1. Generic compression method scheme

2.2.1. Reducing redundancy

Compression aims to quantify and code the source information using a number of bits close to the entropy of this source (the entropy is the average quantity of information contained in one of the source‘s messages) by exploiting the redundancy of the data representing a natural phenomenon as in medical imagery. We have Shannon [SHA 49] to thank for the mathematical definitions of these information, entropy and redundancy concepts. These definitions are looked at in detail in section 2.2.3.

Redundancy in this sense must be understood as the similarity of messages or symbols when they are analyzed one after another, or next to each other. This redundancy may be spatial (in neighboring pixels or between blocks or areas of pixels); spectral (between the different bands created by a multispectral system or the Red, Green and Blue (RGB) components); or temporal (between successive images in a video). Compression methods use these different types of redundancy and reduce the average number of bits required to code a source symbol (a pixel of the image). This step is undoubtedly that which appeals most to researchers in this field, as it involves analyzing the content of the data, detecting redundancy through the use of innovative tools adapted to the content, and then proposing a compact and decorrelated representation of the information. Although pixel-based methods do exist and can be effective, the key methods use orthogonal transform (Discrete Cosine Transform (DCT) and Discrete Wavelet Transform (DWT) most commonly) in order to change the representation space and aim at an optimal representation in terms of decorrelation/compactness with transformed coefficients. We should also note that a color transformation of RGB to YCbCr belongs to the step of the reduction of redundancy (spectral redundancy in this case).

2.2.2. Quantizing the decorrelated information

Decorrelated information may take the form of integer, real, complex, vector values or forms. It is represented in a certain dynamic range. The data formats quoted above, and the dynamic range associated with the information, are often incompatible with the average number of bits per symbol with which we aim to quantify and code. In such cases, we make use of quantization methods.

Let us consider a continuous real variable to be quantized. Quantization methods allow us to make this variable discrete over its entire dynamic range by defining a finite number of intervals (according to a quantization step which may be either uniform or not), and by assigning a value to each of these intervals (for example the middle value of each interval). We should note the importance of the choices of the quantization step and the value assigned to each interval. The strategy behind the quantization method will determine the optimal values of these two parameters, generally based on the statistics of the source to be quantized.

The performance of the quantization is measured in terms of minimization of global distortion (total error after quantization) for a given bitrate to allocate to this source (for example, an average of 3 bits/pixel to quantize a digital mammography numerized at 12 bits/pixel).

We can define two main classes of quantization: scalar quantization and vector quantization. The first is applied to scalars such as the intensity of a pixel or the value of a coefficient, whereas the second is applied to blocks of neighboring pixels or coefficients. It is at this stage of the quantization that the loss of information (and thus a lower quality of the restored image) is introduced into the compression process. This loss is of course irreversible. In this chapter, we have opted not to detail quantization methods. These methods can be studied in the references [MAX 60], [LIN 80] and [GRA 84]. However, when we detail the norms, the quantization stage will also be looked at in further detail.

2.2.3. Coding the quantized values

The values which emerge from the quantization process are generally represented by a binary code of fixed length (N bits/symbol). The coding stage allows us to reduce the average number of bits allocated to each quantized value. The established techniques are based on the information theory presented below. They involve no loss of information.

It was Shannon [SHA 49] who in 1949 developed information theory, with a global vision of communication systems, and opened the door for coding techniques. The developments he made have led to an optimization in the representation of messages generated by the information source given the entropy of this source (for example, the...