Image Transformation

Image Processing:
Image Compression (2)
ƒ Image transformation represent the image as coefficients of a set of
basis functions
ƒ in the KLT case the basis functions are chosen in order to
decorrelate pixel values
ƒ they are dependent of the image and must be encoded together
Transform based compression with the coefficients !
Wavelet based compression ƒ for other global transforms (Fourrier, Walsh, Hadamard, ...), the set
Haar Transform of basis functions is fixed
Diadic Transfom ƒ the decorrelation is less performant
Compression of color images ƒ but the basis functions need not to be encoded !
Illustration of JPEG Compression

© 2004 Rolf Ingold, University of Fribourg

Walsh Hadamard Basis Function Wavelet Transforms

ƒ Walsh Hadamard ƒ Wavelet tranforms provide an alternative to more traditional Fourier

compression operates transforms
on binary basis ƒ Wavelet transforms convert a signal into a series of wavelets, i.e
functions ƒ using basis functions that are bounded in frequency as well as in
space domains
ƒ There exist an infinity of wavelets transforms
ƒ the first known discrete wavelets transfom was invented by Alfred
Haar in 1909
ƒ in the late 1980s and early 1990s, Stéphane Mallat made some
fundamental contributions to the development of wavelet theory
ƒ orthogonal wavelets with compact support were introduced by
Ingrid Daubechies in 1988
ƒ since then, many other wavelets have been invented

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

Continuous Wavelet Transforms Haar Wavelets

ƒ Mathematicaly, the continuous wavelet transform (CWT) is defined by ƒ The Haar wavelet can also be described as a step function
+∞
1 1 ⎛t − τ⎞
γ ( τ, σ) = x(t ) ∫
σ
ψ σ, τ (t ) dt ψ σ, τ (t ) = ψ⎜
σ ⎝ σ ⎠
⎟ ⎧ 1 0 ≤ x < 12
⎪
−∞ ψ ( x) = ⎨− 1 12 ≤ x < 1
where τ represents translation and σ a scale factor of the mother ⎪ 0 otherwise
wavelet ψ(τ) ⎩
ƒ Haar transforms can be understood as a combination of Haar wavelets
ƒ Then, the original function can be reconstructed using the inverse with different scale and shift parameters
transform
+∞ +∞ +∞ 2
1 ⎛ t − τ ⎞ dσ Ψ (ζ )
x (t ) = ∫∫
Cψ − ∞ − ∞
γ ( τ, σ)ψ⎜
⎝ σ ⎠ σ
⎟ dτ 2 Cψ = ∫
−∞
ζ
dζ

where Ψ is the Fourier transform of ψ

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

Haar Transform Computation of the Haar Transform

ƒ The Haar transform can be expressed as a combination of the ƒ The Haar Transform can be computed stepwise as follows
following basic functions ƒ separate odd samples and even samples
ƒ one step function ƒ compute their sum (mean value) and (half of) their differences
⎧1 0 ≤ t < 1 sn −1,l = ( sn, 2l + sn , 2l +1 ) / 2
φ(t ) = ⎨
⎩0 otherwise
d n −1,l = ( sn, 2l +1 − sn , 2l ) / 2
ƒ and several Haar wavelets ƒ at the end, keep the last sum and all differences
ψ ij (t ) = ψ ( 2 j t − i ) ƒ Example : the Haar transform of [8,4,9,7] is [7,-1,2,1]

[ 8 4 9 7 ]
[ 6 8 ] [ 2 1 ]
[ 7 ] [ -1 ]

ƒ The Haar transform of N samples can be computed in O(N) time !

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg
Haar Transform in 2D space Illustration of the Haar Transform

ƒ The standard Haar ƒ The wavelet transform has many zero or near zero values !
decomposition in 2D space is
obtained by computing
ƒ a 1D Haar transform on each
row
ƒ then a 1D Haar transform on
each column
(or conversely)

ƒ The corresponding basis

functions are illustrated on the
right side

original Lena picture and

