Computer Vision: Algorithms and Applications | Richard Szelisky

Free official electronic version: Computer Vision: Algorithms and Applications, 2nd ed.

P.S. Part name was added by me.

Introduction

Sample Editor Command
Very difficult due to imperfect information.
A brief history of computer vision.

Part I: The Basics

Image formation

Sample Editor Command
Homogeneous coordinates and how to use them to describe 2D/3D transformations compactly.
Photometric image formation
Models of lighting, reflectance, shading, and optics.
Digital camera
- Sampling and aliasing when digitizing an image.
- Demosaicing color-filter arrays and describing colors in different color spaces.
- Gamma correction and white balance.
- Image compression techniques used by JPEG and other image formats.

Image processing

Operations
- Point-level operators
- Convolutional operators (linear filtering)
- Neighborhood operators
  e.g. Bilateral filtering
Pyramids
- Fourier transforms
- Laplacian pyramids
- Wavelet pyramids

Model fitting and optimization

Data interpolation
- Radial basis functions (RBFs)
  When using a robust loss function, the data fitting process is called robust data fitting.
- Variational methods
  Optimize a function directly by regularizing its derivatives via energy minimization.
Markov random fields
Honestly, since the book doesn't cover the preliminary knowledge, I don't quite understand this part.

Deep Learning

Classical machine learning
- Supervised learning
  e.g. Nearest neighbors, Bayesian classification, logistic regression, support vector machine, and decision trees (forests).
- Unsupervised learning
  e.g. Clustering, K-means (vs Gaussian mixtures), principal component analysis, and manifold learning (non-linear dimensionality reduction).
- Semi-supervised learning
Deep neural networks
- Basic components of MLP
  Layers, weight initialization (e.g. He Initialization), activations (e.g. ReLU), regularization (e.g. dropout), normalization (e.g. Batch Normalization), loss function, and back-propagation.
- CNN and its variants
  e.g. AlexNet, GoogLeNet, ResNet, VGGNet-16, ZF Net, etc.
  - Adversarial examples
  - Self-supervised learning
    e.g. Pre-training and contrastive learning.
  - 3D CNN
- Other networks: RNN, Transformer, VAE, GAN, etc.

Part II: 2D Vision

Recognition

Instance recognition
Recognize objects in a cluttered scene.
Image classification
- Classic feature-based methods include bag of words and part-based models, etc.
- Classic (PCA) decomposition-based methods include Active Appearance Model and 3D Morphable Model, etc.
- Starting from AlexNet, Deep Learning-based methods have taken over the field.
Object detection
When a subpart of the image is localized and classified, it's called object detection.
- Classic methods are typically based on PCA, clustering, support vector machine, boosting, etc.
- Seminal works based on Deep Learning include YOLO, R-CNN, Fast R-CNN, Faster R-CNN, FPN, DETR, etc.
Semantic segmentation
When classification is performed at the pixel level, it's called semantic segmentation.
Seminal works include U-Net, Mask R-CNN, etc. More recent work tends to adopt feature pyramid-based frameworks.
- When an instance boundary is distinguished, it's called instance segmentation.
- Seminal works in human pose estimation include OpenPose, DensePose, HRNet, etc.
Video understanding
e.g. Two Stream CNN
Vision and language
e.g. CLIP, DALL·E, VQA, etc.

Feature detection and matching

Point and patch-level
- Feature detector
  Using auto-correlation to find the most distinguishable feature points from the image.
  - Uncertainty indicators, asymmetry indicators, Gaussian weighting windows, and scale pyramids are common techniques for augmenting it.
  - Scale (e.g. SIFT), rotation (e.g. Harris), and affine (e.g. MSER) invariance are also addressed.
- Feature descriptor
  e.g. Scale Invariant Feature Transform (SIFT)
- Feature matching
  To improve efficiency, hashing, k-d trees, binning, etc. are applied.
  To improve robustness, RANSAC can be used.
