2D Fourier Transform

(1)

2D Fourier Transform

(2)

Overview

• Signals as functions (1D, 2D) – Tools

• 1D Fourier Transform

– Summary of definition and properties in the different cases

• CTFT, CTFS, DTFS, DTFT

• DFT

• 2D Fourier Transforms – Generalities and intuition – Examples

– A bit of theory

• Discrete Fourier Transform (DFT)

• Discrete Cosine Transform (DCT)

(3)

Signals as functions

• Continuous functions of real independent variables – 1D: f=f(x)

– 2D: f=f(x,y) x,y

– Real world signals (audio, ECG, images)

• Real valued functions of discrete variables – 1D: f=f[k]

– 2D: f=f[i,j]

– Sampled signals

• Discrete functions of discrete variables – 1D: f^d=f^d[k]

– 2D: f^d=f^d[i,j]

– Sampled and quantized signals

(4)

Images as functions

• Gray scale images: 2D functions

– Domain of the functions: set of (x,y) values for which f(x,y) is defined : 2D lattice [i,j] defining the pixel locations

– Set of values taken by the function : gray levels

• Digital images can be seen as functions defined over a discrete domain {i,j: 0<i<I, 0<j<J}

– I,J: number of rows (columns) of the matrix corresponding to the image – f=f[i,j]: gray level in position [i,j]

(5)

Example 1: δ function

[ ]

⎩⎨⎧

≠

=

= =

j i j

i

j j i

i 0 , 0;

0 , 1

δ

[ ]

⎩⎨

⎧ = =

=

− otherwise

J j J i

j

i 0

; 0 , 1

δ

(6)

Example 2: Gaussian

2 2 2

2

2 ) 1

,

( ^σ

π σ

y x

e y

x f

+

=

2 2 2

2

2 ] 1

,

