What's a good basis for images?

Extract a row (or column) from the image:

 

Figure 9: Image from the CU home page.

• The extracted row can be thought of as a function f(x).
• Find a function basis that is good in describing slowly varying information (overall shape) and rapidly varying information (steep slopes).
• The trigonometric functions form such a basis! $\Rightarrow$
  Fourier analysis.
• Functions can be thought of as vectors in a vector space.
• We can introduce an orthonormal basis in the vector space of periodic functions by
  
  $$\{ e^{2\pi i kx} \}_{k=0}^\infty = \{ \cos(2\pi kx)+i\sin(2\pi kx) \}_{k=0}^\infty \ .$$
  
  

• A basis function $e^{2\pi i kx}$ with a large k is a rapidly oscillating function.
• Rapidly oscillating basis functions can pick up details of a function.
• A basis function $e^{2\pi i kx}$ with a small k is a slowly oscillating function.
• Slowly oscillating basis functions can pick up overall shape of a function, but cannot pick up information about details of the function.
• By using the orthogonal decomposition theorem we can expand f(x) as
  
  $$f(x) = \sum_{k=0}^\infty < f(x),e^{2\pi i kx}> \ e^{2\pi ikx} \ .$$
  
  

• The expansion coefficients are computed by
  
  $$< f(x),e^{2\pi i kx} \ > \ =\int_0^1 f(x)e^{-2\pi ikx}\ dx \s... ...c{1}{N}\sum_{k=0}^N f(\frac{n}{N})e^{-2\pi ik\frac{n}{N}} \ .$$
  
  
  This sum is called the Discrete Fourier Transform (DFT).
• By a clever organization of the computations, these sums can be computed in a "fast" manner called the Fast Fourier Transform (FFT).

• The (magnitude of the) expansion coefficients
  
  $$< f(x),e^{2\pi i kx} \ > \ =\int_0^1 f(x)e^{-2\pi ikx}\ dx$$
  
  
  are the numbers displayed in right plots in Figure 8.