Vector correlation system for automatically locating patterns in an image

• US 6,385,340 B1
• Filed: 01/04/2000
• Issued: 05/07/2002
• 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): CHANG, JON CARLTON
• Application Number:
  US09/477,542
• Time in Patent Office: 854 Days
• Field of Search: 382/219, 382/291, 382/181, 382/209, 382/213, 382/215, 382/216, 382/217, 382/218, 382/220, 382/221, 382/278
• US Class Current: 382/218
• 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 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 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 only where a sufficiently large angular difference exists 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.

2. The method as recited in claim 1, wherein said correlating step further includes determining whether a correlation has exceeded a predetermined threshold.

3. The method of claim 1 wherein the step of converting said abstract template into a ranging template further includes the 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 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.