Methods and systems for detecting road curbs

• US 9,285,230 B1
• Filed: 12/20/2013
• Issued: 03/15/2016
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Silver, David Harrison, Ferguson, David Ian
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): Patel, Shardul
• Application Number:
  US14/135,818
• Time in Patent Office: 816 Days
• Field of Search: 701/1, 701/301, 701/41, 701 22- 28, 701/400, 382/103, 382/104, 382/406, 382/107, 356/4.01, 356/4.08
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01S 13/86 Combinations of radar systems with non-radar systems, e.g. sonar, direction finder
• CPC Class Codes: G01S 13/865 Combination of radar systems with lidar systems
• CPC Class Codes: G01S 13/867 Combination of radar systems with cameras
• CPC Class Codes: G01S 13/89 for mapping or imaging
• CPC Class Codes: G01S 13/931 of land vehicles
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G01S 2013/93273 on the top of the vehicles
• CPC Class Codes: G01S 2013/93275 in the bumper area
• CPC Class Codes: G01S 2013/93277 in the lights
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

Methods and systems for detecting road curbs are described herein. A vehicle'"'"'s computing system may receive point clouds collected in an incremental order as the vehicle navigates a path. The point clouds may include data points representative of the vehicle'"'"'s environment at a given timepoint and include associated position information indicative of the vehicle'"'"'s position at the timepoint. Based on the associated position information in the point clouds, the computing system may process the point clouds into a dense point cloud representation and may determine features of the representation. The computing system may provide the features to a classification system that is configured to output an estimate of whether the features are representative of a road curb. Based on the output of the classification system, the computing system may determine whether the given data points represent one or more road curbs in the vehicle'"'"'s environment.

Claims

1. A method of detecting a road curb in an environment, the method comprising:

receiving a plurality of point clouds collected in an incremental order as a vehicle navigates a path, wherein a given point cloud comprises data points representative of the environment of the vehicle at a given timepoint and has associated position information indicative of a position of the vehicle at the given timepoint;

based on respective associated position information of the plurality of point clouds, processing, by a computing device, the plurality of point clouds into a dense point cloud representation;

identifying, using the dense point cloud representation, given data points having a distribution indicative of a physical structure of a potential road curb;

determining features using the given data points of the dense point cloud representation for determination of whether the given data points correspond to one or more road curbs in the environment, wherein the features include;

an elevation profile indicating a height and a slope of data points of the distribution relative to a ground level of the environment; and

an angle of incidence of a collection of the given data points;

providing the features to a classification system that is configured to output an estimate of whether the features are representative of a road curb; and

based on an output of the classification system, determining whether the given data points represent one or more road curbs in the environment of the vehicle.

2. The method of claim 1, wherein determining the slope of data points of the distribution comprises:

configuring a local plane to fit to the data points;

determining a slope of the local plane fit to the data points; and

based on the slope of the local plane, determining the slope of the data points, wherein the slope is indicative of a quality level associated with the local plane fit to the data points.

3. The method of claim 1, further comprising:

determining a second slope of a road in the environment of the vehicle, wherein the vehicle is navigating on the road;

performing a comparison between the slope of the given data points and the second slope of the road; and

based on the comparison, determining if the given data points represent one or more road curbs.

4. The method of claim 1, further comprising:

determining if the slope of the given data points is within a threshold variance of a horizontal slope; and

based on the determination, determining if the given data points represent one or more road curbs.

5. The method of claim 1, wherein determining an elevation profile of the given data points comprises analyzing respective heights of the given data points from ground level.

6. The method of claim 1, wherein the elevation profile of the given data points is indicative of whether the given data points are configured in a bimodal distribution, wherein data points configured in a bimodal distribution represent a structure of a road curb.

7. The method of claim 1, wherein the elevation profile of the given data points includes information corresponding to skewness and kurtosis associated with the given data points;

and

based on the skewness and kurtosis associated with the given data points, determining that the given data points represent a structure indicative of a road curb.

8. The method of claim 1, wherein determining an angle of incidence of a collection of the given data points comprises:

determining one or more angles between a plurality of lasers used to capture the collection of the given data points and one or more surfaces in the environment, wherein the plurality of lasers reflect off the one or more surfaces; and

estimating an angle of incidence of the given data points based on the one or more angles.

9. The method of claim 1, further comprising:

determining whether the angle of incidence of the collection of the given data points is higher than a predefined threshold; and

