An Introduction to Digital Video Data Compression in Java
by
Fore June

To obtain the source code of the programs presented in the book, click the following link ( Resources ). Enter user name 'forej' and the password printed in the book to access it.

Sample Chapters:

Supplementary materials

  • Principal Component Analysis
  • Active Shape Models
  • Table of Content

    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