Reminder: 1D Fourier Series

Spatial frequency analysis of a step edge

Fourier decomposition
 Fourier series reminder

Example

= +

1
f (x) = sin x + sin 3x + . . .
3
Fourier series for a square wave

X 1
= f (x) = sin nx
n=1,3,5,... n
Fourier series: just a change of basis
M f(x) = F()

. =

.
.
.
Inverse FT: Just a change of basis
M-1 F() = f(x)

. =

.
.
.
1D Fourier Transform

Reminder transform pair - definition

Example

x u
2D Fourier transforms
2D Fourier transform

Definition
Sinusoidal Waves
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.
v

slide: B. Freeman
Here u and v are larger than
in the previous slide.

u
And larger still...

u
Some important Fourier Transform Pairs
FT pair example 1
v

rectangle centred at origin

with sides of length X and Y u

f(x,y) |F(u,v)|

separability

|F(u,v)|
FT pair example 2

Gaussian centred on origin

f(x,y)

F(u,v)
• FT of a Gaussian is a Gaussian
• Note inverse scale relation
FT pair example 3

Circular disk unit height and

radius a centred on origin
f(x,y)

F(u,v)

• rotational symmetry
• a ‘2D’ version of a sinc
FT pairs example 4

f(x,y) F(u,v)
 Summary

f(x,y)

+ +
= +…
Transformations

As in the 1D case FTs have the following properties

• Linearity

• Similarity

• Shift
In 2D can also rotate, shear etc
Under an affine transformation:
Example
How does F(u,v) transform if f(x,y) is rotated by 45 degrees?
f(x,y) |F(u,v)|
The convolution theorem
 Filtering vs convolution in 1D

filtering f(x) with h(x)

f(x) 100 | 200 | 100 | 200 | 90 | 80 | 80 | 100 | 100

h(x) 1/4 | 1/2 | 1/4 molecule/template/kernel

g(x) | 150 | | | | | | |
Z
g(x) = f (u)h(x − u) du convolution of f(x) and h(x)
Z
= f (x + u0)h(−u0) du0 after change of
X variable
= f (x + i)h(−i)
i
• note negative sign (which is a reflection in x) in convolution
• h(x) is often symmetric (even/odd), and then (e.g. for even)
 Filtering vs convolution in 2D

convolution

filtering image f(x,y)

filter / kernel h(x,y)

g(x,y) =

for convolution, reflect filter in x and y axes

 Convolution
• Convolution:
– Flip the filter in both dimensions (bottom to top, right to left)

h
convolution
filtering with with
h h h
f

slide: K. Grauman
Filtering vs convolution in 2D in Matlab

2D filtering f=image
• g=filter2(h,f); h=filter

g[m, n]   h[k , l ] f [m  k , n  l ]
k ,l
2D convolution
• g=conv2(h,f);

g[m, n]   h[k , l ] f [m  k , n  l ]
k ,l
 Convolution theorem

Space convolution = frequency multiplication

In words: the Fourier transform of the convolution of two

functions is the product of their individual Fourier transforms

Proof: exercise

Why is this so important?

Because linear filtering operations can be carried out by simple
multiplications in the Fourier domain
 The importance of the convolution theorem
It establishes the link between operations in the frequency
domain and the action of linear spatial filters

Example smooth an image with a Gaussian spatial filter

Gaussian
scale=20 pixels

*
1. Compute FT of image and FT of Gaussian
2. Multiply FT’s
3. Compute inverse FT of the result.
 f(x,y) g(x,y)
Gaussian
scale=3 pixels

*
Inverse Fourier
Fourier transform transform

|F(u,v)| |G(u,v)|
 f(x,y) Gaussian scale=3 pixels g(x,y)

*
Inverse Fourier
Fourier transform transform

|F(u,v)| |G(u,v)|
There are two equivalent ways of carrying out linear spatial
filtering operations:
1. Spatial domain: convolution with a spatial operator
2. Frequency domain: multiply FT of signal and filter, and compute
inverse FT of product

Why choose one over the other ?

