An Introduction to Video Compression in C/C++

To obtain the source code of the programs presented in the book, click the following link ( Resources ).

Sample Chapters:

Table of Content

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