Notes 20110310 CIS 6320 Image Processing

From SnOwy - Ed's Wiki Notebook

Discrete FT (DFT) and IDFT (inverse)

Today, we talk about the 2D case

• in one dimension, we only need one integer
• M, N ::= are positive numbers;
• function ::= a total function from (0 .. M-1) &times (0 .. N-1) into C
• for any u, v in 0 .. M-1;
• for any v, y in 0 .. N-1;
• in 1D ... K_u(x) = (1/M)exp(2jπux/M)
• in 2D ... K_u,v(x,y) = (1/(MN))exp(2jπ(ux/M+vy/N))
• in 1D ... F(F) = Σ_u=0^M-1F(u)L_u (where F is curvy-F)
• F is a function -- the forward Fourier transform
• F is a function -- this will be set to an image when transforming images (pictures)
• F(u) is a complex number -- (the codomain of F -- the image of u in F)
• K_u -- kernel -- a function
• F(u)K_u -- this product is a function
• this is why F(F) can be assigned in this way
• what is the value at function F^-1(F)(x) ?
  •  ::= &Sigma_u=0^M-1F(u)K_u(x)
• so let's define in two dimensions F^-1(F) = Σ_u=0^M-1Σ_v=0^N-1F(u,v)K_u,v
• f | 0..M-1×0..N-1 → C // (x, y) |→ f(x, y)
• F | C^{0..M-1×0..N-1} → C^{0..M-1×0..N-1} // f |→ F(f) // F |→ F(F)
• recall last class -- we needed to recognize a geometric sequence and express it as a series (sum of sequence)
• 2D transform justification proof for bijection (use of F^-1 notation) is derived from 1D transform proof
• important properties ...
• calculating the inverse Fourier transform ...
• F^-1(F) = (1/(MN))F(F^*)^* (EXPRESSION 1)
  • proof is the same as in 1D -- notice the difference is that in 1D, the result does not have 'N' in the denominator
• F is linear ..
• for any functions f₁ and f₂ for any complex number c ...
• F(cf₁) = cF(f₁) and F(f₁ + f₁) = F(f₁) + F(f₂)
• we can use EXPRESSION 1 to show that F^-1 is also linear
• the extension CLEANUP
  • F-hat | Z² → C // (u,v) |→ Σ_x=0M-1</sup>Σ_y=0^N-1 ...
• &forall(u,v) ∈ Z², F-hat(u+M,v) = F-hat(u,v+N) = F-hat(u,v)
• we can prove this by substituting each u+M for M and v+N for N and using the properties of Euler's formula
• separability ...
• K_u,v^M,N(x,y) = (1/(MN))exp(2yπ(ux/M+vy/N))
• let's use a different notation -- the kernel α^M,N -- size M×N -- separable iff &exists; a kernel β^M of size M and kernel γ^N of size N
• such that ... &forall(u,v),&forall(x,y),&alph;a_u,v^M,N(x,y) = β_u^M(x)γ_v^N(y)
• α^M,N = K^M,N
• K_u,v^M,N(x,y) = (1/M)(exp(2yπux/M))(1/N)(exp(2yπvy/N))
• is the same as &alph;a_u,v^M,N(x,y) = β_u^M(x)γ_v^N(y)
  • it turns out in our case, γ = β so we can stick with just the one symbol β
  • the Fourier kernels are not only separable, they are also symmetric
• 2D transforms with separable kernels can be computed using 1D transforms
  • these are important results because
• we only need to implement a single 1D forward Fourier transform
  • we use EXPRESSION 1 to perform the IDT (inverse)
  • and because of separability, we are capable of combining a collection of 1D DTs to create our higher dimension DTs

Separability Proof

We are using separability to prove we are able to use a 1D Fourier transform to get FTs of higher dimensions.

• F ::= F^M,N(f)
  • F is a specific curvy-F that operates only on functions whose domains are two dimensions in integers
• F(u,v) = Σ_x=0^M-1(Σ_y=0^N-1f(x,y)k_y^N(u))k_x^M(u)
• ... this is a rewriting of ...
  • ΣΣf(x,y)k_x,y^M,N(u,v)
  • ΣΣf(x,y)k_x^M(u)k_y^N(v)
• -- distributive property
• f(x,•) ::= y |→ f(x,y)
  • notation f(x,•) means we are fixing the variable x
  • domain is 0 .. N-1
  • codomain is C
• F_x ::= F^N(f(x,•)) -- there are M many of these in an M×N function
• F(u,v) = Σ_x=0^M-1(...we must rewrite the inner sum...)k_x^M(u)
  • we are only calculating the one dimensional Fourier transform -- we are holding x constant
• the inner sum is exactly the same as the 1D Fourier transform -- F_x(v)
• F(u,v) = Σ_x=0^M-1F_x(v)k_x^M(a)
  • we thus calculate M number of Fourier transforms -- this is half of the proof.
  • the other half of the proof -- we need to hold v constant ....
• this is more difficult because we need to index specific values within the inner sum
• F_•(v) ::= x |→ F_x(v)
• F(•,v) ::= F^M(F_•(v)) -- there are N many of these in an M×N function
• F(u,v) = F(•,v)(u)
• We thus need to calculate M+N transforms