• The filter may be simpler to specify or compute in one of the domains
• Computational cost
The sampling theorem
Discrete Images - Sampling

f(x)

x
x
X x
Fourier transform pairs
Sampling Theorem in 1D
spatial domain frequency domain

x
*
F(u) u

replicated copies of F(u)

 Apply a box filter

1/X u
f(x) F(u)

The original continuous function f(x) is completely recovered from the samples
provided the sampling frequency (1/X) exceeds twice the greatest frequency of the
band-limited signal. (Nyquist sampling limit)
 The Sampling Theorem and Aliasing
if sampling frequency is reduced …
spatial domain frequency domain

x u

Frequencies above the Nyquist limit are

‘folded back’ corrupting the signal in the
acceptable range.
The information in these frequencies is
not correctly reconstructed.
Sampling Theorem in 2D
frequency domain

* =
1/Y
1/X
F(u,v)

* =
The sampling theorem in 2D

If the Fourier transform of a function ƒ(x,y) is zero for all

frequencies beyond ub and vb,i.e. if the Fourier transform is
band-limited, then the continuous function ƒ(x,y) can be
completely reconstructed from its samples as long as the
sampling distances w and h along the x and y directions
are such that 1 and 1
w h
2ub 2vb
 Rect Function

• Rect function:

 1 1
1, for x  and y 
rect ( x, y )   2 2
 0, otherwise

• It is normally used to pick up a particulate section of a given

function:

x   y 
f ( x, y )  rect ( , )
wX wY

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Sinc Function

• The sinc function is defined as

sin(x)
sinc( x) 
x

• The sinc function is normalized.


 -
sinc( x)dx  1

Any arbitrary band-limited signal can be written as a weighted sum of

multiple sinc functions … (the Nyquist Sampling Theorem)

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Triangular Signals and Gaussian Signals

• Triangular function:

x x
Tri ( )  1  for x  L
2L L
0 for x  L

• Normalized Gaussian function:

x2
1  2
G1D ( x)  e 2
2 
x2 y2
1 
G2 D ( x, y )  e 2 2
2 2

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Separable Signals and Periodic Signals

• The separable signals is a class of continuous signals that satisfy

x2 y2 x2 y2
1  1  1 
e 2 2
 e 2 2
 e 2 2
2 2 2  2 
f ( x, y )  f1 ( x)  f 2 ( y )

• A signal is periodic if

f ( x, y )  f ( x  X , y )  f ( x, y  Y )
where X and Y are the signal periods

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Two Dimensional Sampling
f s ( x, y )  f ( x, y )   s ( x, y, x, y )
 
 
n -m -
f ( x,y )  δ( x - n  x , y - m  y )
 
 
n -m -
f ( n  x , m  y )  δ( x - n  x , y - m  y )

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Fourier Transform
 Restoration of the Original 2-D Function
Given that the Nyquist sampling condition is met, the original function
could be recovered exactly as
f ( x, y)  f s ( x, y)  h( x, y)
1 x  1 y 
 f s ( x, y)    sinc( )   sinc( )
 x x   y y 
   1 x  1 y 
   f (nx, my)  δ( x  n  x, y  m  y)   sinc( )   sinc( ) 
n   m  x x   y y  
 
1 x  n  x y  m  y
  f (nx, my)  sinc( )  sinc( )
n   m xy x y

sin(x)
sinc( x) 
x
NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Fourier Transform
 General Concept of a System

• A continuous-to-continuous system is defined as

g ( x, y )  S [ f ( x, y )]

• A system is a mapping process from an input signal to the output

signal

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems

A system is linear if it satisfies the superposition principle

 I
 I
S  f ( x, y )   wi  f i ( x, y )   wi  S  f i ( x, y )
 i 1  i 1
where
f ( x, y ) is the input signal,
S 
 is an operator that represents the system,
f ( x, y ) is the total input signal and
wi s are weighting factors.
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – An Example
For example, consider an amplifier with gain A:

f1
+ L so
f2
S w1 f1  w2 f 2   A( w1 f1  w2 f 2 )
=

