Two-step ODETLAP and induced terrain for improved geographical data reconstruction

This thesis presents two algorithms that improve geographical data reconstruction. The 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. The 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 required by many visualization and analysis tasks. These two algorithms are tailored to work with the following characteristic features of 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 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 approaches which attempt to alleviate the problem suffer from significant terrain feature loss and the reliance of human in deciding the appropriate smoothing factor. Our two-step ODETLAP procedure fixes both problems. The process first applies an accuracy-centric ODETLAP to complete the missing depths from the given samples. After that, the vigorous depth fluctuations along the tracklines are removed by applying a smoothing-centric 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 with 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 geographical layers which may imply how river flows. An example is the set of height samples that may hint water flow directions. Another example is the hydrological consistency constraints which represent our knowledge on the possible global river network topology. Our induced terrain approach incorporates these additional pieces of information by first reconstructing a fictitious virtual terrain surface in compliance with the available geographical 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 the given river locations as local minima properly. If no sufficient reliable height samples are available (sample density smaller than 10% or low signal-to-noise ratio), we can recover 40% of what we would have corrected with rich height samples by portraying the given river locations as local minima and assigning relatively small heights to areas radiating from segment tips. Data from other geographical layers can also be used to refine the induced terrain. For example, known water flow directions can be used to correct river heights 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 among river derivation schemes with different execution speeds and hydrographical consistency constraints.