REFERENCES · EXAMPLES · TIME_REQUIREMENTS · BUGS · SEE_ALSO

## NAME

xyxymatch -- Match pixels coordinate lists using various methods

## USAGE

`xyxymatch input reference output tolerance`

## PARAMETERS

- input
- The list of input coordinate files.

- reference
- The list of reference coordinate files. The number of reference coordinate files must be one or equal to the number of input coordinate files.

- output
- The output matched x-y lists containing: 1) the coordinates of the object in the reference list in columns 1 and 2, 2) the coordinates of the object in the input list in columns 3 and 4, and 3) the line number of the objects in the original reference and input lists in columns 5 and 6.

- tolerance
- The matching tolerance in pixels.

- refpoints = ""
- The list of tie points used to compute the linear transformation
from the input coordinate system to the reference coordinate system. Refpoints
is a text file containing the x-y coordinates of 1-3 reference list tie points
in the first line, followed by the x-y coordinates of the 1-3 corresponding
input tie point in succeeding
lines. If refpoints is undefined then the parameters
*xin*,*yin*,*xmag*,*ymag*,*xrotation*,*yrotataion*,*xref*, and*yref*are used to compute the linear transformation from the input coordinate system to the reference coordinate system.

- xin = INDEF, yin = INDEF
- The x and y origin of the input coordinate system. Xin and yin default to 0.0 and 0.0 respectively.

- xmag = INDEF, ymag = INDEF
- The x and y scale factors in reference pixels per input pixels. Xmag and ymag default to 1.0 and 1.0 respectively.

- xrotation = INDEF, yrotation = INDEF
- The x and y rotation angles measured in degrees counter-clockwise with respect to the x axis. Xrotation and yrotation default to 0.0 and 0.0 respectively.

- xref = INDEF, yref = INDEF
- The x and y origin of the reference coordinate system. Xref and xref default to 0.0 and 0.0 respectively.

- xcolumn = 1, ycolumn = 2
- The columns in the input coordinate list containing the x and y coordinate values respectively.

- xrcolumn = 1, yrcolumn = 2
- The columns in the reference coordinate list containing the x and y coordinate values respectively.

- separation = 9.0
- The minimum separation for objects in the input and reference coordinate lists. Objects closer together than separation pixels are removed from the input and reference coordinate lists prior to matching.

- matching = "triangles"
- The matching algorithm. The choices are:
- tolerance
- A linear transformation is applied to the input coordinate list,
the transformed input list and the reference list are sorted,
points which are too close together are removed, and the input coordinates
which most closely match the reference coordinates within the
user specified tolerance are determined. The tolerance algorithm requires
an initial estimate for the linear transformation. This estimate can be
derived interactively by pointing to common objects in the two displayed
images, by supplying the coordinates of tie points via the
*refpoints*file, or by setting the linear transformation parameters*xin*,*yin*,*xmag*,*ymag*,*xrotation*,*yrotation*,*xref*, and*yref*. Assuming that well chosen tie points are supplied, the tolerance algorithm functions well in the presence of any shifts, axis flips, x and y scale changes, rotations, and axis skew, between the two coordinate systems. The algorithm is sensitive to higher order distortion terms in the coordinate transformation.

- triangles
- A linear transformation is applied to the input coordinate list, the transformed input list and the reference list are sorted, points which are too close together are removed, and the input coordinates are matched to the reference coordinates using a triangle pattern matching technique and the user specified tolerance parameter. The triangles pattern matching algorithm does not require prior knowledge of the linear transformation, although it will use one if one is supplied. The algorithm functions well in the presence of any shifts, axis flips, magnification, and rotation between the two coordinate systems as long as both lists have a reasonable number of objects in common and the errors in the computed coordinates are small. However since the algorithm depends on comparisons of similar triangles, it is sensitive to differences in the x and y coordinate scales, any skew between the x and y axes, and higher order distortion terms in the coordinate transformation.

- nmatch = 30
- The maximum number of reference and input coordinates used by the "triangles" pattern matching algorithm. If either list contains more coordinates than nmatch the lists are subsampled. Nmatch should be kept small as the computation and memory requirements of the "triangles" algorithm depend on a high power of the lengths of the respective lists.

