Sparse Representation and Multiscale Methods - Application to Digital Elevation Models

In general, a Digital Elevation Model (DEM) is produced either digitizing existing maps and elevation values are interpolated from the contours, or elevation information is collected from stereo imagery on digital photogrammetric workstations. Both methods produce a DEM to the required specification, but each method contains a variety of possible production scenarios, and each method results in DEM cells with totally different character. Common artifacts found in DEM are missing-values at different location which can influence the output of the application that uses this particular DEM.

In this work we introduce a numerically-stable multiscale scheme to evaluate the missing-value DEM's quantity of interest (elevation, slope, etc.). This method is very efficient for the case when dealing with large high resolution DEMs that cover large area, resulting in O(10⁶-10¹⁰) data points. Our scheme relies on graph-based algorithms and low-rank approximations of the entire adjacency matrix of the DEM's graph. When dealing with large data sets such as DEMs, the Laplacian or kernel matrix resulted from the interaction of the data points is stupendously big. One needs to identify a subspace that capture most of the action of the kernel matrix. By the application of a randomized projection on the graph affinity matrix, a well-conditioned basis is identified for it numerical range. This basis is later used in out-of-sample extension at missing-value location.

In many cases, this method beats its classical competitors in terms of accuracy, speed, and robustness.