Introduction

Independent scalar quantization of a sequence of samples from a source is especially inefficient when there is dependence or memory among the samples. Even if there is no memory, where the samples are truly statistically independent, scalar quantization of each sample independently, although practical, is a suboptimal method. When neighboring samples provide information about a sample to be quantized, one can make use of this information to reduce the rate needed to represent a quantized sample. In this chapter, we shall describe various methods that exploit the memory of the source sequence in order to reduce the rate needed to represent the sequence with a given distortion or reduce the distortion needed to meet a given rate target. Such methods include predictive coding, vector coding, and tree- and trellis-based coding. This chapter presents detailed explanations of these methods.

Predictive coding

The first approach toward coding of sources with memory is using scalar quantization, because of its simplicity and effectiveness. We resort to a simple principle to motivate our approach. Consider the scenario in Figure 6.1, where a quantity un is subtracted from the source sample xn at time n prior to scalar quantization (Q). The same quantity un is added to the quantized difference ẽn to yield the reconstructed output yn.

This book is an outgrowth of a graduate level course taught for several years at Rensselaer Polytechnic Institute (RPI). When the course started in the early 1990s, there were only two textbooks available that taught signal compression, Jayant and Noll and Gersho and Gray. Certainly these are excellent textbooks and valuable references, but they did not teach some material considered to be necessary at that time, so the textbooks were supplemented with handwritten notes where needed. Eventually, these notes grew to many pages, as the reliance on published textbooks diminished. The lecture notes remained the primary source even after the publication of the excellent book by Sayood, which served as a supplement and a source of some problems. While the Sayood book was up to date, well written, and authoritative, it was written to be accessible to undergraduate students, so lacked the depth suitable for graduate students wanting to do research or practice in the field. The book at hand teaches the fundamental ideas of signal compression at a level that both graduate students and advanced undergraduate students can approach with confidence and understanding. The book is also intended to be a useful resource to the practicing engineer or computer scientist in the field. For that purpose and also to aid understanding, the 40 algorithms listed under Algorithms in the Index are not only fully explained in the text, but also are set out step-by-step in special algorithm format environments.

In this chapter, we introduce the concept that correlated sources need not be encoded jointly to achieve greater efficiency than encoding them independently. In fact, if they are encoded independently and decoded jointly, it is theoretically possible under certain conditions to achieve the same efficiency as when encoded jointly. Such a method for coding correlated sources is called distributed source coding (DSC). Figure 14.1 depicts the paradigm of DSC with independent encoding and joint decoding. In certain applications, such as sensor networks and mobile communications, circuit complexity and power drain are too burdensome to be tolerated at the transmission side. DSC shifts complexity and power consumption from the transmission side to the receiver side, where it can be more easily handled and tolerated. The content of this chapter presents the conditions under which DSC is ideally efficient and discusses some practical schemes that attempt to realize rate savings in the DSC paradigm. There has been a plethora of recent work on this subject, so an encyclopedic account is impractical and ill-advised in a textbook. The goal here is to explain the principles clearly and elucidate them with a few examples.

Slepian–Wolf coding for lossless compression

Consider two correlated, discrete scalar sources X and Y. Theoretically, these sources can be encoded independently without loss using H(X) and H(Y) bits, respectively, where H(X) and H(Y) are the entropies of these sources. However, if encoded jointly, both these sources can be reconstructed perfectly using only H(X, Y) bits, the joint entropy of these sources.

Introduction

In the previous chapter, Chapter 3, we presented the theory of lossless coding and derived properties for optimality of uniquely decodable, prefix-free source codes. In particular, we showed that entropy is the absolute lower rate limit of a prefix-free code and presented tree and arithmetic structures that support prefix-free codes. In this chapter, we shall present coding methods that utilize these structures and whose rates approach the entropy limit. These methods are given the generic name of entropy coding. Huffman coding is one common form of entropy coding. Another is arithmetic coding and several adaptive, context-based enhancements are parts of several standard methods of data compression. Nowadays, lossless codes, whether close to optimal or not, are often called entropy codes. In addition to Huffman and arithmetic coding, we shall develop other important lossless coding methods, including run-length coding, Golomb coding, and Lempel–Ziv coding.

Huffman codes

The construction invented by Huffman [1] in 1952 yields the minimum length, prefix-free code for a source with a given set of probabilities. First, we shall motivate the construction discovered by Huffman. We consider only binary (D = 2) codes in this chapter, since extensions to non-binary are usually obvious from the binary case and binary codes are predominant in practice and the literature. We have learned that a prefix-free code can be constructed, so that its average length is no more than 1 bit from the source entropy, which is the absolute lower limit.

Entropy and lossless coding

