Vehicle navigation using point cloud decimation

A method for navigation of a vehicle using point cloud decimation includes generating, by a processor circuit, a ground plane point cloud and an object point cloud. Generating the ground plane point cloud and the object point cloud includes performing point cloud decimation of a 3-D point cloud using ground plane segmentation. The further includes navigating, by the processor circuit, the vehicle using at least the object point cloud.

FIELD

The present disclosure relates to vehicle navigation and more particularly to vehicle navigation using point cloud decimation.

BACKGROUND

Autonomous vehicles may use three-dimensional (3-D) scanning devices, such as light detection and ranging (lidar) sensors, for use in navigation. For example, unmanned aerial vehicles or drones may use lidar sensors for navigation at an airport or other environment. Lidar sensors can provide centimeter scale accuracy for depth measurements and a dense, 360° view of the surrounding environment. Lidar sensors are capable of generating point clouds including hundreds of thousands of points per second which results in high computational costs and delays in processing. For navigation of a moving vehicle, the processing times for extracting static and dynamic objects which the vehicle must avoid in the environment can be unacceptable. Accordingly, there is a need for processing points clouds more efficiently that is acceptable for navigation of a moving vehicle.

SUMMARY

In accordance with an embodiment, a method for navigation of a vehicle using point cloud decimation includes generating, by a processor circuit, a ground plane point cloud and an object point cloud. Generating the ground plane point cloud and the object point cloud include performing point cloud decimation of a 3-D point cloud using ground plane segmentation. The method also includes navigating, by the processor circuit, the vehicle using at least the object point cloud.

In accordance with another embodiment, a system for navigation of a vehicle using point cloud decimation includes a processor circuit and a memory associated with the processor circuit. The memory includes computer readable program instructions that, when executed by the processor circuit cause the processor circuit to perform a set of functions including generating a ground plane point cloud and an object point cloud. Generating the ground plane point cloud and the object point cloud include performing point cloud decimation of a 3-D point cloud using ground plane segmentation. The set of functions also include navigating the vehicle using at least the object point cloud.

In accordance with an embodiment and any of the preceding embodiments, wherein performing point cloud decimation using ground plane segmentation includes defining a representation of a ground plane.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include performing a scanning operation using a 3-D scanning sensor to collect an electronic image of an environment associated with the vehicle. The electronic image includes the 3-D point cloud including point cloud data, and further including generating an output to a vehicle control system of an object point cloud defining objects and structures to be avoided during navigation of the vehicle.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include applying a voxel filter to the 3-D point cloud to eliminate redundant point cloud data and to produce a voxelized point cloud. The voxelized point cloud defines a downsampled version of the 3-D point cloud.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include performing angle and range subset selection on the downsampled version of the 3-D point cloud to select a subset of points for producing a representation of a ground plane.

In accordance with an embodiment and any of the preceding embodiments, wherein performing the angle and range subset selection includes projecting the downsampled version of the 3-D point cloud on a two-dimensional plane; overlaying a polar coordinate grid of points on the downsampled point cloud; and selecting the subset of points of the downsampled version of the 3-D point cloud closest to each point of the polar coordinate grid to ensure vertical planar surfaces contribute only a single point to the selected subset of points so that a majority of points in the selected subset of points belong to actual ground.

In accordance with an embodiment and any of the preceding embodiments, wherein producing the representation of the ground plane includes producing an equation representative of the ground plane. The equation defines a curve fit to points of the subset of points that represent the ground plane.

In accordance with an embodiment and any of the preceding embodiments, wherein producing the representation of the ground plane includes running a random sample consensus (RANSAC) algorithm on the selected subset of points to produce an equation representative of the ground plane.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include determining which points in the downsampled version of the 3-D point cloud are located in the ground plane point cloud and which points in the downsampled version of the 3-D point cloud are located in the object point cloud using the representation of the ground plane.

