Efficient image registration

• US 5,548,326 A
• Filed: 08/31/1994
• Issued: 08/20/1996
• Est. Priority Date: 10/06/1993
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Michael, David
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US08/299,015
• Time in Patent Office: 720 Days
• Field of Search: 348/86, 348/87, 348/90, 348/92, 348/94, 348/95, 348/126, 382/145, 382/146, 382/147, 382/149, 382/150, 382/151
• US Class Current: 348/87
• CPC Class Codes: B23K 20/007 Ball bonding
• CPC Class Codes: B23K 31/12 relating to investigating the properties, e.g. the weldability, of materials
• CPC Class Codes: B23K 37/04 for holding or positioning work
• CPC Class Codes: G01R 31/309 of printed or hybrid circuits or circuit substrates
• CPC Class Codes: G01R 31/66 Testing of connections, e.g. of plugs or non-disconnectable joints testing for incorrect line connections G01R31/55
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 2207/30152 Solder
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration

Abstract

A method and apparatus for efficient registration of a pair of digitized images is provided that obtains a registration metric value based upon a Sum of Absolute Differences registration metric computation for each of a plurality of neighboring-pixel relative displacements, and, for example, iteratively selects a new initial relative displacement from among the plurality of neighboring-pixel relative displacements such that each succeeding new initial relative displacement is associated with a smaller registration metric value, until an initial relative displacement that is associated with a minimum registration metric value is reached. In general, the relative displacement that is associated with the minimum registration metric value is located using a two-dimensional numerical optimization analysis. The invention is especially useful for flaw and defect analysis, such as Golden Template Analysis, third optical inspection, as well as for pair-wise comparison of die images on a semiconductor wafer.

Claims

1. A method for efficient registration of a pair of digitized images including a first image and a second image, each image including a plurality of pixels, each pixel being associated with at least one of a gray value and a don'"'"'t-care symbol, the method comprising the steps of:

(A) selecting an initial relative displacement between said first image and said second image such that a plurality of pixels of said first image are in overlapping relationship with a plurality of pixels of said second image;

(B) computing a registration metric value corresponding to said initial relative displacement using a registration metric computation that includes the steps of;

computing the difference between the gray value of each pixel of said first image and the gray value of the pixel of said second image that is in overlapping relationship with said each pixel of said first image;

computing the absolute value of the difference between the gray value of each pixel of said first image and the gray value of each pixel of said second image that is in overlapping relationship with said each pixel of said first image; and

computing a sum of absolute differences by computing the summation of each absolute value computed for each pixel of said first image that is in overlapping relationship with a pixel of said second image;

(C) computing a registration metric value corresponding to each of a plurality of neighboring-pixel displacements using said registration metric computation;

(D) determining which displacement among the plurality of neighboring-pixel displacements and said initial relative displacement resulted in the smallest registration metric value;

(E) if the displacement that resulted in the smallest registration metric value is one of said plurality of neighboring-pixel displacements, repeating steps (A), (B), (C), (D), and (E) using said one displacement as said initial relative displacement; and

(F) else, provide registration parameters corresponding to the most recent version of said initial relative displacement for placing said pair of digitized images in registered relationship.

2. The method of claim 1, further including the step of:

using said registration parameters for computing sub-pixel registration parameters.

3. The method of claim 1, further including the step of:

after step (E), if the displacement that resulted in the smallest registration metric value is not one of said plurality of neighboring-pixel displacements, calculating a difference image based on a difference between said first image and said second image, wherein said first and second images are relatively displaced according to said most recent version of said initial relative displacement.

4. The method of claim 1, wherein said second image is at least as large as said first image, and said initial relative displacement between said first image and said second image is selected such that each of the pixels of said first image is in overlapping relationship with at least one pixel of said second image.

