Pattern matching system and method with improved template image sampling using low discrepancy sequences

• US 6,229,921 B1
• Filed: 01/06/1999
• Issued: 05/08/2001
• Est. Priority Date: 01/06/1999
• Status: Expired due to Term

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Vazquez, Nicolas, Wenzel, Lothar, DeKey, Samson
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Azarian, Seyed
• Application Number:
  US09/227,508
• Time in Patent Office: 853 Days
• Field of Search: 382/209, 382/210, 382/208, 382/217, 382/112, 382/141, 382/161, 382/100, 382/181, 382/215, 382/220, 707/526, 707/527, 707/523, 704/221, 704/231, 704/236, 704/237, 704/243
• US Class Current: 382/209
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30108 Industrial image inspection
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation

Abstract

A system and method for performing pattern matching to locate zero or more instances of a template image in a target image. The method first comprises sampling the template image using a Low Discrepancy sequence, also referred to as a quasi-random sequence, to determine a plurality of sample pixels in the template image which accurately characterize the template image. The Low Discrepancy sequence is designed to produce sample points which maximally avoid each other. After the template image is sampled or characterized, the method then performs pattern matching using the sample pixels and the target image to determine zero or more locations of the template image in the target image. The method may also perform a local stability analysis around at least a subset of the sample pixels to determine a lesser third number of sample pixels which have a desired degree of stability, and then perform pattern matching using the third plurality of sample pixels. In one embodiment, the local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes, and the pattern matching performs a plurality of iterations of pattern matching using different sets of sample pixels, preferably performed in a coarse to fine manner, e.g., using sets of sample pixels with successively smaller stability neighborhood sizes and/or step sizes. The present invention also includes performing rotation invariant pattern matching by sampling the template image along one or more rotationally invariant paths, preferably circular perimeters, to produce one or more sets of sample pixels. These sample pixels from the circular paths are then used in the pattern matching. The rotationally invariant pattern matching may also use local stability analysis and coarse to fine searching techniques.

Claims

1. A method for performing pattern matching to locate a template image in a target image, wherein the target image is larger than the template image, wherein the template image comprises a first plurality of pixels, the method comprising:

sampling the template image using a Low Discrepancy sequence to determine a second plurality of sample pixels in the template image which characterize the template image, wherein said second plurality is less than said first plurality;

performing pattern matching using the second plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

2. The method of claim 1, wherein the Low Discrepancy sequence is a quasi-random sequence.

3. The method of claim 1, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

4. The method of claim 1, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the template image than a random sequence.

5. The method of claim 1, wherein the Low Discrepancy sequence is a Halton sequence.

6. The method of claim 1, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

7. The method of claim 1,

wherein said sampling determines a second number of sample pixels, wherein said second number is less than said first number;

the method further comprising;

performing a local stability analysis for at least a subset of said sample pixels, wherein said performing said local stability analysis determines a third plurality of sample pixels which have a desired degree of stability, wherein said third number is less than said second number;

wherein said performing pattern matching uses the third plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

8. The method of claim 7, wherein said performing the local stability analysis operates to ensure stability of each of said subset of sample pixels to spatial perturbations around the sample pixel.

9. The method of claim 7, wherein said performing the local stability analysis for each of said at least a subset of said sample pixels comprises:

for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

10. The method of claim 7, wherein said performing the local stability analysis determines a first set of sample pixels with a first stability neighborhood size and a second set of sample pixels with a second stability neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein said performing pattern matching comprises;

performing a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

performing a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

11. The method of claim 1, the method further comprising:

performing a local stability analysis around at least a subset of said sample pixels, wherein said performing said local stability analysis determines a stability neighborhood for each of said subset of said sample pixels;

wherein said performing the local stability analysis determines a first set of sample pixels with a first neighborhood size and a second set of sample pixels with a second neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein said performing pattern matching comprises;

performing a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

performing a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

12. The method of claim 11, wherein said performing the local stability analysis for each of said at least a subset of said sample pixels comprises:

for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

13. The method of claim 11, wherein said performing the pattern matching utilizing the first stability neighborhood size includes using a first step size, and wherein the performing pattern matching using the second stability neighborhood size utilizes a second step size, wherein said first step size is greater than said second step size.

14. The method of claim 13, wherein said first step size corresponds to said first stability neighborhood size and wherein said second step size corresponds to said second stability neighborhood size.

15. The method of claim 1, further comprising:

receiving the target image after said sampling the template image, wherein said performing pattern matching is performed in response to receiving the target image, wherein said pattern matching is performed substantially in real time after receiving the target image.

16. A system for performing pattern matching to locate a template image in a target image, wherein the target image is larger than the template image, wherein the template image comprises a first plurality of pixels, the system comprising:

a memory which stores the template image;

a processor coupled to the memory which is operable to sample the template image using a Low Discrepancy sequence to determine a second plurality of sample pixels in the template image which characterize the template image, wherein said second plurality is less than said first plurality;

wherein the processor is operable to perform pattern matching using the second plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

17. The system of claim 16, wherein the Low Discrepancy sequence is a quasi-random sequence.

18. The system of claim 16, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

19. The system of claim 16, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the template image than a random sequence.

20. The system of claim 16, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

21. The system of claim 16,

wherein, in sampling the template image using the Low Discrepancy sequence, the processor determines a second number of sample pixels, wherein said second number is less than said first number;

wherein the processor is further operable to;

