Spline-based image registration

• US 5,611,000 A
• Filed: 01/16/1996
• Issued: 03/11/1997
• Est. Priority Date: 02/22/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Szeliski, Richard S., Coughlan, James M.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/586,357
• Time in Patent Office: 420 Days
• Field of Search: 382/294, 382/295, 382/151, 382/293, 348/263, 348/700
• US Class Current: 382/294
• CPC Class Codes: G06T 3/14 Transformations for image registration, e.g. adjusting or mapping for alignment of images
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/269 using gradient-based methods
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

The light intensity values of a first and second image are stored in a memory as pixels. A transformation from the second image to a derived image is perforated by a spline function in cooperation with a spline control grid. The spline control grid has a plurality of control vertices at predetermined locations with respect to the pixels of the second image. The transformation adjusts the light intensity values proportional to the distance between the control vertices and the pixels of the second image. The first image is compared with the derived image. The difference between the first image and the derived image is determined. The control vertices of the control grid are iteratively displaced until the difference between the first and derived image is less than a desired amount. The final coordinates of the control vertices parametrize the motion field of the first and second image.

Claims

1. A method for extracting motion information from a sequence of images, comprising the steps of:

storing a first image in a memory as a first set of light intensity values;

storing a second image in said memory as a second set of light intensity values;

storing a spline control grid in said memory as a dam structure, said spline control grid having a plurality of control vertices at predetermined locations with respect to said second image;

transforming said second image to a derived image by a spline function in cooperation with the spline control grid, said spline control grid being a data structure stored said memory, the locations of said control vertices parametrizing said spline function;

comparing said first image to said derived image;

displacing, in response to there being a difference between said first image and said derived image, the locations of said control vertices to minimize the difference between said first and derived images; and

repeating said transforming, comparing, and displacing steps until the difference between said first image and said second image is less than a desired amount, the locations of control vertices stored in said memory characterizing the motion information of said first image and said second image.

2. The method as in claim 1 further including

adjusting said second set of light intensity values proportional to a distance between the locations of said control vertices and the locations of said light intensity values.

3. The method as in claim 1 wherein said transforming step uses a bi-linear spline function.

4. The method as in claim 1 wherein the locations of said control vertices are a regular sub-sampling of the locations of said second set of light intensity values.

6. The method as in claim 1 wherein said second set of light intensity values are stored as a multi-level pixel pyramid having a plurality of image levels, said plurality of image levels arranged in a coarse-to-fine order.

7. The method as in claim 6 wherein said transforming, comparing, and displacing steps are first performed at a coarser image level of said multi-level pixel pyramid to extract coarse motion information, and where the coarse motion information is used to initiate said transforming, comparing, and displacing steps at a finer level of said multi-level pixel pyramid.

8. The method as in claim 1 wherein the motion of said first image relative to the motion of said second image is a planar optical flow, and wherein each control vertex is associated with a set of motion control parameters to specify the motion of said first image relative to the motion of said second image.

9. The method as in claim 1 wherein said transformation is a three-dimensional projective transformation to recover a depth estimate of the motion information, said depth estimate perpendicular to the plane of said first and second images.

10. The method as in claim 1 wherein the sequence of images are arranged in a temporal order, and further including

determining a total differences between any two images of said sequence of images by summing the differences between intervening temporally adjacent pairs of images of said sequence of images.

5. The method as in claim I further including

determining a light intensity gradient of said derived image at each location of said control vertices, and

displacing the locations of said control vertices by and an amount proportional to a corresponding one of said light intensity gradients of each of said control vertices.

11. In a computer system, a method for extracting motion information from a sequence of images, comprising:

storing a first set of light intensity values as a first image in a memory of the computer system;

storing a second set of light intensity values as a second image in the memory;

storing a plurality of control vertices in the memory as a data structure;

associating the plurality of control vertices with the second image, each control vertex having a predetermined location with respect to the second image;

adjusting the light intensity values of the second image to create a derived image, the adjusting being proportional to the distance between the control vertices and the light intensity values;

determining a difference in light intensity values between the first image and the derived image;

displacing each control vertex to a new predetermined location to minimize the difference between the first image and the derived image; and

repeating the adjusting, determining, and displacing steps until the difference between the first image and the derived image is less than a predetermined amount, the locations of distorted control vertices stored in said memory characterizing the motion information of the first image and the second image.

