Method for fast, robust, multi-dimensional pattern recognition
First Claim
1. In a search tool for finding instances of a pattern in an image, a method for specifying a generalized non-translational degree of freedom (DOF), the method comprising the steps of:
- receiving a function that maps a value of a DOF parameter to a two-dimensional (2D) coordinate transform value in accordance with the generalized non-translational DOF;
specifying a low end of a range of values of the DOF parameter to be searched;
specifying a high end of a range of values of the DOF parameter to be searched;
using a data processing device to determine a step size of the DOF parameter to be searched; and
using the data processing device to identify a start of a range of the DOF parameter to be searched.
4 Assignments
0 Petitions
Accused Products
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.
255 Citations
49 Claims
-
1. In a search tool for finding instances of a pattern in an image, a method for specifying a generalized non-translational degree of freedom (DOF), the method comprising the steps of:
-
receiving a function that maps a value of a DOF parameter to a two-dimensional (2D) coordinate transform value in accordance with the generalized non-translational DOF; specifying a low end of a range of values of the DOF parameter to be searched; specifying a high end of a range of values of the DOF parameter to be searched; using a data processing device to determine a step size of the DOF parameter to be searched; and using the data processing device to identify a start of a range of the DOF parameter to be searched. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A data processing device, comprising a non-transitory computer readable medium storing a search tool computer program, for finding instances of a pattern in an image, the computer program configured to receive a generalized non-translational degree of freedom (DOF) object, the object comprising:
a low end of a range of values of the DOF parameter to be searched;
a high end of a range of values of the DOF parameter to be searched;
a start of a range of the DOF parameter to be searched;
a step size of the DOF parameter to be searched;
a function, implemented on the data processing device, that maps a value of the DOF parameter to a two-dimensional (2D) coordinate transform value, the DOF parameter changing in value in accordance with the generalized non-translational degree of freedom (DOF).- View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41)
-
42. In a pattern search tool computer program product, the 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:
-
compute a model of a two-dimensional pattern to be found based on a training image of an example pattern having a similar shape as the pattern to be found and based on a range of values of the DOF parameter to be searched, the model comprising a set of model points lying along contours of the pattern; and compute a step size of the DOF responsive to the model points, wherein the computing comprises computing a distance value responsive to the relative position of a plurality of the model points; computing the step size responsive to the distance value; and modifying the step size when there are not an integer number of steps over the range of values of the DOF to a modified step size selected to produce an integer number of steps over the range of values of the DOF. - View Dependent Claims (43, 44, 45, 46, 47)
-
-
48. A search tool apparatus for finding instances of a pattern in an image that computes a step size of a non-translational degree of freedom (DOF) having a range of values for the DOF to be searched, the apparatus comprising:
-
a model module to analyze a training image to produce a model of the pattern to be found, the training image containing an example pattern of similar shape to the pattern to be found, the model comprising a set of model points lying along contours of the pattern; step size module to analyze the model points and compute, responsive to the analysis, a step size of the DOF, wherein the analysis comprises computing a distance value responsive to the relative position of a plurality of the model points; computing the step size responsive to the distance value; and modifying the step size to get an integer number of steps over the range when the computed step size does not produce an integer number of steps over the range of values of the DOF. - View Dependent Claims (49)
-
Specification