perform a local stability analysis for at least a subset of said sample pixels, wherein said local stability analysis determines a third plurality of sample pixels which have a desired degree of stability, wherein said third number is less than said second number;

wherein, in performing pattern matching using the sample pixels and the target image, the processor uses the third plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

22. The system of claim 21, wherein the local stability analysis operates to ensure stability of each of said subset of sample pixels to spatial perturbations around the sample pixel.

23. The system of claim 21, wherein the local stability analysis for each of said at least a subset of said sample pixels comprises, for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

24. The system of claim 21, wherein, in performing the local stability analysis, the processor is operable to determine a first set of sample pixels with a first stability neighborhood size and a second set of sample pixels with a second stability neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein, in performing said pattern matching, the processor is operable to;

perform a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

perform a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

25. The system of claim 16, wherein the processor is further operable to:

perform a local stability analysis around at least a subset of said sample pixels, wherein said local stability analysis determines a stability neighborhood for each of said subset of said sample pixels;

wherein said local stability analysis determines a first set of sample pixels with a first neighborhood size and a second set of sample pixels with a second neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein, in performing said pattern matching, the processor is operable to;

perform a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

perform a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

26. The system of claim 25, wherein the local stability analysis for each of said at least a subset of said sample pixels comprises, for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

27. The system of claim 25, wherein the pattern matching utilizing the first stability neighborhood size includes using a first step size, and wherein the pattern matching using the second stability neighborhood size utilizes a second step size, wherein said first step size is greater than said second step size.

28. The system of claim 27, wherein said first step size corresponds to said first stability neighborhood size and wherein said second step size corresponds to said second stability neighborhood size.

29. The system of claim 16, wherein the system further includes an input for receiving the target image;

wherein the processor performs said pattern matching in response to the input receiving the target image, wherein said pattern matching is performed substantially in real time after receiving the target image.

30. The system of claim 16, wherein the system is a machine vision system.

31. A memory medium which comprises program instructions for performing pattern matching to locate a template image in a target image, wherein the target image is larger than the template image, wherein the template image comprises a first plurality of pixels, wherein the program instructions are executable to implement:

sampling the template image using a Low Discrepancy sequence to determine a second plurality of sample pixels in the template image which characterize the template image, wherein said second plurality is less than said first plurality;

performing pattern matching using the second plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

32. The memory medium of claim 31, wherein the Low Discrepancy sequence is a quasi-random sequence.

33. The memory medium of claim 31, wherein the Low Discrepancy sequence is designed to produce sample points which maximally avoid each other.

34. The memory medium of claim 31, wherein said Low Discrepancy sequence sampling results in fewer points to characterize the template image than a random sequence.

35. The memory medium of claim 31, wherein the Low Discrepancy sequence is a sequence selected from the group comprising:

Halton, Sobol, Faure, and Niederreiter.

36. The memory medium of claim 31,

wherein said sampling determines a second number of sample pixels, wherein said second number is less than said first number;

wherein the program instructions are further executable to implement;

performing a local stability analysis for at least a subset of said sample pixels, wherein said performing said local stability analysis determines a third plurality of sample pixels which have a desired degree of stability, wherein said third number is less than said second number;

wherein said performing pattern matching uses the third plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

37. The memory medium of claim 36, wherein said performing the local stability analysis operates to ensure stability of each of said subset of sample pixels to spatial perturbations around the sample pixel.

38. The memory medium of claim 36, wherein said performing the local stability analysis for each of said at least a subset of said sample pixels comprises:

for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

39. The memory medium of claim 36, wherein said performing the local stability analysis determines a first set of sample pixels with a first stability neighborhood size and a second set of sample pixels with a second stability neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein said performing pattern matching comprises;

performing a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

performing a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

40. The memory medium of claim 31, wherein the program instructions are further executable to implement:

performing a local stability analysis around at least a subset of said sample pixels, wherein said performing said local stability analysis determines a stability neighborhood for each of said subset of said sample pixels;

wherein said performing the local stability analysis determines a first set of sample pixels with a first neighborhood size and a second set of sample pixels with a second neighborhood size, wherein the first stability neighborhood size is greater than the second stability neighborhood size;

wherein said performing pattern matching comprises;

performing a first iteration of pattern matching using the first set of sample pixels having the first stability neighborhood size;

wherein said first iteration of pattern matching determines one or more candidate locations in the target image which possibly include the template image; and

performing a second iteration of pattern matching using the second set of sample pixels having the second stability neighborhood size at said determined one or more candidate locations in the target image.

41. The memory medium of claim 40, wherein said performing the local stability analysis for each of said at least a subset of said sample pixels comprises:

for each sample pixel, finding a neighborhood around the sample pixel where the value of the sample pixel correlates highly with the template image pixel values in the neighborhood.

42. The memory medium of claim 40, wherein said performing the pattern matching utilizing the first stability neighborhood size includes using a first step size, and wherein the performing pattern matching using the second stability neighborhood size utilizes a second step size, wherein said first step size is greater than said second step size.

43. The memory medium of claim 42, wherein said first step size corresponds to said first stability neighborhood size and wherein said second step size corresponds to said second stability neighborhood size.

44. The memory medium of claim 31, wherein the program instructions are further executable to implement:

receiving the target image after said sampling the template image, wherein said performing pattern matching is performed in response to receiving the target image, wherein said pattern matching is performed substantially in real time after receiving the target image.