Planar surface detection

1. A method comprising:

obtaining a point cloud of a scene including a plurality of points in a gravity-aligned coordinate system;

generating, based on the plurality of points, a height histogram indicative of a plurality of non-overlapping height ranges in the gravity-aligned coordinate system and a respective plurality of weights; and

generating one or more horizontal plane hypotheses based on the height histogram, wherein generating the one or more horizontal plane hypotheses includes determining that one or more weights of the height histogram is greater than a threshold and generating one or more horizontal plane hypotheses corresponding to the respective height ranges.

2. The method of claim 1 , wherein each of the plurality of points is associated with three coordinates in the gravity-aligned coordinate system, one of the three coordinates corresponding to a height of the point.

3. The method of claim 2 , wherein generating the height histogram includes, for an unpaired point of the plurality of points:

determining a height of the unpaired point based on the one of the three coordinates; and

incrementing, by an amount, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of non-overlapping height ranges including the height of the unpaired point.

4. The method of claim 2 , wherein generating the height histogram includes, for two paired points of the plurality of points:

determining a height of a line defined by the two paired point based on the one of the three coordinates of each of the two paired points;

determining a length of the line based on the others of the three coordinates of each of the two paired points; and

incrementing, by an amount scaled by the length of the line, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of height ranges including the height of the line.

5. The method of claim 4 , wherein incrementing the one of the respective plurality of weights is performed in response to determining that the line is substantially horizontal.

6. The method of claim 2 , wherein each of the plurality of points is further associated with an uncertainty.

7. The method of claim 6 , wherein generating the height histogram includes, for an unpaired point of the plurality of points:

determining a height probability distribution of the unpaired point based on the one of the three coordinates and the uncertainty; and

increasing a plurality of the respective plurality of weights of the height histogram corresponding to the height probability distribution of the point.

8. The method of claim 6 , wherein generating the height histogram includes, for two paired point of the plurality of points:

determining a height probability distribution of a line defined by the two paired points based on the one of the three coordinates and the uncertainty of each of the two paired points; and

determining a length of the line based on the others of the three coordinates of each of the two paired points; and

increasing, by an amount scaled by the length of the line, a plurality of the respective plurality of weights of the height histogram corresponding to the height probability distribution of the point.

9. The method of claim 8 , wherein increasing the plurality of the respective plurality of weights is performed in response to determining that the line is substantially horizontal.

10. The method of claim 1 , wherein generating the one or more horizontal plane hypotheses includes detecting one or more peaks in the height histogram and generating one or more horizontal plane hypotheses corresponding to the peaks.

11. The method of claim 10 , further comprising applying a non-maxima suppression algorithm to the height histogram.

12. The method of claim 1 , wherein generating the one or more horizontal plane hypotheses includes generating one or more sets of planar coefficients, each set defining a horizontal plane.

13. A device comprising:

a scene camera; and

one or more processors to:

obtain a point cloud of a scene including a plurality of points in a gravity-aligned coordinate system;

generate, based on the plurality of points, a height histogram indicative of a plurality of non-overlapping height ranges in the gravity-aligned coordinate system and a respective plurality of weights; and

generate one or more horizontal plane hypotheses based on the height histogram wherein generating the one or more horizontal plane hypotheses includes determining that one or more weights of the height histogram is greater than a threshold and generating one or more horizontal plane hypotheses corresponding to the respective height ranges.

14. The device of claim 13 , wherein each of the plurality of points is associated with three coordinates in the gravity-aligned coordinate system, one of the three coordinates corresponding to a height of the point.

15. The device of claim 14 , wherein generating the height histogram includes, for an unpaired point of the plurality of points:

determining a height of the unpaired point based on the one of the three coordinates; and

incrementing, by an amount, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of non-overlapping height ranges including the height of the unpaired point.

16. The device of claim 14 , wherein generating the height histogram includes, for two paired points of the plurality of points:

determining a height of a line defined by the two paired point based on the one of the three coordinates of each of the two paired points;

determining a length of the line based on the others of the three coordinates of each of the two paired points; and

incrementing, by an amount scaled by the length of the line, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of height ranges including the height of the line.

17. A non-transitory memory storing one or more programs, which, when executed by one or more processors of a device with one or more scene cameras, cause the device to:

obtain a point cloud of a scene including a plurality of points in a gravity-aligned coordinate system;

generate, based on the plurality of points, a height histogram indicative of a plurality of non-overlapping height ranges in the gravity-aligned coordinate system and a respective plurality of weights; and

generate one or more horizontal plane hypotheses based on the height histogram, wherein generating the one or more horizontal plane hypotheses includes determining that one or more weights of the height histogram is greater than a threshold and generating one or more horizontal plane hypotheses corresponding to the respective height ranges.

18. The non-transitory computer-readable medium of claim 17 , wherein each of the plurality of points is associated with three coordinates in the gravity-aligned coordinate system, one of the three coordinates corresponding to a height of the point, wherein generating the height histogram includes, for an unpaired point of the plurality of points:

determining a height of the unpaired point based on the one of the three coordinates; and

incrementing, by an amount, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of non-overlapping height ranges including the height of the unpaired point.

19. The non-transitory computer-readable medium of claim 17 , wherein each of the plurality of points is associated with three coordinates in the gravity-aligned coordinate system, one of the three coordinates corresponding to a height of the point, wherein generating the height histogram includes, for two paired points of the plurality of points:

determining a height of a line defined by the two paired point based on the one of the three coordinates of each of the two paired points;

determining a length of the line based on the others of the three coordinates of each of the two paired points; and

incrementing, by an amount scaled by the length of the line, one of the respective plurality of weights of the height histogram corresponding to the one of the plurality of height ranges including the height of the line.