based on the determination, estimating that the collection of the given data points represent one or more road curbs.

10. The method of claim 1, further comprising:

receiving, via a sensor, the given data points in a plurality of laser returns;

determining a range associated with the plurality of laser returns; and

based on the range associated with the plurality of laser returns, determining the range of detection of the given data points.

11. The method of claim 1, wherein determining the range of detection of the given data points comprises:

measuring intensity of returns of a plurality of lasers used to capture the given data points, wherein measuring the intensity of the returns comprises using at least one sensor; and

based on the intensity of the returns, determining the range of detection of the given data points, wherein the range of detection is indicative of the distance between the vehicle and one or more objects that correspond to the given data points.

12. The method of claim 1, wherein determining features using the given data points of the dense point cloud representation comprises:

determining one or more features of the dense point cloud representation based on a cost associated with respective features of the one or more features, wherein the cost is based on processing power required to determine a given feature and respective features associated with a lower cost are determined prior to the respective features associated with a higher cost.

13. The method of claim 1, wherein determining the given data points comprises using one or more of computer vision, object recognition, and pose estimation to identify the given data points in the dense point cloud representation to analyze in order to detect if one or more road curbs are in the environment of the vehicle.

14. The method of claim 1, wherein processing the plurality of point clouds into a dense point cloud representation comprises:

accumulating the plurality of point clouds from a sensor of the vehicle;

aligning the data points of the plurality of point clouds into the dense point cloud representation, and

wherein determining features of the dense point cloud representation comprises determining features based on a subset of data of the dense point cloud, wherein the subset of data is indicative of data corresponding to one or more edges of a road the vehicle is traveling on.

15. The method of claim 1, wherein processing the plurality of point clouds into a dense point cloud representation comprises:

determining differences between respective point clouds in the plurality of point clouds;

processing the plurality of point clouds into the dense point cloud representation; and

modifying the dense point cloud representation to reduce the determined differences between respective point clouds in the plurality of point clouds.

16. A system comprising:

at least one processor; and

a memory having stored thereon instructions that, upon execution by the at least one processor, cause the system to perform functions comprising;

receiving a plurality of point clouds collected in an incremental order as a vehicle navigates a path, wherein a given point cloud comprises data points representative of the environment of the vehicle at a given timepoint and has associated position information indicative of a position of the vehicle at the given timepoint;

based on respective associated position information of the plurality of point clouds, processing the plurality of point clouds into a dense point cloud representation;

identifying, using the dense point cloud representation, given data points having a distribution indicative of a physical structure of a potential road curb;

determining features using the given data points of the dense point cloud representation for determination of whether the given data points correspond to one or more road curbs in the environment, wherein the features include;

an elevation profile indicating a height and a slope of data points of the distribution relative to a ground level of the environment;

an angle of incidence of a collection of the given data points;

providing the features to a classification system that is configured to output an estimate of whether the features are representative of a road curb; and

based on an output of the classification system, determining whether the given data points represent one or more road curbs in the environment of the vehicle.

17. The system of claim 16, further comprising:

providing instructions to control the vehicle based on whether the given data points represent one or more road curbs in the environment of the vehicle.

18. The system of claim 16, wherein determining features using the given data points of the dense point cloud representation comprises determining the features simultaneously.

19. A non-transitory computer readable medium having stored thereon instructions that, upon execution by a computing device, cause the computing device to perform functions comprising:

receiving a plurality of point clouds collected in an incremental order as a vehicle navigates a path, wherein a given point cloud comprises data points representative of the environment of the vehicle at a given timepoint and has associated position information indicative of a position of the vehicle at the given timepoint;

based on respective associated position information of the plurality of point clouds, processing the plurality of point clouds into a dense point cloud representation;

identifying, using the dense point cloud representation, given data points having a distribution indicative of a physical structure of a potential road curb;

determining features using the given data points of the dense point cloud representation for determination of whether the given data points correspond to one or more road curbs in the environment, wherein the features include;

an elevation profile indicating a height and a slope of data points of the distribution relative to a ground level of the environment; and

an angle of incidence of a collection of the given data points;

providing the features to a classification system that is configured to output an estimate of whether the features are representative of a road curb; and

based on an output of the classification system, determining whether the given data points represent one or more road curbs in the environment of the vehicle.

20. The non-transitory computer readable medium of claim 19, wherein the dense point cloud representation includes data points corresponding to one or more road curbs positioned on multiple sides of the vehicle.