Object and ground segmentation from a sparse one-dimensional range data

• US 9,097,804 B1
• Filed: 07/16/2014
• Issued: 08/04/2015
• Est. Priority Date: 07/23/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Silver, David Harrison, Ferguson, David Ian Franklin
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US14/332,498
• Time in Patent Office: 384 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: B60W 40/076 Slope angle of the road
• 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/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/931 of land vehicles
• CPC Class Codes: G01S 2013/9316 combined with communication equipment with other vehicles or with base stations

Abstract

Methods and systems for object and ground segmentation from a sparse one-dimensional range data are described. A computing device may be configured to receive scan data representing points in an environment of a vehicle. The computing device may be configured to determine if a test point in the scan data is likely to be an obstacle or ground by comparing the point to other points in the scan data to determine if specific constraints are violated. Points that do not pass these tests are likely to be above the ground, and therefore likely belong to obstacles.

Claims

1. A method comprising:

receiving, at a computing device of a vehicle, scan data representing a plurality of points in an environment of the vehicle, the plurality of points being associated with a ground and one or more objects on or proximate to the ground;

determining, using the scan data, a horizontal distance between a first point of the plurality of points and a second point of the plurality of points;

determining, using the scan data, a vertical distance between the first point and the second point;

for the horizontal distance being smaller than a threshold horizontal distance, making a comparison between the vertical distance and a threshold vertical distance; and

based on an output of the comparison indicating that the vertical distance is greater than the threshold vertical distance, determining that the second point is unassociated with the ground and is a candidate object point that represents a given point on the one or more objects.

2. The method of claim 1, further comprising:

for the vertical distance being less than the threshold vertical distance, determining that the second point is a candidate ground point.

3. The method of claim 1, further comprising

for the horizontal distance being greater than a threshold horizontal distance, determining a slope of a line connecting the first point and the second point;

making a comparison between the slope and a predetermined slope for the ground; and

based on an output of the comparison indicating the slope being within a threshold slope value from the predetermined slope, determining that the second point is a candidate ground point associated with the ground and unassociated with the one or more objects.

4. The method of claim 3, further comprising:

based on an output of the comparison indicating the slope is different from the predetermined slope by an amount greater than the threshold slope value, determining that the second point is unassociated with the ground and is a candidate object point that represents a given point on the one or more objects.

5. The method of claim 1, wherein the scan data further comprises range information indicative of respective horizontal distances between given points of the plurality of points and height information indicative of respective vertical distances between the given points of the plurality of points.

6. The method of claim 5, further comprising:

determining, based on the range information and the height information, that a given point above an adjacent point and closer to the vehicle than the adjacent point is unassociated with the ground and is associated with the one or more objects.

7. The method of claim 1, wherein the scan data corresponds to light emitted from a light detection and ranging (LIDAR) device and reflected from the ground and the one or more objects.

8. The method of claim 1, wherein the scan data comprises pixels of an image captured by an image-capture device coupled to the vehicle and depicting the ground and the one or more objects.

9. The method of claim 1, wherein the scan data comprises one-dimensional data that represents a column of pixels in an image, a row of pixels in the image, or a laser scan line.

10. The method of claim 1, wherein the computing device is configured to control the vehicle in an autonomous operation mode, the method further comprising:

providing, by the computing device, instructions to control the vehicle based on determining candidate ground points, wherein providing the instructions comprises determining a driving decision for the vehicle.

11. The method of claim 1, wherein determining that the second point is a candidate object point comprises determining that the second point is a candidate object point in real-time.

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

receiving scan data representing a plurality of points in an environment of a vehicle, the plurality of points being associated with a ground and one or more objects on or proximate to the ground;

determining, using the scan data, a horizontal distance between a first point of the plurality of points and a second point of the plurality of points;

determining, using the scan data, a vertical distance between the first point and the second point;

for the horizontal distance being smaller than a threshold horizontal distance, making a comparison between the vertical distance and a threshold vertical distance; and

based on an output of the comparison indicating that the vertical distance is greater than the threshold vertical distance, determining that the second point is unassociated with the ground and is a candidate object point that represents a given point on the one or more objects.

13. The non-transitory computer readable medium of claim 12, wherein the functions further comprise:

for the vertical distance being less than the threshold vertical distance, determining that the second point is a candidate ground point.

14. The non-transitory computer readable medium of claim 12, wherein the functions further comprise:

for the horizontal distance being greater than a threshold horizontal distance, determining a metric indicative of a slope of a line connecting the first point and the second point;

making a comparison between the metric indicative of the slope and a corresponding metric indicative of a predetermined slope for the ground; and

based on an output of the comparison indicating that the metric is within a threshold slope value from the corresponding metric, determining that the second point is a candidate ground point associated with the ground and unassociated with the one or more objects.

15. The non-transitory computer readable medium of claim 14, wherein the functions further comprise:

based on an output of the comparison indicating that the metric is different from the corresponding metric by an amount greater than the threshold slope value, determining that the second point is unassociated with the ground and is a candidate object point that represents a given point on the one or more objects.

16. The non-transitory computer readable medium of claim 12, wherein the scan data comprises one-dimensional data that represents a column of pixels in an image, a row of pixels in the image, or a laser scan line.

17. The non-transitory computer readable medium of claim 12, wherein the functions further comprise:

providing control instructions to control the vehicle in an autonomous operation mode based on determining candidate ground points, wherein the function of providing the instructions comprises determining a driving decision for the vehicle.

18. A system, comprising:

at least one processor; and

data storage comprising instructions that, when executed by the at least one processor, cause the system to perform functions comprising;

receiving scan data representing a plurality of points in an environment of a vehicle, the plurality of points being associated with a ground and one or more objects on or proximate to the ground;

determining, using the scan data, a horizontal distance between a first point of the plurality of points and a second point of the plurality of points;

determining, using the scan data, a vertical distance between the first point and the second point;

for the horizontal distance being smaller than a threshold horizontal distance, making a comparison between the vertical distance and a threshold vertical distance; and

based on an output of the comparison indicating that the vertical distance is greater than the threshold vertical distance, determining that the second point is unassociated with the ground and is a candidate object point that represents a given point on the one or more objects.

19. The system of claim 18, wherein the functions further comprise:

for the vertical distance being less than the threshold vertical distance, determining that the second point is a candidate ground point.

20. The system of claim 18, further comprising:

a light detection and ranging (LIDAR) device coupled to the vehicle; and

an image-capture device coupled to the vehicle, wherein the scan data comprises;

(i) a one-dimensional line scan data that corresponds to light emitted from the LIDAR device and reflected from the ground and the one or more objects, or (ii) pixels of an image captured by the image-capture device and depicting the ground and the one or more objects.