Use RANSAC for rejecting outier triangles

[cgarling]

After rejecting outlier triangles, you can then derive the best-matching transformation given the set of all "good" triangles rather than the single best triangle.

Shouldn't be blocking for release but would be nice to have at some point. Some example code is here.

[icweaver]

100%, thanks Chris! Will get a milestone tag going

[RainerHeintzmann]

An alternative is to use the found triangle and then check for all of the already found stars, whether they have matching partners and use them in the Kabsch algorithm. This is implemented in the PR.
However, I am still struggling a bit to understand the norm that was used. Just the best side-ratios in triangles seems a bit dangerous to me. I guess one wants the triangles to cover a decent size of the field of view as well as a transformation, which seems currently defined by only a singe well-matching triangle, to not massively change scales or alike. Are there any measures to prevent this? Any ideas how to best avoid such potential problems? Thanks for this great repo!

[cgarling]

The ratio of side lengths is one example of a geometric hashing algorithm to represent the set of all possible unique triangles. When generalizing to more than 3 sources per set there are other choices that can be made for how to represent the configuration of the sources (see e.g. section 2.2 of Lang+2010).

And for robustness you want to find the best transformation given the set of all matching triangles between the frames. This can be found in several ways, typically the simplest solution is an overconstrained chi-squared minimization (it looks like this is what CoordinateTransformations.kabsch does, I'm familiar with the Umeyama 1991 algorithm they use for the similarity transformation).

However it is difficult to determine the set of triangles which match between images a priori because some sources that are detected in one frame may be missing from another. Therefore triangles that can be constructed from one image may not be able to be constructed from another due to these missing sources. This is where algorithms like RANSAC can help. E.g., you can define a goodness-of-fit metric and a tolerance that can be used to adaptively filter out non-matching triangles as the transformation is refined.

[icweaver]

Exactly. Currently, it's still very easy to get false positives with my naive starting implementation. RANSAC would make things much more robust and in line with the reference Python impl

[RainerHeintzmann]

Is the current implementation preserving parity (handedness)?
One worry is the selection of a wrong triangle, but I think if one limits the scaling to maybe +-5% and like currently chooses only the 10 brightest stars, this is probably OK.
However it is also important that such a triangle covers a substantial part of the field of view which is what worried me more. This is why I implemented the matching of more stars without the need for triangles. Limiting the triangles to a minimum area (10% of the total area?) would also be a good idea.

[icweaver]

It's my understanding that the current scheme has the same guarantees as the mapping used in the reference paper (eq. 3), i.e., the triangles are fully described up to translation, rotation, scaling, and coordinate flipping.

I don't have detailed knowledge about this though, and will defer to you and Chris on additional concerns to consider. I imagine that using RANSAC to accomplish steps 4 and 5 of the alignment algorithm proposed on pg. 2 will get us most of the way there

[cgarling]

Unless I'm mistaken we are actually not fitting scale (we set scale=false when calling CoordinateTransformations.kabsch). Rigid transformations only do translation and rotation, if we set scale=true in the kabsch call then a full similarity transformation is fit which does translation, rotation, and scaling (see here). Both methods will correct for orientation / handedness if I understand your terminology correctly Rainer.

[RainerHeintzmann]

I we should be careful to not mix between the
assignment problem
and the
transformation problem.

The Kabsch algorithm deals with transformation but needs an assignment. My issue is that the triangle ratios in being scale-invariant open the gate for wrong assignments (e.g. a large triangle to a small one) which we can possibly avoid.
I found some old code dealing with robust point matching for thin plate splines. Maybe this can also be applied to the astro alignment problem at hand.