Golden template comparison using efficient image registration

• US 5,640,200 A
• Filed: 12/28/1994
• Issued: 06/17/1997
• Est. Priority Date: 08/31/1994
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Michael, David J. S.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US08/364,920
• Time in Patent Office: 902 Days
• Field of Search: 348/86, 348/87, 348/92, 348/94, 348/95, 348/126, 348/130, 382/144, 382/145, 382/150, 382/151, 382/160
• US Class Current: 348/87
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06T 7/32 using correlation-based methods

Abstract

Golden Template Comparison (GTC) is a method that can be applied to flaw and defect detection in images of 2-dimensional scenes. When a test image is compared to a golden template image, the images must be registered, and then subtracted. The resulting difference image is then analyzed for features that indicate flaws or defects. The registration step is a major determinant of the performance of GTC, and the invention performs the registration step of GTC using a highly efficient and accurate registration method. The registration method of the invention provides substantial registration of all of the features common to the test image and the golden template image, even when one of the images to be registered is flawed, using a registration metric based on minimization of the sum of the absolute value of the differences between the images to be registered, and an efficient optimization technique, such as a version of gradient descent, wherein a local minimum in a registration metric space is found to the nearest pixel using less computational resources than needed to compute the entire registration metric space.

Claims

1. A method for golden template analysis of a test image, the method comprising the steps of:

acquisition of a plurality of sample images;

acquisition of a test image;

creating a golden template image using said plurality of sample images,;

comparing said golden template image with said test image, including the steps of;

registering said golden template image and said test image by minimizing a sum of absolute differences metric, and

subtracting said golden template image from said test image to provide a difference image; and

analyzing said difference image to provide comparison results.

2. The method of claim 1, wherein the step of creating a golden template image includes the step of:

registering said plurality of sample images by minimizing a sum of absolute differences metric.

3. The method of claim 1, wherein said golden template image includes:

a template image having a plurality of pixels, each pixel being the mean of a plurality of spatially corresponding pixels of the plurality of sample images; and

a standard deviation image having a plurality of pixels, each pixel being the standard deviation of the plurality of spatially corresponding pixels of the plurality of sample images.

4. The method of claim 1, wherein said step of registering said golden template image and said test image includes a whole-pixel registration phase and a sub-pixel registration phase.

5. The method of claim 1, wherein said step of analyzing said difference image includes the steps of:

subtracting a threshold image from said difference image to provide an error image; and

performing at least a geometric and topological analysis of said error image.

6. The method of claim 5, wherein said error image binarized prior to performing said at least geometric and topological analysis, wherein a first pixel value indicates that the corresponding absolute difference exceeded the threshold value for that pixel, and a second pixel value indicates that the corresponding absolute difference did not exceed the threshold value for that pixel.

7. The method of claim 5, wherein said threshold image is based on a linear mapping of a standard deviation image, and said standard deviation image is derived from said plurality of sample images, said linear mapping being determined at least partly by the effects of at least one of process variations, video noise, imaging variations, template errors, and scene misregistration.

8. The method of claim 1, wherein said step of registering said golden template image and said test image includes the steps of:

(A) selecting an initial relative displacement between said golden template image and said test image such that a plurality of pixels of said golden template image are in overlapping relationship with a plurality of pixels of said test 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 a gray value of each pixel of said golden template image and a gray value of the pixel of said test image that is in overlapping relationship with said each pixel of said golden template image;

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

computing a sum of absolute differences by computing the summation of each absolute value computed for each pixel of said golden template image that is in overlapping relationship with a pixel of said test 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.

9. The method of claim 8, further including the step of:

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

10. The method of claim 8, wherein said test image is at least as large as said golden template image, and said initial relative displacement between said golden template image and said test image is selected such that each of the pixels of said golden template image is in overlapping relationship with at least one pixel of said test image.

11. The method of claim 8, wherein said golden template 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.

12. The method of claim 8, further including the steps of:

selecting a search area within said test image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said test 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.

13. The method of claim 8, 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.

14. The method of claim 8, 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 golden template image is in overlapping relationship with a second pixel that contains the centroid of said test image.

15. The method of claim 8, 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.

16. The method of claim 8, 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.

17. The method of claim 1, wherein said step of registering said golden template image and said test image includes the steps of:

(A) selecting an initial relative displacement between said golden template image and said test image such that a plurality of pixels of said golden template image are in overlapping relationship with a plurality of pixels of said test 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.

18. The method of claim 17, 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.

19. The method of claim 17, wherein said test image is at least as large as said golden template image, and said initial relative displacement between said golden template image and said test image is selected such that each of the pixels of said golden template image is in overlapping relationship with at least one pixel of said test image.

20. The method of claim 17, wherein said golden template 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.

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

selecting a search area within said test image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said test 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.

22. The method of claim 17, 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.

23. The method of claim 17, wherein said minimum registration metric value is a local minimum registration metric value.

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

25. The method of claim 17, 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.

26. The method of claim 17, 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.

27. The method of claim 1, wherein said step of registering said golden template image and said test image includes the steps of:

(A) selecting an initial relative displacement between said golden template image and said test image such that a plurality of pixels of said golden template image are in overlapping relationship with a plurality of pixels of said test 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.

28. The method of claim 27, further including the step of:

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

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

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

30. The method of claim 27, 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.

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

32. The method of claim 27, wherein said golden template 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.

33. The method of claim 27, further including the step of:

selecting a search area within said test image, said search area being defined by a search area boundary that can enclose as many as all of the pixels of said test 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.

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

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