Fitting Smooth Manifolds to Point Clouds in a Level Set Formulation

Abstract

Since its inception, curves and surfaces have been the principal means of representation of observed geometry in computer vision. In many practical applications, one’s knowledge of the shapes of real-life objects is obtained through discrete measurements, which are subsequently converted into their continuous counterparts through the process of either curve or surface fitting, depending on the object dimensionality. Unfortunately, the measurement noise due to environmental effects, operator errors and/or hardware limitations makes the fitting problem a challenging one, requiring its solutions to possess a substantial degree of robustness. Moreover, in the case of surface fitting, the use of relatively complex fitting mechanisms might be disadvantageous due to their typically higher computational requirements, which could, in turn, create an implementation bottleneck due to the high dimensionality of the data. Accordingly, in this work, we propose a unified approach to fitting of smooth geometric manifolds, such as curves and surfaces, to point clouds. The proposed method is based on a level-set formulation, which leads to a simple and computationally efficient algorithm, the practical value of which is demonstrated through a series of examples.

1 Introduction

The problem of fitting of smooth geometric manifolds, such as spatial curves and surfaces, to finite sets of Euclidean points is unarguably one of the classical problems of image processing and computer vision. Such sets of points, commonly referred to as point clouds, are typically acquired by means of range/depth sensors to provide a raw description of the shape and geometry of scanned objects. Due to their irregular and noisy nature, however, point clouds are rarely used by higher level algorithms and visualization software. Instead, the latter “prefer” to process continuous representations of observed geometries, which are derived from point clouds through the process of curve/surface fitting. Virtual and augmented reality, reverse engineering, and medical imaging are only a few examples of application areas, where such fitting problems routinely arise [1]. Moreover, the recent advance in digital scanning technologies has resulted in a widespread proliferation of a variety of new depth/range scanning devices, which often present unexplored challenges from the viewpoint of curve/surface fitting. To cope with these challenges, a broad spectrum of fitting methodologies has been so far proposed [2], which generally differ in their ability to withstand the effects of noise and scarce sampling as well as to effectively deal with non-trivial topologies [3].

The current arsenal of methods for curve/surface fitting is vast, suggesting a variety of possible taxonomies. A particular way to classify such methods could be based on their property of being either explicit or implicit [4]. In the explicit formulation, it is standard to represent surfaces by means of triangulated meshes obtained based on Voronoi diagrams [5] or Delaunay triangulation [6]. In their core, such methods are based on systematically connecting the points of a cloud until a predefined completeness criterion is met. Under weak noise conditions and in the absence of considerable gaps between data points, explicit representations are known to provide satisfactory and useful results. Unfortunately, their quality degrades quickly when the aforementioned assumptions start to fail.

In implicit representation, curves and surfaces are typically defined by means of either the indicator functions of closed subsets of or the level sets of Lipschitz-continuous functions [3, 7]. Thus, for instance, the fitting procedure in [8] utilized the zero level-set of a distance function, in which case it was also possible to determine the topological types of reconstructed surfaces. While promising in many respects, however, the method lacked in geometric accuracy. In [9], the same group of authors introduced an accurate surface model for unorganized point data. Unfortunately, this work provided little evidence on the performance of the proposed method in the case of incomplete and irregularly sampled data [10]. A method called Poisson Surface Reconstruction was introduced in [11] based on the observation that the normal field of the boundary of a solid can be interpreted as the gradient of the indicator function of a surface, which can, in turn, be used to model this surface in an implicit manner. Further modifications of this method were described in [12], including its adjustments to the case of sparse point clouds and improvements of computational efficiency. An interesting method exploiting the underlying geometric structure of point clouds in combination with a convex formulation of image segmentation was described in [3]. The method has been shown to perform reliably under a variety of conditions, including scenarios with incomplete/scarce data and complex topologies. Yet, to achieve such performance, one requires to possess prior information in the form of point normals, which might not always be available. Finally, a surface fitting formulation based on the concept of function approximation by means of Radial Basis Functions (RBF) was reported in [13]. In addition to its other merits, the method was also shown to be computationally efficient, which makes it particularly valuable when dealing with large data sets [14].