Edge and contour-level
- Edge detection
  Apply the Laplacian of Gaussian (LoG) or Difference of Gaussian (DoG), and then find the zero crossings.
- Contour detection
  Linking neighboring detected edge pixels.
  When the contour is detected interactively via an energy-minimization scheme, it's called contour tracking, e.g. snakes, scissors, level sets, etc.
- Lines and vanishing points
  e.g. Hough transforms
Segmentation
The image features can also be used to merge/segment image regions.
e.g. Region merging, watershed, mean shift, normalized cuts, etc.

Image alignment and stitching

Pairwise alignment
With a predefined motion model, the parameters that best align two images can be estimated via least squares. For better results, iterative algorithms like non-linear least squares can be used. Further improvements can be achieved via robust least squares and RANSAC.
- Jacobian $J$ : $\Delta x = x' - x = \frac{\partial f}{\partial p}p = J(x)p$
- Hessian $H$ : $H(x) = \sum_i J^T(x) J(x)$
Global alignment (bundle adjustment)
When the alignments of all images are optimized directly instead of pairwise, the process is called bundle adjustment. It can be formulated as the summed cost across all image pairs (feature correspondences) and optimized via least squares.
Compositing
When compositing aligned images, multiple available pixels at a compositing location need to be selected or weighted for deghosting. Exposure compensation is also needed.

Motion estimation

Parametric motion
Brightness and color difference are also taken into account.
- Translational motion model
  Classic motion estimation techniques include hierarchical motion estimation, Fourier-based alignment, and Taylor-series-based incremental refinement at the subpixel level.
  - Optical flow constraint (Lucas-Kanade)
    $I_x u + I_y v + I_t = 0$
- Motion models with more parameters
  Can be optimized with Taylor series expansion and gradient descent/non-linear least squares.
- Spline-based motion
  Define motion based on control vertices.
Optical flow
Motion of each pixel - a highly under-constrained problem.
- Regularization-based method
  A smoothness term can be used to constrain the motion field. A Markov random field (MRF) is another alternative.
- Patch-based method
  Performs translational alignment within a coarse-to-fine pyramid.
- Deep Learning-based methods
  e.g. DeepFlow, FlowNetS, SPyNet, PWC-Net, $\text{HD}^3$ , LiteFlowNet3, etc.
Layered motion
Group pixels into layers/objects.

Computational photography

Photometric calibration
Covers radiometric response function (log exposure > pixel value), noise level estimation, vignetting, and optical blur.
High dynamic range imaging (HDR)
Merging photos taken under different exposures. When displaying an HDR image, it needs to be tone-mapped to a displayable gamut, for which sophisticated methods utilizing high/low-pass filters, gradient information, etc. have been developed.
Image quality improvement
Covers super-resolution, denoising, and blur removal.
Image demosaicing and lens blur (bokeh) are also discussed.
Image matting and compositing
Covers blue screen matting, natural image matting, optimization-based matting, and video matting.
Matting with special effects like smoke, shadow, and flash is also discussed.
Texture analysis and synthesis
Can be used for hole filling, non-photorealistic rendering, style transfer, etc.

Part III: 3D Vision

Structure from motion and SLAM

Geometric calibration
Point $p$ $p$ in 3D space is mapped to the camera's local frame by the extrinsic parameters: $[R|t]p$ $[R ∣ t] p$ , and then mapped to the pixel grid by the intrinsic parameters: $K[R|t]p$ $K [R ∣ t] p$ .
- Camera intrinsic estimation
  The most important factor in the camera intrinsics is the focal length. For wide-angle lenses, radial distortion factors are also needed.
- Camera extrinsic estimation (pose estimation)
  With known point locations, the camera extrinsic can be estimated via least squares or iterative optimization.
- $\infty$ Triangulation
  The converse problem of pose estimation is to estimate a point's location with a known camera pose.
