Detecting principal directions of unknown environments

• US 8,060,271 B2
• Filed: 06/06/2008
• Issued: 11/15/2011
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Toyota Motor Corporation
• Original Assignee: Toyota Motor Engineering & Manufacturing North America Incorporated (Toyota Motor Corporation)
• Inventors: Dolgov, Dmitri A., Thrun, Sebastian
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US12/134,763
• Publication Number:
  US 20090306881A1
• Time in Patent Office: 1,257 Days
• Field of Search: 701/28, 701/33, 701/36, 701/200, 701/207, 701/211, 382/103, 382/204, 382/276, 348/169, 348/208.14
• US Class Current: 701/28
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 2201/0213 Road vehicle, e.g. car or truck
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle

Abstract

Apparatus and methods according to some embodiments of the present invention use a graphical model, such as a Markov random field model, to represent principal driving directions within an environment. The model has a plurality of nodes representing spatial locations within the environment, and the principal direction for each node is determined probabilistically using linear features detected within an image of the environment. Apparatus and methods according to embodiments of the present invention can be used in improved autonomous navigation systems, such as robotic vehicles.

Claims

1. A method of determining principal directions for an environment, the principal directions relating to vehicle operation within the environment, the method comprising:

forming a graphical model of the environment, the graphical model having nodes corresponding to spatial locations within the environment,

the graphical model being a Markov random field model; and

determining principal directions for the nodes using linear features detected within the environment, determining the principal directions further including

determining principal directions for nodes having at least one proximate linear feature using angular data related to the at least one proximate linear feature, and

determining principal directions for nodes not having a proximate linear feature using a potential function for change in principal direction between neighboring nodes,

the potential function being selected to obtain a smooth variation in principal directions between neighboring nodes.

2. The method of claim 1, wherein the potential function for change in principal direction between neighboring nodes has the form

3. The method of claim 2, using the distance measure φ

(β

,γ

)=sin²(2(β

−

γ

)), where β and

γ

represent angles for the principal directions of neighboring nodes.

4. The method of claim 1, the nodes representing an array of spatial coordinates within a two-dimensional image representing the environment.

5. The method of claim 1, further including detection of linear features within the environment using a sensor system located on a vehicle,

the principal directions being used to determine a trajectory of the vehicle through the environment.

6. The method of claim 1, further comprising detection of linear features within the environment using a sensor system, the detection of the linear features comprising

acquiring image data representing the environment, and

detecting linear features within the image data.

7. The method of claim 6, further comprising image processing of the image data before linear feature detection,

the image processing including threshold filtering and edge detection.

8. The method of claim 6, the sensor system including a lidar sensor.

9. The method of claim 6, the sensor system including at least one sensor selected from the group of sensors consisting of a radar sensor, an optical sensor, and an IR sensor.

10. A method of determining principal driving directions within an environment, the method comprising:

obtaining image data representing the environment;

detecting linear features within the image data;

forming a graphical model of the environment, the graphical model having a plurality of nodes corresponding to spatial locations within the environment;

determining principal directions for nodes having a proximate linear feature using angular data related to the proximate linear feature; and

assigning principal directions for nodes not having a proximate linear feature using a potential function for angular changes in principal direction between neighboring nodes,

the potential function being selected to obtain a smooth variation in principal directions between neighboring nodes.

11. The method of claim 10, further comprising using the principal directions to assist steering a vehicle through the environment.

12. The method of claim 10, the graphical model being a Markov random field model,

the nodes representing a grid of spatial coordinates within the environment,

the linear features providing local evidence of principal direction.

13. The method of claim 10, further comprising determining principal directions for nodes having a plurality of proximate linear features using a weighted average of angular data related to the plurality of proximate linear features.

14. The method of claim 13, the weighted average using linear feature length as a weighting factor.

15. An apparatus operable to assist autonomous navigation of a vehicle through an environment, the apparatus comprising;

an environment sensor supported by the vehicle; and

an electronic circuit, receiving sensor data from the environment sensor, the electronic circuit being operable to;

detect linear features within the environment, and

determine principal directions within the environment using a Markov random field model having nodes corresponding to spatial locations within the environment,

angular data related to the linear features being input into the Markov random field model,

principal directions for nodes having at least one proximate linear feature being determined using angular data related to the at least one proximate linear feature,

principal directions for nodes not having a proximate linear feature being determined using a potential function for change in principal direction between neighboring nodes, and

the potential function giving a smooth variation in principal directions between neighboring nodes.

16. The apparatus of claim 15, the environment sensor including at least one sensor selected from the group of sensors consisting of a lidar sensor, a radar sensor, an optical sensor, and an IR sensor.

17. The apparatus of claim 15, the electronic circuit comprising a processor operable to execute an algorithm,

the algorithm being operable to determine the principal directions within the environment using the Markov random field model.