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