Procrustes Alignment Error
You are given two sets of corresponding 2D points and need to compute the alignment error (sum of squared distances between corresponding points).
After aligning point sets (e.g., by centering at origin), the alignment error measures how well they match:
E=∑i=1n​∥pi​−qi​∥2=∑i=1n​[(px,i​−qx,i​)2+(py,i​−qy,i​)2]
This is used in:
- Procrustes analysis for shape matching
- ICP convergence checking
- Evaluating transformation quality
Lower error means better alignment.
Example:
points1 = [(0, 0), (1, 0)] points2 = [(0, 0), (1, 0.1)]
0.01
Computing squared distances for each pair:
Pair 1: (0,0) ↔ (0,0)
- dx = 0 - 0 = 0
- dy = 0 - 0 = 0
- squared_dist = 0² + 0² = 0
Pair 2: (1,0) ↔ (1,0.1)
- dx = 1 - 1 = 0
- dy = 0 - 0.1 = -0.1
- squared_dist = 0² + (-0.1)² = 0.01
Total error = 0 + 0.01 = 0.01
The small error indicates the point sets are nearly identical.
Constraints:
- points1 and points2 are lists of corresponding (x, y) points of same length
- Each point in points1 corresponds to the same-indexed point in points2
- Return total squared error rounded to 4 decimal places
More from CV: Image Alignment and Stitching
Procrustes Alignment Error: Background & Strategy
Background Knowledge
Procrustes Analysis Fundamentals
Procrustes analysis is a statistical technique for comparing two shapes by finding the optimal transformation (rotation, reflection, and/or translation) that aligns one point set to another. The core idea is that two shapes may be identical but differ in position, orientation, or scale. By applying geometric transformations, we can measure how similar the shapes truly are. The alignment error quantifies this similarity: it's the sum of squared Euclidean distances between corresponding points after optimal alignment. This metric is fundamental because it's scale-invariant and rotation-invariant once proper alignment is applied.
Why This Matters in Computer Vision
In image alignment and stitching applications, you frequently encounter scenarios where you have two sets of corresponding feature points (e.g., detected corners or keypoints) from different images or views. The Procrustes alignment error helps determine whether these correspondences are correct and how well the geometric transformation between images works. Lower error indicates better alignment quality. This is also critical in Iterative Closest Point (ICP) algorithms, where alignment error convergence signals when the algorithm has found a stable solution.
Mathematical Foundation
The formula you've been given computes the sum of squared residuals after alignment. Before computing this error, the point sets are typically centered (translated so their centroids is at the origin). This preprocessing step removes translation as a variable, allowing you to focus on rotation and scale. The squared distances are summed rather than taking absolute distances because: (1) squaring penalizes larger errors more heavily, (2) it's mathematically convenient for optimization, and (3) it's differentiable everywhere, making it suitable for gradient-based methods.
Algorithm/Approach
The general approach to solving Procrustes alignment error problems follows this pattern:
- Preprocess the point sets: Center both sets by subtracting their centroids
- Compute the optimal transformation: Use Singular Value Decomposition (SVD) or similar techniques to find the best rotation/reflection matrix
- Apply the transformation: Transform one point set using the optimal transformation
- Calculate the error: Compute the sum of squared distances using the formula provided
The key insight is that once you've found the optimal alignment transformation, computing the error is straightforward—it's just the Euclidean distance formula applied to all corresponding points.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.