Detecting principal directions of unknown environments

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

Φ

⁡

(

θ

)

=

1

2

⁢

∑

i

⁢

⁢

∑

j

∈

N

⁡

(

i

)

⁢

⁢

φ

⁡

(

θ

i

,

θ

j

)

,

where N(i) is a set of neighbors of node i, and φ is a distance measure between angles of the principal directions of neighboring nodes.

3. The method of claim 2 , using the distance measure φ(β,γ)=sin 2 (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.