5. The method of claim 1, wherein said first image includes a region that includes a first plurality of pixels, each pixel of said first plurality of pixels being associated with a gray value, and wherein said region is bounded by at least a second plurality of pixels, each pixel of said second plurality of pixels being associated with a don'"'"'t-care symbol.

6. The method of claim 1, further including the steps of:

selecting a search area within said second image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said second image,

and wherein step (E) further includes the step of;

if the displacement that resulted in the smallest registration metric value falls outside of the search area boundary, providing registration parameters corresponding to the most recent version of said initial relative displacement for placing said pair of digitized images in registered relationship.

7. The method of claim 1, further including the steps of:

after step (B), storing said registration metric value in association with said initial relative displacement; and

after step (C), storing each said registration metric value in association with a corresponding neighboring-pixel displacement, and

wherein in step (E), whenever steps (A), (B), (C), (D), and (E) are repeated, a registration metric value for a relative displacement is calculated only if a registration metric value has not been previously calculated and stored in association with said relative displacement.

8. The method of claim 1, wherein said initial relative displacement between said first image and said second image is such that a first pixel that contains the centroid of said first image is in overlapping relationship with a second pixel that contains the centroid of said second image.

9. The method of claim 1, wherein the step of computing a registration metric value corresponding to each of a plurality of neighboring-pixel relative displacements is computed for the contiguous north, east, south, and west neighboring-pixel relative displacements.

10. The method of claim 1, wherein the step of computing a registration metric value corresponding to each of a plurality of neighboring-pixel relative displacements is computed for the contiguous north, east, south, west, north-east, south-east, south-west, and north-west neighboring-pixel relative displacements.

11. A method for efficient registration of a pair of digitized images including a first image and a second image, each image including a plurality of pixels, each pixel being associated with at least one of a gray value and a don'"'"'t-care symbol, the method comprising the steps of:

(A) selecting an initial relative displacement between said first image and said second image such that a plurality of pixels of said first image are in overlapping relationship with a plurality of pixels of said second image;

(B) computing a registration metric value corresponding to said initial relative displacement using a Sum of Absolute Differences registration metric computation;

(C) obtaining a registration metric value based upon said Sum of Absolute Differences registration metric computation for each of a plurality of neighboring-pixel relative displacements, and iteratively selecting a new initial relative displacement from among said plurality of neighboring-pixel relative displacements such that each succeeding new initial relative displacement is associated with a smaller registration metric value, until an initial relative displacement that is associated with a minimum registration metric value is reached.

12. The method of claim 11, further including the step of:

based upon said initial relative displacement that is associated with a minimum registration metric, computing sub-pixel registration parameters.

13. The method of claim 11, further including the step of:

upon reaching said initial relative displacement that is associated with a minimum registration metric, calculating a difference image based upon a difference between said first image and said second image, wherein said first and second images are relatively displaced according to said initial relative displacement.

14. The method of claim 11, wherein the step of obtaining said registration metric value includes the steps of:

calculating a registration metric value for a relative displacement based upon said Sum of Absolute Differences registration metric computation only if a registration metric value has not already been calculated and previously stored in association with said relative displacement.

15. The method of claim 11, wherein said second image is at least as large as said first image, and said initial relative displacement between said first image and said second image is selected such that each of the pixels of said first image is in overlapping relationship with at least one pixel of said second image.

16. The method of claim 11, wherein said first image includes a region that includes a first plurality of pixels, each pixel of said first plurality of pixels being associated with a gray value, and wherein said region is bounded by at least a second plurality of pixels, each pixel of said second plurality of pixels being associated with a don'"'"'t-care symbol.

17. The method of claim 11, further including the step of:

selecting a search area within said second image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said second image,

and wherein the step of iteratively computing a registration metric value also terminates when a succeeding new initial relative displacement falls outside of the search area boundary, whereupon registration parameters are provided corresponding to the most recent version of said initial displacement that does not fall outside of the search area boundary.

18. The method of claim 11, further including the step of:

