Point pattern matching

Another method to register images efficiently makes use of point-pattern matching. The peak detector is applied to all input planes, and the search for offsets is then performed by using only on geometrical point positions. Among many algorithms comparing lists of points to find similar geometries, the fastest and most reliable one was identified as the one described by F. Murtagh in [Murtagh 92]. See references for other point-pattern matching algorithms.

The algorithmic problem can be described as: two lists of point coordinates are related by the fact that in each list it is possible to extract a subset containing matching points, i.e. points which are bound pairwise by the following transformation:

$$\left\{ \begin{array}{l} x' = x + dx + N_x(x,y) \\ y' = y + dy + N_y(x,y) \end{array} \right.$$

where (dx,dy) is a fixed vector for all point pairs, and N_x(x,y), N_y(x,y) are two noise functions depending on the point position. (x',y') is the matching point associated to (x,y). The amount of added noise in the position by N_x and N_y should remain small, typically less than 10 pixels over a 1024² image.

Actually, transformations supported by Murtagh's algorithm include scale changes and rotations, but these are irrelevant to the jitter case and thus have been suppressed from the algorithmic search to limit possibilities of errors. The main issue is, given the two lists, to identify candidate transformations and associated lists of matching points. The point-pattern matching algorithm does not actually try to compute the transformation, it rather tries to identify point patterns with criteria which are independant from scale, offset, and rotation changes.

Differences brought to this algorithm for our implementation are the following:

• The definition of the world-view of a point has been extended to yield more precision (a factor 10) in the matching evaluation.
• Only geometrical point positions are used for pattern matching. It is reasonable to think that by adding some more informations about points to match such as star colour or relative brightness, one could improve the detection by excluding impossible matches. Provision has been taken to easily include that kind of information in the code.

Some more work has been done in the direction of removing impossible matching pairs, e.g. a point which is found is several pairs. The algorithm is run several times with rejection criteria, only the most stable points are retained. Matching efficiency is greatly increased this way.

Once the points have been matched they are sorted out by pairs. A least-square algorithm is applied to estimate the best translation vector between both sets.

Example: figure 6 shows an example of point-pattern matching over 50 points. The first list has been randomly generated, the second one has been shifted from the first by an offset vector of (12.34, 34.56), and then a gaussian noise of maximum 10 pixels amplitude has been added to the point positions in the second list. Points have then been randomly removed from each list, leaving 47 points in the first list and 43 in the second one. The matcher indicates 41 matching point pairs, and an estimated offset of (12.30 , 34.34).

  

Figure 6: Point Pattern Matching: example

This method has been proved extremely precise because there are always many points of interest in SOFI/ISAAC images, which allows building a least-square estimation from a high number of point pairs. However, the reliability of the pattern matching is only about $80\%$ at this stage, which excludes the possibility to use it without user interaction (cross-correlation reaches $100\%$. Some more work has to be done to fine-tune it automatically and bring its reliability to a higher value. This technique might also be used together with cross-correlation as a first estimate for the place to look for matches. For the moment, none of this algorithm is actually present in the code implementing the jitter reduction process.