Method for partitioning a pattern into optimized sub-patterns

• US 8,081,820 B2
• Filed: 07/22/2003
• Issued: 12/20/2011
• 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): Mehta, Bhavesh M
• Assistant Examiner(s): Strege, John B
• Application Number:
  US10/625,201
• Publication Number:
  US 20050117801A1
• Time in Patent Office: 3,073 Days
• Field of Search: 382/173, 382/181, 382/190, 382/209, 382/224, 382/225
• US Class Current: 382/173
• 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 each candidate partition is scored using a scoring function based on characteristics of a sub-pattern derived therefrom and wherein the characteristics of the sub-pattern includes an overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern;

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

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

providing an image; and

extracting a list of features from the image.

4. The method of claim 3, wherein extracting a list of features from the images includes:

sampling the image so as to provide a regular array of pixels.

5. The method of claim 3, wherein extracting a list of features from the images includes:

using an edge extraction method to provide an edge image; and

sampling the edge image to provide a plurality of edge feature points.

6. The method of claim 5, wherein each edge feature point includes the angle of the edge at that edge feature point.

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

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

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

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

providing a pre-generated list of features.

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

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

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

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

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

16. The method of claim 15, wherein building a weighted graph using the list of features of the pattern includes:

fully connecting the feature points to make a graph; and

setting the weights on each link.

17. The method of claim 15, wherein building a weighted graph using the list of features of the pattern includes:

sparsely connecting the feature points to make a graph; and

setting the weights on each link.

18. The method of claim 16, wherein the weights on each link are based on the distance between each pair of feature points.

19. The method of claim 18, wherein weights decrease as the distance between feature points increases.

20. The method of claim 16, wherein the weights on each link are based on at least one of similarity of angle and similarity of magnitude.

21. The method of claim 16, wherein the weights on each link are based on values associated with the feature points of the pattern.

22. The method of claim 16, wherein the weights on each link are determined such that:

larger weights represent a pair of features that tend to be together in the same sub-lists of features; and

smaller weights indicate a pair of features that can be included in different sub-lists of features.

23. The method of claim 15, wherein partitioning the weighted graph to generate candidate partitions includes:

dividing the weighted graph into two sub-graphs, one of which may be empty; and

converting the two sub-graphs into two sub-lists of features.

24. The method of claim 15, wherein partitioning the weighted graph to generate candidate partitions includes:

partitioning the weighted graph using a “

normalized cut”

method to generate candidate partitions.

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

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

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

28. The method of claim 1, wherein in generating a set of candidate partitions using the list of features of the pattern, at least one feature of the pattern appears on a plurality of sub-lists of features of the pattern.

29. The method of claim 1, wherein characteristics of the sub-pattern includes:

spatial coherence of the features corresponding to the sub-pattern.

30. The method of claim 1, wherein characteristics of the sub-pattern includes:

overall spatial size of the area spanned by the feature points corresponding to the sub-pattern.

31. The method of claim 30, wherein the area spanned by the feature points is represented by the smallest bounding box that includes all the feature points.

32. The method of claim 1, wherein characteristics of the sub-pattern includes:

the number of feature points in the sub-pattern.

33. The method of claim 1, wherein characteristics of the sub-pattern includes:

the total amount of weight in links “

cut”

by the partition algorithm to create the sub-pattern.

34. The method of claim 1, wherein characteristics of the sub-pattern includes:

spatial coherence of the features corresponding to the sub-pattern;

overall spatial size of the area spanned by the feature points corresponding to the sub-pattern;

the number of feature points in the sub-pattern;

the total amount of weight in links “

cut”

by the partition algorithm to create the sub-pattern; and

the overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern.

35. The method of claim 1, wherein the overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern depends on;

the search algorithm used.

36. The method of claim 1, wherein the overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern depends on;

degeneracy of the features of a sub-pattern.

37. The method of claim 1, wherein the overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern depends on;

redundancy of the sub-pattern within the original pattern.

38. The method of claim 1, wherein determining a best-scoring partition among the set of candidate partitions includes:

using a partition score threshold.

39. The method of claim 38, wherein the partition score threshold is settable.

40. The method of claim 38, wherein the partition score threshold is predetermined.

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

42. The method of claim 38, 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.

43. A method 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 comprising:

representing the pattern as a plurality of feature points;

generating candidate partitions of the plurality of feature points;

scoring the candidate partitions by examining characteristics of each potential sub-pattern of each candidate partition, wherein each candidate partition is scored using a scoring function based on characteristics of a sub-pattern derived therefrom and wherein the characteristics of the sub-pattern includes an overall “

suitability”

of the sub-pattern used as a search pattern applied to the original pattern;

selecting the highest-scoring partition;

applying it to the plurality of feature points so as to create one or more sub-pluralities of feature points.

44. The method of claim 43, wherein the sub-pluralities of feature points are used as sub-patterns by an image search method that is adapted to use pluralities of feature points.

45. The method of claim 43, wherein the characteristics of each potential sub-pattern of each candidate partition include:

area, number of feature points, and suitability of the sub-pattern for use with a particular search method.