Classification of objects as well as recognition of their position and orientation in space

• US 8,311,342 B2
• Filed: 10/22/2008
• Issued: 11/13/2012
• Est. Priority Date: 10/26/2007
• Status: Active Grant

• Current Assignee: Sick AG (Sick)
• Original Assignee: Sick AG (Sick)
• Inventors: Tomm, Alexander, Erb, Frank, Schopp, Thomas
• Primary Examiner(s): Liew, Alex
• Assistant Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US12/289,215
• Publication Number:
  US 20090110301A1
• Time in Patent Office: 1,483 Days
• Field of Search: 382/224, 382/192, 382/182, 382/141, 235/454, 235/559
• US Class Current: 382/224
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

A method for the classification of objects (16) and/or the recognition of their position and/or their orientation in space is set forth, wherein measurement object data points of a measurement object surface are generated using a distance resolving receiver unit (18) and, with the aid of model object data determined in advance, hypotheses on the class, the position and/or the orientation of a measurement object (16) are proposed and verified from the measurement object data points. A plurality of different hypothesis tests can be executed cascaded in such a way that only on verification of a hypothesis through a hypothesis test is a subsequent hypothesis test carried out within this cascade, until either a hypothesis is falsified by the failure of a hypothesis test or a hypothesis is verified as a whole through a complete run through a cascade without falsification.

Claims

1. A method for, determining at least one of an object classification, an object position, and an object orientation in space, comprising the steps of:

generating measurement object data points of a measurement object surface using a distance resolving receiver unit;

using the measurement object data points in conjunction with model object data determined in advance to propose and verify a hypothesis on at least one of a class, a position, and an orientation of a measurement object,

wherein a plurality of different hypothesis tests are cascaded in such a way, that only on verification of a hypothesis through a hypothesis test is a subsequent hypothesis test carried out within this cascade, the hypothesis tests continuing until either;

a hypothesis is falsified by failure of a hypothesis test, or

a hypothesis is verified as a whole through a complete run through a cascade without falsification,

wherein the hypotheses tests include a bounding box test in which a selection of measurement object data points is tested to see whether they lie within an envelope body of the measurement object, a range image test, a position and orientation optimization test in which measurement object data points are brought into an optimal match with a surface grid of a measurement object, and a nearest neighbour test where the 0^th iteration of the position optimization is based on a selection of the measurement object data points.

2. The method in accordance with claim 1, wherein the cascade is processed starting from a hypothesis test with a shortest run time up to a hypothesis test with a longest run time.

3. A method in accordance with claim 1, wherein the model object data include model histograms which, respectively starting from a point of the model surface, describe at least one of the position distribution and a property of neighbouring model surface points.

4. A method in accordance with claim 3,

wherein the model object data are calculated from a CAD file and archived in a model library,

wherein selected model histograms are only stored once in the model library,

wherein only a reference to a corresponding model histogram is stored in memory, and

wherein the model histograms are compressed for data reduction.

5. A method in accordance with claim 3, wherein correspondences are determined between model surface points and measurement surface points by evaluating a similarity between model histograms and measurement histograms using at least one of a distance norm and a correlation, and

wherein a small proportion of correspondences with the best similarity evaluation are used for the hypothesis tests.

6. A method in accordance with claim 1, further comprising the steps of:

running the cascade of the hypotheses tests a plurality of times until at least one of a hypothesis is verified to the required accuracy, a highest run time is exceeded or an upper limit of a number of hypothesis to be tested is exceeded;

proposing, for each run through the cascade, a hypothesis for the object class, a position and an orientation of the measurement object is proposed;

randomly determining at least two subsets of point correspondences under the requirement that all point correspondences of each subset belong to the same object class; and

determining a position and orientation of the measurement object from at least one of the position and the orientation belonging the point correspondences of the at least two subsets.

7. A method in accordance with claim 1, wherein the range image test includes the following steps:

recording of a measurement distance image of the measurement object, in which the distances are in particular colour coded or grey coded;

calculation of a virtual model distance image of the model object of the hypothesis in position and orientation of the hypothesis and in particular from the perspective of the recording unit;

comparison of measurement distance images and model distance images, in particular calculation of a distance norm or a correlation and

acceptance of the hypothesis, if the comparison shows a match in the scope of a preset tolerance.

8. A method in accordance with claim 1, further comprising the steps of:

testing hypotheses in parallel in a pipeline; and

generating a next hypothesis while either;

at least one hypothesis is still being tested or

a cascade of a further hypothesis test is started while a previous hypothesis is still being tested.

9. A method in accordance with claim 1, further comprising the steps of:

segmenting the measurement object in advance;

combining subsets of the measurement object data points which respectively belong to a segments; and

determining position and orientation for every segment of the class.

10. A method in accordance with claim 1, wherein the measurement object data points are recorded three-dimensionally;

and,

wherein the distances are determined by at least one of a light transit time process, a light cutting process, active triangulation by the evaluation of a contrast pattern, and stereoscopy.

14. The method in accordance with claim 1, wherein corresponding measurement histograms are generated from at least one part of the measurement object data points.

15. The method in accordance with claim 4, wherein the reference to the corresponding model histogram is stored in memory using at least one of referencing and hashing to the model surface points.

16. The method in accordance with claim 4,

wherein the model object data are taught from a CAD file and archived in a model library,

wherein selected model histograms are only stored once in the model library,

wherein only a reference to a corresponding model histogram is stored in memory, and

wherein the model histograms are compressed for data reduction.

17. The method in accordance with claim 5, wherein a proportion of at most 1% of a distribution of the similarity evaluation of all possible comparisons between model histograms and measurement histograms is used for hypothesis tests.

18. The method in accordance with claim 8, wherein each individual hypothesis test within a cascade is executed in parallel.

19. The method in accordance with claim 8, at least one of a plurality of threads and a plurality of hypotheses are generated and tested in parallel on a plurality of components.

20. The method in accordance with claim 10, wherein the measurement object data points are recorded three-dimensionally using at least one technique selected from the group consisting of sampling with a laser scanner, using a distance resolving image sensor as a composite recording, and using a combination of lines of a relatively moved measurement object.

11. An apparatus for recognizing at least one of an object classification, an object position, and an object orientation in space, comprising:

a distance resolving optoelectronic receiver unit configured to generate measurement object data points of a measurement object surface;

a model memory configured to store model object data; and

an evaluation unit configured to generate from the measurement object data points hypotheses for at least one of the class, the position and the orientation of a measurement object using model object data and configured to verify these generated hypotheses,

wherein the evaluation unit is further configured to execute a plurality of different hypothesis tests cascaded in such a way, that only upon verification of a hypothesis by a hypothesis test is a subsequent hypothesis test carried out within this cascade, the hypothesis tests continuing until either;

a hypothesis is falsified by the failure of a hypothesis test, or

a hypothesis is verified as a whole through a complete run through the cascade without falsification,

wherein the hypotheses tests include a bounding box test in which a selection of measurement object data points is tested to see whether they lie within an envelope body of the measurement object, a range image test, a position and orientation optimization test in which measurement object data points are brought into an optimal match with a surface grid of a measurement object, and a nearest neighbour test where the 0^th iteration of the position optimization is based on a selection of the measurement object data points.

12. The apparatus in accordance with claim 11,

wherein the receiver unit is selected from the group consisting of a laser scanner, a stereo camera, and a lighting apparatus configured to emit light pulses or modulated light;

and

wherein the evaluation unit is configured to determine distances from at least one of a light run time and a phase shift.

13. The apparatus in accordance with claim 11, wherein the receiver unit includes at least one of a pixel resolving linear and a matrix-like image sensor;

and

wherein the evaluation unit is configured to determine measurement data points in a three-dimensional detection area.