Pattern matching system and method which performs local stability analysis for improved efficiency

• US 6,219,452 B1
• Filed: 01/06/1999
• Issued: 04/17/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 H
• Application Number:
  US09/227,506
• Time in Patent Office: 832 Days
• Field of Search: 382/217, 382/218, 382/219, 382/220, 382/221, 382/161, 382/177, 382/215, 382/216, 382/209, 382/210, 707/516, 707/523, 707/526, 707/527, 707/541
• US Class Current: 382/217
• 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

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 one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, the method comprising:

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

performing a local stability analysis around 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;

performing pattern matching using the third 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 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.

3. The method of claim 1, 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.

4. The method of claim 1, wherein said performing the local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

5. The method of claim 4, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of sample pixels.

6. The method of claim 1, wherein said performing the local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels in a coarse to fine manner.

7. The method of claim 6, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller stability neighborhood sizes.

8. The method of claim 6, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller step sizes.

9. The method of claim 6, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller stability neighborhood sizes and successively smaller step sizes.

10. The method of claim 6,

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

and

wherein one or more second iterations of pattern matching are performed at said determined one or more candidate locations in the target image.

11. The method of claim 6, wherein said first iteration of pattern matching utilizes a first stability neighborhood size;

wherein each of said one or more second iterations of pattern matching utilize a smaller stability neighborhood size than said first stability neighborhood size.

12. The method of claim 11, wherein said first iteration of pattern matching utilizes a first step size;

wherein each of said one or more second iterations of pattern matching utilize a smaller step size than said first step size.

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

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

15. The method of claim 14, wherein said performing the local stability analysis includes determining said first step size and said second step size.

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

17. The method of claim 1, wherein said local stability analysis is performed for all of said sample pixels.

18. The method of claim 1, wherein said sampling the template image uses a low discrepancy sequence, wherein the low discrepancy sequence is designed to produce sample points which maximally avoid each other.

19. 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.

20. A method for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, the method comprising:

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

performing a local stability analysis around at least a subset of said sample pixels, wherein said performing said local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

performing pattern matching using the sample pixels and the target image to determine zero or more locations of the template image in the target image, wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

21. The method of claim 20, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of sample pixels.

22. The method of claim 20, wherein said performing said plurality of iterations of pattern matching uses different ones of said sets of sample pixels in a coarse to fine manner.

23. The method of claim 22, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller stability neighborhood sizes.

24. The method of claim 22, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller step sizes.

25. The method of claim 22, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with successively smaller stability neighborhood sizes and successively smaller step sizes.

26. The method of claim 22,

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

wherein one or more second iterations of pattern matching are performed at said determined one or more candidate locations in the target image.

27. The method of claim 22, wherein said first iteration of pattern matching utilizes a first stability neighborhood size;

wherein each of said one or more second iterations of pattern matching utilize a smaller stability neighborhood size than said first stability neighborhood size.

28. The method of claim 27, wherein said first iteration of pattern matching utilizes a first step size;

wherein each of said one or more second iterations of pattern matching utilize a smaller step size than said first step size.

29. The method of claim 20, 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.

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

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

32. The method of claim 20, 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.

33. The method of claim 32, wherein said performing the local stability analysis includes discarding one or more sample pixels which do not have a desired degree of stability, wherein said discarded sample pixels are not used in said pattern matching.

34. The method of claim 20,

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

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.

35. The method of claim 20, wherein said sampling the template image uses a low discrepancy sequence;

wherein the low discrepancy sequence is designed to produce sample points which maximally avoid each other.

36. A method for performing pattern matching to locate one or more instances of a template image in a target image the method comprising:

sampling the template image to determine a plurality of sample pixels which describe the template image;

determining stability neighborhood information for at least a subset of the sample pixels;

determining a step size based on said stability neighborhood information;

performing pattern matching by comparing at least a subset of the sample pixels representing the template image with portions of the target image, wherein said performing pattern matching uses said step size in stepping the at least a subset of the sample pixels across the target image.

37. The method of claim 36, wherein said determining stability neighborhood information determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said determining said step size comprises determining a plurality of step sizes for each of said sets of sample pixels;

wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

38. The method of claim 36, further comprising:

receiving the target image after said sampling the template image and after said performing the local stability analysis, 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.

39. A method for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, the method comprising:

performing a local stability analysis around at least a subset of said pixels, wherein said performing said local stability analysis determines a plurality of sets of pixels with differing stability neighborhood sizes;

performing pattern matching using the pixels and the target image to determine zero or more locations of the template image in the target image, wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of pixels.