f1  Aw1 f1  Aw2 f 2  w1S  f1   w2 S  f 2 

L
+ so
f2 L It satisfies the Superposition Principle
 I
 I
Covered in S  f ( x, y )   wi  f i ( x, y )   wi  S  f i ( x, y )
lecture  i 1  i 1
NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – Why Important?

• Linear systems is mathematically more “tractable”.

 I

f ( x, y )  S  f ( x, y )   wi  f i ( x, y )  g ( x, y )
 i 1 
• Many imaging systems used in medical and other applications can be
described as linear systems.

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – Why Important?
• Linear systems satisfy the Superposition Principle.

 I  I
g(x, y)  S f (x, y)  S  w i  f i (x, y)  w i  S  f i (x, y)
i1  i1

• It would be good if we can decompose an arbitrary signal into a linear

combination of a series of basis functions – such as the -function.

• If one can derive the response of the system to this basis function,

• then the response of a system to the arbitrary input signal should

easily follow …
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Continuous Fourier Transform

www.revisemri.com
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Fourier Transform
 Comb and Sampling Function

• The sampling function is critical for the discretization of

continuous signals.
• The sampled signal function is then
 
s (x, y, x, y)     (x  mx, y  ny)
m n

where x and y are the sampling intervals

fs (x, y)  f (x, y) s (x, y)
 
 f (x, y)    (x  mx, y  ny)
m n

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – Why Important?

Since we can often decompose an arbitrary input signal as a linear

combination of basis functions (delta functions, or sinusoidal
functions, or sinc functions etc.),

the response of a linear system to the given arbitrary input signal

can therefore be modeled as the linear combination of the response
of the system to each individual basis functions….

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – Why Important?
• The Superposition Principle.
 I  I
g(x, y)  S  f (x, y)  S  w i  f i (x, y)  w i  S  f i (x, y)
i1  i1
• Given a discrete input signal

• The response of the linear system is

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function
One of the most common shape for impulse responses used in
imaging application

x x

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function
For a linear system, knowing the IRF, one could compute the output from any
arbitrary input function as

 
 
 
f ( x , y ) ( x   , y   )dxdy  f (  , )
or
 
 
 
f (  , ) (   x ,  y )dxdy  f ( x , y )
g ( x, y )  S [ f ( x, y )] 
 
 S   f ( , ) ( x   , y   )dd 
  

   
 
 
f (  , ) ( x   , y   )dxdy  f ( x , y )
Using the sampling property of

S  f ( , ) ( x   , y   )dd
  delta function
  

f ( , )S  ( x   , y   )dd
 
 
 
The linearity condition is
used here
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function
For a linear system, knowing the IRF enables one to compute the output
from any arbitrary input function.

g ( x, y )  S [ f ( x, y )]

 S   f ( , ) ( x   , y   )dd 
 

   
S  f ( , ) ( x   , y   )dd
 
   

f ( , )S  ( x   , y   )dd
 
 
 

The impulse response function is defined as

h( x , y , , )  S  ( x   , y   )
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function
For a linear system, knowing the IRF enables one to compute the output from any
arbitrary input function:

g ( x, y )  S [ f ( x, y )]

 S   f ( , ) ( x   , y   )dd 
 

   
S  f ( , ) ( x   , y   )dd
 
   

f ( , )S  ( x   , y   )dd
 
 
 

Or written explicitly as

 
g( x , y )    f (  , )h( x , y , , )dd
 
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function
• For a 2-D problem, the impulse response is a 4-D function.

 
g ( x, y )    f ( , )h( x, y,  , )dd
 

• The computation can be greatly reduced with further

simplifications …

What exactly is this function again? What does it

tell us about the system?

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Shift Invariant Systems

To PC display

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Shift Invariant Systems

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Shift Invariant Systems (II)

• A system is called shift-invariant if

g ( x  x, y  y )  S  f ( x  x, y  y )

• Shift-invariance does not require or imply linearity

• The impulse response function of a shift invariant system is

