# Image Registration Software: Iterated Five-Parameter Linear Least-Squares Fitting

## Introduction

FORTRAN code lsqtrsdrv.f processes pixel coordinates of selected points simultaneously specified in two different coordinate systems that have some known relative rotation and x and y offset, all of which may be slightly in error. The possibility of slight x and y scale changes between the two coordinate systems, which have been previously unaccounted for, is also entertained. The software solves for small corrections to the relative rotation angle, x and y offsets, and x and y scale factors, which are required to register the two coordinate systems.

Optionally, the software produces fits with the same x and y scales for both coordinate systems and/or fits with no rotation between the two coordinate systems. It has also been recently upgraded to perform optional outlier rejection.

The software is an extension of source code developed by Howard McCallon for the 2MASS program.

## Description

The software fits source position data {x, y; x', y'} given in two different coordinate systems, and initial estimates of the relative rotation angle {t0}, and x and y offsets {x0, y0} between the two coordinate systems to the model
```x'=[(1+a1)x+a2][cos(t0)+a0sin(t0)]+[(1+a3)y+a4][sin(t0)-a0cos(t0)]+x0

y'=-[(1+a1)x+a2][sin(t0)-a0cos(t0)]+[(1+a3)y+a4][cos(t0)+a0sin(t0)]+y0

```
by adjusting the parameters {a0, a1, a2, a3, a4} using the method of least squares (LSQ).  Thus the model allows for small additional differences in rotation angle, and x and y offsets, as well as small changes in x and y scale between the two coordinate systems.

Because, as an approximation, the data model is linear in its fit parameters, a good fit will not be obtained unless the correction rotation angle (a0), x and y offsets (a2, a4), and x and y scale changes (a1, a3) are sufficiently small. To partly make up for the deficiencies of the linear approximation, the LSQ routine is iterated to improve the fit.

The image registration data {t0, x0, y0} are zero for the present application; estimates of these quantities for the general case may be obtained using rotlsqdrv2.f, where t0=theta, x0=delta", and y0=gamma".

Only rotations about (x=0, y=0) are currently handled by lsqtrsdrv.f.

At least three sources (three sets of {x, y, x', y'} pixel coordinates) are required for the data fitting of all five parameters (translation, rotation, and plate scales). A minimum of two sources are required when data fitting with either no rotation or no plate-scale changes. A minimum of one source is requred when data fitting with both no rotation and no plate-scale changes.

The optional outlier-rejection capability of the software is enabled by specifying a greater-than-zero minimum tolerable reduction in reduced chi2 of the fit to the data with outlier candidates excluded, relative to the case where no sources are rejected. Outlier candidates are selected on the basis of whether their radial position deviations from the fit are greater than a specified tolerance, or whether their x or y position deviations from the fit are greater than a specified non-integral multiple of the fit standard deviation with the source in question excluded from the estimate of the fit standard deviation.

The software is now under both CVS version control (/proj/wire/cvsroot/da/russ/acs), and make control (makefile.f). The executables have been delivered to /proj/wire/tst/bin. The source codes are located in /proj/wire/russ/acs.

## Required and Optional Inputs

The following is a list of the required inputs for lsqtrsdrv.f:
1. Pixel coordinates of source points in the two coordinate systems of interest {x, y; x', y'}.
2. Source-point weights (the higher the weight, the more accurate the pixel coordinates).
3. Initial estimates of {t0, x0, y0}.
4. Weighted average standard deviation of the data.

The source positions and weights are read from standard input, one source per line, where each line includes {x, y; x', y'; w} in that order.

The weighted average standard deviation of the data is only used to normalize the goodness of fit measure, chi2, which is included with the outputs. Its value affects how outlier rejection is done (but it does not affect the convergence of the iterated linear least-squares fitting).

The table below describes the available command-line inputs.

