Method for fast, robust, multi-dimensional pattern recognition
First Claim
1. A method for refining search results representing possible instances of a pattern in an image having a square grid of pixels and associated positions, the search results being characterized by at least one non-translation degree of freedom (DOF), the method comprising the steps of:
- using a data processing device to run a program to, for each DOF instance in a DOF list, divide a corresponding DOF step size by 2, each DOF instance including the corresponding DOF step size and a 2D coordinate transform function based on a DOF associated with the DOF instance; and
providing a refined search result, using the data processing device, for each search result to be refined in a result list, by performing a fine-scan procedure using the DOF list, 2D coordinate transform functions included in DOF instances in the DOF list, and the search result to be refined.
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.
261 Citations
31 Claims
-
1. A method for refining search results representing possible instances of a pattern in an image having a square grid of pixels and associated positions, the search results being characterized by at least one non-translation degree of freedom (DOF), the method comprising the steps of:
-
using a data processing device to run a program to, for each DOF instance in a DOF list, divide a corresponding DOF step size by 2, each DOF instance including the corresponding DOF step size and a 2D coordinate transform function based on a DOF associated with the DOF instance; and providing a refined search result, using the data processing device, for each search result to be refined in a result list, by performing a fine-scan procedure using the DOF list, 2D coordinate transform functions included in DOF instances in the DOF list, and the search result to be refined. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A method for refining search results representing possible instances of a pattern in an image having a square grid of pixels and associated positions, the search results being characterized by at least one non-translation degree of freedom (DOF), the method comprising the steps of:
-
using a data processing device to run a program to, for each DOF instance in a DOF list, divide a corresponding DOF step size by a value greater than one thereby providing a revised DOF step size, each DOF instance including the corresponding DOF step size and a 2D coordinate transform function based on a DOF associated with the DOF instance; and providing a refined search result, using the data processing device to, for each search result to be refined in a result list, by performing a fine-scan procedure using the DOF list, 2D coordinate transform functions included in DOF instances in the DOF list, modified DOF step sizes included in DOF instances in the DOF list, and the search result to be refined.
-
-
26. In a two-dimensional pattern matching data processing product for refining search results representing possible instance of a pattern in an image, the search results being characterized by at least one non-translation degree of freedom (DOF) the product tangibly embodied in a non-transitory and data processing device readable medium, the product comprising instructions being operable to cause a data processing apparatus to:
-
divide, for each DOF instance in a DOF list, a corresponding DOF step size by a value greater than one there by providing a revised DOF step size, each DOF instance including the corresponding DOF step size and a 2D coordinate transform function based on a DOF associated with the DOF instance; and provide a refined search result for each search result in a result list, by performing a fine-scan procedure using the DOF list, 2D coordinate transform functions included in DOF instances in the DOF list, modified DOF step sizes included in DOF instances in the DOF list, and the search result to be refined. - View Dependent Claims (27, 28, 29, 30, 31)
-
Specification