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.3.2 Pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
10.3.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
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.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Chapter 15 Principal Component Analysis 253
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
15.2 Matrix Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
15.3 Discrete Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
15.3.1 Standard Deviation . . . . . . . . . . . . . . . . . . . . . . . . . . 262
15.3.2 Covariance and Correlation . . . . . . . . . . . . . . . . . . . . . 263
15.3.3 Correlation and Covariance Matrices . . . . . . . . . . . . . . . . 264
15.4 Eigenvectors and Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 266
15.5 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . 271
15.5.1 PCA Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
15.6 Eigenvectors by Jacobi Method . . . . . . . . . . . . . . . . . . . . . . . . 276
Chapter 16 Active Shape Models (ASMs) 283
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.2 Statistical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.3 PCA with Fewer Samples than Dimensions . . . . . . . . . . . . . . . . . . 287
16.4 Shape Model Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
Bibliography 291
Index 294
