Transcript L10 draft - Princeton University

10/19/06
ELE 488 Fall 2006
Image Processing and Transmission
(10-19-06)
Image Compression
Review of Basics
Huffman coding
run length coding
Quantization
independent samples
uniform and optimum
correlated samples
vector quantization
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Why Compression?
• Storage and transmission
– Large size of uncompressed multimedia data
– High bandwidth to send uncompressed video in real time.
• Slow access to storage devices does not allow real time play
back of uncompressed content
– 1 x CD-ROM transfer rate ~ 150 kB/s
– 320 x 240 x 24 fps video ~ 5.5MB/s
=> 36 seconds to transfer 1-sec uncompressed video
from CD
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Example: Storing An Encyclopedia
– 500,000 pages of text (2kB/page)
3,000 color pictures (64048024bits)
~ 1GB => 2:1
~ 3GB => 15:1
– 500 maps (64048016bits=0.6MB/map)
~ 0.3GB => 10:1
– 60 minutes of stereo sound (176kB/s)
~ 0.6GB => 6:1
– 30 animations with average 2 minutes long
(64032016bits16frames/s=6.5MB/s)
~ 23.4GB => 50:1
– 50 digitized movies with average 1 minute long
(64048024bits30frames/s = 27.6MB/s)
~ 82.8GB => 50:1
Require a total of 111.1GB storage capacity without compression
Reduce to 2.96GB with compression
ELE 488 F06
From Ken Lam’s DCT talk 2001 (HK Polytech
Sampling and Quantization
• Signal is sampled
• Each sample quantized to B bits (uniform steps)
 B bit per sample
• How many samples?
sampler +
– Nyquist
encoder
quantizer
– In practice?
image capture
• B=?
– Signal to noise ratio: 6 dB per bit
– Meaning in practice?
• CD music: 44100x2x16 = 1.41 Mb/sec – raw data rate
• Observations:
– Not all quantization levels occur equally likely
• Should B bits be used for the frequently occurred samples
as well as less likely occurred samples?
– Why uniform quantization?
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Variable Length Codes
• Quantized PCM values may not occur with equal probability
– Is it best to use same # of bits for each sample?
• Example: 4 levels with probabilities:
P(level 1)=0.125, P(level 2)=0.5, P(level 3)=0.25, P(level 4)=0.125
– Need 2 bits to code each symbol IF using same # bits
– If use less bits for levels with high probability and more bits
for low probability (Variable Length Codes – VLC)
• level 2 => [0], level 3 => [10], level 1 => [110],
and level 4 => [111]
• Average code length is i pi li =1.75 bits < 2 bits
• Compression ration = 2/1.75
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001/2004)
Entropy Coding
• Use fewer bits for commonly occurred values
• Minimum # of bits for each level determined by “entropy of source”
– Entropy is a measure of information of a source
• Definition: H = i pi log2 (1 / pi) bits
(entropy of previous example is 1.75)
• Can represent a source perfectly with avg. H+ bits per
sample (Shannon Lossless Coding Theorem)
– “Compressability” depends on the sources
• Need to design a codebook to decode the encoded stream
efficiently and without ambiguity
• Huffman Coding – assigns ~ log2 (1/pi) bits for the ith symbol
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Huffman Coding
000
00
001
10
010
010
S2
0.15
011
011
S3
0.14
100
1100
S4
0.125
101
1101
S5
0.0625 0
0.0625 1
110
1110
S6
1111
0.125
111
S7
0.0625 0
0.0625 1
PCM
Huffman
(trace from
root)
ELE 488 F06
S0
S1
0.25
0
0.54
0.21
0
1
0
0
1
1.0
0.29
0.46
0
1
1
0.25
1
Step 1 – Arrange pi in decreasing order
Step 2 – Merge two nodes with smallest prob to a
new node and sum up prob. Arbitrarily assign 1
and 0 to each pair of merging branch
Step-3 – Repeat until only one node left
Read out codeword sequentially from root to leaf
UMCP ENEE631 Slides (created by M.Wu © 2001)
Huffman Coding: Pros & Cons
• Pro
– Simple to implement (table lookup)
– Gives best coding efficiency
• Con
– Need source statistics
– Integer code length for each symbol
 average code length usually larger than min (entropy)