Command-line input  Definition
-x0 value Estimate of x offset (pixels).  Default is zero.
-y0 value Estimate of y offset (pixels).  Default is zero.
-t0 value Estimate of rotation angle (degrees).  Default is zero.
-siginp or -sig value Weighted average standard deviation (pixels).  Default is 0.1 pixels.
-chi2tol or value Minimum tolerable reduction in reduced chi2 for acceptable fit with outlier candidates excluded versus no sources rejected. Must be greater than zero to enable outlier-rejection processing. Default is 0.0.
-npostol or value Number of x or y fit standard deviations that are used as maximum tolerable x or y deviations between data and fit in the outlier-rejection processing. Default is 5.0.
-radtol or value Maximum tolerable radial position deviations between data and fit, used as a basis for outlier rejection. Default is 0.25 pixels.
-noscale or -nos Switch that causes the data fitting to be done with no scale change between the two coordinate systems.
-norotation or -nor Switch that causes the data fitting to be done with no rotation between the two coordinate systems.
-verbose or -v  Verbose mode. Default is off.
-test  Execute in test mode? Default is no test mode.  Five test source positions and weights, which are embedded within the software, are used.

## Outputs

The final outputs are:

a2 (pixels)
a4 (pixels)
a1 (dimensionless)
a3 (dimensionless)
a0 (degrees)
Corrected x offset (pixels)
Corrected y offset (pixels)
Corrected rotation angle (degrees)
Number of sources kept for final data fitting
Number of outliers rejected
chi2 (dimensionless)
# of degrees of freedom
x residual (pixels)
x standard deviation (pixels)
y residual (pixels)
y standard deviation (pixels)

Note that the corrected x and y offsets and rotation angle are given in terms of theta, delta", and gamma" as defined for rotlsqdrv2.f.

## Usage and Sample Outputs

Example of how to execute lsqtrsdrv.f with the test and verbose switches invoked:
`lsqtrsdrv -test -v`

In this case, five parameters are computed. The corresponding output is

```\$Id: lsqtrsdrv.f,v 1.10 1998/04/06 14:40:15 laher Exp \$

lsqtrsdrv.f
Date - Time: 04/06/1998(98096) - 07:46:06 | Cpu:   0.140   0.050u  0.090s

All parameters for command /proj/wire/tst/bin/lsqtrsdrv:

t0=0.;x0=0.;y0=0.;xpivot=0.;ypivot=0.;siginp=0.1;chi2tol=0.0;npostol=5.0;

Solving for 5 parameters: dx, dy, dt, dsx, and dsy

TESTING: Running with   5 test points.

Input for test case:
t0    =    215.00000000000
x0    =    402.00000000000
y0    =   103.000000000000
dx    =   -6.8793509513911
dy    =   -11.462308364455
dtheta=   -5.2000000000000
dsx   =    5.0000000000000D-02
dsy   =   -8.0000000000000D-02

x          y          x'         y'         w
41.18000   46.43000  353.85902  102.58388    2.00000
24.74000   86.17000  343.41214   63.35384    1.50000
69.13000  109.95000  293.48325   76.77087    1.00000
73.46000   74.21000  311.29978  104.93936    0.50000
25.25000  115.94000  325.25586   42.69128    0.25000

Fitting input data...

Output from lsqtrsdrv.f (lsqtrs2):

Iter       dxout       dyout       dtout      dsxout      dsyout        chi2
1  -8.166E+00  -1.110E+01  -5.009E+00   4.883E-02  -8.117E-02   1.282E+03
2  -6.902E+00  -1.157E+01  -5.199E+00   5.024E-02  -7.961E-02   2.789E+00
3  -6.900E+00  -1.156E+01  -5.199E+00   5.024E-02  -7.961E-02   2.467E+00
4  -6.900E+00  -1.156E+01  -5.199E+00   5.024E-02  -7.961E-02   2.467E+00
Iterated linear LSQ routine converged after   4 iterations.

Final outputs:
dxout       =   -6.9001318568390
dyout       =   -11.561123163140
dsxout      =    5.0239558133034D-02
dsyout      =   -7.9605503783698D-02
dtout       =   -5.1986277857829
delx        =    414.78361741244
dely        =    107.39804871681
theta       =    220.19862778578
scalex      =    1.0502395581330
scaley      =   0.92039449621630
# kept      =  5
# rejected  =  0
chi2        =    2.4670984176760
# degs frdm =  5
x residual  =    5.30773E-02
x std. dev. =    6.88436E-03
y residual  =    4.46616E-02
y std. dev. =    7.10467E-03

```

Example of how to execute lsqtrsdrv.f to solve for only x and y shifts and a rotation angle (keeping the x and y scales fixed):

