Video compression fundaments

Video Compression Basics

Video compression fundaments

■ since a video stream has 2 spatial and 1 temporal dimensions, video compression is usually done independently in the spatial dimensions and, respectively, in the time dimension

■ in the spatial dimensions – compression tries to eliminate spatial redundancy (like in JPEG)

■ in the time dimension – compression tries to eliminate temporal redundancy (i.e. motion of objects)

Video compression fundaments (2)

■ the spatial encoder typically works on 8 x 8 pixel blocks of a frame

■ the temporal encoder typically works on 16 x 16 pixel image blocks

■ motion estimation/compensation is used for the temporal encoder; motion estimation unit create motion vectors for each 16 x 16 block

■ there are 3 types of frames:

■ I-frames : intracoded frames, key frames

■ P-frames: predicted frames

■ B-frames: bi-directional predicted frames

Compression in the time domain

■ difference between consecutive frames is often small

■ remove inter-frame redundancy

■ sophisticated encoding, relatively fast decoding

Video compression standards

■ there are 2 family of standards: ISO/IEC MPEG and ITU- T

■ International Standardization Organization(ISO),

International Electrotechnical Commission (IEC) , MPEG (Moving Pictures Experts Group) produced the MPEG standards:

■ MPEG-1, 1992 : video standards for CDROMs and Internet video

■ MPEG-2, 1994 : video standards for television and telecommunications standards

■ MPEG-4, 1999 : advanced video coding standards

■ MPEG-7, 2001 : metadata for audio-video streams, Multimedia Content Description Interface

■ MPEG-21, 2002 : distribution, exchange, user access of multimedia data and intellectual property management

Video compression standards (2)

■ International Telecommunication Union (ITU-T)

developed several recommendations for video coding:

■ H.261, 1990 : the first video codec specification, “Video Codec for Audio Visual Services at p x 64kbps”

■ H.262, 1995 : Infrastructure of audiovisual services—Coding of moving video

■ H.263, 1995 : Video coding for low bit rate communications

■ H.264, 2002 : Advanced Video Codec (AVC), in conjunction with MPEG-4

General design of a video encoder

Frame Intracoding

■ a frame is intracoded similar to the way a JPEG encoder encodes images

■ Spatial Operator T refers to DCT (Discrete Cosine Transform)

■ Quantizer Q refers to the quantization matrix

■ VLC refers to Variable Length Coding, i.e. run-length encoding (including zig-zag order) plus entropy

encoding (Huffman encoding)

Motion estimation/compensation

■ was invented in 1960s

■ is based on the idea that motion in a video is created by solid objects which move on a relatively fixed background

■ comprises 3 steps:

■ first stage estimates objective motion (motion estimation) between the previously reconstructed frame and the current frame; results MVs (Motion Vectors) for each 16x16 block of pixels

■ the second stage creates the current frame prediction (MC) using the motion estimates and the previously reconstructed frame

■ the final stage encodes the difference between the prediction and the actual current frame (i.e. the prediction error) and the MVs

■ for motion estimation MSE (Mean Squared Error) is used:

Motion estimation/compensation (2)

Compressed video stream

MPEG-1

MPEG-1

■ developed by the Working Group 11 (WG11) of

SubCommittee 29 (SC29) of the Joint ISO/IEC Technical Committee 1 (JTC 1) on Information Technology;

informally MPEG (Motion Picture Experts Group)

■ was developed between 1988-1990

■ in 1992-1994 reached an International Standard

■ was based on JPEG work and the ITU-T Recommendation H.261

■ the goal was a coding standard for digital video and audio motion picture for digital storage media at about 1.5 Mbps; so that the video (approx. 1 hour long) can be stored on a CD, VCD (Video Compact Disk) – which is

approx. 648 MBytes large

MPEG-1 parts

■ the MPEG-1 standard only specifies the syntax of the bit stream and the semantics/operation of the decoding

process and leaves out the design of the encoder and decoder (to stimulate competition and industry product differentiation) although it provides a reference

implementation

■ MPEG-1 was designed mainly for storage on reliable storage spaces, not for transmission on noisy channels

■ the standard has 5 parts/layers:

■ 1. systems (11172-1)

■ 2. video (11172-2)

