COMP 249 Advanced Distributed Systems
Multimedia Networking
The Video Data Type
Coding & Compression Basics
Kevin Jeffay
Department of Computer Science
University of North Carolina at Chapel Hill
jeffay@[Link]
September 7, 1999
[Link]
The Video Data Type
Outline
! What is video?
» Video components
» Representations of video signals
» Color spaces
! Digital Video
» Coding
! Compression basics
» Simple compression
» Interpolation-based techniques
» Predictive techniques
» Transforms
» Statistical techniques
2
Video Basics
The components of video
R-value
G-value
B-value
! Video deals with absorbed and projected light
» Cameras absorb light and monitors project light
! The primary colors in this domain are:
» red, green, and blue
Video Basics
The components of video transmission
! Video is a multi-dimensional signal
R-component G-component B-component
x
y
time
4
Video Basics
Video as a 1-dimensional signal
! Representation of a 2-dimensional image
(R, G, B)11, (R, G, B)12, (R, G, B)13, ..., (R, G, B)row, col
! Representation of motion (3-dimensional images)
33 ms NTSC (30 fps)
40 ms PAL (25 fps)
Frame i Frame i+1
5
Video Basics
Resolution
! Television broadcast
standards
» NTSC — 525 lines Videophone
» PAL — 625 lines (128x112)
! Computer graphics QCIF (176x144)
standards
DVI (256x240)
» VGA — 640x480
» SVGA — 1024x768 H.261 CIF (352x288)
! Multimedia standards
» CIF — 352x288 NTSC (440x480)
» QCIF — 176x144
! Digital video standards Image sizes
(in picture elements)
» CCIR 601 — 720x480
» HDTV — 1440x1152
6
Video Basics
Color spaces
! RGB is not widely used for transmitting a signal between
capture and display devices
» It’s difficult to manage 3 separate inputs & outputs
(and requires too much bandwidth)
! Composite formats are used instead
» Luminance (“Y”) — the brightness of the monochrome signal
» Chrominance — the coloring information
» Chrominance is typically represented by two “color difference”
signals:
❖ “U” and “V” (“hue and tint”) or
❖ “I” and “Q” (“saturation” and “color”)
Video Basics
Color spaces
U = 0 Plane
R R
Y=1
White V=0
Plane
R=G=B
(gray values) G G
B B
! NTSC video ! PAL video/Digital recorders
» Y = 0.30R + 0.59G + 0.11B » Y = 0.3R + 0.6G + 0.1B
» I = 0.60R – 0.28G – 0.32B » U = (B – Y) x 0.493
» Q = 0.21R – 0.52G + 0.31B » V = (R – Y) x 0.877
8
Video Basics
Digital video
! Sample an analog representation of video (RGB or
YUV) & quantize
» Two dimensions of video are already discretized
» Sample in the horizontal direction according to the
resolution of the media
! 8-bits per component per sample is common
» 24 bits per picture element (pixel)
! Storage/transmission requirements
» NTSC — 440 x 480 x 30 x 24 = 152x106 bits/sec
(19 MB/s or 24 bits/pixel (bpp))
9
The Video Data Type
Outline
! What is video?
» Video components
» Representations of video signals
» Color spaces
! Digital Video
» Coding
! Compression basics
» Simple compression
» Interpolation-based techniques
» Predictive techniques
» Transforms
» Statistical techniques
10
Digital Video
Compression Techniques
! Do we really need every “bit” of a video stream?
» Not if redundancy exists
» Not if we can’t perceive the effect of eliminating the bit
! Eliminating redundancy
» Spatial redundancy
» Temporal redundancy
! Eliminating imperceptible detail
» Coding
» Domain transformation
11
Digital Video
Compression Techniques
Simple Interpolative Predictive Transform Statistical
Truncation
Truncation DPCM
DPCM Discrete
Discrete Huffman
Huffman&&
CLUT
CLUT Sub-sampling
Sub-sampling Motion
Motion Cosine
Cosine Arithmetic
Arithmetic
Run-length
Run-length Compensation
Compensation Transform
Transform coding
coding
Fixed Adaptive
Video
Input Video
Color
Color
Video
Compression Bit
Bit
Components
Components Compression Assignment
Algorithm Assignment
Algorithm
Compressed
(PCM Signals)
Bit-Stream
Adapted from Buford p.147 12
Video Compression
Issues
! Bandwidth requirements of resulting stream
» Bits per pixel (bpp)
! Image quality
! Compression/decompression speed
» Latency
» Cost
» Symmetry
! Robustness
» Tolerance of errors and loss
! Application requirements
» Live video
» Stored video
13
Simple Image Compression
Truncation
! Reducing the number of bits per pixel
» Throw away the least significant bits of each sample value
! Example
» Go from RGB at 8 bits/component sample ([Link]) to 5 bits
([Link])
❖ Go from 24 bpp to 15 bpp
❖ This gives “acceptable results”
» Go from YUV at 8 bits/component sample [Link] (16 bpp)
! Advantage — simple!
14
Simple Compression Schemes
Color-table lookup (CLUT)
! Quantize coarser in the color 0 1 2 3 4 5 6 7 ...
domain 0
1
» Pixel values represent indices
into a color table 2
3
» Tables can be optimized for
individual images 4
5
6
! Entries in color table stored at
7
“full resolution” (e.g. 24 bits)
...
! Example:
» 8-bit indices (256 colors) gives
(440 x 480) x 8 + (24 x 256) = 1.7x106 bits/sec
15
Simple Compression Schemes
Run-length encoding
17 23 54 54 54 54 54 54 54 22 11
RLE
17 23 (54, 7) 22 11
! Replace sequences of pixel components with identical
values with a pair (value, count)
! Works well for computer-generated images, cartoons.
works less well for natural video
! Also works well with CLUT encoded images
(i.e., multiple techniques may be effectively combined)
16
Interpolative Compression Schemes
Color sub-sampling
! Do not acquire chrominance component values at all
sampling points
» Humans have poor acuity for color changes
» UV and IQ components were defined with this in mind
! Example: Color representation in digital tape recorders
» Subsampling by a factor of 4 horizontally is performed
Y component U component V component
17
Interpolative Compression Schemes
Color sub-sampling
! Subsampling by a factor of 4 horizontally & vertically
Y component U component V component
! Interpolating between samples provides “excellent” results
» Chrominance still sampled at 8 bpp
18
Interpolative Compression Schemes
Color sub-sampling
! Intermediate pixels either take on the value of nearest
sampling point or their value is computed by interpolation
(0,0) (1,0)
! Bi-linear interpolation: ...
U(1,
U(1,1)
1)==U(0,0)x0.75
U(0,0)x0.75++U(1,0)x0.25
U(1,0)x0.25++
U(0,1)x0.75
U(0,1)x0.75++U(1,1)x0.25
U(1,1)x0.25 (0,1) (1,1)
...
...
...
Sub-sampled
U or V component
19
Interpolative Compression Schemes
Color sub-sampling
Y component U component V component
! Storage/transmission requirements reduction:
» Within a 4x4 pixel block:
(8 bpp luminance)x16 samples + (8 bpp chrominance)x2
bpp =
16
=9
» A 62.5% reduction overall
20
Predictive Compression Schemes
Exploiting spatial & temporal redundancy
! Adjacent pixels are frequently similar
» Do pixel-by-pixel DPCM compression
❖ Leads to smearing of high-contrast edges
» ADPCM — a little better, a little worse
❖ Introduces “edge quantization” noise
! Motion Estimation — If the future is the similar to the
past, encode only the difference between frames
» This assumes we can store a previous frame to compare with
a future one
21
Transform-Based Compression
Exploiting redundancy in other domains
! A simple linear transformation
2 x 2 array of pixels 1-D array of differences
A B
A B–A C–A D–A
C D
» Encode differences with less precision
! Storage savings
» Original array: 4 pixels x 8 bpp = 32 bits
» Transformed array: 8 bits + (3 pixels x 4 bpp) = 20 bits
22
Transform-Based Compression
The Discrete Cosine Transform (DCT)
! A transformation into the frequency domain
! Example: 8 adjacent pixel values (e.g., luminance)
255 127
128 0
0 -128
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
Sample values Level-shifted values
! What is the most compact way to represent this
signal?
23
Transform-Based Compression
The Discrete Cosine Transform (DCT)
! Represent the signal in terms of a set of cosine basis
functions
1.0 1.0 1.0 1.0
0 0 0 0
-1.0 -1.0 -1.0 -1.0
1.0 1.0 1.0 1.0
0 0 0 0
-1.0 -1.0 -1.0 -1.0
24
Transform-Based Compression
The Discrete Cosine Transform (DCT)
1.0
1.0
0.5
0
0.0
-0.5 -1.0
-1.0 Sampled 2.5 Hz
cosine wave
! The basis functions derive from sampling cosine
functions of increasing frequency
» From 0-3.5 Hz
» Basis functions sampled at 8 discrete points
25
The Discrete Cosine Transform
Represent input as a sum of scaled basis functions
Level-shifted values DCT coefficients
Σ
127 7 150
0 = 0 X i
i =0
-128 -150
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 i
0 1.0 1 1.0 2 1.0 3 1.0
0 0 0 0
-1.0 -1.0 -1.0 -1.0
4 1.0 5 1.0 6 1.0 7 1.0
0 0 0 0
-1.0 -1.0 -1.0 -1.0
26
Transform-Based Compression
The Discrete Cosine Transform (DCT)
! The 1-dimensional transform:
7
C(µ)
F(µ) =
2 Σ
x=1
f(x) cos (2x+1)µπ
16
» F(µ) is the DCT coefficient for µ = 0..7
» f(x) is the xth input sample fot x = 0..7
» C (µ) is a constant (equal to 2-0.5 if µ = 0 and 1 otherwise)
! The 2-dimensional (spatial) transform:
7 7
C(µ)C(ν)
F(µ,ν) = ΣΣ
2 2 y=1 x=1
f(x,y) cos (2x+1)µπ cos (2y+1)νπ
16 16
27
Transform-Based Compression
The Discrete Cosine Transform (DCT)
! DCT coefficients encode the spatial frequency of the input
signal
» DC coefficient — zero spatial frequency (the “average”
sample value)
» AC coefficients — higher spatial frequencies
“DC coefficient”
“AC coefficients”
150
-150
! Claim: Higher frequency coefficients will be zero and can
be ignored
28
Transform-Based Compression
The two-dimensional DCT
! Apply the DCT in x and y dimensions simultaneously to
8x8 pixel blocks
» Code coefficients individually
with fewer bits
172 -18 15 -8 23 -9 -14 19
21 -34 24 -8 -10 11 14 7
-9 -8 -4 6 -5 4 3 -1
Video Frame -10 6 -5 4 -4 4 2 1
-8 -2 -3 5 -3 3 4 6
4 -2 -4 6 -4 4 2 -1
4 -3 -4 5 6 3 1 1
0 -8 -4 3 2 1 4 0
DCT Coefficients
29
Statistical Compression
Huffman coding
! Exploit the fact that not all sample values are
equally likely
» Samples values are non-uniformly distributed
» Encode “common” values with fewer bits and less
common values with more bits
! Process each image to determine the statistical
distribution of sample values
» Generate a codebook — a table used by the decoder to
interpret variable length codes
» Codebook becomes part of the compressed image
30
Statistical Compression
Huffman coding
P(ACBD)
P(ACBD)==11
Symbol Probability Code
A 0.75 1
1 0
B 0.125 01 P(BCD)
P(BCD) == 0.25
0.25
C 0.0625 001
D 0.0625 000
1 0
P(CD)
P(CD) == 0.125
0.125
1 0
P(A)
P(A) == 0.75
0.75 P(B)
P(B) == 0.125
0.125 P(C)
P(C) == 0.062
0.062 P(D)
P(D) == 0.062
0.062
! Order all possible sample values in a binary tree by
combining the least likely samples into a sub-tree
! Label the branches of the tree with 1’s and 0’s
» Huffman code is the sequence of 1’s and 0’s on the path
from the root to the leaf node for the symbol 31
