System and method for generating a terrain model for autonomous navigation in vegetation

• US 7,822,266 B2
• Filed: 06/02/2006
• Issued: 10/26/2010
• Est. Priority Date: 06/02/2006
• Status: Active Grant

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Stentz, Anthony J., Courville, Aaron C., Wellington, Carl K.
• Primary Examiner(s): Bella; Matthew C
• Assistant Examiner(s): RAHMJOO, MANUCHER
• Application Number:
  US11/446,089
• Publication Number:
  US 20070280528A1
• Time in Patent Office: 1,607 Days
• Field of Search: 382/154, 382/156, 382/157, 382/159
• US Class Current: 382/154
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/188 Vegetation
• CPC Class Codes: G06V 20/38 Outdoor scenes
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

The disclosed terrain model is a generative, probabilistic approach to modeling terrain that exploits the 3D spatial structure inherent in outdoor domains and an array of noisy but abundant sensor data to simultaneously estimate ground height, vegetation height and classify obstacles and other areas of interest, even in dense non-penetrable vegetation. Joint inference of ground height, class height and class identity over the whole model results in more accurate estimation of each quantity. Vertical spatial constraints are imposed on voxels within a column via a hidden semi-Markov model. Horizontal spatial constraints are enforced on neighboring columns of voxels via two interacting Markov random fields and a latent variable. Because of the rules governing abstracts, this abstract should not be used to construe the claims.

Claims

1. A system for determining ground height, comprising:

a sensor array for producing data about a volume, said volume represented by a terrain map divided into a plurality of voxels;

a plurality of terrain modeling rules, said rules including domain information for interpreting data from said sensor array, an assumption imposed by a two-dimensional, horizontal model that ground height is smoothly varying, and an assumption imposed by a two-dimensional, horizontal model that voxels having a particular classification will cluster; and

an inference engine responsive to said sensor array, said terrain modeling rules, and vertical structural assumptions for inferring a classification for each voxel, said inference engine further producing a most likely ground height based on said inferred classifications.

2. The system of claim 1 wherein said domain information is captured in a plurality of sensor models, one for each type of sensor in said sensor array.

3. The system of claim 1 wherein said sensor array includes a camera, an infrared sensor, and a range finder.

4. The system of claim 1 wherein said vertical structural assumptions for inferring a classification include assumptions to prevent a voxel from being classified as ground if said voxel is above a voxel classified as either vegetation or free space, or an assumption that prevents a voxel from being classified as vegetation if said voxel is above a voxel classified as free space.

5. The system of claim 4 wherein said vertical structural assumptions for inferring a classification are implemented as a hidden semi-Markov model.

6. The system of claim 1 wherein said terrain modeling rules additionally impose an assumption that vegetation of a same type has a similar height above the ground.

7. The system of claim 1 wherein said assumptions imposed by said two-dimensional, horizontal models are implemented by two interacting Markov random fields.

8. The system of claim 1 wherein said inference engine infers classifications iteratively.

9. The system of claim 1 wherein said assumptions imposed by two-dimensional, horizontal models include priors for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns.

10. The system of claim 1 additionally comprising an autonomous driving system responsive to said most likely ground height.

11. A method for determining ground height, comprising:

producing sensor data about a volume, said volume represented by a terrain map divided into a plurality of voxels; and

performing on a computer the steps comprising;

providing a plurality of terrain modeling rules, said rules including domain information for interpreting said sensor data, an assumption imposed by a two-dimensional, horizontal model that ground height is smoothly varying, and an assumption imposed by a two-dimensional, horizontal model that voxels having a particular classification will cluster;

inferring a classification for each voxel based on said sensor data, said terrain modeling rules, and vertical structural assumptions; and

producing a most likely ground height based on said inferred classifications.

12. The method of claim 11 wherein said domain information is captured in a plurality of sensor models, one for each type of sensor used to produce sensor data.

13. The method of claim 12 wherein said models include a camera, an infrared sensor, and a range finder sensor models.

14. The method of claim 11 wherein said vertical structural assumptions include one of an assumption that prevents a voxel from being classified as ground if said voxel is above a voxel classified as either vegetation or free space, or an assumption that prevents a voxel from being classified as vegetation if said voxel is above a voxel classified as free space.

15. The method of claim 14 wherein said vertical structural assumptions for inferring a classification are implemented using a hidden semi-Markov model.

16. The method of claim 11 wherein said terrain modeling rules additionally impose an assumption that vegetation of a same type has a similar height above the ground.

17. The method of claim 11 wherein said assumptions imposed by said two-dimensional, horizontal models are implemented by two interacting Markov random fields.

18. The method of claim 11 wherein said inferring is carried out iteratively.

19. The method of claim 11 wherein said assumptions imposed by two-dimensional, horizontal models include priors for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns.

20. The method of claim 11 additionally inputting said most likely ground height to an autonomous driving system.