Chapter 3 Image Enhancement in Frequency Domain.pdf

CSIT Image ehancement slide

1. Chapter 3

Image Enhancement in the Frequency Domain

2. Chapter 3

REFERENCES
“Digital Image Processing’, Rafael C.

% Gonzalez & Richard E. Woods,
Addison-Wesley, 2002

Much of the material that follows is taken from this book

Slides by Brian Mac Namee
[email protected]

3. Background

* The French mathematician Jean Baptiste Joseph Fourier
“ Born in 1768
Published Fourier series in 1822
Fourier’s ideas were met with skepticism
* Fourier series

Any periodical function can be expressed as the sum of sines
and/or cosines of different frequencies, each multiplied by a
different coefficient

4. Frequency Domain
ARAVA
NOIA
IA

5. Frequency Domain

It does not matter how complicated the function is; as long as it is periodic and meets
some mild mathematical conditions, it can be represented by such a sum.

Even functions that are not periodic (but whose area under the curve is finite) can be
expressed as the integral of sines and/or cosines multiplied by a weighing function. The
formulation in this case is the Fourier Transform, and its utility is even greater than the
Fourier series in most practical problem.

Both representations share the important characteristic that a function, expressed in
either a Fourier series or transform, can be reconstructed completely via an inverse
process with no loss of information.

6. Fourier Transform

* Fourier transform

Functions can be expressed as the integral of sines and/or cosines
multiplied by a weighting function

Functions expressed in either a Fourier series or transform can be
reconstructed completely via an inverse process with no loss of
information

7. Fourier Transform

* Easier to remove undesirable frequencies

* Faster perform certain operations in frequency domain than
in spatial domain

8. Fourier Transform

* Spatial, or image variables: x, y
* Transform, or frequency variables: u, v

9. Introduction to the Fourier Transform and the Frequency Domain

* The one-dimensional Fourier transform and its inverse
Fourier En)

u)=f fixe” 2" dx

Inverse „Ei transform

= [ Fluje?™du

10. Introduction to the Fourier Transform and the Frequency Domain

These two equations comprise the Fourier transform pair. These two equations exist if
f(x) is continuous and integrable and F(u) is integrable. These conditions are almost
always satisfied in practice. We are concerned with functions f(x), which are real,
however the Fourier transform of a real function is, generally, complex. So,

F(u) = R(u) + jI(u)

where R(u) and /(u)denote the real and imaginary components of F (u)respectively.

11. Introduction to the Fourier Transform and the Frequency Domain

Expressed in exponential form, F(u)is: F(u) = |F(u)|e/?()

Where, |F (u)| = YR?(u) + P(wand p(u) = tan-1 10

RC)

The magnitude function |F(u)|is called the Fourier spectrum of F(x) and p(u)is the phase
angle.

The square of the spectrum, P(u) = |F(u)|? = R?(u) + I?(u), is commonly called the
power spectrum (or the spectral density) of f(x).

The variable u is often called the frequency variable. This name arises from the expression
of the exponential term e/?”%*jn terms of sines and cosines (from Euler's formula):

er j?mux = cos(2mux) — jsin(2rux)

12. Introduction to the Fourier Transform and the Frequency Domain

Interpreting the integral in the Fourier transform equation as a limit summation of
discrete terms make it obvious that:

+ F(u)is composed of an infinite sum of sine and cosine terms.
+ Each value of u determines the frequency of its corresponding sine-cosine pair.

13. Introduction to the Fourier Transform and the Frequency Domain

Consider the following simple function.

fo

14. Introduction to the Fourier Transform and the Frequency Domain

The Fourier transform is:

F(u)= | f(xexpl-j2mer]dx

fe) pu
=f Aexp[—j2mux]dx
= -A
= rm yx ax _
F4 L= Foru ——f[e 1]
o x x = A fein -e/mX Jor

pi
= À sinçruX Ja
zu

15. Introduction to the Fourier Transform and the Frequency Domain

This is a complex function. The Fourier spectrum is: ¡Fw!
A

= i — jrux

IF@l | |IstnunIle |

= Ax] enn

