Chapter 4: Model Fitting and Optimization

RANSAC is a probabilistic algorithm that draws minimal random subsets of size $n$ from $N$ data points. Each subset determines a unique model (e.g., 2 points define a line), and the consensus set is $\{i : |r_i| < \tau\}$. The probability that a given sample contains only inliers is $w^n$ where $w$ is the inlier ratio. After $k$ iterations, the probability of never drawing an all-inlier sample is $(1 - w^n)^k$, which decreases exponentially in $k$. RANSAC's expected complexity is $O(k \cdot N)$ where $k$ scales as $O(w^{-n})$ — exponential in the sample size $n$ but independent of the total number of outliers.

The threshold $\tau$ defines the decision boundary between inliers and outliers. For zero-mean Gaussian noise with known standard deviation $\sigma$, the squared residual follows a $\chi^2_d$ distribution with $d$ degrees of freedom (1 for a line, 2 for a homography point). Setting $\tau^2 = F_{\chi^2_d}^{-1}(p)$ at confidence level $p = 0.95$ gives $\tau \approx 1.96\sigma$ for $d = 1$ and $\tau \approx 2.45\sigma$ for $d = 2$. A threshold that is too tight reduces the effective inlier ratio $w$, exponentially increasing the required iterations via the formula $k \propto w^{-n}$.

The iteration formula $k = \log(1 - p) / \log(1 - w^n)$ comes from requiring the failure probability $(1 - w^n)^k \leq 1 - p$. Taking logarithms (both sides negative, so the inequality flips) gives $k \geq \log(1 - p) / \log(1 - w^n)$. For small $w^n$, $\log(1 - w^n) \approx -w^n$, so $k \approx -\log(1-p) / w^n$. This reveals the exponential dependence on $n$: doubling the minimal sample size squares the required iterations. For a homography ($n = 4$) with 50% outliers ($w = 0.5$), $k \approx 72$, while for the fundamental matrix ($n = 8$), $k \approx 1177$ — motivating the 5-point algorithm that reduces $n$.

Total variation $\text{TV}(u) = \int |\nabla u| \, dx$ measures the total arc length of the 1D signal graph, or equivalently the $L^1$ norm of the gradient field. For piecewise-constant signals, $\text{TV}$ equals the sum of absolute jump heights. The space $\text{BV}(\Omega)$ of bounded-variation functions is strictly larger than the Sobolev space $W^{1,1}$, meaning TV is finite even for functions with jump discontinuities (edges), whereas the $L^2$ gradient norm $\int |\nabla u|^2$ diverges at discontinuities. This is precisely why TV regularization preserves edges.

The ROF (Rudin-Osher-Fatemi) functional $\min_u \lambda \text{TV}(u) + \frac{1}{2}\|u - f\|_2^2$ is a convex optimization problem whose Euler-Lagrange equation involves the curvature operator $\text{div}(\nabla u / |\nabla u|)$. The parameter $\lambda$ controls the bias-variance tradeoff: as $\lambda \to 0$, $u \to f$ (data fit, high variance); as $\lambda \to \infty$, $u$ converges to a constant (low variance, high bias). The solution forms a one-parameter family of piecewise-constant approximations to $f$, and the "staircasing" effect — flat regions separated by sharp jumps — is a direct consequence of the $L^1$ penalty promoting sparsity in the gradient domain.

The $L^1$ norm $|\nabla u|$ imposes a constant marginal penalty per unit of gradient magnitude, while the $L^2$ norm $|\nabla u|^2$ imposes an increasing marginal penalty. Formally, the proximal operator of the $L^1$ norm is soft-thresholding $\text{prox}_{\lambda \|\cdot\|_1}(x) = \text{sign}(x) \max(|x| - \lambda, 0)$, which shrinks small gradients to zero while only slightly reducing large ones. In contrast, the $L^2$ proximal operator scales all gradients by $1/(1+\lambda)$, uniformly attenuating edges and noise alike. This soft-thresholding property is equivalent to sparsity promotion — $L^1$ minimization seeks solutions with few nonzero gradients (few edges), which matches natural image statistics.