- ratio = 10.0
- The maximum ratio of the longest to shortest side of the triangles generated by the "triangles" pattern matching algorithm. Triangles with computed longest to shortest side ratios > ratio are rejected from the pattern matching algorithm. Ration should never be set higher than 10.0 but may be set as low as 5.0.

- nreject = 10
- The maximum number of rejection iterations for the "triangles" pattern matching algorithm.

- xformat = "%13.3f", yformat = "%13.3f"
- The format of the output reference and input x and y coordinates. By default the coordinates are output right justified in a field of 13 characters with 3 places following the decimal point.

- interactive = no
- Compute the initial linear transformation required to transform the input coordinate coordinates to the reference coordinate system, by defining up to three tie points using the image display and the image cursor.

- verbose = yes
- Print messages about the progress of the task ?

- icommands = ""
- The image display cursor.

## DESCRIPTION

XYXYMATCH matches the x and y coordinates in the reference coordinate list
*reference*
to the corresponding x and y coordinates in the input
coordinate list *input*
to within a user specified tolerance
*tolerance*
, and writes the matched coordinates to the output
file *output*
. The output file is suitable for input to the
GEOMAP task which computate the actual transformation required to
register the corresponding reference and input images.

XYXYMATCH matches the coordinate lists by: 1) computing an initial
guess at the linear transformation required to match the input
coordinate system to the reference coordinate system, 2) applying
the computed transformation to the input coordinates, 3) sorting
the reference and input coordinates and removing points with a
minimum separation specified by the parameter *separation*
from both lists, 4) matching the two lists using either the "tolerance"
or "triangles" algorithm, and 5) writing the matched list to the
output file.

The initial estimate of the linear transformation is computed in one of
hree ways. If *interactive*
is "yes" the user displays the reference and
input images corresponding to the reference and input coordinate files
on the image display, and marks up to three objects which the two
images have in common with the image cursor. The coordinates of these
tie points are used as tie points to compute the linear transformation.
If *refpoints*
is defined, the x-y coordinates of up to three tie
points are read from succeeding lines in the refpoints file. The format
of two sample refpoints files is shown below.

# First sample refpoints file (1 reference file and N input files) x1 y1 [x2 y2 [x3 y3]] # tie points for reference coordinate file x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file 1 x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file 2 ... x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file N # Second sample refpoints file (N reference files and N input files) x1 y1 [x2 y2 [x3 y3]] # tie points for reference coordinate file 1 x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file 1 x1 y1 [x2 y2 [x3 y3]] # tie points for reference coordinate file 2 x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file 2 ... x1 y1 [x2 y2 [x3 y3]] # tie points for reference coordinate file N x1 y1 [x2 y2 [x3 y3]] # tie points for input coordinate file N

The coordinates of the tie points can be typed in by hand if *refpoints*
is "STDIN". If the refpoints file is undefined the parameters
*xin*
, *xin*
, *xmag*
, *ymag*
, *xrotation*
, *xrotation*
,
*xref*
, and *yref*
are used to compute the linear transformation
from the input coordinates [xi,yi] to the reference coordinates [xr,yr]
as shown below. Orientation and skew are the orientation of the x and y axes
and their deviation from non-perpendicularity respectively.

xr = a + b * xi + c * yi yr = d + e * xi + f * yi xrotation = orientation - skew / 2 yrotation = orientation + skew / 2 b = xmag * cos (xrotation) c = -ymag * sin (yrotation) e = xmag * sin (xrotation) f = ymag * cos (yrotation) a = xref - b * xin - c * yin = xshift d = yref - e * xin - f * yin = yshift

The reference and input coordinates are read from columns *xrcolumn*
,
*yrcolumn*
in the reference, and *xcolumn*
, and *ycolumn*
in the
input coordinate lists respectively. The input coordinates are transformed
using the computed linear transformation and stars closer together than
*separation*
pixels are removed from both lists.

