AlignTK - align

PURPOSE

align takes a set of pairwise maps relating a set of images, and then attempts to find maps positioning each image in absolute space that are consistent with the given set of maps.  For example, one may have a stack of 2-D section images forming a volume, and give align the pairwise maps between adjacent sections, and have it produce the maps that will position each section into 3-D space.  Or, one may have overlapping images of portions of a 2-D obect, and give align the pairwise maps of those images that overlap, and have it produce the maps that will position each image into 2-D space.  The ability to do either of these tasks depends on the input maps being consistent.  If that condition is not met, then align will only be able to produce a solution at lower resolution or not at all.

The align program is based on a multi-resolution relaxation algorithm, and represents each image as a grid of nodes, with springs between adjacent nodes attempting to maintain the original geometry of that image.  The pairwise maps given to the program are translated into spring between nodes in different images, which attempt to pull the images into registry.  When all maps have been translated, the program has a large spring network which is allowed to relax to obtain a solution that is a compromise between retaining the original image geometries and making the images match up closely with each other.

TYPICAL USAGE

align -image_list images.lst   \
        -images images/          \
        -masks image_masks/  \
        -map_list maps.lst        \
        -maps maps/               \
        -output aligned_maps/  \
        -schedule schedule.lst

COMMAND LINE ARGUMENTS

-absolute_maps directory/

If this option is specified, use the given maps as a guide to where each image should be positioned in absolute space.  If a map with the given image name is present in the specified directory, then a force will be applied to each node in the spring network to move toward the absolute position specified by the map.  The magnitude of this force is controlled by the kAbsolute value of the current relaxstion step, as specified in the schedule file.   If no map with the given image name is present in the specified directory, then no force will be applied to nodes of that image.  This option is useful for globally influencing the overall shape of the relaxed network, but care must be taken to apply these forces throughout the 3-D network and not just to a small number of images in the stack, e.g., the beginning and ending image.   Usually, if forces are applied to only a small number of images, these images will become "cusps", and intervening images in the stack will appear unnaturally stretched.

-constraints directory/

If this option is specifed, read a list of constraints for each image from the specified directory.  A constraint file constrains particular image points to be at a fixed position in absolute space, and has the format:

x_image y_image x_absolute y_absolute

...

where (x_image, y_image) are the pixel coordinates of a point in the image, and (x_absolute, y_absolute) are the coodinates in absolute space that this point should be pinned to.

Constraints are "stronger" than absolute maps, in that the constraints pin particular nodes in the spring network to an absolute position, whereas absolute maps only cause a force to be applied to a node to push it in the right direction.  Constraints can thus help the spring network to settle faster.   If constraints for an image are present and no initial map is explicitly provided (via the -initial_maps option), then the constraints will be used to compute an initial placement for the image, overriding any transformation present for that image in the image list file.

-fixed image_name

Consider the given image as fixed.   Its position will not be altered at all during the relaxation process.   It is possible to have multiple -fixed options when invoking the program.

-focus widthxheight+offset_x+offset_y,image_name

When outputting diagnostic grids, only show the specified rectangle (width, height, and offsets given in pixels relative to the specified image).

-fold_recovery number_of_retries

This option requests that the program try to recover if a fold develops in the spring network.  The specified value limits the number of retries that will happen before the program exits with an error.  During a fold recovery operation, the program attempts to pick the map region it believes to be most inconsistent, and removes the springs associated with that portion of the map from the spring network.  The spring network is backed up to state prior to fold developed and then the relaxation process continues.  This recovery technique works best if there are many redundant maps present, such as one might find in a two-dimensional mosaic of partially overlapping tiles.  It does not work very well with three-dimensional image stacks; folds there are best addressed by manual removal of map portions after inspecting the quality of the pairwise maps.

-grid_size widthxheight

Specifies the resolution in pixels to use for the diagnostic grids that are output.  Defaults to 1024x1024.

-image_list images.lst

Specifies the file that contains the list of names of the images to be aligned.  In its simplest form this file contains just a list of names, one per line.  However, each line in this file may contain additional information for each image, and conform to the following format (where brackets indicate optional elements):

image_name [ width height [ rotation scale tx ty [ model_name [ kFactor ] ] ] ]

We describe each of these components here:

image_name - an alphanumeric string (no spaces)

width - the image width in pixels  if known; if unknown, set this to -1 and it will be looked up in the image file; defaults to -1

height - the image height in pixels if known; if unknown, set this to -1 and it will be looked up in the image file; defaults to -1

rotation - the initial rotation to be applied to the image; this is in radians, positive being counter-clockwise; defaults to 0