Compression of a digital signal source is just its representation with fewer information bits than its original representation. We are excluding from compression cases when the source is trivially over-represented, such as an image with gray levels 0 to 255 written with 16 bits each when 8 bits are sufficient. The mathematical foundation of the discipline of signal compression, or what is more formally called source coding, began with the seminal paper of Claude Shannon [1, 2], entitled “A mathematical theory of communication,” that established what is now called Information Theory. This theory sets the ultimate limits on achievable compression performance. Compression is theoretically and practically realizable even when the reconstruction of the source from the compressed representation is identical to the original. We call this kind of compression lossless coding. When the reconstruction is not identical to the source, we call it lossy coding. Shannon also introduced the discipline of Rate-distortion Theory [1–3], where he derived the fundamental limits in performance of lossy coding and proved that they were achievable. Lossy coding results in loss of information and hence distortion, but this distortion can be made tolerable for the given application and the loss is often necessary and unavoidable in order to satisfy transmission bandwidth and storage constraints. The payoff is that the degree of compression is often far greater than that achievable by lossless coding.

Introduction

In many circumstances, data are collected that must be preserved perfectly. Data that are especially expensive to collect, require substantial computation to analyze, or involve legal liability consequences for imprecise representation should be stored and retrieved without any loss of accuracy. Medical data, such as images acquired from X-ray, CT (computed tomography), and MRI (magnetic resonance imaging) machines, are the most common examples where perfect representation is required in almost all circumstances, regardless of whether it is really necessary to preserve the integrity of the diagnostic task. The inaccuracies resulting from the acquisition and digitization processes are ignored in this requirement of perfection. It is only in the subsequent compression that the digitized data must be perfectly preserved. Physicists and materials scientists conduct experiments that produce data written as long streams or large arrays of samples in floating point format. These experiments are very expensive to set up, so there is often insistence that, if compressed, the decompressed data must be identical to the original.

Nowadays, storage and transmission systems are overwhelmed with huge quantities of data. Although storage technology has made enormous strides in increasing density and reducing cost, it seems that whatever progress is made is not enough. The users and producers of data continue to adapt to these advances almost instantaneously and fuel demand for even more storage at less cost. Even when huge quantities of data can be accommodated, retrieval and transmission delays remain serious issues.

The importance of compression

It is easy to recognize the importance of data compression technology by observing the way it already pervades our daily lives. For instance, we currently have more than a billion users [1] of digital cameras that employ JPEG image compression, and a comparable number of users of portable audio players that use compression formats such as MP3, AAC, and WMA. Users of video cameras, DVD players, digital cable or satellite TV, hear about MPEG-2, MPEG-4, and H.264/AVC. In each case, the acronym is used to identify the type of compression. While many people do not know what exactly compression means or how it works, they have to learn some basic facts about it in order to properly use their devices, or to make purchase decisions.

Compression's usefulness is not limited to multimedia. An increasingly important fraction of the world's economy is in the transmission, storage, and processing of all types of digital information. As Negroponte [2] succinctly put it, economic value is indeed moving “from atoms to bits.” While it is true that many constraints from the physical world do not affect this “digital economy,” we cannot forget that, due to the huge volumes of data, there has to be a large physical infrastructure for data transmission, processing, and storage. Thus, just as in the traditional economy it is very important to consider the efficiency of transportation, space, and material usage, the efficiency in the representation of digital information also has great economic importance.

Introduction

Due to advances in the technology of metrology and storage density, acquisition of images is now increasingly being practiced in more than two dimensions and in ever finer resolutions and in numerous scientific fields. Scientific data are being acquired, stored, and analyzed as images. Volume or three-dimensional images are generated in clinical medicine by CT or MRI scans of regions of the human body. Such an image can be regarded as a sequence of two-dimensional slice images of a bodily section. Tomographic methods in electron microscopy, for example, produce images in slices through the material being surveyed. The material can be a biological specimen or a materials microstructure. In remote sensing, a surface is illuminated with broad-spectrum radiation and the reflectance spectrum of each point on the surface is measured and recorded. In this way, a reflectance “image” of the surface is generated for a number of spectral bands. One uses the term multi-spectral imaging when the number of bands is relatively small, say less than 20, and the term hyper-spectral imaging when the number of bands is larger, usually hundreds. In either case, one can view the data either as a sequence of images or a single image of vector pixels. One particular kind of multi-spectral image is a color image, where the spectrum is in the range of visible wavelengths. Because of the properties of the human visual system, only three particular color images are needed to generate a visual response in the human viewer.

Introduction

In normal circumstances, lossless compression reduces file sizes in the range of a factor of 2, sometimes a little more and sometimes a little less. Often it is acceptable and even necessary to tolerate some loss or distortion between the original and its reproduction. In such cases, much greater compression becomes possible. For example, the highest quality JPEG-compressed images and MP3 audio are compressed about 6 or 7 to 1. The objective is to minimize the distortion, as measured by some criterion, for a given rate in bits per sample or equivalently, minimize the rate for a given level of distortion.

