Bounding Methods for Heterogeneous Lidar-derived Navigational Geofences
Safe Unmanned Aerial Vehicle (UAV) operations near the ground require navigation methods that avoid fixed obstacles such as buildings, power lines and trees. Aerial lidar surveys of ground structures are available with the precision and accuracy to geolocate obstacles, but the high volume of raw survey data can exceed the compute power of onboard processors and the rendering ability of ground-based flight planning maps. Representing ground structures with bounding polyhedra instead of point clouds greatly reduces the data size and can enable effective obstacle avoidance, as long as the bounding geometry envelopes the structures with high spatial fidelity. This report describes in detail four methods to compute bounding geometries of ground obstacles from lidar point clouds. The four methods are: 1) 2.5D Maximum Elevation Box, 2) 2.5D Ground Map Extrusion, 3) 3D Bounding Cylinder, and 4) 3D Bounding Box. The methods are applied to five point cloud datasets from lidar surveys of UAV flight research sites in Georgia and Virginia with an average point spacing that ranges from 0.1m to 0.6m. The methods are assessed using survey areas with geometrically heterogeneous ground structures: buildings, vegetation, power lines, and sub-meter structures such as road signs and guy wires. The 2.5D Maximum Elevation Box method is useful for simple structures. The 2.5D Ground Map Extrusion method efficiently encloses vegetation, but requires handdrawn ground footprints. The 3D Bounding Cylinder method excels at enclosing linear structures such as power lines and fences. The 3D Bounding Box method excels at enclosing planar structures such as buildings. The methods are compared on the basis of data compression and boundary fidelity on selected areas. The 2.5D methods yield the highest data compression but the polyhedra produced by them enclose significant amounts of empty space. Boundary fidelity is superior for the 3D methods, though this fidelity comes at the cost of a roughly thirtyfold lower data compression ratio than the 2.5D Maximum Elevation Box method. A mix of these output geometries is proposed for autonomous UAV navigation with limited on-board computing. Both the accuracy and spatial detail of emerging satellite-based survey technology lower than that of aerial lidar scanning survey technology. Sub-meter structures and thin linear structures are not reliably mapped at present by satellite-based surveys.