Method of recognizing objects within two-dimensional and three-dimensional images

• US 6,026,189 A
• Filed: 11/13/1997
• Issued: 02/15/2000
• Est. Priority Date: 11/13/1997
• Status: Expired due to Fees

• Current Assignee: National Research Council Canada
• Original Assignee: National Research Council Canada
• Inventors: Greenspan, Michael
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/969,778
• Time in Patent Office: 824 Days
• Field of Search: 382/226, 382/154, 382/227, 382/286, 382/289, 382/291
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

A new method is presented for efficient and reliable object recognition within noisy, cluttered, and occluded range images. An image is captured and quantized into cells having characteristics. A tree data structure is provided wherein each node of the tree is associated with a cell. The tree is traversed according to the characteristics of each associated cell using a best-first algorithm. When a leaf node is reached, potential object poses, types and locations associated with the leaf node are stored. Once sufficient information is stored, each potential recognized object is verified using a more reliable algorithm.

Claims

1. A method of recognising objects within an image comprising the steps of:

a) providing contents of a plurality of elements within the image;

b) providing a data structure comprising a plurality of nodes, a node associated with a relative location of an element from the plurality of elements wherein some nodes are associated with at least an object pose;

c) selecting a first element from the plurality of elements, the first element having a predetermined characteristic and a first location;

d) selecting a current node from the plurality of nodes;

e) in dependence upon the data structure and a characteristic other than an extracted feature of contents of an element at an element location associated with the current node and the first element location, selecting another node as the current node;

f) if a current node has a predetermined node type, repeating steps (e) and (f); and

,

g) storing information relating to a plurality of object poses associated with at least the current node, some of the plurality of object poses relating to incorrectly recognised object poses.

2. The method of recognising objects within an image as defined in claim 1 wherein the nodes of the data structure comprise at least one of a parent node and descendant node, wherein a parent node is associated with a descendant node and a node without descendant nodes is a leaf node, wherein nodes of the data structure are associated with relative element locations, and an association between a parent node and a descendent node of the data structure is based on a characteristic of at least an element associated with the parent node.

3. A method of recognising objects within an image as defined in claim 2 wherein the step of (e) in dependence upon a characteristic of an element at the element location associated with the current node and the data structure, selecting another node as the current node comprises selecting a descendant node of the current node in dependence upon a characteristic of an element at the element location associated with the current node.

4. A method of recognising objects within an image as defined in claim 2 wherein the step of (e) in dependence upon a characteristic of an element at the element location associated with the current node and the data structure, selecting another node as the current node comprises when the current node is a leaf node, selecting a previously unselected descendant node to a previously selected node and when the current node is other than a leaf node, selecting a descendant node of the current node in dependence upon a characteristic of an element at the element location associated with the current node.

5. A method of recognising objects within an image as defined in claim 1 wherein the selection of current nodes is substantially according to a best first search algorithm.

6. A method of recognising objects within an image as defined in claim 1 comprising the step (h) verifying some of the object poses related to the stored information in dependence upon the first location.

7. A method of recognising objects within an image as defined in claim 6 wherein the step (h) is performed using at least one of a plurality of verification stages and template matching.

8. A method of recognising objects within an image as defined in claim 6 wherein the stored information comprises at least one of an object type associated with a node, an object location associated with a node and an object orientation associated with a node;

and wherein the step of verifying some of the object poses comprises the step of determining if elements within a second image of an object having a substantially same object pose are substantially similar to elements within the image.

9. A method of recognising objects within an image as defined in claim 6 wherein the step of (h) verifying some of the object poses related to the stored information in dependence upon the first location is performed upon storing the information relating to at least an object pose.

10. A method of recognising objects within an image as defined in claim 1 wherein the image is a range image and the elements are voxels and the predetermined characteristic is the presence of a surface location within a voxel.

11. A method of recognising objects within an image as defined in claim 10 wherein the characteristic comprises one of:

surface;

wherein a surface within the image intersects a voxel;

free;

wherein the voxel lies between a sensor and a surface-valued voxel;

occluded;

wherein the voxel lies beyond a surface-valued voxel from the sensor head; and

,

unknown;

wherein the voxel lies outside of the image.

12. A method of recognising objects within an image as defined in claim 1 wherein upon storing information, a previously unselected node related to a previously selected node is selected as the current node.

13. A method of recognising objects within an image as defined in claim 1 wherein the leaf nodes are associated with a plurality of relative object poses and wherein the predetermined node type is a node other than a leaf node.

14. A method of recognising objects within an image comprising the steps of:

a) providing contents of a plurality of cells within the image, the contents having a characteristic comprising one of surface wherein a surface within the image intersects the cell, free wherein the cell lies between a sensor and a surface-valued cell, occluded wherein the cell lies beyond a surface-valued cell from the sensor head, and unknown wherein the cell lies outside of the image;

b) providing a data structure comprising a plurality of nodes, a node comprising at least one of a parent node and descendant node, wherein a parent node is associated with a descendant node and a node without descendant nodes is a leaf node, wherein nodes of the data structure are associated with relative cell locations, wherein associations between nodes of the data structure are based on a characteristic of at least the cell associated with the parent node, and wherein leaf nodes are associated with at least one of object pose, object type, and object location;

c) selecting a first cell from the plurality of cells, the first cell having a predetermined characteristic;

d) selecting a current node from the plurality of nodes;

e) when the current node is a leaf node selecting a previously unselected descendant node of a previously selected node and when the current node is other than a leaf node, in dependence upon a characteristic of a cell at the cell location associated with the current node and the data structure, selecting a descendant node associated with the current node and based on the characteristic of the current node, as the current node;

f) in dependence upon the characteristic of the cell associated with the current node, determining a likelihood that the first cell is part of an image of an object to be recognised;

g) if the node has a predetermined node characteristic, storing information relating to the object, the information comprising at least one of an object type associated with the current node, an object location associated with the current node and an object orientation associated with the current node;

h) when less than a predetermined amount of information is stored and when the determined likelihood is above a threshold likelihood, repeating steps (e) to (h); and

,

i) verifying some of the objects to be recognised in dependence upon the stored information.

15. A method of recognising objects within an image as defined in claim 14 wherein the step (i) is performed using template matching.

16. A method of recognising objects within an image as defined in claim 14 wherein the step (i) is performed using a plurality of verification stages.

17. A method of recognising objects within an image as defined in claim 14 wherein the data structure is an unbalanced binary tree data structure.

18. A method of recognising objects comprising the steps of:

a) providing an image;

b) selecting a first point within the image, the point having a characteristic, and adding the point to a first set;

c) if fewer than a first number of object poses is consistent with characteristics and locations of points in the first set, performing one of adding the object poses to a second set and verifying some of the number of object poses consistent with characteristics and locations of points in the first set;

d) if at least a first number of object poses is consistent with characteristics and locations of points in the first set, determining a location of a next point based on contents of the first set and the object poses consistent with characteristics and locations of points in the first set;

e) adding the determined next point to the first set; and

,

f) until one of the first point forms part of an object pose and the first point forms part of no object pose is determined repeating steps (c) to (f).

19. A method of recognising objects within an image as defined in claim 18 comprising the step (g) verifying some of the object poses in the second set with the points in the image.

20. A method of recognising objects within an image as defined in claim 19 wherein the step (g) is performed using at least one of template matching and a plurality of verification stages.