Unit-1.B IMAGE TRANSFORMATIONS and fundamental.ppt

Image transformation

1. 1
UNIT-II
Prepared by
T. RAVI KUMAR NAIDU
1
Image Transformations

2. 2
Contents
•Fourier Transform and DFT
•Walsh Transform
•Hadamard Transform
•Walsh-Hadamard Transform (WHT)
•Discrete Cosine Transform (DCT)
•Haar Transform
•Slant Transform
•Comparison of various Transforms

6. •To get some sense of what basis elements look like, we plot a
basis element --- or rather, its real part ---as a function of x,y
for some fixed u, v. We get a function that is constant when
(ux + vy) is constant.
• The magnitude of the vector (u, v) gives a frequency, and its
direction gives an orientation. The function is a sinusoid with
this frequency along the direction, and constant perpendicular
to the direction.

7. Here u and v are larger than in the previous slide.
And larger still...

14. DFT Properties: (1) Separability
•The 2D DFT can be computed using 1D transforms only:
Forward DFT:
2 ( ) 2 ( ) 2 ( )
ux vy ux vy
j j j
N N N
e e e
  

  

kernel is separable:

15. DFT Properties: (1) Separability (cont’d)
•Rewrite F(u,v) as follows:
•Let’s set:
•Then:

16. •How can we compute F(x,v)?

•How can we compute F(u,v)?
DFT Properties: (1) Separability (cont’d)
N x DFT of rows of f(x,y)
DFT of coloums of F(x,v)

17. DFT Properties: (1) Separability (cont’d)

18. DFT Properties: (2) Periodicity
•The DFT and its inverse are periodic with period N

19. DFT Properties: (3) Symmetry

20. DFT Properties: (4) Translation
f(x,y) F(u,v)
• Translation in spatial domain:
• Translation in frequency domain:

21. DFT Properties: (4) Translation (cont’d)
•To “see” a full period, we need to translate the origin of the
transform at u=N/2 (or (N/2,N/2) in 2D)
|F(u-N/2)|
|F(u)|

22. DFT Properties: (4) Translation (cont’d)
•To move F(u,v) at (N/2, N/2), take

23. DFT Properties: (4) Translation (cont’d)
no translation after translation
sinc
sinc

24. DFT Properties: (5) Rotation
•Rotating f(x,y) by θ rotates F(u,v) by θ

25. DFT Properties: (6) Addition/Multiplication
but …
DFT Properties: (7) Scale

26. DFT Properties: (8) Average value
So:
Average:
F(u,v) at u=0, v=0:

27. Magnitude and Phase of DFT
•What is more important?
•Hint: use the inverse DFT to reconstruct the input
image using only magnitude or phase information
magnitude phase

28. Magnitude and Phase of DFT (cont’d)
Reconstructed image using
magnitude only
(i.e., magnitude determines the
strength of each component)
Reconstructed image using
phase only
(i.e., phase determines
the phase of each component)

29. 29
Walsh Transform
“+” denotes for +1 and “-” denotes for -1.
 
 





1n
0i
ubxb
i1ni
1
N
1
u,xgIn 1-D case we have :
In the following table N=8 so n=3 (2
3
=8).
1-D kernel

30. 30
Walsh Transform
When N=2
n
, the 2-D forward and inverse Walsh kernels are given by the relations
  
 
  
 












1
0
1
0
11
11
1
1
,,,
1
1
,,,
n
i
vbybubxb
n
i
vbybubxb
iniini
iniini
N
vuyxh
and
N
vuyxg
Where b
k
(z) is the k
th
bit in the binary representation of z.
So the forward and inverse Walsh transforms are equal in form; that is:

31. 31
Walsh Transform
This figure shows the basis functions
(kernels) as a function of u and v
(excluding the 1/N constant term) for
computing the Walsh transform when
N=4. Each block corresponds to varying x
and y form 0 to 3 (that is, 0 to N-1), while
keeping u and v fixed at the values
corresponding to that block. Thus each
block consists of an array of 4×4 binary
elements (White means “+1” and Black
means “-1”). To use these basis functions
to compute the Walsh transform of an
image of size 4×4 simply requires
obtaining W(0,0) by multiplying the image
array point-by-point with the 4×4 basis
block corresponding to u=0 and v=0,
adding the results, and dividing by 4, and
continue for other values of u and v.

32. 32
1D-Walsh Transform

33. 33
1D – Inverse Walsh Transform

34. 34
2D-Walsh Transform

