FINITE FOURIER TRANSFORM

In practical image processing one considers finite signals, ie, functions defined on finitely many discrete points, Fk for k ranging from 0 to N-1. Such F can be considered as a periodic signal with period N.
The Fourier transform of F is

F^v = 1/N ∑k=0N-1 e(-2πi k v/N) Fk
is also periodic with period N. Its inverse is
Fk = ∑v=0N-1 e(2πi k v/N) F^v

The convolution of finite signals is

(F * G)k = ∑n Fn Gk-n
and
(F * G)^v = N F^v G^v

If F is real it has N independent components (degrees of freedom), its Fourier transform is complex but it satisfies

F^*v = F^N-v
therefore
F^0 is real
F^N/2 is real
F^v for intermediate v is complex
Conversely if F is even (ie, symmetric: Fk=FN-k) then F^ is real. If F is odd (ie, antisymmetric) then F^ is purely imaginary (and has only N/2 -1 degrees of freedom).

These symmetries are also present for the 2-dim Fourier transforms.

 

Marco Corvi - Page hosted by geocities.com.