ARO Broad Agency Announcement

Background: Urban terrain is particularly challenging to model because it has "ubiquitous" discontinuities (walls, corners) as well as planar regions and regions of slow and rapid smooth change and it has multivalent height and non-genus-0 topology (buildings, overhangs, bridges, underpasses, subways, etc.). Point-cloud data for urban terrain is becoming widely available both in databases and in real time. "Explicit" methods, that is, methods that provide an explicit representation of the surface(s) such as trianqular mesh surfaces (TMSS) are often used to model urban terrain. TMSs can model corners and planar regions accurately and with high compression but not regions of smooth change. Fourier based methods, splines and kriging have advantages for representation of slowly changing smooth regions but display Gibbs phenomena near discontinuities or rapid change. Radial basis functions do not allow sufficient compression. Wavelets are computationally expensive for point-cloud data. "Implicit" methods, that is, methods based on level-set technology, handle topological issues in natural ways but can be computationally complex. As the practical need shifts from "terrain skins" (representations of height as a univalent function of latitude and longitude) to fully 3D terrain with multivalent height and non-genus-0 topology, new methods are required.

Objective: Develop an analytical framework and accurate and efficient computational procedures that are consistent with this framework for modeling the 3D geometry and topology of large regions (1 to 10^4 km^2) of urban terrain.

Research Concentration Areas (RCAs): Interdisciplinary research in geometric modeling, approximation theory, data and information processing, nonparametric statistics, electrical engineering, computer science, learning theory and scientific computing is needed in the following 7 areas:

RCA 1: Develop a static nonlinear model or models (explicit, implicit or hybrid) for 3D urban terrain that accurately represent the geometry and the topology of the terrain directly from highly nonuniformly distributed point-cloud data by automatic, nohuman-in-the-loop procedures with raw compression ratios up to 100. (Raw compression ratio = number of degrees of freedom in data divided by number of degrees of freedom in model). Noise and uncertainty (generally with either unknown or highly non-Gaussian statistical properties) should be taken into account. New approaches are required. TMSs, Fourier-based methods, conventional splines, radial basis functions, kriging, wavelets, tensor-product representations and various other methods that have been extensively investigated over the past 20 years are not recommended.

RCA 2: Quantify the computational expense both for generating the model and for using the model to compute items of interest (including but not limited to line of sight). Scalability is required.

RCA 3: Develop or determine an appropriate metric or metrics to measure the accuracy of the model of RCA 1 and determine estimates of accuracy of the model(s) in those metrics. It is unlikely that conventional metrics (such as rms) will be applicable.

RCA 4: In the metric(s) developed in RCA 3, determine tradeoffs between accuracy and compression.

RCA 5: Develop methods for computationally efficient generation of a multiresolution sequence of models of increasing geometric and topological accuracy. These methods should be developed in the metrics of RCA 3 and in the context of (sub) optimizing the accuracy/compression tradeoff determined in RCA 4. The multiresolution sequence of models should behave "continuously" and "monotonically" as resolution is increased or decreased (that is, no surprise temporary "pop-ins/outsPr or other artifacts as resolution is changed). Ad hoc multiresolution procedures not developed as part of a mathematically unified approach should not be proposed.

RCA 6: Based on the static models of RCA 1, develop procedures for dynamically learning or re-learning 3D urban terrain as data that supplement or replace previous data become available.

RCA 7: Test the models and procedures of RCAs 1, 5 and 6 on large point-cloud urban data sets. For applications such as calculation of line-of-sight regions, quantitatively compare the results for the models and procedures developed under this effort with the best competing approaches.

Impact: Military, peace-keeping and humanitarian operations increasingly take place in urban regions. 3D urban terrain models are needed for simulation, training, mission planning, operational situational awareness and autonomous navigation of ground and air vehicles.

Research Topic Chief: Dr. John Lavery, ARO