We are given a set of $n$ points on the plane $a_i = \{x^a_i, y^a_i\}$ and $b_i = \{x^b_i, y^b_i\}$.

Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and vector $t$ such that $\sum_{i=0}^{n-1} ||M a_i + t - b_i ||^2$ is minimized, in fact, we can even do so analytically.

Assume however that the points a_i are composed of different subsets to which a different affine transform was applied.

Let $\epsilon$ be a small, tolerance value. A partition $\cup_{j=0}^m P_j = [1\ldots n] \wedge \forall j, k, P_j \cap P_k = \emptyset$ is said to be admissible iff

$$\forall j,~ \exists M_j, t_j,~ \forall i \in P_j,~ ||M_j a_i + t_j - b_i||^2 < \epsilon$$

Simply speaking, we partition the points into different subsets each of which is sent to $b$ with its own affine transform.

An admissible partition always exists because it's always possible to sent a to b exactly if each point is given its own affine transform (in fact, every 3 points can be sent to any other 3 points).

We want to cut up the points in as few pieces as possible: an admissible partition is minimal when it has fewer or equal subsets than any other admissible partitions.

How would one go about finding an admissible partition? Heuristics and approximate solutions are welcome. One approach would be to consider the transformation defined by every triplet of points and try to cluster those together, but this requires looking at $O(n^3)$ transforms.


1 Answer 1


I would suggest you try using RANSAC. Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those. Repeat many times, and keep the best cluster. Remove the points in that cluster, and then repeat.

This might perform better than your $O(n^3)$ time solution if you expect to have a few large clusters (but probably it is not better if you expect to have many small clusters).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.