Fundamental Data Compression (eBook)

Cover 1
Contents 6
Preface 18
Chapter 1. Introduction 24
1.1 Data compression problems 26
1.2 Lossless and lossy compression 28
1.3 Deriving algorithmic solutions 30
1.4 Measure of compression quality 34
1.5 Limits on lossless compression 36
Summary 38
Learning outcomes 38
Exercises 38
Laboratory 39
Assessment 40
Bibliography 40
Chapter 2. Coding symbolic data 42
2.1 Information, data and codes 42
2.2 Symbolic data 43
2.3 Variable length codes 46
2.4 Elementary information theory 55
2.5 Data compression in telecommunication 62
2.6 Redundancy 63
2.7 Compression algorithms 66
Summary 69
Learning outcomes 69
Exercises 69
Laboratory 70
Assessment 70
Bibliography 70
Chapter 3. Run-length algorithms 72
3.1 Run-length 72
3.2 Hardware data compression (HDC) 73
3.3 Algorithm Design 75
Summary 86
Learning outcomes 86
Exercises 87
Laboratory 87
Assessment 87
Bibliography 88
Chapter 4. Huffman coding 90
4.1 Static Huffman coding 90
4.2 Shannon-Fano approach 98
4.3 Optimal Huffman codes 104
4.4 Implementation efficiency 105
4.5 Extended Huffman coding 109
Summary 110
Learning outcomes 110
Exercises 111
Laboratory 112
Assessment 112
Bibliography 113
Chapter 5. Adaptive Huffman coding 114
5.1 Adaptive approach 114
5.2 Compressor 115
5.3 Decompressor 118
5.4 Disadvantages of Huffman algorithms 121
Summary 121
Learning outcomes 121
Exercises 122
Laboratory 122
Assessment 122
Bibliography 122
Chapter 6. Arithmetic coding 124
6.1 Probabilities and subintervals 124
6.2 Model and coders 126
6.3 Simple case 130
6.4 General case 132
Summary 137
Learning outcomes 137
Exercises 137
Laboratory 138
Assessment 138
Bibliography 138
Chapter 7. Dictionary - based compression 140
7.1 Patterns in a string 141
7.2 LZW coding 142
7.3 LZ77 family 152
7.4 LZ78 family 159
7.5 Applications 162
7.6 Comparison 163
Summary 163
Learning outcomes 164
Exercises 164
Laboratory 165
Assessment 165
Bibliography 167
Chapter 8. Prediction and transforms 168
8.1 Predictive approach 168
8.2 Move to Front coding 172
8.3 Burrows-Wheeler Transform (BWT) 174
8.4 Transform approach 179
8.5 Discrete Cosine Transform (DCT) 186
8.6 Subband coding 187
8.7 Wavelet transforms 188
Summary 190
Learning outcomes 190
Exercises 191
Laboratory 192
Assessment 193
Bibliography 193
Chapter 9. Audio compression 194
9.1 Modelling sound 194
9.2 Sampling 196
9.3 Quantisation 199
9.4 Compression performance 204
9.5 Speech compression 206
9.6 Music compression 208
Summary 209
Learning outcomes 209
Exercises 210
Assessment 211
Bibliography 211
Chapter 10. Image compression 212
10.1 Image data 212
10.2 Bitmap images 214
10.3 Vector graphics 215
10.4 Bitmap and vector graphics 216
10.5 Colour 217
10.6 Classifying images by colour 219
10.7 Classifying images by appearance 220
10.8 Image compression 221
Summary 230
Learning outcomes 230
Exercises 231
Laboratory 232
Assessment 233
Bibliography 233
Chapter 11. Video compression 234
11.1 Analogue video 234
11.2 Digital video 235
11.3 Moving pictures 235
11.4 MPEG 236
11.5 Basic principles 236
11.6 Temporal compression algorithms 236
11.7 Group of pictures 238
11.8 Motion estimation 239
11.9 Work in different video formats 239
Summary 240
Learning outcomes 240
Exercises 240
Assessment 240
Bibliography 240
Appendix A. Brief history 242
Appendix B. Matrices 246
Appendix C. Fourier series and harmonic analysis 254
Appendix D. Pseudocode notation 258
Appendix E. Notation 262
Index 264