Method for fast, robust, multi-dimensional pattern recognition
View Patent ↗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.
1. A method of training a model pattern for use in probe-based pattern matching, the method comprising:
providing a processor that performs the steps of:
obtaining a description of an object as at least one boundary;
selecting a subset of boundary segments along the at least one boundary for probe placement based on curvature along the subject of boundary segments; and
placing probes along the selected boundary segments.
2. The method of claim 1 , wherein each probe indicates boundary direction at a point along the at least one boundary.
3. The method of claim 1 , wherein obtaining a description of an object as at least one boundary includes:
forming a chain of boundary points.
4. The method of claim 1 , wherein a corner of a boundary is a boundary zone having positions that are not selected for probe placement.
5. The method of claim 1 , wherein placing probes along the reliable selected boundary segments includes:
placing a number of probes with predetermined spacing along the reliable selected boundary segment.
6. The method of claim 1 , wherein placing probes along the selected boundary segments includes:
placing a predetermined number of probes with equal spacing along the selected boundary segments.
7. The method of claim 6 , wherein the predetermined number of probes is 64.
8. The method of claim 6 , wherein a minimum spacing between probes is enforced.
9. The method of claim 6 , wherein a maximum spacing between probes is enforced.
10. The method of claim 6 , wherein both a minimum spacing and a maximum spacing is enforced.
11. The method of claim 1 , wherein obtaining a description of an object as at least one boundary includes:
choosing an appropriate granularity.
12. The method of claim 1 , wherein obtaining a description of an object as at least one boundary includes:
processing a training image to obtain boundary points.
13. The method of claim 1 , wherein obtaining a description of an object as at least one boundary includes:
processing a CAD description to obtain boundary points.
14. The method of claim 3 , wherein forming a chain of boundary points includes:
connecting neighboring boundary points that have consistent directions; and
organizing connected boundary points into chains of boundary points.
15. The method of claim 14 , further including:
removing short chains of boundary points.
16. The method of claim 14 , further including:
removing weak chains of boundary points.
17. The method of claim 1 , wherein selecting reliable boundary segments along the at least one boundary includes:
dividing chains of boundary points into segments of low curvature separated by corners of high curvature.
18. The method of claim 12 , wherein processing a training image to obtain boundary points includes:
detecting boundary points in the training image.
19. The method of claim 14 , wherein organizing connected boundary points into chains of boundary points includes:
for each chain, storing starting and ending points, length, total gradient magnitude, and whether the chain is open or closed.
20. The method of claim 16 , wherein removing weak chains of boundary points includes:
removing chains of boundary points having a total gradient magnitude that is below a parameter.
21. The method of claim 16 , wherein removing weak chains of boundary points includes:
removing chains of boundary points having an average gradient magnitude that is below a parameter.
22. The method of claim 1 , wherein using curvature along a boundary includes:
determining whether a direction of a boundary point differs from that of either neighbor by more than 22.5 degrees.
23. The method of claim 1 , wherein placing probes along the selected boundary segments includes:
placing a target number of probes with equal spacing along the selected boundary segments, such that probe spacing is not allowed to fall beyond predetermined limits.
24. The method of claim 23 , wherein the target number of probes is 64.
25. The method of claim 23 , wherein the predetermined limits include:
probe spacing cannot fall below 0.5 pixels; and
probe spacing cannot be greater than 4.0 pixels.
26. A method of training a model pattern for use in probe-based pattern matching, the method comprising:
providing a processor that performs the steps of:
detecting boundary points in a training image of an object;
forming a chain of boundary points so as to provide at least one boundary;
selecting only boundary segments of low curvature along the at least one boundary for probe placement; and
placing a target number of probes along the selected boundary segments.
27. The method of claim 26 , wherein each probe indicates boundary direction at a point along the at least one boundary.
28. The method of claim 26 , wherein the target number of probes is 64.
29. The method of claim 26 , wherein both a minimum and a maximum spacing between probes is enforced.
30. The method of claim 26 , wherein detecting boundary points includes:
choosing an appropriate granularity.
31. The method of claim 26 , wherein detecting boundary points in a training image of an object is replaced by:
processing a CAD description of an object to obtain boundary points.
32. The method of claim 26 , wherein forming a chain of boundary points includes:
connecting neighboring boundary points that have consistent directions; and
organizing connected boundary points into chains of boundary points.
33. The method of claim 32 , further including:
removing weak chains of boundary points.
34. The method of claim 33 , wherein removing weak chains of boundary points includes:
removing chains of boundary points having an average gradient magnitude that is below a parameter.
35. The method of claim 1 wherein the step of selecting boundary segments includes selecting less than all boundary segments.
36. The method of claim 1 wherein the step of selecting boundary segments includes selecting boundary segments of low curvature and rejecting boundary segments of high curvature.
37. A method of training a model pattern for use in probe-based pattern matching, the method comprising:
providing a processor that performs the steps of:
obtaining a description of an object as at least one boundary wherein the boundary includes a plurality of boundary portions;
selecting a subset of the plurality of boundary portions as selected boundary segments where the subset includes less than all of the plurality of boundary portions; and
placing probes along the selected boundary segments.
38. A computer program product, tangibly embodied in a non-transitory computer readable medium, the computer program product comprising instructions being operable to cause a data processing apparatus to:
obtain a description of an object as at least one boundary;
select a subset of boundary segments along the at least one boundary for probe placement based on curvature along the subject of boundary segments; and
place probes along the selected boundary segments.
39. The product of claim 38 , wherein a corner of a boundary is a boundary zone having positions that are not selected for probe placement.
40. The product of claim 38 , further comprising:
removing short chains of boundary points.
41. The product of claim 38 , further comprising:
removing weak chains of boundary points.
42. The product of claim 38 , wherein selecting reliable boundary segments along the at least one boundary includes:
dividing chains of boundary points into segments of low curvature separated by corners of high curvature.