Code on Github. Slides (in french; for a course project)

There are a number of “open” problems in curve/surface reconstruction, such as reconstructing self-intersections, quantifying uncertainty and topological guarantees in the presence of noise.

In the computer graphics/CAGD litterature, it is often assumed that the set of observed points forms a dense exact sample from the object of interest. Topological properties of reconstruction algorithms are then analysed from this deterministic point of view. However, this framework is difficult to adapt to the presence of noise and can at best provide a sampling theory for -neighbourhoods.

The “implicit” approaches to reconstruction supposes the existence of a smooth function modelling the object of interest as the level set . If the observed points also carry gradient information, then there is hope that we may approximate in a neighbourhood of the curve. In fact, as I show in this post (a particular case of the Nash-Tognoli theorem), approximating both and its gradient in the sup norm entails the ability to approximate the surface in the Hausdorff + diffeomorphic topology of compact manifold space. Somewhat similar ideas have been exploited in Kolluri (2008) to obtain topological guarantees for a *moving least squares* implicit method of reconstruction.

There has also been a few statistical approches to the problem (e.g. Gu et al. (2014)). Those I am aware of, while pertinent and original, do not bring considerably more profound insight. Likelihood based inference currently seems to bring more computational and theorical difficulties than solutions.

**Ideas and brainstorming:**

*How can we assess wether a reconstruction has been successful?*Assume we are trying to reconstruct a smooth manifold and let be the reconstructed curve (or hypersurface). Let be the normal function (i.e. is a unit normal to at the point ). We may be given a credible region for as the set where quantifies pointwise normal uncertainty. Points in that are closest to more than one point on may be considered problematic: their existence entails that some plausible deformations of (as defined by ) are not manifolds.*How can we reconstruct self-intersections?*I’d like to try this: where is parametrized by arc length and constrained to a suitable space of curves, and where is a regularization parameter. This is sort of an orthogonal regression with total curvature penalty. The real issue here is figuring out if this can be solved reasonably efficiently.*Fused ridge implicit reconstruction.*Solve . Here we may restrict to be a polynomial of known degree. I don’t know if this would work well. Maybe can be more easily approximated here using the gradient of .

[…] Closed curve reconstruction with periodic splines, fused ridge and a traveling salesman. […]