35. 35
2D – Inverse Walsh Transform

36. Implementation of the 2-D Walsh Transform
•The 2-D Walsh transform is separable and symmetric .
•Therefore it can be implemented as a sequence of two 1-D
Walsh transforms, in a fashion similar to that of the 2-D DFT.
•Remember that the Fourier transform is based on
trigonometric terms.
•The Walsh transform consists of basis functions whose
values are only 1 and -1.
•They have the form of square waves.
•These functions can be implemented more efficiently in a digital
environment than the exponential basis functions of the Fourier
transform.
36

37. Kernels of Forward and Inverse Walsh Transform
•For 1-D signals the forward and inverse Walsh kernels differ
only in a constant multiplicative factor of N .
•This is because the array formed by the kernels is a
symmetric matrix having orthogonal rows and columns,
so its inverse array is the same as the array itself!
•In 2-D signals the forward and inverse Walsh kernels are
identical!
•The Concept of Sequency : We can think of frequency as
the number of zero crossings or the number of transitions in
a basis vector and we call this number sequency.
37

38. The Concept of Sequency
38
Sequency: 0 1 3 2 7 6 4 5

39. 2-D Hadamard Transform
39

40. 2-D Inverse Hadamard Transform
40

41. 41
Hadamard Transform
When N=2
n
, the 2-D forward and inverse Hadamard kernels are given by the relations
 
 
 
 









1
0
1
0
1
1
,,,
1
1
,,,
n
i
iiii
n
i
iiii
vbybubxb
vbybubxb
N
vuyxh
N
vuyxg
Where b
k(z) is the kth bit in the binary representation of z.
So the forward and inverse Hadamard transforms are equal in form; that is:

42. 42
Hadamard Transform





1
01
1
,
n
i
ii
ubxb
N
uxgIn 1-D case we
have :
In the following table N=8 so n=3 (2
3
=8).
1-D kernel
“+” denotes for +1 and “-” denotes for -1.
 






1
01)(
1
1
0
n
i
ii ubxb
N
x
xf
N
uH

43. 43
Hadamard Transform
This figure shows the basis functions
(kernels) as a function of u and v
(excluding the 1/N constant term) for
computing the Hadamard transform
when N=4. Each block corresponds to
varying x and y form 0 to 3 (that is, 0 to
N-1), while keeping u and v fixed at the
values corresponding to that block. Thus
each block consists of an array of 4×4
binary elements (White means “+1” and
Black means “-1”) like Walsh transform.
If we compare these two transforms we
can see that they only differ in the sense
that the functions in Hadamard transform
are ordered in increasing sequency and
thus are more “natural” to interpret.

44. Recursive Relationship of the
Hadamard Transform
44

45. 45
The Concept of Sequency
Sequency: 0 7 3 4 1 6 2 5

46. 46
1-D WHT Kernel Functions

47. 1-D WHT Kernel Functions
Sequency: 0 1 2 3 4 5 6 7

48. 48
2-D Walsh-Hadamard Transform (WHT)

49. 49
2-D WHT Kernel Functions

50. 50
WHT and Fourier Transform

51. 1-D Discrete Cosine Transform

52. 1-D Discrete Cosine Transform

53. 53
2-D Discrete Cosine Transform

54. 54
Discrete Cosine Transform (DCT)
Each block consists of 4×4 elements, corresponding to x and y varying
from 0 to 3. The highest value is shown in white. Other values are shown
in grays, with darker meaning smaller.

55. 55
Slant Transform
•The Slant Transform matrix of order N*N is the recursive expression








11
11
2
1
S
2
 
2
1
2
2
N
1N4
N3
a








Where I is the identity matrix, and
 
2
1
2
2
N
1N4
4N
b










56. Slant Transform

57. 57
Haar Transform
The Haar transform is based on the Haar functions, h
k
(z), which are
defined over the continuous, closed interval [0,1] for z, and for
k=0,1,2,…,N-1, where N=2
n
.
The first step in generating the Haar transform is to note that the
integer k can be decomposed uniquely as k=2
p
+q-1
where 0≤p≤n-1, q=0 or 1 for p=0, and 1≤q≤2
p
for p≠0.
With this background, the Haar functions are defined as
 






















1,0zforotherwise0
2
q
z
2
2/1q
2
2
2/1q
z
2
1q
2
N
1
zhzh
and
1,0zfor
N
1
zhzh
pp
2/p
pp
2/p
00k
000



58. Haar Transform
Or

64. The End
64