# Clustering a set of point by affine transform

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.

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).