Post-Production: Video Compression

I.	Introduction
	A.	MPEG-Moving Picture Expert Group
	B.	Defines standards for compression of digital video/audio signals.
	C.	Based on ITU-T standard for video conferenceing/telephony
	D.	Combined with JPEG (Joint Photographic Experts Group) for 			compressing electronic still images
	E.	Goal: Define video coding algorithm for digital storage media.  
	F.	Three Sections
		1.	Systems aspect (multiplexing+synchronization)
		2.	Video Coding
		3.	Audio Coding
	G.	This first standard called MPEG-1, restricted to non-interlaced video-		formats.   Designed to support bit-rates up to 1.5 Mbit/s
	H.	MPEG-2, capable of coding interlaced pictures directly, supports HD 		formats w/bit rate range from 15/30 Mbit/s.
	I.	MPEG standards specify syntax and semantics of bit-streams and 			decoding process, NOT encoding process
	J.	Encoding to discretion of coder designers to allow for new techniques to 		develop.
II.	Video Coding Principles
	A.	Studio quality 625 line component picture requires 216 Mbit/s to convey 		luminance and chrominance.
		1.	Y = 8 bit x 13.5 MHz = 108
		2.	CB = 8 x 6.75 = 54
		3.	CR = 8 x 6.75 = 54
	B.	Bandwidth restricting media such as satellite transmission requires way 		to reduce high bit rate needed to represent digitized picture.
	C.	Video bit-rate reduction system: Removes redundant and less important 		information  from signal prior to transmission, reconstructs approximation 		of image from remaining information at the decoder.  
	D.	Redundancy Types
		1.	Spatial and Temporal Redundancy: Pixel values correlate with 			those of their neighbors over space and time, to an extent a picture 			value can be predicted if neighboring values known
		2.	Entropy Redundancy: Some code values occur more than others.  			More commonly used values use shorter codes than those that 			occur less frequently.
		3.	Psychovisual Redundancy: Occurs due to function of eyes and 			brain.  Eye has limit for fine detail (spatial resolution limit) and 			ability to track fast-moving images (temporal resolution limit).  
