Geometric pattern matching using dynamic feature combinations

• US 7,340,089 B2
• Filed: 01/10/2005
• Issued: 03/04/2008
• Est. Priority Date: 08/17/2004
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Fisher, Matthew S., Nair, Dinesh, Ramamoorthy, Subramanian, Smyth, Bruce, Kumar, Satish V.
• Primary Examiner(s): Desire; Gregory M
• Application Number:
  US11/032,423
• Publication Number:
  US 20060039601A1
• Time in Patent Office: 1,149 Days
• Field of Search: 382/103, 382/156, 382/209, 382/217, 382/159, 706/20, 706/25
• US Class Current: 382/159
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data

Abstract

A geometric pattern matching method to locate instances of a template image in a target image using a plurality of models with different feature combinations. A learning phase involves learning geometric information about the template image and creating a model for each of a plurality of different respective parent features. Each model comprises a relationship tree from the respective parent feature to one or more other child features, and hence each model may have different feature combinations. In a matching phase, the method may examine a plurality of different models to determine matches in the target image being analyzed. The matching phase may select different models dynamically based on prior matching results.

Claims

1. A computer readable memory medium storing program instructions for detecting patterns in an image, wherein the program instructions are executable to implement:

in a learning phase,

storing a template image in a memory medium;

determining a plurality of geometric features present in the template image;

creating a model for each of a plurality of respective parent features, wherein each model comprises a relationship tree from the respective parent feature to one or more other child features;

in a matching phase,

a) receiving a target image;

b) extracting first geometric features from the target image that correspond to a first parent feature in a first model;

c) matching the first parent feature to the first geometric features from the target image to determine a first one or more matches;

d) extracting second geometric features from the target image that correspond to at least one child feature in the first model;

e) matching the at least one child feature to the second geometric features from the target image;

f) updating any of the first one or more matches in response to matching the at least one child feature to the second geometric features from the target image;

(g) performing b)-f) for each of a plurality of models; and

storing information regarding one or more matches in the target image.

2. The computer readable memory medium of claim 1, wherein the order of the child features is different for each of at least a subset of respective parent features.

3. The computer readable memory medium of claim 1, wherein at least one parent feature is a child feature in a model corresponding to another parent feature.

4. The computer readable memory medium of claim 1, wherein the program instructions are further executable to implement:

performing d)-f) for each of a plurality of child features in the first model.

5. The computer readable memory medium of claim 1, wherein the program instructions are further executable to implement:

if steps d) and/or e) do not find a geometric feature from the target image that matches a respective child feature, then selecting a new model based on a second different parent feature.

6. The computer readable memory medium of claim 5, where said selecting the new model comprises selecting a previously identified child feature of the first model as the second parent feature, wherein the second parent feature is the parent feature of the new model.

7. The computer readable memory medium of claim 5, where said selecting the new model comprises selecting a previously unidentified feature as the second parent feature, wherein the second parent feature is the parent feature of the new model.

8. The computer readable memory medium of claim 5, wherein in the target image an object of interest is at least partially occluded.

9. The computer readable memory medium of claim 1, wherein the program instructions are further executable to implement:

in the learning phase, sorting the parent features into an order based on strength, wherein stronger parent features have a greater ability to distinguish and/or identify the template image.

10. The computer readable memory medium of claim 9, wherein the strength of the parent features is determined at least partially based on:

1) the geometry of the feature;

2) how well the feature was found in the image; and

3) the size of the feature.

11. The computer readable memory medium of claim 9,

wherein a first set of stronger features is used in updating one or more matches;

wherein a second set of less stronger features is used in updating a score of one or more matches.

12. The computer readable memory medium of claim 1,

wherein said matching in c) comprises, for each of one or more matches, storing match data in a respective data structure;

wherein said updating the match in f) comprises, for each of one or more matches, updating the data in the respective data structure.

13. A method for detecting patterns in an image, the method comprising:

in a learning phase,

storing a template image in a memory medium;

determining a plurality of geometric features present in the template image;

creating a model for each of a plurality of respective parent features, wherein each model comprises a relationship tree from the respective parent feature to one or more other child features;

in a matching phase,

a) receiving a target image;

b) extracting first geometric features from the target image that correspond to a first parent feature in a first model;

c) matching the first parent feature to the first geometric features from the target image to determine a first one or more matches;

d) extracting second geometric features from the target image that correspond to at least one child feature in the first model;

e) matching the at least one child feature to the second geometric features from the target image;

f) updating any of the first one or more matches in response to matching the at least one child feature to the second geometric features from the target image;

performing b)-f) for each of a plurality of models.

14. The method of claim 13, wherein the order of the child features is different for each of at least a subset of respective parent features.

15. The method of claim 13, wherein at least one parent feature is a child feature in a model corresponding to another parent feature.

16. The method of claim 13, further comprising:

performing d)-f) for each of a plurality of child features in the first model.

17. The method of claim 13, further comprising:

If steps d) and/or e) do not find a geometric feature from the target image that matches a respective child feature, then selecting a new model based on a second different parent feature.

18. The method of claim 17, where said selecting the new model comprises selecting a previously identified child feature of the first model as the second parent feature, wherein the second parent feature is the parent feature of the new model.

19. The method of claim 17, where said selecting the new model comprises selecting a previously unidentified feature as the second parent feature, wherein the second parent feature is the parent feature of the new model.

20. The method of claim 17, wherein in the target image an object of interest is at least partially occluded.

21. The method of claim 13, further comprising:

in the learning phase, sorting the parent features into an order based on strength, wherein stronger parent features have a greater ability to distinguish and/or identify the template image.

22. The method of claim 21, wherein the strength of the parent features is determined at least partially based on:

1) the geometry of the feature;

2) how well the feature was found in the image; and

3) the size of the feature.

23. The method of claim 21,

wherein a first set of stronger features is used in updating one or more matches;

wherein a second set of less stronger features is used in updating a score of one or more matches.

24. The method of claim 13,

wherein said matching in c) comprises, for each of one or more matches, storing match data in a respective data structure;

wherein said updating the match in f) comprises, for each of one or more matches, updating the data in the respective data structure.