(D) providing registration parameters corresponding to the version of said initial displacement that is associated with said minimum registration metric value.

19. The method of claim 11, wherein said minimum registration metric value is a local minimum registration metric value.

20. The method of claim 11, wherein said initial relative displacement between said first image and said second image is such that a first pixel that contains the centroid of said first image is in overlapping relationship with a second pixel that contains the centroid of said second image.

21. The method of claim 11, wherein the step of computing a registration metric value corresponding to each of a plurality of neighboring-pixel relative displacements is computed for the contiguous north, east, south, and west neighboring-pixel relative displacements.

22. The method of claim 11, wherein the step of computing a registration metric value corresponding to each of a plurality of neighboring-pixel relative displacements is computed for the contiguous north, east, south, west, north-east, south-east, south-west, and north-west neighboring-pixel relative displacements.

23. A method for efficient registration of a pair of digitized images including a first image and a second image, each image including a plurality of pixels, each pixel being associated with at least one of a gray value and a don'"'"'t-care symbol, the method comprising the steps of:

(A) selecting an initial relative displacement between said first image and said second image such that a plurality of pixels of said first image are in overlapping relationship with a plurality of pixels of said second image;

(B) computing a registration metric value corresponding to said initial relative displacement using a Sum of Absolute Differences registration metric computation;

(C) locating a relative displacement that is associated with a minimum registration metric value using a two-dimensional numerical optimization analysis.

24. The method of claim 23, further including the step of:

based on said relative displacement that is associated with said minimum registration metric value, computing sub-pixel registration parameters.

25. The method of claim 23, further including the step of:

after step (C), calculating a difference image based upon a difference between said first image and said second image, wherein said first and second images are relatively displaced according to said relative displacement that is associated with said minimum registration metric value.

26. The method of claim 23, step (C) further including the step of:

calculating a registration metric value for a relative displacement based upon said Sum of Absolute Differences registration metric computation only if a registration metric value has not already been calculated and previously stored in association with said relative displacement.

27. The method of claim 23, wherein said second image is at least as large as said first image, and said initial relative displacement between said first image and said second image is selected such that each of the pixels of said first image is in overlapping relationship with at least one pixel of said second image.

28. The method of claim 23, wherein said first image includes a region that includes a first plurality of pixels, each pixel of said first plurality of pixels being associated with a gray value, and wherein said region is bounded by at least a second plurality of pixels, each pixel of said second plurality of pixels being associated with a don'"'"'t-care symbol.

29. The method of claim 23, further including the step of:

selecting a search area within said second image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said second image,

and wherein said relative displacement, of the step of locating a relative displacement that is associated with a minimum registration metric value, does not fall outside of the search area boundary.

30. The method of claim 23, wherein said two-dimensional numerical optimization analysis is a gradient descent analysis.

31. The method of claim 23, wherein said two-dimensional numerical optimization analysis is a steepest descent analysis.

32. Apparatus for efficient registration of a pair of digitized images including a first image and a second image, each image including a plurality of pixels, each pixel being associated with at least one of a gray value and a don'"'"'t-care symbol, the apparatus comprising:

(A) means for selecting an initial relative displacement between said first image and said second image such that a plurality of pixels of said first image are in overlapping relationship with a plurality of pixels of said second image;

(B) means for computing a registration metric value corresponding to said initial relative displacement using a Sum of Absolute Differences registration metric computation;

(C) means for locating a relative displacement that is associated with a minimum registration metric value using a two-dimensional numerical optimization analysis.

33. The apparatus of claim 32, wherein said means for computing a registration metric value comprises:

means for computing the absolute value of the difference between the gray value of each pixel of said first image and the gray value of each pixel of said second image that is in overlapping relationship with said each pixel of said first image; and

means, in communication with said means for computing the absolute value, for computing a sum of absolute differences by computing the summation of each absolute value computed for each pixel of said first image that is in overlapping relationship with a pixel of said second image.