■ 3. audio (11172-3) – includes MPEG-1 Layer III (.mp3)

■ 4. conformance testing (11172-4)

■ 5. software simulation (11172-5)

MPEG-1 target applications

■ MPEG-1 was designed basically for storage on CDs,

VCDs, digital audio tapes at a rate of approx. 1.5 Mbps

■ MPEG-1 targeted an asymmetric encoding-decoding process; encoding process is more complex and

processing demanding and it is done usually once while decoding is simpler and is done more frequently

■ it should have the following features: playback, frame- based random access and editing, reverse playback, fat forward/backward play, mild robustness to uncorrectable errors.

■ the decoder must be low cost

MPEG-1 Part 1, Systems

■ MPEG-1 Systems specifies the layout and methods for multiplexing encoded audio (max. 32 streams), video (max. 16 streams) and other data streams (max. 2) in a standard bitstream while maintaining

synchronization between these different stream contents

■ MPEG-1 Systems stream was later renamed to MPEG-1 Program

Stream (because its design is identically to MPEG-2 Program Stream)

■ the Program Stream is intended for storage and transmission over relatively reliable data channels (offers limited error protection)

■ the Program Stream multiplexes Packetized Elementary Streams(PES) into a standard bitstream

■ a PES is made from packetizing an Elementary Stream (ES- a raw

audio or video bitstream output by an MPEG-1 encoder) and adding a CRC (Cyclic Redundancy Check) checksum to each packet

■ 90 KHz resolution PTS (Presentation TimeStamp) and DTS (Decoding TimeStamp) values help synchronize I-,P- and B-frames in the

Program Stream

MPEG-1 Program Stream

MPEG-1 Part 2, Video – codec design

MPEG-1 source encoder implementation

MPEG-1 input source

■ MPEG-1 process only progressive analog video (not interlaced)

■ the input format for MPEG-1 video is SIF (Source Input Format): a YCbCr 4:2:0 subsampled 352x240 resolution for NTSC, 30 fps, or 352x288 resolution for PAL, 25 fps, format

■ picture format:

■ x – luminance component, o – chrominance component

MPEG-1 types of frames

■ I-frame - intra-coded (key) frames; frames that are coded independently of other frames similar to JPEG; allows random access and editing to video streams

■ P-frame – (forward-) predicted frames; inter-frames that are coded as the difference between the current frame and the previous (I- or P-frame); the P-frame can have intra-coded macroblocks and

forward-predicted macroblocks; for each forward-predicted macroblock it is coded the prediction error (difference) and 1 motion vector

■ B-frame – bidirectional predicted-frames or backward-predicted

frames; achieves the best compression; are coded as the difference between the current frame and the I- or P- frame preceding it and the I- or P-frame after it; the B-frame can have intra-coded,

forward-predicted and backward-predicted macroblocks; for each backward-predicted macroblock it is coded the prediction error (average difference) and 2 motion vectors

■ D-frame – DC-frames; only the DC coefficient of each macroblock is coded; are used for previewing a video

Bidirectional motion compensation prediction (B-frames)

■ for motion estimation only the luminance component is compared

■ better prediction can be provided if both the past and the future frames are used

Motion compensation with half-pixel accuracy

■ often, a macroblock moves to a position that is not on the pixel grid, but between pixels

■ this is why MPEG-1 has half-pixel accuracy in motion estimation (the half-pixel value is computed using bilinear interpolation)

GOP (Group of pictures)

■ each video sequence is divided into GOPs

■ there are 4 types of pictures: I-frame, P-frame, B- frame, D-frame

■ DC pictures (D-pictures) are low-resolution pictures obtained by decoding only the DC coefficient of the discrete cosine transform (DCT) coefficients of each macroblock.

Slices, macroblocks, blocks

■ an MPEG-1 picture is made from slices

■ slice – continuous sequence of macroblocks in a raster scan order (from left to right and top to bottom)

■ macroblock – a 16x16 block of luminance samples, one 8x8 Cb block and 8x8 Cr block; a coded macroblock

contains (frame) prediction error and one or two motion vectors

■ block – a matrix of Y/Cb/Cr samples (usually 16x16 or 8x8)

Macroblock encoding

■ for each macroblock there is a quantization scale

(between 1 and 31) which is multiplied by a quantization weighting matrix and so results the quantization matrix for the macroblock