In this chapter, we make a modest start toward the understanding of how to compress realistic sources by presenting the theory and practice of quantization and coding of sources of independent and identically distributed random variables. Later in the chapter, we shall explain some aspects of optimal lossy compression, so that we can assess how well our methods perform compared to what is theoretically possible.

Quantization

The sources of data that we recognize as digital are discrete in value or amplitude and these values are represented by a finite number of bits. The set of these discrete values is a reduction from a much larger set of possible values, because of the limitations of our computers and systems in precision, storage, and transmission speed. We therefore accept the general model of our data source as continuous in value. The discretization process is called quantization.

In this chapter, we shall describe coding systems, primarily for images, that use the principles and algorithms explained in previous chapters. A complete coding system uses a conjunction of compression algorithms, entropy coding methods, source transformations, statistical estimation, and ingenuity to achieve the best result for the stated objective. The obvious objective is compression efficiency, stated as the smallest rate for a given distortion for lossy coding or smallest rate or compressed file size in lossless coding. However, other attributes may be even more important for a particular scenario. For example, in medical diagnosis, decoding time may be the primary concern. For mobile devices, small memory and low power consumption are essential. For broadcasting over packet networks, scalability in bit rate and/or resolution may take precedence. Usually to obtain other attributes, some compression efficiency may need to be sacrificed. Of course, one tries to obtain as much efficiency as possible for the given set of attributes wanted for the system. Therefore, in our description of systems, we shall also explain how to achieve other attributes besides compression efficiency.

Wavelet transform coding systems

The wavelet transform consists of coefficients grouped into subbands belonging to different resolutions or scales with octave frequency separation. As such, it is a natural platform for producing streams of code bits (hereinafter called codestreams) that can be decoded at multiple resolutions.

Introduction

Source coding began with the initial development of information theory by Shannon in 1948 [1] and continues to this day to be influenced and stimulated by advances in this theory. Information theory sets the framework and the language, motivates the methods of coding, provides the means to analyze the methods, and establishes the ultimate bounds in performance for all methods. No study of image coding is complete without a basic knowledge and understanding of the underlying concepts in information theory.

In this chapter, we shall present several methods of lossless coding of data sources, beginning with the motivating principles and bounds on performance based on information theory. This chapter is not meant to be a primer on information theory, so theorems and propositions will be presented without proof. The reader is referred to one of the many excellent textbooks on information theory, such as Gallager [2] and Cover and Thomas [3], for a deeper treatment with proofs. The purpose here is to set the foundation and present lossless coding methods and assess their performance with respect to the theoretical optimum when possible. Hopefully, the reader will derive from this chapter both a knowledge of coding methods and an appreciation and understanding of the underlying information heory.

The notation in this chapter will indicate a scalar source on a one-dimensional field, i.e., the source values are scalars and their locations are on a one-dimensional grid, such as a regular time or space sequence.

Introduction

In previous chapters, we described mathematical transformations that produce nearly uncorrelated elements and pack most of the source energy into a small number of these elements. Distributing the code bits properly among these transform elements, which differ statistically, leads to coding gains. Several methods for optimal rate distribution were explained in Chapter 8. These methods relied on knowledge of the distortion versus rate characteristics of the quantizers of the transform elements. Using a common shape model for this characteristic and the squared error distortion criterion meant that only the variance distribution of the transform elements needed to be known. This variance distribution determines the number of bits to represent each transform element at the encoder, enables parsing of the codestream at the decoder and association of decoded quantizer levels to reconstruction values. The decoder receives the variance distribution as overhead information. Many different methods have arisen to minimize this overhead information and to encode the elements with their designated number of bits. In this chapter, we shall describe some of these methods.

Application of source transformations

A transform coding method is characterized by a mathematical transformation or transform of the samples from the source prior to encoding. We described the most common of these transforms in Chapter 7. The stream of source samples is first divided into subblocks that are normally transformed and encoded independently.

Principles

The storage requirements of samples of data depend on their number of possible values, called alphabet size. Real-valued data theoretically require an unlimited number of bits per sample to store with perfect precision, because their alphabet size is infinite. However, there is some level of noise in every practical measurement of continuous quantities, which means that only some digits in the measured value have actual physical sense. Therefore, they are stored with imperfect, but usually adequate precision using 32 or 64 bits. Only integer-valued data samples can be stored with perfect precision when they have a finite alphabet, as is the case for image data. Therefore, we limit our considerations here to integer data.

Natural representation of integers in a dataset requires a number of bits per sample no less than the base 2 logarithm of the number of possible integer values. For example, the usual monochrome image has integer values from 0 to 255, so we use 8 bits to store every sample. Suppose, however, that we can find a group of samples whose values do not exceed 15. Then every sample in that group needs at most 4 bits to specify its value, which is a saving of at least 4 bits per sample. We of course need location information for the samples in the group. If the location information in bits is less than four times the number of such samples, then we have achieved compression.