Method for finding a pattern which may fall partially outside an image

#This invention relates to machine vision systems, and more particularly, to techniques for finding a pattern in an image.

#In many applications, it is necessary to determine the location or, more generally, the pose (multi-degree-of-freedom position) of an object in a scene using machine vision, and various techniques exist for performing such a search. Such techniques generally involve a method for systematically visiting a plurality of locations in an image, and at each location visited, performing a computation using a model and a match-quality metric. The match-quality metric represents the quality of the match between the model at that location (pose) in the image and the pattern in the image. For example, one commonly used match-quality metric is normalized (cross) correlation, which computes a score between equal-sized regions of two images using a particular formula, such as the formula on page 653 of Pratt, Digital Image Processing, 2nd Ed., Wiley-Interscience. A simple high-level algorithm might compute the normalized correlation metric at all translations of the model image where the model image would fit entirely within the image of the scene, and the location would be the translation at which the score was greatest.

#A limitation that is typical of many pattern location algorithms, and of normalized-correlation-based pattern location algorithms in particular, is an inability to find the correct location if the object is not entirely contained within the field of view, and thus only part of the pattern occurs in the image.

#The invention will be more fully understood from the following detailed description, in conjunction with the following figures, wherein:

#FIG. 1 is a flowchart illustrating the steps for determining a set of optimal model poses in accordance with the principles of the invention;

#FIG. 2 is a diagram illustrating the overlapping image region for each of several translation-only poses of a model;

#FIG. 1 is a flow diagram for the method of locating a pattern in an image using a model according to the present invention. The process begins with step 100, wherein some information about the model may be precomputed, although not all metrics require such precomputation. This type of precomputation is sometimes referred to as “training”. For example, when using correlation as the metric, it is typical to precompute the sum of all model pixels and the sum of the squares of all model pixels. When correlation is to be used with rotation and scale as possible degrees of freedom in the search method that selects the poses to be evaluated using the metric, one might pre-generate rotated and scaled models. For other metrics, one might also perform some sort of feature extraction, such as performing edge detection. Some metrics may not require any precomputation. For example, one can do correlation with no precomputation, but usually doing the precomputation decreases execution time at runtime.

#The process then continues with step 110, where a pose is generated for consideration. A pose is a mathematical transformation from coordinates in the model to coordinates in the image (and vice versa). If we represent coordinates in the model as (x, y) and coordinates in the image as (x′, y′), then a pose P is a function (or other mapping) where (x′, y′)=P(x, y) For example, if the pose represents a translation (x0, y0), then (x′, y′)=P(x, y)=(x+x0, y+y0)

#If the pose P represents a combination of a translation (x0, y0), rotation θ, scale S, aspect A, and shear K, then (x′, y′)=P(x, y)=M(θ, S, A, K)*(x, y)+(x0, y0) where M can be represented as a 2×2 matrix and the multiplication indicates multiplication of that matrix by the column vector (x, y), yielding x′=(S cos θ)x+AS(−sin θ−(cos θ)(tan K))y y′=(S sin θ)x+AS(cos θ−(sin θ)(tan K))y