Structure from motion (SfM)
SfM aims to recover the locations of corresponding points in space and the camera poses at the same time.
- Epipolar geometry
  - Points in $l_0$ are mapped to $l_1$ when viewed from camera 1.
  - Essential matrix $E = [t]_{\times} R$
    Epipolar constraint: $\hat{x}_1^T E \hat{x}_0 = 0$
  - Fundamental matrix $F = K_1^{-T}EK_0^{-1}$
    When camera intrinsics are unavailable, the 3D locations of the pixels are unavailable. In this case, the equation can only be formulated with the pixel-grid coordinates: $x_1^T F x_0 = 0$
- Two-frame SfM
  Based on the epipolar constraint, the 8-point algorithm uses 8 pairs of corresponding points to estimate the extrinsics and the 3D point locations.
- Multi-frame SfM
  Bundle adjustment can be used in the context of 3D and for SfM, leading to multi-frame SfM. For efficiency, sparsity structure can be exploited.
Simultaneous localization and mapping (SLAM)
Solving the (sparse) 3D reconstruction and localization problem online. It's extensively applied in autonomous navigation and augmented reality (AR).

Depth estimation

Plane sweep
Based on epipolar geometry, warp source image $k$ $k$ to disparity plane $d$ $d$ of a virtual camera to form a disparity space image (DSI) $\tilde{I}(x, y, d, k)$ $\tilde{I} (x, y, d, k)$ , and then use the DSI for dense depth estimation.
- Rectification
  Based on epipolar geometry, rectify images for dense matching.
- Local optimization
  Using window-based aggregation of the matching cost on DSI to optimize the depth estimation.
- Global optimization
  Using global optimization methods like dynamic programming to optimize the depth estimation on DSI.
Multi-view stereo
Depth estimation with multiple views.
e.g. COLMAP (used by NeRF).
Monocular depth estimation
Depth estimation with a single view. Usually based on Deep Learning.

3D reconstruction

Surface representations
e.g. Triangle meshes, point clouds, voxels, implicit functions/signed distance functions, etc.
Shape from X
Recover shape from shading, texture, focus, etc.
- 3D scanning
  Active (illumination) stereo: light detection and ranging (Lidar), laser-based 3D scanners, time-of-flight (ToF), etc.
- Model-based reconstruction
  With a shape model as a prior, the reconstruction can be much more accurate and efficient. It has been widely used for architecture, faces (e.g. FLAME), hands (e.g. MANO), human bodies (e.g. SMPL, SMPL-X, STAR), etc.
Recovering texture maps and albedos
- Texture maps
  Texture maps can be constructed after parametrizing the surface with $(u, v)$ coordinates.
- Albedo maps
  A light source can be explicitly modeled to estimate the reflectance-component (albedo) maps while making texture-map estimation more accurate.
- Bidirectional reflectance distribution functions (BRDFs)
  
  For view-dependent appearance modeling.

Image-based rendering

Image-based rendering (view interpolation)
- View-dependent texture maps
  Attach multiple texture maps to the shape for different view angles and blend these textures during rendering.
- Layered depth images
  Represent the scene as layers of different depths. This idea was recently rediscovered as the multiplane image (MPI).
- Lumigraphs
  The light color of a ray crossing two points from two planes bounding the 3D volume.
- Light fields
  The emitted light color of any point in a 3D volume.
- $\infty$ Environment mattes
  Instead of changing the virtual camera, environment mattes change the background.
Video-based rendering
- Video animation
  Animate an image with newly specified activity/script.
- Video textures
  Continue the video in a plausible manner.
- 3D and free-viewpoint video
Neural rendering w/ Deep Learning
Survey: TewariA2020
These methods can be classified by their 3D representations: texture-mapped meshes, depth images and layers, volumetric grids (e.g. NeRF, NeRF in the wild, etc.), and implicit functions (e.g. NeuS).

Conclusion

