Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Th size
The
i off typical
t i l still
till image
i
(1200x1600)
(1200 1600)
1200 1600 3byte 5760000byte
5,760 Kbyte 5.76 Mbyte
The size of two hours standard television (720x480)
movies
fframe
pixels
i l
b t
bytes
(760 480)
3
31,104,000bytes / sec
pixel
frame
sec
sec
bytes
31,104,000
(60 60)
2hours 2.24 1011 bytes
y
sec
h
hour
224GByte.
30
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Data,
D
t IInformation,
f
ti
and
dR
Redundancy
d d
Information
Data
D t is
i usedd to represent information
i f
i
Redundancy in data representation of an
i f
information
ti provides
id no relevant
l
t information
i f
ti or
repeats a stated information
Let n1,
n1 and n2 are data represents the same
information. Then, the relative data redundancy R
of the n1 is defined as
R = 1 1/C where C = n1/n2
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Redundancy in Digital Images
Coding redundancy
usually appear as results of the uniform
representation of each pixel
Spatial/Temopral redundancy
because the adjacent pixels tend to have
similarity in practical.
Irrelevant Information
Image contain information which are ignored
by the human visual system.
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Coding Redundancy
19922008 R. C. Gonzalez & R. E. Woods
Spatial Redundancy
Irrelevant Information
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Coding Redundancy
Assume the discrete random variable for rk in the interval
[0,1] that represent the ggrayy levels. Each rk occurs with
probability pk
If the number of bits used to represent each value of rk by
l(rk) then
L 1
Lavg l (rk ) p(rk )
k 0
The average code bits assigned to the gray level values.
The length of the code should be inverse proportional to
it probability
its
b bilit (occurrence).
(
)
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Examples of variable length encoding
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Spatial/Temopral Redundancy
Internal Correlation between the pixel result from
Respective Autocorrelation
Structural Relationship
Geometric Relation shipp
The value of a pixel can be reasonably predicted
from the values of its neighbors.
g
To reduce the inter-pixel redundancies in an image
the 2D array is transformed (mapped) into more
efficient format (Frequency Domain etc.)
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Irrelevant information and Psycho-Visual
Redundancy
The brightness of a region depend on other factors
that the light reflection
The perceived intensity of the eye is limited an non
linear
Certain information has less relative importance
p
that
other information in normal visual processing
g
g
In ggeneral, observer searches for distinguishing
features such as edges and textural regions.
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Measuring Information
A random even E that occurs with
probability P(E) is said to contain I(E)
information where I(E) is defined as
I(E) = log(1/P(E)) = -log(P(E))
log(P(E))
P(E) = 1 contain no information
P(E) = requires one bit of information.
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Measuring Information
For a source of events a0, a1,a2, .., ak with
associated probability P(a0),
) P(a1),
) P(a2),
) .., P(ak).
)
The average information per source (entropy) is
k
H P (a j ) log(
l ( P (a j )
j 0
For image, we use the normalized histogram to generate the
source probability,
b bili which
hi h leas
l
to the
h entropy
L 1
~
H pr (ri ) log(
og( pr (ri ))
i 0
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Fidelity Criteria
Objective Fidelity Criteria
The information loss can be expressed as a function of the
encoded and decoded images.
For image
g I (x,y)
y and its decoded approximation I(x,y)
y
For any value of x and y, the error e(x,y) could be defined as
e( x, y ) I ' ( x, y ) I ( x, y )
For the entire Image
M 1 N 1
I ' ( x, y) I ( x, y)
x 0 y 0
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Fidelity Criteria
The mean-square-error, erms is
erms
M 1 N 1
I ' ( x, y) I ( x, y)
x 0 y 0
The mean-square-error signal-to-noise ratio SNRmsis
M 1 N 1
SNRms
2
I
'
(
x
,
y
)
x 0 y 0
M 1 N 1
I
'
(
x
,
y
)
I
(
x
,
y
)
x 0 y 0
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Th approximations
Three
i i
off the
h same image
i
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Huffman coding is an entropy
encoding algorithm used for
lossless data compression. The
t
term
refers
f to
t the
th use off a variablei bl
length code table for encoding a
source symbol (such as a character
in a file) where the variable-length
code table has been derived in a
particular way based on the
estimated probability of occurrence
for each possible value of the
source symbol.
b l
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Huffman
H
ff
coding
di
Assignment procedure
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Arithmetic coding is a form of
variable-length entropy encoding.
A string is converted to arithmetic
encoding,
di usually
ll characters
h
t are
stored with fewer bits
Arithmetic coding encodes the
entire message into a single
number, a fraction n where (0.0
n < 1.0).
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Compression Algorithms
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Symbol compression
This approaches determine a set of
symbols that constitute the image,
and take advantage of their multiple
appearance. It convert each symbol
into token, generate a token table
and represent
p
the compressed
p
image
g
as a list of tokens.
This approach is good for document
images.
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
DFT and
d DCT
The periodicity implicit in the 1-D DFT
and DCT. The DCT provide better
continuity that the general DFT.
DFT
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
B k Si
Bock
Size vs. R
Reconstruction
t ti E
Error
The DCT provide the least error at almost
anyy sub-image
g size.
The error takes its minimum at sub-images
of sizes between 16 and 32.
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Lossless Predictive coding
The encoder expects a discrete samples
of a signal f(n).
1 A predictor is applied and its
1.
output is rounded to the nearest
integer. f (n)
2 The error is estimated as
2.
e(n) f (n) f (n)
3. The compressed stream consist of
first sample
p and the errors,,
encoded using variable length
coding
19922008 R. C. Gonzalez & R. E. Woods
The decoder uses the predictor and the
error stream to reconstructs the
original signal f(n).
1. The predictor is initialized using
the first sample.
2. The received error is added to
predictor result.
f (n) f (n) e(n)
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Lossless Predictive coding
Linear predictors usually have the
form:
m
f (n) round ai f (n i )
i 0
Original Image (view of the earth).
The prediction error and its histogram.
1. The error is small in uniform
regions
2. Large close to edges and sharp
changes in pixel intensities
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Lossy Predictive coding
The encoder expects a discrete
samples of a signal f(n).
1 A predictor is applied and its
1.
output is rounded to the nearest
integer, f (n)
2 The error is mapped into limited
2.
rage of values (quantized) e(n)
3. The compressed stream consist
of first sample
p and the mapped
pp
errors, encoded using variable
length coding
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Lossy Predictive coding
The decoder uses error stream to
reconstructs an approximation of the
original signal, f (n)
1. The predictor is initialized using the
first sample.
2 The
2.
Th received
i d error is
i added
dd d to
t
predictor result.
f (n) e( n) f (n)
e(n)
e( n ) 0
otherwise
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Prediction Error
The following images show the
prediction error of the predictor
f ( x, y ) 0.97 f ( x, y 1)
f ( x, y ) 0.5 f ( x, y 1) 0.5 f ( x 1, y )
f ( x, y ) 0.75 f ( x, y 1) 0.75 f ( x 1, y ) 0.5 f ( x 1, y 1)
0.97 f ( x, y 1) h v
f ( x, y )
0.97 f ( x 1, y ) otherwise
h | f ( x 1, y ) f ( x 1, y 1)
v | f ( x, y 1) f ( x 1, y 1)
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
Optimal Predictors
What are the parameters of a linear predictor that minimize error
E{e (n)} E f (n) f (n)
2
While taking into account
f (n) e(n) f (n) e(n) f (n) f (n)
Using the definition of linear predictor
2
m
2
E{e (n)} E f (n) i f (n 1)
i 1
We assume that f(n) has a mean zero and variance 2
R 1r
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
And R-1 is the mxn autocorrelation matrix
E f (n 1) f (n 1) E f (n 1) f (n 2)
E f (n 2) f (n 1) E f (n 2) f (n 2)
R
E f (n m) f (n 1) E f (n m) f (n 1)
E f (n) f (n 1)
E f (n 1) f (n m)
1
a
m
19922008 R. C. Gonzalez & R. E. Woods
E f (n 1) f (n m)
... E f (n 2) f (n m)
... E f (n m) f (n 1)
...
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
Digital Image Processing, 3rd ed.
Gonzalez & Woods
www.ImageProcessingPlace.com
Ch t 8
Chapter
Image Compression
19922008 R. C. Gonzalez & R. E. Woods
