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

• US 6,959,112 B1
• Filed: 06/29/2001
• Issued: 10/25/2005
• Est. Priority Date: 06/29/2001
• Status: Expired due to Fees

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Wagman, Adam
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Patel, Shefali
• Application Number:
  US09/895,369
• Time in Patent Office: 1,579 Days
• Field of Search: 382/181, 382/199, 382/209, 382/216, 382/151, 382/289, 382/291, 382/154
• US Class Current: 382/181
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method is provided for finding a whole pattern in an image, where at least a portion of the whole pattern falls outside the boundary of the image. The method includes, for each candidate pose of a search model of the whole pattern that results in a transformed search model that may extend beyond the boundary of the image, applying a match-quality metric to only a subset of search model features and corresponding image features, the subset being uniquely determined by the pose. The features which do not overlap the image at that pose of the model are completely excluded from the metric computation. All the relevant available information is used, using no arbitrarily hypothesized information. The higher-level strategy of the search procedure is free to consider poses where the model extends partially outside the image, and the results of each metric computation will be the most true value possible.

Claims

1. A method for finding a whole pattern, a portion of the whole pattern falling outside the boundary of an image, the method including:

for each candidate pose of a search model of the whole pattern that results in a transformed search model that falls partially outside the boundary of the image, applying a match-quality metric to only a subset of search model features and corresponding image features, the subset being uniquely determined by the pose.

2. The method of claim 1, wherein the subset of model features is determined in accordance with at least a portion of the boundary of the image.

3. The method of claim 1, wherein the subset of model features falls within an overlap region of the transformed search model and the image.

4. The method of claim 1, wherein the model features are pixels.

5. The method of claim 1, wherein the model features include edge elements.

6. A method for finding a whole pattern, at least a portion of the whole pattern falling outside the boundary of an image, the method including:

for each candidate pose of a search model of the whole pattern that results in a transformed search model that falls partially outside the boundary of the image, computing a match-quality score by considering only model features of the transformed search model that overlap the image, thereby ignoring model features of the transformed search model that fall outside the boundary of the image.

7. The method of claim 6, wherein at least some of the model features of the transformed search model that overlap the image also abut at least a portion of the boundary of the image.

8. The method of claim 6, wherein the model features are pixels.

9. The method of claim 6, wherein the model features include edge elements.

10. A method for finding a pattern which may fall partially outside a boundary of an image, the method comprising:

providing a search model, the search model having a model boundary;

providing an image, the image having an image boundary and a pattern only partially contained within the image boundary;

performing a search strategy for systematically generating a sequence of candidate poses of the search model, some of the candidate poses possibly resulting in a partial overlap of the search model and the image;

computing a match-quality metric for each candidate pose in the sequence of candidate poses to provide a plurality of metric results; and

using the plurality of metric results to determine the pose of the pattern in the image.

11. The method of claim 10, wherein computing the match-quality metric includes:

computing an overlap region in the search model and an overlap region in the image, thereby ignoring model features of the search model that fall outside the boundary of the image, using the candidate pose of the model, the model boundary, and the image boundary; and

computing the metric using the model features within the overlap region in the model, and the image features within the overlap region in the image.