Method for subpixel registration of images

• US 6,628,845 B1
• Filed: 03/15/2000
• Issued: 09/30/2003
• Est. Priority Date: 10/20/1999
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Martucci, Stephen, Stone, Harold S., Chang, EE-Chien, Orchard, Michael T.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US09/526,417
• Time in Patent Office: 1,294 Days
• Field of Search: 382/294, 382/295, 382/296, 382/289, 382/280, 382/151, 348/263, 348/264, 348/95, 358/450
• US Class Current: 382/294
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: G06T 7/37 using transform domain methods
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

Methods for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations are provided. A preferred implementation of the methods includes the steps of: multiplying the first image by a window function to create a first windowed image; transforming the first windowed image with a Fourier transform to create a first image Fourier transform; multiplying the second image by the window function to create a second windowed image; transforming the second windowed image with a Fourier transform to create a second image Fourier transform; computing a collection of coordinate pairs from the first and second image Fourier transforms such that at each coordinate pair the values of the first and second image Fourier transforms are likely to have very little aliasing noise; computing an estimate of a linear Fourier phase relation between the-first and second image Fourier transforms using the Fourier phases of the first and second image Fourier transforms at the coordinate pairs in a minimum-least squares sense; and computing the displacements in the x and/or y directions from the linear Fourier phase relationship. Also provided are a computer program having computer readable program code and program storage device having a program of instructions for executing and performing the methods of the present invention, respectively.

Claims

1. A method for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations, the method comprises the steps of:

multiplying the first image by a window function to create a first windowed image;

transforming the first windowed image with a Fourier transform to create a first image Fourier transform;

multiplying the second image by the window function to create a second windowed image;

transforming the second windowed image with a Fourier transform to create a second image Fourier transform;

computing a collection of coordinate pairs from the first and second image Fourier transforms such that at each coordinate pair the values of the first and second image Fourier transforms are likely to have very little aliasing noise;

computing an estimate of a linear Fourier phase relation between the first and second image Fourier transforms using the Fourier phases of the first and second image Fourier transforms at the coordinate pairs in a minimum-least squares sense; and

computing the displacements in the x and/or y directions from the linear Fourier phase relationship.

2. The method of claim 1, wherein the window is a periodic window function.

3. The method of claim 2, wherein the periodic window function is a 3-term Blackman window.

4. The method of claim 2, wherein the periodic window function is a 4-term Blackman-Harris window.

5. The method of claim 1, wherein the window function is a symmetric window function.

6. The method of claim 5, wherein the symmetric window function is a 3-term Blackman window.

7. The method of claim 5, wherein the symmetric window function is a 4-term Blackman-Harris window.

8. The method of claim 1, wherein the step of computing a collection of coordinate pairs comprises fixing the coordinate pairs to lie within a fixed distance of a central peak.

9. The method of claim 1, wherein the step of computing a collection of coordinate pairs comprises fixing the Fourier magnitude of the first image Fourier transform and of the second image Fourier transform to be among the highest predetermined percent of the magnitudes within a fixed distance of a central peak.

10. The method of claim 1, wherein the step of computing a collection of coordinate pairs comprises setting the ratio of the Fourier magnitude of the first image transform to the Fourier magnitude of the second image transform to lie between 1/(1+ρ

) and 1+ρ

, where ρ

is a positive number.

11. The method of claim 10, wherein ρ

is between 0.8 and 1.5.

12. The method of claim 1, wherein the step of computing a collection of coordinate pairs comprises a conjunction of two or more of the following:

fixing the coordinate pairs to lie within a fixed distance of a central peak;

fixing the Fourier magnitude of the first image Fourier transform and of the second image Fourier transform to be among the highest predetermined percent of the magnitudes within a fixed distance of a central peak; and

setting the ratio of the Fourier magnitude of the first image transform to the Fourier magnitude of the second image transform to lie between 1/(1+ρ

) and 1+ρ

, where ρ

is a positive number.

13. A method for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations, the method comprises the steps of:

registering the first and second images to the nearest pixel location; and

registering the first and second images to the nearest sub-pixel location, wherein the registering of the first and second images to the nearest sub-pixel location comprises the steps of;

multiplying the first image by a window function to create a first windowed image;

transforming the first windowed image with a Fourier

transform to create a first image Fourier transform;

multiplying the second image by the window function to create a second windowed image;

transforming the second windowed image with a Fourier transform to create a second image Fourier transform;

computing a collection of coordinate pairs from the first and second image Fourier transforms such that at each coordinate pair the values of the first and second image Fourier transforms are likely to have very little aliasing noise;

