xfsimplex(1)                                                      xfsimplex(1)



NAME
       xfsimplex - Searches for best transformation between two images

SYNOPSIS
       xfsimplex  [options]  input_file_a  input_file_b  output_file

DESCRIPTION
       This program searches for the best general linear transform between a
       pair of images by varying either the six formal parameters of the
       transform, the six "semi-natural" parameters underlying such a trans-
       form, or restricted subsets of those semi-natural parameters.

       These semi-natural parameters are, in the order in which the program
       will consider them:
          Delta X
          Delta Y
          Global rotation (average rotation of X & Y axes)
          Global magnification (average stretch of X & Y axes)
          Difference between stretch along Y- & X-axis
          Difference between rotation of Y- & X-axis With the -variables
       option, one enters either zero to search for formal parameters, or a
       number specifying how many of the natural parameters are to be varied.
       If one selects 2, only Delta X and Delta Y will be varied; if one
       selects 4, global rotation and magnification will be varied also. At
       the end, the program outputs a six-parameter transformation (the 2x2 A
       matrix and DX and DY) in the standard format.

       Because the search method used by this program works iteratively from a
       given starting point, it is unlikely to find the proper alignment if it
       requires a large displacement.  To overcome this problem, the program
       can be given an initial transformation to work from. This allows a
       large displacement to be found by cross-correlation and passed to this
       program.

       To find the best fit between images, the search can optimize either a
       simple point-by-point difference between the images, the cross-correla-
       tion coefficient, or a measure of the distance between points of simi-
       lar intensities in the images.  The resulting transformation is applied
       to the second image to align it to the first.

       The search uses a so-called simplex minimization routine which starts
       searching with an initial step size and refines the step size near a
       minimum.  It terminates the minimization when either 1) the most recent
       points under consideration gave difference measures all within a cer-
       tain fractional tolerance of the point with the minimum measure; or 2)
       the most recent points had transformation parameters all within a cer-
       tain tolerance of the point with the minimum measure. The latter toler-
       ances are expressed as fractions of the following basic step sizes: 1
       for delta X and Y; 0.025 for the 4 parameters of the transformation
       matrix, if using formal parameters; or 2 degrees for global rotation
       and differences between X and Y rotations, and 0.025 for global magni-
       fication and difference between X and Y magnifications, if using semi-
       natural parameters.

       By default, the program will perform an initial minimization with a
       coarse tolerance for termination, then it will restart the minimization
       at the best point, and terminate with a finer tolerance. If the overall
       alignment method involves two stages, coarse and fine, then you should
       omit the initial minimization by specifying tolerances of zero for it.

       At the end of the search, the program outputs the number of iterations,
       the minimum difference/distance or maximum correlation value found, and
       the transformation parameters.  If semi-natural parameters were
       searched for, first those parameters are output, then the formal param-
       eter matrix is output.  The difference measure is normalized to be the
       mean difference per pixel as a multiple of the standard deviation of
       the first image.  If correlation coefficients are used, then the mea-
       sure of difference being minimized is one minus the correlation coeffi-
       cient.  The distance measure is expressed as the mean distance per com-
       parison point.

