RANSAC Homography Estimation

1. Background Knowledge

A homography is a $3 \times 3$ projective transformation that maps points from one plane to another in homogeneous coordinates: $\mathbf{p'} \sim H\mathbf{p}$, where $\mathbf{p} = (x, y, 1)^T$ and $\mathbf{p'} = (x', y', 1)^T$. It can represent rotations, translations, scaling, and perspective distortions between two views of a planar scene or images taken by a rotating camera. Because $H$ is defined up to scale, it has 8 degrees of freedom (9 parameters minus 1 scale).

With a set of point correspondences $(x_i, y_i) \leftrightarrow (x'_i, y'_i)$, homography estimation can be cast as a linear problem using the DLT (Direct Linear Transform) algorithm. Each correspondence provides two linear equations in the 8 unknowns, so at least 4 correspondences are needed. DLT builds a matrix $A$ such that $Ah = 0$, where $h$ is the 9-vector formed by stacking the entries of $H$. The solution is obtained using SVD as the right singular vector corresponding to the smallest singular value.

In practice, many correspondences are noisy and contain outliers (wrong matches). Directly running DLT on all points often fails. RANSAC (Random Sample Consensus) makes the estimation robust by repeatedly sampling minimal subsets (4 points), estimating a candidate $H$, then counting how many points are consistent with it (inliers) according to a reprojection error threshold. The model with the largest inlier set is chosen, and a final refined homography is typically re-estimated using all inliers.

---

2. Algorithm / General Approach

For this problem, the general pattern is:

1. Use RANSAC to search over many possible homographies:

• Randomly sample 4 correspondences.
• Estimate a homography from these using DLT.
• Evaluate how many correspondences agree with this homography (inliers).

2. After RANSAC finishes:

• Take the best inlier set (largest consensus).
• Re-estimate the homography using all inliers (again via DLT, now overdetermined).

This is a classic “robust model fitting” pattern: alternate between (a) random minimal subset sampling to generate hypotheses, and (b) model verification by counting inliers under an error threshold.

---

3. Step-by-Step Strategy

A. Represent correspondences

• Input: two lists of corresponding points $\{(x_i, y_i)\}_{i=1}^N$ in image 1 and $\{(x'_i, y'_i)\}_{i=1}^N$ in image 2.
• Store them as arrays of shape $(N, 2)$.

B. Implement DLT homography estimation

Given at least 4 correspondences:

1. For each pair $(x, y) \leftrightarrow (x', y')$, build two rows of $A$:

$$\begin{bmatrix} -x & -y & -1 & 0 & 0 & 0 & x x' & y x' & x' \\ 0 & 0 & 0 & -x & -y & -1 & x y' & y y' & y' \end{bmatrix}$$

2. Stack these rows for all correspondences into matrix $A$ of size $(2N \times 9)$.
3. Compute SVD: $A = U \Sigma V^T$.
4. Let $h$ be the last column of $V$ (or last row of $V^T$); reshape $h$ into $3 \times 3$ matrix $H$.
5. Optionally normalize $H$ (e.g., divide by $H_{2,2}$ or $H_{2,3}$) so that scale is fixed.

Code sketch (DLT):

import numpy as np

def dlt_homography(src_pts, dst_pts):
 # src_pts, dst_pts: (N, 2), N >= 4
 N = src_pts.shape
 A = []
 for i in range(N):
 x, y = src_pts[i]
 xp, yp = dst_pts[i]
 A.append([-x, -y, -1, 0, 0, 0, x*xp, y*xp, xp])
 A.append([0, 0, 0, -x, -y, -1, x*yp, y*yp, yp])
 A = np.asarray(A)
 _, _, Vt = np.linalg.svd(A)
 h = Vt[-1]
 H = h.reshape(3, 3)
 return H / H[2, 2]

C. Define reprojection error and inliers

Given $H$ and a correspondence $(x, y) \leftrightarrow (x', y')$:

1. Map source to destination:

$$\begin{bmatrix} \tilde{x}' \\ \tilde{y}' \\ w \end{bmatrix} = H \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} \quad \Rightarrow \quad \hat{x}' = \tilde{x}' / w,\; \hat{y}' = \tilde{y}' / w$$

2. Compute error, e.g., Euclidean distance:

$$e = \sqrt{(\hat{x}' - x')^2 + (\hat{y}' - y')^2}$$

3. A point is an inlier if $e < \text{threshold}$ (e.g., a few pixels).

D. RANSAC loop

Parameters:

• max_iters: maximum number of iterations.
• threshold: reprojection error threshold.
• Optionally confidence and an estimated outlier ratio to adaptively set iterations.

Algorithm:

def ransac_homography(src_pts, dst_pts, max_iters=1000, threshold=3.0):
 N = src_pts.shape
 best_H = None
 best_inliers = None
 best_inlier_count = 0

 for _ in range(max_iters):
 # 1. Randomly sample 4 distinct indices
 idx = np.random.choice(N, 4, replace=False)
 H_candidate = dlt_homography(src_pts[idx], dst_pts[idx])

 # 2. Compute reprojection errors for all points
 ones = np.ones((N, 1))
 pts_h = np.hstack([src_pts, ones]) # (N, 3)
 proj = (H_candidate @ pts_h.T).T # (N, 3)
 proj_xy = proj[:, :2] / proj[:, 2:3] # divide by w

 errors = np.linalg.norm(proj_xy - dst_pts, axis=1)

 # 3. Determine inliers
 inliers = errors < threshold
 inlier_count = np.sum(inliers)

 # 4. Update best model
 if inlier_count > best_inlier_count:
 best_inlier_count = inlier_count
 best_inliers = inliers
 best_H = H_candidate

 # 5. Re-estimate H using all inliers
 if best_inliers is not None and np.sum(best_inliers) >= 4:
 best_H = dlt_homography(src_pts[best_inliers], dst_pts[best_inliers])

 return best_H, best_inliers

You can refine iteration count using:

$$N_\text{iters} = \frac{\log(1 - p)}{\log(1 - (1 - \epsilon)^s)}$$

where $p$ is desired success probability, $\epsilon$ is outlier ratio, and $s=4$ (sample size).

---

4. Common Pitfalls

• Degenerate samples: Four points that are nearly collinear produce an unstable homography. You should detect and skip such samples or rely on numerical conditioning (SVD often exposes degeneracies via tiny singular values).
• Lack of normalization: Not normalizing coordinates (centering and scaling) can lead to numerical instability in DLT. A more robust implementation uses Hartley normalization (shift to zero mean, scale so average distance is $\sqrt{2}$), applies DLT, and denormalizes.
• Too tight / too loose threshold:
• Too small: almost no inliers; RANSAC fails.
• Too large: many outliers classified as inliers; homography is inaccurate. Choose based on expected pixel noise.
• Not re-estimating on all inliers: The homography from a single 4-point sample is noisy; always recompute $H$ using all inliers at the end.