Moving least squares

Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples via the calculation of a weighted least squares measure biased towards the region around the point at which the reconstructed value is requested.

In computer graphics, the moving least squares method is useful for reconstructing a surface from a set of points. Often it is used to create a 3D surface from a point cloud through either downsampling or upsampling.

Definition

Here is a 2D example. The circles are the samples and the polygon is a linear interpolation. The blue curve is a smooth interpolation of order 3.

Consider a function $f:\mathbb {R} ^{n}\to \mathbb {R}$ and a set of sample points $S = \{ (x_i,f_i) | f(x_i) = f_i \}$ where $x_{i}\in {\mathbb {R}}^{n}$ and the $f_{i}$ 's are real numbers. Then, the moving least square approximation of degree $m$ at the point $x$ is $\tilde{p}(x)$ where ${\tilde {p}}$ minimizes the weighted least-square error

\sum_{i \in I} (p(x_i)-f_i)^2\theta(\|x-x_i\|)

over all polynomials $p$ of degree $m$ in $\mathbb {R} ^{n}$ . $\theta(s)$ is the weight and it tends to zero as $s\to \infty$ .

In the example $\theta(s) = e^{-s^2}$ . The smooth interpolator of "order 3" is a quadratic interpolator.

References

The approximation power of moving least squares David Levin, Mathematics of Computation, Volume 67, 1517-1531, 1998
Moving least squares response surface approximation: Formulation and metal forming applications Piotr Breitkopf; Hakim Naceur; Alain Rassineux; Pierre Villon, Computers and Structures, Volume 83, 17-18, 2005.
Generalizing the finite element method: diffuse approximation and diffuse elements, B Nayroles, G Touzot. Pierre Villon, P, Computational Mechanics Volume 10, pp 307-318, 1992

External links

An As-Short-As-Possible Introduction to the Least Squares, Weighted Least Squares and Moving Least Squares Methods for Scattered Data Approximation and Interpolation

This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Moving least squares

Definition

See also

References

External links