computing an estimate of a linear Fourier phase relation between the first and second image Fourier transforms using the Fourier phases of the first and second image Fourier transforms at the coordinate pairs in a minimum-least squares sense; and

computing the displacements in the x and/or y directions from the linear Fourier phase relationship.

14. The method of claim 13, wherein the window is a periodic window function.

15. The method of claim 14, wherein the periodic window function is a 3-term Blackman window.

16. The method of claim 14, wherein the periodic window function is a 4-term Blackman-Harris window.

17. The method of claim 13, wherein the window function is a symmetric window function.

18. The method of claim 17, wherein the symmetric window function is a 3-term Blackman window.

19. The method of claim 17, wherein the symmetric window function is a 4-term Blackman-Harris window.

20. The method of claim 13, wherein the step of computing a collection of coordinate pairs comprises fixing the coordinate pairs to lie within a fixed distance of a central peak.

21. The method of claim 13, wherein the step of computing a collection of coordinate pairs comprises fixing the Fourier magnitude of the first image Fourier transform and of the second image Fourier transform to be among the highest predetermined percent of the magnitudes within a fixed distance of a central peak.

22. The method of claim 13, wherein the step of computing a collection of coordinate pairs comprises setting the ratio of the Fourier magnitude of the first image transform to the Fourier magnitude of the second image transform to lie between 1/(1+ρ

) and 1+ρ

, where ρ

is a positive number.

23. The method of claim 22, wherein ρ

is between 0.8 and 1.5.

24. The method of claim 13, wherein the step of computing a collection of coordinate pairs comprises a conjunction of two or more of the following:

fixing the coordinate pairs to lie within a fixed distance of a central peak;

fixing the Fourier magnitude of the first image Fourier transform and of the second image Fourier transform to be among the highest predetermined percent of the magnitudes within a fixed distance of a central peak; and

setting the ratio of the Fourier magnitude of the first image transform to the Fourier magnitude of the second image transform to lie between 1/(1+ρ

) and 1+ρ

, where ρ

is a positive number.

25. A computer program product embodied in a computer-readable medium for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations, the computer program product comprising:

computer readable program code means for multiplying the first image by a window function to create a first windowed image;

computer readable program code means for transforming the first windowed image with a Fourier transform to create a first image Fourier transform;

computer readable program code means for multiplying the second image by the window function to create a second windowed image;

computer readable program code means for transforming the second windowed image with a Fourier transform to create a second image Fourier transform;

computer readable program code means for computing a collection of coordinate pairs from the first and second image Fourier transforms such that at each coordinate pair the values of the first and second image Fourier transforms are likely to have very little aliasing noise;

computer readable program code means for computing an estimate of a linear Fourier phase relation between the first and second image Fourier transforms using the Fourier phases of the first and second image Fourier transforms at the coordinate pairs in a minimum-least squares sense; and

computer readable program code means for computing the displacements in the x and/or y directions from the linear Fourier phase relationship.

26. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations, the method comprises the steps of:

multiplying the first image by a window function to create a first windowed image;

transforming the first windowed image with a Fourier transform to create a first image Fourier transform;

multiplying the second image by the window function to create a second windowed image;

transforming the second windowed image with a Fourier transform to create a second image Fourier transform;

computing a collection of coordinate pairs from the first and second image Fourier transforms such that at each coordinate pair the values of the first and second image Fourier transforms are likely to have very little aliasing noise;

computing an estimate of a linear Fourier phase relation between the first and second image Fourier transforms using the Fourier phases of the first and second image Fourier transforms at the coordinate pairs in a minimum-least squares sense; and

computing the displacements in the x and/or y directions from the linear Fourier phase relationship.

27. A method for registering first and second images which are offset by an x and/or y displacement in sub-pixel locations, the method comprises the steps of:

(a) Fourier transforming the first image to produce a first image Fourier transform;

(b) Fourier transforming the second image to produce a second image Fourier transform;

(c) summing the energy of the first image Fourier transform and the energy of the second image Fourier transform and dividing the sum by 2 to produce an average image energy;

(d) selecting one or more first displacements for an iterative search;

(e) using each first displacement, the first-image Fourier transform, and the second-image Fourier transform to compute a first baseband-plus-aliasing Fourier transform;

(f) comparing the energy of the first baseband-plus-aliasing Fourier transform to the average image energy;

(g) stopping the search if the energy comparisons are within a fixed precision;

(h) continuing the search if the energy comparisons are not within the fixed precision by selecting a new displacement for the search;

(i) computing a second baseband-plus-aliasing Fourier transform using the new displacement, first-image Fourier transform, and the second-image Fourier transform;

(j) repeating steps (h) and (i) until the fixed precision is reached or a criterion for stopping the search unsuccessfully is satisfied.