h( x, y,  , )  S[  , ( x, y )]  h( x   , y   )

4-D  2-D
Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Shift Invariant Systems (III)

• The impulse response function of a shift invariant system is

 
g ( x, y )    f ( , )h( x, y,  , )dd
 
 
  f ( , )h( x   , y   )dd
 

 f ( x, y )  h ( x, y )
• The output of a linear and shift-invariant system is the input
convolved with the impulse response function.

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Linear Systems – Why Important?

• Many imaging systems used in medical and other applications can be

described as linear systems.

• Ideally, we should have

Image = Object * Impulse Response Function + Noise

Convolution process

• We are not quite there yet …

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Impulse Response Function

• The impulse response function is defined as

h( x , y , , )  S [ ( x   , y   )]

• The impulse response function is sometimes referred to as the point-

spread function (PSF).

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Convolution Operation in 1-D – Examples



f (x)  g(x)  
f ()g(x  )d

• red, blue: convolved signals

• green: convolution result

two boxes two Gaussians

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Properties of Convolution Operation

 
f ( x, y )  h ( x, y )    f ( , )h( x   , y   )dd
 

• Commutativity

h1 ( x, y )  h2 ( x, y )  h2 ( x, y )  h1 ( x, y )
• Distributivity

h1 ( x, y )  h2 ( x, y) f ( x, y )  h1 ( x, y )  f ( x, y )  h2 ( x, y )  f ( x, y )

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Convolution Operation – Examples

g ( x, y )  f ( x, y )  gaussian( x, y )
where
x2 y2
1 
gaussian( x, y )  e 2 2
2 2

original =1 =2

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Connection of LSI Systems

Covered in
lecture

g ( x, y )  h1 ( x, y )  h2 ( x, y ) f ( x, y ) g ( x, y )  h2 ( x, y )  h1 ( x, y )  f ( x, y )

 h2 ( x, y )  h1 ( x, y ) f ( x, y )  h1 ( x, y )  h2 ( x, y )  f ( x, y )

LSI systems may be decomposed into the combination of multiple sub-

systems. This may lead to a simplified mathematical representation of the
complete system…

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Separable Systems
A system is called separable if

h( x, y )  h1 ( x)h2 ( y )

in which case, the convolution between the input and the impulse
response function is

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Separable Systems
For a separable system, the 2-D convolution operation can be re-write as
two 1-D convolution operations.

g ( x, y )  h( x, y ) * f ( x, y )  h1 ( x) * h2 ( y ) * f ( x, y )

An example

x2 y2  1  1 
2 2
x y
1   2  2
gaussian( x, y )    
2
2
e e 2 e 2
2 2  2 2  2 2 
  

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
 Separable Systems – An Example

An input image pass through a separable system having a impulse

response function described by a 2-D Gaussian function
x2 y2 x2 y2
1  1  1 
gaussian( x, y )  e 2 2
 e 2 2
 e 2 2
2 2 2  2 

g ( x, y )  f ( x, y )  gaussian( x, y )
x2  y 2
1 
 f ( x, y )  e 2 2
2 2

  2 
2 2
x y
1 1  2
  f ( x, y )  e 2
 e 2

 2   2 

Covered in
lecture

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019 Signals and Systems
1. Parseval’s Theorem and Inner Product Preservation
Another important property of FT is that the inner product of
two functions is equal
Z Z to the inner product of their FT’s.
1
x(v, u)y ⇤(u, v)dudv
1
1Z Z
1
= 2 X(!1, !2)Y ⇤(!1, !2)d!1d!2
4⇡ 1
where ⇤ stands for complex conjugate operation. When x = y
we obtain the well-known Parseval energy conservation formula
i.e.Z Z 1 Z Z 1
1
|x(u, v)| dudv = 2
2
|X(!1, !2)|2d!1d!2
1 4⇡ 1
i.e. the total energy in the function is the same as in its FT.
2. Frequency Response and Eigenfunctions of 2-D LSI Systems
An eigen-function of a system is defined as an input function