(mux)

16. 2D Fourier Transform

The Fourier transform can be extended to 2 dimensions:

Fear) = || ra ye Pre ax dy

and the inverse transform

1 = || Faune ax dy

The 2-D Fourier spectrum is:

|F(u,v)| = /R?(u,v) + (uv)

The phase angle is: p(u,v) = tan”! pu]

The power spectrum is: P(u,v) = |F(u,v)|? = R?(u,v) + I?(u,v)

17. 2D Fourier Transform

F (uv) = | [ 10x. Dexpl- j2r(ux + vy)ldxdy

x E
10) = Afexpl- j2muex]dx expl- ¡20 y dy
o o
A _ erm + E law .
= Aja am
A au 1 m
o à le 2 a er à 52 roy
_ sin(muX)e "| sin(zvY)e /””
Tan Ge)
The spectrum is IF@,v)= an RN nen,

(muX) (war)

18. Discrete Fourier Transform

Discrete Fourier Transform (DFT) is purely discrete

Discrete-time data sets are converted into a discrete-
frequency representation.

19. Discrete Fourier Transform

Suppose a continuous function, f(x), is discretized into a sequence by taking N samples Ax
units apart.

Fo), f (Xo + Ax), f (to + 2Ax), ..., f (Xp + [N — 1]Ax))
Let x refer to either a continuous or discrete value by saying f(x) = f(xo + xAx)

Where x assumes the discrete values 0, 1, ..., N-1 and f(0), f (1), ..., f(N — 1)denotes any

7° N uniformly spaced samples from a corresponding continuous function.

Fox + 240)

Lo + 340) fixe + (N - Marl

20. Discrete Fourier Transform

The discrete Fourier transform is given by:
1 N-1
F(u) = =), f(xje?™/N y =0,1,..,N—1
x=0

The discrete inverse Fourier transform is given by:

Ni
f(x) = Y feel ;x =0,1,..,N-1
x=0
The values ofu = 0,1, ..... N — lin the discrete case correspond to samples of the

continuous transform at 0, Au, 2Au, ..., (N — 1)Au and Au = =

21. Question

fix) = fim + 140)

4

3 Find the Fourier Spectrum, Phase angle and Power
Spectrum for N = O and 1

2

22. fix) = fm + zAr)

Solution

Given,
f(0) =2
1(1) =3
1(2) =4
f(3) =4

N-1
F(u) = aD. Fix)e zrux/n
x=0

Where N= 4 (0,1,2,3)

23. Solution

For U=0

Fourier Spectrum

IF@| = RW+RrG) = (8) = 2
4 4
1X Power Spectrum
Flo)=2 fixe’ 132 rés
= FMP =R@+Pa =(7) = 2
4 16
F(0)=1[2+3+4+4] Phase Angle
A u) = tan! = tan > = tan = 0.2084
13 eu) = tan nn 13/ 7 13
F(0)=— 4

24. Solution

ForU=1 5
F)= 2 f(x) masa
x=0

m ytd paje al
F TD IE!
A (ee f(2)e "re f(8)e 772]

F 1)= 41241 +34(cos 4 jsin Æ)+ 4x (cos x jsin 2}+4%( cos = sin]

F 1)=412+143x(0- jx1)+4#(-1-jx0)+4+(0-j+-1)]

F 1)=4[2-3j-4+4]]

line 1,1;
F(U=3li-21= -5*q

25. Solution

ForU=1
Fourier Spectrum
14 1% V5
— 2 2 =q (== = mS
|F@)| =/R?@) +P) = ı( 5) +12) 7
Power Spectrum
At 5
2 =p? 2 = ae = =
IF@I? = Rw) +12) = "a 16
Phase Angle
1
= tan = an 4 =-0.4636
p(u) = tan re tan 1

2

26. Practice

Calculate for U=2 and 3

