Image registration method

• US 6,266,452 B1
• Filed: 03/18/1999
• Issued: 07/24/2001
• Est. Priority Date: 03/18/1999
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: McGuire, Morgan S.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/271,643
• Time in Patent Office: 859 Days
• Field of Search: 382/294, 382/295, 382/298, 382/300, 382/264, 382/254, 382/293, 382/266, 382/276, 382/277, 382/278, 382/280, 382/289, 382/170, 382/124, 382/296, 382/297, 382/299, 359/29, 348/42
• US Class Current: 382/294
• CPC Class Codes: G06T 3/02 Affine transformations for image registration G06T3/147; for image mosaicing G06T3/4038
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/37 using transform domain methods
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method for registering a pattern image with a reference image is provided. The pattern image and the reference image differ from each other by a Rotation-Scale-Translation (RST) transformation defined by a scale factor s, a rotation factor φ, and a translation vector (Δx, Δy). A Fourier-Mellin invariant is used to perform image registration by isolating the rotation, scale and transformation parameters of the RST transformation between the reference image r and the pattern image p.

Claims

1. A method for registering a pattern image with a reference image, wherein the pattern image and the reference image differ from each other by a Rotation-Scale-Translation transformation defined by a scale factor s, a rotation factor φ

, and a translation vector (Δ

x, Δ

y), the method comprising;

(a) preprocessing the reference image and the pattern image, including the steps of;

(a-1) transforming the reference image and the pattern image from a pixel domain to a Fourier-Mellin domain to provide a transformed reference and a transformed pattern, respectively; and

(a-2) converting the transformed reference and the transformed pattern from Cartesian (x, y) coordinates to polar-log (log_B(radius), angle) coordinates, where B is a global constant logarithm base;

(b) recovering at least one potential scale factor, including the steps of;

(b-1) summing the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern along the angle axis thereof to provide a reference scale signature and a pattern scale signature, respectively;

(b-2) correlating the reference scale signature with the pattern scale signature using a normalized correlation to provide a correlated scale signature;

(b-3) detecting local maxima of the correlated scale signature which comprise a set of scale signature shifts; and

(b-4) raising the logarithm base B to the power of each scale signature shift to provide the at least one potential scale factor;

(c) recovering the rotation factor φ

, including the steps of;

(c-1) summing the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern along the log_B(radius) axis thereof to provide a reference rotation signature and a pattern rotation signature, respectively;

(c-2) correlating the reference rotation signature with the pattern rotation signature using a normalized circular correlation to provide a correlated rotation signature; and

(c-3) detecting the maximum value of the correlated rotation signature which comprises the rotation factor φ

; and

(d) recovering the scale factor s and the translation vector (Δ

x, Δ

y), including the steps of;

(d-1) rotating the pattern image by −

φ

to provide a rotated pattern;

(d-2) for each potential scale factor, resealing the rotated pattern by the inverse of the potential scale factor to provide a candidate pattern;

(d-3) for each candidate pattern, determining a potential translation vector which, when the candidate pattern is translated by the potential translation vector, produces the highest correlation between the reference image and the translated candidate pattern; and

(d-4) selecting the translated candidate pattern which produces the highest correlation with the reference image, whereby the potential scale factor and the potential translation vector associated with the selected candidate pattern comprise the actual scale factor s and the actual translation vector (Δ

x, Δ

y), respectively.

2. The method of claim 1, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of wavelet-decomposing the reference image and the pattern image prior to the transforming step (a-1).

3. The method of claim 1, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of filtering the reference image and the pattern image to prevent artifacts caused by implicit tiling of the reference image and the pattern image prior to the transforming step (a-1).

4. The method of claim 3, wherein the step of filtering to prevent artifacts comprises filtering the reference image and the pattern image with a blur filter to remove the artifacts.

5. The method of claim 1, wherein the step (b) of recovering at least one potential scale factor further includes the step of filtering the reference scale signature and the pattern scale signature after the summing step (b-1) and prior to the correlating step (b-2) to increase the signal-to-noise ratio of the scale signatures.

6. The method of claim 1, wherein the step (c) of recovering the rotation factor φ

further includes the step of filtering the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern prior to the summing step (c-1) to enhance edges present therein.

17. The method of claim 4, wherein the blur filter blurs edges cyclically around the image to which it is applied.

18. The method of claim 17, wherein the blur filter blurs the edges by smoothing pixels within a predetermined number of pixels of the image border.

7. A method for registering a pattern image with a reference image, wherein the pattern image and the reference image differ from each other by a Rotation-Scale-Translation transformation defined by a scale factor s, a rotation factor φ

, and a translation vector (Δ

x, Δ

y), wherein the scale factor s is known, the method comprising;

(a) preprocessing the reference image and the pattern image, including the steps of;

(a-1) transforming the reference image and the pattern image from a pixel domain to a Fourier-Mellin domain to provide a transformed reference and a transformed pattern, respectively; and