In accordance with an embodiment and any of the preceding embodiments, wherein determining which points in the downsampled version of the 3-D point cloud are located in the ground plane point cloud and which points are located in the object point cloud include determining a height of each point in the downsampled version of the 3-D point cloud relative to the ground plane; including a particular point in the ground plane point cloud in response to the height of the particular point being less than an acceptance threshold; and including the particular point in the object point cloud in response to the height of the particular point being greater than a rejection threshold.

In accordance with an embodiment and any of the preceding embodiments, wherein the particular point is an ambiguous point in response to the height of the particular point not being less than the acceptance threshold and not being greater than the rejection threshold.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include evaluating a group of neighboring points of the ambiguous point for a vertical feature; including the ambiguous point in the ground plane point cloud in response to determining that the group of neighboring points do not include the vertical feature; and including the ambiguous point in the object point cloud in response to determining that the group of neighboring points do include the vertical feature.

In accordance with an embodiment and any of the preceding embodiments, wherein the vehicle is an autonomous vehicle, and the method and system also include generating an output to a vehicle control system of an object point cloud defining objects and structures to be avoided during navigation of the vehicle.

In accordance with an embodiment and any of the preceding embodiments, wherein the vehicle is an aircraft, and the method and system further include generating an output to a vehicle control system of an object point cloud defining objects and structures to be avoided during navigation of the vehicle.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include generating a plurality of object point cloud; and tracking a moving object using the plurality of object point clouds.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include performing local vehicle motion planning using one or more object point clouds.

In accordance with an embodiment and any of the preceding embodiments, the method and system also include performing global route planning using one or more object point clouds.

DETAILED DESCRIPTION

The following detailed description of embodiments refers to the accompanying drawings, which illustrate specific embodiments of the disclosure. Other embodiments having different structures and operations do not depart from the scope of the present disclosure. Like reference numerals may refer to the same element or component in the different drawings.

FIGS. 1A and 1Bare a flow chart of an example of a method100for navigation of a vehicle using point cloud decimation102in accordance with an embodiment of the present disclosure. Referring also toFIG. 4,FIG. 4is a block schematic diagram of an example of a vehicle400including a system402for navigating the vehicle400using point cloud decimation102in accordance with an embodiment of the present disclosure.

In block104, a scanning operation is performed using one or more 3-D scanning sensors404to collect an electronic image or images106of an environment406associated with the vehicle400. The environment406may include a ground plane408, one or more moving objects410and one or more stationary objects412. Each electronic image106includes a 3-D point cloud108. Each 3-D point cloud108comprises a multiplicity of points110and each point110includes point cloud data112. Examples of the point cloud data112include at least a 3-D coordinate location of the point110in the point cloud108relative to some reference, for example, the 3-D scanning sensor404.

In block114, a ground plane point cloud116and an object point cloud118are generated. The ground plane point cloud116may also be referred to as ground point cloud or simply ground. Generating the ground plane point cloud116and the object point cloud118include performing point cloud decimation102of the 3-D point cloud108using ground plane segmentation414(FIG. 4) and object segmentation416(FIG. 4). In other words, points110in the 3-D point cloud that correspond to the actual ground are separated into the ground plane point cloud116, and points110that correspond to moving objects410or stationary objects412are separated into one or more object point clouds118. Point cloud decimation102using ground plane segmentation414and object segmentation416is described in more detail with reference to blocks122-136. Performing point cloud decimation102includes defining a representation120of the ground plane408(FIG. 4) or actual ground.

In block122, a voxel filter417(FIG. 4) is applied to the 3-D point cloud108to eliminate redundant point cloud data112and to produce a voxelized point cloud124. The voxelized point cloud124defines a downsampled version of the 3-D point cloud126. The downsampled version of the 3-D point cloud126is also referred to herein as the downsampled point cloud126.