scale - the initial scale factor to apply to the image; 2 means scale up by a factor of 2; defaults to 1

tx - the initial x translation to apply to the image; positive means move to the right; defaults to 0

ty - the initial y translation to apply to the image; positive means move down; defaults to 0

model_name - the deformation model to use for this image (see -models option for more info); defaults to an identity model, i.e., no deformation

kFactor - a factor to multiply all the intra-image spring constants by for this image;  this can be used to make some images stiffer (kFactor > 1) or more elastic (kFactor < 1) than other images; defaults to 1

-images directory/

Specifies the directory where the images are stored.  The image content is actually not used by align since all necessary information to do the alignment is stored in the map files; only the image headers are accessed in order to obtain the image sizes.

-incremental

If this option is given, output both the maps and the diagnostic grids after each step in the relaxation schedule.  This is useful to have at least a coarse alignment available in case folds during later steps in the schedule.

-initial_maps directory/

Specifies the directory where initial placement maps for each image are stored.  These maps override any initial transformation specified in the image list  file.

-interval number_of_iterations

Sets the number of iterations between successive output of the diagnostic grids.  Only has an effect if the -output_grid option is given.

-label

This option will place image name labels on the diagnostic grids.  Only has an effect if the -output_grid option is given.

-map_list maps.lst

Specifies the map list file to use for the alignment.  The map list file contains the names (one per line) of all maps relating one image to another.  The format of each line in this file is:

image_name0  image_name1  map_name  [ weight ]

These components are as follows:

image_name0 - the first image that the map refers to

image_name1 - the second image that the map refers to (the reference image)

map_name - the name given to the map.  This will be used to construct the filename in the maps directory.  Often the map_name is formed as some combination of the image names that it refers to.

weight - an optional weight factor to multiply all the inter-image spring constants by for springs generated from this map. This can be used to make some maps more important than others.  If omitted, this defaults to 1.

-maps directory/

Specifies the directory where the maps are stored.

-masks directory/

Specifies the directory where the image masks are stored.   It is necessary to have the align program use image masks if not all the pixels of the images contain valid image content.  See the section on image masks in the CONCEPTS page of AlignTK for more details.

-minimize_area

If this option is given, then rotate and translate the final output maps so that the image area is minimized.   For example, if the images were 1024x128 in size, the relaxation process might settle with the long edge being diagonal, and therefore produce maps that when applied to the original images would yield images ~800x800 in size.  This option would rotate and translate the maps so the output maps would yield images ~1024x128 in size.

-models directory/

Specifies the directory where distortion model maps are stored.   The distortion model maps represent the assumed actual physical shape of an image.   This is useful where there are camera, lens, or other optical distortions which can be modeled.  These models are then used to stretch the digital image into its actual physical shape in the spring model so that it matches up better with other adjacent and overlapping images.

-output directory/

Specifies the directory where output maps will be saved.

-output_fold_maps

If this option is given, then, if a fold is detected, output maps in the vicinity of the fold.  These can be used with the inspect program to manually fix the incorrect map(s).  The maps will be created in the directory named by the -output_grid option.

-output_grid directory/

Specifies the directory in which to write the diagnostic grid files.

-output_springs directory/

If this option is present, then diagnostic spring images will be output into the specified directory.

-schedule schedule.lst

Specifies the schedule of relaxation steps to be performed on the spring network.  The schedule determines at what resolution level the spring network is constructed and relaxed, the minimum number of iterations for that step, and the criteria for step termination.  The schedule file consists of a sequence of lines (one line per step) with the following format:

level kIntra kInter [ kAbsolute [ min_iterations [ threshold [ step_size [ clamp_x [ clamp_y ] ] ] ] ] ]

These components are as follows:

level - the resolution level at which to construct the spring network and perform the relaxation; this is a log-scale with 0 being one node in the spring network every 1 pixels, 4 being one node every 16 pixels, 8 being one node every 256 pixels, etc.  Typically, these resolution levels will be in the range 6-14, with higher values for earlier steps, and lower values for later steps.

kIntra - the spring constant to use for intra-image springs, i.e., those springs which tend to preserve image geometry and act to oppose image distortion.  Typically, values will start higher, around 10. and decrease in later steps.   What is most important is the ratio between kIntra and kInter.

kInter - the spring constant to use for inter-image springs, i.e., those springs which tend to pull adjacent images into alignment.  Typically, values will start lower, around 0.1, and increase in later steps.  What is most important is the ratio between kIntra and kInter.

kAbsolute - the spring constant to use for absolute positioning springs, i.e., those springs which tend to pull each image toward an absolute position in space.  This will typically be 0, except in the case where the -absolute_maps option is given, when it typically be in the range 0.1-1.  The default value is 0.

