FOURIER TRANSFORM

The Fourier transform is a mathematical tool widely used in image processing. We need to distinguish among the transforms for continuos functions on R or on a finite interval, and discretely supported functions.

Before listing the formulas of the Fourier Transforms, we introduce the convolution of two function or two sequences:

F * G (x) = ∫R F(x-y) G(y) dy
  = ∫R F(y) G(x-y) dy
(F * G)k = ∑h Fk-h Gh
  = ∑h Fh Gk-h

Continuous functions on R
The Fourier transform is a linear operator: this means that the transform of F+G is equal to the sum of the two transforms, and the transform of a F is equal to a times the transform of F. From a mathematical point of view is well defined for function in L1 and maps them in Loo. It is then extended by continuity to a map over L2 where it turns out to be unitary (norm preserving, and invertible).

F^(v) = 1/(2 π) ∫R e(-i v x)   F(x) dx
F(x) = ∫R e(i v x)   F^(v) dv
(F * G)^ (v) = 2 π F^ (v) G^ (v)
| F |2 = 2 π | F^ |2
< F | G > = 2 π < F^ | G^ >

The first two identities are the definition of the Fourier transform and its inverse. The third identity is the convolution theorem. The fourth identity is called Parceval theorem and relates the L2 norms of a function and its transforms. The last identity generalizes this to the inner products.
In particular we notice that the Fourier transform of the "delta function" is constant D^(v) = 1/(2 π).

Other important identities are:

G(t) = F(t-a) ==> G^(v) = e(-i v a) F^(v)
G(t) = F(a t) ==> G^(v) = 1/a F^(v/a)

Continuous functions on the interval [-B, B]

F^k = 1/(2 B) ∫[-B,B] e(-i k x π/B) F(x) dx
F(x) = ∑k e(i k x π/B) Fk
(F^ * G^ )k = ( (F G)^ )k
∑k F^k G^*k = 1/(2 B) ∫[-B,B] F(x) G*(x) dx

The inverse identity is a consequence of an important result known as Poisson formula:

1/(2 B) ∑k e(i k v π/B) = ∑n D( v + 2 B n )

Discrete function
This case is not really different from the previous one. It is just the same formulas from a different perspective. The function is a sequence of values at coordinates n T, where T denotes the sampling spacing. As a consequence its fourier transform is periodic with period 2/T.

F^(y) = 2/T ∑n e(-i n y π T) Fn T
Fn T = ∫[-1/T,1/T] e(i n y π T) F^(y) dy

Band-limited function
These functions have Fourier transform with compact support inside the interval [-1/T, 1/T].
Essentially the formulas of the previous case holds for band-limited functions too, however the transform formula produces a periodic function which coincides with the original band-limited transform only in the interval [-1/T,1/T].

Marco Corvi - Page hosted by geocities.com.