Vector correlation system for automatically locating patterns in an image

• US 6,023,530 A
• Filed: 11/13/1995
• Issued: 02/08/2000
• Est. Priority Date: 11/13/1995
• Status: Expired due to Term

• Current Assignee: Applied Intelligent Systems, Inc. (MKS Instruments Incorporated)
• Original Assignee: Applied Intelligent Systems, Inc. (MKS Instruments Incorporated)
• Inventors: Wilson, Stephen S.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/556,367
• Time in Patent Office: 1,548 Days
• Field of Search: 382/101, 382/209, 382/213, 382/216, 382/217-221, 382/215, 382/291
• US Class Current: 382/219
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

The present invention relates to a combined approach of image and template correlation, and vector correlation wherein edge detection and pattern searching are joined in a single operation to provide great flexibility without requiring extensive computational facilities. A template is devised from a sparse set of coordinate points that model only the important edges of an object to be located within an image. Different templates are dynamically reconstructed as an estimation of the object location within the image becomes more precise.

Claims

1. For use in an automatic image processing system, a method for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising the steps of:

determining an estimation of the object;

translating the estimation of the object into an abstract template by defining said abstract template using a number of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said estimation of the object and a corresponding edge direction passing through said coordinate point substantially perpendicular to said edge at said coordinate point;

converting the abstract template into a template based on the estimation of the object including a plurality of coordinate edge pairs, at least one coordinate edge pair formed of a pair of coordinate edge points spaced on opposite sides of the one edge of the estimation of the object;

using an equal number of vectors along substantially vertical and substantially horizontal extents of said template; and

selecting at least one vector for one edge of said estimation of the object subject to a sufficiently large angular difference between adjacent edges;

displacing said template to each of a plurality of known coordinating point locations within said image; and

correlating said template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

2. For use in an automatic image processing system, a method for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising the steps of:

determining an estimation of the object;

translating the estimation of the object into an abstract template by defining said abstract template using a number of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said estimation of the object and a corresponding edge direction passing through said coordinate point substantially perpendicular to said edge at said coordinate point;

converting the abstract template into the template including a plurality of coordinate edge pairs, at least one coordinate edge pair formed of a pair of coordinate edge points spaced on opposite sides of the one edge of the estimation of the object;

determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge directions;

positioning, for each vector of said abstract template, one of the pairs of coordinate points lying equally spaced from said coordinate point for said vector along said corresponding edge direction, a positive coordinate point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

displacing said template to each of a plurality of known coordinating point locations within said image; and

correlating said template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

3. The method as recited in claim 2, comprising the step of assigning a weight to each of said coordinate points of said template, a negative weight assigned to said negative coordinate point and a positive weight assigned to said positive coordinate point.

4. A method as recited in claim 2, wherein said displacement is no larger than one half the smallest dimension of an edge of said estimation of said object having one of said vectors.

5. The method as recited in claim 2, comprising the further steps of:

A. cutting said displacement substantially in half;

B. converting the abstract template into a revised template;

C. searching for maximum correlation at a plurality of locations surrounding said location corresponding to said correlating step; and

D. continuing steps A through C until said displacement is equal to a minimum value.

6. The method as recited in claim 2, comprising the further steps of:

A. setting a possible angle of rotation equal to an initial angle of rotation minus a range of rotation;

B. deriving a revised abstract template from said abstract template;

C. deriving a revised template from said revised abstract template;

D. displacing said revised template to each of a plurality of known coordinate point locations within said image;

E. searching for maximum correlation corresponding to one of said known coordinate point locations;

F. storing said location from step E and said corresponding angle of rotation; and

G. calculating a new angle of rotation by adding said angle of rotation plus said range of rotation.

7. The method as recited in claim 6, comprising the further steps of:

H. repeating steps B through G until said new angle of rotation is greater than said initial angle of rotation plus said range of rotation;

I. choosing said location and said angle of rotation from step F giving maximum correlation and substituting said angle of rotation for said initial angle of rotation;

K. cutting said displacement substantially in half and said range in rotation in half; and

L. repeating steps A through K until said displacement is at a minimum threshold.

8. An apparatus for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising the steps of:

determining an estimation of the object;

means for translating the estimation of the object to an abstract template;

