Recently, the accuracy and cost of laser range scanners and the need to efficiently process and classify the input information of these scanners has given rise to a growing area of research concerned with modeling and encoding terrain data. Furthermore, a growing need to integrate these models into existing applications, such as autonomous navigation and streaming encoding for data communication, has allowed research groups from multiple universities to collaborate in order to promote the exchange of ideas and techniques. Our work aims at analyzing, modeling, classifying, and encoding large amounts of urban terrain data obtained from scanners known as point clouds. While no information may be given about the point cloud, an accurate model which can classify various features of the terrain as well as approximate regions of uncertainty is required for correct navigation of the area. Moreover, the computational cost of these simulations must not be allowed to bottleneck navigation in situations where real-time performance is necessary, and our research also includes methods to accelerate our computations to meet these goals. We also research metrics for the data which will provide the most accurate approximation possible under the given constraints of the data.
Modeling – Urban terrain data may contain highly detailed features which are diffult to classify and model for a number of reasons. These features may include bridges, overhangs, telephone/power lines, rubble, humans, vehicles, and discontinuities in the data from sensing error. All of these features must be accurately and efficiently processed before any meaningful navigation is possible. Moreover, it is essential that no assumptions be made about the incoming data. Our research explores explicit/implicit models of the terrain by using a number of techniques. In particular, we focus on analyzing and composing the imput data into a set of “primitives” which are used for on-board navigation, as well as an intermediate step between surface reconstruction and compression/encoding. It is our goal to provide a model which facilities fast/accurate classification and transmission of the data, and to provide a client-side model for processing the transmitted intermediate data into a more complex form, providing a trade-off between data communication speed and client-side computational complexity.
Metrics for Accurate Approximation – For an accurate model of the data, a set of metrics must be employed which provide the desired accuracy and robustness of the data. We research metrics which are beneficial for navigation, giving the desired degree of physical accuracy. These metrics can be used at every stage of the process to prevent error which may prevent meaningful navigation. Much of our work employs a two-sided Hausdorff metric which has been shown to work well in practice.
Encoding – In the field, decisions must be made as soon as data is available from sensors/units. Our research explores how progressive encoding can be performed for all components of the terrain model, as well as employing a hierarchical structure of the domain so that it may be streamed from the transmitter to the receiver and processed almost immediately, even before the entire payload of data has been received. Our research looks at encoding the hierarchical structures, surface normals/equations, and clipping regions to name a few. Again, a tradeoff must be made between the accuracy of the data and the availability of data to the client.
Approximation – While an exact representation of the terrain data may be impossible, an accurate and robust approximation of the data is required. Substantial research has been done into data approximation. It is critical to employ a physically accurate approximation model, as it influences decisions about navigation and path-planning.
Computation Efficiency of Reconstruction – Many times, the device reading input and processing the data for transmission may be a low-cost, low-power mobile device which can only afford a limited number of resources. For this reason, we research into methods for improving computational efficiency for every stage of the process by looking into both software and hardware acceleration techniques which can provide the needed speed. Hardware components such as GPU processing and parallel algorithms are very promising areas of this research.
Compression – While encoding the data allows for streaming reconstruction of the data, an efficient compression model must be employed to reduce the transfer time for the payload. An accurate and efficient compression model must be used for preprocessing before transmission, and post-processing on the client-side. Trade-offs on both sides is important for the accuracy and robustness of the transmitted data.
Our current research aims at developing a method to decompose and model basic primitive information derived from point cloud data, and then using these primitives, reconstruct an accurate surface represenation from the primitive data. This way, the primitives/data structures used may be encoded efficiently before transfer, and the implicit surface reconstruction may be performed on the server-side from this primitive data. The primitive data is also essential in understanding the physical layout of the field for autonomous navigation.
A simple octree structure used for progressive encoding, surface reconstruction, and primitive generation.
We make use of a hierarchical spatial subdivision scheme known as an octree in order to decompose the point cloud data into finer pieces. Octrees provide the useful property that highly dense regions of the cloud (more data and detail) are able to be split up into finer resolution than regions of sparse data. From the octree, each cell's contents are analyzed to produce a primitive for that cell. These primitives can be simple planes or higher order surfaces. After primitive information is created for each cell, we use a two-sided Hausdorff error metric to determine if the primitive is a reasonable fit given the cell's data, or if further subdivision of the cell into smaller pieces is necessary. While the one-sided Hausdorff distance provides a decent metric for measuring the accuracy of a fit, the two-sided Hausdorff gives an extra constraint which can prevent situations in which there is a poor spread of data with relation to the primitive. When the Hausdorff metric for any cell's fit is above a user-defined threshold, the cell is split to the next level. In practice, this technique has been shown to detect many of the features present in urban terrain data.
Two different types of primitives for a light pole.
While the two-sided Hausdorff metric provides a very accurate error measure for the primitive fit, there are many cases where the cell can not simply be split up into finer pieces due to the sparsity of the data within that cell. In these cases, we employ the use of axis-aligned bounding boxes in order to "clip" the areas of the primitive which are not part of the data. Features such as overhangs or thin structures have these issues, and we have found that in practice using a bounding structure as a means to clip portions of the primitive give a much better approximation of certain features with very minimal additional computational complexity.
Different types of data sets and their primitive information used for navigation and reconstruction.
Following the primitive computations, there is sufficient information available to perform implicit surface reconstruction. While the primitive information is sufficient for navigation, the surface reconstruction will allow the client-side or human to have a better understanding of the terrain. We employ the use of multiple implicit surface reconstruction techniques, as well as wavelets to smooth out the surface and give a much better accurate approximation. Our research includes methods to progressively stream the data to the client so that they may have an overview of the terrain even before all of the information is received. Moreover, given limited bandwidth and bit transfer speed in many real military and civilian applications, the progressive encoding allows for decisions to be made about the terrain or the mission, even if the data is cut off mid-transmission, or the entire data-set has not arrived yet. We are working closely with Richard Baraniuk's team at Rice University to perform efficient encoding techniques with the terrain data.
Multiple surfaces after reconstruction.
If you would like more information, please contact us directly.
Page containing links to data and source for an updated version of this project.
Slides containing more images and data currently in our methods.
A list of links and articles explaining some of our methods with surface reconstruction and approximation theory.
Slides explaining our methods at a high level (coming soon)
The scope of this research requires a cooperative effort between multiple research institutions. For more information about the respective research group, see the links below.
Rice University - Richard Baraniuk
University of South Carolina - Robert C. Sharpley
University of Texas – Richard Tsai
University of California, Los Angeles – Stan Osher
University of California, Irvine - Hongkai Zhao
Virginia Tech - Andrew Kurdila
Our research is funded in part by ARO MURI, AFOSR, the DTRA and the NSF.