min_iterations - the minimum number of relaxation iterations for this step; defaults to 2000.

threshold - this value determines when the spring network is considered to have settled for this particular step, and it is time to proceed to the next step.  The value is in parts-per-million per iteration, so if the value is 1.0, then the relaxation step will be considered finished when the energy of the spring network changes on average by less than one part-per-million per relaxation iteration.  This energy is averaged over 512 iterations so that the termination criterion is less sensitive to noise in the spring system when it is being run close to instability.  The default value for the threshold is 1.0.

step_size - this determines how fast to move the nodes in the spring network in response to spring forces applied to them.  If it is too small, the relaxation process will take much computer time; it it is too large, the network will become unstable and "blow up" with positions diverging toward infinity.   Reasonable values for this depend on the particular spring network, but oftern are in the 0.1 to 0.3 range.  However, it is usually better to let this value be set dynamically by giving a value of 0.  When the step size is determined dynamically, the total energy of the spring network is monitored as the network relaxes.  The step size is gradually increased until the energy increases (which indicates the onset of instability) and then backed off by a factor of 2.  The net effect is to keep the step_size nearly as large as possible for the given network, and this speeds up simulation time.  The default value for this parameter is 0 (to request that it be set dynamically).

clamp_x - a binary value (0 or 1), this parameter, if 1, clamps all of the x positions of the nodes.  The network is still free to settle in the y dimension.  Restricting the node movement to a signel dimension can sometimes help to get certain networks with with poor initial maps to settle without folding.  This option should not be used where large rotations are required.  The default value is 0.

clamp_y - a binary value (0 or 1), this parameter, if 1, clamps all of the y positions of the nodes.  The network is still free to settle in the x dimension (see clamp_x for additional info).  The default value is 0.

AlignTK -- EXAMPLES

PAIRWISE REGISTRATION OF TWO IMAGES

find_rst

register

apply_map

ALIGNMENT OF SMALL IMAGE STACK

mkdir -p cmaps
find_rst -pairs pairs.lst -tif -input images/ -output cmaps/ -max_res 1024 -scale 1.0 -tx -50-50 -ty -50-50 -summary cmaps/summary.out

mkdir -p maps
register -pairs pairs.lst -input images/ -tif -output maps/ -distortion 2.0 -output_level 6 -depth 6 -quality 0.5 -summary maps/summary.out -input_map cmaps/

mkdir -p amaps
mkdir -p grids
align -images images/ -image_list images.lst -map_list pairs.lst -maps maps/ -output amaps/ -schedule schedule.lst -incremental -output_grid grids/ -grid_size 1800x1400 -fixed z08

mkdir -p aligned
apply_map -image_list images.lst -images images/ -maps amaps/ -output aligned/ -memory 1000

ALIGNMENT OF LARGE IMAGE STACK

<pending>

ALIGNMENT OF PARTIAL IMAGES INTO COMPOSITE IMAGE

<pending>

ALIGNMENT OF STACKS OF COMPOSITE IMAGES

<pending>

AlignTK -- TOOLS

ALIGN -- takes a set of relative maps relating images, and uses a relaxation method to produce a set of absolute maps that position those images in space.

APPLY_MAP --applies a map to an image or a set of maps to a set of images to produce one or more output images.

BEST_AFFINE -- finds the affine map that best approximates the given arbitrary map.

BEST_RIGID -- find the rigid map that best approximates the given arbitrary map.

CLEAN_MAPS  -- allows one to remove portions of maps that are untrustworthy or inconsistent with other maps

COMBINE_MASKS  -- logically combines two masks into one.

COMPOSE_MAPS  -- takes 2 maps and composes their effects into a single output map.

EXTRAPOLATE_MAP -- extrapolates a given map to a map covering a larger area.

FIND_RST -- finds the rotation, scale, and translation that best registers one image to another.

GEN_IMAPS -- generates a set of intensity maps for a set of overlapping images.

GEN_MASK -- generates a mask from an image according to various rules

INSPECTOR -- allows one to inspect images and maps, and to add correspondence points to guide the registration of difficult image pairs

INVERT_MAP  -- takes an input map and outputs its inverse.

MERGE_IMAGES -- combines two aligned images into one.

ORTHO -- generates orthogonally-oriented image stacks from a 3-D volume.

REDUCE -- reduces the resolution of an image.

REDUCE_MASK -- reduces the resolution of a mask.

REGISTER -- finds the best map that registers one image to another image.

TRANSFORM_IMAGES -- transforms a set of images according to the given rotation, scale, and translation operators.