OPTIONS
       Xfsimplex uses the PIP package for input (see the manual page for
       pip) and can still take sequential input interactively, to maintain
       compatibility with old command scripts.  The following options can be
       specified either as command line arguments (with the -) or one per line
       in a command file or parameter file (without the -).  Options can be
       abbreviated to unique letters; the currently valid abbreviations for
       short names are shown in parentheses.


       -aimage (-ai) OR -AImageFile   File name
              Input image file with reference image to be aligned to.  If this
              option is not entered, the first non-option argument will be
              used for this input file.

       -bimage (-bim) OR -BImageFile       File name
              Name of image file with image to align to reference.  If this
              option is not entered, the second non-option argument will be
              used for this input file.

       -output (-o) OR -OutputFile    File name
              Output file for transformation.  If this option is not entered,
              the third non-option argument will be used for this output file.

       -initial (-i) OR -InitialTransformFile   File name
              Input file with transformation to start search with.  The final
              reported transformation will include the initial one rather than
              being incremental to it.

       -useline (-use) OR -UseTransformLine     Integer
              Line number of initial transform in file, numbered from 0
              (default 0)

       -sections (-se) OR -SectionsToUse   Two integers
              Sections to use from the first and second file (default 0,0)

       -variables (-v) OR -VariablesToSearch    Integer
              Number of semi-natural variables to search, or 0 to search for
              formal parameters.  See above for the meaning and order of the
              variables selected by this option.

       -limits (-lim) OR -LimitsOnSearch   Multiple floats
              Limits for each of the variables being searched.  Each number
              entered specifies the maximum amount that the respective vari-
              able can change from its initial value.  Enter a 0 to avoid lim-
              iting a parameter.  If the search is being done on formal param-
              eters, then only the first two (shift in X and Y) can be lim-
              ited, so only 1 or 2 values can be entered.  If the search is on
              semi-natural parameters, then you can enter more or fewer values
              than the number of variables being searched.  Extra values are
              ignored, missing values are assumed to be zero.

       -edge (-e) OR -EdgeToIgnore    Floating point
              Fraction or number of pixels to ignore on edges of image.  Enter
              a value less than 0.5 for a fraction, or a value greater than 1
              for a number of pixels.  The default is 0.05.

       -xminmax (-x) OR -XMinAndMax   Two integers
              Starting and ending coordinates to analyze in X (numbered from
              1).  This entry overrides the X coordinates implied by the -edge
              entry or default.

       -yminmax (-y) OR -YMinAndMax   Two integers
              Starting and ending coordinates to analyze in Y (numbered from
              1).  This entry overrides the Y coordinates implied by the -edge
              entry or default.

       -binning (-bin) OR -BinningToApply       Integer
              Binning to apply to the images.  The default is 2.

       -antialias (-an) OR -AntialiasFilter     Integer
              Type of antialiasing filter to use for image reduction instead
              of binning.  Antialiasing becomes important when the images are
              highly reduced in size.  Ordinary binning reduces aliasing, but
              not as much as these filters do.  This option makes any filter-
              ing be applied after the image reduction (thus it implies the
              -after option).  As in Newstack, the available types here
              are:
                  2: Blackman - fast but not as good at antialiasing as slower
                                filters
                  3: Triangle - fast but smooths more than Blackman
                  4: Mitchell - good at antialiasing, smooths a bit
                  5: Lanczos 2 lobes - good at antialiasing, less smoothing
                                than Mitchell
                  6: Lanczos 3 lobes - slower, even less smoothing but more
                                risk of ringing
                 -1: Use the default filter, currently Lanczos 2

       -sig1 OR -FilterSigma1    Floating point
              Sigma value to filter low frequencies in both images with a
              curve that is an inverted Gaussian.  This filter is 0 at 0 fre-
              quency and decays up to 1 with the given sigma value.  However,
              if a negative value of radius1 is entered, this filter will be
              zero from 0 to |radius1| then decay up to 1.

       -rad1 OR -FilterRadius1   Floating point
              Low spatial frequencies in both images will be attenuated by a
              Gaussian curve that is 1 at this cutoff radius and falls off
              below this radius with a standard deviation specified by Filter-
              Sigma2.  Spatial frequency units range from 0 to 0.5.  Use Fil-
              terSigma1 instead of this entry for more predictable attenuation
              of low frequencies.

       -rad2 OR -FilterRadius2   Floating point
              High spatial frequencies in both images will be attenuated by a
              Gaussian curve that is 1 at this cutoff radius and falls off
              above this radius with a standard deviation specified by Filter-
              Sigma2.

       -sig2 OR -FilterSigma2    Floating point
              Sigma value for the Gaussian rolloff below and above the cutoff
              frequencies specified by FilterRadius1 and FilterRadius2

       -after (-af) OR -FilterAfterBinning
              Apply the Fourier filter after binning data.  This will be much
              faster, but it may introduce aliased noise from the higher fre-
              quencies in the original data unless antialiased reduction is
              used.  The radius and sigma values represent frequencies in the
              binned image, not the original image.  If antialias reduction is
              not used, the default is to filter before binning, in which case
              the high frequencies can be removed before binning; if
              antialiasing is used, the filtering always happens after reduc-
              tion and this option is redundant.

       -sobel (-so) OR -SobelFilter
              Apply edge-detecting Sobel filter to both images.  This filter
              will be applied after binning and filtering if any.

       -float (-fl) OR -FloatOption   Integer
              0 to float images to have the same range, 1 to float them to
              have the same mean and standard deviation, or -1 to leave inten-
              sities alone.  Only pixels within the range being analyzed will
              be considered when determining the scaling.  The default is 1.

       -ccc (-cc) OR -CorrelationCoefficient
              Compute the standard cross-correlation coefficient instead of
              difference between images.  The difference measure that is mini-
              mized will be 1 minus the CCC, but the CCC itself is printed in
              the trace and final output.  It takes < 5% more time to compute
              the CCC.

       -local (-lo) OR -LocalPatchSize     Integer
              Size of square subareas (patches) within which to compute a mea-
              sure of image difference, in pixels before binning, if any.  The
              image will be divided into patches of this size and the measure
              will be computed separately within each patch; then a weighted
              average will be formed, weighted by the number of pixels actu-
              ally available for comparison within each patch.  If image dif-
              ference is being computed, the measure will be the standard
              deviation of the difference; otherwise the correlation coeffi-
              cient is computed.  Patches with less than half the full number
              of pixels will be pooled with the nearest patches containing
              enough pixels.  This option should prevent the need for low fre-
              quency filtering, which would increase execution time by roughly
              10%.  Patch sizes on the order of 1/20 to 1/10 of the image size
              should be effective.

       -linear (-lin) OR -LinearInterpolation
              Use linear interpolation instead of nearest pixel interpolation
              when computing image differences or correlation coefficients.

       -distance (-di) OR -DistanceMeasure
              Use distance instead of difference or correlation measure

       -near (-n) OR -NearestDistance      Integer
              Distance to search to eliminate redundant points, or 0 not to
              search, when using the distance measure.  The default is 0 for #
              of pixels < 240*180, 1 if # of pixels is between 240*180 and
              480*360, 2 if # of pixels > 480*360.

       -radius (-radi) OR -RadiusToSearch       Floating point
              Radius to search for matching pixels when using the distance
              measure.  The default is 4 if binning by 2, or 5 if not.

       -density (-de) OR -DensityDifference     Floating point
              Maximum density difference that constitutes a match when using
              the distance measure, as a fraction of the density range.  The
              default is 0.05.

       -percent (-pe) OR -PercentileRanges      Multiple floats
              Lower and upper limits of percentile ranges to match.  The
              default is to have two ranges, i.e., 0,8,92,100, for images less
              than 320*240, scaling down to 5% ranges as image size increases
              from 320*240 to 640*480.

       -coarse (-co) OR -CoarseTolerances       Two floats
              Fractional tolerances in difference and parameters for the ini-
              tial search.  Enter 0,0 to skip the initial search.  The default
              values are 0.005 and 0.2 of the basic step size.

       -final (-fi) OR -FinalTolerances    Two floats
              Fractional tolerances in difference and parameters for the final
              or only search.  The default values are 0.0005 and 0.02 of the
              basic step size, or 0.001 and 0.04 for images no bigger than 128
              by 128.

       -step (-st) OR -StepSizeFactor      Floating point
              Factor to multiply basic step size by to get initial step size.
              The default is 2.

       -trace (-t) OR -TraceOutput    Integer
              1 for output at each step, 2 for output at new minima

       -param (-pa) OR -ParameterFile      Parameter file
              Read parameter entries as keyword-value pairs from a parameter
              file.

       -help (-h) OR -usage
              Print help output

       -StandardInput
              Read parameter entries from standard input.


