Hartley & Zisserman, Chapter 5

Algorithm Evaluation
& Error Analysis

Performance bounds, covariance propagation, and Monte Carlo methods — how to know if your estimate is any good.

Prerequisites: Chapter 4 (Estimation) + Covariance matrices.

Chapters

Simulations

Chapter 0: Why Evaluate Algorithms?

Chapter 4 gave us algorithms to estimate a homography. But how do we know if the estimate is any good? How uncertain is it? Is there a fundamental limit to how well any algorithm can perform?

This chapter answers these questions with three tools: Cramer-Rao bounds (theoretical lower bounds on error), covariance propagation (how input noise maps to output uncertainty), and Monte Carlo simulation (empirical error estimation).

The three questions:
1. How good can any algorithm be? (Cramer-Rao bound)
2. How good is my algorithm? (Covariance of the estimate)
3. How do I verify this empirically? (Monte Carlo)

What does the Cramer-Rao bound tell you?

The theoretical minimum variance of any unbiased estimator The exact error of the DLT algorithm The number of RANSAC iterations needed

Chapter 1: Performance Bounds

For any estimation problem with Gaussian noise, the Cramer-Rao Lower Bound (CRLB) gives the minimum achievable covariance. If your algorithm achieves this bound, it is efficient — no algorithm can do better.

The CRLB is the inverse of the Fisher Information Matrix J: Cov(θ̂) ≥ J⁻¹. The MLE achieves this bound asymptotically (with enough data).

J = E[(∂ log L / ∂θ)(∂ log L / ∂θ)^T] | Cov(θ̂) ≥ J⁻¹

Practical meaning: If your Gold Standard (MLE) estimate has covariance close to J⁻¹, you have extracted all the information the data contains. If another algorithm has much larger covariance, it is leaving information on the table.

An estimator is called "efficient" when it:

Achieves the Cramer-Rao lower bound — no unbiased estimator can have lower variance Runs in linear time Uses the fewest correspondences possible

Chapter 2: Covariance of the Estimate

Given noisy input data with known covariance Σ_x, what is the covariance of the estimated transformation Σ_H? This is the covariance propagation problem.

For a linear mapping y = Ax, the covariance propagates simply: Σ_y = A Σ_x A^T. For nonlinear mappings y = f(x), we linearize with the Jacobian J: Σ_y ≈ J Σ_x J^T.

Linear: Σ_y = A Σ_x A^T | Nonlinear: Σ_y ≈ J Σ_x J^T

Forward propagation: Start with input covariance, push through the algorithm to get output covariance. This tells you how uncertain each entry of H is. The eigenvectors of Σ_H show the most and least uncertain directions in parameter space.

For a linear map y = Ax, how does covariance propagate?

Σ_y = A Σ_x A^T Σ_y = A^T Σ_x A Σ_y = A Σ_x

Chapter 3: Forward Transport

Forward transport of covariance: given Σ_θ (covariance of the estimated parameters), compute the covariance of some derived quantity like a reprojected point.

If the derived quantity is x̂ = f(θ), then Σ_x̂ ≈ J_f Σ_θ J_f^T, where J_f = ∂f/∂θ. This gives you error ellipses around predicted points — a visual representation of uncertainty.

Error ellipses: The covariance matrix of a 2D point estimate defines an ellipse. The eigenvalues give the semi-axis lengths, and eigenvectors give the orientation. A 95% confidence ellipse has semi-axes scaled by √5.99 (from the χ² distribution with 2 DOF).

Error Ellipses

Each ellipse shows the uncertainty of a reprojected point. Increase noise to see ellipses grow.

Noise σ5

What does an error ellipse around a reprojected point represent?

The region of uncertainty — the true point is likely within this ellipse The size of the point in the image The RANSAC inlier threshold

Chapter 4: Backward Transport

Backward transport: given a measurement and its covariance, infer the covariance of the underlying parameters. This is the inverse problem. If y = f(x) and we observe y with covariance Σ_y, what is Σ_x?

For the over-determined case (more measurements than parameters), the covariance is: Σ_x = (J^T Σ_y⁻¹ J)⁻¹. This is the covariance of the weighted least-squares solution.

The key result: For MLE with Gaussian noise, the covariance of the estimated parameters equals the inverse Fisher information: Σ_θ = J⁻¹. This connects backward transport directly to the Cramer-Rao bound.

What does backward transport of covariance compute?

The uncertainty of estimated parameters given measurement uncertainty The noise level in the input images The convergence rate of Levenberg-Marquardt

Chapter 5: Monte Carlo Methods

Sometimes the math for covariance propagation is too complex. Monte Carlo simulation provides an empirical alternative: generate many synthetic datasets with known noise, run your algorithm on each, and compute the sample covariance of the results.

1. Ground Truth

Choose a known H and point positions

↓

2. Add Noise

Perturb point positions with Gaussian noise (σ = 1 pixel)

↓

3. Estimate

Run your algorithm to get Ĥ

↓

4. Repeat 1000×

Collect all Ĥ estimates

↓

5. Analyze

Compute sample mean, covariance, compare to CRLB

Monte Carlo is the gold standard for algorithm evaluation. It lets you test algorithms in controlled conditions, compare to theoretical bounds, and verify that your covariance propagation formulas are correct.

What is the purpose of Monte Carlo simulation in algorithm evaluation?

Empirically measure the error distribution of an algorithm by running it on many synthetic datasets Find the global optimum of a cost function Detect outliers in the data

Chapter 6: Residual Analysis

After estimating H, the residuals e_i = d(x'_i, Hx_i) tell you how well the model fits the data. For MLE under Gaussian noise with variance σ², the sum of squared residuals follows a χ² distribution:

Σ_i (e_i / σ)² ~ χ²_{2n − p}

where n is the number of correspondences and p is the number of parameters (8 for H). If the residuals are much larger than expected, either the noise model is wrong, there are outliers, or the geometric model is inappropriate.

Residual diagnostics: Plot the residuals. They should be randomly distributed with no pattern. Structured residuals (e.g., residuals correlated with position) indicate model inadequacy. Outlying residuals indicate mismatches.

What distribution should the sum of squared normalized residuals follow for a correct MLE fit?

Chi-squared with 2n − p degrees of freedom Uniform distribution Poisson distribution

Chapter 7: Connections

This chapter gave us the tools to evaluate and compare estimation algorithms rigorously. The same error analysis framework applies to every estimation problem in the book:

Tool	Purpose	When to Use
CRLB	Theoretical best achievable	Algorithm design & comparison
Covariance propagation	Analytical error prediction	Fast uncertainty estimates
Monte Carlo	Empirical error measurement	Validation & complex cases
Residual analysis	Model adequacy check	After every estimation

"The MLE achieves the Cramer-Rao lower bound asymptotically. It is the gold standard against which other estimators should be measured."

— Hartley & Zisserman, Chapter 5

What is the relationship between MLE and the Cramer-Rao bound?

MLE achieves the CRLB asymptotically — it is the best possible estimator for large samples MLE always exceeds the CRLB They are unrelated

← Chapter 4 Chapter 6: Camera Models →

Algorithm Evaluation& Error Analysis