In block128, angle and range subset selection is performed on the downsampled point cloud126to select a subset of points130of the downsampled point cloud126for producing the representation120of a ground plane408. An example of performing the angle and range subset selection will be described in more detail with reference toFIG. 1D. The selected subset of points130are those points of the downsampled point cloud126(voxelized point cloud124) that are closest to points208(FIG. 2) of a polar coordinate grid202that is overlaid the downsampled point cloud126or voxelized point cloud124.

In block132, a representation120of the ground plane408(FIG. 4) is produced using the selected subset of points130. In accordance with an embodiment, producing the representation120of the ground plane408includes producing an equation134representative of the ground plane408. The equation134defines a curve fit to points of the selected subset of points116that correspond to the ground plane408(FIG. 4). The method performs angle and range subset selection to select a subset of points130of the downsampled point cloud126, where a mathematical curve-fitting function may be utilized to define a best-fit equation for the selected subset of points116that corresponds to the representation of the ground plane408. In accordance with an example, producing the representation120of the ground plane408includes running a random sample consensus (RANSAC) algorithm on the selected subset of points130to produce the equation134representative of the ground plane408. An example of RANSAC algorithm is described in “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography” by Martin A. Fischer and Robert C Bolles, Communications of the ACM Graphics and Image Processing, Volume 24, Number 6, June 1981, the contents of which are incorporated herein by reference.

In block136, a determination is made which points in the downsampled point cloud126are located in the ground plane point cloud116(acceptance region) and which points in the downsampled point cloud126are located in the object point cloud118(rejection region) using the representation120of the ground plane408(FIG. 4). An example of determining which points in the downsampled point cloud126are located in the ground plane point cloud116and which points are located in the object point cloud118is described in more detail with reference toFIG. 1E. Any ambiguities between which points of the downsampled point cloud126are located in the ground plane point cloud116and which points are located in the object point cloud118are resolved by the method156described with reference toFIG. 1E. Accordingly, point cloud decimation102is performed in block114which includes blocks122-136by segmenting the ground plane point cloud116and the object point cloud118, where performing point cloud decimation to determine which points are segmented to or located in the ground plane point cloud and the object point cloud may comprise defining a representation of a ground plane.FIG. 3is an illustration of an example of an object point cloud118for use in navigation of a vehicle in accordance with an embodiment of the present disclosure. Illustrated in the exemplary object point cloud118are structures302, such as buildings302a-302d, and objects304-308, such as moving objects, e.g., aircraft304a-304band vehicles306a-306b, and stationary objects, e.g., light pole308, where a two-dimensional plane or grid310is depicted with respect to the object point cloud118.

In accordance with the example inFIGS. 1A-1C, the method100returns to block104and another scanning operation is performed using the one or more 3-D scanning sensors404to collect additional electronic images106of the environment406(FIG. 4) associated with the vehicle, for example, vehicle400inFIG. 4. Accordingly, as the vehicle400moves or taxies at an airport or other facility, electronic images including 3-D point clouds108are continuously collected and processed as described herein to generate a plurality of object point clouds118that are used for navigation of the vehicle400within the environment406associated with the vehicle400. The method may further include generating an output to a vehicle control system428of an object point cloud118defining objects304-308and structures302to be avoided during navigation of the vehicle400. The object point clouds118are also useable for other purposes as described with reference toFIG. 1C.

Referring also toFIG. 1C, in block138, a vehicle, such as for example the vehicle400inFIG. 4, is navigated using at least one or more of the plurality of object point clouds118continuously generated by the method100inFIG. 1A. In block140, a moving object, for example moving object410inFIG. 4, is continuously tracked using at least the object point clouds118that are continuously generated by the method100. Additionally, stationary objects, such as stationary object412inFIG. 4, can be avoided during navigation of the vehicle400.

In accordance with an embodiment, in block142, global route planning is performed using at least one or more object point clouds1118.

