chapter 2, Source Models and Entropy

In II Information Theory Concepts from: Digital Image Compression Techniques

Author(s): Majid Rabbani, Paul W. Jones

Published: 01 February 1991

Chapter DOI: 10.1117/3.34917.ch2

Chapter Page Count: 9 pages

Previous Chapter | Next Chapter

Front Matter

I Background
1. Digital Images and Image Compression

References to Part 1

II Information Theory Concepts
2. Source Models and Entropy

3. Variable-Length Codes

4. Entropy Estimation and Lossless Compression

5. Rate-Distortion Theory and Lossy Compression

References to Part 2

III Lossless Compression Techniques
6. Bit Plane Encoding

7. Lossless Predictive Coding

8. Lossy Plus Lossless Residual Encoding

References to Part 3

IV Lossy Compression Techniques
9. Lossy Predictive Coding

10. Transform Coding

11. Block Truncation Coding

12. Vector Quantization

13. Subband Coding

14. Hierarchical Coding

15. Choosing a Lossy Compression Technique

References to Part 4

A. Compression of Color Images

Back Matter

Preview

Chapter Contents

2.1 Discrete Memoryless Sources
2.2 Extensions of a Discrete Memoryless Source
2.3 Markov Sources
2.3.1 Example
2.4 Extensions of a Markov Source and Adjoint Sources
2.4.1 Example
2.5 The Noiseless Source Coding Theorem

Excerpt

Any information-generating process can be viewed as a source that emits a sequence of symbols chosen from a finite alphabet. For example, this text has been generated by a source with an alphabet that contains all the ASCII symbols. Similarly, a computer performs its computations on binary data, and such data may be considered as a sequence of symbols generated by a source with a binary alphabet composed of 0 and 1.

In the case of images, one may think of an n-bit image as being generated by a source with an alphabet of 2ⁿ symbols representing the possible code values. The ordering of the sequence produced by an image source might correspond to adjacent pixel values based on a 1-D raster scan, or it might correspond to values taken from a 2-D block of pixels. It is advantageous to develop models for image sources in order to measure the “information” conveyed by these sequences of symbols. In the following chapters, we examine several source models and related information theory concepts that are useful in image compression.

2.1 Discrete Memoryless Sources

The simplest form of an information source is the discrete memoryless source (DMS), in which successive symbols produced by the source are statistically independent. A DMS S is completely specified by its source alphabet S = {s₁,s₂,…,s_n} and the associated probabilities of occurrence {p(s₁),p(s₂),…,p(s_n)}. An important quantity is the average information provided by a DMS. Before defining this quantity, we should first address the question of what is meant by the “information” contained in a certain event.