diff options
Diffstat (limited to 'pkg/images/immatch/doc/xyxymatch.hlp')
| -rw-r--r-- | pkg/images/immatch/doc/xyxymatch.hlp | 468 |
1 files changed, 468 insertions, 0 deletions
diff --git a/pkg/images/immatch/doc/xyxymatch.hlp b/pkg/images/immatch/doc/xyxymatch.hlp new file mode 100644 index 00000000..82a8c8bb --- /dev/null +++ b/pkg/images/immatch/doc/xyxymatch.hlp @@ -0,0 +1,468 @@ +.help xyxymatch Jul95 images.immatch +.ih +NAME +xyxymatch -- Match pixel coordinate lists using various methods +.ih +USAGE +xyxymatch input reference output tolerance +.ih +PARAMETERS +.ls input +The list of input coordinate files. The input file is a whitespace-delimited +text table containing the coordinates. The \fIxcolumn\fR and \fIycolumn\fR +parameters define the coordinate columns to be used. +.le +.ls 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. +The reference file is a whitespace-delimited +text table containing the coordinates. The \fIxrcolumn\fR and \fIyrcolumn\fR +parameters define the coordinate columns to be used. +.le +.ls output +The output matched x-y lists containing three pairs of numbers: the coordinates +of the object in the reference list in columns 1 and 2, the +coordinates of the object in the input list in columns 3 and 4, and +the line number of the objects in the original reference and input +lists in columns 5 and 6. +.le +.ls tolerance +The matching tolerance in pixels. +.le +.ls 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 points in succeeding +lines. If refpoints is undefined then the parameters \fIxin\fR, \fIyin\fR, +\fIxmag\fR, \fIymag\fR, \fIxrotation\fR, \fIyrotataion\fR, \fIxref\fR, +and \fIyref\fR are used to compute the linear transformation from the +input coordinate system to the reference coordinate system. +.le +.ls 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. +.le +.ls 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. +.le +.ls 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. +.le +.ls xref = INDEF, yref = INDEF +The x and y origin of the reference coordinate system. Xref and yref default +to 0.0 and 0.0 respectively. +.le +.ls xcolumn = 1, ycolumn = 2 +The columns in the input coordinate list containing the x and y coordinate +values respectively. +.le +.ls xrcolumn = 1, yrcolumn = 2 +The columns in the reference coordinate list containing the x and y coordinate +values respectively. +.le +.ls 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. +.le +.ls matching = "triangles" +The matching algorithm. The choices are: +.ls 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 +\fIrefpoints\fR file, or by setting the linear transformation parameters +\fIxin\fR, \fIyin\fR, \fIxmag\fR, \fIymag\fR, \fIxrotation\fR, +\fIyrotation\fR, \fIxref\fR, and \fIyref\fR. 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. +.le +.ls 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. +.le +.le +.ls 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. +.le +.ls 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. \fIratio\fR should never +be set higher than 10.0 but may be set as low as 5.0. +.le +.ls nreject = 10 +The maximum number of rejection iterations for the "triangles" pattern +matching algorithm. +.le +.ls 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. +.le +.ls 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. +.le +.ls verbose = yes +Print messages about the progress of the task ? +.le +.ls icommands = "" +The image display cursor. +.le + +.ih +DESCRIPTION + +XYXYMATCH matches the x and y coordinates in the reference coordinate list +\fIreference\fR to the corresponding x and y coordinates in the input +coordinate list \fIinput\fR to within a user specified tolerance +\fItolerance\fR, and writes the matched coordinates to the output +file \fIoutput\fR. The output file is suitable for input to the +GEOMAP task which computes 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 \fIseparation\fR +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 +three ways. If \fIinteractive\fR 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 \fIrefpoints\fR 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. + +.nf +# 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 + +.fi + +The coordinates of the tie points can be typed in by hand if \fIrefpoints\fR +is "STDIN". If the refpoints file is undefined the parameters +\fIxin\fR, \fIxin\fR, \fIxmag\fR, \fIymag\fR, \fIxrotation\fR, \fIyrotation\fR, +\fIxref\fR, and \fIyref\fR 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. + +.nf + 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 +.fi + +The reference and input coordinates are read from columns \fIxrcolumn\fR, +\fIyrcolumn\fR in the reference, and \fIxcolumn\fR, and \fIycolumn\fR in the +input coordinate lists respectively. The input coordinates are transformed +using the computed linear transformation and stars closer together than +\fIseparation\fR pixels are removed from both lists. + +The coordinate lists are matched using the algorithm specified by +the \fImatching\fR +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 \fItolerance\fR. +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 constructs a list of triangles +using up to \fInmatch\fR 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 \fInmatch\fR 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 output file respectively, in a format +specified by the \fIxformat\fR and \fIyformat\fR parameters. +The respective line numbers in the original reference and input +coordinate files are written to columns 5 and 6 respectively. + +If \fIverbose\fR is yes, detailed messages about actions taken by the +task are written to the terminal as the task executes. + +.ih +ALGORITHMS + +The "triangles" algorithm uses a sophisticated pattern matching +technique which requires no tie point information from the user. +It is expensive computationally and hence is restricted to a maximum +of \fInmatch\fR 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 \fItolerance\fR or +with a ratio of the longest to shortest side greater than \fIratio\fR +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 +in the counter-clockwise sense. Those in the minority category +are eliminated. +The rejection step can be repeated up to \fInreject\fR 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 each 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 +\fItolerance\fR parameter will increase the ability to deal with distortions but +will also produce more false matches. + +.ih +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: + +.nf +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 +.fi + +.ih +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). + +.ih +EXAMPLES + +1. Match the coordinate list of an image to the coordinate list of a reference +image using the triangles 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. + +.nf + 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 +.fi + +2. Match the coordinate lists above using the tolerance matching algorithm +and the image display and cursor. + +.nf + 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 +.fi + +3. Repeat example 2 but run xyxymatch non-interactively by setting the +appropriate linear transformation parameters rather than marking stars +on the image display. + +.nf + 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 +.fi + +4. Repeat example 2 but run xyxymatch non-interactively +inputting the appropriate linear transformation via a list of tie points +rather than marking stars on the image display or creating a refpoints +file. + +.nf + 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 +.fi + +.ih +TIME REQUIREMENTS +.ih +BUGS +.ih +SEE ALSO +daophot.daofind,lintran,imlintran,geomap,register,geotran +.endhelp |