The level-set framework, in which curves and surfaces are defined in terms of the level-set of Lipschitz-continuous functions, offers a number of critical advantages, among which are the simplicity of parameterization and the ability to deal with relatively complex topologies in an easy and straightforward manner. The practical implementation of such methods in the context of curve/surface fitting, however, may be rather challenging, thereby risking to put these methods in disadvantage with respect to other techniques. Accordingly, the main purpose of this work is to introduce a level-set based formulation of the problem of curve/surface fitting which offers two important advantages. First, the formulation is independent of the problem dimensionality, and it can be applied in the cases of curve and surface fitting with virtually no adjustments. Second, the formulation leads to a particularly simple and computationally efficient solution, which allows its application in both time-critical and data-extensive scenarios.

The rest of this paper is organized as follows. Sections 2 and 3 provide a formal description of the fitting problem and its solution, respectively. Experimental results with 2D and 3D point clouds are presented in Sect. 4, followed by a discussion and conclusions in Sect. 5.

2 Problem Formulation

Let be a Lipschitz-continuous function (with $d=2$ and $d=3$ corresponding to the cases of curve and surface fitting, respectively), whose zero level set

will be used to model the geometric manifold of interest (i.e., either a curve or a surface). In particular, in what follows, the level-set function $\phi (\mathbf{r})$ will be defined to be the signed distance function (SDF) of the zero level-set $\varGamma$ of $\phi$. Such SDF is given by the unique solution of Eikonal equation

with $\nabla \phi$ standing for the gradient of $\phi$ and $|\nabla \phi (\mathbf{r})|$ being its magnitude at $\mathbf{r}$.

By the nature of its definition, the value $\phi (\mathbf{r})$ of an SDF $\phi$ returns the distance between $\mathbf{r}$ and the zero-level set $\varGamma$. Thus, given a set of N points $\{\mathbf{r}_i\}_{i=1}^N$, the average cumulative distance between the point cloud and $\varGamma$ can be computed as

$$\begin{aligned} D(\phi ) = \frac{1}{N}\sum _{i=1}^{N} | \phi (\mathbf{r}_i) |, \end{aligned}$$

(1)

where the absolute value is used to cancel out the effect of the sign of $\phi$ (which we assume to have negative values inside $\varGamma$). Clearly, the closer the points $\mathbf{r}_i$ to $\varGamma$, the lower the value of $D(\phi )$. Consequently, the fitting problem at hand can be formulated as a minimization problem in $\phi$, whose optimal solution returns the minimum possible value of $D(\phi )$.

An obvious flaw of the above approach consist in its proneness to the “curse of dimensionality”. Indeed, in an attempt to minimize $D(\phi )$, the optimization is likely to result in a solution with an excessively variable, fluctuating $\varGamma$ which might contradict the physical nature of the object represented by the point cloud. Such situations are particularly frequent in the case of noisy and/or incomplete (scarce) measurements, which necessitates the use of regularization. To this end, it has been proven effective to penalize the area of $\varGamma$, which (owing to the co-area formula), amounts to requiring the SDF $\phi$ to be a function of bounded variation (BV) [19]. Such functions are known to have relatively small values of their total-variation (TV) semi-norms defined as

(2)

Subsequently, to guarantee the zero level-set $\varGamma$ (and, hence, the resulting manifold) has a plausible configuration, the minimization of $D(\phi )$ should be restricted to the functions with relatively small values of TV semi-norms, which leads to an optimization problem of the form

$$\begin{aligned} \min _{\phi } \left\{ D(\phi ) + \lambda \Vert \phi \Vert _\mathrm{TV} \right\} , \end{aligned}$$

(3)

where $\lambda > 0$ is a user-defined regularization constant. Denoting the cost functional in (3) by $E(\phi )$, namely $E(\phi ) := D(\phi ) + \lambda \Vert \phi \Vert _\mathrm{TV}$, its (local) minimizers $\phi ^*$ are characterized by the Euler-Lagrange condition

$$\begin{aligned} \frac{\delta E (\phi ^*)}{\delta \phi } = 0, \end{aligned}$$

(4)

with $\delta E /\delta \phi$ being the first variational derivative of $E(\phi )$. A particularly simple and computationally efficient solution to the above equation is detailed in the following section.

3 Proposed Solution

A solution to the Euler-Lagrange equation (4) can be found as a stationary point of the gradient flow given by [15]