means for defining said abstract template using a series of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said estimation of the object and a corresponding edge direction passing through said coordinate point substantially perpendicular to said edge at said coordinate point;

means for converting the abstract template into a template including a plurality of coordinate edge pairs, at least one coordinate edge pair formed of a pair of coordinate edge points spaced on opposite sides of the one edge of the estimation of the object;

means for determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge direction;

means for positioning, for each vector of said abstract template, a pair of coordinate points lying equally spaced from said coordinate point for said vector along said corresponding edge direction, a positive coordinate point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

means for displacing said template to each of a plurality of known coordinate point locations within said image; and

means for correlating said template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

9. A computer readable storage medium containing software executable by a computer to perform process steps for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, the process steps comprising:

determining an estimation of the object;

translating the estimation of the object into an abstract template by defining said abstract template using a series of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on a edge of said estimation of the object and a corresponding edge direction passing through said coordinate point substantially perpendicular to said edge at said coordinate point;

converting the abstract template into a template including a plurality of coordinate edge pairs, at least one coordinate edge pair formed of a pair of coordinate edge points spaced on opposite sides of the one edge of the estimation of the object;

determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge directions;

positioning, for each vector of said abstract template, one of the pairs of coordinate points lying equally spaced from said coordinate point from said vector along said corresponding edge direction, a positive point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

displacing said template to each of a plurality of known coordinate point locations within said image; and

correlating said template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

10. The storage medium as recited in claim 9, comprising the further process steps of:

A. cutting said displacement substantially in half;

B. converting the abstract template into a revised template;

C. searching for maximum correlation at a plurality of locations surrounding said location corresponding to said correlating step; and

D. continuing steps A through C until said displacement is equal to a minimum value.

11. The storage medium as recited in claim 9, comprising the further process steps of:

A. setting a possible angle of rotation equal to an initial angle of rotation minus a range of rotation;

B. deriving a revised abstract template from said abstract template;

C. deriving a revised template from said revised abstract template;

D. displacing said revised template to each of a plurality of known coordinate point locations within said image;

E. searching for maximum correlation corresponding to one of said known coordinate point locations;

F. storing said location from step E and said corresponding angle of rotation; and

G. calculating a new angle of rotation by adding said angle of rotation plus said range of rotation.

12. The storage medium as recited in claim 11, comprising the further process steps of:

H. repeating steps B through G until said new angle of rotation is greater than said initial angle of rotation plus said range of rotation;

I. choosing said location and said angle of rotation from step F giving maximum correlation and substituting said angle of rotation for said initial angle of rotation;

K. cutting said displacement substantially in half and said range in rotation in half; and

L. repeating steps A through K until said displacement is at a minimum threshold.

13. For use in an automatic image processing system, a method for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising the steps of:

determining a template corresponding to an estimation of the object;

translating said template to an abstract template by defining said abstract template using a number of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said template and a corresponding edge direction passing through said coordinate point perpendicular to said edge at said coordinate point, and using an equal number of vectors along substantially vertical and substantially horizontal extents of said template;

minimizing said number of said vectors;

selecting at least one vector for each different edge of said template subject to a threshold determination of a sufficiently large angular difference between adjacent edges;

converting said abstract template to a ranging template;

displacing said ranging template to each of a plurality of known coordinate point locations within said image; and

correlating said ranging template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

14. For use in an automatic image processing system, a method for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising the steps of:

determining a template corresponding to an estimation of the object;

defining an abstract template using a number of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said template and a corresponding edge direction passing through said coordinate point perpendicular to said edge at said coordinate point;

converting said abstract template into a ranging template including the further steps of;

determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge directions;

positioning, for each vector of said abstract template, a pair of coordinate points lying equally spaced from said coordinate point for said vector along said corresponding edge direction, a positive coordinate point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

displacing said ranging template to each of a plurality of known coordinating point locations within said image; and

correlating said ranging template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

15. The method as recited in claim 14, comprising the step of assigning a weight to each of said coordinate points of said ranging template, a negative weight assigned to said negative coordinate point and a positive weight assigned to said positive coordinate point.

16. The method as recited in claim 14, wherein said displacement is no larger than one half the smallest dimension of an edge of said object having one of said vectors.

17. The method as recited in claim 14, comprising the further steps of:

