* Research

Ph.D. Theses

Two-Step ODETLAP and Induced Terrain Framework for Improved Geographical Data Reconstruction

By Tsz-Yam Lau
Advisor: W. Randolph Franklin
November 20, 2012

This thesis presents two algorithms that improve geographical data reconstruction. First is the two-step Overdetermined Laplacian Partial Differential Equation (ODETLAP) which automates minimum-error, artifact-free surface reconstruction from extremely unevenly distributed data samples. Second is the induced terrain framework which references multiple geographical attributes in the reconstruction of a geographical layer. Reconstruction is important since we often cannot obtain the data values of all locations, which is a condition required by many visualization and analysis tasks. These two algorithms are tailored to work with the following characteristic features of partial geographical data: extremely unevenly distributed samples due to the fundamental limitations of the respective surveys, and the availability of multiple attributes that are usually collected in the same geospatial domain.

Sea-floor surface reconstruction is an example problem suffering from survey-induced uneven sample distribution. The wide-coverage option using altimeter fails to detect seafloor features which are narrower than 3 kilometers. As a result, the high-resolution version of this problem is still confined to extremely unevenly distributed samples along the few ship routes, in which case numerous generic reconstruction algorithms generate unacceptable surfaces featuring abnormal depth fluctuations which are correlated with the trackline locations. All conventional smoothing attempts to alleviate the problem suffer from significant terrain feature loss and the reliance of human to decide appropriate smoothing factor. Our two-step ODETLAP procedure fixes both problems. The process first applies an accuracy-biased ODETLAP to complete the missing depth data from the given samples. After that, the vigorous depth fluctuations along the tracklines are removed by applying a smoothing-biased ODETLAP on the completed depth grid. To determine the optimal smoothing factor automatically, the procedure computes the areas of the individual bumps on the reconstructed surface. A surface suffering heavily from the artifacts has many small bumps but few big ones. Smoothing reduces such skewness. For many datasets, the artifact is mostly gone when the coefficient of variation of the areas drops to around 1.3. Using that value to gauge the smoothing factor, the automated scheme successfully generates artifact-free seafloor surfaces within an error budget smaller than other conventional approaches.

The problem of completing hydrography network from broken river segments features the availability of data from multiple geographical layers. Conventional approaches solve the problem using typical line joining algorithms, ignoring samples in other geospatial layers which may imply how river flows. An example is the set of height samples which physically determines water flow direction. Another example is the hydrological consistency constraints which represent our knowledge on the possible global river network topology. Our induced terrain approach incorporates these pieces of additional information by first reconstructing a fractious virtual terrain surface in compliance with the available geospatial data, and then deriving a river network which passes through the given river segments with a modified river derivation scheme that ensures the required hydrological consistency. If the height samples are evenly distributed across the terrain, the induced terrain can be generated with any conventional 2D reconstruction algorithm such as natural neighbor interpolation. However, if the height samples are concentrated at river locations only, the hydrology-aware variant of ODETLAP is needed to model given river locations as local minima properly. If no sufficient reliable height samples are available (density < 0.1 or high signal-to-noise ratio), portraying given river locations as local minima with relatively smaller heights at directions radiating from segment tips recovers 40% of what we can correct with rich height samples. Data from other geographical layers can also be used to refine the above induced terrain. For example, known water flow directions can be used to correct the heights along river segments which may have been reconstructed incorrectly with height samples alone. This improves the accuracy by 1-4 percentage points. Meanwhile, known non-river locations can be protected from being river locations in the reconnection results by raising their heights to a level unreachable by any water. While effective in boosting accuracy by around 5 percentage points, this scheme also makes it simple to switch between river derivation schemes with different execution speeds and hydrographical consistency constraints.

* Return to main PhD Theses page