`lsqtrsdrv -test -v -nos -siginp 0.05`

For this case, the input sigma is set to the same value used by rotlsqdrv2.f for fitting the same data using a different technique. The corresponding output is

```\$Id: lsqtrsdrv.f,v 1.10 1998/04/06 14:40:15 laher Exp \$

lsqtrsdrv.f
Date - Time: 04/06/1998(98096) - 07:47:38 | Cpu:   0.120   0.050u  0.070s

All parameters for command /proj/wire/tst/bin/lsqtrsdrv:

t0=0.;x0=0.;y0=0.;xpivot=0.;ypivot=0.;siginp=0.05;chi2tol=0.0;npostol=5.0;

Solving for 3 parameters: dx, dy, and dt

TESTING: Running with   5 test points.

Input for test case:
t0    =    69.000000000000
x0    =  -10.0000000000000
y0    =   102.000000000000
dx    =   -2.4129448887140
dy    =  -0.97655814427490
dtheta=   -2.1958000000000
dsx   =  0.
dsy   =  0.

x          y          x'         y'         w
41.18000   46.43000   45.53000   79.94000    2.00000
24.74000   86.17000   77.87000  108.36000    1.50000
69.13000  109.95000  114.63000   73.98000    1.00000
73.46000   74.21000   82.23000   58.30000    0.50000
25.25000  115.94000  106.12000  117.37000    0.25000

Fitting input data...

Output from lsqtrsdrv.f (lsqtrs2):

Iter       dxout       dyout       dtout      dsxout      dsyout        chi2
1  -2.479E+00  -9.387E-01  -2.195E+00   0.000E+00   0.000E+00   2.516E+01
2  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.573E+00
3  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.573E+00
4  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.574E+00
5  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.573E+00
6  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.573E+00
7  -2.445E+00  -1.032E+00  -2.197E+00   0.000E+00   0.000E+00   4.573E+00
Iterated linear LSQ routine converged after   7 iterations.

Final outputs:
dxout       =   -2.4452442699382
dyout       =   -1.0321920116430
dsxout      =  0.
dsyout      =  0.
dtout       =   -2.1968080150192
delx        =   -11.766586855050
dely        =   103.983473445258
theta       =    71.196808015019
scalex      =    1.0000000000000
scaley      =    1.0000000000000
# kept      =  5
# rejected  =  0
chi2        =    4.5735325777658
# degs frdm =  7
x residual  =   -2.36911E-03
x std. dev. =    3.57262E-02
y residual  =    2.86211E-03
y std. dev. =    2.32810E-02

```

The results from lsqtrsdrv.f and rotlsqdrv2.f for this case agree to within 0.07 pixels (~1 arcsecond for WIRE pixels) for the offsets, and to within 0.001 degrees for the rotation (which is negligible).

Example of how to execute lsqtrsdrv.f on the test case with outlier rejection enabled:

`lsqtrsdrv -test -v -chi2tol 0.8`

The corresponding output is

