6.0 LINEAR METHODS AND FOURIER ANALYSIS🔗⧉

A blurred photograph combines light from neighboring scene points. With fixed optics, geometry, and exposure, an unclipped linear sensor records a weighted sum of those contributions. This lets us describe image formation with a linear operator and ask which details survive the measurement.

The variable matters. Ordinary incoherent imaging is linear in incident intensity under these assumptions. Coherent wave propagation is linear in complex amplitude, but an intensity detector measures its squared magnitude. For a nonlinear process, a local linear approximation can still be useful when the process is differentiable and the perturbation is small; motion magnification uses this idea to relate displacement to image change.

Chapter 6.1, Introduction to forward and inverse linear methods starts with a five-sample blur. Chapter 6.2, Convolution, Chapter 6.3, Fourier, Chapter 6.4, Sampling, downsampling, and aliasing, Chapter 6.5, Resampling and upsampling, and Chapter 6.6, Pyramids and wavelets develop operations we can use directly on images. Chapter 6.7, Image formation as a linear system then asks what a measurement determines, Chapter 6.7, When linearity breaks down identifies the model's limits, and Chapter 6.9, Efficient linear solvers explains how to recover an estimate without storing an enormous matrix.

There are three reasons for learning these methods: some physical processes are linear in the chosen variable; some nonlinear processes admit a useful local linear approximation; and linear algebra supplies both explanations and algorithms. A change of basis can expose which image patterns a camera attenuates, singular values can diagnose sensitivity to noise, and least-squares solvers can fit measurements without constructing an inverse explicitly. The paraxial approximation in lens optics is another example of the second reason: restricting attention to small angles makes a more complicated geometric problem tractable.

Contents of this part

• 6.1 Introduction to forward and inverse linear methods
  • 6.1.1 A one-dimensional blur, forward
  • 6.1.2 Running the blur backward: the idealized case
  • 6.1.3 The catch: noise and ill-conditioning
  • 6.1.4 A corner camera: reading the edge of a shadow
  • 6.1.5 A different challenge: sampling and aliasing
  • 6.1.6 What the measurement determines
• 6.2 Convolution
  • 6.2.1 Convolution as a weighted sum of neighboring pixels
  • 6.2.2 The flip: where-from vs. where-to
  • 6.2.3 Convolution as a sum of translated images
  • 6.2.4 Properties: the impulse, normalization, symmetry, commutativity
  • 6.2.5 Nitty-gritty: finite images
  • 6.2.6 A blur zoo
  • 6.2.7 Separability
  • 6.2.8 Linear sharpening
  • 6.2.9 Gradient and oriented filters
  • 6.2.10 Is imaging blur usually a shift-invariant convolution?
  • 6.2.11 Fixed and data-dependent weights
• 6.3 Fourier
  • 6.3.1 Why Fourier
  • 6.3.2 Complex waves are eigenvectors of shifts and convolution
  • 6.3.3 The tiniest Fourier transform in the West
  • 6.3.4 Definition: one coefficient per wave
  • 6.3.5 Reading an image's Fourier transform
  • 6.3.6 A small bestiary of transforms
  • 6.3.7 Optics and Fourier
  • 6.3.8 MTF: a lens's frequency response
  • 6.3.9 The fine print: two limitations of Fourier
  • 6.3.10 Windowing: the price of measuring a real spectrum
  • 6.3.11 Application preview: can we deblur, given the blur?
  • 6.3.12 Convolution by FFT
• 6.4 Sampling, downsampling, and aliasing
  • 6.4.1 Aliasing: a high frequency in disguise
  • 6.4.2 Nyquist and the sampling theorem
  • 6.4.3 In two dimensions, aliasing has a direction
  • 6.4.4 Sampling in the frequency domain: spectral replicas
  • 6.4.5 Seeing it: sampling and pre-filtering, hands on
  • 6.4.6 The ideal reconstruction filter: sinc, and why it is unreachable
  • 6.4.7 Practical filters: from the box to bicubic and Lanczos
• 6.5 Resampling and upsampling
  • 6.5.1 Domain operations: moving pixels around
  • 6.5.2 Start with scaling up
  • 6.5.3 The naive idea, and why it leaves gaps
  • 6.5.4 Loop over the output, use the inverse transform
  • 6.5.5 Nearest neighbor
  • 6.5.6 Linear interpolation, in 1-D first
  • 6.5.7 Bilinear, in 2-D
  • 6.5.8 The convolution perspective
  • 6.5.9 The full signal-processing view: sample, reconstruct, prefilter, resample
  • 6.5.10 Upsampling vs. downsampling: scale the kernel
  • 6.5.11 Prefiltering when the transform isn't a clean scale
  • 6.5.12 Resampling and encoding
  • 6.5.13 Beyond Nyquist-limited reconstruction
  • 6.5.14 Practical implementation choices
• 6.6 Pyramids and wavelets
  • 6.6.1 Halfway between space and frequency
  • 6.6.2 The idea: process an image at many resolutions
  • 6.6.3 The Gaussian pyramid
  • 6.6.4 The Laplacian pyramid
  • 6.6.5 Reconstruction: an exact encoder and decoder
  • 6.6.6 Each level is a frequency band
  • 6.6.7 What the bands look like on a real image
  • 6.6.8 Limitations
  • 6.6.9 Cousins: wavelets and steerable pyramids
  • 6.6.10 Pyramid blending
  • 6.6.11 Other applications
  • 6.6.12 Coarse-to-fine methods
• 6.7 Image formation as a linear system
  • 6.7.1 Linear systems from a billboard to an image
  • 6.7.2 How solvable is an imaging problem?
  • 6.7.3 Regularization
  • 6.7.4 Linear systems from ray space (plenoptic function or light field) to an image
  • 6.7.5 Space–time: imaging across time
  • 6.7.6 Other forms of linearity, and multilinearity
  • 6.7.7 Designing measurements for recovery
• 6.8 When linearity breaks down
• 6.9 Efficient linear solvers
  • 6.9.1 The problem, and the one trick
  • 6.9.2 Direct methods, and why they wall out
  • 6.9.3 Basic iterative solvers
  • 6.9.4 Conjugate gradient
  • 6.9.5 Preconditioning
  • 6.9.6 Multigrid
  • 6.9.7 Which solver when, and the edges

▸ full collapsible outline of this part