$$\begin{aligned} \frac{\partial \phi }{\partial t} = - \frac{\delta E (\phi )}{\delta \phi }, \end{aligned}$$

(5)

where $t > 0$ is an artificial time that can be thought of as a continuous equivalent of an iteration index. Thus, to implement the gradient flow, the first variational derivative $\delta E /\delta \phi$ needs to be computed first. To this end, one can first redefine $D(\phi )$ as

$$ D(\phi ) = \frac{1}{N}\sum _{i=1}^{N} | \phi (\mathbf{r}_i) | = \frac{1}{N}\sum _{i=1}^{N} \int | \phi (\mathbf{r}) | \, \delta (\mathbf{r}- \mathbf{r}_i) \, d\mathbf{r}= \int | \phi (\mathbf{r}) | \, g_N(\mathbf{r}) \, d\mathbf{r}$$

with

$$ g_N(\mathbf{r}) = \frac{1}{N}\sum _{i=1}^{N} \delta (\mathbf{r}- \mathbf{r}_i) $$

and $\delta (\mathbf{r})$ be the standard Dirac delta function. In this case, the first variational derivative of $D(\phi )$ can be shown to have the form of

$$ \frac{\delta D (\phi )}{\delta \phi } = \mathrm{sign (\phi )} \cdot g_N, $$

where we have adopted the sign function, $\mathrm{sign}(x)$, as a practical approximation of the first-order derivative of |x|. On the other hand, the first variational derivative of $\Vert \phi \Vert _\mathrm{TV}$ is well known to be equal to $- \mathrm{div} (\nabla \phi /| \nabla \phi |)$, with div standing for the operator of divergence. Therefore, combining the two results leads to

$$\begin{aligned} \frac{\delta E (\phi )}{\delta \phi } = \mathrm{sign (\phi )} \cdot g_N - \lambda \, \mathrm{div} (\nabla \phi /| \nabla \phi |), \end{aligned}$$

(6)

and, subsequently, to the gradient flow of the form

$$\begin{aligned} \frac{\partial \phi }{\partial t} = \lambda \, \mathrm{div} (\nabla \phi /| \nabla \phi |) - \mathrm{sign (\phi )} \cdot g_N. \end{aligned}$$

(7)

The next step is to discretize (7), to which end we take advantage of a semi-implicit approach to produce

$$ \frac{\phi _{t + \varDelta t} - \phi _t}{\varDelta t} = \lambda \, \mathrm{div} (\nabla \phi _{t + \varDelta t} /| \nabla \phi _{t + \varDelta t} |) - \mathrm{sign (\phi _t)} \cdot g_N, $$

where $\phi _t$ and $\phi _{t + \varDelta t}$ denote the values of $\phi$ at times t and $t + \varDelta t$, respectively. Thus, rearranging the terms in the above numerical approximation, one obtains

$$\begin{aligned} \phi _{t + \varDelta t} - (\lambda \varDelta t) \, \mathrm{div} (\nabla \phi _{t + \varDelta t} /| \nabla \phi _{t + \varDelta t} |) = \phi _t - \varDelta t \, \mathrm{sign (\phi _t)} \cdot g_N. \end{aligned}$$

(8)

To conclude the derivations, we recall that any real subdifferentiable functional with a monotone subdifferential (where $\mathcal {X}$ is the Banach space to which $\phi$ is supposed to belong, such as the space of BV functions in our case) can be associated with its proximal map $\mathrm{prox}_{F}: \mathcal {X} \rightarrow \mathcal {X}$ defined as [16]

$$\begin{aligned} \mathrm{prox}_{F}(\psi ) = \arg \inf _{\phi \in \mathcal {X}} \left\{ \frac{1}{2} \Vert \phi - \psi \Vert _2^2 + F(\phi ) \right\} . \end{aligned}$$

(9)

In the special case when $F(\phi ) = \tau \Vert \phi \Vert _\mathrm{TV}$, with some $\tau > 0$, one has

$$\begin{aligned} \mathrm{prox}_{\tau \Vert \cdot \Vert _\mathrm{TV}}(\psi ) = \arg \inf _{\phi \in \mathcal {X}} \left\{ \frac{1}{2} \Vert \phi - \psi \Vert _2^2 + \tau \Vert \phi \Vert _\mathrm{TV} \right\} , \end{aligned}$$