[

^σ

π σ

j i

e j

i f

+

=

Continuous function

Discrete version

(7)

Example 3: Natural image

(8)

Example 3: Natural image

(9)

Convolution

( ) ( ) ( ) ( ) ( )

[ ] [ ] [ ] [ ] [ ]

k

c t f t g t f g t d

c n f n g n f k g k n

τ τ τ

+∞

−∞

+∞

=−∞

= ∗ = −

∫

∑

(10)

( , ) ( , ) ( , ) ( , ) ( , )

[ , ] [ , ] [ , ]

k k

c x y f x y g x y f g x y d d

c i k f n m g i n k m

τ ν τ ν τ ν

+∞ +∞

−∞ −∞

+∞ +∞

=−∞ =−∞

= ⊗ = − −

= − −

∫ ∫

∑ ∑

[n,m]

filter impulse response rotated by 180 deg

2D Convolution

• Associativity

• Commutativity

• Distributivity

(11)

g(k,l)

img(k,l) g(a-k,b-l) 1. fold about origin

2. displace by ‘a’ and ‘b’

img(k,l) k

l

g(a-k,b-l)

a

b

Tricky part: borders

• (zero padding, mirror...)

3. compute integral of the box

2D Convolution

(12)

Convolution

Filtering with filter h(x,y)

sampling property of the delta function

(13)

Fourier Transform

• Different formulations for the different classes of signals

– Summary table: Fourier transforms with various combinations of continuous/discrete time and frequency variables.

– Notations:

• CT: continuous time

• DT: Discrete Time

• FT: Fourier Transform (integral synthesis)

• FS: Fourier Series (summation synthesis)

• P: periodical signals

• T: sampling period

• ω_s: sampling frequency (ω_s=2π/T)

• For DTFT: T=1 → ω_s=2π

(14)

1D FT: basics

(15)

Fourier Transform: Concept

■ A signal can be

represented as a weighted sum of sinusoids.

■ Fourier Transform is a change of basis, where the basis functions consist of sines and cosines

(complex exponentials).

(16)

Fourier Transform

• Cosine/sine signals are easy to define and interpret.

• However, it turns out that the analysis and manipulation of

sinusoidal signals is greatly simplified by dealing with related signals called complex exponential signals.

• A complex number has real and imaginary parts: z = x + j*y

• A complex exponential signal: r*exp(j*a) =r*cos(a) + j*r*sin(a)

(17)

Overview

Self dual D

P D

P Discrete Time

Fourier Series (DTFS)

Dual with CTFS C

P D

Discrete Time Fourier Transform (DTFT)

Dual with DTFT D

C P (Continuous Time)

Fourier Series (CTFS)

Self- dual C

C (Continuous Time)

Fourier Transform (CTFT)

Duality Analysis/Synthesis

Frequency Time

Transform

( ) ^{( )}

( ) 1 ( )

2

j t t

j t

F f t e dt

f t F e d

ω

ω ω

ω

ω ω

π

= −

=

∫

/ 2

2 /

/ 2

2 /

[ ] ( )

( ) [ ]

T

j kt T

T

j kt T k

F k f t e dt

f t F k e

π

−

=

∫

∑ ( )

( )

2 /

/ 2

2 /

/ 2

[ ] [ ] 1

s

j n

j t

n

j n

j t s

F e f n e

f n F e e d

ω πω ω

ω

ω πω ω ω

ω ω

−

=

∑

∫

1

2 /

1 0

2 /

0

[ ] 1 [ ]

[ ] [ ]

N

j kn T N n

j kn T n

F k f n e

N

f n F k e

π π

− −

− =

=

∑

(18)

Dualities

FOURIER DOMAIN SIGNAL DOMAIN

Sampling Periodicity

DTFT

CTFS

Sampling+Periodicity _DTFS/DFT Sampling +Periodicity

(19)

Discrete time signals

• Sequences of samples

• f[k]: sample values

• Assumes a unitary spacing among samples (T_s=1)

• Normalized frequency Ω

• Transform

– DTFT for NON periodic sequences

– CTFS for periodic sequences – DFT for periodized sequences

• All transforms are 2π periodic

• Sampled signals

• f(kT_s): sample values

• The sampling interval (or period) is T_s

• Non normalized frequency ω

• Transform

– DTFT – CSTF – DFT

– BUT accounting for the fact that the sequence values have been generated by sampling a real signal → f_k=f(kT_s)

• All transforms are periodic with period ω_s

T

s

ω

Ω =

(20)

CTFT

• Continuous Time Fourier Transform

• Continuous time a-periodic signal

• Both time (space) and frequency are continuous variables – NON normalized frequency ω is used

• Fourier integral can be regarded as a Fourier series with fundamental frequency approaching zero

• Fourier spectra are continuous

– A signal is represented as a sum of sinusoids (or exponentials) of all frequencies over a continuous frequency interval

( ) ^{( )}

( ) 1 ( ) 2

j t t

j t

F f t e dt

f t F e d

ω

ω ω

ω

ω ω

π

=

−

=

∫

analysis

synthesis Fourier integral

(21)

CTFT: change of notations

■ Fourier Transform of a 1D continuous signal

( ) ( )

^{j x}

F ω

^∞

f x e

⁻ ^ω

dx

−∞

= ∫

■ Inverse Fourier Transform

( ) 1 ( )

2 f x F ω e

j x^ω

d ω π

∞

−∞

= ∫

( ) ( )

cos sin

e⁻j x^ω = ωx − j ωx

“Euler’s formula”

Change of notations:

2 2 2

x y

u u

v

ω π

→

⎧ →

⎨ →

⎩

(22)

Then CTFT becomes

■ Fourier Transform of a 1D continuous signal

( ) ( )

^j2 ^ux

F u f x e

^π

dx

∞ −

−∞

= ∫

■ Inverse Fourier Transform

( ) ( )

^j2 ^ux

f x F u e

^π

du

∞

−∞

= ∫

( ) ( )

2

cos 2 sin 2

j ux

e

⁻ ^π

= π ux − j π ux

“Euler’s formula”

(23)

CTFS

• Continuous Time Fourier Series

• Continuous time periodic signals – The signal is periodic with period T₀

– The transform is “sampled” (it is a series)

/ 2

2 / / 2

2 /

[ ] ( )

( ) [ ]

T

j kt T T

j kt T k

F k f t e dt

f t F k e

π

−

=

∫

∑

0

0 0

/ 2

0 / 2

0

1 ( )

( ) 2

o

T

jn t

n T

T

jn t

T n

n

D f t e dt

T

f t D e

T

ω

ω π

−

=

∫

∑

our notations table notations

fundamental frequency

T₀↔T D_n ↔F[k]

(24)

CTFS

• Representation of a continuous time signal as a sum of orthogonal components in a complete orthogonal signal space

– The exponentials are the basis functions

• Fourier series are periodic with period equal to the fundamental in the set (2π/T₀)

• Properties

– even symmetry → only cosinusoidal components – odd symmetry → only sinusoidal components

(25)

CTFS: example 1

(26)

CTFS: example 2

(27)

From sequences to discrete time signals

• Looking at the sequence as to a set of samples obtained by sampling a real signal with frequency ω_s we can still use the

formulas for calculating the transforms as derived for the sequences by

– Stratching the time axis (and thus squeezing the frequency axis if T_s>1)

– Enclosing the sampling interval T_s in the value of the sequence samples (DFT)

k s

( )

s

f = T f kT 2 2

s

T

T ω

π ω π Ω =

→ =

(28)

DTFT

• Discrete Time Fourier Transform

• Discrete time a-periodic signal

• The transform is periodic and continuous with period

( )

2 /

/ 2

2 /

/ 2

[ ] [ ] 1

s

j n

j t

n

j n

j t s

F e f n e

f n F e e d

πω ω ω

ω

πω ω ω

ω

ω ω

−

=

∑

∫

( )

2

( ) [ ]

[ ] 1 2

j k k

j k

F f k e

f k F e d

π

+∞ − Ω

=−∞

Ω

Ω =

= Ω Ω

∑

∫

0 2π Ω =

( )

_c

s

F F

T

⎛ ⎞Ω

Ω = ⎜ ⎟

normalized ⎝ ⎠

frequency

non normalized frequency

Ts

ω

Ω =

s 2 / s

T = π ω

(29)

Discrete Time Fourier Transform (DTFT)

• F(Ω) can be obtained from F_c(ω) by replacing ω with Ω/T_s. Thus F(Ω) is identical to F_c(ω) frequency scaled by a factor 1/T_s

– T_s is the sampling interval in time domain

• Notations

( )

( ) ( )

( )

² ^/

2 2

( ) 2 /

( ) [ ] ( ) [ ] ^s

c s

s s

j k j k

s

k k

F F

T T T

T T

F F T F

F f k e F T F f k e ^{πω ω}

π π

ω ω

ω πω ω

ω ω

+∞ +∞

−

− Ω

=−∞ =−∞

⎛ ⎞Ω

Ω = ⎜ ⎟

⎝ ⎠

= → =

= Ω → Ω =

Ω → =

Ω =

∑

→ = =

∑

_ _

periodicity of the spectrum

normalized frequency (the spectrum is 2π-periodic)

(30)

DTFT: unitary frequency

( )

2

1 2

2 2

2 1 1

2 2

1 2

2 1

2

2 2

( ) [ ] ( ) [ ]

[ ] 1 ( ) [ ] ( ) ( )

2 ( ) [ ]

[ ] ( )

j k j ku

k k

j k j ku j ku

j ku k

j ku

u f

F f k e F u f k e

f k F e d f k F u e du F u e du

F u f k e

f k F u e du

π

π π

π

π ω π

π

∞ ∞

− Ω −

=−∞ =−∞

Ω

−

∞ −

=−∞

−

Ω = =

Ω = → =

= Ω Ω → = =

⎧ =

⎪ ⎪⎪

⎨ ⎪ =

⎪ ⎪⎩

∑ ∑

∫ ∫ ∫

∑

∫

NOTE: when T_s=1, Ω=ω and the spectrum is 2π-periodic. The unitary frequency u=2π/ Ω corresponds to the signal frequency f=2π/ω.

This could give a better intuition of the transform properties.

(31)

Connection DTFT-CTFT

0 Ts 4Ts

0 1 4

t

k

ω

Ω 0

0

2π/Ts

2π Fc(ω)

F(Ω)

sampling periodization

f(t)

f(kT_s)

Fc(ω) _

f[k]

(32)

Differences DTFT-CTFT

• The DTFT is periodic with period Ω_s=2π (or ω_s=2π/T_s)

• The discrete-time exponential e^jΩk has a unique waveform only for values of Ω in a continuous interval of 2π

• Numerical computations can be conveniently performed with the Discrete Fourier Transform (DFT)

(33)

DTFS

• Discrete Time Fourier Series

• Discrete time periodic sequences of period N₀ – Fundamental frequency

0 2 / Nπ 0

Ω =

1

2 / 1 0

2 / 0

[ ] 1 [ ]

[ ] [ ]

N

j kn T N n

j kn T n

F k f n e

N

f k F k e

π

− −

− =

=

∑

0

1

0 0 1

0

1 [ ]

[ ]

N

jr k r

k N

jr k r

r

D f k e

N

f k D e

− − Ω

=

− Ω

=

∑

(34)

Discrete Fourier Transform (DFT)

• The DFT transforms N₀ samples of a discrete-time signal to the same number of discrete frequency samples

• The DFT and IDFT are a self-contained, one-to-one transform pair for a length-N₀ discrete-time signal (that is, the DFT is not merely an

approximation to the DTFT as discussed next)

• However, the DFT is very often used as a practical approximation to the DTFT

0 0

1 1 2

0 0

1 1 2

0 0

0

1 1

2

N N j rk

jr k N

r k k

k k

N N jr k

jr k N

k r r

k k

F f e f e

f F e F e

N N

N

π

− − −

− Ω

= =

− −

Ω

= =

Ω =

∑ ∑

(35)

DFT

k zero padding

0 N₀

0 2π r

F(Ω)

2π/N₀ 4π

(36)

Discrete Cosine Transform (DCT)

• Operate on finite discrete sequences (as DFT)

• A discrete cosine transform (DCT) expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies

• DCT is a Fourier-related transform similar to the DFT but using only real numbers

• DCT is equivalent to DFT of roughly twice the length, operating on real data with even symmetry (since the Fourier transform of a real and even function is real and even), where in some variants the input and/or output data are shifted by half a sample

• There are eight standard DCT variants, of which four are common

• Strong connection with the Karunen-Loeven transform – VERY important for signal compression

(37)

DCT

• DCT implies different boundary conditions than the DFT or other related transforms

• A DCT, like a cosine transform, implies an even periodic extension of the original function

• Tricky part

– First, one has to specify whether the function is even or odd at both the left and right boundaries of the domain

– Second, one has to specify around what point the function is even or odd

• In particular, consider a sequence abcd of four equally spaced data points, and say that we specify an even left boundary. There are two sensible possibilities: either the data is even about the sample a, in which case the even extension is dcbabcd, or the data is even about the point halfway between a and the previous point, in which case the even extension is dcbaabcd (a is repeated).

(38)

Symmetries

(39)

DCT

0

1

0

0 0

1 0

0 0 0

cos 1 0,...., 1

2

2 1 1

2 cos 2

N

k n

n

N

n k

k

X x n k k N

N

x X X k k

N N

π

−

=

−

=

⎡ ⎛ ⎞ ⎤

= ⎢⎣ ⎜⎝ + ⎟⎠ ⎥⎦ = −

⎧ ⎡ ⎛ ⎞⎤⎫

= ⎨⎩ + ⎢⎣ ⎜⎝ + ⎟⎠⎥⎦⎬⎭

∑

• Warning: the normalization factor in front of these transform definitions is merely a convention and differs between treatments.

– Some authors multiply the transforms by (2/N₀)^1/2 so that the inverse does not require any additional multiplicative factor.

• Combined with appropriate factors of √2 (see above), this can be used to make the transform matrix orthogonal.

(40)

Sinusoids

• Frequency domain characterization of signals

Frequency domain Signal domain

( ) ( )

^{j t}

F ω

^+∞

f t e

⁻ ^ω

dt

−∞

= ∫

(41)

Gaussian

(42)

rect

sinc function

(43)

Images vs Signals

1D

• Signals

• Frequency

– Temporal – Spatial

• Time (space) frequency characterization of signals

• Reference space for

– Filtering

– Changing the sampling rate – Signal analysis

– ….

2D

• Images

• Frequency

– Spatial

• Space/frequency characterization of 2D signals

• Reference space for

– Filtering

– Up/Down sampling – Image analysis – Feature extraction – Compression

– ….

(44)

2D spatial frequencies

• 2D spatial frequencies characterize the image spatial changes in the horizontal (x) and vertical (y) directions

– Smooth variations -> low frequencies – Sharp variations -> high frequencies

x y

ω_x=1

ω_y=0 ω_x=0

ω_y=1

(45)

2D Frequency domain

ω_x ω_y

Large vertical

frequencies correspond to horizontal lines

Large horizontal

frequencies correspond to vertical lines

Small horizontal and vertical frequencies correspond smooth grayscale changes in both directions

Large horizontal and vertical frequencies correspond sharp grayscale changes in both directions

(46)

Vertical grating

ω_x ω_y

0

(47)

Double grating

ω_x ω_y

0

(48)

Smooth rings

(49)

2D box

2D sinc

(50)

Margherita Hack

(51)

Einstein

log amplite of the spectrum

(52)

What we are going to analyze

• 2D Fourier Transform of continuous signals (2D-CTFT)

• 2D Fourier Transform of discrete signals (2D-DTFT)

• 2D Discrete Fourier Transform (2D-DFT)

( ) ( )

^{j t}

, ( ) ( )

^{j t}

F ω

^+∞

f t e

⁻ ^ω

dt f t

^+∞

F ω e

^ω

dt

−∞ −∞

= ∫ = ∫

0 0

0

1 1

0

0 0 0 0

1 2

[ ] , [ ] ,

N N

jr k jr k

r N r

k r

F f k e f k F e

N N

π

− −

− Ω Ω

= =

= ∑ = ∑ Ω =

2

( ) [ ] , [ ] 1 ( )

2

j k j k

k

F f k e f k F e dt

π

∞ − Ω Ω

=−∞

Ω = ∑ = ∫ Ω

1D

(53)

2D Continuous Fourier Transform

• Continuous case (x and y are real) – 2D-CTFT (notation 1)

( ) ⁽ ⁾

⁽ ⁾

( )

2

( )

⁽ ⁾

ˆ , ,

1 ˆ

, ,

4

x y

j x y

x y

j x y

x y x y

f f x y e dxdy

f x y f e d d

ω ω

ω ω ω ω

π

+∞ − +

−∞

+∞ +

−∞

=

∫

( ) ( ) ( ) ( )

( ) ( )

* *

2 2 2

2

1 ˆ

, , , ˆ ,

4

1 ˆ

, ,

4

x y x y x y

x y x y

f x y g x y dxdy f g d d

f g f x y dxdy f d d

ω ω ω ω ω ω π

ω ω ω ω π

=

= → =

∫∫ ∫∫

Parseval formula

Plancherel equality

(54)

2D Continuous Fourier Transform

• Continuous case (x and y are real) – 2D-CTFT

( ) ( )

⁽ ⁾

( ) ( )

⁽ ⁾

( )

⁽ ⁾

( )

2

2 2 2

2 2

ˆ , ,

1 ˆ

, , 2

4 1 ˆ , 2

4

x y

j ux vy

u v

f u v f x y e dxdy

f x y f u v e dudv

f u v e dudv

π

ω π ω π

π π

+∞ − +

−∞

+∞ +

−∞

+∞ +

−∞

=

= =

=

∫

(55)

2D Continuous Fourier Transform

• 2D Continuous Fourier Transform (notation 2)

( ) ( )

⁽ ⁾

( ) ( )

⁽ ⁾

2

ˆ , ,

, ˆ ,

j ux vy

f u v f x y e dxdy

f x y f u v e dudv

π

+∞ − +

−∞

+∞ +

−∞

=

= =

∫

2

ˆ

2

( , ) ( , )

f x y dxdy f u v dudv

∞ ∞ ∞ ∞

−∞ −∞ −∞ −∞

∫ ∫ = ∫ ∫

Plancherel’s equality

(56)

2D Discrete Fourier Transform

0

0 0

1

0

1

0 0

0

[ ] [ ] 1

2

N

jr k r

k

N

jr k

N r

r

F f k e

f k F e

N N

π

− − Ω

=

− Ω

=

= Ω =

∑

0 0

0

0 0

1 1

( )

0 0

1 1

( )

2

0 0

0

[ , ] [ , ]

[ , ] 1 [ , ]

2

N N

j ui vk

i k

N N

j ui vk N

u v

F u v f i k e

f i k F u v e

N

N π

− −

− Ω +

= =

− −

Ω +

= =

=

= Ω =

∑ ∑

The independent variable (t,x,y) is discrete

(57)

Delta

• Sampling property of the 2D-delta function (Dirac’s delta)

• Transform of the delta function

0 0 0 0

( x x y , y ) ( , ) f x y dxdy f x y ( , )

∞

δ

−∞

− − =

∫

( ^{( , )} ) ^{( , )}

^j^{2 (}^{ux vy}⁾

¹

F δ x y

^{∞ ∞}

δ x y e

⁻ ^π ⁺

dxdy

−∞ −∞

= ∫ ∫ =

(

( 0, 0)

)

( 0, 0) ^j^{2 (}^{ux vy}⁾ ^j^{2 (}^ux⁰ ^vy⁰⁾

F δ x x y y ^{∞ ∞} δ x x y y e⁻ ^π ⁺ dxdy e⁻ ^π ⁺

−∞ −∞

− − =

∫ ∫

− − = ^shifting_property

(58)

Constant functions

■ Fourier Transform of the constant (=1 for all x and y)

{ }

^{2 (} ⁾

( , ) 1 ,

( , )

j ux vy

k x y x y

F k

^{∞ ∞}

e

⁻ ^π ⁺

dxdy δ u v

−∞ −∞

= ∀

= ∫ ∫ =

{ }

1 2 ( ) 2 (0 0)

( , ) ( , )

^j ^{ux vy} ^j ^{x v}

1 F

⁻

δ u v

^{∞ ∞}

δ u v e

^π ⁺

dudv e

^π ⁺

−∞ −∞

= ∫ ∫ = =

Take the inverse Fourier Transform of the impulse function

(59)

Trigonometric functions

• Cosinusoidal function oscillating along the x axis – Constant along the y axis

{ }

^{2 (} ⁾

2 ( ) 2 ( )

2 ( )

( , ) cos(2 )

cos(2 ) cos(2 )

2

j ux vy

j fx j fx

j ux vy

s x y fx

F fx fx e dxdy

e e

e dxdy

π

π π

π

π ^{∞ ∞} π ⁻ ⁺

−∞ −∞

∞ ∞ −

− +

−∞ −∞

=

= =

⎡ + ⎤

= ⎢ ⎥

⎣ ⎦

∫ ∫

( ) ( )

2 ( ) 2 ( )

1 1

( ) ( )

2 2

j u f x j u f x

e ^π e ^π dxdy δ u f δ u f

∞ ∞

− − − +

−∞ −∞

⎡ ⎤

=

∫ ∫

⎣ + ⎦ = ⎡⎣ − + + ⎤⎦

(60)

Vertical grating

ω_x ω_y

0

(61)

Ex. 1

(62)

Ex. 2

(63)

Ex. 3

Magnitudes

(64)

Examples

(65)

Properties

■ Linearity

■ Shifting

■ Modulation

■ Convolution

■ Multiplication

■ Separability

( , ) ( , ) ( , ) ( , ) af x y + bg x y ⇔ aF u v + bG u v

( , ) * ( , ) ( , ) ( , ) f x y g x y ⇔ F u v G u v

( , ) ( , ) ( , ) * ( , ) f x y g x y ⇔ F u v G u v

( , ) ( ) ( ) ( , ) ( ) ( ) f x y = f x f y ⇔ F u v = F u F v

0 0

2 ( )

0 0

( , )

^j ^ux ^vy

( , )

f x − x y − x ⇔ e

⁻ ^π ⁺

F u v

0 0

2 ( )

0 0

( , ) ( , )

j u x v y

e

^π ⁺

f x y ⇔ F u u v v − −

(66)

Separability

2 ( )

( , ) ( , )

^j ^{ux vy}

F u v f x y e

^π

dxdy

∞ ∞ − +

−∞ −∞

= ∫ ∫

2 2

( , )

^j ^ux ^j ^vy

f x y e

^π

dx e

^π

dy

∞ ∞

− −

−∞ −∞

⎡ ⎤

= ⎢ ⎥

⎣ ⎦

∫ ∫

( , )

^j2 ^vy

F u y e

^π

dy

∞ −

−∞

= ∫

2D Fourier Transform can be implemented as a sequence of 1D Fourier Transform operations performed

independently along the two axis

(67)

• Fourier Transform of a 2D a-periodic signal defined over a 2D discrete grid

– The grid can be thought of as a 2D brush used for sampling the continuous signal with a given spatial resolution (T_x,T_y)

2D Fourier Transform of a Discrete function

2

( ) [ ] , [ ] 1 ( )

2

j k j k

k

F f k e f k F e dt

π

∞ − Ω Ω

=−∞

Ω = ∑ = ∫ Ω

( )

1 2

2 2 2

( , ) [ , ]

[ ] 1 ( , )

4

x y

j k k

x y

k k

j k k

x y x y

F f k k e

f k F e d

π

π π

− Ω + Ω +∞ +∞

=−∞ =−∞

Ω + Ω

Ω Ω =

= Ω Ω Ω Ω

∑ ∑

∫ ∫

(68)

Unitary frequency notations

1 2

2 ( )

1 2

1/ 2 1/ 2

2 ( )

1 2

1/ 2 1/ 2

2 2

( , ) [ , ]

[ , ] ( , )

x y

j k u k v

k k

j k u k v

u v

F u v f k k e

f k k F u v e dudv

π

π π

+∞ +∞

− +

=−∞ =−∞

− +

− −

⎧ Ω =

⎨Ω = ⎩

=

∑ ∑

∫ ∫

• The integration interval for the inverse transform has width=1 instead of 2π

– It is quite common to choose

1 1

2 u v, 2

− ≤ <

(69)

Properties

• Periodicity: 2D Fourier Transform of a discrete a-periodic signal is periodic with period

– The period is 1 for the unitary frequency notations and 2π for normalized frequency notations. Referring to the firsts:

( )

2 ( ) ( )

( , ) [ , ] ^j ^{u k m} ^{v l n}

m n

F u k v l f m n e ^π

∞ ∞

− + + +

=−∞ =−∞

+ + =

∑ ∑

( )

2 2 2

[ , ]

^j ^{um vn} ^j ^km ^j ^ln

m n

f m n e

^π

e

^π

e

^π

∞ ∞

− + − −

=−∞ =−∞

= ∑ ∑

2 ( )

[ , ]

^j ^{um vn}

m n

f m n e

^π

∞ ∞

− +

=−∞ =−∞

= ∑ ∑

1 1

( , ) F u v

=

Arbitrary integers

(70)

Properties

• Linearity

• shifting

• modulation

• convolution

• multiplication

• separability

• energy conservation properties also exist for the 2D Fourier Transform of discrete signals.

• NOTE: in what follows, (k₁,k₂) is replaced by (m,n)

(71)

Fourier Transform: Properties

■ Linearity

■ Shifting

■ Modulation

■ Convolution

■ Multiplication

■ Separable functions

■ Energy conservation

[ , ] [ , ] ( , ) ( , ) af m n + bg m n ⇔ aF u v + bG u v

0 0

2 ( )

0 0

[ , ]

^j ^um ^vn

( , )

f m m n n − − ⇔ e

⁻ ^π ⁺

F u v

[ , ] [ , ] ( , ) * ( , ) f m n g m n ⇔ F u v G u v

[ , ]* [ , ] ( , ) ( , ) f m n g m n ⇔ F u v G u v

0 0

2 ( )

0 0

[ , ] ( , )

j u m v n

e

^π ⁺

f m n ⇔ F u u v v − −

[ , ] [ ] [ ] ( , ) ( ) ( ) f m n = f m f n ⇔ F u v = F u F v

2 2

[ , ] ( , )

m n

f m n F u v dudv

∞ ∞ ∞ ∞

=−∞ =−∞ −∞ −∞

∑ ∑ = ∫ ∫

(72)

Impulse Train

■ Define a comb function (impulse train) as follows

,

[ , ] [ , ]

M N

k l

comb m n

^∞ ^∞

δ m kM n lN

=−∞ =−∞

= ∑ ∑ − −

where M and N are integers

2

[ ] comb n

n

1

(73)

2D-DTFT: delta

■ Define Kronecker delta function

■ Fourier Transform of the Kronecker delta function

1, for 0 and 0 [ , ]

0, otherwise

m n

δ m n _{= ⎨} ^⎧ ⁼ ⁼ ^⎫ _⎬

⎩ ⎭

( ) ( )

2 2 0 0

( , ) [ , ]

^j ^{um vn} ^j ^u ^v

1

m n

F u v

^∞ ^∞

δ m n e

⁻ ^π ⁺

e

⁻ ^π ⁺

=−∞ =−∞

⎡ ⎤

= ∑ ∑ ⎣ ⎦ = =

(74)

Fourier Transform: (piecewise) constant

■ Fourier Transform of 1

To prove: Take the inverse Fourier Transform of the Dirac

delta function and use the fact that the Fourier Transform has to be periodic with period 1.

( )

2

[ , ] 1

( , )

j um vn

m n

k l

f m n

F u v e

u k v l

π

δ

∞ ∞

− +

=−∞ =−∞

∞ ∞

=−∞ =−∞

=

⎡ ⎤

= ⎣ ⎦ =

= − −

∑ ∑

(75)

Impulse Train

,

[ , ] [ , ]

M N

k l

comb m n

^∞ ^∞

δ m kM n lN

=−∞ =−∞

− −

∑ ∑

[ ^, ] ¹ ^,

k l k l

k l

m kM n lN u v

MN M N

δ δ

∞ ∞ ∞ ∞

=−∞ =−∞ =−∞ =−∞

⎛ ⎞

− − ⇔ ⎜ ⎝ − − ⎟ ⎠

∑ ∑ ∑ ∑

1 1,

( , )

M N

comb u v

,

[ , ] comb

M N

m n

( )

,

( , ) ,

M N

k l

comb x y

^∞ ^∞

δ x kM y lN

=−∞ =−∞

− −

∑ ∑

• Fourier Transform of an impulse train is also an impulse train:

(76)

Impulse Train

2

[ ] comb n

n u

1 ¹₂

1 2

1 ( )

2 comb u

1 2