Notes 20110303 CIS 6320 Image Processing

From SnOwy - Ed's Wiki Notebook

Contents 1 Fourier Transform (FT) in Digital Image Processing (DIP) 1.1 Review 1.2 Canonical Basis 2 Examples 3 Fourier Transform -- in one dimension 3.1 Complex Numbers 4 Adding and Multiplication of complex numbers using polar coordinates 5 Course Administrivia

Fourier Transform (FT) in Digital Image Processing (DIP)

Review

• important class of image transforms -- change of basis
• getting the coordinates in the new basis ...
• f = Σ_uΣ_vF(u,v)K_u,v
• f(x,y) = Σ_uΣ_vF(u,v)K_u,v(x,y)
• F = Σ_xΣ_yf(x,y)k_x,y
• F(u,v) = Σ_xΣ_yf(x,y)k_x,y(u,v)
• we need to find the k_x,y -- forward transformation kernel
• but we actually find K_u,v first -- the inverse transformation kernel
• remember, k_x,y is a basis that we calculate
• K_u,v is a basis that we started with (we had to express things in basis c (given) in basis K (given))

Canonical Basis

• c_0,0 = [1 0 // 0 0]
• c_0,1 = ...
• c_0,0(0,0) = 1
• c_0,0(0,1) = 0
• ... based on the basis c ...
• ... c_u,v(x,y) = δ_u,x δ_v,y
  • -- where δ is the Kronecker Delta (δ_a,b → 1 iff: a == b; else: → 0

Examples

• 2ⁿ×2ⁿ Walsh basis function
• Hadamard basis function
• Today ... M×N Fourier basis function
• K_u,v(x,y) ::= (1 / MN) e ^{2 j π (ux/M + vy/N)}
  • j is the imaginary unit

Fourier Transform -- in one dimension

• f = Σ_uF(u)k_x
• we're using the complex numbers -- we update the vector space tuple scalar operation with C instead of R
• the complex number was introduced because Italian mathematicians needed to solve cubic equations
• this work extended to many polynomial equations
• the complex numbers are a magic door for these solutions since the solutions were often real numbers

Complex Numbers

• z ∈ C
  • z = a + jb
  • a, b ∈ R²
  • j² = -1
• a = R(z)
• b = J(z)
• a + jb = a′ + jb′ → (a = a′ ∧ b = b′)
• (a + jb) + (a′ + jb′) = (a + a′) + j(b + b′)
• (a + jb) &time; (a′ + jb′) = (aa′ - bb′) + j(ab′ + ba′)
• z = a+jb
• z^* = a-jb -- the conjugate of z
• for z = a+jb, if a == 0, then z is "imaginary".
• z + z^* = 2a ∈ R
• (z + z′)^* = z^* + z′^*
• (zz')^* = z^*z′^*
• zz^* = a² + b² ∈ R
• (z^*)^* = z

a + jb    (a + jb) (a' - jb')   (aa' + bb')     (ba' - ab')
------- = ------------------- = ----------- + j -----------
a'+ jb'   (a'+ jb) (a' - jb')   (a'2 + b'2)     (a'2 + b'2)

• we can illustrate a complex number in a 2D plane ...
• horizontal axis: real part (a)
• vertical axis: imaginary part (b)
• so that z = (a, b) = a + jb ...
• we can express this using polar coodinates ...
• -- moment arm goes from the positive horizontal axis counter clockwise
• z = r(cos θ + j sin θ) -- polar
• z = a + jb -- rectangular
• for Fourier transform, the polar coordinates are more practical
• r = |z| (the modulus of z -- call this modulus in this class, it's the same as the magnitude)
• r ∈ [0, +∞[
• &theta ∈ ]-π, π] : θ : arg(z) -- the argument of z
• arg(0) is a singularity -- the only place where θ is non-unique
• convention -- arg(0) always 0

Adding and Multiplication of complex numbers using polar coordinates

We want to do these operations in this transform domain because it's computationally (mathematically) simple.

• z = r(cosθ + jsinθ)
• |zz′| = r(cosθ + jsinθ)r′(cosθ′ + jsinθ′)
• -- here, we're interested in getting the modulus (magnitude) of the operation --
• rr′ + {(cosθcosθ&prime - sinθsinθ′) + j(sinθcosθ′ + sinθ′cosθ)}
• rr′(cosθ + θ′) + jsin(θ + θ′)
• modulus ...
  • |zz′| = |z||z′|
• argument ...
  • arg(zz′) = arg(z) + arg(z′) (mod 2π)
• sum of complex in polar?
• |z + z′|
• exponentiation of complex in polar ...
  • zⁿ = rⁿ(cos(nθ) + jsin(nθ))
  • de Moivre's formula (1730)
  • holds true only for integers
• Euler's Forumla (1748)
  • e^jθ = cosθ + jsinθ
  • z = r(cosθ + jsinθ)
  • z = re^jθ
  • zz′ = (re^jθ)(r′e^jθ′) = rr′e^{j(θ + θ′)}
• where ...
  • (re^jθ)(r′e^jθ′) = e^ae^b
  • rr′e^{j(θ + θ′)} = e^a+b
  • rr′(cos(θ + θ′) + jsin(θ + θ′))
• the re^jθ notation is very practical and holds ...
• aside: if θ = π -- then e^jπ + 1 = 0
  • e^jπ = -1 -- where -1 = (cos(π) + jsin(π))
    • cos(π) = -1; jsin(π) = 0j
  • e^j2π = 1 -- where 1 = (cos(2π) + jsin(2π))
    • cos(2π) = 1; jsin(2π) = 0j
  • e^j½π = j -- where j = (cos(½π) + jsin(½π))
    • cos(½π) = 0; jsin(½π) = j

Course Administrivia

• send a review of the background material two days ahead of the mathematical talk