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

• US 8,825,260 B1
• Filed: 07/23/2013
• Issued: 09/02/2014
• Est. Priority Date: 07/23/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ferguson, David Ian Franklin, Silver, David Harrison
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US13/948,207
• Time in Patent Office: 406 Days
• Field of Search: None
• US Class Current: 701/23
• 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, scan data representing a plurality of points in an environment 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;

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.

2. The method of claim 1, further comprising:

determining a vertical distance between the first point and the second point;

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

for the vertical distance being 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; and

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:

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.

4. 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.

5. The method of claim 4, wherein the computing device is configured to control a vehicle, the method 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.

6. 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.

7. The method of claim 1, wherein the scan data comprises pixels of an image depicting the ground and the one or more objects.

8. 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.

9. The method of claim 1, wherein the computing device is configured to control a 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.

10. The method of claim 1, further comprising:

determining a vertical distance between the first point and the second point; and

determining, for the horizontal distance being less than the threshold horizontal distance and the vertical distance being greater than a threshold vertical distance, that both the first point and the second point are candidate object points unassociated with the ground.

11. The method of claim 1, wherein determining that the second point is a candidate ground point comprises determining that the second point is a candidate ground 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 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;

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 of the line 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 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.

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

determining a vertical distance between the first point and the second point;

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

for the vertical distance being 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; and

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:

determining a vertical distance between the first point and the second point; and

determining, for the horizontal distance being less than the threshold horizontal distance and the vertical distance being greater than a threshold vertical distance, that both the first point and the second point are candidate object points unassociated with the ground.

15. 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.

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

providing 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.

17. The non-transitory computer readable medium of claim 16, wherein determining candidate ground points comprises determining the candidate ground points in real-time.

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 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;

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 of the line 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 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.

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

based on an output of the comparison indicating the metric indicative of the slope of the line is different from the corresponding metric indicative of 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.

20. The system of claim 18, wherein the scan data comprises a one-dimensional line scan data that corresponds to light emitted from a light detection and ranging device and reflected from the ground and the one or more objects.