\F(2)|=[0/4)? + (0/4 7°? = 1/4
\F@)=(2/4)? + 0/4)? }? = V5/4

27. 2-D Discrete Fourier Transform

In the 2-D case:

-1N-1
1 jan (a+ 2).
F(u,v) = —— De ye PM) ;u = 0 > M—18&v =0—N—1
nn 2, Dy
M-1N-1 en
f(xy) = F(u, ver") x=0>M-18y =0>N-1

u=0 v=0

28. 2-D Discrete Fourier Transform

The discrete function f(x,y) represents samples of the continuous function at

f (Xo + XAX, yo + yAy)

when N=M (such as in a square image)
N-1N-1

Fu, v) = wd, 2 federn

And

2

-1

=

-1

f(x,y) = F(u, vJelzrt +vy)/N

zı-
R
1
4
=
[il
4

29. 2-D Discrete Fourier Transform

Magnitude or spectrum
|F(u, v)|=[R’(u, v)+1?(u, v)|

Phase angle or phase spectrum
| I(u,v)
R(u, v)

NIB

o(u,v)=tan

Power spectrum or spectral density

P(u,v)=|F(u,v)| =R°(u,v)+I°(u,v)

30. Filtering in the frequency domain

Filter Parameters

Distance Function

+ To generate filter transfer functions, it is necessary to know the distance of each element of the transfer
function to the origin (0,0). In the filter transfer function equations, this distance to the origin is denoted as
(D (u, v)), or simply as D.

+ Since the frequency domain data ranges from 0 to 2m in both the horizontal and vertical direction, rather than
between —Tt and rr, it is convenient to use a special function to calculate the distances.

Cutoff Frequency
+ The transition point between the pass and stop bands of the filter is denoted as D,
Band Width

+ For band-reject and band-pass filters, where the data between lower and upper cutoff frequencies is either
rejected or passed, the width is denoted as w.

31. Properties Of 2D Fourier Transform

The dynamic range of the Fourier spectra is generally higher than can be
displayed. A common technique is to display the function

D(u,v) = clog[1 + |F(u,v)|]
where c is a scaling factor and the logarithm function performs

“compression” of the data. ‘c’ is usually chosen to scale the data into the
range of the display devices [0,255]

32. Properties Of 2D Fourier Transform
Separability

Te

(a) Original image (b) DFT of each row of (a) (e) DFT of each column of (b)

33. Properties Of 2D Fourier Transform

Separability

2D Fourier Transforms can be implemented as a sequence of 1D Fourier
Transform operations performed independently along the two axis

j j Sx Nee" dxdy = Î cv] fe "dx =

= J Flu, ye? dy = F (u,v)

1D DFT along 1D DFT along
2D DFT | > the rows the cols

34. Properties Of 2D Fourier Transform

Separability

(0, 0) (N- 1) (0, 0) (N-D (0, 0) (N=)
y v ey
Row transforms Column
Sy) —— Fan | Fran
Multiplication by N transforms
(N=) (N=) (N-1
x x u

The main advantage of separability property is that a Fourier Transform of any dimension
can be performed by applying 1D transform on each dimension

35. Properties Of 2D Fourier Transform

Translation

The translation properties of the Fourier transform pair are

j2m(uox+voy)
faye NS FU Ug, v — v9)

and
F(X =X. Y — Yo) > Flu,vJe=s2rtuxotvyo)/N

where the double arrow indicates a correspondence between a function and its Fourier
transform (or vice versa). Multiplying f(x,y) by the exponential and taking the transform
results in a shift of the origin of the frequency plane to the point (wo, vo).

36. Properties Of 2D Fourier Transform

Periodicity

The discrete Fourier transform (and its inverse) are periodic with period N.
F(u,v) = F(u+N,v) = F(u,v +N) = F(u+N,v+N)

Although F(u,v) repeats itself infinitely for many values of u and v, only N values of each
variable are required to obtain f(x,y) from F(u,v).

ie. Only one period of the transform is necessary to specify F(u,v) in the frequency
domain.

37. Properties Of 2D Fourier Transform
Conjugate Symmetry

If f(x,y) is real (true for all of our cases), the Fourier transform exhibits conjugate
symmetry: F(u,v)=F*(-u,-v); F*(u,v) is the complex conjugate of F(u,v)

Or the more interesting: | F(u,v)|=|F(-u,-v)|
Example-1
F(t) = et F(t) = eI = alt= F(t)

F(-t) =e) Hence, F(t) = F(-t)