(10)

which is always well-defined due to the strict convexity of its associated cost functional. Although this operator does not admit a closed-form definition, there are a number of numerical procedures that can be used to compute $\mathrm{prox}_{\tau \Vert \cdot \Vert _\mathrm{TV}}$ in a computationally efficient manner [17, 18]. It is worthwhile noting that, in the context of image processing, finding efficient numerical methods for computation of $\mathrm{prox}_{\tau \Vert \cdot \Vert _\mathrm{TV}}$ dates back to the seminal work in [19] that pioneered the field of TV-denoising.

Now, having the proximal map (10) defined, it can be shown that the update equation in (8) can be alternatively defined as

$$\begin{aligned} \phi _{t + \varDelta t} = \mathrm{prox}_{ (\lambda \varDelta t) \Vert \cdot \Vert _\mathrm{TV} } \left\{ \phi _t - \varDelta t \, \mathrm{sign (\phi _t)} \cdot g_N \right\} . \end{aligned}$$

(11)

Consequently, starting from some initial curve/surface $\varGamma$ associated with $\phi _0 = \phi _{t = 0}$, an optimal solution to the problem of curve/surface fitting in the sense of minimum cumulative distance can be computed as a stationary point of the sequence of fixed-point iterations (i.e., recursive re-substitutions) produced by

$$\begin{aligned} \phi \mapsto T_{\lambda , \varDelta t} \{ \phi \}, \end{aligned}$$

(12)

where $T_{\lambda , \varDelta t}: \mathcal {X} \rightarrow \mathcal {X}$ stands for the composition of the proximal map $\mathrm{prox}_{ (\lambda \varDelta t) \Vert \cdot \Vert _\mathrm{TV}}$ with the simple non-linear map defined by $I - \varDelta t \mathrm{sign}(\cdot ) \cdot g_N$. In practice, we replace $g_N$ with its smooth approximation $g_{N,\sigma }$ obtained via spatial convolution with a normalized, isotropic Gaussian kernel $G_\sigma$ of standard deviation $\sigma$, viz.

In practice, such sums can be computed efficiently, e.g., by first uniformly quantizing the values of $\mathbf{r}_i$ to the vertices of a (sufficiently dense) rectangular lattice, and then performing the summation in the domain of a discrete Fourier transform (DFT), followed by an inverse Fourier transformation.

It is interesting to notice that the map $x \mapsto x - \varDelta t \, \mathrm{sign}(x) a$, with $0 \le a \le 1$, is neither linear nor monotone, and, what is more important, it does not preserve the sign of x. Thus, applying this map to an SDF $\phi$ may, in general, forfeit the fundamental property of such $\phi$ to have values of opposite signs on both sides of its zero-level set. To avoid this undesirable effect, it has proven useful to replace the above map by soft thresholding $S_{\varDelta t g_{N, \sigma }}(x) := \max (|x| - \varDelta t \, g_{N, \sigma }, 0) \cdot \mathrm{sign}(x)$ which, similarly to the former, reduces the positive values of $\phi$, while increasing the negative values of $\phi$ by $\varDelta t \, g_{N, \sigma }$. (In some sense, both maps try to “shorten the distance” to points $\mathbf{r}_i$, which are represented by the “peaks” of $g_{N, \sigma }$.) However, $S_{\varDelta t g_{N, \sigma }}$ provides the additional advantage of continuity, while keeping the sign of its argument intact.

In practical computations, we used $\varDelta t \in (0, 1]$, while adapting $\sigma$ recursively according to $\sigma \mapsto \beta \sigma$, starting with some initial $\sigma > 0$ and a predefined $0.9< \beta < 1$. In this case, the proposed numerical scheme acquires the flavor of a multi-grid method. Particularly, in the beginning of iterations (when $\sigma$ is still relatively large) the intermediate solutions are predominantly effected by a rough collective configuration of the data points as a cloud, while becoming more and more responsive to the individual forces of each point $\mathbf{r}_i$ towards convergence. To summarize, the final algorithm can be described by the pseudo-code shown below.

