Contents
About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Chapter 1 Introduction 1
1.1 The Value of Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 MPEG-4 and H.264 Video Compression Standards . . . . . . . . . . . . . . 2
1.3 This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Chapter 2 Elements of Information 5
2.1 What Is Information? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Memory Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Markov Memory Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Information of Text and Kolmogorov Complexity . . . . . . . . . . . . . . . 11
2.5 Data Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Chapter 3 Imaging Basics 15
3.1 Sampling and Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Spatial Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.2 Temporal Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.3 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Color Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 RGB Color Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Color Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.1 The XYZ Color Model . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4.2 YUV Color Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.3 YCbCr Color Model . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Conversions between RGB and YCbCr . . . . . . . . . . . . . . . . . . . . . 29
3.5.1 Floating Point Implementation . . . . . . . . . . . . . . . . . . . . . 29
3.5.2 Integer Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.6 YCbCr Sampling Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4:4:4 YCbCr Sampling Formats . . . . . . . . . . . . . . . . . . . . . . . 33
4:2:2 YCbCr Sampling Formats (High Quality Color Reproduction) . . . . 34
4:2:0 YCbCr Sampling Formats (Digital Television and DVD Storage) . . . 34
3.7 Measuring Video Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7.1 Subjective Quality Measurement . . . . . . . . . . . . . . . . . . . . 35
3.7.1.1 ITUR BT.500 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7.2 Objective Quality Measurement . . . . . . . . . . . . . . . . . . . . 37
Chapter 4 Image and Video Storage Formats 39
4.1 Portable Pixel Map ( PPM ) . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 The Convert Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Read and Write PPM Files . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4 Common Intermediate Format ( CIF ) . . . . . . . . . . . . . . . . . . . . . 44
Chapter 5 Macroblocks 47
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Implementing RGB and 4:2:0 YCbCr Transformation for Video Frames . . . 47
5.3 Testing Implementation Using PPM Image . . . . . . . . . . . . . . . . . . . 56
Chapter 6 Discrete Cosine Transform ( DCT ) 63
6.1 Time, Space and Frequency Domains . . . . . . . . . . . . . . . . . . . . . 63
6.2 Discrete Cosine Transform ( DCT ) . . . . . . . . . . . . . . . . . . . . . . 63
6.3 Floating-point Implementation of DCT and IDCT . . . . . . . . . . . . . . . 65
6.4 Fast DCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.5 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.6 Inverse DCT ( IDCT ) Implementation . . . . . . . . . . . . . . . . . . . . . 80
6.7 Applying DCT and IDCT to YCbCr Macroblocks . . . . . . . . . . . . . . . 86
Chapter 7 Quantization and Run-level Encoding 97
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.2 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2.1 Scalar Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2.2 Vector Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.3 MPEG-4 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.3 Reordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.4 Run-Level Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Chapter 8 Huffman Encoding 115
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.2 Huffman Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.3 Huffman Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.4 Pre-calculated Huffman-based Tree Coding . . . . . . . . . . . . . . . . . . 125
8.5 Huffman Coding Implementation . . . . . . . . . . . . . . . . . . . . . . . 127
Chapter 9 Image Prediction and Motion Compensation 137
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.2 Temporal Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.3 Block Based Motion Estimation and Motion Compensation . . . . . . . . . 138
9.4 Matching Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.5 Choice of Block Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.6 Motion Estimation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.6.1 Full Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.6.2 Fast Searches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Three Step Search ( TSS ) . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Hierarchical Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Nearest Neighbours Search . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
9.7 Frame Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.7.1 Intraframes (I-frames) . . . . . . . . . . . . . . . . . . . . . . . . . .149
9.7.2 Inter-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
P-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154
B-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154
9.8 Typical GOP Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
9.9 Rate Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
9.10 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Chapter 10 Video Programming 159
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
10.2 Simple DirectMedia Layer ( SDL ) . . . . . . . . . . . . . . . . . . . . . . 159
10.3 SDL API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
10.3.1 Initializing the Library . . . . . . . . . . . . . . . . . . . . . . . . 160
10.3.2 Video API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Choosing and setting video modes . . . . . . . . . . . . . . . . . . . . . . 162
Drawing pixels on the screen . . . . . . . . . . . . . . . . . . . . . . . . .164
Loading and displaying images . . . . . . . . . . . . . . . . . . . . . . . . 166
10.4 SDL Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
10.4.1 Event Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
10.5 SDL Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.5.1 What Are Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.5.2 Pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.5.3 SDL Thread Programming . . . . . . . . . . . . . . . . . . . . . . 174
10.6 A Simple PPM Viewer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
10.7 The Producer-Consumer Problem . . . . . . . . . . . . . . . . . . . . . . . 179
10.8 A Multi-threaded Raw Video Player . . . . . . . . . . . . . . . . . . . . . . 183
Chapter 11 Video File Formats and Codec Player 189
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.2 Video Storage Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.2.1 Requirements of Video File Format . . . . . . . . . . . . . . . . . . 189
11.2.2 Common Internet Video Container File Format . . . . . . . . . . . . 189
11.2.3 Simple Raw or Stream Video Format . . . . . . . . . . . . . . . . . 190
11.2.4 Internet Playlist, Index, and Scripting Format . . . . . . . . . . . . . 190
11.3 Case Study: AVI Files ( .avi ) . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.3.1 RIFF File Format . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.3.2 AVI RIFF Format . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.4 Utility Program for Reading AVI Files . . . . . . . . . . . . . . . . . . . . 195
11.5 A Simple Video Codec for Intra Frames . . . . . . . . . . . . . . . . . . . . 198
11.5.1 Compressed File Header . . . . . . . . . . . . . . . . . . . . . . . . 198
11.5.2 Modified RGB-YCbCr Transformation . . . . . . . . . . . . . . . . 200
11.5.3 Intra Frame Codec Implementation . . . . . . . . . . . . . . . . . . 201
Chapter 12 DPCM Video Codec 205
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
12.2 DPCM Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . . . . 206
12.3 Implementation of DPCM Codec . . . . . . . . . . . . . . . . . . . . . . . 208
Chapter 13 Implementation of Video Codec with ME and MC 215
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.2 Points and Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.3 Three Step Search ( TSS ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
13.4 Reconstructing Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
13.5 Encoding Motion Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
13.6 Encoding One Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
13.7 Decoding a Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Chapter 14 Hybrid Coding 237
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
14.2 MPEG-4 Facial Animation . . . . . . . . . . . . . . . . . . . . . . . . . . 239
14.3 Computing Face Mesh Vertices . . . . . . . . . . . . . . . . . . . . . . . . 242
14.4 Keyframing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
14.5 Extracting FAPs From Video . . . . . . . . . . . . . . . . . . . . . . . . . 246
14.5.1 Active Appearance Model (AAM) . . . . . . . . . . . . . . . . . . 247
14.5.2 An AAM Search Algorithm . . . . . . . . . . . . . . . . . . . . . . 249
14.6 3DS File Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
14.7 Parsing 3DS Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
14.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Bibliography 277
Index 281
