Procrustes Analysis

Implement Procrustes analysis for optimal rigid alignment of point sets. This technique is crucial in computer vision and image processing for aligning two sets of points that differ by a rigid transformation, which includes rotation and translation.

The goal is to find the optimal rotation matrix $R$ and translation vector $t$ that minimizes the sum of squared errors between the two point sets. Given two point sets $P = \{p_i\}$ and $Q = \{q_i\}$ , the objective is to minimize $\sum_i \|R \cdot p_i + t - q_i\|^2$ .

Center both point sets by subtracting their respective centroids.
Compute the covariance matrix of the centered point sets.
Use Singular Value Decomposition (SVD) to find the optimal rotation.

\sum_i \|R \cdot p_i + t - q_i\|^2

This technique is widely used in image registration and object recognition.

Example:

Input:

source = [[0,0], [1,0], [0,1]]
target = [[1,1], [2,1], [1,2]]  # Translated by (1,1)

Output:

R=identity, t=[1,1], error≈0

Reasoning:

Centroids: source=[1/3, 1/3], target=[4/3, 4/3] Centered points are identical → rotation is identity Translation: target_centroid - source_centroid = [1, 1]

Constraints:

source: Source points (N, 2)
target: Target points (N, 2)
Return: Dict with 'R' (2×2 rotation), 't' (translation), 'error'

Example:

Constraints:

Test Results