1 INTRODUCTION 1
1.1 Communicating pictures: the need for compression . . . . . . . . . . . . . . 1
1.1.1 What is compression? . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Why do we need compression? . . . . . . . . . . . . . . . . . . . . . 2
1.2 Applications and Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Generic drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Application drivers and markets . . . . . . . . . . . . . . . . . . . . 6
1.3 Requirements and trade-offs in a compression system . . . . . . . . . . . . 8
1.3.1 The benefits of a digital solution . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Trade-offs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 The Basics of Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Still image encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Encoding video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.3 Measuring visual quality . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 The Need for Standards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 Some basic facts about standards . . . . . . . . . . . . . . . . . . . . 11
1.5.2 A brief history of video encoding standards . . . . . . . . . . . . . . 12
1.6 The creative continuum: an interdisciplinary approach . . . . . . . . . . . . 13
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 THE HUMAN VISUAL SYSTEM 17
2.1 Principles and theories of human vision . . . . . . . . . . . . . . . . . . . . 17
2.2 Acquisition: the human eye . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Retinal tissue layers . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Optical processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Retinal photoreceptors and their distribution . . . . . . . . . . . . . 22
2.2.4 Visual processing in the retina . . . . . . . . . . . . . . . . . . . . . 24
2.3 The visual cortex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 Opponent processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 Biased competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.3 Adaptation processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
ii
CONTENTS iii
2.3.4 V1 - the primary visual cortex . . . . . . . . . . . . . . . . . . . . . 27
2.3.5 V2 - the prestriate cortex . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.6 Dorsal and Ventral Streams . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.7 Extrastriate Areas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Visual fields and acuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.1 Field of view . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2 Acuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.3 Light, luminance and brightness . . . . . . . . . . . . . . . . . . . . 30
2.4.4 Light level adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Color processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.1 Opponent theories of color . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.2 CIE 1931 chromaticity chart . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Spatial processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6.1 Just noticeable difference, contrast and Weber’s Law . . . . . . . . . 36
2.6.2 Frequency-dependent contrast sensitivity . . . . . . . . . . . . . . . . 37
2.6.3 Multiscale edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6.4 Perception of textures . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6.5 Shape and Object Recognition . . . . . . . . . . . . . . . . . . . . . 42
2.6.6 The importance of phase information . . . . . . . . . . . . . . . . . . 43
2.7 Perception of Scale and depth . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7.1 Size or Scale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7.2 Depth cues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.7.3 Depth cues and 3-D entertainment . . . . . . . . . . . . . . . . . . . 46
2.8 Temporal and spatio-temporal response . . . . . . . . . . . . . . . . . . . . 47
2.8.1 Temporal CSF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.8.2 Spatio-temporal CSF . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.8.3 Flicker and peripheral vision . . . . . . . . . . . . . . . . . . . . . . 48
2.9 Attention and eye movements . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.9.1 Saliency and attention . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.9.2 Eye movements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.10 Visual masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.10.1 Texture masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.10.2 Edge masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.10.3 Temporal masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.11 A perceptual basis for image and video compression . . . . . . . . . . . . . . 53
3 SIGNAL PROCESSING AND INFORMATION THEORY FUNDAMENTALS
60
3.1 Signal and picture sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.1 The sampling theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.2 Multidimensional sampling lattices . . . . . . . . . . . . . . . . . . . 64
3.2 Statistics of images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
CONTENTS iv
3.2.1 Histograms and distributions . . . . . . . . . . . . . . . . . . . . . . 67
3.2.2 Mean values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2.3 Correlation in natural images . . . . . . . . . . . . . . . . . . . . . . 68
3.3 Filtering and transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.3.1 Discrete time linear systems . . . . . . . . . . . . . . . . . . . . . . . 74
3.3.2 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.3.3 Linear filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.4 Filter frequency response . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3.5 Examples of practical filters . . . . . . . . . . . . . . . . . . . . . . . 78
3.3.6 Non-linear filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3.7 Linear transforms and the DFT . . . . . . . . . . . . . . . . . . . . . 80
3.4 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4.1 Basic theory of quantization . . . . . . . . . . . . . . . . . . . . . . . 82
3.4.2 Adaptation to signal statistics . . . . . . . . . . . . . . . . . . . . . . 84
3.4.3 HVS weighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.4.4 Vector quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5 Linear prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5.1 Basic feedforward linear predictive coding . . . . . . . . . . . . . . . 84
3.5.2 Linear prediction with the predictor in the feedback loop . . . . . . . 88
3.5.3 Wiener Hopf equations and the Wiener filter . . . . . . . . . . . . . 90
3.6 Information and entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6.1 Self information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.6.3 Symbols and statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.7 Machine learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.7.1 An overview of AI and machine learning . . . . . . . . . . . . . . . . 95
3.7.2 Neural networks and error backpropagation . . . . . . . . . . . . . . 96
3.7.3 Deep neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4 DIGITAL PICTURE FORMATS AND REPRESENTATIONS 112
4.1 Pixels, blocks and pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.1.1 Pixels, samples or pels . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.1.2 Moving pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.1.3 Coding units and macroblocks . . . . . . . . . . . . . . . . . . . . . . 115
4.1.4 Picture types and Groups Of Pictures . . . . . . . . . . . . . . . . . 115
4.2 Formats and aspect ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.1 Aspect ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.2 Displaying different formats . . . . . . . . . . . . . . . . . . . . . . . 122
4.3 Picture scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3.1 Standards conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
CONTENTS v
4.4 Gamma correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.5 Color spaces and color transformations . . . . . . . . . . . . . . . . . . . . . 127
4.5.1 Color descriptions and the HVS . . . . . . . . . . . . . . . . . . . . . 127
4.5.2 Sub-sampled color spaces . . . . . . . . . . . . . . . . . . . . . . . . 133
4.5.3 Color sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.6 Measuring and comparing picture quality . . . . . . . . . . . . . . . . . . . 138
4.6.1 Compression ratio and bit rate . . . . . . . . . . . . . . . . . . . . . 138
4.6.2 Objective distortion and quality metrics . . . . . . . . . . . . . . . . 139
4.6.3 Subjective assessment . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.7 Rates and distortions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.7.1 Rate-distortion characteristics . . . . . . . . . . . . . . . . . . . . . . 144
4.7.2 Rate distortion optimization . . . . . . . . . . . . . . . . . . . . . . . 146
4.7.3 Comparing video coding performance . . . . . . . . . . . . . . . . . . 146
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5 TRANSFORMS FOR IMAGE AND VIDEO CODING 151
5.1 The Principles of decorrelating transforms . . . . . . . . . . . . . . . . . . . 151
5.1.1 The basic building blocks . . . . . . . . . . . . . . . . . . . . . . . . 151
5.1.2 Principle components and axis rotation . . . . . . . . . . . . . . . . 152
5.2 Unitary transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.2.1 Basis functions and linear combinations . . . . . . . . . . . . . . . . 155
5.2.2 Orthogonality and normalization . . . . . . . . . . . . . . . . . . . . 156
5.2.3 Extension to 2-D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.3 Basic transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
5.3.1 The Haar transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
5.3.2 The Walsh-Hadamard transform . . . . . . . . . . . . . . . . . . . . 158
5.3.3 So why not use the discrete Fourier transform? . . . . . . . . . . . . 162
5.3.4 Desirable properties of an image transform . . . . . . . . . . . . . . . 162
5.4 Optimum transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.4.1 Discarding coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.4.2 The Karhunen-Loeve transform (KLT) . . . . . . . . . . . . . . . . . 165
5.4.3 The KLT in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.5 Discrete Cosine Transform (DCT) . . . . . . . . . . . . . . . . . . . . . . . . 167
5.5.1 Derivation of the DCT . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.5.2 DCT basis functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.5.3 Extension to 2-D: Separability . . . . . . . . . . . . . . . . . . . . . 172
5.5.4 Variants on sinusoidal transforms . . . . . . . . . . . . . . . . . . . . 174
5.6 Quantization of DCT coefficients . . . . . . . . . . . . . . . . . . . . . . . . 175
5.6.1 The basics of quantization . . . . . . . . . . . . . . . . . . . . . . . 175
5.6.2 Perceptually optimized quantization matrices . . . . . . . . . . . . . 178
5.7 Performance comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
CONTENTS vi
5.7.1 DCT vs DFT revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.7.2 Comparison of transforms . . . . . . . . . . . . . . . . . . . . . . . . 181
5.7.3 Rate-distortion performance of the DCT . . . . . . . . . . . . . . . . 181
5.8 DCT implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.8.1 Choice of transform block size . . . . . . . . . . . . . . . . . . . . . . 185
5.8.2 DCT complexity reduction . . . . . . . . . . . . . . . . . . . . . . . . 185
5.8.3 Field vs frame encoding for interlaced sequences . . . . . . . . . . . 187
5.8.4 Integer transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.8.5 DCT DEMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.9 JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
6 FILTER BANKS AND WAVELET COMPRESSION 192
6.1 Introduction to multiscale processing . . . . . . . . . . . . . . . . . . . . . . 192
6.1.1 The short time Fourier transform and the Gabor transform . . . . . 193
6.1.2 What is a wavelet? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6.1.3 Wavelet and filter bank properties . . . . . . . . . . . . . . . . . . . 196
6.2 Perfect reconstruction filter banks . . . . . . . . . . . . . . . . . . . . . . . . 197
6.2.1 Filter and decomposition requirements . . . . . . . . . . . . . . . . . 197
6.2.2 The 1-D filter bank structure . . . . . . . . . . . . . . . . . . . . . . 198
6.3 Multirate filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
6.3.1 Upsampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
6.3.2 Downsampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
6.3.3 System transfer function . . . . . . . . . . . . . . . . . . . . . . . . . 207
6.3.4 Perfect reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . 209
6.3.5 Spectral effects of the two-channel decomposition . . . . . . . . . . . 209
6.4 Useful filters and filter banks . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.4.1 Quadrature mirror filters . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.4.2 Wavelet filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6.4.3 Multistage (multiscale) decompositions . . . . . . . . . . . . . . . . . 216
6.4.4 Separability and extension to 2-D . . . . . . . . . . . . . . . . . . . . 217
6.4.5 Finite length sequences, edge artifacts and boundary extension . . . 220
6.4.6 Wavelet compression performance . . . . . . . . . . . . . . . . . . . . 224
6.5 Coefficient quantization and bit allocation . . . . . . . . . . . . . . . . . . . 224
6.5.1 Bit allocation and zonal coding . . . . . . . . . . . . . . . . . . . . . 224
6.5.2 Hierarchical coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
6.6 JPEG2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
6.6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
6.6.2 Architecture - bit planes and scalable coding . . . . . . . . . . . . . 227
6.6.3 Coding performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
6.6.4 Region of interest coding . . . . . . . . . . . . . . . . . . . . . . . . . 228
6.6.5 Benefits and status . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
CONTENTS vii
7 LOSSLESS COMPRESSION METHODS 233
7.1 Motivation for lossless image compression . . . . . . . . . . . . . . . . . . . 233
7.1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.1.2 Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.1.3 Dictionary methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.2 Symbol encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.2.1 A generic model for lossless compression . . . . . . . . . . . . . . . . 236
7.2.2 Entropy, efficiency and redundancy . . . . . . . . . . . . . . . . . . . 236
7.2.3 Prefix codes and unique decodability . . . . . . . . . . . . . . . . . . 237
7.3 Huffman coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.3.1 The basic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.3.2 Minimum variance Huffman coding . . . . . . . . . . . . . . . . . . . 241
7.3.3 Huffman decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
7.3.4 Modified Huffman coding . . . . . . . . . . . . . . . . . . . . . . . . 243
7.3.5 Properties of Huffman codes . . . . . . . . . . . . . . . . . . . . . . . 244
7.3.6 Adaptive methods for Huffman encoding . . . . . . . . . . . . . . . . 245
7.4 Symbol formation and encoding . . . . . . . . . . . . . . . . . . . . . . . . . 248
7.4.1 Dealing with sparse matrices . . . . . . . . . . . . . . . . . . . . . . 248
7.4.2 Symbol encoding in JPEG . . . . . . . . . . . . . . . . . . . . . . . . 249
7.4.3 JPEG performance examples . . . . . . . . . . . . . . . . . . . . . . 254
7.4.4 Lossless JPEG mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
7.4.5 Context Adaptive Variable Length Coding (CAVLC) in H.264/AVC 257
7.5 Golomb coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
7.5.1 Unary codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
7.5.2 Golomb and Golomb-Rice codes . . . . . . . . . . . . . . . . . . . . . 258
7.5.3 Exponential Golomb codes . . . . . . . . . . . . . . . . . . . . . . . . 258
7.6 Arithmetic coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
7.6.1 The basic arithmetic encoding algorithm . . . . . . . . . . . . . . . . 260
7.6.2 The basic arithmetic decoding algorithm . . . . . . . . . . . . . . . . 263
7.6.3 Advantages and properties of arithmetic coding . . . . . . . . . . . 265
7.6.4 Binary implementations of arithmetic coding . . . . . . . . . . . . . 267
7.6.5 Tag generation with scaling . . . . . . . . . . . . . . . . . . . . . . . 269
7.6.6 Context-adaptive arithmetic coding . . . . . . . . . . . . . . . . . . . 271
7.6.7 Arithmetic coding with binary symbols . . . . . . . . . . . . . . . . . 272
7.7 Performance comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
8 CODING MOVING PICTURES: MOTION PREDICTION 281
8.1 Temporal correlation and exploiting temporal redundancy . . . . . . . . . . 281
8.1.1 Why motion estimation? . . . . . . . . . . . . . . . . . . . . . . . . . 281
8.1.2 Projected motion and apparent motion . . . . . . . . . . . . . . . . . 283
CONTENTS viii
8.1.3 Understanding temporal correlation . . . . . . . . . . . . . . . . . . 284
8.1.4 How to form the prediction . . . . . . . . . . . . . . . . . . . . . . . 284
8.1.5 Understanding temporal correlation . . . . . . . . . . . . . . . . . . 287
8.1.6 Approaches to motion estimation . . . . . . . . . . . . . . . . . . . . 287
8.2 Motion models and motion estimation . . . . . . . . . . . . . . . . . . . . . 288
8.2.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
8.2.2 Affine and high order models . . . . . . . . . . . . . . . . . . . . . . 288
8.2.3 Translation only models . . . . . . . . . . . . . . . . . . . . . . . . . 289
8.2.4 Pixel-recursive methods . . . . . . . . . . . . . . . . . . . . . . . . . 291
8.2.5 Frequency domain motion estimation using phase correlation (PhC) 292
8.3 Block Matching Motion Estimation (BMME) . . . . . . . . . . . . . . . . . 295
8.3.1 Translational block matching . . . . . . . . . . . . . . . . . . . . . . 295
8.3.2 Matching criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
8.3.3 Full search algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
8.3.4 Properties of block motion fields and error surfaces . . . . . . . . . 297
8.3.5 Motion failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
8.3.6 Restricted and unrestricted vectors . . . . . . . . . . . . . . . . . . . 302
8.4 Reduced complexity motion estimation . . . . . . . . . . . . . . . . . . . . . 303
8.4.1 Pixel grids and search grids . . . . . . . . . . . . . . . . . . . . . . . 303
8.4.2 Complexity of full search . . . . . . . . . . . . . . . . . . . . . . . . . 303
8.4.3 Reducing search complexity . . . . . . . . . . . . . . . . . . . . . . . 304
8.4.4 2-D Logarithmic Search (TDL) . . . . . . . . . . . . . . . . . . . . . 305
8.4.5 N-Step Search (NSS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
8.4.6 Diamond search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
8.4.7 Hexagonal search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
8.4.8 Test Zone Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
8.4.9 Initialization and termination criteria . . . . . . . . . . . . . . . . . . 311
8.4.10 Reduced complexity block matching algorithm performance comparisons
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
8.5 Skip and merge modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
8.6 Motion vector coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
8.6.1 Motion vector prediction . . . . . . . . . . . . . . . . . . . . . . . . . 315
8.6.2 Entropy coding of motion vectors . . . . . . . . . . . . . . . . . . . . 315
8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
9 THE BLOCK-BASED HYBRID VIDEO CODEC 319
9.1 The block-based hybrid model for video compression . . . . . . . . . . . . . 319
9.1.1 Picture types and prediction modes . . . . . . . . . . . . . . . . . . . 319
9.1.2 Properties of the DFD signal . . . . . . . . . . . . . . . . . . . . . . 321
9.1.3 Operation of the video encoding loop . . . . . . . . . . . . . . . . . . 322
9.1.4 Operation of the video decoder . . . . . . . . . . . . . . . . . . . . . 322
9.2 Intra-frame prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
CONTENTS ix
9.2.1 Intra-prediction for small luminance blocks . . . . . . . . . . . . . . 328
9.2.2 Intra-prediction for larger blocks . . . . . . . . . . . . . . . . . . . . 329
9.3 Sub-pixel motion estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
9.3.1 Sub-pixel matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
9.3.2 Interpolation methods . . . . . . . . . . . . . . . . . . . . . . . . . . 331
9.3.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
9.3.4 Interpolation-free methods . . . . . . . . . . . . . . . . . . . . . . . . 336
9.4 Multiple reference frame motion estimation . . . . . . . . . . . . . . . . . . 336
9.4.1 Justification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9.4.2 Properties, complexity and performance of MRF-ME . . . . . . . . . 337
9.4.3 Reduced complexity MRF-ME . . . . . . . . . . . . . . . . . . . . . 338
9.4.4 The use of multiple reference frames in current standards . . . . . . 338
9.5 Variable block sizes for motion estimation . . . . . . . . . . . . . . . . . . . 339
9.5.1 Influence of block size . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.5.2 Variable block sizes in practice . . . . . . . . . . . . . . . . . . . . . 339
9.6 Variable sized transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
9.6.1 Integer transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
9.6.2 DC coefficient transforms . . . . . . . . . . . . . . . . . . . . . . . . 342
9.7 In-loop deblocking operations . . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
10 MEASURING AND MANAGING PICTURE QUALITY 347
10.1 General considerations and influences . . . . . . . . . . . . . . . . . . . . . . 348
10.1.1 What do we want to assess? . . . . . . . . . . . . . . . . . . . . . . . 348
10.1.2 Noise, distortion and quality . . . . . . . . . . . . . . . . . . . . . . . 348
10.1.3 Influences on perceived quality . . . . . . . . . . . . . . . . . . . . . 349
10.2 Subjective testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
10.2.1 Justification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
10.2.2 Test sequences and conditions . . . . . . . . . . . . . . . . . . . . . 351
10.2.3 Choosing subjects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
10.2.4 Testing environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.2.5 Testing methodology and recording of results . . . . . . . . . . . . . 353
10.2.6 Statistical analysis and significance testing . . . . . . . . . . . . . . . 357
10.2.7 The complete evaluation process . . . . . . . . . . . . . . . . . . . . 358
10.2.8 Subjective testing through crowdsourcing . . . . . . . . . . . . . . . 358
10.2.9 Measuring immersion in visual content . . . . . . . . . . . . . . . . . 360
10.3 Test data sets and how to use them . . . . . . . . . . . . . . . . . . . . . . . 361
10.3.1 Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
10.3.2 The relationship between Mean Opinion Score and an objective metric363
10.3.3 Evaluating metrics using public (or private) databases . . . . . . . . 363
10.4 Objective quality metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
CONTENTS x
10.4.1 Why do we need quality metrics? . . . . . . . . . . . . . . . . . . . . 365
10.4.2 A characterization of PSNR . . . . . . . . . . . . . . . . . . . . . . . 367
10.4.3 A perceptual basis for metric development . . . . . . . . . . . . . . 368
10.4.4 Perception-based image and video quality metrics . . . . . . . . . . 370
10.4.5 The future of metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
10.5 Rate-distortion optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
10.5.1 Classical rate-distortion theory . . . . . . . . . . . . . . . . . . . . . 378
10.5.2 Practical rate distortion optimization . . . . . . . . . . . . . . . . . . 380
10.5.3 The influence of additional coding modes and parameters . . . . . . 382
10.5.4 From Rate-Distortion to Rate-Quality Optimization . . . . . . . . . 387
10.6 Rate control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
10.6.1 Buffering and HRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
10.6.2 Rate control in practice . . . . . . . . . . . . . . . . . . . . . . . . . 391
10.6.3 Regions of interest and rate control . . . . . . . . . . . . . . . . . . . 394
10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
11 COMMUNICATING PICTURES: DELIVERY ACROSS NETWORKS401
11.1 The operating environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
11.1.1 Characteristics of modern networks . . . . . . . . . . . . . . . . . . . 401
11.1.2 Transmission types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.1.3 Operating constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.1.4 Error characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
11.1.5 The challenges and a solution framework . . . . . . . . . . . . . . . . 406
11.2 The effects of loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
11.2.1 Synchronization failure . . . . . . . . . . . . . . . . . . . . . . . . . . 407
11.2.2 Header loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
11.2.3 Spatial error propagation . . . . . . . . . . . . . . . . . . . . . . . . 408
11.2.4 Temporal error propagation . . . . . . . . . . . . . . . . . . . . . . . 410
11.3 Mitigating the effect of bitstream errors . . . . . . . . . . . . . . . . . . . . 411
11.3.1 Video is not the same as data! . . . . . . . . . . . . . . . . . . . . . 411
11.3.2 Error resilient solutions . . . . . . . . . . . . . . . . . . . . . . . . . 412
11.4 Transport layer solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
11.4.1 Automatic Repeat Request (ARQ) . . . . . . . . . . . . . . . . . . . 414
11.4.2 FEC Channel coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
11.4.3 Hybrid ARQ (HARQ) . . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.4.4 Packetization strategies . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.5 Application Layer solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
11.5.1 Network abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
11.5.2 The influence of frame type . . . . . . . . . . . . . . . . . . . . . . . 418
11.5.3 Synchronization codewords . . . . . . . . . . . . . . . . . . . . . . . 420
11.5.4 Reversible VLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
CONTENTS xi
11.5.5 Slice structuring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
11.5.6 Error tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
11.5.7 Redundant motion vectors . . . . . . . . . . . . . . . . . . . . . . . . 424
11.6 Cross layer solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
11.6.1 Link adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
11.7 Inherently robust coding strategies . . . . . . . . . . . . . . . . . . . . . . . 427
11.7.1 Error Resilient Entropy Coding (EREC) . . . . . . . . . . . . . . . . 427
11.7.2 Pyramid vector quantization (PVQ) . . . . . . . . . . . . . . . . . . 431
11.8 Error concealment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
11.8.1 Detecting missing information . . . . . . . . . . . . . . . . . . . . . . 434
11.8.2 Spatial error concealment (SEC) . . . . . . . . . . . . . . . . . . . . 435
11.8.3 Temporal error concealment . . . . . . . . . . . . . . . . . . . . . . . 436
11.8.4 Hybrid methods with mode selection . . . . . . . . . . . . . . . . . . 440
11.8.5 Intelligent error concealment . . . . . . . . . . . . . . . . . . . . . . 442
11.9 Congestion management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
11.9.1 HTTP Adaptive Streaming (HAS) . . . . . . . . . . . . . . . . . . . 442
11.9.2 Scalable video encoding . . . . . . . . . . . . . . . . . . . . . . . . . 445
11.9.3 Multiple description coding (MDC) . . . . . . . . . . . . . . . . . . . 447
11.10Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
12 VIDEO CODING STANDARDS AND FORMATS 453
12.1 The need for and role of standards . . . . . . . . . . . . . . . . . . . . . . . 453
12.1.1 The focus of video standardization . . . . . . . . . . . . . . . . . . . 453
12.1.2 The standardization process . . . . . . . . . . . . . . . . . . . . . . . 454
12.1.3 Intellectual property and licensing . . . . . . . . . . . . . . . . . . . 455
12.2 H.120 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
12.2.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
12.2.2 Primary features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12.3 H.261 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12.3.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12.3.2 Picture types and primary features . . . . . . . . . . . . . . . . . . . 456
12.4 MPEG-2/DVB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
12.4.1 Brief History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
12.4.2 Picture types and primary features . . . . . . . . . . . . . . . . . . . 458
12.4.3 MPEG-2 profiles and levels . . . . . . . . . . . . . . . . . . . . . . . 459
12.5 H.263 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
12.5.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
12.5.2 Picture types and primary features . . . . . . . . . . . . . . . . . . . 460
12.6 MPEG-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
12.6.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
12.6.2 Picture types and primary features . . . . . . . . . . . . . . . . . . . 465
CONTENTS xii
12.7 H.264/AVC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
12.7.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
12.7.2 Primary features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
12.7.3 Network abstraction and bitstream syntax . . . . . . . . . . . . . . . 468
12.7.4 Pictures and partitions . . . . . . . . . . . . . . . . . . . . . . . . . . 469
12.7.5 The Video coding layer . . . . . . . . . . . . . . . . . . . . . . . . . 472
12.7.6 Profiles and levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
12.7.7 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
12.7.8 Scalable extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
12.7.9 Multiview extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
12.8 H.265/HEVC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
12.8.1 Brief background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
12.8.2 Primary features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
12.8.3 Network abstraction and high level syntax . . . . . . . . . . . . . . . 479
12.8.4 Pictures and partitions . . . . . . . . . . . . . . . . . . . . . . . . . . 480
12.8.5 The Video Coding Layer (VCL) . . . . . . . . . . . . . . . . . . . . . 482
12.8.6 Profiles and Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
12.8.7 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
12.8.8 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
12.9 H.266/VVC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
12.9.1 Brief background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
12.9.2 Primary features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
12.9.3 High-level syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
12.9.4 Picture partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
12.9.5 Intra prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
12.9.6 Inter prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
12.9.7 Transformation and quantization . . . . . . . . . . . . . . . . . . . . 496
12.9.8 Entropy coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
12.9.9 In-loop filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
12.9.10Coding tools for 360 video . . . . . . . . . . . . . . . . . . . . . . . 499
12.9.11 Profiles, tiers and levels . . . . . . . . . . . . . . . . . . . . . . . . . 499
12.9.12Performance gains for VVC over recent standards . . . . . . . . . . . 499
12.10The Alliance of Open Media (AOM) . . . . . . . . . . . . . . . . . . . . . . 501
12.10.1VP9 and VP10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
12.10.2AV1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
12.11Other standardized and proprietary codecs . . . . . . . . . . . . . . . . . . . 502
12.11.1VC-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
12.11.2 Dirac or VC-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
12.11.3 RealVideo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
12.12Codec comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
12.13Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
CONTENTS xiii
13 COMMUNICATING PICTURES - THE FUTURE 509
13.1 The motivation: more immersive experiences . . . . . . . . . . . . . . . . . 509
13.2 New formats and extended video parameter spaces . . . . . . . . . . . . . . 510
13.2.1 Influences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
13.2.2 Spatial resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
13.2.3 Temporal resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
13.2.4 Dynamic range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
13.2.5 360 degree video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
13.2.6 Parameter interactions and the creative continuum . . . . . . . . . . 521
13.3 Intelligent video compression . . . . . . . . . . . . . . . . . . . . . . . . . . 522
13.3.1 Challenges for compression: understanding content and context . . 522
13.3.2 Parametric video compression . . . . . . . . . . . . . . . . . . . . . 525
13.3.3 Context based video compression . . . . . . . . . . . . . . . . . . . . 527
13.4 Deep video compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
13.4.1 The need for data - training datasets for compression . . . . . . . . . 528
13.4.2 Deep optimization of compression tools . . . . . . . . . . . . . . . . 529
13.4.3 End to end architectures for deep image compression . . . . . . . . 534
13.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