A. cutting said displacement in half;

B. converting the abstract template into a revised ranging template;

C. searching for maximum correlation at a plurality of locations surrounding said location corresponding to said correlating step; and

D. continuing steps A through C until said displacement is equal to a minimum value.

18. The method as recited in claim 14, comprising the further steps of:

A. setting a possible angle of rotation equal to an initial angle of rotation minus a range of rotation;

B. deriving a revised abstract template from said abstract template;

C. deriving a revised ranging template from said revised abstract template;

D. displacing said revised ranging template to each of a plurality of known coordinate point locations within said image;

E. searching for maximum correlation corresponding to one of said known coordinate point locations;

F. storing said location from step E and said corresponding angle of rotation; and

G. calculating a new angle of rotation by adding said angle of rotation plus said range of rotation.

19. The method as recited in claim 18, comprising the further steps of:

H. repeating steps B through G until said new angle of rotation is greater than said initial angle of rotation plus said range of rotation;

I. choosing said location and said angle of rotation from step F giving maximum correlation and substituting said angle of rotation from said initial angle of rotation;

K. cutting said displacement in half and said range in rotation in half; and

L. repeating steps A through K until said displacement is at a minimum threshold.

20. An apparatus for locating a position of an object within the image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, comprising:

means for determining a template corresponding to an estimation of the object;

means for translating said template to an abstract template;

means for defining said abstract template using a series of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on an edge of said template and a corresponding edge direction passing through said coordinate point perpendicular to said edge at said coordinate point;

means for determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge direction;

means for positioning, for each vector of said abstract template, a pair of coordinate points lying equally spaced from said coordinate point for said vector along said corresponding edge direction, a positive coordinate point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

means for converting said abstract template to a ranging template;

means for displacing said ranging template to each of a plurality of known coordinate point locations within said image; and

means for correlating said ranging template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

21. A computer readable storage medium containing software executable by a computer to perform process steps for locating a position of an object within an image, the image defined by a plurality of image pixels, each image pixel having a known intensity value and a known coordinate point, the process steps comprising:

determining a template corresponding to an estimation of the object;

translating said template to an abstract template by defining said abstract template using a series of vectors comprising a set of coordinate points and corresponding edge directions, each coordinate point lying on a edge of said template and a corresponding edge direction passing through said coordinate point perpendicular to said edge at said coordinate point;

converting said abstract template to a ranging template including the steps of;

determining a displacement defined from said coordinate points of said vectors and extending along corresponding edge directions; and

positioning, for each vector of said abstract template, a pair of coordinate points lying equally spaced from said coordinate point from said vector along said corresponding edge direction, a positive point corresponding to a positive value of said displacement and a negative coordinate point corresponding to a negative value of said displacement;

displacing said ranging template to each of a plurality of known coordinating point locations within said image; and

correlating said ranging template with said image at each of said locations until a maximum correlation is located, wherein the location corresponding to said maximum correlation indicates the position of the object.

22. The storage medium as recited in claim 21, comprising the further process steps of:

A. cutting said displacement in half;

B. converting said abstract template into a revised ranging template;

C. searching for maximum correlation at a plurality of locations surrounding said location corresponding to said correlating step; and

D. continuing steps A through C until said displacement is equal to a minimum value.

23. The storage medium as recited in claim 21, comprising the further process steps of:

A. setting a possible angle of rotation equal to an initial angle of rotation minus a range of rotation;

B. deriving a revised abstract template from said abstract template;

C. deriving a revised ranging template from said revised abstract template;

D. displacing said revised ranging template to each of a plurality of known coordinate point locations within said image;

E. searching for maximum correlation corresponding to one of said known coordinate point locations;

F. storing said location from step E and said corresponding angle of rotation; and

G. calculating a new angle of rotation by adding said angle of rotation plus said range of rotation.

24. The storage medium as recited in claim 23, comprising the further process steps of:

H. repeating steps B through G until said new angle of rotation is greater than said initial angle of rotation plus said range of rotation;

I. choosing said location and said angle of rotation from step F giving maximum correlation and substituting said angle of rotation for said initial angle of rotation;

K. cutting said displacement in half and said range in rotation in half; and

L. repeating steps A through K until said displacement is at a minimum threshold.