To advance click enter or page down to go back use page up 1

 that is reproduced at the output with a possible change in the
amplitude. For an LSI system eigen-functions are given by
f (u, v) = exp(j!1u + j!2v)

Using the 2-D

Z convolution
Z 1 integral
g(u, v) = h(u u0, v v 0) exp[j!1u0 + j!2v 0]du0dv 0
1
change ũ = u u , ṽ = v v 0, then
0

g(u, v) = H(!1, !2) exp[j!1u + j!2v]

where Z Z 1
H(!1, !2) = h(ũ, ṽ) exp[j!1ũ + j!2ṽ]dũdṽ
1
= F{h(u, v)}
To advance click enter or page down to go back use page up 2
 is the frequency response of the 2-D system. The output is a
complex exponential function with the same frequency as the
input signal but its amplitude and phase are changed by the
complex gain H(!1, !2) of the 2-D system.
Example:
Determine the frequency response of a 2-D system whose impulse
response is
⇢
1 |u|  X, |v|  Y
h(u, v) =
0 elsewhere

Find H(!1, !2).

Z Z 1
j(!1u0+!2v 0)
H(!1, !2) = h(u , v )e
0 0
du0dv 0
1

To advance click enter or page down to go back use page up 3

 Z X Z Y
= e1j(!1u +!2v )du dv
1X 1Y
⇢Z ⇢Z
X Y
= e1j!1u du e1j!2v dv
1X 1Y

ej!1X ⇤ e1j!1X ej!2Y ⇤ e1j!2Y

= ( )( )
j⇡1 j⇡2
sin ⇡1X sin ⇡2Y
= 2X( )2Y ( )
⇡1 X ⇡2 Y
= 4XY sinc(⇡1X)sinc(⇡2Y )

To advance click enter or page down to go back use page up 4

 Image Sampling and Quantization
The most basic requirement for computer processing of images is
that the images must be available in digital form i.e. arrays of
integer numbers. For digitization the given image is sampled on a
discrete grid and each sample or pixel is quantized to an integer
value representing a gray level. The digitized image can then be
processed by the computer.
To advance click enter or page down to go back use page up 5
 2-D Sampling Theorem
Definition: An image x(u, v) is called ”bandlimited” if its FT
X(!1, !2) is zero outside a bounded region in the frequency plane
i.e.

X(!1, !2) = 0 |!1| > !10, |!2| > !20

!10, !20: Bandlimits of the image. If the spectrum is circularly

4
symmetric then the single spatial frequency [!0 = !10 = !20] is
the bandwidth.

To advance click enter or page down to go back use page up 6

 Sampling Vs. Replication
The FT of a sampled image is a scaled, periodic replication of the
FT of the original image. To show this result, we sample x(u, v)
using and ideal image sampling function, sa(u, v) that is defined as
1 1
4
sa(u, v; u, v) = (u m u, v n v)
m= 1 n= 1

with the “sampling intervals” u, v. The sampled image is

xs(u, v) = x(u, v)sa(u, v; u, v)

1
= x(m u, n v) (u m u, v n v)
m,n= 1

It can be shown that the FT of the sampling function with spacing

To advance click enter or page down to go back use page up 7
 2⇡ 2⇡
u, v is another sampling function with spacing u, v . Then,
using the convolution in frequency domain we get
1
1 2⇡k 2⇡l
Xs(!1, !2) = X(!1 , !2 )
u v u v
k,l= 1

Let us define discrete frequency variables (i.e. in discrete

domain) ⌦1=!1 u,⌦2=!2 v, then we get 2-D Discrete Space Fourier
Transform (DSFT),
1
1 ⌦1 2⇡k ⌦2 2⇡l
Xs(⌦1, ⌦2) = X( , )
u v u v
k,l= 1

This result shows sampling in the spatial domain causes periodicity

in the frequency domain (See Figure).
To advance click enter or page down to go back use page up 8
 !2

!vs/2

!vs
R1
!vs-!20
!us-!10

!20
"!us !us !1
"!10 !10

"!20
R
R2 !us/2