38. Properties Of 2D Fourier Transform

Implication of Periodicity and Symmetry

Consider a 1-D case:
F(u)=F(u+N) indicates F(u) has a period of length N
|F(u)|=|F(-u)| shows the magnitude is centered about the origin.

Because the Fourier transform is formulated for values in the range from [0,N-1], the
result is two back-to-back half periods in this range. To display one full period in the
range, move (shift) the origin of the transform to the point u=N/2

Fourier spectrum
with back-to-back
half periods in the

range
[0,n-1]

Shifted spectrum
with a

full period

in the

same range

39. Filtering in the frequency domain

b

ton.
Ontario, Canada.)

40. Filtering in the frequency domain

Input image

F0)y)

Filter's frequency
response
H (u,v)

Output image Inverse fourier
ax. y) transform

41. Filtering in the frequency domain

For each filtering operation, we will describe the construction
three types of filters in the frequency domain.

- Ideal Filters
- Gaussian Filter
- Butterworth Filter

42. Filtering in the frequency domain

Ideal Filters

* Ideal filters are quick and easy to implement and give an easy to understand appreciation of the
filter.

+ Unfortunately, ideal filters typically yield undesired results.

+ Specifically, ideal filters suffer from a problem known as ringing where extra lines appear around
the edges of objects in an image

43. Filtering in the frequency domain

Gaussian Filters

+ The shape of a Gaussian filter transfer function is bell-shaped curve that
models the probability distribution function

« The smooth transition between the pass-band and stop-band produces good
results with no noticeable ringing artifacts. The cutoff frequency of Gaussian
filters is determined by a variable (0).

44. Filtering in the frequency domain
Butter worth Filters

« The shape of a butter worth filter transfer function is tune-able

«The order of the filter (n) determines the gradient of the transition
between the pass-band and stop-band.

«It can assume a gentle transition like in Gaussian filters, or it can
assume an abrupt transition like ideal filters.

«A nice aspect of Butter worth filters is that the cutoff frequency is a
parameter of transfer function equation. Thus, it is simpler to determine
the parameters from examining the image in the frequency domain.

45. Filtering in the frequency domain

Smoothing Filters

ideal low-pass filter
1 if D(u, 0) < Do
Hi, v) = { 0 if D(u, v) > Do

Gaussian Low-pass filter
Hexlu, v) = e-(Ptus))/ 20°
Butterworth low-pass filter
1
Hgrlu, v) =
;
NT

46. Smoothing Frequency-Domain Filter

Ideal Low Pass

Hu)

Pi»)

abe

FIGURE 4.10 (a) Perspective plot of an ideal lowpass filter transfer function. (b) Filter displayed as an
image. (c) Filter radial cross section.

47. tena ae

ab
FIGURE 4.11 (a) An image of size 500 X 500 pixels and (b) its Fourier spectrum. The
superimposed circles have radii values of 5, 15, 30, 80, and 230, which enclose 92.0,

94.6, 96.4, 98.0, and 99.5% of the image power, respectively.

48. Smoothing Frequency-Domain Filter

Butterworth Low Pass

H(u,v) Hu, v)
10

Día, v)

Ale

FIGURE 4.14 (a) Perspective plot of a Butterworth lowpass filter transfer function. (b) Filter displayed as an
image. (c) Filter radial cross sections of orders 1 through 4.

49. Smoothing Frequency-Domain Filter

MELLE 5 |
cdo fl
IN ==

aaaaaaaa

Butterworth Low Pass

«a a
... a
III

+ al
VIII

