Determining article location and orientation using three-dimensional X and Y template edge matrices

• US 6,094,501 A
• Filed: 04/30/1998
• Issued: 07/25/2000
• Est. Priority Date: 05/05/1997
• Status: Expired due to Fees

• Current Assignee: Shell Oil Company (Shell Plc)
• Original Assignee: Shell Oil Company (Shell Plc)
• Inventors: Beatty, David Andrew
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US09/070,328
• Time in Patent Office: 817 Days
• Field of Search: 382/103-106, 382/151, 382/154, 382/173, 382/199, 382/205, 382/209, 382/217-220, 382/263, 382/266, 382/278, 382/279, 382/285, 382/289, 382/291, 382/295, 382/296, 348/94, 348/95, 348/116, 348/148, 348/139, 348/42, 701/300, 345/436-439, 250/559.29, 250/559.3, 250/559.37, 250/559.38, 356/375, 356/390
• US Class Current: 382/154
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method to identify the location and orientation of an article is provided, the method comprising the steps of: obtaining an image of the article with the article having a known orientation and location relative to a camera; creating a X and Y template edge matrix from the image of the article; creating a plurality of sets of modified template edge matrices, each of the sets of modified template edge matrices being a X and Y template edge matrix with the article in a different orientation; capturing an digital visual image containing the article, the digital image being a matrix of pixels; creating X and Y article edge matrices from the matrix of pixels; quantifying difference between each of the sets of modified template edge matrices and the X and Y article edge matrices with the modified template edge matrices placed at a plurality of locations within the bounds of the article edge matrices; and identifying the location and orientation of the article as the orientation of the article represented by the set of modified template edge matrices at the location within the bounds of the X and Y article edge matrices with the minimal quantified differences between the modified template edge matrices and the X and Y article edge matrices wherein a plurality of images are obtained and three dimensional images are created of the article in both the known and the unknown position. The three dimensional images are used either in the initial matching of the article, or to verify a position and orientation of the article in the article determined from matching two dimensional images.

Claims

1. A method to identify the location and orientation of an article, the article placed on a surface, the method comprising the steps of:

obtaining an plurality of images of the article with the article having a known orientation and location relative to a camera with the plurality of images representing views from a plurality of positions;

creating X and Y template edge matrices from each of the images of the article;

creating a three dimensional X edge matrix from the plurality of X template edge matrices;

creating a three dimensional Y edge matrix from the plurality of Y template edge matrices;

creating a plurality of sets of modified three dimensional template edge matrices, each of the sets of modified three dimensional template edge matrices being a three dimensional X or Y template edge matrix with the article in a different orientation;

obtaining an plurality of images of the article with the article having a unknown orientation or location relative to a camera with the plurality of images representing views from a plurality of positions;

creating X and Y edge matrices from each of the images of the article in an unknown orientation and location;

creating a three dimensional X edge matrix from the plurality of X edge matrices with the article in an unknown orientation and location;

creating a three dimensional Y edge matrix from the plurality of Y edge matrices with the article in an unknown orientation and location;

quantifying difference between each of the sets of modified three dimensional template edge matrices and the three dimensional X and Y edge matrices of the article in an unknown orientation and location with the modified three dimensional template edge matrices placed at a plurality of locations within the bounds of the three dimensional edge matrices of the article in an unknown orientation and location; and

identifying the location and orientation of the article as the location and orientation of the article represented by the set of modified three dimensional template edge matrices with the minimal quantified differences between the modified three dimensional template edge matrices and the three dimensional X and Y edge matrices of the article in an unknown orientation and location.

2. The method of claim 1 wherein, prior to quantifying difference between the modified three dimensional X and Y template edge matrices and the three dimensional X and Y edge matrices with the article in an unknown orientation and position, portions of the three dimensional X and Y article edge matrices that are at the surface are deleted.

3. The method of claim 1 wherein three images of the article in the known and in the unknown portions and orientation are captured.

4. The method of claim 1 further comprising the steps of

smoothing the modified template edge matrices and the three dimensional X and Y edge matrices by averaging adjacent pixels and subsampling to obtain reduced matrices with a reduced number of pixels;

quantifying the difference between each of the reduced modified template edge matrices and the reduced article edge matrices with the reduced modified template edge matrices placed at a plurality of locations within the bounds of the article edge matrices; and

quantifying the difference between each of the sets of modified template edge matrices and the three dimensional X and Y edge matrices with the modified template edge matrices placed at a plurality of locations only for locations near the location and the orientation having minimum differences between the reduced matrices.

5. The method of claim 1 wherein the edge matrices are obtained by applying to the image to obtain horizontal and vertical edge matrices respectively the operators:

##EQU15## and;

##EQU16##

6. The method of claim 1 wherein a plurality of modified three dimensional template edge matrices are created with the template edge matrices transformed to represent different angles from normal to the optical axis.

7. The method of claim 1 wherein portions of the modified three dimensional template edge matrices outside of outlines of the article are ignored when quantifying the difference between each of the modified template edge matrices and the article edge matrices.

8. The method of claim 1 wherein the plurality of locations is every contiguous set of pixels within the three dimensional edge matrices within which a modified three dimensional template edge matrices will fit.

9. The method of claim 4 wherein the plurality of locations for which the difference between each of the reduced modified three dimensional template edge matrices and the reduced three dimensional edge matrices are quantified include every contiguous set of pixels within the reduced modified template edge matrices will fit.

10. The method of claim 1 wherein the edge matrices are obtained by applying to the image to obtain horizontal edge matrices by the minimum of:

and ##EQU17## and vertical edge matrices by the minimum of;

##EQU18## and ##EQU19##