In block144, local vehicle motion planning is performed using at least one or more object point clouds118generated by the method100. Accordingly, movement of a vehicle, such as vehicle400inFIG. 4, may be planned prior to movement of the vehicle using at least. one or more object point clouds118to avoid any stationary object412(FIG. 4). The object point clouds118continuously generated by the method100during movement of the vehicle are also used to evade any moving objects410that may enter a planned route of the vehicle from the local vehicle motion planning in block144.

Referring toFIG. 1D,FIG. 1Dis a flow chart of an example of a method146for performing angle and range subset selection in accordance with an embodiment of the present disclosure. In accordance with an example, the method146is used for the block114inFIGS. 1A-1B. Referring also toFIG. 2,FIG. 2is an illustration of an example of performing angle and range subset selection on the downsampled point cloud126to select a subset of points130(FIG. 1A) for producing a representation120(FIG. 1B) of the ground plane408(FIG. 4) and ensuring that vertical planar surfaces418cannot contribute points to the selected subset of points130when determining the equation134(FIG. 1B) representative of the ground plane408(FIG. 4) in accordance with an embodiment of the present disclosure. Each box inFIG. 2represents a voxel206of the voxelized point cloud124. As previously described, the voxelized point cloud124defines the downsampled point cloud126. Applying a voxel filter417(FIG. 4) in block122ofFIG. 1Ato the 3-D point cloud108causes voxelization of the 3-D point cloud108. Voxelization of the 3-D point cloud108means carving a space in a real n-dimensional coordinate system (n) into an n-dimensional grid of contiguous hyper-rectangles. The centroid of each of the hyper-rectangle is computed and becomes the location of the voxel206.FIG. 2illustrates a two-dimensional representation of the voxelized point cloud124. In accordance with an example, assuming that each voxel206has dimensions of 1 meter by 1 meter and one voxel206is defined by corners with coordinates (0,0) and (1,1), if there are three points inside that voxel206at coordinates (0.25, 0.75), (0.5, 0.5) and (0.75, 0.25), then the coordinates of that voxel206are an average of the coordinates of the three points: ((0.25+0.5+0.75)/3, (0.75, 0.5, 0.25)/3)=(0.5, 0.5).

In block148, the downsampled point cloud126or voxelized point cloud124is projected on a two-dimensional plane200or cartesian grid as illustrated inFIG. 2.

In block150, a polar coordinate grid202including a plurality of points208is overlaid on the downsampled point cloud126.

In block154, selection is made from the downsampled point cloud126of the particular subset of points130that are closest to each point208of the polar coordinate grid202(where selection may be based on angle and range for a point cloud point relative to the polar coordinate grid points) to ensure vertical planar surfaces418(FIG. 4) contribute only a single point to the subset of points130so that a majority of points of the selected subset of points130belong to actual ground, such as ground plane408inFIG. 4. The selected subset of points130are then used to produce a representation120of the ground plane408(FIG. 4) or actual ground in block132ofFIG. 1Bas previously described.

FIG. 1Eis a flow chart of an example of a method156for determining which points in a downsampled point cloud126are located in a ground point cloud116and which points are located in an object point cloud118in accordance with an embodiment of the present disclosure. In accordance with an example, the method156is used to perform the block136inFIG. 1B. The method156is performed for each point in the downsampled point cloud126.

In block158, a height (H) of each point in the downsampled point cloud126relative to the ground plane408(FIG. 4) is determined. In block160, a determination is made if the height (H) of a particular point in the downsampled point cloud126is less than an acceptance threshold. In accordance with an example, the acceptance threshold is set at a level so that any points that are an ambiguous point162as to whether the point should be in the ground plane point cloud116or the object point cloud118are evaluated as described further herein so that the ambiguous point162is included in the correct point cloud116or118or most likely correct point cloud116or118.

In block160, if the height (H) of the particular point is less than the acceptance threshold, the method156advances to block164. In block164, the particular point of the downsampled point cloud126is included in the ground plane point cloud116in response to the height (H) of the particular point being less than the acceptance threshold.