III.	MPEG Video Compression Toolkit
	A.	Introduction
		1.	Sample rate reduction reduces bit rate, but introduces loss of 				resolution.
		2.	Very low bit rates (MPEG-1)
			a.	Alternate fields discarded and horizontal						sample rate reduced to  about 360 pixels per line.
			b.	Sample rate for chrominance is half that of luminance for X 				and Y
			c.	Reduces  bit rate to less than 1/5 original
		3.	Broadcast Quality (3-10 Mbit/s)
			a.	No horizontal sample rate reduction for luminance or 				chrominance.
			b.	No temporal sub-sampling done either
			c.	Vertical  chrominance sampling frequency is halved
			d.	MPEG-2 therefore uses 4:2:0 more frequently over 4:2:2
			e.	PAL decoder naturally sub samples at 4:2:0
		4.	Discrete Cosine Transform (DCT): Assists removing spatial 			redundancy by concentrating signal energy into few coefficients
		5.	Multi-Compensated Interframe Prediction: Removes temporal 			redundancy using techniques similar to Differential Pulse-code 			modulation.
	B.	Discrete Cosine Transform
		1.	Luminance signal of 4:2:0 625 line picture is 705 horizontal pixels 			and 576 lines vertically.
		2.	MPEG removes spatial redundancy by processing signals in 2D 			8x8 blocks of pixels.
		3.	DCT transform goes between normal 2D image and represents it 			in frequency domain.
		4.	Each coefficient in the block indicates contribution of different DCT 			basis function.
		5.	Called DC coefficient, represents average brightness of block
		6.	Increasing horizontal frequencies left to right, increasing vertical 			frequencies from top to bottom.  
		7.	DCT actually increases bit rate from 8x8 8-bit pixels to 8-8 block 			with 11-bit DCT coefficients.
		8.	This allows for reversibility of the function
		9.	Bit rate reduced because in normal blocks, energy concentrated in 			low frequency coefficients and higher ones are near zero.
		10.	Coefficients aren't transmitted if close to zero, reducing bit rate
		11.	Remaining coefficients quantized and coded
		12.	Non-uniform distribution due to spatial redundancy in original 			block
		13.	Best transforms based on concentration of energy of picture into 			few coefficients.
		14.	DCT accomplishes this and is also reversible
		15.	Blocks ar 8x8 because trade off between large picture area and 			spatial variation in a picture.
		16.	Large block would also emphasize variations between blocks and 			lead to windowing.
	C.	Coefficient Quantisation
		1.	Different quantisation applied depending on frequency within the 			block.
		2.	Objective to minimize number of bits sent to decoder while 				allowing image to still be reconstructed
		3.	Reduced quantization accuracy reduces number of bits sent to 			decoder but increases chance of error
		4.	Quantisation noise is irreversible, making the coding and 				decoding process "lossy"
		5.	More error tolerated in higher frequencies because noise less 			visible. 
		6.	Noise also less visible in chrominance than luminance
		7.	MPEG uses weighing matrices to define relative accuracy for 			quantization.  
		8.	Different weighting matrices based on different prediction modes.
		9.	Weighted coefficients passed through fixed linear quantization 			law .
		10.	Sometimes increased threshold around zero to maximize number 			of coefficients quantized to zero, these values are usually noise.
		11.	Noise more visible in blocks with  high contrast edges between 			two areas.
		12.	Quantisation can be modified in these blocks to limit the error, 			especially for high frequency coefficients
	D.	Zig Zag Coefficient Scanning, run length coding, variable length 			coding
		1.	After quantization 8 x 8 blocks scanned in zig-zag pattern to turn 			2D arrays into serial string of quantized coefficients
		2.	For picture material with strong vertical frequency components due 			to interlaced structure, bias used to scan vertical coefficients first. 
		3.	For pictures without strong vertical structure, scan is diagonal from 			top left to bottom right.	
		4.	Coder signals scan pattern choice to decoder
		5.	String of coefficients produced by scanning system by counting 			number of zero coefficients before a non zero coefficient, this is 			called run length coding.
		6.	Run length value and non-zero coefficient are combined using 			variable length code.
		7.	Small runs of zeros more likely than long, small coefficients more 			likely than large.
		8.	Code allocates code of different length depending on the 				frequency of occurrence of each zero/run length combination 			(similar to entropy redundancy)
		9.	Common ones are smaller, less common longer
		10.	All other combinations made up of escape code plus two fixed 			length codes, one 6 bit for run length, one 12 bit for coefficient 			value
		11.	Sometimes a second VLC code table is needed
		12.	DC coefficient treated differently in different modes
		13.	VLC's all designed so that no complete codeword is prefix for any 			other codeword, so decoder can identify where one codeword 			ends and another starts
		14.	No VLC can do 23 contiguous zeros, this combination is for 				synchronizing purposes
		15.	DC coefficients within blocks differentially encoded before variable 			length coding
	E.	Buffering and feedback
		1.	Process creates varying bit-rate depending upon complexity of 			picture and amount and type of motion
		2.	For constant bit rate needed for transmission over fixed bit-rate 			system, buffer is needed to smooth out variations in bit-rate
		3.	To prevent overflow or underflow of buffer, occupancy is monitored 			and feedback applied to coding processes to control input at 			buffer.
		4.	When buffer becomes full, quantiser more coarser in to reduce 			number of bits used to code each DCT coefficient
		5.	As buffer empties, DCT quantisation is finer
		6.	Final bier rate at output of MPEG video can be freely varied. 
		7.	If output bit rate reduced, buffer empties slower and DCT 				coefficient quantisation is coarser.
		8.	Decreasing output bit-rate reduces quality of decoded pictures
		9.	Output bit rate of video encoder can be readily reduced to fit more 			channels.
		10.	An HDTV channel would require more space
	F.	Reduction of temporal redundancy; Interframe Prediction
		1.	Takes advantage of small changes between one frame to the next
		2.	Differential Pulse Code Modulation coder quantizes the 				differences between an input and a prediction based on a 				previous locally-decoded  output.
		3.	Local decoder reconstructs pictures as they would appear at the 			destination decoder and forms the input for the predictor
		4.	Samples in one frame are used in prediction of incoming samples
		5.	MPEG combines interframe prediction with DCT and variable 			length coding
		6.	Coder subtracts prediction and input to form "prediction error" 			picture.
		7.	Prediction error transformed with DCT, coefficients quantized and 			coded with VLC.
		8.	Simplest predictions based on comparing the same blocks in 			samples and reference.
		9.	This causes a delay of one frame, which is good for prediction in 			stationary regions but not moving regions.
	G.	Motion-Compensated interframe prediction
		1.	The reference block is shifted when being compared to block 			being coded to compensate for translational movement.
		2.	Motion occurring detected through 'block matching' where trial 			offsets tested in coder.
		3.	Best offset based on minimum error between coded block and 			prediction.
		4.	This algorithm is left to coder because encoding is not covered in 			MPEG.
		5.	Search area has to be loud enough to cover any time of movement 			from frame to frame.
		6.	Increases search area also increases amount of processing 			needed.
		7.	Bi-directional prediction forms prediction between previous frame 			and following frame using linear combination.
		8.	This is useful where motion uncovers new details
		9.	To allow prediction using a future frame, frames have to be 				reordered so they're transmitted in a different order than the 			displayed order.
		10.	This causes processing delay
		11.	Motion Compensation is usually in 16 pixel macroblocks.
		12.	Trade off between minimizing bit rate (larger blocks) and varying 			prediction process (smaller blocks)
		13.	Motion vectors differentially encoded in reference to previous 			vectors in order to minimize size.
		14.	Motion vector value then encoded using another VLC table
	H.	Prediction Modes
		1.	Motion-compensated predictor uses many methods for prediction.
		2.	Forward predicted from past picture or backward predicted from 			future picture (P coded)
		3.	Interpolated is averaging the forward and backward prediction (B 			coded)
		4.	Zero value prediction encodes source image block instead of 			prediction error block (I coded)
		5.	No prediction information needed
		6.	Fields of frames can be predicted separately from their own motion 			vector (field prediction coding), or together uses a common motion 			vector (frame prediction coding)
		7.	Frame prediction coding better for slow motion, field prediction for 			increased motion.
	I.	16 x 8 Motion Compensation
		1.	Two motion vectors used, one for upper and other for lower half of 			macroblock
		2.	Only used in field-structured pictures, approximating a frame-			structured 16 x 16 block.
	J.	Dual Prime Mode
		1.	Used in both field and frame structured
		2.	Generates a motion vector and a differential offset motion vector
		3.	For field pictures, two vectors and predictions for field pictures 			combined at end.
		4.	For frame pictures, process repeated for each field for four 				predictions which combine at end for 2 final predictions.
		5.	Alternate to bi-directional prediction because it avoids frame re-			ordering and delay but is still similarly efficient.
		6.	Coder chooses prediction method for each macroblock in order to 			minimize distortion, choice is transmitted to decoder.  
		7.	Some macroblocks don't have to be coded, no DCT coefficient, 			address counter skips to next coded block.  Decoder output is the 			predictor output.
	K.	Picture types-Three types in MPEG-2, defines which prediction mode 		may be used for each macroblock
		1.	Intra Pictures (I Pictures): Coded without reference to other 			pictures, reduces spatial redundancy.  Gives a spot in bit stream 			where decoding can begin without reference to other pictures
		2.	Predictive Pictures( P Pictures):  Coded with motion 				compensation from past I or P pictures.  Reduces both spatial and 			temporal redundancy, giving increased compression than I 				pictures.
		3.	Bi-directionally-predictive pictures (B pictures)
			a.	Use past and future I and P pictures for motion 					compensation, offering the most compression.
			b.	Requires re-ordering of pictures, introducing delay.
		4.	Group of pictures
			a.	Sequence in which the different types of pictures occurs
			b.	GOP structure has N, number of pictures in group and M, 				spacing between P pictures.
			c.	Each picture type has a different number of bits
IV.	MPEG Profiles and Levels
	A.	Intro
		1.	Different algorithms or tools for different functions
		2.	Including all this in a decoder is too complex so individual profiles 			used depending on the use.
		3.	Level sets constraints on different parameters within the profile
		4.	Higher profiles are supersets of lower ones
		5.	Number of possible profiles is restricted using conformance 			points
	B.	Simple profile - Uses no B-frames so theres no backward or interpolated 		prediction.  Also no re-ordering so it is good for low-delay application.
	C.	Main profile - Has support for B frames to improve picture quality, 			increases delay.  used for most MPEG-2 video decoder chips.
	D.	SNR profile - Support for enhancement layers of DCT coefficient 			refinement with Signal to Noise Scalability
	E.	Spatial profile - Support for enhancement layers carrying image at 		different resolutions with spatial scalability tool.
	F.	High profile - Support for 4:2:2 sampled video
	G.	All decoders also support MPEG-1.
V.	Conclusion
	A.	This is some shit.
	B.	MPEG serves wide range of applications, bit-rates, qualities, and 			services.
	C.	Based on flexible toolkit of bit rate reduction techniques. 
	D.	Bitstream syntax and decoding is defined, coding is not specified.
	E.	Picture quality dependent on content a lot of the time