Algorithm: 2D transformation, find outlying pairs of points and omit

Question

I am looking for the following type of algorithm:

There are n matched pairs of points in 2D. How can I identify outlying pairs of points according to Affine / Helmert transformation and omit them from the transformation key? We do not know the exact number of such outlying pairs.

I cannot use Trimmed Least Squares method because there is a basic assumption that a k percentage of pairs is correct. But we do not have any information about the sample and do not know the k... In such a sample of all pairs could be correct or vice versa.

Which types of algorithms are suitable for this problem?

Answer 1

Use RANSAC:

Repeat the following steps a fixed number of times:

• Randomly select as much pairs as are necessary to compute the transformation parameters.
• Compute the parameters.
• Compute the subset of pairs that have small projection error (the 'consensus set').
• If the consensus set is large enough, compute a projection for it (e.g. with Least Squares).
• Computer the consensus set's projection error
• Remember the model if it is the best you found so far.

You have to experiment to find good values for

• "a fixed number of times"
• "small projection error"
• "consensus set is large enough".

Answer 2

The simplest approach is compute your transformation based on all points, compute the residuals for each point, remove the points with high residuals until you reach an acceptable transformation or hit the minimum number of acceptable input points. The residual for any given point is the join distance between the forward transformed value for a point, and the intended target point.

Note that the residuals between an affine transformation and a Helmert (conformal) transformation will be very different as these transformations do different things. The non-uniform scale of the affine has more 'stretch' and will hence lead to smaller residuals.