Incremental recognition of a three dimensional object

• US 6,363,173 B1
• Filed: 10/14/1998
• Issued: 03/26/2002
• Est. Priority Date: 12/19/1997
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Lay, Keith, Stentz, Anthony
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/173,073
• Time in Patent Office: 1,259 Days
• Field of Search: 382/195, 382/196, 382/197, 382/198, 382/199, 382/200, 382/106, 382/291, 382/289, 382/286, 382/153, 382/154
• US Class Current: 382/195
• CPC Class Codes: E02F 9/2045 Guiding machines along a predetermined path for graders E02F3/841; machines for construction of roads E01C19/004
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

The present invention is a method and apparatus for determining the location, orientation, and dimensions of an object using range data from a scanning sensor based on data for a relatively small portion of the object. The present recognition method uses characteristics of a scanning sensor along with the geometrical characteristics of objects that typically receive loads in an earthmoving environment, such as dump trucks. The data from a single scanline provided by a scanning sensor system is processed to determine if there are discontinuities in the scanline. In the present invention, discontinuities in adjacent scanlines are assumed to be in close proximity to each other and to correspond to dominant linear features in a model of the object. The top and bottom edges of an object, such as a dump truck bed, can be located as discontinuities in a single scanline. These discontinuities are used to form possible interpretations of the object'"'"'s position and orientation. As more scanlines are received, discontinuities that are in close proximity form part of the same interpretation. Lines are also fit to the discontinuities and compared to edges or linear features in the model of an object. Geometric constraints derived from the model are used to eliminate unfeasible interpretations and to confirm feasible interpretations.

Claims

1. A method for determining the position, size, and orientation of an object having at least one linear feature based upon range data from a plurality of scanlines provided by a sensor system scanning the object, and utilizing a data processing system including a database of numerical data corresponding to at least one model having at least one linear feature, the method comprising the steps of:

(a) locating discontinuities in the scanlines as they are received;

(b) using a state table of expected features to generate a list of active interpretations of the object using the model information and the locations of the discontinuities from only partial range data of the object;

(c) evaluating the interpretations to determine the most valid interpretation which is the interpretation with the most matched features that have a minimum amount of data up to the current scanline; and

(d) calculating the position and orientation of the object using the interpretation that most closely matches the object.

2. The method as set forth in claim 1 wherein step (a) further comprises locating discontinuities in a scanline by attempting to fit line segments in the scanline range data and marking a range point as a discontinuity when the error from a line segment being fit is beyond a threshold value.

3. The method as set forth in claim 1 wherein step (a) further comprises locating discontinuities in a scanline by checking the distance between successive range data points in a scanline and labeling a point as a discontinuity when the distance exceeds a threshold.

4. The method as set forth in claim 1 wherein step (a) further comprises locating discontinuities in a scanline by detecting differences in height values of range data points in the scanline that exceed a threshold.

5. The method as set forth in claim 1 wherein generating the list of active interpretations in step (b) further comprises at least one best fit line through range data points associated with the at least one linear feature of the object consisting of a unit vector and two endpoints.

6. The method as set forth in claim 1 wherein generating the list of active interpretations in step (b) further comprises calculating the centroid for a planar region associated with the at least one linear feature of the object.

7. The method as set forth in claim 1 wherein step (c) further comprises using proximity constraints to limit the number of interpretations to compare, the proximity constraints being based on discontinuities in adjacent scanlines corresponding to the same linear feature of an object.

8. The method as set forth in claim 1 wherein step (c) further comprises using geometric constraints to limit the number of interpretations to compare.

9. An apparatus for determining the position, size, and orientation of an object having at least one linear feature comprising:

a data processing system including a data storage device and a data processor, the data storage device including range data scanlines of the object, and data corresponding to at least one model having at least one linear feature, the data processor being operable to locate discontinuities in the scanlines, generate a list of active interpretations of the object using the model database and the locations of the discontinuities, compare discontinuities with the active interpretations on a scanline by scanline basis to find the interpretation that most closely matches the object, and calculate the position and orientation of the object using the interpretation that most closely matches the object based on the data available.

