NAME

     cnmregister - Register filtered gray scale images

SYNOPSIS

     cnmregister [-compress C] [-n max_num_loc] [-s num_seeds]
                 [-win width height] [-max_dist max_distance]
                 [-max_Hratio max_Hratio] [-max_angle max_angle]
                 [-xml] [-help] {file1} {file2} [file2...]

DESCRIPTION

     The program cnmregister registers two or more filtered
     images, outputting a set of registration landmarks. Input is
     two or more 8 bit tiff files. Background pixels on each
     image must be set to white (255). All other pixels are
     assumed to be foreground.

     The program outputs a set of registration landmarks on each
     of the images in cnm or xml format. Corresponding landmarks
     mark corresponding points on the images.

OPTIONS

     -compress C
          Compress image width and height by a factor of C for
          faster processing. Note that total image compression is
          CxC. Output coordinates of registration landmarks are
          uncompressed.

     -n max_num_loc
          Maximum number of registration landmarks.

     -s num_seeds
          Number of seed locations used in initial search for
          corresponding locations. Initial search for
          corresponding locations is computationally intensive.
          Increasing the number of seed locations can greatly
          increase the running time.

     -win width height
          Matching window width and height in uncompressed
          pixels. Given two locations in two different images,
          windows are centered around each location and compared
          to determine if the locations match.

     -max_dist max_distance
          Maximum distance between the image coordinates of two
          matching locations in two different images. This is not
          a guarantee on the maximum distance but is used to
          guide the search for matching locations and reduce
          cnmregister's running time.

     -max_Hratio max_Hratio
          Maximum ratio between the calculated and the expected
          partial Hausdorff distance. Ratios less than this
          maximum signify matching locations. Lower values for
          -max_Hratio give more reliable matching locations but
          produce fewer matches. Values must be between 0 and 1.

     -max_angle max_angle
          Maximum angular distortion in degrees. For any two
          pairs of corresponding landmarks (p1,q1) and (p2,q2)
          where p1 and p2 are in one image and q1 and q2 are in
          another, the angle between vector (p1-p2) and vector
          (q1-q2) is at most than max_angle.

     -xml Output the landmarks in xml format to file
          landmark.xml.

     -help
          Print a brief help message.

ALGORITHM

     The registration algorithm is based on the pixel matching
     algorithm described by Huttenlocher et. al.  in [HK93].
     Huttenlocher et. al. define the k'th partial Hausdorff
     distance as a measure between two sets of pixels and give an
     algorithm for quickly computing this distance.  The k'th
     partial Hausdorff distance is described in the next section.

     The algorithm chooses an evenly distributed set of locations
     on the first image, known as the registration image.
     Locations which are at the "center" of foreground regions
     are preferred.  The algorithm also chooses an evenly
     distributed subset of locations on the registration image,
     called the seed locations.  Various searching techniques are
     used to find good matches between the chosen locations on
     the registration image and locations on the other image.
     Initially, more exhaustive and computationally intensive
     searches are done to find matches for the seed set.  Once a
     significant portion of the seed set is matched, the matching
     seed set locations are used to guide the search for matches
     for the rest of the chosen locations.

     To measure the correspondence between two locations in two
     different images, the registration algorithm places a window
     around each location, overlays the two windows and measures
     the k'th partial Hausdorff distance between the foreground
     pixels in the two windows.  A small value indicates a good
     match.

     The appropriate threshold to indicate a good match varies
     depending upon the images or even the portion of images
     being compared.  Instead of requiring the user to specify
     this threshold, the algorithm computes the expected k'th
     partial Hausdorff distance for a (uniform) random
     distribution of the foreground pixels in the two windows.
     If the ratio of the computed value and this expected value
     is less than a user specified threshold ratio, then the
     locations are matched.  While the user still needs to
     specify a threshold ratio, this ratio is much less dependent
     on the images being compared.

     Some location matches are inevitably erroneous, despite
     having small difference measurements.  To eliminate these,
     the algorithm measures the angular distortion between pairs
     of matching locations.  For any two pairs of matching
     locations (p1,q1) and (p2,q2) where p1 and p2 are in one
     image and q1 and q2 are in another, measure the angle
     between vector (p1-p2) and vector (q1-q2).  If this angle is
     greater than some user specified threshold, then one of
     these matches is erroneous.  By comparing all pairs, the
     algorithm identifies which matches are erroneous and
     eliminates them from consideration.

     Note that the procedure to eliminate angular distortion
     implicitly assumes that the images have approximately the
     same orientation.

     [HK93] D.P. Huttenlocher, G.A. Huttenlocher, and W.J.
     Rucklidge. Comparing images using the Hausdorff distance.
     IEEE Trans. on Pattern Anal. and Mach. Intell. 15. 850-863.
     1993.

PARTIAL HAUSDORFF DISTANCE

     Given a pixel p and a set of pixels B, the distance from p
     to B is the distance from p to the closest pixel in B.  The
     directed Hausdorff distance from A to B is the maximum
     distance from any point p in A to B.  The Hausdorff distance
     between A and B is the maximum of the directed Hausdorff
     distance from A to B and the directed Hausdorff distance
     from B to A.

     The directed k'th partial Hausdorff distance is the k'th
     ranked distance from any point p in A to B where distances
     are ranked in increasing order.  When k is equals the size
     of A, this is simply the directed Hausdorff distance.  The
     k'th partial Hausdorff distance is the maximum of the
     directed k'th partial Hausdorff distance from A to B and the
     directed k'th partial Hausdorff distance from B to A.

     To quickly compute the k'th partial Hausdorff distance, a
     distance matrix containing the (L1) distance to the nearest
     foreground pixel is created for each image.  Locating the
     foreground pixels in one image in the distance matrix of the
     other image gives the distance from each pixel to the
     foreground pixels of the other image.  All these distances
     over all foreground pixels are stored in a histogram, and
     the k'th ranked distance is retrieved from that histogram.

AUTHOR

     Rephael Wenger.