Method and apparatus for relating and combining multiple images of the same scene or object(s)

• US 5,706,416 A
• Filed: 11/13/1995
• Issued: 01/06/1998
• Est. Priority Date: 11/13/1995
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Picard, Rosalind W., Mann, Steve
• Primary Examiner(s): Nguyen, Phu K.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/558,012
• Time in Patent Office: 785 Days
• Field of Search: 395/127, 395/121, 395/130, 395/135, 395/136, 395/133
• US Class Current: 345/427
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration

Abstract

Digitally encoded images having common subject matter are spatially related to one another and combined utilizing a projective coordinate transformation, the parameters of which are estimated featurelessly. For a given input image frame, the universe of possible changes in each image point consistent with the projective coordinate transformation is defined and used to find the projective-transformation parameters which, when applied to the input image, make it look most like a target image. The projective model correctly relates images of common (static) subject matter taken by a single camera at a fixed location, free to rotate about its center of projection (e.g., free to rotate about its optical axis, and to pan and tilt) and having a lens free to zoom; and planar scenes recorded by a camera free to move arbitrarily (including translation or other movements of the center of projection itself).

Claims

1. A method of aligning a plurality of images having common subject matter, each image being encoded as an ordered set of pixels each having at least one associated pixel parameter, the method comprising:

a. featurelessly approximating parameters of a projective coordinate transformation that spatially relates, in first and second images, pixels corresponding to common subject matter therebetween;

b. applying the parameters to the first image to thereby transform it into a processed image, the common subject matter encoded by pixels in the processed image being substantially spatially consistent with the common subject matter encoded by pixels in the second image; and

c. aligning the images by combining the pixels corresponding to the common subject matter.

2. The method of claim 1 wherein the parameters are approximated according to steps comprising:

a. for each of a plurality of pixels in the first image, defining a model velocity u_m, v_m that quantifies, in each of two orthogonal directions, allowable deviations in a pixel parameter according to the projective coordinate transformation;

b. for each of the plurality of first-image pixels, defining a flow velocity u_f, v_f that expresses, in each of two orthogonal directions, the actual deviation in the pixel parameter between the first-image pixel and a plurality of pixels in the second image; and

c. locating, for each of the plurality of first-image pixels, a corresponding second image pixel such that the squared sum of differences between u_m, v_m and u_f, v_f for all of the plurality of first-image pixels and all corresponding second-image pixels is minimized.

3. The method of claim 1 wherein the parameters are approximated according to steps comprising:

a. generating an optical flow field comprising flow velocities relating pixels in the first image to corresponding pixels in the second image; and

b. regressively approximating, from the flow field, parameters of a projective coordinate transformation consistent with the flow field.

4. The method of claim 2 wherein the squared sum of differences is given by ##EQU11##

5. The method of claim 2 wherein the plurality of pixels in the first image are the four corners of a pixel bounding box.

6. The method of claim 1 further comprising the steps of:

d. sampling each of the first and second images at a first sampling frequency to produce initial sets of pixels encoding the images at an initial resolution;

e. performing step (a) on the pixels at the initial resolution to identify subject matter common to the first and second images;

f. sampling each of the first and second images at a second sampling frequency to produce subsequent sets of pixels encoding the images at a higher resolution; and

g. performing steps (a) and (b) on the pixels.

7. The method of claim 1 further comprising the steps of:

d. following transformation of the first image into the processed image, repeating at least once steps (a) and (b) on the processed image to transform the processed image into a reprocessed image; and

e. deriving a new set of transformation parameters based on transformation of the first image into the processed image and transformation of the processed image into the reprocessed image.

8. The method of claim 7 further comprising repeating steps (d) and (e) on different versions of the first and second images, each version encoding a different resolution level.

9. The method of claim 1 wherein the second image is a zoomed-in version of a portion of the first image, the pixels of the first image being upsampled and combined with the pixels of the second image by a process selected from (i) last to arrive, (ii) mean, (iii) median, (iv) mode and (v) trimmed mean.

10. A method of aligning a plurality of images having common subject matter, each image being encoded as an ordered set of pixels each having at least one associated pixel parameter, the method comprising:

a. analyzing first and second images to identify pixels corresponding to common subject matter therebetween and spatially related by a first projective coordinate transformation;

b. approximating the first projective coordinate transformation;

c. projectively transforming the first image using the approximate projective coordinate transformation to produce an intermediate image;

d. analyzing the intermediate and second images to identify pixels corresponding to common subject matter therebetween and spatially related by a second projective coordinate transformation;

e. approximating the second projective coordinate transformation;

f. accumulating the approximate projective coordinate transformations into a composite transformation relating the first image to the second image;

g. applying the composite transformation to the first image to thereby transform it into a processed image, the common subject matter encoded by pixels in the processed image being substantially spatially consistent with the common subject matter encoded by pixels in the second image; and

h. aligning the images by combining the pixels corresponding to the common subject matter.

11. Apparatus for aligning first and second images having common subject matter comprising:

a. first and second computer memories for storing each image as an ordered set of pixels each having at least one associated pixel parameter;

b. analysis means for featurelessly approximating parameters of a projective coordinate transformation that spatially relates pixels corresponding to common subject matter of the first and second images; and

c. image-processing means for (i) applying the parameters to the contents of the first computer memory to thereby transform them into a processed image, the common subject matter encoded by pixels in the processed image being substantially spatially consistent with the common subject matter encoded by pixels in the second computer memory, and (ii) aligning the images by combining the pixels corresponding to the common subject matter.

12. The apparatus of claim 11 wherein the analysis module is configured to approximate the parameters by:

a. for each of a plurality of pixels in the first computer memory, defining a model velocity u_m, v_m that quantifies, in each of two orthogonal directions, allowable deviations in a pixel parameter according to the projective coordinate transformation;

b. for each of the plurality of pixels in the first computer memory, defining a flow velocity u_f, v_f that expresses, in each of two orthogonal directions, the actual deviation in the pixel parameter between the pixel in the first computer memory and a plurality of pixels in the second computer memory; and

c. locating, for each of the plurality of pixels in the first computer memory, a corresponding pixel in the second computer memory such that the squared sum of differences between u_m, v_m and u_f, v_f for all of the plurality of pixels in the first computer memory and all corresponding pixels in the second computer memory is minimized.

13. The apparatus of claim 11 wherein the analysis module is configured to approximate the parameters by:

a. generating an optical flow field comprising flow velocities relating pixels in the first computer memory to corresponding pixels in the second computer memory; and

b. regressively approximating, from the flow field, parameters of a projective coordinate transformation consistent with the flow field.

14. A visual thesaurus comprising:

a. a database of images each stored as an ordered set of pixels, each pixel having at least one associated pixel parameter;

b. first and second computer memories for storing a reference image and a database image;

c. analysis means for sequentially retrieving images from the database and storing each retrieved image in the second computer memory, the analysis means operating, for each retrieved image, on the first and second computer memories to detect the existence of common subject matter between the reference image and the database image by featurelessly determining whether pixels from the first computer memory can be related to pixels of the second computer memory according to a projective coordinate transformation, and if not, rejecting the database image as unrelated to the reference image; and

d. an interface for displaying database images related to the reference image.