Linear Spline Approximation

In several applications, one is concerned with the representation of complex geometries or complex physical phenomena at multiple levels of resolution. In the context of computer graphics and scientific visualization, so-called multi-resolution methods are crucial for the analysis of very large numerical data sets. Examples include high-resolution terrain data (digital elevation maps), laser scans of mechanical models, and high-resolution, three-dimensional imaging data (e.g., X-ray computed tomography or magnetic resonance imaging data).

We approached the construction of multi-resolution representations of very large scattered data sets using the principle of simulated annealing. Our goal is the computation of several optimal linear spline approximations to a given scattered data set. This approach is a generalization of data-dependent triangulation algorithms.

When representing high-resolution data sets with low-resolution linear spline approximations, one has to be careful where to place the spline's control points and how to connect them in order to achieve a faithful representation of the data set. To find the optimal linear spline approximation with a given number of control points, we employ an iterative optimization algorithm that attempts to improve the quality, measured by an appropriate error norm, of an initial approximation by moving the spline's control points. This iteration is governed by the simulated annealing algorithm, an optimization technique well fit for high-dimensional problems where the desired global minimum is hidden among many, poorer, local minima.

Figure 1: Photograph of Golden Gate bridge, approximated by a vector-valued bivariate linear spline containing 3,200 control points.

Project Goals

The main project goals were to design data structures and algorithms to represent and manipulate linear spline approximations to scattered data, and to implement a suite of approximation programs for uni- and bivariate, scalar- or vector-valued scattered data. In detail, these goals included:

Design data structures to represent linear splines
- Represent univariate splines as ordered set of valued sites, connected by line segments.
- Represent bivariate splines as triangulations of the convex hull of set of valued sites.
Implement algorithm to create initial linear spline approximation from scattered data
- Calculate scattered data set's convex hull.
- Create random initial configuration by selecting a subset of samples from a data set and calculating its Delaunay triangulation.
- Create "greedy" optimal initial configuration by incrementally inserting those samples that are worst represented by the current configuration.
Implement algorithms to manipulate linear splines
- Move control point globally by removing and re-inserting it from/into the spline.
- Move control points locally by sliding them along a vector connecting their old and new positions, and updating the spline's connectivity incrementally.
- Change connectivity by "rotating" an edge of the spline's triangulation (for bivariate splines only).
Implement error metric appropriate for linear spline approximations to scattered data.
Implement version of Simulated Annealing algorithm to govern global minimization of spline's approximation error.
Write multi-resolution viewer program to display hierarchies of linear spline approximations.

Project Status

In October 1998, the project reached the level of functionality listed above; and a thesis describing it and the approximation results achieved by it was submitted to the Universität Karlsruhe (TH), Karlsruhe, Germany, to fulfill the requirements for the degree "Diplom-Informatiker" (Master of Science degree in computer science). The Diploma Thesis (in German) is available for download (PDF format, 7,009K). The project has not been maintained since, and all related source code has just recently been released under the GNU General Public License (see download page).

Related Publications

Kreylos, O., Optimale Approximation uni- oder multivariater Funktionen in mehreren Auflösungen, diploma thesis, Fakultät für Informatik, Universität Karlsruhe (TH), Karlsruhe, Germany, 1999
Available for download (PDF format, 7,009KB)
Kreylos, O. and Hamann, B., On Simulated Annealing and the Construction of Linear Spline Approximations for Scattered Data, Proceedings of the Joint EUROGRAPHICS and IEEE TVCG Symposium on Visualization, Vienna, Austria, May 1999, pp. 189-198
Hamann, B., Kreylos, O., Monno, G. and Uva, A.E., Optimal Linear Spline Approximation of Digitized Models, Proceedings of the IEEE International Conference on Information Visualization (IV99) - Computer Aided Geometric Design Symposium, IEEE Computer Society Press, Los Alamitos, CA, pp. 244-249
Kreylos, O. and Hamann, B., Data Structures for Optimizing Linear Spline Approximations, Computers & Graphics 24(3) (2000), Special Issue on Data Visualization, pp. 353-361
Bremer, P.-T., Kreylos, O., Hamann, B. and Wolter, F.-E., Simplification of Closed Triangulated Surfaces, in: Haungs, M.L., ed., Proceedings of the 2000 UC Davis Student Workshop on Computing, TR CSE-2000-9 (presented at: "2000 UC Davis Student Workshop on Computing," University of California, Davis, California, September 2000)
Bremer, P.-T., Hamann, B., Kreylos, O. and Wolter, F.-E., Simplification of Closed Triangulated Surfaces Using Simulated Annealing, to appear in: Lyche, T. and Schumaker, L.L., eds., Mathematical Methods in CAGD: Oslo 2000, Vanderbilt University Press, Nashville, Tennessee, pp. 45-54
Kreylos, O. and Hamann, B., On Simulated Annealing and the Construction of Linear Spline Approximations to Scattered Data, IEEE Transactions on Visualization and Computer Graphics 7(1) (2001), pp. 17-31
Available for download (PDF format, 1,006KB)
Bremer, P.-T., Kreylos, O. and Hamann, B., A Data-Dependent Gradient Quantization Scheme for the Acceleration of Volume Rendering, in: Erbacher, R.F., Chen, P.C., Groehn, M., Roberts, J.C. and Wittenbrink, C.M., eds., Visual Data Exploration and Analysis VIII, Proceedings SPIE Vol. 4302, SPIE - The International Society for Optical Engineering, Bellingham, Washington

Pages In This Section

Approximation Examples: Examples of multi-resolution approximations of different data sets, including a laser scan and several RGB images.
Download: Download page for all source code necessary to compile and use the Linear Spline Approximation Package.