Method for partitioning a pattern into optimized sub-patterns

• US 9,147,252 B2
• Filed: 12/19/2011
• Issued: 09/29/2015
• Est. Priority Date: 07/22/2003
• Status: Active Grant

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Davis, Jason, Koljonen, Juha
• Primary Examiner(s): STREGE, JOHN B
• Application Number:
  US13/330,003
• Publication Number:
  US 20120155768A1
• Time in Patent Office: 1,380 Days
• Field of Search: 382/173, 382/181, 382/190, 382/209, 382/224, 382/225
• US Class Current: 1/1
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/426 Graphical representations

Abstract

A method is provided for dividing a pattern into a plurality of sub-patterns, each sub-pattern being adapted for use with an image search method that can provide a plurality of sub-pattern search results. The method represents the pattern as a plurality of feature points, generates candidate partitions of the plurality of feature points, and then scores the candidate partitions by examining characteristics of each potential sub-pattern of each candidate partition. The highest-scoring partition is selected, and then it is applied to the plurality of feature points, creating one or more sub-pluralities of features. The invention advantageously provides a plurality of sub-patterns where each sub-pattern contains enough information to be located with a feature-based search method, where that information has been pre-evaluated as being useful and particularly adapted for running feature-based searches.

Claims

1. A method for partitioning a pattern into optimized sub-patterns, the method comprising:

providing a list of features of the pattern;

generating a set of candidate partitions using the list of features of the pattern;

scoring each candidate partition of the set of candidate partitions by building sub-patterns using the set of candidate partitions, wherein the scoring includes analyzing degeneracy;

determining a best-scoring partition among the set of candidate partitions;

applying the best-scoring partition to the list of features so as to provide a plurality of sub-lists of features respectively representing a plurality of optimized sub-patterns.

2. The method of claim 1, wherein determining a best-scoring partition among the set of candidate partitions includes using a partition score threshold.

3. The method of claim 2, wherein the partition score threshold is settable.

4. The method of claim 2, wherein the partition score threshold is predetermined.

5. The method of claim 2, wherein the partition score threshold includes a portion that is predetermined and a portion that is settable.

6. The method of claim 2, wherein if no candidate partition has a score above the partition score threshold, then the list of features of the candidate partition is deemed to be one that cannot be usefully sub-divided.

7. The method of claim 1, wherein providing a list of features includes using at least one sub-list from the plurality of sub-lists of features generated by an earlier application of the method as the list of features of the pattern.

8. The method of claim 1, wherein providing a list of features of the pattern includes:

providing and image; and

extracting a list of features from the image.

9. The method of claim 1, wherein features of the pattern are 2D image points.

10. The method of claim 1, wherein features of the pattern are points of any dimensionality.

11. The method of claim 1, wherein providing a list of features includes:

providing an abstract pattern description; and

extracting a list of features from the abstract pattern description.

12. The method of claim 1, wherein providing a list of features includes providing a pre-generated list of features.

13. The method of claim 1, wherein generating a set of candidate partitions using the list of features of the pattern includes using a clustering algorithm.

14. The method of claim 1, wherein generating a set of candidate partitions using the list of features of the pattern includes using a spatial subdivision algorithm.

15. The method of claim 1, wherein generating a set of candidate partitions using the list of features of the pattern includes using a method that yields sub-lists that include pattern features that span an area of the pattern that is spatially small with respect to the area of the entire pattern.

16. The method of claim 1, wherein generating a set of candidate partitions using the list of features of the pattern includes using a method that provides sub-lists having pattern features that are more near to each other than to pattern features in other sub-lists.

17. The method of claim 1, wherein generating a set of candidate partitions using the list of features of the pattern includes:

building a weighted graph using the list of features of the pattern; and

partitioning the weighted graph to generate candidate partitions.

18. The method of claim 1, wherein in generating a set of candidate partitions using the list of features of the pattern, at least one candidate partition has only a single sub-list of features of the pattern.

19. The method of claim 1, wherein in generating a set of candidate partitions using the list of features of the pattern, each candidate partition has many sub-lists of features of the pattern.

20. The method of claim 1, wherein in generating a set of candidate partitions using the list of features of the pattern, some features included in the list of features of the pattern do not appear on any sub-list of features of the pattern.