Automated registration

If the coordinates of your images are just offset from each other (related by a translation in X and Y) and they have image features in common it may be possible to register them with a minimum of effort and preparation. More precisely, the relation between coordinates does not have to be exactly an offset, but to be sufficiently `well modelled' by an offset, that is with distorting terms small enough that the error in positioning is in general a larger effect.

Automated registration is performed by the applications:

• FINDOBJ
• FINDOFF
• REGISTER

used in that order.

FINDOBJ locates and centroids image features, FINDOFF determines the correspondence of the image-features and REGISTER produces the mappings from this information. This sequence is used in the demonstration script ccdexercise.

FINDOBJ works by looking for pixels above a threshold value, objects are then identified as groups of `connected' pixels. The groups of connected pixels are then centroided to give an accurate position. FINDOBJ has a number of parameters which can be tweaked to identify a suitable group of objects from the data; however if you can't make it work satisfactorily you could use the interactive program IDICURS instead for this step.

FINDOFF is the crucial application in this sequence, it performs pattern-matching between all the object positions. It assesses the degree of match found between each pair of frames and assigns it a weight. The best matches are then used to identify corresponding objects on each frame. The inter-comparison process which provides the pattern-matching facilities uses two algorithms, one which matches all the point pair-offsets between any two input lists, counting all the other points which are then paired (within an error box). The match with the most positions paired is then chosen. The second uses a statistical algorithm based on histograms of the differences in the offsets (where the peak in a histogram is assumed to be the most likely difference). In each case an estimate of the positional error must be given as it is used when deciding which positions match or as the bin size when forming histograms.

Which algorithm you should use depends on the number of points your position lists contain and the expected number of objects in the overlaps. Obviously it is much easier to detect a match between two lists which have most of their positions in common. With small overlaps a serious concern is the likelihood of finding a `false' match. False matches are more likely the larger the datasets and the smaller the overlaps.

The first algorithm (named SLOW) is the most careful and is capable of pairing positions in data with small overlaps (although a level of false detections will always be present) but the process is inherently slow scaling as $N^{3}\ln_{2}N$. The second algorithm (named FAST) is an N² process so is much quicker, but requires better overlap statistics. The maximum time taken for determining the correspondence of two position lists for the SLOW algorithm are shown in table . If you intend to process large lists then take heed.

Table: Maximum time taken to process two lists of N points. The tests were run on a DEC Alpha 3000/300.

N	50	100	250	500	1000
Time (seconds)	0.5	2.5	53	535	5800

Because the FAST process takes so little CPU time it is better to try this first (without the SLOW process as a backup, FAILSAFE=FALSE), only use the SLOW algorithm when you have small datasets or do not have large overlaps.

Having obtained estimates of the offsets between each dataset pair and the number of positions in common, the next stage is to determine a global solution to the registration of all the datasets. A major consideration is the possible presence of false matches.

The global registration process works by forming a graph with each position list at a node and with connecting edges of weight the number of matched position-pairs. The edge weights may be modified by a completeness factor which attempts to assess the quality of the match (this is based on the ratio of the expected number of matches in the overlap region to the actual number, random matches shouldn't return good statistics when compared with genuine ones). This still leaves a possibility of false matches disrupting any attempt to register the datasets so a single `spanning tree' is chosen (this is a graph which just visits each node the minimum number of times required to get complete connectivity, no loops allowed) which has the highest possible number of matched positions (rejecting edges with few matched positions/low completenesses where possible). This gives a most likely solution to the offsets between the position lists, rather than the best solution which could well include false matches; compare this with a median as opposed to a mean. This registration is then used to identify objects in all datasets, resulting in labelled position lists which are output for use by REGISTER.

Note it is not necessary that the pixel grids of the images are simply related by an offset, but that their Current coordinate systems are. For instance you might have two images with reasonably accurate SKY coordinate systems which were attached by the observing system, but which you wish to register more accurately by matching image features. The telescope was rotated as well as shifted between the observations so that the X-direction of one data array is different from the X-direction of the other. But since the SKY coordinate system of each only has small errors, the RA-direction of each is the same. Then as long as SKY is the Current coordinate system, the methods in this section can be used to align the images automatically (see section § for an example). If you know the non-offset parts of the transformation but they are not already present as attached coordinate systems, then you may be able to add them yourself using WCSEDIT or ASTIMP as explained in later sections.

Invoking FINDOBJ, FINDOFF and REGISTER is simple.

% findobj in='*' outlist='*.find'
% findoff inlist='*' outlist='*.off' error=1
% register inlist='*' fittype=1

This locates the objects on all the images in the current directory, performs pattern-matching and finally registers them, attaching a new coordinate system labelled `CCD_REG' to each image. See ``Using position lists'' if using `*' for both the IN and INLIST parameters seems mysterious.

If the coordinates of the images are already quite well matched (offsets are expected to be small) and the object matching is just to improve the alignment, then FINDOFF can be invoked with the RESTRICT parameter; this instructs it to look for matching objects only in the parts of the images which overlap according to the existing Current coordinate system, which can dramatically decrease running time and the likelihood of a false match.

FINDOFF's other parameters are detailed in a later section and some of its internals are explained in P.W. Draper, 1993, `Preparing multiple CCD frames for the photometry of extended fields', Proceedings of the 5th ESO/ST-ECF Data Analysis Workshop.