Fast hierarchical noniterative registration algorithm

This note describes a fast algorithm for registering pairs of images from a time sequence of images. The algorithm solves a linear regression problem based on a linearization of the image matching equation, to obtain the regi stration coefficients. The problem of ill-posedness caused by differentiati on of a noisy image sampled on a finite lattice is solved by means of a pat ch algorithm. The algorithm uses an integrated form of the linearized displ acement equation. Registration is simultaneously carried out on a set of co mputationally fast prefilters providing three downsampled bandpass images f or each input image. The filters are multilevel and permit an efficient and versatile hierarchical registration procedure. Downsampling the images bef ore registration significantly reduces computation time. As a final step, r egistration is repeated using full-size images. Results for two-dimensional (2D) images using a six-parameter affine registration transformation and a 12-parameter second-order polynomial transformation indicate the method is 2.5 times faster (12.7 s/256 x 256 image pair) than a previous iterative m ethod (28 s/pair) and, like the previous method, is robust to noise. The me thod may easily be generalized to 3D image registration and more general tr ansformations, and is well-suited to parallel processing. (C) 1999 John Wil ey & Sons, Inc.