Image Transforms
copyright 2002©H. R. Myler
Fourier Transform Pair:
∞ ∞
F (u , v) = ∫∫ f ( x, y )e − j 2π (ux + vyy ) dxdy
d d
−∞ −∞
∞ ∞
f ( x, y ) = ∫∫ F (u , v)e j 2π ( ux + vy ) dudv
−∞ −∞
Same properties as in 1D apply
copyright 2002©H. R. Myler
Fourier Transform Pair:
We can show that for a “box” image of finite size X by Y
and of a constant value A:
X 2 Y 2
− j 2π ( ux + vy ) ⎡ sin (π uX ) ⎤ ⎡ sin (π vY ) ⎤
F (u, v) = ∫ ∫
− X 2 −Y 2
Ae dxdy = AXY ⎢ ⎥⎢
⎣ π uX ⎦ ⎣ π vY ⎦
⎥
The magnitude (spectrum) is:
sin (π uX ) sin (π vY )
F (u, v) = AXY
π uX π vY
copyright 2002©H. R. Myler
maxima of:
cos 2π (ux+vy)
copyright 2002©H. R. Myler
Discrete Fourier Transform Pair:
M −1 N −1 ⎛ ux vy ⎞
− j 2π ⎜ + ⎟
F (u , v) = ∑ ∑ f ( x, y )e ⎝M N ⎠
x =0 y =0
M −1 N −1 ⎛ ux vy ⎞ kernels
j 2π ⎜ + ⎟
f ( x, y ) = ∑ ∑ F (u, v)e ⎝M N ⎠
x =0 y =0
For an M x N image
copyright 2002©H. R. Myler
The Fourier Transform kernel is
separable: -2π jux -2π jvy
exp exp
N N
• Separability gives rise to processing
advantages in the computer. The transform
may be performed as a single dimensional
computation on the rows and columns.
• The Fourier matrix can be factored into the
product of 2 log2 N sparse and diagonal
matrices (observed by Good in 1958). This is
the basis for the Fast Fourier Transform.
copyright 2002©H. R. Myler
http://sepwww.stanford.edu/oldsep/hale/FftLab.html
copyright 2002©H. R. Myler
Fast Fourier Transform
To approximate a function by samples, and to
approximate the Fourier integral by the discrete Fourier
transform, requires applying a matrix whose order is the
number sample points n n.
Since multiplying an n x n matrix by a vector costs on the
order of n2 arithmetic operations, the problem gets quickly
worse as the number of sample points increases.
However, if the samples are uniformly spaced, then the
Fourier matrix can be factored into a product of just a few
sparse matrices, and the resulting factors can be applied
to a vector in a total of order n log n arithmetic operations.
This is the so-called fast Fourier transform or FFT.
copyright 2002©H. R. Myler
A separable transform can be written as:
M −1 N −1
T (u , v) = ∑ ∑ f ( x, y ) g1 ( x, u ) g 2 ( y, v)
x =0 y =0
M −1 N −1
f ( x, y ) = ∑ ∑ T (u, v)h1 ( x, u )h2 ( y, v)
u =0 v =0
The kernel is symmetric if:
g 1 (x,u)= g 2 (y,v)
copyright 2002©H. R. Myler
A separable transform can be computed in
two steps:
N −1
T ( x, v ) = ∑ f ( x, y ) g 2 ( y , v )
y =0
M −1
T (u , v) = ∑ T ( x, v) g1 ( x, u )
x =0
This means that the transform can be
computed on the rows of the image, and
then on the columns.
copyright 2002©H. R. Myler
This means that the transform can be
computed on the rows of the image, and
then on the columns.
f(x,y) process T(x,v)
rows
T(u,v) process
columns
copyright 2002©H. R. Myler
2D DFT example
Bright spots
in the corners
Centered
spectrum
copyright 2002©H. R. Myler
2D DFT examples with enhanced details
Details were enhanced
by the log
transformation.
Both spectrum of the
translated rectangle is
identical to the spectrum
of the initial rectangle
(previous slide).
The spectrum of the
rotated image also
rotates by the same
angle
copyright 2002©H. R. Myler
Walsh Transform:
n −1
1
g ( x, u ) = ∑ ( −1)
bi ( x ) bn−1−i ( u )
N i =0
b k z is the kth bit from the binary
representation of z.
e.g., let z=13, then z=1101 binary.
b z =11 b 0 z =1
1
3
b z =1 b 1 z =0
2
copyright 2002©H. R. Myler
• The Walsh transform uses square‐waves as
it's basis functions, and these vary from ‐1
to +1.
• We talk of sequency instead of frequency
• We talk of sequency instead of frequency
when discussing the Walsh.
• The advantage of the Walsh transform is
that it does not require floating‐point math
or transcendental functions.
• The inverse Walsh kernel is identical to the
forward kernel.
copyright 2002©H. R. Myler
Hadamard Transform:
The Hadamard transform is similar to the Walsh
in that it uses square waves of ‐1 to +1 in
amplitude.
amplitude
The transform is easily derived from
multiplication of the image with the
Hadamard matrix:
F=H
The lowest order Hadamard matrices are given
by: ⎡1 1 1 1 ⎤
⎢ ⎥
1 ⎡1 1 ⎤ 1 ⎢1 −1 1 −1⎥
H 0 = 1; H1 = ⎢ ⎥ ; H =
2 ⎣1 −1⎦ 2 ⎢1 1 1 1 ⎥
2
⎢ ⎥
copyright 2002©H. R. Myler
⎣1 −1 1 −1⎦
Any order of 2N Hadamard matrix can
now be derived from:
1 ⎡HN HN ⎤
= ⎢H − H N ⎥⎦
H2N
2⎣ N
Sometimes, the normalization factor is
Sometimes the normalization factor is
omitted.
copyright 2002©H. R. Myler
Discrete Cosine Transform(DCT):
Kernel: g(x,u) = 2 cos 2x+1uπ
N 2N
M −1 N −1
⎡π ⎛ 1⎞ ⎤ ⎡π ⎛ 1⎞ ⎤
2D: F (u , v) = ∑ ∑ f ( x, y) cos ⎢⎣ M ⎜⎝ x + 2 ⎟⎠ u ⎥⎦ cos ⎢⎣ N ⎜⎝ y + 2 ⎟⎠ v ⎥⎦
x =0 y =0
•This transform is simpler than the Fourier as it does not require complex
numbers. The DCT has the added advantage of mirror‐symmetry.
•If the DCT is used for block‐encoding, where the image is partitioned into
sub‐pictures prior to transforming, the DCT has less edge degredation
because of it's symmetry properties.
• The inverse kernel is identical to the forward form.
copyright 2002©H. R. Myler
