| xyxymatch | images.immatch | xyxymatch |
xyxymatch -- Match pixels coordinate lists using various methods
xyxymatch input reference output tolerance
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.
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.
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
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).
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
daophot.daofind,lintran,imlintran,geomap,register,geotran