Method for fast, robust, multi-dimensional pattern recognition

• US 8,229,222 B1
• Filed: 12/30/2004
• Issued: 07/24/2012
• Est. Priority Date: 07/13/1998
• Status: Expired due to Fees

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Corporation
• Inventors: McGarry, E. John, Silver, William M., Hill, Matt, Foster, Willard, Wagman, Adam
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US11/028,007
• Time in Patent Office: 2,763 Days
• Field of Search: 382/118, 382/141, 382/181, 382/190, 382/197, 382/209, 382/276, 382/266, 348/92, 348/125
• US Class Current: 382/181
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

Disclosed is a method for determining the absence or presence of one or more instances of a predetermined pattern in an image, and for determining the location of each found instance within a multidimensional space. A model represents the pattern to be found, the model including a plurality of probes. Each probe represents a relative position at which a test is performed in an image at a given pose, each such test contributing evidence that the pattern exists at the pose. The method further includes a comparison of the model with a run-time image at each of a plurality of poses. A match score is computed at each pose to provide a match score surface. Then, the match score is compared with an accept threshold, and used to provide the location any instances of the pattern in the image.

Claims

1. An apparatus for determining the absence or presence of instances of a pattern in an image, and for determining the pose of each found instance, the apparatus comprising:

a training module for providing a model based on a training image, the model including a geometric description of the expected shape of the object, the geometric description including a plurality of pattern boundary points; and

a run-time module for using the model, a received list of generalized degrees-of-freedom (DOFs), and a received run-time image to provide a list of results.

2. The apparatus of claim 1, wherein the list of generalized DOFs includes nested loops that specify the order of coarse and fine scanning a search space with the generalized DOFs.

3. The apparatus of claim 2, wherein the run-time module includes a single non-virtual member function of a base class for implementing the nested loops.

4. The apparatus of claim 3, wherein the single non-virtual member function of the base class is defined to include an input parameter that is a type selected from the list of generalized DOFs.

5. The apparatus of claim 1, wherein the list of generalized DOFs specifies only non-translation degrees of freedom to be scanned.

6. The apparatus of claim 1, wherein the list of generalized DOFs specifies a nesting order of scanning non-translation degrees of freedom.

7. The apparatus of claim 1, wherein the list of generalized DOFs specifies an order in which coordinate transforms are composed to get an overall pose for all non-translation degrees of freedom.

8. The apparatus of claim 1, wherein a generalized DOF that is first on the list of generalized DOFs comprises a generalized DOF scanned in an outermost loop, and a corresponding transform comprises a first-to-be-applied transform in mapping from model coordinates to run-time image coordinates.

9. The apparatus of claim 1, wherein a generalized DOF that is last on the list of generalized DOFs comprises a generalized DOF scanned in an innermost loop, and a corresponding transform comprises a last-to-be-applied transform in mapping from model coordinates to run-time image coordinates.

10. The apparatus of claim 1, wherein each generalized DOF in the list of generalized DOFs is represented by an object oriented programming language class that is derived from an abstract base class.

11. The apparatus of claim 10, wherein the abstract base class specifies a fixed interface to any generalized DOF.

12. The apparatus of claim 10, wherein the abstract base class comprises functionality that is common to all generalized DOFs.

13. The apparatus of claim 1, wherein for each generalized DOF in the list of generalized DOFs, any functionality that is specific to a generalized DOF is specified as a virtual function in a base class.

14. The apparatus of claim 1, wherein for each generalized DOF in the list of generalized DOFs, any functionality that is specific to a generalized DOF is overridden in each derived class for a specific generalized DOF.

15. The apparatus of claim 13, wherein functionality that is specific to a generalized DOF includes a function that maps a parameter value to a coordinate transform.

16. The apparatus of claim 1, wherein for each generalized DOF in the list of generalized DOFs, data that is specific to a generalized DOF is held in data members of a base class.

17. The apparatus of claim 16, wherein data that is specific to a generalized DOF includes at least one of:

parameter limits, maximum step size, actual step size, or cyclic period value.

18. The apparatus of claim 1, wherein for each generalized DOF in the list of generalized DOFs, data specifying fixed attributes of the generalized DOF is initialized by a constructor of a derived class.

19. The apparatus of claim 18, wherein data specifying fixed attributes of the generalized DOF includes:

the cyclic period value.

20. The apparatus of claim 1, wherein the list of generalized DOFs includes three list elements having a redundant degree of freedom.

21. The apparatus of claim 20, wherein the runtime module is configured to allow a user to specify a search space by selecting one of:

holding all three list elements fixed, allowing only a first list element to vary, allowing only a second list element to vary, allowing only a third list element to vary, allowing first and second list elements to vary, allowing first and third list elements to vary, and allowing second and third list elements to vary.

22. The apparatus of claim 1, wherein each result in the list of results corresponds to an instance of the model in the received run-time image.

23. The apparatus of claim 1, wherein each result in the list of results contains a pose that maps model points to corresponding run-time image points.

24. The apparatus of claim 1, wherein each result in the list of results contains position information specifying in image coordinates the position of the origin of a coordinate system of the model at a pose corresponding to an instance of the model in the run-time image.

25. The apparatus of claim 1, wherein each result in the list of results contains a match score.

26. The apparatus of claim 1, wherein each result in the list of results contains a list of generalized DOF parameters corresponding to the list of generalized DOFs, and specifying non-translation degrees of freedom of a pose represented by the result.

27. The apparatus of claim 1 wherein the list of results includes at least two separate instances of the model in the run-time image.