aaaaaa

5
con Cal
III =

aaaaaaa

50. bed

FIGURE 4.16 (a)-(d) Spatial representation of BLPFs of order 1,2
profiles through the center of the filters (all fillers have a cutoff frequenc
as a function of filter order.

d 20, and corresponding gray-level
of 5). Note that ringing increases

51. Smoothing Frequency-Domain Filter

Gaussain Low Pass

Due)

abc

FIGURE 4.17 (a) Perspective plot of a GLPF transfer function. (b) Filter displayed as an image. (c) Filter
radial cross sections for various values of Do.

52. Smoothing Frequency-Domain Filter

1
= à
HI ==

aaaaaaaa

m
a
1m

+
Meee

aaaaaaaa

ed
I

Ma alalal

24 a
LL

Gaussain Low Pass

53. Smoothing Frequency-Domain Filter

Gaussain Low Pass

ab

FIGURE 4.19

(a) Sample text of
poor resolution
(note broken
characters in
magnified view).
(b) Result of
filtering with a
GLPF (broken
character
segments were
joined).

Historically, certain computer
programs were written using
only two digits rather than
four to define the applicable
year. Accordingly, the
company's software may
recognize a date using "00"

as 1900 rather than pal
2000.

Historically, certain computer
programs were written using
only two digits rather than
four to define the applicable
year. Accordingly, the
company's software may
recognize a date using "00"
as 1900 rather than the year

dl

2000. ea

54. abe
FIGURE 4.20 (a) Original image (1028 X 732 pixels). (b) Result of filteri

(©) Result of filtering with a GLPF with Do = 80. Note reduction in skin fine
of (b) and (e).

with a GLPF with Dy = 100.
lines in the magnified sections

55. Filtering in the frequency domain

Sharpening Filters

O High pass filter
H,,(u,v) =1- H,,(u,v)

ideal high-pass filter
_ [0 ifD(u, v) < Do
Hınla,v) -{ 1 if Du, ») > Do

Gaussian high-pass filter
Hanlu, v) = 1 — Pda
Butterworth high-pass filter
1

Honlu, v) = Tr ID Dr

56. |. | |
| |

FIGURE 4.23 Spatial representations of typical (a) ideal, (b) Butterworth, and (e) Gaussian frequency
domain highpass filters, and corresponding gray-level profiles.

abc

57. J

aeaaaaa

able

FIGURE 4.24 Results of ideal highpass filtering the image in Fig. 4.11(a) with Do = 15, 30, and 80,
respectively. Problems with ringing are quite evident in (a) and (b).

58. aaaaaaaa

abc

FIGURE 4.25 Results of highpass filtering the image in Fig. 4.11(a) using a BHPF of order 2 with Dj = 15.
30, and 80, respectively. These results are much smoother than those obtained with an ILPF

59. Tne

aaaaaaaa

ANDE

FIGURE 4.26 Results of highpass filter
30, and SO, respectively. Compare with

the image of Fig
s. 4.24 and 4.25.

4.11(a) using a GHPF of order 2 with Do = 15

60. Sharpening Frequency-Domain Filter
Laplacian High Pass
The Laplacian in the frequency domain

fi LO Guy FW)

„FEN, F0»)
ox? oy”
=(ju)’ F(u, v) + (jv) Fu, v)
=- (u? +v?)F(u,v)

61. Sharpening Frequency-Domain Filter
Laplacian High Pass

Vf (xy) =- (u? +v?)F(u, v)
H(u,v) =- (u? +v’)
* After centering

