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 for running a probe-based system at high speed on a digital computer, the method comprising:
providing a computer programmed to perform the steps of:
converting probe information of a probe, including probe position represented as a real 2-vector into compiled probe information of the probe including a mapped image pixel address offset represented as a single integer.
2. The method of claim 1 , wherein the probe information is represented by a probe data set including:
probe position;
probe direction; and
probe weight.
3. The method of claim 2 , wherein probe position is in pattern coordinates.
4. The method of claim 2 , wherein probe direction is in pattern coordinates.
5. The method of claim 2 , wherein probe direction is expected gradient direction.
6. The method of claim 2 , wherein probe direction is a binary angle.
7. The method of claim 2 , wherein probes of zero weight are not used.
8. The method of claim 1 , wherein the compiled probe information is represented by a compiled probe data set including:
offset;
direction; and
weight.
9. The method of claim 8 , wherein the offset is a pixel address offset of the probe in a gradient magnitude image and a gradient direction image.
10. The method of claim 8 , wherein direction is a binary angle.
11. The method of claim 8 , wherein the direction is an expected gradient (boundary) direction, mapped to image coordinates.
12. The method of claim 8 , wherein the weight is the probe weight copied from the probe data set.
13. The method of claim 8 , wherein the weight is a scaled integer converted from a real number.
14. The method of claim 1 , wherein converting probe information of a probe into compiled probe information of the probe includes:
using as inputs: a coordinate transformation, and a rectangle to be set to a minimum enclosing rectangle of the pixel offsets of the compiled probes.
15. The method of claim 14 , further including:
initializing by setting the rectangle to a null rectangle; and
setting a list of compiled probe objects to null.
16. The method of claim 14 , wherein the coordinate transformation represents a specific setting of generalized degree-of-freedom (DOF) parameters.
17. The method claim 1 , wherein converting probe information of a probe into compiled probe information of the probe includes:
for each probe in a list of probes, mapping each probe using a 2-dimensional coordinate transformation, the 2-dimensional coordinate transformation including a non-translation portion and a translation portion.
18. The method of claim 17 , wherein mapping each probe using a 2-dimensional coordinate transformation includes:
mapping probe position of each probe to image coordinates using the input coordinate transform to provide a mapped image pixel offset in X, and a mapped image pixel offset in Y;
rounding the mapped image pixel offset in X, and rounding the mapped image pixel offset in Y, to provide a rounded mapped image pixel offset in X, and a rounded mapped image pixel offset in Y; and
adding the product of the rounded mapped image pixel offset in X and a pixel address difference between columns, to the product of the rounded mapped image pixel offset in Y and a pixel address difference between the rows, to provide a compiled probe offset value.
19. The method of claim 18 , wherein mapping each probe using a 2-dimensional coordinate transformation includes:
constructing a unit vector in a gradient direction, with respect to pattern coordinates, by computing the cosine and sine of the angle of the gradient direction;
rotating the unit vector 90 degrees to get a direction along a boundary that contains the probe, thereby providing a rotated unit vector;
mapping the rotated unit vector, using the non-translation portion of the 2-dimensional coordinate transformation, to image coordinates to get a boundary direction in image coordinates, thereby providing a mapped rotated unit vector;
rotate the mapped rotated unit vector minus 90 degrees to get a direction normal to the boundary in image coordinates, thereby providing a resulting vector;
if the determinant of the non-translation portion is negative, rotate the direction normal to the boundary by 180 degrees, thereby providing a resulting vector; and
computing an angle of the resulting vector using an arctan function, to provide a compiled probe direction.
20. The method of claim 19 , wherein converting probe information of a probe into compiled probe information of the probe includes:
for each probe in a list of probes, setting a compiled weight of the probe to the original weight of the probe.
21. A method for running a probe-based system at high speed on a digital computer, the method comprising:
providing a computer programmed to perform the steps of:
converting probe information of a probe, comprising probe position represented as a floating point 2-vector, into compiled probe information of the probe comprising a mapped image pixel address offset represented as a single integer.
22. The method of claim 21 , wherein converting further comprises the step of rounding.
23. The method of claim 21 , wherein the probe information is represented by a probe data set including:
the probe position;
probe direction; and
probe weight.
24. A non-transitory and processor readable medium having stored thereon a data structure for probe-based system, the data structure comprising:
a probe object, having at least a 2-vector representation of position, and
a compiled probe object having one integer as a pixel address offset derived by altering information of the position of the probe object, such that a portion of the information of the position of the probe object is lost.
25. A computerized program apparatus, the apparatus comprising:
a memory,
a probe object, stored on the memory, having a 2-vector probe coordinates
a compiled probe object, stored on the memory, having a single integer image pixel offset address,
the computer program apparatus comprising instructions being operable in a probe-based system to cause data processing apparatus to derive the single integer image pixel offset address by converting the 2-vector probe coordinates.
26. The apparatus of claim 25 , wherein deriving the single integer image pixel offset address includes:
for each probe in a list of probes, mapping each probe using a 2-dimensional coordinate transformation, the 2-dimensional coordinate transformation comprising a non-translation portion and a translation portion.
27. The apparatus of claim 25 , wherein deriving the single integer image pixel offset address includes:
using as inputs: a coordinate transformation, and a rectangle to be set to a minimum enclosing rectangle of the pixel offsets of the compiled probes.
28. The apparatus of claim 25 , wherein the 2-vector probe coordinates are 2 vector coordinates and deriving the single integer image pixel offset address includes:
altering information of the position of the probe object, such that a portion of the information of the position of the probe object is lost.
29. The apparatus of claim 25 , wherein probe information is represented by a probe data set including: the probe position; probe direction; and probe weight.