12. The method as in claim 11 wherein the adjusting step uses a bi-linear spline function parametrized by the locations of the control vertices.

13. The method as in claim 11 wherein the location of said control vertices are a regular sub-sampling of the locations of the light intensity values of the second image.

14. The method as in claim 11 including

determining an individual difference between each light intensity value of the first image and a corresponding light intensity value of the derived image;

combining the individual differences to determine the total difference between the first image and the derived image.

15. The method as in claim 11 including

displacing the control vertices proportionally to the rate of change of the difference between said first and derived image while repeating the adjusting, determining, and displacing steps.

16. The method as in claim 11 wherein the first image and the second image are stored as multi-level pixel pyramid having a plurality of images levels, the plurality of image levels being arranged in a coarse-to-fine order.

17. The method as in claim 16 wherein the adjusting, determining, and displacing steps are first performed at a coarser level of the multi-level pixel grid to extract coarse motion information, and where the coarse motion information is used to initiate the adjusting, determining, and displacing steps at a finer level of the multi-level pixel pyramid.

18. The method as in claim 11 wherein the motion of said first image relative to said second image is planar optical flow, and

assigning four control vertices to the second image.

19. The method as in claim 11 having a sequence of images arranged in a temporal order, and where a total differences of any two images of the sequence of images is determined by summing the differences between intervening temporally adjacent pairs of images of the sequence of images.

20. An apparatus for extracting motion information from a sequence of images, comprising:

a memory for storing a first image, a second image, and a plurality of control vertices associated with the second image, the first image, the second image, and the plurality of control vertices stored as data structures in the memory, the first and second images each expressed as a plurality of light intensity values, each light intensity value having a predetermined location, and the control vertices being expressed as coordinates relative to the locations of the light intensity values of the second image;

means for transforming the second image to a derived image by adjusting each light intensity value of the second image by an amount proportional to a distance between the location of a particular light intensity value and a location of a corresponding control vertex;

a comparator for determining a difference between the first image and the derived image; and

means for adjusting the location of each of the plurality of control vertices to minimize the difference between the first image and the derived image, the adjusted locations of the control vertices parametrizing the motion information of the first image and the second image.

21. The apparatus of claim 20 wherein the proportional adjustment of the light intensity values of the second image are expressed by a spline-function parametrized by the coordinates of the control vertices.

22. The apparatus of claim 20 where the coordinates are a regular sub-sampling of the locations of the light intensity values.

23. The apparatus of claim 20 further including

a spatial differentiator for determining a light intensity gradient at locations corresponding to the control vertices, and

an error integrator for combining the light intensity gradients with the difference between the first image and the derived image to determine an amount for displacing each of the control vertices.

24. An apparatus for extracting motion information from a sequence of images, comprising:

a memory storing a first image, a second image, and a plurality of control vertices associated with the second image, the first image, the second image, and the plurality of control vertices stored as data structures in the memory, the first and second images each expressed as a plurality of light intensity values, each light intensity value having a predetermined location, and the control vertices being expressed as coordinates relative to the locations of the light intensity values of the second image;

means for transforming the second image to a derived image, the transformation adjusting each light intensity value of the second image by an amount proportional to a distance between the location of a particular light intensity value and a corresponding control vertex, the proportional amount expressed as a spline-function parametrized by the distance;

a comparator for determining a difference between the first image and the derived image; and

means for adjusting the location of each of the plurality of control vertices to minimize the difference between the first image and the derived image, the adjusted locations of the control vertices stored in said memory parametrizing the motion information of the first image and the second image.

25. A computer implemented method for extracting motion information from a sequence of images, comprising the steps of:

storing a first physical image in a memory as a first set of light intensity values;

storing a second physical image in said memory as a second set of light intensity values;

defining, in said memory, a control grid for said first set of light intensity values, said control grid responsive to spline functions;

distorting said control grid into a distorted control grid;

interpreting the first set of light intensity values using said spline functions of said distorted control grid to generate a distorted set of light intensity values stored in said memory;

comparing said distorted set of light intensity values with said second set of light intensity values to determine a difference;

adjusting said distorted control grid to achieve a desired difference;

using a final distorted control grid stored in said memory after said desired difference is achieved to characterize motion of the light intensity values from said first physical image to said second physical image.