• Improvement
– Code groups of symbols
– Arithmetic coding
– Lempel-Ziv coding or LZW algorithm
• “universal”, no need to estimate source statistics
• fix-length codeword for variable-length source symbols
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Run-Length Coding
• How to efficiently encode a string of binary symbols (2 levels)?
“ w w w w w w w b b w w w b w b w w w w w w b b b . . . .”
• Run-length coding (RLC)
– Code lengths of runs of w and of b
good if often getting frequent large runs of “0” and sparse “1”
– For the example (7w) (1b) (3w) (1b) (1w) (1b) (6w) (3b) . . .
– Assign fixed-length codeword to run-lengths in a range
(e.g. <7)
– Or use variable-length code (Huffman) to obtain further
improvement
• RLC also applicable to general a data sequence with many
consecutive “w” or “b”
ELE 488 F06
Facsimile
ELE 488 F06
http://home.maine.rr.com/randylinscott/fax.htm
UMCP ENEE631 Slides (created by M.Wu © 2001)
Probability Model of Run-Length Coding
• Assume w occurs independently with probability p
• Calculate prob of runs of length L. Restrict L to L=0,1, …, M
P( L = l ) = pL (1 – p) for 0  l  M –1 (geometric distribution)
P( L = M ) = pM (when having M or more “0”)
• Avg. # binary symbols per zero-run
– Savg = L (L+1) pL (1-p) + M pM = (1 – pM ) / ( 1 – p )
• Compression ratio
C = Savg / log2 (M+1) = (1 – pM ) / [( 1–p ) log2(M+1)]
• Example
– p = 0.9, M=15  Savg = 7.94, C = 1.985, H = 0.469 bpp
– Avg. run-length coding rate Bavg = 4 bit / 7.94 ~ 0.516 bpp
– Coding efficiency = H / Bavg ~ 91%
ELE 488 F06
Sampling and Quantization
• Signal is sampled
• Each sample quantized to B bits (uniform steps)
 B bit per sample
• How many samples?
sampler +
– Nyquist
encoder
quantizer
– In practice?
image capture
• B=?
– Signal to noise ratio: 6 dB per bit
– Meaning in practice?
• CD music: 44100x2x16 = 1.41 Mb/sec – raw data rate
• Observations:
– Not all quantization levels occur equally likely
• Should B bits be used for the frequently occurred samples as
well as less likely occurred samples?
– Why uniform quantization?
ELE 488 F06
Quantization
Quantizer
x↔u
correction
ELE 488 F06
Quantization
Quantizer
…
ELE 488 F06
Mean Square Error
Mean square error:
Optimization problem:
Solution gives optimum thresholds (tk) and reconstruction values (rk)
ELE 488 F06
Solution
rk conditional
mean (centroid)
ELE 488 F06
The Lloyd-Max Quantizer
Optimal mean square error quantizer:
Nonlinear equations.
Closed form solution only for simple p(x).
Resort to numerical solution in general.
ELE 488 F06
Numerical Solution of the LM Equations
Iterative algorithm:
a. Pick initial values for t (e.g. uniform grid)
b. Find r values using (1). ( numerical integration)
c. Find new t values using (2)
d. Go to line b until the t and r values converge
OR: Start with a=t1 and r1. Determine t2 using (1).
Then determine r2 using (2) …. If tL>b, repeat with
smaller r1. If tL < b, repeat with larger r1.
ELE 488 F06
Observations on the optimal quanitizer
ELE 488 F06
Example: Uniform Density
Uniform quantizer is the optimal mean square quantizer
ELE 488 F06
Uniform Density, cont.
Uniform density of interval:
ELE 488 F06
Example: Triangle
Start with uniform quantizer
Use iterative algorithm.
optimum thresholds (red)
reconstruction values (blue)
ELE 488 F06
Example: Gaussian
Start with uniform quantizer
Use iterative algorithm.
optimum thresholds (red) and
reconstruction values (blue)
ELE 488 F06
Example: Triangle 2
Start with uniform quantizer
Use iterative algorithm.
optimum thresholds (red) and
reconstruction values (blue)
ELE 488 F06
Example: Gaussian Mixture
Start with uniform quantizer
Use iterative algorithm.
optimum thresholds (red) and
reconstruction values (blue)
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Implement Nonuniform Quantizer Using Companding
u
f(.)
compressor
w
Uniform
quantizer
y
g(.)
expander
u’
• Compressor-Expander
– Uniform quantizer proceeded and followed by nonlinear operations
• Why use compandor?
– Smaller values suffer more distortion under uniform quantizer
– Nonlinearity in perceived luminance
• small difference in low luminance is more visible
– Overall companding system may approximate Lloyd-Max quantizer
ELE 488 F06
UMCP ENEE631 Slides (created by M.Wu © 2001)
Compandor
• Nonlinear transformation
– To make overall system approximate Lloyd-Max quantizer
– Without iterative process to determine parameters
ELE 488 F06
(Jain’s Fig.4.19)