Moving least squares

From HandWiki

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.


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

Consider a function [math]\displaystyle{ f: \mathbb{R}^n \to \mathbb{R} }[/math] and a set of sample points [math]\displaystyle{ S = \{ (x_i,f_i) | f(x_i) = f_i \} }[/math]. Then, the moving least square approximation of degree [math]\displaystyle{ m }[/math] at the point [math]\displaystyle{ x }[/math] is [math]\displaystyle{ \tilde{p}(x) }[/math] where [math]\displaystyle{ \tilde{p} }[/math] minimizes the weighted least-square error

[math]\displaystyle{ \sum_{i \in I} (p(x_i)-f_i)^2\theta(\|x-x_i\|) }[/math]

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

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

See also


External links