Fundamental Data Compression

Contents......Page 6
List of Figures......Page 12
List of Algorithms......Page 15
Preface......Page 17
Acknowledgements......Page 22
1 Introduction......Page 23
1.1.1 Compression......Page 25
1.1.2 Decompression......Page 26
1.2 Lossless and lossy compression......Page 27
1.3 Deriving algorithmic solutions......Page 29
1.4 Measure of compression quality......Page 33
1.5 Limits on lossless compression......Page 35
Exercises......Page 37
Laboratory......Page 38
Bibliography......Page 39
2.1 Information, data and codes......Page 40
2.2 Symbolic data......Page 41
2.3.1 Modelling......Page 44
2.3.2 Unique decodability......Page 45
2.3.3 Prefix codes and binary trees......Page 46
2.3.4 Prefix codes and unique decodability......Page 48
2.3.5 Kraft inequality......Page 49
2.4 Elementary information theory......Page 53
2.4.1 Entropy......Page 55
2.4.2 Optimum codes......Page 59
2.5 Data compression in telecommunication......Page 60
2.6 Redundancy......Page 61
2.7 Compression algorithms......Page 64
Exercises......Page 67
Bibliography......Page 68
3.1 Run-length......Page 70
3.2 Hardware data compression (HDC)......Page 71
3.2.1 Encoding......Page 72
3.3 Algorithm Design......Page 73
Learning outcomes......Page 84
Assessment......Page 85
Bibliography......Page 86
4.1 Static Huffman coding......Page 87
4.1.1 Huffman approach......Page 89
4.1.2 Huffman compression algorithm......Page 91
4.1.3 Huffman decompression algorithm......Page 94
4.2 Shannon-Fano approach......Page 95
4.2.1 Shannon-Fano algorithm......Page 97
4.3 Optimal Huffman codes......Page 101
4.4 Implementation efficiency......Page 102
4.5 Extended Huffman coding......Page 106
Learning outcomes......Page 107
Exercises......Page 108
Assessment......Page 109
Bibliography......Page 110
5.1 Adaptive approach......Page 111
5.2 Compressor......Page 112
5.2.1 Encoding algorithm......Page 114
5.3 Decompressor......Page 115
5.3.1 Decoding algorithm......Page 117
Learning outcomes......Page 118
Bibliography......Page 119
6.1 Probabilities and subintervals......Page 120
6.2 Model and coders......Page 122
6.3 Simple case......Page 126
6.3.1 Encoding......Page 127
6.4 General case......Page 128
6.4.1 Compression algorithm......Page 130
6.4.3 Unique decodability......Page 131
6.4.5 Renormalisation......Page 132
Exercises......Page 133
Bibliography......Page 134
7 Dictionary-based compression......Page 136
7.1 Patterns in a string......Page 137
7.2.1 Encoding......Page 138
7.2.2 Decoding......Page 144
7.3.1 Prefix match......Page 148
7.3.2 A typical compression step......Page 149
7.3.3 Decompression algorithm......Page 153
7.4 LZ78 family......Page 155
7.4.1 Encoding......Page 156
7.4.2 Decoding......Page 157
7.5 Applications......Page 158
Summary......Page 159
Exercises......Page 160
Assessment......Page 161
Bibliography......Page 163
8.1 Predictive approach......Page 164
8.1.1 Encoding......Page 167
8.2 Move to Front coding......Page 168
8.3 Burrows-Wheeler Transform (BWT)......Page 170
8.4 Transform approach......Page 175
8.4.1 Orthogonal transform......Page 180
8.5 Discrete Cosine Transform (DCT)......Page 182
8.6 Subband coding......Page 183
8.7 Wavelet transforms......Page 184
8.7.1 Scale-varying basis functions......Page 185
Learning outcomes......Page 186
Exercises......Page 187
Laboratory......Page 188
Bibliography......Page 189
9.1 Modelling sound......Page 190
9.2 Sampling .'......Page 192
9.2.1 Nyquist frequency......Page 194
9.3 Quantisation......Page 195
9.3.1 Scalar quantisation......Page 197
9.3.2 Uniform quantisers......Page 198
9.3.3 Non-uniform quantisers......Page 199
9.4 Compression performance......Page 200
9.5.1 Speech coders......Page 202
9.5.3 Silence compression......Page 203
9.6.1 Streaming audio......Page 204
Learning outcomes......Page 205
Exercises......Page 206
Bibliography......Page 207
10.1 Image data......Page 208
10.1.1 Resolution......Page 209
10.2.1 Displaying bitmap images......Page 210
10.3.1 Storing graphic components......Page 211
10.4 Bitmap and vector graphics......Page 212
10.5.1 RGB colour model......Page 213
10.5.3 LC representation......Page 214
10.6 Classifying images by colour......Page 215
10.7 Classifying images by appearance......Page 216
10.8 Image compression......Page 217
10.8.1 Lossless image compression......Page 218
10.8.2 Greyscale and colour images......Page 220
10.8.3 Lossy compression......Page 223
10.8.5 Image file formats......Page 225
Learning outcomes......Page 226
Exercises......Page 227
Laboratory......Page 228
Bibliography......Page 229
11.1 Analogue video......Page 230
11.3 Moving pictures......Page 231
11.6 Temporal compression algorithms......Page 232
11.7 Group of pictures......Page 234
11.9 Work in different video formats......Page 235
Bibliography......Page 236
A Brief history......Page 237
B.1 Special matrices......Page 240
B.2 Matrix operations......Page 242
B.3 Determinants......Page 243
B.4 Orthogonal matrix......Page 244
B.4.1 Inner product......Page 245
B.4.2 Vector space......Page 246
C.1 Fourier series......Page 247
C.2 Convergent series......Page 248
C.2.1 Euler's identity......Page 249
D.3 Operations......Page 250
D.7 Control keywords......Page 251
D.8 Examples of sequential structures......Page 252
E Notation......Page 254
Index......Page 255