Note that, for any value of $\varDelta t$, $S_{\varDelta t g_{N,\sigma }}$ is guaranteed to be a contraction, which, in conjunction with the contractiveness of the proximal map, suggests that the sequence of solutions produced by $\phi \mapsto T_{\lambda , \varDelta t}\{\phi \}$ always converges to a stationary point. However, for any given $\phi$, its corresponding $T_{\lambda , \varDelta t}\{\phi \}$ does not yield an SDF, in general. For this reason, the above pseudo-code has been augmented with the procedure of redistancing ReDist, which effectively replaces a given $\phi \in \mathcal {X}$ with an SDF that has a zero-level set $\varGamma$ identical to that of $\phi$¹. Even thought such mapping may not always be contractive, from the practical point of view, the proposed algorithm has never failed to converge in a relatively small number of iterators (see below), under broad experimental conditions.

4 Experimental Results

The proposed method has been tested on a dataset of both 2D and 3D artificial point clouds. In the course of evaluations, the algorithm’s performance was tested under a variety of different experimental conditions, as defined by various levels of measurement noise, the presence of skewness in the distribution of $\{\mathbf{r}_i\}_{i=1}^{N}$ and various fractions of data points assumed to be missing.

In our experiments, the original geometric manifolds (i.e., curves and surfaces) were used as the mean values around which the cloud points $\mathbf{r}_i$ had then been randomly distributed. To this end, we used a centered uniform distribution in conjunction with an offset to emulate the effect of asymmetric sampling. In all the experiments, $\phi _0$ was computed by fast matching initiated at the boundary of the convex hull of its associated data cloud. The values of $\lambda , \varDelta t, \sigma$, and $\beta$ were set to be equal to 100, 0.95, 0.03, and 0.99, respectively. All coding and simulations were performed in MATLAB (Mathworks Inc, version R2018b).

Fig. 1.

Results applying the proposed algorithm to 2D “noisy” point clouds. (a) optimal solution after 10 iterations, (b) optimal solution after 30 iterations. The blue and red colors correspond to the initial and final solutions, respectively. (Color figure online)

Fig. 2.

Results analogous to Fig. 1 obtained in the case of asymmetric data sampling.

In the case of symmetric sampling in 2D (i.e., when the number of planar data points is approximately equal on both sides of the original curve), some representative results obtained using the proposed method are shown in Fig. 1, with Fig. 2 showing analogous results for the case of asymmetric sampling. One can see that, in all the cases, the proposed algorithm has managed to converge to the expected shapes just in a few tens of iterations.

To quantitatively evaluate the proposed algorithm, a distance between the original and fitted manifolds has been computed. In each case, the distance was defined to be the average distance between the points on the fitted manifold and its continuous counterpart. To facilitate the computation of the distances, the original manifolds were chosen to be

• a circle (radius 50), an oval (max radius 50, axis ratio 1:0.5), and a square (side length 100), in the case of $d=2$,

• a sphere (radius 50) and an ellipsoid (max radius 50, axis ratio 1:1:0.5), in the case of $d=3$.

The conditions of asymmetric sampling were emulated by sub-sampling the data points on one size of a given manifold by a factor of 2. Moreover, the data points were further subjected to random removals of their localized subsets to imitate the effects of “holes”. Finally, all data points were contaminated by additive Gaussian noise with different values of its standard deviation $\sigma _n$.

Table 1. Empirical mean cumulative errors (average ± 1 standard deviation)

Table 1 summarizes the results of present quantitative analysis, showing the values of mean cumulative distance for different types of manifolds as well as the values of N and $\sigma _n$. Each entry in Table 1 has been computed as an average of 10 independent trials. As expected, the noisy scenarios with higher extents of skewness and incompletion in measurements results in higher values of the errors. A relative increase of the error can also be observed in the case of square, due to the non-smoothness of its shape. Overall, however, the proposed method demonstrated a stable and reasonably accurate performance. A sample results of surface and curve fitting is shown in Fig. 3.

Fig. 3.

Results of fitting the sphere surface and the square curves.

5 Conclusion

In this paper, a simple numerical method for fitting closed curves and surfaces of various topologies to points clouds has been presented. The proposed numerical solution was based on implicit discretization, which allows using substantially larger time steps $\varDelta t$ (as opposed to explicit schemes), thus improving the rate of convergence. Moreover, the proposed formulation is parameter-free, offering the same unified algorithmic structure in both 2D and 3D settings.