STScI Logo

xyxymatch images.immatch


NAME · USAGE · PARAMETERS · DESCRIPTION · ALGORITHMS · FORMATS
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


Source Code · Search Form · STSDAS