"!vs

To advance click enter or page down to go back use page up 9

 Let !us = 2⇡u and !vs = 2⇡
v (i.e. sampling frequencies), then
alternatively
1
1
Xs(!1, !2) = 2 !us!vs X(!1 k!us, !2 l!vs)
4⇡
k,l= 1

As can be seen from the Figure, for no overlapping between the

replica the lower bounds on the sampling frequencies are 2!10 and
2!20. These frequencies are referred to as ”Nyquist frequencies”.
Their reciprocals are called ”Nyquist intervals”. The sampling
frequency must be equal to or greater than twice the frequency
associated with the finest detail in the image (edges).

To advance click enter or page down to go back use page up 10

 Reconstruction
If the sampling frequencies !us and !vs are greater than twice
of the bandlimits i.e. !us 2!10, !vs 2!20 then X(!1, !2)
can be recovered from Xs(!1, !2) by a 2-D ideal low-pass filter
(interpolation filter) with frequency response
⇢
u v !1 , ! 2 2 R
H(!1, !2) =
0 otherwise

where R is any region whose boundary aR is contained within the

region between R1 and R2 as shown in the Figure. Then

X̃(!1, !2) = H(!1, !2)Xs(!1, !2) = X(!1, !2)

i.e. exact reconstruction.

To advance click enter or page down to go back use page up 11
 A
! !typical X choice
! for RX is a rectangular region, e.g. R =
us !us !vs !vs
2 , 2 ⇥ 2 , 2 for which the impulse response is the
ideal 2-D interpolation function i.e.

h(u, v) = Sinc(u!us)sinc(v!vs)

That is, X(!1, !2) = H(!1, !2) · Xs(!1, !2), gives

x̃(u, v) = h(u, v) ⇤ ⇤xs(u, v)

1
= x(m u, n v)sinc(!us(u m u))
m,n= 1

sinc(!vs(v n v))

To advance click enter or page down to go back use page up 12

 Remarks
1. The above equation is an infinite order interpolation that
reconstructs the continuous function x(u, v) from its samples
x(m u, n v).
2. For a rectangular passband with size W1 ⇥ W2, the
impulse response of the interpolation filter is h(u, v) =
sinc(uW1)sinc(vW2).

Undersampling and Aliasing E↵ects

If the sampling frequencies are below the Nyquist rates i.e. !us <
2!10 and !vs < 2!20, then the periodic replications of X(!1, !2)
will overlap, resulting in a distorted spectrum Xs(!1, !2) from
which X(!1, !2) cannot be recovered. The frequencies above
half the sampling frequencies, that is, above !2us , !2vs are called
To advance click enter or page down to go back use page up 13
 the ”fold-over frequencies”. This overlapping causes some of the
high frequencies (or fold-over frequencies) in the original image to
appear as low frequencies (below !2us , !2vs ) in the sampled image.
This phenomenon is called ”Aliasing”. Aliasing cannot be removed
by post filtering but can be avoided by pre low pass filtering the
image so that its bandlimits are less than one-half of the sampling
frequencies.

In images aliasing causes edge smearing and loss of details. The

spectrum of an undersampled image can be written as

1
Xs(!1, !2) = [X(!1, !2) + E(!1, !2)]
u v
To advance click enter or page down to go back use page up 14
 where
1
E(!1, !2) = X(!1 k!us, !2 l!vs)
k, l = 1
(k, l) 6= (0, 0)

After the filtering with a 2-D LPF

⇢
u v |!1|  !2us , |!2|  !vs
H(!1, !2) = 2
0 otherwise

we get X̃(!1, !2) = H(!1, !2)Xs(!1, !2). In the spatial domain,

we get

x̃(u, v) = x(u, v) + e(u, v)

To advance click enter or page down to go back use page up 15
 where
Z !us Z !vs
1 2 2
e(u, v) = 2 E(!1, !2) exp[j(!1u + !2v)]d!1d!2
4⇡ !us
2
!vs
2

represents the aliasing error artifact in the reconstructed image

after the filtering.

