Estimate Translation

easyPROLeast Squares AlignmentAlignmentCV: Image Alignment and Stitching

Implement a function to estimate the optimal translation that aligns two point sets with known correspondences. This problem is rooted in Least Squares Alignment, a fundamental concept in Image Alignment and Stitching, where the goal is to find the best transformation that minimizes the distance between two sets of points.

The translation vector that achieves this alignment can be found by considering the centroids of the source and target point sets, which are the average positions of all points in each set. The optimal translation is the vector that moves the centroid of the source to the centroid of the target.

Here are the steps to estimate the translation:

Compute the centroid of the source point set.
Compute the centroid of the target point set.
Calculate the translation vector as the difference between the target and source centroids.

\mathbf{t} = \bar{\mathbf{q}} - \bar{\mathbf{p}}

This technique is widely used in computer vision applications, such as image registration and object tracking.

Example

Input

source = [(0, 0), (1, 0)]
target = [(5, 5), (6, 5)]

Output

(5.0, 5.0)

Reasoning

Inputs: source holds $n = 2$ points $\mathbf{p}_1 = (0, 0)$ , $\mathbf{p}_2 = (1, 0)$ , and target holds their partners $\mathbf{q}_1 = (5, 5)$ , $\mathbf{q}_2 = (6, 5)$ . Point $i$ of one list corresponds to point $i$ of the other.
Source centroid: $\bar{\mathbf{p}} = \left(\frac{0 + 1}{2}, \frac{0 + 0}{2}\right) = (0.5, 0)$ .
Target centroid: $\bar{\mathbf{q}} = \left(\frac{5 + 6}{2}, \frac{5 + 5}{2}\right) = (5.5, 5)$ .
Translation: $\mathbf{t} = \bar{\mathbf{q}} - \bar{\mathbf{p}} = (5.5 - 0.5,\ 5 - 0) = (5, 5)$ , rounded to 4 decimal places, giving (5.0, 5.0) as a pair $(t_x, t_y)$ .
Check: adding $\mathbf{t}$ to each source point gives $(5, 5)$ and $(6, 5)$ , exactly the targets, so the squared alignment error $\sum_i \lVert \mathbf{p}_i + \mathbf{t} - \mathbf{q}_i \rVert^2$ is $0$ .
Notice: with noisy points no single shift fits every pair, yet the centroid difference still minimises that sum of squared errors. Each pair "votes" for $\mathbf{q}_i - \mathbf{p}_i$ and the result is the average vote.

Constraints

source and target are lists of corresponding (x, y) points
Return translation as (tx, ty) tuple
Round to 4 decimal places

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

Background Knowledge

Least Squares Alignment is a fundamental technique in computer vision for registering point sets by finding the optimal transformation that minimizes the sum of squared distances between corresponding points. When restricted to translation-only transformations, this becomes one of the simplest yet most important alignment problems. The key insight is that the optimal translation doesn't require iterative optimization—it has a closed-form solution based on the centroids of the two point sets.

The mathematical foundation relies on the principle that minimizing the sum of squared errors (a least squares objective) for a translation-only transformation reduces to a simple centroid calculation. This works because translation is a linear transformation that affects all points uniformly. Unlike more complex transformations (rotation, scaling), translation has no coupling between different points—each point moves by the same vector, making the problem separable and solvable analytically.

This concept extends naturally to more complex alignment problems. Once you understand translation estimation, you can build toward rigid transformations (translation + rotation) and affine transformations, which are commonly used in image stitching and 3D reconstruction applications.

Algorithm/Approach

The approach for translation estimation follows this pattern:

Compute centroids of both point sets independently
Calculate the difference between target and source centroids
Apply the translation to verify alignment (optional for validation)

This is a direct analytical solution rather than an iterative optimization method. The translation vector is computed in a single pass through the data with no iteration needed.

Step-by-Step Strategy

Step 1: Understand the Input

You have two point sets: source points $\mathbf{P} = \{$ \mathbf{p} $_1,$ \mathbf{p} $_2, \ldots,$ \mathbf{p} $_n\}$ and target points $\mathbf{Q} = \{$ \mathbf{q} $_1,$ \mathbf{q} $_2, \ldots,$ \mathbf{q} $_n\}$
Points are typically 2D (for images) or 3D (for 3D data), represented as coordinate vectors
Correspondences are already known (point $\mathbf{p}_i$ matches with $\mathbf{q}_i$ )

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