(a-2) converting the transformed reference and the transformed pattern from Cartesian (x, y) coordinates to polar-log (log_B(radius), angle) coordinates, where B is a global constant logarithm base;

(b) recovering the rotation factor φ

, including the steps of;

(b-1) summing the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern along the log_B(radius) axis thereof to provide a reference rotation signature and a pattern rotation signature, respectively;

(b-2) correlating the reference rotation signature with the pattern rotation signature using a normalized circular correlation to provide a correlated rotation signature; and

(b-3) detecting the maximum value of the correlated rotation signature which comprises the rotation factor φ

; and

(c) recovering the translation vector (Δ

x, Δ

y), including the steps of;

(c-1) rotating the pattern image by −

φ

to provide a rotated pattern;

(c-2) rescaling the rotated pattern by the inverse of the scale factor s to provide a candidate pattern;

(c-3) determining the translation vector (Δ

x, Δ

y) which, when the candidate pattern is translated by the translation vector (Δ

x, Δ

y), produces the highest correlation between the reference image and the translated candidate pattern.

8. The method of claim 7, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of wavelet-decomposing the reference image and the pattern image prior to the transforming step (a-1).

9. The method of claim 7, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of filtering the reference image and the pattern image to prevent artifacts caused by implicit tiling of the reference image and the pattern image prior to the transforming step (a-1).

10. The method of claim 9, wherein the step of filtering to prevent artifacts comprises filtering the reference image and the pattern image with a blur filter to remove the artifacts.

11. The method of claim 7, wherein the step (b) of recovering the rotation factor φ

further includes the step of filtering the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern prior to the summing step (b-1) to enhance edges present therein.

19. The method of claim 10, wherein the blur filter blurs edges cyclically around the image to which it is applied.

20. The method of claim 19, wherein the blur filter blurs the edges by smoothing pixels within a predetermined number of pixels of the image border.

12. A method for registering a pattern image with a reference image, wherein the pattern image and the reference image differ from each other by a Rotation-Scale-Translation transformation defined by a scale factor s, a rotation factor φ

, and a translation vector (Δ

x, Δ

y), wherein the rotation factor φ

is known, the method comprising;

(a) preprocessing the reference image and the pattern image, including the steps of;

(a-1) transforming the reference image and the pattern image from a pixel domain to a Fourier-Mellin domain to provide a transformed reference and a transformed pattern, respectively; and

(a-2) converting the transformed reference and the transformed pattern from Cartesian (x, y) coordinates to polar-log (log_B(radius), angle) coordinates, where B is a global constant logarithm base;

(b) recovering at least one potential scale factor, including the steps of;

(b-1) summing the polar-log (log_B(radius), angle) reference and the polar-log (log_B(radius), angle) pattern along the angle axis thereof to provide a reference scale signature and a pattern scale signature, respectively;

(b-2) correlating the reference scale signature with the pattern scale signature using a normalized correlation to provide a correlated scale signature;

(b-3) detecting local maxima of the correlated scale signature which comprise a set of scale signature shifts; and

(b-4) raising the logarithm base B to the power of each scale signature shift to provide the at least one potential scale factor; and

(c) recovering the scale factor s and the translation vector (Δ

x, Δ

y), including the steps of;

(c-1) rotating the pattern image by −

φ

to provide a rotated pattern;

(c-2) for each potential scale factor, resealing the rotated pattern by the inverse of the potential scale factor to provide a candidate pattern;

(c-3) for each candidate pattern, determining a potential translation vector which, when the candidate pattern is translated by the potential translation vector, produces the highest correlation between the reference image and the translated candidate pattern; and

(c-4) selecting the translated candidate pattern which produces the highest correlation with the reference image, whereby the potential scale factor and the potential translation vector associated with the selected candidate pattern comprise the actual scale factor s and the actual translation vector (Δ

x, Δ

y), respectively.

13. The method of claim 12, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of wavelet-decomposing the reference image and the pattern image prior to the transforming step (a-1).

14. The method of claim 12, wherein the step (a) of preprocessing the reference image and the pattern image further includes the step of filtering the reference image and the pattern image to prevent artifacts caused by implicit tiling of the reference image and the pattern image prior to the transforming step (a-1).

15. The method of claim 14, wherein the step of filtering to prevent artifacts comprises filtering the reference image and the pattern image with a blur filter to remove the artifacts.

16. The method of claim 12, wherein the step (b) of recovering at least one potential scale factor further includes the step of filtering the reference scale signature and the pattern scale signature after the summing step (b-1) and prior to the correlating step (b-2) to increase the signal-to-noise ratio of the scale signatures.

21. The method of claim 15, wherein the blur filter blurs edges cyclically around the image to which it is applied.

22. The method of claim 21, wherein the blur filter blurs the edges by smoothing pixels within a predetermined number of pixels of the image border.