If the height (H) of the particular point is not less than the acceptance threshold in block160, the method156advances to block166. In block166, a determination is made if the height (H) of the particular point is greater than a rejection threshold. Similar to the acceptance threshold, the rejection threshold is set at a level so that any point that is an ambiguous point162as to which point cloud116or118the point belongs is evaluated as described herein so that the ambiguous point162is included in the correct point cloud116or118or most likely correct point cloud116or118.

In block166, if the height (H) of the particular point is greater than the rejection threshold, the method156advances to block168. In block168, the particular point is included in the object point cloud118in response to the height (H) of the particular point being greater than the rejection threshold.

If the height (H) of the particular point is not greater than the rejection threshold in block166, the particular point is an ambiguous point162. Accordingly, the particular point is an ambiguous point162in response to the height (H) of the particular point not being less than the acceptance threshold in block160and not being greater than the rejection threshold in block166.

In block170, a group of points in the downsampled point cloud126(FIG. 1A) neighboring the ambiguous point162are evaluated for vertical features. For example, a total vertical variation or height variation with respect to ground of neighboring points of the ambiguous point162is computed. Neighboring points are points within a preset radius of the ambiguous point162. For example, the preset radius may be about 0.5 meters. If the total variation of the group of neighboring points is greater than a predetermined limit, e. g., about 0.1 meters, then a determination is made that the group of neighboring points include vertical features.

In block172, a determination is made if the group of points neighboring the ambiguous point162have a vertical feature or features. The ambiguous point162is included in the ground point cloud116in block164in response to determining that the group of neighboring points do not include the vertical feature or features. The ambiguous point162is included in the object point cloud118in block168in response to determining that the group of neighboring points do include the vertical feature or features.

FIG. 4is a block schematic diagram of an example of a vehicle400including a system402for navigating the vehicle400using point cloud decimation102(FIGS. 1A-1B) in accordance with an embodiment of the present disclosure. Exampled of the vehicle400include but are not necessarily limited to an autonomous vehicle, an aircraft, an unmanned aerial vehicle or drone, etc.

As previously described, the system402includes one or more 3-D scanning sensors404. Examples of the 3-D scanning sensor or sensors include but are not limited to 3-D light detection and ranging (lidar) sensors or any other type sensor capable of providing an electronic image or 3-D point cloud as described herein.

The system402also includes a processor circuit420and a memory422associated with the processor circuit420. In accordance with an example, the memory422includes a database424for storing the electronic images106including the 3-D points clouds108and associated points110and data112. The memory422also includes computer readable program instructions that, when executed by the processor circuit420cause the processor circuit to perform a set of functions, for example, the set of functions described with reference toFIGS. 1A-1Dand methods100,146and156. The computer readable program instructions include a point cloud decimation module426. In accordance with an embodiment, the methods described with reference toFIGS. 1A-1Dare embodied in the point cloud decimation module426and are performed by the processor circuit420when executed by the processor circuit420.

Similar to that previously described, the point cloud decimation module426performing the methods previously described generates the ground plane point cloud116and the object point cloud118. The system402also includes moving object tracking module configured to track any moving objects410in the environment406associated with the vehicle400using at least the object point cloud118so that the vehicle400can be maneuvered to avoid the moving objects410and any stationary objects412in the environment406.

A vehicle control system428is configured to control steering, throttle actuation, brake actuation, a vehicle management system (VMS) etc.

In accordance with an example, a route planning module430is provided. The route planning module430is embodied on a processor circuit432that is separate from the vehicle400. The route planning module430is configured to perform as set of functions including but not necessarily limited to global route planning, local vehicle motion planning436, and avoidance behaviors438.

Although specific embodiments have been illustrated and described herein, those of ordinary skill in the art appreciate that any arrangement which is calculated to achieve the same purpose may be substituted for the specific embodiments shown and that the embodiments have other applications in other environments. This application is intended to cover any adaptations or variations. The following claims are in no way intended to limit the scope of embodiments of the disclosure to the specific embodiments described herein.