Notes 20110308 CIS 6320 Image Processing

From SnOwy - Ed's Wiki Notebook

Cleanup needed ...

Continuing on the DFT and IDFT

Contents 1 IDFT Kernel 2 DFT Kernel 3 Consider a function F 3.1 Justification 4 Let's consider a sequence 5 Consider the function F 6 let f be a function 7 Summary

IDFT Kernel

Memorize this...

• K_u(x) ::= (1/M)e^2jπux/M

DFT Kernel

Memorize this...

• k_x(u) ::= e^-2jπux/M

Consider a function F

• f = Σ_u=0M-1F(u)K_u
  • this is the inverse Fourier transform of F
• this is a general change of basis formula
  • F(u) coordinates in the transform basis
  • returns -- coordinates in the original basis -- this is the inverse Fourier transform
• consider a function f ...
• F = Σ_x=0^M-1f(x)k_x
  • returns -- coordinates in the new basis
• this function F(f) -- is the forward Fourier transform of f (as above)
• F(f) is a function that transforms functions
  • domain: a set of functions
  • co-domain: a set of functions
• F^-1(F) is the inverse Fourier transform of F
  • we must assume hence F() is a bijection
• F is the Fourier transform

Justification

• F^-1(F(f)) = f
  • iff F = F(f) then f = F^-1(F)
• same is true for F(F(F))
• F^-1 º F = H
• F º F^-1 = H
  • H is the identity matrix

Let's consider a sequence

• a sequence is an unbounded ordered collection
• a tuple is a bounded ordered collection
• here's a simple sequence ...
• (arⁱ)_{i ∈ N}
• we assume (a ≠ 0), (r ≠ 0)
• a is the initial term
• r is the common ratio
• Σ_i=0^n-1arⁱ = a(1-rⁿ)/(1-r) when r ≠ 1
• if r = 1, then result is a×n

Consider the function F

• f ::= F^-1(F)
• f(x) = (1/M)Σ_u=0^M-1F(u)e^2jπux/M
• e^jθ = cosθ + jsinθ
  • = cos(-θ) + jsin(-θ)
  • = cosθ - jsinθ
  • = (e^jθ)^*
• f^*(x) = (1/M)Σ_u=0^M-1F^*(u)e^2jπux/M
• f^*(x) = (1/M)F(F^*)(x)
• f = (1/M)F(F^*)^*
  • F^-1(F) = (1/M)F(F^*)^* -- QED
• F is linear ...
• for any functions f1, f2, for any complex number c:
  • F(c1f) = cF(f1) and F(f1 + f2) = F(f1) + F(f2)

let f be a function

• Fhat | Z → C // | u |→ Σ_x=0^M-1f(x)e^-2jπux/M is periodic
• Fhat is an extension of F -- an extention onto the domain Z
  • periodic -- ∀u∈Z, Fhat(u+M) = Fhat(u)

Summary

• we have shown the Fourier transform is ...
  • f = (1/M)F(F^*)^*
  • linear
  • periodic