Least Squares Approximation of Scattered Data with B-splines

1.1

Utladalen.jpg

A B-spline surface representing an area in Jotunheimen

Short introduction

This documentation contains a brief reference manual for the SINTEF LSMG library developed at at SINTEF Applied Mathematics. The LSMG library is a means to make (penalized) least squares approximations to scattered data with B-spline surfaces.

The methods have been developed for making high quality smooth surface approximations to scattered data in applications such as geological modelling, GIS and CAD/CAM. Special attention has been payed to i) creating large surfaces fast and ii) "natural" extrapolation of surfaces outside the domain of the scattered data or to areas of the domain with no scattered data. These properties are important especially in geology and GIS. Although the approximation methods are global, they are fast due to the multigrid schemes that are used for solving linear equation systems.

The main interface is through the class MGsystem which contains multigrid schemes for solving the approximation problem fast. The class LSsystem which contains basic iterative relaxation procedures (equation solvers) can also be used directly or in combination with MGsystem.

This library uses the same data structures as the SINTEF MBA library (Multilevel B-spline approximation library) which can optionally be used as a "preconditioner" when running the more CPU demanding algorithms in the LSMG library.

Getting started

It's very easy - just look at the examples referred to below, copy the main programs, modify them for your needs, compile and run!

Solving the scattered data approximation problem with multigrid equation solvers

These are the most powerful methods for calculating a B-spline surface as a least squares approximation to the scattered data. You can choose among different multigrid schemes, decide the number of iterations to be run by the iterative equation solvers, adjust smoothness of the surface etc. You find a small minimal code example in class MGsystem. Read the documentation for the functions that are called there. Then, copy the complete main program to a file - compile it and run it! The program samples the resulting spline surface and writes the result to a VRML file.

Simple relaxation

This is a simpler method with pure relaxation only, i.e., starting with a (good) starting vector, use one of the iterative equation solvers in class LSsystem and run a given number of iterations. (Here, relaxation means the iteration process by an iterative equation solver). You find a small example in class LSsystem. Read the documentation for the functions that are called there. Then, copy the complete main program to a file - compile it and run it! The program samples the resulting spline surface and writes the result to a VRML-file. This method can be used if you already have a fair initial solution and you want to improve it or smooth it by giving a specified smoothing factor. The initial solution may be the result from the SINTEF MBA library (which is extremely fast), or from the methods in class MGsystem.

You can download a free VRML-viewer from Kongsberg SIM.

If you have got the Visual C++ workspace with all the source code, then you can build the application and run it with the current main program.

Download

A GPL-version of the library (for Linux/Unix) can be downloaded from http://www.sintef.no/math_software.

Please report any problems or comments to jan.b.thomassen@sintef.no

Øyvind Hjelle, June 2002

Last modified 28.11.2007 by Jan Thomassen

SINTEFlogo.gif

Generated on Wed Nov 28 12:27:29 2007 for LSMG by  doxygen 1.5.1