■ 2 types of intracoded macroblock for I-frames:

■ intra-d – uses the current (of the previous macroblock) quantization scale

■ intra-q – defines a new quantization scale; the macroblock header specifies a 5-bit quantizer scale factor

■ 8 types of macroblocks for P-frames: intra-d, intra-q, pred-m, pred-c, pred-mc, pred-cq, pred-mcq, skipped

■ 12 types of macroblocks for B-frames: intra-d, intra-q, pred- i, pred-ic, pred-b, pred-bc, pred-f, pred-fc, pred-icq, pred-fcq, pred- bcq, skipped

Macroblock types in P-frames

■ intra-d and intra-q : the same as used in I-frames

■ pred-m : the macroblock is forward-predictive encoded (difference from the previous frame) using a forward motion vector

■ pred-c : the macroblock is encoded using a coded pattern; a 6-bit coded block pattern is transmitted as a variable-length code and this tells the decoder which of the 6 blocks in the macroblock are coded (1) and which are not coded (0)

■ pred-mc : the macroblock is forward-predictive encoded using a forward motion vector and also a 6-bit coded pattern is included

■ pred-cq : a pred-c macroblock with a new quantization scale

■ pred-mcq : a forward-predictive macroblock encoded using a coded pattern with a new quantization scale

■ skipped : they have a zero motion vector and no code; the decoder copies the corresponding macroblock from the previous frame into the current frame

Macroblock encoding in P-frames

■ the macroblock encoding process in P-frames chooses the type of a macroblock using an algorithm like this:

Macroblock types in B-frames

■ intra-d, intra-q : the same as used for I-frames

■ pred-i : bidirectionally-predictive encoded macroblock with forward motion vector and backward motion vector

■ pred-ic : a pred-c macroblock encoded using a 6-bit coded pattern

■ pred-b : backward-predictive encoded macroblock with backward motion vector

■ pred-bc : a pred-b macroblock encoded using a 6-bit coded pattern

■ pred-f : forward-predictive encoded macroblock with forward motion vector

■ pred-fc : a pred-b macroblock encoded using a 6-bit coded pattern

■ pred-icq : a pred-ic macroblock with a new quantization scale

■ pred-fcq : a pred-fc macroblock with a new quantization scale

■ pred-bcq : a pred-bc macroblock with a new quantization scale

■ skipped : the same as for P-frames

Macroblock encoding in B-frames

■ the macroblock encoding process in B-frames chooses the type of a macroblock using an algorithm like this:

MPEG-1 video bitstream syntax

MPEG-1 video bitstream syntax - detail

MPEG-1 video bitstream syntax structures

■ video sequence layer header contains: the picture size

(horizontal and vertical), pel aspect ratio, picture rate, bit rate, minimum decoder buffer size, constraint parameters flag, control for loading 64-bit values for intra and nonintra quantization tables and user data

■ GOP layer header contains: the time interval from the start of the video sequence, the closed GOP flag (decoder needs frames from previous GOP or not?), broken link flag and user data

■ picture layer header contains: the temporal reference of the picture, picture type (I,P,B,D), decoder buffer initial occupancy, forward motion vector resolution and range for P- and B-frames, backward motion vector resolution and range for B-frames and user data

■ slice layer header contains: vertical position where the slice starts and the quantizer scale for this slice

■ macroblock layer header contains: optional stuffing bits,

macroblock address increment, macroblock type, quantizer scale, motion vector, coded block pattern

■ a block contains 8x8 coded DCT coefficients

MPEG-1 Layer III Audio (.mp3)

MPEG-2

Need for MPEG-2

■ MPEG-1 allowed rates of 1.5 Mbps at SIF resolution and higher resolution coding standards were needed for

direct video broadcasting and storage on DVB, DVD

■ MPEG-1 allowed encoding only of progressive scan sources, not interlaced scan sources

■ MPEG-1 provides limited error concealment for noisy channels

■ a more flexible choice of formats, resolutions and bitrates was needed

MPEG-2

■ MPEG-2 was designed mainly for storage (DVD, DVB) and

transmission on noisy channels (direct terrestrial or satellite TV broadcast)

■ MPEG-2 standards were published as ISO/IEC 13818