its Haar transform (with adjusted brightness (+128) and contrast (×8))

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

Wavelet Based Compression Illustration of Haar Based Compression

ƒ Simple entropy coding of Haar wavelets can be used for loss-free ƒ Original Lena picture and its result of Haar based compression
compression removing 7/8 and 15/16 of coefficients
ƒ Lossy compression is obtained by
ƒ ordering coefficients according to their power
ƒ removing less significant coefficients
ƒ quantizing the other coefficients
ƒ applying entropy coding

compression 1:7.7 compression 1:14

PSNR=31.51dB PSNR=28.34dB

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

Dyadic Wavelet Transform Illustration of Dyadic Wavelet Transform

ƒ A more efficient representation ƒ The resulting transform contains multi-resolution square subimages
for entropy coding can be
achieved by using a slightly
modified 2D Haar Transform
ƒ alternation between rows and
columns are applied within
each decomposition steps

ƒ The resulting basis functions are

illustrated on the right

original Lena picture and

its Haar transform (with adjusted brightness (+128) and contrast (×8))

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

Encoding of Dyadic Wavelet Coefficients Color image compression

ƒ Optimal coefficient encoding uses the ƒ Color image compression could be done bank-wise
quadtree structure of multi-resolution ƒ not very efficient because it ignores color correlation
subimages ƒ KLT transforms in RGB space can be used to decorrelate color
ƒ Various encoding schemes have been information
proposed ƒ Other methods work in "physiological" color spaces :
ƒ EZW (embedded zerotree wavelet) ƒ using different sampling
ƒ SPIHT (set partitioning in ƒ using different quantization steps
hierchical trees)
for luminance and chrominance
ƒ WDR (wavelet difference
reduction)
ƒ ...

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg
Schema of JPEG compression DCT basis functions

ƒ The discrete cosine transform (DCT) is a Fourier-related transform

using only real numbers
ƒ The Discrete Cosine Transform is defined as
N −1 N −1
⎡ (2 x + 1)uπ ⎤ ⎡ (2 y + 1)vπ ⎤
F (u , v) = α(u )a (v) ∑∑
x = 0 y =0
f ( x, y ) cos ⎢
⎣ 2 N ⎥⎦
cos ⎢
⎣ 2N ⎥⎦

⎧⎪ 1
u=0
with α (u ) = ⎨
N
⎪⎩ 2
N
u>0

ƒ The DCT is separable and can be computed using a fast algorithm

ƒ The reverse function

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

DCT basis functions Quantization tables in JPEG

ƒ Quantization tables are used to approximate

ƒ different quantization is performed on luminance and chrominance

------------------------------ ------------------------------
16 11 10 16 24 40 51 61 17 18 24 47 99 99 99 99
12 12 14 19 26 58 60 55 18 21 26 66 99 99 99 99
14 13 16 24 40 57 69 56 24 26 56 99 99 99 99 99
14 17 22 29 51 87 80 62 47 66 99 99 99 99 99 99
18 22 37 56 68 109 103 77 99 99 99 99 99 99 99 99
24 35 55 64 81 104 113 92 99 99 99 99 99 99 99 99
49 64 78 87 103 121 120 101 99 99 99 99 99 99 99 99
72 92 95 98 112 100 103 99 99 99 99 99 99 99 99 99
------------------------------ ------------------------------

ƒ Quantization error is the main source of the lossy compression.

ƒ Quantization tables can be scaled to adjust the quality factor.

© 2004 Rolf Ingold, University of Fribourg © 2004 Rolf Ingold, University of Fribourg

JPEG Encoding

ƒ Encoding is performed in three steps

1) Zig-zag scan to transformed 8 x 8 blocs into 1 x 64 vectors

2) Two type of encoders

a) DPCM : Differential Pulse Code Modulation (encode the
difference from previous 8 x 8 blocks ), on DC components
b) RLE : Run Length Encode (RLE) on AC components
(supposed to contain a lot of 0)
3) Entropy based coding of values

© 2004 Rolf Ingold, University of Fribourg