INTERACTIVE INPUT
       A subset of entries can still be made by running the program interac-
       tively.  All of the parameters have defaults which may be selected with
       , or / (the values in [] below and contained in [] in the prompts)

       ***lines 1-4
        first image file
        second image file
        data file into which to place the best fitting transformation
        name of file file with starting transformation, or Return if none

       *** line 5 (6 values):
        Fractional tolerances in the difference/distance measure and in the
          transformation parameter values, to allow termination of final or
          only minimization [.0005 and 0.02, or .001 and 0.04 for
          images no bigger than 128 by 128]
        Fractional tolerances in the difference/distance measure and in the
          transformation parameter values, to allow termination of initial
          minimization [.005 and 0.2].  Enter 0,0 to skip initial search.
        Factor to apply to basic step sizes to get initial step sizes [2]
        1 for trial-by-trial output, 2 for output of trials that yield new
          minima only.

       ***line 6
        0 for search on formal parameters, or # of natural parameters to
          vary [0]

       ***lines 7-10
        Fraction of images to ignore at edges [0.05]; or number of pixels
          if the number entered is 1 or greater
        float images to have same range (0) or same mean and S.D. (1), or
          do not float images (-1) [1]
        binning factor for reducing images in x and y [2]
        use difference (0) or distance (1) measure [0]

       If difference measure is chosen, one more line of input:

       ***line 11
        1 to use bilinear interpolation during the search [0]

       If distance measure is chosen, 5 more lines of input:

       *** lines 11-14
        distance to search to eliminate redundant points with similar
          densities from comparison [default depends on image size after
          reduction, if any: 0 for # of pixels < 240*180, 1 if # of pixels
          between 240*180 and 480*360, 2 if # of pixels > 480*360
        distance to search for matching densities [4 if reduce by 2, 5 if
          not]
        maximum density difference constituting a match [0.05]
        Number of ranges of densities to make comparisons with [2]

       *** line 15
        lower and upper PERCENTILES for these ranges.  The default is 0,8,92,
          100 for small images.  This means that the darkest 8% and brightest
          8% of pixels will be used for comparison (minus ones eliminated
          because of redundancy).  The default depends on image size after
          reduction, if any; the range is scaled from 8% down to 5% as image
          size increases from 320*240 to 640*480

       The distance measure has been little used and the defaults for it are
       based on limited experimentation. These defaults are set in an attempt
       to limit the number of "points for comparison" to several thousand.  If
       there are more than about "5000 points for comparison", you should
       depart from the defaults in order to reduce this number.

HISTORY
       Written by David Mastronarde, 4/5/91 (adapted from XFSEARCH)
       7/1/08: Converted to PIP, added search limits, filtering, CCC

BUGS
       Email bug reports to mast at colorado dot edu.



BL3DEMC                              4.7.3                        xfsimplex(1)