10. The apparatus as set forth in claim 9 wherein the data processor is operable to locate discontinuities in a scanline by fitting line segments to range data in a scanline and marking a range point as a discontinuity when the error from a line segment being fit is beyond a threshold value.

11. The apparatus as set forth in claim 9 wherein the data processor is operable to locate discontinuities in a scanline by checking the distance between successive range data points in a scanline and labeling a point as a discontinuity when the distance exceeds a threshold.

12. The apparatus as set forth in claim 9 wherein the data processor is operable to locate discontinuities in a scanline by detecting differences in height values of range data points in the scanline that exceed a threshold.

13. The apparatus as set forth in claim 9 wherein the interpretation comprises at least one best fit line through the at least one linear feature of the object consisting of a unit vector and two endpoints.

14. The apparatus as set forth in claim 9 wherein the interpretation comprises a centroid for the range points associated with the at least one linear feature of the object.

15. The apparatus as set forth in claim 9 wherein the data processor is operable to use proximity constraints to limit the number of interpretations to compare, the proximity constraints being based on discontinuities in adjacent scanlines corresponding to the at least one linear feature of an object.

16. The apparatus as set forth in claim 9 wherein the data processor is operable to use geometric constraints to limit the number of interpretations to compare.

17. An apparatus for determining the position, size, and orientation of an object in an earthmoving environment, the object having at least one linear feature comprising:

a data processing system including a data storage device and a data processor, the data storage device including range data scanlines of the object provided by a scanning sensor system, and data corresponding to at least one model having at least one linear feature, the data processor being operable to locate discontinuities in the scanlines, generate a list of active interpretations of the object using the model database and the locations of the discontinuities, compare discontinuities with the active interpretations on a scanline by scanline basis to find the interpretation that most closely matches the object, and calculate the position and orientation of the object using the interpretation that most closely matches the object based on the data available.

18. The apparatus as set forth in claim 17 wherein the object is the bed of a dump truck.

19. The apparatus as set forth in claim 18 wherein the scanning sensor system is located at an earthmoving machine positioned adjacent the bed of the dump truck, the scanning sensor system operable to generate substantially vertical scanlines of the bed of the dump truck, the scanlines being adjacent to one another from the rear to the front of the dump truck bed.

20. An apparatus for recognizing an object and determining the position, size, and orientation of the object in a scene of the earthmoving environment, the object having at least one linear feature comprising:

a data processing system including a data storage device and a data processor, the data storage device including range data scanlines of the object provided by a scanning sensor system, and data corresponding to at least one model having at least one linear feature, the data processor being operable to simulate the scanning of the object using a model of the object, generate a state table indicating possible orientations of the object in the earthmoving environment using data from the simulated scanning, locate discontinuities in the range data scanlines, generate a list of active interpretations of the object using the model database and the locations of the discontinuities, compare discontinuities with the active interpretations to find the interpretation that most closely matches the object, and calculate the position and orientation of the object using the interpretation that most closely matches the object.

21. The apparatus as set forth in claim 20 wherein the state table is generated using geometric constraints of the object model that determine possible states that can be transitioned to from a given state.

22. The apparatus as set forth in claim 20 wherein a plurality of simulated scans of the object model are performed over a range of possible positions and orientations for the object with respect to a loading machine.

23. The apparatus as set forth in claim 20 wherein the state transitions are determined using angles between features of the object model, the length of features, proximity distance for a particular feature, and direction of the cross product of two linear features.

24. The apparatus as set forth in claim 20, wherein the determination of whether to transition to a new state is made using object model information including proximity of features in a scanline to common features in the previous state, the angle between scene features and the angle between possible model features matched with the scene features, the direction of the incremental scene features and the direction of the possible model features matched to these scene features.

25. The apparatus as set forth in claim 20 wherein the object model is scanned using a simulated sensor model having variable scanning rates.

26. The apparatus as set forth in claim 20 wherein the object model is scanned using a simulated sensor model having variable sampling resolutions.

27. The apparatus as set forth in claim 20 wherein the object model is scanned using a simulated sensor model having variable beam widths.