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

• US 20070280528A1
• Filed: 06/02/2006
• Published: 12/06/2007
• Est. Priority Date: 06/02/2006
• Status: Active Grant

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Stentz, Anthony, Wellington, Carl, Courville, Aaron
• Granted Patent: US 7,822,266 B2
• Time in Patent Office: Days
• 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 surface height, comprising:

a sensor array for producing data about a volume in which surface height is to be determined, said volume being divided into a plurality of voxels which are to be classified;

a plurality of surface modeling rules for providing domain information for interpreting data from said sensor array, for enforcing spatial constraints vertically among voxels, and for enforcing spatial constraints horizontally among columns of voxels; and

an inference engine responsive to said sensor array and said surface modeling rules so to classify each voxel, at least certain of said voxels being classified as surface.

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 surface modeling rules for enforcing spatial constraints vertically comprises a hidden semi-Markov model imposed on vertically positioned voxels.

5. The system of claim 1 wherein said surface modeling rules for enforcing spatial constraints horizontally include two interacting Markov random fields and a latent variable that interact across columns of voxels.

6. The system of claim 1 wherein said horizontal spatial constraints enforced by said surface modeling rules comprise assumptions of class continuity, surface smoothness and similarity of vegetation height.

7. The system of claim 1 wherein said classifying is carried out iteratively by said inference engine.

31. The system of claim 1 wherein said enforcing spatial constraints horizontally includes enforcing priors horizontally among columns of voxels.

8. A system for determining ground height, comprising:

a sensor array for producing data about a volume in which ground height is to be determined, said volume being divided into a plurality of voxels which are to be classified;

a plurality of terrain modeling rules, said rules including domain information for interpreting data from said sensor array, a spatial constraint for limiting the classification of vertically aligned voxels, and horizontal spatial constraints for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns; and

an inference engine responsive to said sensor array and said terrain modeling rules so to classify each voxel as one of either ground, vegetation, obstacle, or free space.

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

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

11. The system of claim 8 wherein said spatial constraint for limiting the classification of vertically aligned voxels includes one of a constraint to prevent a voxel from being classified as ground if said voxel is above a voxel classified as either vegetation or free space, or a constraint that prevents a voxel from being classified as vegetation if said voxel is above a voxel classified as free space.

12. The system of claim 11 wherein said spatial constraint is implemented as a hidden semi-Markov model.

13. The system of claim 8 wherein said horizontal spatial constraints comprise assumptions about class continuity, smoothness of ground, and similarity of vegetation height

14. The system of claim 13 wherein said assumptions about class continuity, smoothness of ground, and similarity of vegetation height are implemented by two interacting Markov random fields and a latent variable.

15. The system of claim 8 wherein said classifying is carried out iteratively by said inference engine.

32. The system of claim 8 wherein said horizontal spatial constraint includes priors for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns.

16. A method for determining surface height, comprising:

producing sensor data about a volume in which surface height is to be determined, said volume being divided into a plurality of voxels which are to be classified; and

classifying each voxel, with at least certain of said voxels being classified as surface, by applying a plurality of surface modeling rules, said surface modeling rules providing domain information for interpreting sensor data, for enforcing spatial constraints vertically among voxels, and for enforcing spatial constraints horizontally among columns of voxels.

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

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

19. The method of claim 16 wherein said surface modeling rules for enforcing spatial constraints vertically are implemented using a hidden semi-Markov model on vertically positioned voxels.

20. The method of claim 16 wherein said surface modeling rules for enforcing spatial constraints horizontally are implemented using two interacting Markov random fields and a latent variable that interact across columns of voxels.

21. The method of claim 16 wherein said horizontal spatial constraints enforced by said surface modeling rules comprise assumptions of class continuity, surface smoothness and similarity of vegetation height.

22. The method of claim 16 wherein said classifying is carried out iteratively.

33. The method of claim 16 wherein said enforcing spatial constraints horizontally includes enforcing priors horizontally among columns of voxels.

23. A method for determining ground height, comprising:

producing sensor data about a volume in which ground height is to be determined, said volume being divided into a plurality of voxels which are to be classified; and

classify each voxel as one of either ground, vegetation, obstacle, or free space by applying a plurality of terrain modeling rules, said rules including domain information for interpreting sensor data, a spatial constraint for limiting the classification of vertically aligned voxels, and horizontal spatial constraints for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns.

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

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

26. The method of claim 23 wherein said spatial constraint for limiting the classification of vertically aligned voxels includes one of a constraint that prevents a voxel from being classified as ground if said voxel is above a voxel classified as either vegetation or free space, or a constraint that prevents a voxel from being classified as vegetation if said voxel is above a voxel classified as free space.

27. The method of claim 26 wherein said spatial constraint is implemented using a hidden semi-Markov model.

28. The method of claim 23 wherein said horizontal spatial constraints comprise assumptions about class continuity, smoothness of ground, and similarity of vegetation height

29. The method of claim 28 wherein said assumptions about class continuity, smoothness of ground, and similarity of vegetation height are implemented by two interacting Markov random fields and a latent variable.

30. The method of claim 23 wherein said classifying is carried out iteratively.

34. The method of claim 23 wherein said horizontal spatial constraint includes priors for limiting the classification of voxels in one column based on the classification of voxels in neighboring columns.