Moving least squares


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.

Contents

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 = {(xi,fi) | f(xi) = fi} where x_i \in \mathbb{R}^n and the fi'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)-f_i)^2\theta(\|x-x_i\|)

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

In the example \theta(s) = e^{-s^2}.

See also

References

External links