Efficient image registration
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
33 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31)
-
-
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. - View Dependent Claims (33)
-
Specification