40. The method of claim 39, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of pixels.

41. The method of claim 39, wherein said performing said plurality of iterations of pattern matching uses different ones of said sets of pixels in a coarse to fine manner.

42. The method of claim 41, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of pixels with one or more of:

successively smaller stability neighborhood sizes or successively smaller step sizes.

43. The method of claim 41,

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

wherein one or more second iterations of pattern matching are performed at said determined one or more candidate locations in the target image.

44. The method of claim 39, further comprising:

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

wherein the local stability analysis is performed around at least a subset of said sample pixels, wherein said local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said pattern matching uses the sample pixels and the target image to determine zero or more locations of the template image in the target image, wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

45. A memory medium comprising program instructions for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, wherein the program instructions are executable to implement:

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

performing a local stability analysis around 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;

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

46. The memory medium of claim 45, 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.

48. The memory medium of claim 45, wherein said performing the local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

49. The memory medium of claim 48, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of sample pixels.

47. The memory medium of 45, 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.

50. A memory medium comprising program instructions for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, wherein the program instructions are executable to implement:

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

performing a local stability analysis around at least a subset of said sample pixels, wherein said performing said local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

performing pattern matching using the sample pixels and the target image to determine zero or more locations of the template image in the target image, wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

51. The memory medium of claim 50, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of sample pixels.

52. The memory medium of claim 50, wherein said performing said plurality of iterations of pattern matching uses different ones of said sets of sample pixels in a coarse to fine manner.

53. The memory medium of claim 52, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of sample pixels with one or more of:

successively smaller stability neighborhood sizes or successively smaller step sizes.

54. The memory medium of claim 50,

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

wherein one or more second iterations of pattern matching are performed at said determined one or more candidate locations in the target image.

55. A memory medium comprising program instructions for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, wherein the program instructions are executable to implement:

performing a local stability analysis around at least a subset of said pixels, wherein said performing said local stability analysis determines a plurality of sets of pixels with differing stability neighborhood sizes;

performing pattern matching using the pixels and the target image to determine zero or more locations of the template image in the target image, wherein said performing pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of pixels.

56. The memory medium of claim 55, wherein said performing said plurality of iterations of pattern matching uses different step sizes for each of said different ones of said sets of pixels.

57. The memory medium of claim 55, wherein said performing said plurality of iterations of pattern matching uses different ones of said sets of pixels in a coarse to fine manner.

58. The memory medium of claim 57, wherein said performing said plurality of iterations of pattern matching in said coarse to fine manner uses sets of pixels with one or more of:

successively smaller stability neighborhood sizes or successively smaller step sizes.

59. The memory medium of claim 57,

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

wherein one or more second iterations of pattern matching are performed at said determined one or more candidate locations in the target image.

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

sampling the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

wherein the local stability analysis is performed around at least a subset of said sample pixels, wherein said local stability analysis determines a plurality of sets of sample pixels with differing stability neighborhood sizes;

wherein said pattern matching uses the sample pixels and the target image to determine zero or more locations of the template image in the target image, wherein said pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of sample pixels.

61. A system for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, the system comprising:

a memory which stores the template image;

an input for receiving the target image;

a processor coupled to the memory which is operable to sample the template image to produce a second plurality of sample pixels, wherein said second plurality of sample pixels is less than the first plurality of pixels in the template image;

wherein the processor is operable to perform a local stability analysis around 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 the processor is operable to perform pattern matching using the third plurality of sample pixels and the target image to determine zero or more locations of the template image in the target image.

62. A system for performing pattern matching to locate one or more instances of a template image in a target image, wherein the template image comprises a first plurality of pixels, the system comprising:

a memory which stores the template image;

an input for receiving the target image;

a processor coupled to the memory which is operable to perform a local stability analysis around at least a subset of said pixels, wherein said local stability analysis determines a plurality of sets of pixels with differing stability neighborhood sizes;

wherein the processor is operable to perform pattern matching using the pixels and the target image to determine zero or more locations of the template image in the target image, wherein said pattern matching comprises performing a plurality of iterations of pattern matching using different ones of said sets of pixels.

63. The system of claim 62, wherein, in performing said plurality of iterations of pattern matching, the processor uses different step sizes for each of said different ones of said sets of pixels.

64. The system of claim 62, wherein the processor uses different ones of said sets of pixels in a coarse to fine manner in performing said plurality of iterations of pattern matching.

65. The method of claim 64, wherein, in performing said plurality of iterations of pattern matching, the processor uses sets of pixels with one or more of:

successively smaller stability neighborhood sizes or successively smaller step sizes.