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

${\displaystyle \sum _{i\in I}(p(x_{i})-f_{i})^{2}\theta (\|x-x_{i}\|)}$

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

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