Overview

Terrain models are a rich resource to both military and civilian analysts for applications such as autonomous navigation, mission planning, battlefield assessment, emergency preparedness, and assessment of natural resources. Their usefulness depends on succinct encoding of terrain data not only for fast query and retrieval but also for efficient and accurate transmission of this data over restricted communication channels. Many applications require first the real-time conversion of point cloud data to a continuous terrain representation for further pipelined processing.

Unfortunately, the development of processing tools for realistic terrain surfaces has too often been ad hoc and simply borrowed from image processing. Terrain maps, however, are not conventional images and most image processing tools fail to extract the essential geometry and topology in the terrains and thereby fail to adhere to particular demands required by typical terrain application settings. This is particularly evident in urban terrain where man-made structures such as overhangs, bridges, arches, towers, and light poles, are not captured correctly. In addition, the metrics used to make decisions on bit allocation and accuracy of fit do not always match well with the targeted applications. Meeting these application demands requires substantially new metrics to measure distortion and new representation systems (explicit/implicit) that effectively capture topology and geometry of surfaces. These representations will be designed to provide a simple way to capture higher genus topology, significantly reduce the number of bits needed to encode terrain (especially in urban settings), and allow for fast assimilation of line-of-sight and avoidance regions for navigation.

This Multi-University project will develop both theory and algorithms which specifically addresses the deficiencies in terrain processing. The theory will analyze the expected performance of hybrid methods based on explicit and implicit representations including a rate distortion theory for Hausdorff and Line of Sight associated metrics. The inherent geometry and topology in terrains will be captured by using both implicit and explicit representations of terrain integrated seamlessly into a terrain encoder. The encoder will be designed to work either directly from raw point cloud data or processed structured data. Our development will be carried out in the context of application domains including autonomous navigation and Line of Sight. The algorithms will be implemented in a software and hardware platform that will be validated at an experimentation facility. Our theory will include

• a mathematical description (model classes) of which surfaces correspond to terrain;
• a determination of which metrics are most suitable to guarantee preservation of the essential geometry and topology of terrain;
• a rate-distortion theory for these model classes with respect to these metrics;
• an identification of fundamental explicit and implicit building blocks for the model classes which will sparsely represent the geometry and topology of terrain surfaces.

Our algorithmic development will address

• the assembly of these building blocks through constrained optimization to guarantee geometric and topological fidelity;
• building fast algorithms to extract these building blocks from both structured and point cloud data;
• building fast algorithms to encode and decode the sparse decompositions;
• fusing information gathered from multiple sensors.

The models for terrain surfaces will seamlessly incorporate both explicit and implicit representations, exploiting the advantages of both of these viewpoints while minimizing their drawbacks. Explicit representations are efficient, easy to extract and encode. However, implicit methods can treat geometry and topology more effectively, and align more comfortably with Line of Sight applications. A hybrid method will most likely provide the ultimate solution. The rate distortion theory will include the analogue of Kolmogorov entropy for mathematical function classes and the Shannon entropy for stochastic encoding. Once the limits of rate distortion are understood, the development of encoders that perform near the optimal limits should be realizable. Such encoders will integrate both explicit and implicit methods for optimal performance. Nonlinear and anisotropic numerical methods will be at the core of such a development. The representation systems for terrain models will allow for the treatment of both structured and point cloud data. The development of such a comprehensive theory can then drive the development of commensurate algorithms and software. All of this will be made with a careful eye to the demands of applications.