Sample Minimal Set

easyPRORANSAC for AlignmentRANSACCV: Image Alignment and Stitching

You are given a list of point correspondences and need to randomly sample a minimal set for model estimation.

RANSAC (Random Sample Consensus) works by:

Randomly sampling the minimum number of points needed to fit a model
Fitting the model to these points
Counting inliers (points that agree with the model)
Repeating and keeping the best model

For different transformations:

Translation: 1 correspondence
Similarity (rotation + scale): 2 correspondences
Affine: 3 correspondences
Homography: 4 correspondences

This function samples 4 correspondences for homography estimation.

Example

Input

correspondences = [
  ((0,0), (1,1)),
  ((1,0), (2,1)),
  ((0,1), (1,2)),
  ((1,1), (2,2)),
  ((2,2), (3,3))
]
seed = 42

Output

[((0, 1), (1, 2)), ((2, 2), (3, 3)), ((0, 0), (1, 1)), ((1, 0), (2, 1))]

Reasoning

Set random seed to 42 for reproducibility
Use random.sample to select 4 unique correspondences
With seed 42, the random selection returns indices 2, 4, 0, 1
Return the correspondences at these indices

The sample is used to compute a homography hypothesis.

Constraints

correspondences is a list of ((x1,y1), (x2,y2)) pairs
seed is used for reproducible random sampling
Return exactly 4 randomly sampled correspondences

Learn this in

Image Alignment and StitchingCV Study Plan

More from CV: Image Alignment and Stitching

Jacobian for Bundle Adjustmenthard Cylindrical Projection for Panoramashard Essential Matrix Estimationhard Procrustes Analysismedium Gradient Descent Updatemedium

Concept primerPREVIEW

You only need to understand what RANSAC is doing at this step: choosing a minimal set of correspondences to estimate a homography.

1. Background Knowledge (concepts & theory)

In image alignment, you have pairs of matching points $(x, y) \leftrightarrow (x', y')$ between two images (feature correspondences). A homography is a $3 \times 3$ projective transformation that maps points from one image plane to another, suitable for planar scenes or pure camera rotation.
A homography $H$ has 8 degrees of freedom (since it is defined up to scale), so you need 4 point correspondences (each gives 2 equations) to solve for it. This is called a minimal set: the smallest number of correspondences needed to uniquely determine the model parameters (assuming no degeneracy).
RANSAC uses minimal sets because:
With outliers present, fitting on all correspondences is unreliable.
By repeatedly sampling small random subsets, you increase the chance of picking an all-inlier set, which yields a good model to then validate on all points.

In this specific problem, you are implementing the part of RANSAC that, for homography estimation, randomly samples 4 distinct correspondences from the list.

2. Algorithm / General Approach

For “sample minimal set” tasks, the general pattern is:

Know the model type (translation, similarity, affine, homography, etc.).
Determine the minimal number of correspondences required for that model.
Randomly select that many distinct indices from the available correspondences.
Return the subset of correspondences corresponding to those indices.

For homography:

Minimal set size = 4.
Each sample for one RANSAC iteration = 4 randomly chosen, unique correspondences.

3. Step-by-Step Strategy to Implement

Assume you are given a list/array matches of size N, where each element is a correspondence (e.g., ((x, y), (x2, y2)) or similar):

Determine counts

Let N = len(matches).
Let S = 4 (minimal set size for homography).

Handle edge cases

If N < S, you cannot form a minimal set; decide how to handle (return error, empty list, etc.).

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results