DIP+CV · Programming Exercise

EP08_02 — 🟢 Homography and RANSAC: Voting by Inliers

8.14.2 EP08_02 🟢 Homography and RANSAC: Voting by Inliers

RANSAC, introduced in the section “Mathematical Modeling: Homography and RANSAC,” repeats a cycle of three steps — sampling a minimal set, estimating a candidate model, and counting how many correspondences are consistent with it (the inliers) — keeping at the end the most voted model. The model estimation step from 4 points (step 2) involves linear algebra that is beyond the scope of this assignment; here, you are directly given a set of already candidate homographies — as if each one had been estimated from a different random sample — and you are tasked with reproducing exactly the algorithm’s decisive step: apply each model to all correspondences and count its inliers, choosing the winner.

8.14.2.1 📋 Implementation Guidelines

  1. Correspondences: Read the integer \(N\) and then \(N\) lines with four real numbers each, \(x\ y\ x'\ y'\) — a point from image A and its (possibly incorrect) corresponding point in image B, exactly as produced by the matching step of EP08_01.
  2. Candidate models: Read the integer \(K\) (number of candidate homographies) and the real number \(\varepsilon\) (reprojection error threshold). Then, read \(K\) lines, each with nine real numbers \(h_{11}\ h_{12}\ h_{13}\ h_{21}\ h_{22}\ h_{23}\ h_{31}\ h_{32}\ h_{33}\) — the elements of the candidate matrix \(H\), in row-major reading order.
  3. Reprojection: For each correspondence \((x,y,x',y')\) and each candidate model \(H_k\), compute the projected point \[ \begin{bmatrix} \hat x \\ \hat y \\ \hat w \end{bmatrix} = H_k \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad (\hat x / \hat w,\ \hat y / \hat w)\ \text{is the projected point.} \]
  4. Reprojection error: \(e = \sqrt{(\hat x/\hat w - x')^2 + (\hat y /\hat w - y')^2}\).
  5. Inlier counting: A correspondence is an inlier of model \(H_k\) if \(e \le \varepsilon\).
  6. Best model selection: The winning model is the one with the largest number of inliers; in case of a tie, choose the one with the smallest index \(k\) (the first one encountered during the RANSAC iterative cycle).
  7. Output: For each model \(k\) from \(0\) to \(K-1\), in reading order, print Modelo k: I inliers. Finally, print Melhor modelo: k_best com I_best inliers.

8.14.2.2 📌 Computational Constraints

  • Inclusive comparison: a reprojection error exactly equal to \(\varepsilon\) counts as an inlier (\(e \le \varepsilon\)).
  • No estimation of \(H\): the matrices are already provided ready-made — there is no need (nor expectation) to solve any linear system.
  • Tie resolved by the smallest index, reflecting the natural behavior of an iterative algorithm that traverses models in order and only replaces the best found so far when a new model strictly surpasses it.

8.14.2.3 🧠 Theoretical Foundation

Element Role in RANSAC
Minimal sample (4 pairs) Sufficient to determine the 8 degrees of freedom of a homography
Candidate model \(H_k\) Estimated from a minimal sample; can be good or bad, depending on whether the sample contained outliers
Reprojection error Measures how well the model “predicts” each observed correspondence
Inlier vs. outlier Correspondences consistent with the winning model (inliers) vs. the remaining ones, typically incorrect matches from the matching step
Final refinement In practice, after selecting the best model, RANSAC recomputes it using only its inliers — a step not required in this assignment

8.14.2.4 📦 Input and Output Specification (VPL)

Input:

  • Line 1: Integer \(N\).
  • Next \(N\) lines: four real numbers \(x\ y\ x'\ y'\).
  • Next line: Integer \(K\) and real number \(\varepsilon\).
  • Next \(K\) lines: nine real numbers (elements of \(H_k\), row-major).

Output:

  • \(K\) lines in the format Modelo k: I inliers.
  • Last line: Melhor modelo: k_best com I_best inliers.

8.14.2.5 📌 Examples

Input Output Observation
5
0 0 0 0
1 1 2 2
2 0 4 0
0 2 0 4
5 5 1 1
2 0.5
2 0 0 0 2 0 0 0 1
1 0 0 0 1 0 0 0 1		 Modelo 0: 4 inliers
Modelo 1: 1 inliers
Melhor modelo: 0 com 4 inliers		 Model 0 (scale ×2) correctly explains 4 of the 5 correspondences; the 5th, \((5,5)\to(1,1)\), is an outlier that neither model explains well.
🎮 Simulator EP08_02: RANSAC — Inlier Count Model: Scale ×2
The candidate model maps (x,y) → to (2x,2y). Adjust the threshold ε and see which correspondences become inliers or outliers.
–
Figure 8.16: EP08_02 Simulator: RANSAC — Voting by Inliers among Candidate Models 
%%writefile EP08_02.py
# Python code
Overwriting EP08_02.py
TestSuite("EP08_02.py").run()
✔️ EP08_02.cases already exists in casos/
📋 6 case(s) loaded from casos/EP08_02.cases

🔍 Testing Python: EP08_02.py
⚠️ EP08_02.py: Empty file (fewer than 3 lines). Tests skipped.