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.2.1 RGB Color Model . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 YUV Color Model . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.3 YCbCr Color Model . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Conversions between RGB and YCbCr . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1 Floating Point Implementation . . . . . . . . . . . . . . . . . . . 24
3.3.2 Integer Implementation . . . . . . . . . . . . . . . . . . . . . . .25
3.4 YCbCr Sampling Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . .28
4:4:4 YCbCr Sampling Formats . . . . . . . . . . . . . . . . . . . . . . .28
4:2:2 YCbCr Sampling Formats (High Quality Color Reproduction) . . . . . .28
4:2:0 YCbCr Sampling Formats (Digital Television and DVD Storage) . . . . 29
3.5 Measuring Video Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.1 Subjective Quality Measurement . . . . . . . . . . . . . . . . . . .30
3.5.1.1 ITUR BT.500 . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5.2 Objective Quality Measurement . . . . . . . . . . . . . . . . . . . 32
Chapter 4 Image and Video Storage Formats 33
4.1 Portable Pixel Map ( PPM ) . . . . . . . . . . . . . . . . . . . . . . . . . .33
4.2 The Convert Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Read and Write PPM Files . . . . . . . . . . . . . . . . . . . . . . . . . . .35
4.4 Common Intermediate Format ( CIF ) . . . . . . . . . . . . . . . . . . . . . .38
Chapter 5 Macroblocks 41
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
5.2 Implementing RGB and 4:2:0 YCbCr Transformation for Video Frames . . . . . . .41
5.3 Testing Implementation Using PPM Image . . . . . . . . . . . . . . . . . . . .53
Chapter 6 Discrete Cosine Transform ( DCT ) 59
6.1 Time, Space and Frequency Domains . . . . . . . . . . . . . . . . . . . . . ..59
6.2 Discrete Cosine Transform ( DCT ) . . . . . . . . . . . . . . . . . . . . . ..59
6.3 Floating-point Implementation of DCT and IDCT . . . . . . . . . . . . . . . . 61
6.4 Fast DCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
6.5 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
6.6 Inverse DCT ( IDCT ) Implementation . . . . . . . . . . . . . . . . . . . . . 78
6.7 Applying DCT and IDCT to YCbCr Macroblocks . . . . . . . . . . . . . . . . . .81
Chapter 7 Quantization and Run-level Encoding 93
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93
7.2 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94
7.2.1 Scalar Quantization . . . . . . . . . . . . . . . . . . . . . . . . 94
7.2.2 Vector Quantization . . . . . . . . . . . . . . . . . . . . . . . . 97
7.2.3 MPEG-4 Quantization . . . . . . . . . . . . . . . . . . . . . . . . 98
7.3 Reordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.4 Run-Level Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Chapter 8 Huffman Encoding 111
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.2 Huffman Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
8.3 Huffman Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . . . .116
8.4 Pre-calculated Huffman-based Tree Coding . . . . . . . . . . . . . . . . . ..121
8.5 Huffman Coding Implementation . . . . . . . . . . . . . . . . . . . . . . . .123
Chapter 9 Image Prediction and Motion Compensation 135
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2 Temporal Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.3 Block Based Motion Estimation and Motion Compensation . . . . . . . . . . . .136
9.4 Matching Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .139
9.5 Choice of Block Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9.6 Motion Estimation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 141
9.6.1 Full Search . . . . . . . . . . . . . . . . . . . . . . . . . . . .142
9.6.2 Fast Searches . . . . . . . . . . . . . . . . . . . . . . . . . . .143
Three Step Search ( TSS ) . . . . . . . . . . . . . . . . . . . .143
Hierarchical Search . . . . . . . . . . . . . . . . . . . . . . .144
Nearest Neighbours Search . . . . . . . . . . . . . . . . . . . .146
Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
9.7 Frame Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .147
9.7.1 Intraframes (I-frames) . . . . . . . . . . . . . . . . . . . . . . 147
9.7.2 Inter-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
P-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
B-frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.8 Typical GOP Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
9.9 Rate Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
9.10 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Chapter 10 Video Programming 157
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .157
10.2 Java Image Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . .158
10.3 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.3.1 What Are Threads . . . . . . . . . . . . . . . . . . . . . . . . .166
10.5.2 Pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . .166
10.5.3 Java Threads . . . . . . . . . . . . . . . . . . . . . . . . . . .168
10.4 The Producer-Consumer Problem . . . . . . . . . . . . . . . . . . . . . . . 170
10.5 A Multi-threaded Raw Video Player . . . . . . . . . . . . . . . . . . . . . 176
Chapter 11 Video File Formats and Codec Player 185
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185
11.2 Video Storage Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.2.1 Requirements of Video File Format . . . . . . . . . . . . . . . . 185
11.2.2 Common Internet Video Container File Format . . . . . . . . . . . 185
11.2.3 Simple Raw or Stream Video Format . . . . . . . . . . . . . . . . 186
11.2.4 Internet Playlist, Index, and Scripting Format . . . . . . . . . .186
11.3 Case Study: AVI Files ( .avi ) . . . . . . . . . . . . . . . . . . . . . . .186
11.3.1 RIFF File Format . . . . . . . . . . . . . . . . . . . . . . . . .187
11.3.2 AVI RIFF Format . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.4 Utility Program for Reading AVI Files . . . . . . . . . . . . . . . . . . . 191
11.5 A Simple Video Codec for Intra Frames . . . . . . . . . . . . . . . . . . . 195
11.5.1 Compressed File Header . . . . . . . . . . . . . . . . . . . . . .195
Chapter 12 DPCM Video Codec 201
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .201
12.2 DPCM Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . . . . .202
12.3 Implementation of DPCM Codec . . . . . . . . . . . . . . . . . . . . . . . .204
Chapter 13 Implementation of Video Codec with ME and MC 211
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211
13.2 Points and Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211
13.3 Three Step Search ( TSS ) . . . . . . . . . . . . . . . . . . . . . . . . . 214
13.4 Reconstructing Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . .218
13.5 Encoding Motion Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13.6 Encoding One Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225
13.7 Decoding a Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .228
Chapter 14 Hybrid Coding 233
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233
14.2 MPEG-4 Facial Animation . . . . . . . . . . . . . . . . . . . . . . . . . . 235
14.3 Computing Face Mesh Vertices . . . . . . . . . . . . . . . . . . . . . . . .239
14.4 Keyframing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242
14.5 Extracting FAPs From Video . . . . . . . . . . . . . . . . . . . . . . . . .242
14.5.1 Active Appearance Model (AAM) . . . . . . . . . . . . . . . . . . 243
14.5.2 An AAM Search Algorithm . . . . . . . . . . . . . . . . . . . . . 245
14.6 3DS File Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
14.7 Parsing 3DS Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
14.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250