H(u,v) =-|(u- M/2Y +(v- N/2)|

62. Fast Fourier Transform

The Discrete Fourier Transform is

M-1

F(u) = Y 109 erm
x=0

Time Complexity :
O(M?)

Cannot it be made Faster?

63. Fast Fourier Transform

+ In image processing, the most common way to represent pixel location is in the spatial domain by column (x), row
(y), and z(value). But sometimes image processing routines may be slow or inefficient in the spatial domain,
requiring a transformation to a different domain that offers compression benefits.

A common transformation is from the spatial to the frequency (or Fourier) domain. The frequency domain is the
basis for many image filters used to remove noise, sharpen an image, analyze repeating patterns, or extract
features. In the frequency domain, pixel location is represented by its x- and y-frequencies and its value is
represented by amplitude.

The Fast Fourier Transform (FFT) is commonly used to transform an image between the spatial and frequency
domain.

- FFT method preserves all original data.
- FFT fully transforms images into the frequency domain

- FFT decomposes an image into sines and cosines of varying amplitudes and phases, which reveals
repeating patterns within the image.

64. Fast Fourier Transform

e Direct computation takes time: 22” multiplicatións
e FFT method takes: n2” multiplications
e Time savings: 2"/n

2" | Direct arithmetic | FFT | Increase in speed
4 16 8 2.0
8 84 24 2.67
16 256 64 4.0
32 1024 160 64
64 4096 384 10.67
128 16384 896 18.3
256 65536 2048 | 32.0
512 262144 4608 | 56.9
1024 1048576 10240 | 102.4

65. Fast Fourier Transform
Time Complexity

The Fast Fourier Transform (FFT) is a way to reduce the complexity of
the Fourier transform computation from O (n?) to 0 (nlogn) which is
a dramatic improvement.

66. Fast Fourier Transform
Radix-2 (DIT/DIF)

1.Radix-2 is the first FFT algorithm

2.It was proposed by Cooley and Tukey in 1965

3.Though it is not the most common algorithm, it laid the foundation
for efficient DFT Calculation.

4.The algorithm appear in
- Decimation In Time (DIT) , or
- Decimation in Frequency (DIF)

67. Fast Fourier Transform

The radix-2 DIT case

A radix-2 decimation-in-time (DIT) FFT is the simplest and most common
form of the Cooley-Tukey algorithm, although highly optimized Cooley-Tukey
implementations typically use other forms of the algorithm as described
below. Radix-2 DIT divides a DFT of size N into two interleaved DFTs (hence
the name "radix-2") of size N/2 with each recursive stage.

68. Fast Fourier Transform
The radix-2 DIT case

Assignment (FFT > DIT)

x(n) = {1,1,1,0,0,0,0,0}

69. Fast Fourier Transform

The radix-2 DIT case

If we let
Wy = 0727/M

the Discrete Fourier Transform can be written as
1 M-1
me. ux
Flu) = y >» f(x) Wu

If Mis a multiple of 2, M = 2K for some positive number K.

Substituting 2X for M gives

1 2K-1
F(U) = 5 2, 100 Wax”

x=0

70. Fast Fourier Transform

The radix-2 DIT case

Separating out the K even terms and the K odd terms,

K-1 K-1
217 1
FW=5 { x D fax) War + ra Y tex + paco)
x=0 x=0

Notice that
Wok = Wy
WAL = WER Wie = WHE Wie
So,

1 1 K-1 ox 1 K-1 ux mu
F(u) = Eon + LND We

71. Fast Fourier Transform

The radix-2 DIT case

F(u) = aioe x ere etch

x=0

F(u) = 5 {Feven(u) + Fogalu)Wex)

Use this to get the first K terms (u = 0..K — 1), then re-use these
parts to get the last K terms (u = K..2K — 1):

F(u+K)= 5 (Feven(u) - Fogg(u) Wi)

72. Convolution

Mathematical operation on two functions (f and g) that produces a third
function (f*g) that expresses how the shape of one is modified by the other.

Finite length signals (N, samples) — circular or periodic convolution

— the summation is over 1 period No=l
— the result is a N, period sequence clk] = JIk1@ glk] = > Siniglk =n]

n=0

73. Zero padding is a technique typically
employed to make the size of the input
sequence equal to a power of two.

In zero padding, you add zeros to the end
of the input sequence so that the total
number of samples is equal to the next
higher power of two.

