A quick how-to on fitting to points in a neighborhood.
Least squares
The basic idea of least squares to fit a function f(x,y)=z to observations (xi, yi, zi) is to make the unknowns be coefficients of some basis involving x, y, 1 (such as x^2,xy,y^2,x,y,1 for quadratics). By filling in a matrix M with the basis elements for the observations, we get M c = z with one row per observation.
The least squares solution minimizes (Mc)^T*Mc by letting c be the solution of (M^T M)c = M^t z. MATLAB will compute this as c = M\z; The residual is then Mc - z, and the solution minimizes sum((Mc-z).^2).
Orthogonal Regression Plane
To find the best fit plane when the residual is measure orthogonally, as distance from the plane, is a simple eigenvector problem, solvable with the singular value decomposition of a 3x3 correlation matrix.
A simple writeup at
Dr. Math
In MATLAB, we can write:
function [resid, n, pt, Q] = bestPlane(P)
% for a given list of points P, find the residual vectors to the best fit plane.
% The plane passes through pt and has normal n; the points project to Q
pt = mean(P);
for i=1:3 % subtract mean
P(:,i) = P(:,i) - pt(i);
end
[u,s,v] = svd(P'*P);
n = v(3,:)'; % plane normal is eigenvector with smallest eigenvalue
resid = (P*n); % project onto n
Q = P;
for i = 1:3
Q(:,i) = P(:,i) - resid*v(3,i);
end
Techniques from recent papers
Poisson fitting
Two papers by
Hoppe: The idea is to use normal information attached to points to compute a function on space that is positive inside and negative outside the object, then to compute a level set at 0. Such objects are watertight by construction. This type of surface is more robust to noise in the data.
- mlstream.pdf Multi-level streaming for out-of-core surface reconstruction, M. Bolitho, M. Kazhdan, R. Burns, H. Hoppe, Symposium on Geometry Processing 2007.
- poissonrecon.pdf Symposium on Geometry Processing 2006.
The UPC data comes from planes where we could get the plane location and use that to determine what is outside. (Reflections would be problematic.)
Moving least squares
- unified_mls.pdf: moving least squares for surface fitting paper by Claudio Silva.
Moving-Least Squares (MLS) surfaces are a popular way to define
a smooth surface from a set of unorganized points. In this paper
we introduce a unified MLS projection consisting of the confluence
of several different ideas, each of which independently enhances
current MLS strategies or ameliorates MLS deficiencies. We begin
by elucidating the shortcomings of the two-phase minimization
procedure proposed by Levin [2003]. We show that there are cases
intrinsic to the geometry of the underlying surface from which the
points are sampled where Levin’s projection fails to find an adequate
approximation. These shortcomings occur regardless of sampling
density or the amount of noise. Our formulation solves this
problem by directly fitting a local approximating function to the
surface using a unified minimization scheme. Our scheme can be
used to create different families of MLS surfaces, depending on the
function space used for the fit. This allows specific priors to be
used in the approximation, leading to better reconstructions. We
present experimental results that show our technique performs well
in a wide range of conditions.
- LEVIN, D. 2003. Geometric Modeling for Scientific Visualization. Springer-Verlag,
ch. Mesh-independent surface interpolation, 37–49.
Mesh segmentation
This was presented at SPM as a simple algorithm to split a mesh up into surface patches with similar characteristics. I have the proceedings if this link doesn't work.
--
JackSnoeyink - 04 Jun 2008
to top