```\$Id: lsqtrsdrv.f,v 1.10 1998/04/06 14:40:15 laher Exp \$

lsqtrsdrv.f
Date - Time: 04/06/1998(98096) - 07:42:30 | Cpu:   0.130   0.020u  0.110s

All parameters for command /proj/wire/tst/bin/lsqtrsdrv:

t0=0.;x0=0.;y0=0.;xpivot=0.;ypivot=0.;siginp=0.1;chi2tol=0.8;npostol=5.0;

Solving for 5 parameters: dx, dy, dt, dsx, and dsy

TESTING: Running with   5 test points.

Input for test case:
t0    =    215.00000000000
x0    =    402.00000000000
y0    =   103.000000000000
dx    =   -6.8793509513911
dy    =   -11.462308364455
dtheta=   -5.2000000000000
dsx   =    5.0000000000000D-02
dsy   =   -8.0000000000000D-02

x          y          x'         y'         w
41.18000   46.43000  353.85902  102.58388    2.00000
24.74000   86.17000  343.41214   63.35384    1.50000
69.13000  109.95000  293.48325   76.77087    1.00000
73.46000   74.21000  311.29978  104.93936    0.50000
25.25000  115.94000  325.25586   42.69128    0.25000

Fitting input data...

Output from lsqtrsdrv.f (lsqtrs2):

Iter       dxout       dyout       dtout      dsxout      dsyout        chi2
1  -8.166E+00  -1.110E+01  -5.009E+00   4.883E-02  -8.117E-02   1.282E+03
2  -6.902E+00  -1.157E+01  -5.199E+00   5.024E-02  -7.961E-02   2.789E+00
3  -6.900E+00  -1.156E+01  -5.199E+00   5.024E-02  -7.961E-02   2.467E+00
4  -6.900E+00  -1.156E+01  -5.199E+00   5.024E-02  -7.961E-02   2.467E+00
Iterated linear LSQ routine converged after   4 iterations.

Performing outlier rejection...

Fit measure: chi2,#degfreedom,chi2reduce =     2.4670984176760  5   0.493420
Number of sources considered =   5
Number of sources to keep =   3
MAXPTS,MINPTS,npts=  5000  3  5
verb,e2tol=  1   0.800000
theta0,delta,gamma=   -3.7524578917878    402.00000000000   103.000000000000

---With source #  1 rejected...
poserrx, n*sigx   =     6.06275E-02    3.59857E-02
poserry, n*sigy   =     5.35371E-02    2.80677E-02
---With source #  4 rejected...
poserrx, n*sigx   =     4.76596E-02    4.54653E-02
poserry, n*sigy   =     4.91226E-02    4.74108E-02
---With source #  2 rejected...
poserrx, n*sigx   =     5.44698E-02    5.22077E-02
poserry, n*sigy   =     3.87959E-02    4.79859E-02
---With source #  5 rejected...
poserrx, n*sigx   =     4.72983E-02    4.48699E-02
poserry, n*sigy   =     2.94774E-02    4.24879E-02
---With source #  3 rejected...
poserrx, n*sigx   =     4.00082E-02    2.80001E-02
poserry, n*sigy   =     3.72755E-02    4.54961E-02

Source #  1 is a candidate outlier

Source #  4 is a candidate outlier

Found   2 candidate outliers in rejection processing.

Fitting data with candidate outliers excluded...

Output from lsqtrsdrv.f (lsqtrs2):

Iter       dxout       dyout       dtout      dsxout      dsyout        chi2
1  -8.615E+00  -1.058E+01  -5.286E+00   4.612E-02  -8.388E-02   1.018E+03
2  -6.918E+00  -1.158E+01  -5.199E+00   4.972E-02  -7.976E-02   3.451E+00
3  -6.919E+00  -1.158E+01  -5.199E+00   4.972E-02  -7.976E-02   3.639E+00
4  -6.919E+00  -1.158E+01  -5.199E+00   4.972E-02  -7.976E-02   3.639E+00
Iterated linear LSQ routine converged after   4 iterations.

chi2,degfreedom=    3.6386776485356    1.00000
chi2minreduce,chi2reduce=   0.493420    3.6386775970459
chi2(reduced)error,e2(reduced)tol=   -6.3744068145752   0.800000

Fit with NO outliers rejected has lowest reduced chi2.

Final outputs:
dxout       =   -6.9001318568390
dyout       =   -11.561123163140
dsxout      =    5.0239558133034D-02
dsyout      =   -7.9605503783698D-02
dtout       =   -5.1986277857829
delx        =    414.78361741244
dely        =    107.39804871681
theta       =    220.19862778578
scalex      =    1.0502395581330
scaley      =   0.92039449621630
# kept      =  5
# rejected  =  0
chi2        =    2.4670984176760
# degs frdm =  5
x residual  =    5.30773E-02
x std. dev. =    6.88436E-03
y residual  =    4.46616E-02
y std. dev. =    7.10467E-03

```

For this case no sources were rejected. This is because the reduced chi2 of the fit with identified candidate outliers excluded was not lower than the reduced chi2 of the fit with no sources excluded.

## Benchmark Results

Successive iterations of the least-squares fit routine produces progressively more accurate results. Typically convergence occurs in 5-10 iterations for the rather tough criterion that the absolute relative change in chi2 must be less than 1x10-6.

Last revised: September 29, 1998

Software developer: Russ Laher (laher@ipac.caltech.edu)

URL: http://spider.ipac.caltech.edu/staff/laher/lsqtrsdrv.html