For example, if you have 10 samples of a
signal, you can add six zeros to make the
total number of samples equal to 16, or
32, which is a power of two

Zero Padding

Zero Padded Signal

74. Correlation

The correlation theorem says that multiplying the Fourier transform of one
function by the complex conjugate of the Fourier transform of the other
gives the Fourier transform of their correlation.

That is, take both signals into the frequency domain, form the complex

conjugate of one of the signals, multiply, then take the inverse Fourier
transform. This is expressed by:

Fog) > F*(ujG(u)

75. Hadamard Transform

The Hadamard transform H,is a 2" x 2"matrix, the Hadamard matrix, that
transforms 2" real numbers x, into 2" real numbers x,

The Hadamard transform can be defined in two ways:
- recursively,

- binary(base-2) representation of the indices n and k

76. Hadamard Transform

We define the 1 x 1 Hadamard transform H, by the identity H, = 1, and then define
H, form > 0 by:

H=+1
1 Hna Hai „Ifi 1
m= lan = =) ali +)
1 É sa € À
(men = US = ml! Fa =|
1-1-1 1

1111341011
1 11 1-1 1
1 11-11
fia 1 11-11
1 1 1 1-1
1H 1-1 1-1 1
1 11 1 1 1 1 1
1 1-1 1 1

77. Haar Wavelets

The haar wavelet is a sequence of rescaled "square-shaped" functions which
together form a wavelet family or basis.

Wavelet analysis is similar to Fourier analysis in that it allows a target function over
an interval to be represented in terms of an orthonormal (Mutual perpendicular along a
line) basis.

The Haar wavelet's mother wavelet function y(t) can be described as

1 0<t<},
vQ=)-1 $<t<1,
0 otherwise.

78. Haar Transform

« The Haar transform is the simplest of the wavelet transforms.

+ This transform cross-multiplies a function against the Haar wavelet with
various shifts and stretches

* It is found effective in applications such as signal and image compression in
electrical and computer engineering as it provides a simple and
computationally efficient approach for analysing the local aspects of a
signal.

79. Haar Transform

The starting point for the definition of the Haar transform is the
Haar functions hy(z), which are defined in the closed interval [0, 1].
The order k of the function is uniquely decomposed into two integers
pq

k=2?+q-1,k=0,1,..., 2-1, andL=2”

where

O0<p<n-1,0<q< 2? forp £ Oandg=0orlforp=0

80. Haar Transform

holz) = hol?) = te, ze (0, 1

0 otherwise in [0,1]

81. Haar Transform

The Haar transform matrix of order L consists of rows resulting from the
preceding functions computed at the points z = m/L, m = 0, 1, 2,..., L- 1. For
example, the 8 x 8 transform matrix is

1 1 1 1 i 1 1 al

1 1 1 1-1 -1 -1 -1

v2 V2 -V2 -V2 0 0 0 0

mil 0 9 0 0 V2 v2 -v2 -v2
“| 2 -2 0 0.0.0 0 0

0 0 2 -2 0 0 0 0

0 0 0 0. 2-2 0 0

0 0 0 0 0 2 -2

82. Haar Transform

Original Image Haar wavelet coefficients

' ah

4 ‚

min
50 100 150 200 250 Decomposition at level 2

83. Discrete Cosine Transform (DCT)

based on most common form for 1D DCT

Clu)= a so fe] ux=0,1,..., N-1
Fo) el
+ fr u=0
a(u)=4 ""
a for u=0.
“mean” value

co TS o.
20

84. Discrete Cosine Transform (DCT)

COR ie —
| ae a d
TL =
mE mu 1

ja LE

LL

Cosine basis functions are orthogonal

85. Discrete Cosine Transform (DCT)

* Corresponding 2D formulation

N-1N-1 , i
direct C(u.v) = a 2 rx, De De q = Dv 1
4,v=0,1,...., N-1

1
Fra for u=0
= N

N

Tal
7
3
:
#
i

NANA E
inverse f(x, y) =>) adujo (clu, De le ee »),

u=0 v=0