Example: An image described by the function

x(u, v) = 2 cos (3u + 4v)

is sampled at u = v = 0.4⇡. Find the reconstructed image

x̃(u, v).

To advance click enter or page down to go back use page up 16

 Expand

cos(3u + 4v) = {ej(3u+4v) + e j(3u+4v)

}/2

and use the property F{ej!0t} = 2⇡ (! !0), to find the 2D

spectrum of x(u, v) as

X(!1, !2) = (2⇡)2[ (!1 3, !2 4) + (!1 + 3, !2 + 4)]

which is bandlimited since X(!1, !2) = 0 for |!1| > 3,|!2| > 4
Thus !10 = 3 and !20 = 4. Also !us = 2⇡u = 5 and !vs = 2⇡v = 5
which are less than the Nyquist frequencies 2!10 = 6 and 2!20 = 8.
Thus aliasing is inevitable. The spectrum of the sampled image is
1
1 2⇡ 2⇡
Xs(!1, !2) = X(!1 k, !2 l)
u v u v
k,l= 1

To advance click enter or page down to go back use page up 17

 1
= 25 [ (!1 3 5k, !2 4 5l)
k,l= 1

+ (!1 + 3 5k, !2 + 4 5l)]

The LPF has a rectangular passband with cuto↵ frequencies at half

the Nyquist frequencies i.e.

⇢
(0 · 4⇡)2 |!1|  2.5, |!2|  2.5
H(!1, !2) =
0 otherwise

After filtering we obtain

X̃(!1, !2) = (2⇡)2[ (!1 2, !2 1) + (!1 + 2, !2 + 1)]

To advance click enter or page down to go back use page up 18
 which gives

x̃(u, v) = 2 cos (2u + v)

Remarks
1. Any frequency component in the original image which is above
[ !2us , !2vs ] by ( !u, !v ) is reproduced (or aliased) as a lower
frequency component at [ !2us !u, !2vs !v ]. In the previous
example, the frequency components 3,4 are above !2us = 2.5 and
2 = 2.5 by !u = 0.5 and !v = 1.5, respectively. Thus,
!vs

these frequencies will be aliased at 2.5 0.5 and 2.5 1.5, which
give x̃(u, v) = 2 cos (2u + v).
2. Images corrupted by additive wideband noise have spectra with
long tails. Thus, sampling based upon the bandlimits of the
To advance click enter or page down to go back use page up 19
 original image will result in aliasing e↵ects as the tail of the
spectrum will fold-over into the bandlimits of the image. This
obviously causes additional noise in the reconstructed image.
To prevent this problem the image must be prefiltered prior to
sampling.

To advance click enter or page down to go back use page up 20

 Review of Key Concepts
Two Dimensional Sampling
f s ( x, y )  f ( x, y )   s ( x, y , x, y )
 
 
n -m -
f ( x,y )  δ( x - n  x , y - m  y )
 
 
n - m -
f ( n  x , m  y )  δ( x - n  x , y - m  y )

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019

 Fourier Transform of Sampled Image
Ff s (u )  F  f s ( x, y )
 F  s  x, y, x, y   f ( x, y )
 combu  x, v  y   F  f ( x, y )
n  m    n   m 
    x u  , y v   * F(u , v)
n   m     x   y 
1 n  m  n m
  
xy n   m  
 (u 
x
, v 
y
) * F(u , v)
 
1 n m
  
xy n   m  
F(u 
x
, v 
y
)

The result: Replicated F(u,v), or “islands” every 1/x in u, and 1/y in v.

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019

 Review of Key Concepts (5)
Two Dimensional Sampling

An sufficiently small sampling interval is important …

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019

 The Nyquist Theorem

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019

 Two Dimensional Sampling

Nyquist Theorem:
In order to restore the original function, the sampling rate must be greater
than twice the highest frequency component of the function.

Nyquist Sampling Interval:

The maximum sampling interval allowed without introduce aliasing is

1
x 
2uc

NPRE 435, Principles of Imaging with Ionizing Radiation, Fall 2019