The coordinate lists are matched using the algorithm specified by
the *matching*
parameter. If matching is "tolerance", XYXYMATCH searches the sorted
transformed input coordinate list for the object closest to the current
reference object within the matching tolerance *tolerance*
.
The major advantage of the "tolerance" algorithm is that it can deal
with x and y scale differences and axis skew in the coordinate
transformation. The major disadvantage is that the user must supply
tie point information in all but the simplest case of small x and y
shifts between the input and reference coordinate systems.

If matching is "triangles" XYXYMATCH contructs a list of triangles
using up to *nmatch*
reference coordinates and transformed input
coordinates, and performs a pattern matching operation on the resulting
triangle lists. If the number of coordinates
in both lists is less than *nmatch*
the entire list is matched using
the "triangles" algorithm directly, otherwise the "triangles" algorithm
is used to estimate a new linear transformation, the input coordinate
list is transformed using the new transformation, and the entire list
is matched using the "tolerance" algorithm. The major advantage of the
"triangles" algorithm is that it requires no tie point information
from the user. The major disadvantages are that it is sensitive to
x and y scale differences and axis skews between the input and reference
coordinate systems and can be computationally expensive.

The matched x and y reference and input coordinate lists are written to
columns 1 and 2, and 3 and 4 of the ouput file respectively, in a format
specified by the *xformat*
and *yformat*
parameters.
The respective line numbers in the original reference and input
coordinate files are written to columns 5 and 6 respectively.

If *verbose*
is yes, detailed messages about actions taken by the
task are written to the terminal as the task executes.

## ALGORITHMS

The "triangles" algorithm uses a sophisticated pattern matching
technique which requires no tie point information from the user.
It is expensive computionally and hence is restricted to a maximum
of *nmatch*
objects from the reference and input coordinate lists.

The "triangles" algorithm first generates a list
of all the possible triangles that can be formed from the points in each list.
For a list of nmatch points this number is the combinatorial factor
nmatch! / [(nmatch-3)! * 3!] or nmatch * (nmatch-1) * (nmatch-2) / 6.
The length of the perimeter, ratio of longest to shortest side, cosine
of the angle between the longest and shortest side, the tolerances in
the latter two quantities and the direction of the arrangement of the vertices
of each triangle are computed and stored in a table.
Triangles with vertices closer together than *tolerance*
or
with a ratio of the longest to shortest side greater than *ratio*
are discarded. The remaining triangles are sorted in order of increasing
ratio. A sort merge algorithm is used to match the triangles using the
ratio and cosine information, the tolerances in these quantities, and
the maximum tolerances for both lists. Next the ratios of the
perimeters of the matched triangles are compared to the average ratio
for the entire list, and triangles which deviate too widely from the mean
are discarded. The number of triangles remaining are divided into
the number which match in the clockwise sense and the number which match
int the counter-clockwise sense. Those in the minority category
are eliminated.
The rejection step can be repeated up to *nreject*
times or until
no more rejections occur whichever comes first.
The last step in the algorithm is a voting procedure in which each remaining
matched triangle casts three votes, one for eached matched pair of vertices.
Points which have fewer than half the maximum number of
votes are discarded. The final set of matches are written to the output file.

The "triangles" algorithm functions well when the reference and
input coordinate lists have a sufficient number of objects (~50%,
in some cases as low as 25%) of their objects in common, any distortions
including x and y scale differences and skew between the two systems are small, and the random errors in the coordinates
are small. Increasing the value of the *tolerance*
parameter will
increase the ability to deal with distortions but will also produce more
false matches.

## FORMATS

A format specification has the form "%w.dCn", where w is the field width, d is the number of decimal places or the number of digits of precision, C is the format code, and n is radix character for format code "r" only. The w and d fields are optional. The format codes C are as follows:

b boolean (YES or NO) c single character (c or '\c' or '\0nnn') d decimal integer e exponential format (D specifies the precision) f fixed format (D specifies the number of decimal places) g general format (D specifies the precision) h hms format (hh:mm:ss.ss, D = no. decimal places) m minutes, seconds (or hours, minutes) (mm:ss.ss) o octal integer rN convert integer in any radix N s string (D field specifies max chars to print) t advance To column given as field W u unsigned decimal integer w output the number of spaces given by field W x hexadecimal integer z complex format (r,r) (D = precision) Conventions for w (field width) specification: W = n right justify in field of N characters, blank fill -n left justify in field of N characters, blank fill 0n zero fill at left (only if right justified) absent, 0 use as much space as needed (D field sets precision) Escape sequences (e.g. "\n" for newline): \b backspace (not implemented) \f formfeed \n newline (crlf) \r carriage return \t tab \" string delimiter character \' character constant delimiter character \\ backslash character \nnn octal value of character Examples %s format a string using as much space as required %-10s left justify a string in a field of 10 characters %-10.10s left justify and truncate a string in a field of 10 characters %10s right justify a string in a field of 10 characters %10.10s right justify and truncate a string in a field of 10 characters %7.3f print a real number right justified in floating point format %-7.3f same as above but left justified %15.7e print a real number right justified in exponential format %-15.7e same as above but left justified %12.5g print a real number right justified in general format %-12.5g same as above but left justified %h format as nn:nn:nn.n %15h right justify nn:nn:nn.n in field of 15 characters %-15h left justify nn:nn:nn.n in a field of 15 characters %12.2h right justify nn:nn:nn.nn %-12.2h left justify nn:nn:nn.nn %H / by 15 and format as nn:nn:nn.n %15H / by 15 and right justify nn:nn:nn.n in field of 15 characters %-15H / by 15 and left justify nn:nn:nn.n in field of 15 characters %12.2H / by 15 and right justify nn:nn:nn.nn %-12.2H / by 15 and left justify nn:nn:nn.nn \n insert a newline

## REFERENCES

A detailed description of the "triangles" pattern matching algorithm used here can be found in the article "A Pattern-Matching Algorithm for Two- Dimensional Coordinate Lists" by E.J. Groth, A.J. 91, 1244 (1986).

## EXAMPLES

1. Match the coordinate list of an image to the coordinate list of a reference image using the trangles matching algorithm and a tolerance of 3 pixels. Use the resulting matched list to compute the transformation required to register the input image lpix to the reference image. For completeness this example demonstrates how the individual input and reference coordinate lists can be generated.

cl> imlintran dev$pix[-*,*] lpix xrot=15 yrot=15 xmag=1.2 \ ymag=1.2 xin=INDEF yin=INDEF xref=265.0 yref=265.0 \ ncols=INDEF nlines=INDEF cl> daofind dev$pix fwhm=2.5 sigma=5.0 threshold=100.0 cl> daofind lpix fwhm=2.5 sigma=5.0 threshold=100.0 cl> xyxymatch lpix.coo.1 pix.coo.1 xymatch toler=3 \ matching=triangles cl> geomap xymatch geodb 1.0 512.0 1.0 512.0

2. Match the coordinate lists above using the tolerance matching algorithm and the image display and cursor.

cl> display dev$pix 1 fi+ cl> display lpix 2 fi+ cl> xyxymatch lpix.coo.1 pix.coo.1 xymatch toler=3 \ matching=tolerance interactive+ ... Mark three points in the reference image dev$pix ... Mark three points in the input image lpix cl> geomap xymatch geodb 1.0 512.0 1.0 512.0

3. Repeat example 2 but run xyxymatch non-interactively by setting the appropriate linear transformation parameters rather than marking stars on the image display.

cl> ... cl> xyxymatch lpix.coo.1 pix.coo.1 xymatch toler=3 \ matching=tolerance xmag=1.2 ymag=1.2 xrot=165 \ yrot=345 xref=646.10 yref=33.38 cl> geomap xymatch geodb 1.0 512.0 1.0 512.0

4. Repeat example 2 but run xyxymatch non-interactively inputing the appropriate linear transformation via a list of tie points rather than marking stars on the image display or creating a refpoints file.

cl> ... cl> type refpts 442.0 409.0 380.0 66.0 69.0 460.0 82.0 347.0 207.0 84.0 371.0 469.0 cl> xyxymatch lpix.coo.1 pix.coo.1 xymatch toler=3 \ refpoints=refpts matching=tolerance cl> geomap xymatch geodb 1.0 512.0 1.0 512.0

## TIME REQUIREMENTS

## BUGS

## SEE ALSO

daophot.daofind,lintran,imlintran,geomap,register,geotran