■ like MPEG-1, the MPEG-2 standard only specifies the syntax of the bit stream and the semantics/operation of the decoding process and

leaves out the design of the encoder and decoder (to stimulate

competition and industry product differentiation) although it provides a reference implementation

■ developed between 1991-1993

■ parts of MPEG-2 reached International Standard in 1994, 1996, 1997, 1999

■ MPEG-3 was originally intended for HDTV at higher bitrates, but was merged with MPEG-2

MPEG-2 parts

■ part 1, Systems : synchronization and multiplexing of audio and video

■ part 2, video

■ part 3, audio

■ part 4, testing compliance

■ part 5, software simulation

■ part 6, extensions for Digital Storage Media Command and Control (DSM-CC)

■ part 7, Advanced Audio Coding (AAC)

■ part 9, extensions for real time interfaces

■ part 10, conformance extensions for DSM-CC

■ part 11, Intellectual Property Management and Protection [ part 8 withdrawn due to lack of industry interest ]

MPEG-2 target applications

■ coding high-quality video at 4-15 Mbps for video on demand (VOD), standard definition (SD) and high-

definition (HD) digital TV broadcasting and for storing video on digital storage media like the DVD

■ MPEG-2 should have scalable coding and should include error resilience techniques

■ MPEG-2 should provide good NTSC quality video at 4-6 Mbps and transparent NTSC quality video at 8-10 Mbps

■ MPEG-2 should provide random access to frames

■ MPEG-2 should be compatible with MPEG-1 (an MPEG-2 decoder should be able to decode an MPEG-1 bitstream)

■ low cost decoders

MPEG-2 Systems

■ MPEG-2 Systems offers 2 types of multiplexation bitstreams:

■ Program Stream: it consists of a sequence of PESs, similar and compatible to MPEG-1 Program (System) Stream, but containing

additional features; MPEG-2 PS is a superset of MPEG-1 PS; it is suited for error-free transmission environments and has long and variable length packets (typically 1-2KB, but can also be 64KB) for coding

efficiency; it has features not present in MPEG-1 PS like: scrambling of data, assigning different priorities to packets, alignment of elementary stream packets, copyright indication, fast forward and fast reverse indication.

■ Transport Stream: designed for transmission through noisy channels;

has a small fixed size packet of 188 bytes; it is suited for cable/satellite TV broadcasting, ATM networks; allows synchronous multiplexing of programs with independent time bases, fast access to the desired program for channel hoping

■ PES (Packetized Elementary Stream) – is the central structure used in both Program and Transport Streams; results from packetizing cntinuous streams of compressed audio or video

MPEG-2 Systems multiplexation

(digital storage media)

Packetized Elementary Streams (PES)

Program Stream structure (simplified)

Transport Stream Structure (simplified)

MPEG-2 Profiles and Levels

■ MPEG-2 is designed o cover a wide range of applications, but not all features are needed by all applications

■ MPEG-2 groups application features into 7 profiles and profiles have different levels

■ simple profile – for low-delay video conferencing applications using only I- and P- frames

■ main profile – most used, high quality digital video apps.

■ SNR (signal to noise ratio) scalable – supports multiple grades of video quality

■ spatially scalable - supports multiple grades of resolution

■ high – supports multiple grades of quality, resolution and chroma formats

■ 4:2:2

■ multiview

MPEG-2 Profiles and Levels (2)

■ there are 4 levels for each profile:

■ low (for SIF pictures)

■ main (for ITU-R BT 601 resolution pictures)

■ high-1440 (for European HDTV resolution pictures)

■ high (for North America HDTV resolution pictures)

MPEG-2 Profiles and Levels (3)

Scalable coding

■ scalable coding – means coding the audio-video stream into a base layer and some enhancement layers, so that when the base layer is decoded basic quality is achieved, but if the transmission channel allows it, decoding

enhancement layers brings additional quality to the decoded stream

■ there are 4 types of scalability

■ SNR scalability

■ spatial scalability

■ temporal scalability

■ hybrid (combination of the above)

SNR scalability

Spatial scalability

Encoding of interlaced video

■ MPEG-2 allows encoding of interlaced video and a frame can be intracoded or intercoded as a picture or as a field of picture

■ motion estimation/compensation can be between frames or between fields