Notes 20110315 CIS 6050 Image Processing

From SnOwy - Ed's Wiki Notebook

continuing from the Discrete Fourier Transform

Contents 1 Convolution theorem 1.1 General case -- what is an extension? 2 Specific case -- g-hat is an extension of g 2.1 Explanation ... 3 g to g-hat ... 4 Bringing this to Transforms 5 = Convolution Theorem

Convolution theorem

use star(*) to mean the convolution of two functions

General case -- what is an extension?

• f | A → B
• g | C → B
• g is an extension of f
• A ⊆ C -- first proposition
• ∀ x ∈ A, g(x) = f(x) -- second proposition

Specific case -- g-hat is an extension of g

• g | 0..M-1 × 0..N-1 → C
• g | Z² → C
• ∀(x,y) ∈ 0..M-1 × 0..N-1, g-hat(x,y) = g(x,y)
• ∀(x,y) ∈ Z², g-hat(x+M,y) = g-hat(x,y+M) = g-hat(x,y)
• g-hat function satisfies the second proposition above
  • now g-hat is perfectly determined
• we will need g-hat
• f and g are total functions from (0..M-1)×(0..N-1) into C
• g-hat defined as M and N periodic extension of g to Z²
• f*g | (0..M-1)×(0..N-1)→C
• // (x,y) |→ Σ_m=0^M-1Σ_n=0^N-1f(m,n)g-hat(x-m,y-m)
  • the convolution of f with g -- g is the image -- f is the mask (the kernel, window, the convolution kernel, filter etc.,)
  • f is in the spatial domain

Explanation ...

• we are replacing the pixels in the spatial domain for pixels in the image g with a weighted sum in a neighbourhood defined by f
• example f() -- f() has the same dimensions as g(), but we can consider a window 3×3 as it is effectively the same
• (most of f() is usually 0 to make these computationally feasible)

1 1 1
1 1 1
1 1 1

• produces a blur

-1 0 1
-1 0 1
-1 0 1

• detects vertical lines
• see notes from convolution theorem
• convolution occurs so far in the spatial domain

g to g-hat ...

• g-hat is a circular indexing of g ...

g

• g

g g g ..
g g g ..
g g g ..
: : : ..

• g-hat
• note that the form (x-m, y-n) -- means we reverse the scanning going right to left and bottom to top for g -- but we go forward for f.
• this is the standard definition of convolution
  • correlation is defined given the form (m-x, n-y) -- we scan left to right, top to bottom for each f, g.
• convolution is equivalent to correlation when f() is reflected about the minor diagonal ...

a b c    i g h
d e f -> f e d
g h i    c b a

• so why do we use more difficult definition for convolution?
  • because F(f*g) = F(f)F(g) holds only for convolution but not correlation

Bringing this to Transforms

• F(f*g) = F(f)F(g) -- case 1
• f*g = F^-1(F(f)F(g)) -- case 2
• the second case is much faster than the first case because we have discovered the fast Fourier transform!
• -- f, g are in the spatial domain; F(f), F(g) are in the frequency domain; F^-1( .. ) is in the spatial domain again
  • note, we won't go into detail, but the reason why we use the term frequency domain, is because there is a mathematical proven link between this transform and the Fourier series (the sum of terms in an infinite sequence)

= Convolution Theorem

• FIXME