Computer vision is a broad field without unifying principles, due to its expansive definition as well as the incredible complexity inherent in the formation of visual information.
Physical principles, statistical methods, and machine learning are the major foundations of computer vision.
- Why learn pre-deep learning techniques? Shree Nayar explained:
  - When you can solve a problem elegantly via first principles, it isn't worth collecting massive amounts of data to do deep learning.
  - When a network doesn't work, first principles are all you have and probably your only hope of understanding why.
  - Finally, curiosity is part of human nature.
Future directions of the field.

Appendix

Linear algebra and numerical techniques

Matrix decompositions
- Singular value decomposition (SVD)
  $A_{m \times n} = U_{m \times p} \Sigma_{p \times p} V_{p \times n}^T$ $A_{m \times n} = U_{m \times p} Σ_{p \times p} V_{p \times n}^{T}$
  $AV = U\Sigma \Leftrightarrow A v_j = \sigma_j u_j$ $A V = U Σ \Leftrightarrow A v_{j} = σ_{j} u_{j}$
  $A = \sum_j \sigma_j u_j v_j^T$ $A = \sum_{j} σ_{j} u_{j} v_{j}^{T}$
  - Eigenvalue decomposition
    Symmetric matrix $C = U \Lambda U^T$ $C = U Λ U^{T}$
    - Principal component decomposition (PCA)
      $C = \frac{1}{n} \sum_i (x_i - \overline{x}) (x_i - \overline{x})^T$
- QR factorization
  $A = QR$
- Cholesky factorization
  $C = L L^T = R^T R$
Least squares
- Linear least squares
  - Vertical residuals
    $E = \|Ax - b\|^2 = x^T(A^TA)x - 2 x^T (A^T b) + \|b\|^2$
    $\arg\min_x E \Rightarrow \frac{\partial E}{\partial x} = 0 \Rightarrow A^T A = A^T b$
    Perform Cholesky factorization on $A^T A = R^T R$ ; then the optimized $x$ can be found by solving $\begin{cases}R^Tz = d\\Rx=z \end{cases}$
  - Total residuals
    $E = \|Ax\|^2 = x^T (A^T A) x$
    $\arg\min_x x^T (A^T A) x$ s.t. $\|x\| = 1$
    The optimized $x$ should be the eigenvector associated with the smallest eigenvalue of $A^T A$ .
- Non-linear least squares
  Estimate the iterative increment $\Delta p$ via Taylor series expansion:
  $E(\Delta p) = \sum_i \|J(x_i,p)\Delta p - r_i\|$
  $p \leftarrow p + \alpha \arg\min_{\Delta p} E$
  Important variants include Damped Gauss-Newton algorithm, Levenberg-Marquardt algorithm, etc.
Efficiency tricks
- Direct sparse matrix techniques
  e.g. Variable reordering.
- Iterative techniques
  e.g. Conjugate gradient, preconditioning, multi-grid, etc.

Bayesian modeling and inference

Estimation theory
Introduces the likelihood of measurement noise under the setting of multivariate Gaussian noise.
- Mahalanobis distance $\|y_i - \overline{y}_i\|_{\Sigma_i^{-1}}$
- Negative log likelihood $-\log L$
- (Fisher) information matrix (the inverse covariance) $C_i = \Sigma^{-1}$
Inference
- Maximum likelihood
  Via (robust) least squares.
- Bayesian inference
  $p(x|y) = \frac{p(y|x)p(x)}{p(y)} \Rightarrow -\log p(x|y) = -\log p(y|x) - \log p(x) + \log p(y)$
- Markov random field
  Use a Gibbs or Boltzmann distribution to describe the prior probability $p(x)$ , with the negative log likelihood written as a sum of pairwise interaction potentials.
Uncertainty (error) estimation

Supplementary material

Important datasets, benchmarks, software, and lectures.

Do you have any ideas or comments? Please join the discussion on X👇