0.3 Approximation and processing in bases  (Page 2/5)

Sampling theorems

Let us consider finite energy signals $\parallel \overline{f}{\parallel }^2=\int {\left|\overline{f}\left(x\right)\right|}^{2}dx$ of finite support, which is normalized to $[0,1]$ or ${[0,1]}^2$ for images. A sampling process implementsa filtering of $\overline{f}\left(x\right)$ with a low-pass impulse response ${\overline{\phi }}_s\left(x\right)$ and a uniform sampling to output a discrete signal:

In two dimensions, $n=(n_1,n_2)$ and $x=(x_1,x_2)$ . These filtered samples can also be written as inner products:

with ${\phi }_s\left(x\right)={\overline{\phi }}_s(-x)$ . Chapter 3 explains that φ _s is chosen, like in the classic Shannon–Whittaker sampling theorem, so that a family of functions ${\left\{{\phi }_s(x-ns)\right\}}_{1\le n\le N}$ is a basis of an appropriate approximation space U _N . The best linear approximation of $\overline{f}$ in U _N recovered from these samples is the orthogonal projection  ${\overline{f}}_N$ of $f$ in U _N , and if the basis is orthonormal, then

A sampling theorem states that if $\overline{f}\in {\mathbf{U}}_N$ then $\overline{f}={\overline{f}}_N$ so recovers $\overline{f}\left(x\right)$ from the measured samples. Most often, $\overline{f}$ does not belong to this approximation space. It is called aliasing in the context of Shannon–Whittaker sampling, where U _N is the space of functions having a frequency support restricted to the N lower frequencies. The approximation error $\parallel \overline{f}-{\overline{f}}_N{\parallel }^2$ must then be controlled.

Linear approximation error

The approximation error is computed by finding an orthogonal basis $\mathcal{B}={\left\{{\overline{g}}_m\left(x\right)\right\}}_{0\le m<+\infty }$ of the whole analog signal space ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right){[0,1]}^2$ , with the first N vector ${\left\{{\overline{g}}_m\left(x\right)\right\}}_{0\le m<N}$ that defines an orthogonal basis of U _N . Thus, the orthogonal projection on U _N can be rewritten as

Since $\overline{f}={\sum }_{m=0}^{+\infty }⟨\overline{f},{\overline{g}}_m⟩{\overline{g}}_m$ , the approximation error is the energy of the removed inner products:

This error decreases quickly when N increases if the coefficient amplitudes $|⟨\overline{f},{\overline{g}}_m⟩|$ have a fast decay when the index m increases. The dimension N is adjusted to the desired approximation error.

Figure (a) shows a discrete image $f\left[n\right]$ approximated with $N={256}^2$ pixels. Figure(c) displays a lower-resolution image $f_{N/16}$ projected on a space ${\mathbf{U}}_{N/16}$ of dimension $N/16$ , generated by $N/16$ large-scale wavelets. It is calculated by setting all thewavelet coefficients to zero at the first two smaller scales. The approximation error is $\parallel f-f_{N/16}{\parallel }^2/{\parallel f\parallel }^2=14\times {10}^{-3}$ . Reducing the resolution introduces more blur and errors.A linear approximation space U _N corresponds to a uniform grid that approximates precisely uniform regular signals.Since images $\overline{f}$ are often not uniformly regular, it is necessary to measure it at a high-resolution N . This is why digital cameras have a resolution that increases as technology improves.

Sparse nonlinear approximations

Linear approximations reduce the space dimensionality but can introduce important errors when reducing the resolutionif the signal is not uniformly regular, as shown by Figure(c). To improve such approximations, more coefficients should be kept where needed—notin regular regions but near sharp transitions and edges.This requires defining an irregular sampling adapted to the local signal regularity. This optimized irregular sampling has a simple equivalent solutionthrough nonlinear approximations in wavelet bases.