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

• US 20090110301A1
• Filed: 10/22/2008
• Published: 04/30/2009
• 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
• Granted Patent: US 8,311,342 B2
• Time in Patent Office: Days
• 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 the classification of objects (16) and/or the recognition of their position and/or their orientation in space, 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, characterized in that 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.

2. A method in accordance with claim 1, wherein the cascade is processed starting from the hypothesis test with the shortest run time up to the hypothesis test with the 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 the position distribution or a property of neighbouring model surfaces points, in particular spin images, 3D shape contexts or remissions images are used as model histograms and/or wherein corresponding measurement histograms are generated from at least one part of the measurement object data points.

4. A method in accordance with claim 3, wherein the model object data are taught and/or are calculated from a CAD file and archived in a model library, and/or wherein model histograms which are equal or very similar, due to symmetries, are only stored once in the model library and using referencing or hashing to the model surface points only the reference to the corresponding model histogram is stored in each case but not the respective model histogram and/or wherein the model histograms are compressed for data reduction.

5. A method in accordance with claim 3, wherein correspondences, in particular point or polygon correspondences, are determined between model surface points and measurement surface points in that the similarity between model histograms and measurement histograms are evaluated, in particular through a distance norm or a correlation, and wherein a small proportion of correspondences with the best similarity evaluation are used for the hypothesis tests, in particular a proportion of at most 1% of a distribution of the similarity evaluation of all possible comparisons between model histograms and measurement histograms.

6. A method in accordance with claim 1, wherein the cascade of the hypotheses tests, in particular based on a RANSAC algorithm, are run through a plurality of times until either 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, wherein for each run through the cascade a hypothesis for the object class, position and orientation of the measurement object (16) is proposed, in that a subset of point correspondences, in particular three point correspondences, is randomly determined under the requirement that all point correspondences of the subset belong to the same object class and that from the position and/or the orientation belonging the point correspondences of the subject a position and orientation of the measurement object (16) are determined.

7. A method in accordance with claim 1, wherein the hypotheses tests include one or a plurality of the following methods, in particular all methods in this sequence:

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, in particular an iterative least mean square method, in which measurement object data points are brought into an optimal match with a surface grid of a measurement object, or a nearest neighbour test, where in particular the 0^th iteration of the position optimization is based on a selection of the measurement object data points.

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

recording of a measurement distance image of the measurement object (16), 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.

9. A method in accordance with claim 1, wherein hypotheses are tested in parallel in a pipeline, in that the next hypothesis is already being generated, while one or a plurality of hypotheses are still being tested and/or in that the cascade of a further hypothesis test is started, while the previous hypothesis is still being tested so that, in particular, each individual hypothesis test within a cascade can be executed in parallel on an own component, and/or in that in parallel a plurality of threads or a plurality of hypotheses are generated and tested on a plurality of components.

10. A method in accordance with claim 1, wherein the measurement object (16) is segmented in advance, in that subsets of the measurement object data points, which respectively belong to a segment, are combined and for every segment the class, position and orientation is determined, in order to classify combined measurement objects (16) or a plurality of measurement objects, arranged next to each other or above of each other.

11. A method in accordance with claim 1, wherein the measurement object data points are recorded three-dimensionally by sampling with a laser scanner or by means of a distance resolving image sensor (18) as a composite recording or through the combination of lines of a relatively moved measurement object (16), wherein the distances are determined by either a light transit time process, a light cutting process, active triangulation by the evaluation of a contrast pattern or by stereoscopy.

12. An apparatus (10) for the classification of objects (16) and/or the recognition of their position and/or their orientation in space, wherein the apparatus (10) includes a distance resolving optoelectronic receiver unit (18) for the generation of measurement object data points of a measurement object surface, a model memory (30) for storing model object data and an evaluation unit (32) which is adapted to generate from the measurement object data points hypotheses, via model object data, for the class, the position and the orientation of a measurement object (16) and to verify these hypotheses, characterized in that the evaluation unit (32) is constructed 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, 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.

13. An apparatus (10) in accordance with claim 12, wherein the evaluation unit (32) is designed to execute a method for the classification of objects (16) and/or the recognition of their position and/or their orientation in space, 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, characterized in that 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.

14. An apparatus (10) in accordance with claim 12, wherein the receiver unit (18) is a laser scanner or a stereo camera or wherein the receiver unit includes lighting, which can emit light pulses or modulated light and wherein the evaluation unit (32) is designed to determine distances from a light run time or a phase shift.

15. An apparatus in accordance with claim 12, wherein the receiver unit (18) includes a pixel resolving linear or matrix-like image sensor (20), and wherein the evaluation unit (24, 32) is adapted to determine measurement data points in a detection area three dimensionally as a composite recording or by likewise scanning of a relatively moved measurement object (16).