Pattern similarity metric for image search, registration, and comparison

• US 6,154,567 A
• Filed: 07/01/1998
• Issued: 11/28/2000
• Est. Priority Date: 07/01/1998
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: McGarry, E. John
• Primary Examiner(s): Tadayon, Bijan
• Assistant Examiner(s): Azarian, Seyed H.
• Application Number:
  US09/108,279
• Time in Patent Office: 881 Days
• Field of Search: 382/219, 382/222, 382/221, 382/229, 382/209, 364/552, 364/488, 364/150, 364/578
• US Class Current: 382/219
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06V 10/421 by analysing segments intersecting the pattern
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

The present invention provides a method for the calculation of a pattern similarity metric that is locally normalized with respect to illumination intensity, and is invariant with respect to rigid body preserving gray scale variations, such as scale, rotation, translation, and non-linear intensity transformations. In one aspect, the invention provides a method for comparing a model image with a run-time image so as to provide a quantitative measure of image similarity. In another general aspect of the invention, a method is provided for searching a run-time image with a model image so as to provide at least one location of the model image within the run-time image.

Claims

1. A method for comparing a model image with a run-time image so as to provide a quantitative measure of image similarity, the method comprising:

at train-time,

extracting sample pixels of the model image so as to provide a pixel position and a gray value for each sample pixel of the model image;

computing gray value differences between overlapping pairs of sample pixels of the model image;

computing a compact binary representation for each overlapping pair;

computing an expanded binary representation for each compact binary representation;

associating a corresponding pixel position with each expanded binary representation to provide a model element; and

grouping all model elements together to provide a model, and at run-time,

determining gray values at a plurality of selected pixel locations in a run-time image in accordance with pixel positions of the elements of the model;

computing gray value differences between overlapping pairs of the selected pixels of the run-time image;

computing a compact binary representation for each overlapping pair of the selected pixels of the run-time image;

computing a run-time bit-expanded representation for each run-time compact binary representation;

comparing each run-time bit-expanded representation with a corresponding model bit-expanded representation to provide a match count increment; and

combining all match count increments to provide a total match value.

2. The method of claim 1, wherein extracting sample pixels of the model image includes:

finding zero-crossings of the gray-scale second derivative of the model image.

3. The method of claim 1, wherein extracting sample pixels of the model image includes:

extracting sample pixels in a random pattern.

4. The method of claim 1, wherein extracting sample pixels of the model image includes:

extracting sample pixels in a biased random pattern.

5. The method of claim 1, wherein extracting sample pixels of the model image includes:

extracting sequences of sample pixels from alternating sides of a curve derived from the model image.

6. The method of claim 1, further comprising:

after computing the expanded binary representation for each compact binary representation, computing a perturbed expanded binary representation for each compact representation.

7. The method of claim 6, further comprising:

combining the perturbed expanded binary representation with the corresponding expanded binary representation.

8. The method of claim 1, further comprising:

associating a search strategy with the model.

9. The method of claim 1, further comprising:

associating normalizing information with the model.

10. The method of claim 1, wherein the step of determining gray values at a plurality of selected locations in a run-time image includes:

adding an image offset to the coordinate portion of each element of the model.

11. The method of claim 1, wherein the step of determining gray values at a plurality of selected locations in a run-time image includes:

transforming the coordinate portion of each element of the model, the selected locations in the run-time image being determined by the coordinates so-transformed.

12. The method of claim 1, wherein the train-time step of computing a compact binary representation includes computing a 3-bit representation.

13. The method of claim 1, wherein the run-time step of computing a compact binary representation includes computing a 3-bit representation.

14. The method of claim 1, wherein the step of comparing each run-time bit-expanded representation with a corresponding model bit-expanded representation to provide a match count increment includes:

for each bit of a bit-expanded code word, if both corresponding bits are equal to one, providing a match count increment, else, not providing a match count increment.

15. The method of claim 14, further including:

only when |Δ

_i+1 |+|Δ

_i | is greater than a threshold, providing a match count increment;

else, not providing a match count increment.

16. The method of claim 15, wherein the threshold is equal to 1.

17. The method of claim 14, wherein a match count increment is provided only if the condition "both corresponding bits are equal to one" has been satisfied over at least one previous match of a run-time bit-expanded representation with a corresponding model bit-expanded representation.

18. The method of claim 14, further including:

subtracting a match count increment whenever the phase angle of the model bit-expanded code is 180 degrees out of phase with respect to the phase angle of the corresponding run-time image bit-expanded code.

19. A method for searching a run-time image with a model image so as to provide at least one location of the model image within the run-time image, the method comprising:

at train-time,

extracting sample pixels of the model image so as to provide a pixel position and a gray value for each sample pixel of the model image;

computing gray value differences between overlapping pairs of sample pixels of the model image;

computing a compact binary representation for each overlapping pair;

computing an expanded binary representation for each compact binary representation;

associating a corresponding pixel position with each expanded binary representation to provide a model element; and

grouping all model elements together to provide a model, and at run-time,

determining gray values at a plurality of selected pixel locations in a run-time image in accordance with pixel positions of the elements of the model;

computing gray value differences between overlapping pairs of the selected pixels of the run-time image;

computing a compact binary representation for each overlapping pair of the selected pixels of the run-time image;

computing a run-time bit-expanded representation for each run-time compact binary representation;

comparing each run-time bit-expanded representation with a corresponding model bit-expanded representation to provide a match count increment;

combining all match count increments to provide a total match value;

determining a plurality of total match values at a plurality of positions in the run-time image to provide a total match value space; and

evaluating the total match value space so as to find local maxima.