Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method

doi:10.1006/cviu.2000.0875

Computer Vision and Image Understanding

Volume 80, Issue 3, December 2000, Pages 295-314

https://doi.org/10.1006/cviu.2000.0875 Get rights and content

Abstract

In this paper we consider a fundamental visualization problem: shape reconstruction from an unorganized data set. A new minimal-surface-like model and its variational and partial differential equation (PDE) formulation are introduced. In our formulation only distance to the data set is used as our input. Moreover, the distance is computed with optimal speed using a new numerical PDE algorithm. The data set can include points, curves, and surface patches. Our model has a natural scaling in the nonlinear regularization that allows flexibility close to the data set while it also minimizes oscillations between data points. To find the final shape, we continuously deform an initial surface following the gradient flow of our energy functional. An offset (an exterior contour) of the distance function to the data set is used as our initial surface. We have developed a new and efficient algorithm to find this initial surface. We use the level set method in our numerical computation in order to capture the deformation of the initial surface and to find an implicit representation (using the signed distance function) of the final shape on a fixed rectangular grid. Our variational/PDE approach using the level set method allows us to handle complicated topologies and noisy or highly nonuniform data sets quite easily. The constructed shape is smoother than any piecewise linear reconstruction. Moreover, our approach is easily scalable for different resolutions and works in any number of space dimensions.

References (30)

N. Amenta et al.
The crust and the β-skeleton: Combinatorial curve reconstruction
Graph. Models Image Process
(1998)
A. Hilton et al.
Implicit surface-based geometric fusion
Comput. Vision Image Understand.
(1998)
S. Osher et al.
Fronts propagating with curvature dependent speed, algorithms based on a Hamilton–Jacobi formulation
J. Comput. Phys.
(1988)
D. Peng et al.
A PDE based fast local level set method
J. Comput. Phys.
(1999)
M. Sussman et al.
A level set approach for computing solutions to incompressible two-phase flows
J. Comput. Phys.
(1994)
H. Zhao et al.
A variational level set approach to multiphase motion
J. Comput. Phys.
(1996)
H. Zhao et al.
Capturing the behavior of bubbles and drops using the variational level set approach
J. Comput. Phys.
(1998)
L. Alvarez et al.
Axioms and fundamental equations of image processing
Arch. Ration. Mech. Anal.
(1993)
N. Amenta, and, M. Bern, Surface reconstruction by Voronoi filtering, in, 14th ACM Symposium on Computational Geometry,...
N. Amenta et al.
A new Voronoi-based surface reconstruction algorithm
Proc. SIGGRAPH'98
(1998)

C. Bajaj et al.

Automatic reconstruction of surfaces and scalar fields from 3D scans

SIGGRAPH'95 Proceedings

(July 1995)

M. Bloor et al.

Using partial differential equations to generate free-from surface

Comput. Aided Geom. Design

(1990)

J.D. Boissonnat

Geometric structures for three dimensional shape reconstruction

ACM Trans. Graphics

(1984)

J. D. Boissonnat, and, F. Cazals, Smooth shape reconstruction via natural neighbor interpolation of distance functions,...

Cited by (268)

Efficient numerical methods for models of evolving interfaces enhanced with a small curvature term
2024, Computers and Mathematics with Applications
The aim of this paper is to propose an Eulerian type of numerical finite difference approximation on structured grids for an advection dominated level set equation enhanced with a small curvature term. The proposed numerical scheme is based on upwind discretization in both the advection and the curvature term. This class of approximations is used in algebraic solvers, such as fast sweeping or fast marching methods, which respect the causality of solutions for which any information is propagating along characteristics, in order to solve the algebraic system in a finite number of computationally simple iterations or updates. An implicit numerical scheme for a time relaxed level set equation with non-zero right-hand side is used in this paper and solved by a nonlinear fast sweeping method. The results of the von Neumann stability analysis of the proposed scheme are presented, and numerical examples are used to verify the analysis.
Robust moving total least squares: A technique for the reconstruction of measurement data in the presence of multiple outliers
2022, Mechanical Systems and Signal Processing
This article is concerned with the reconstruction of contaminated measurement data based on the moving total least squares (MTLS) method, which is extensively applied to many engineering and scientific fields. Traditional MTLS method is lack of robustness and sensitive to the outliers in measurement data. Based on the framework of MTLS method, we proposed a robust MTLS method called RMTLS method by introducing a two-step pre-process to detect and remove the anomalous nodes in the support domain. The first step is an iterative regression procedure that combines with k-medoids clustering to automatically reduce the weight of anomalous node for a regression-based reference (curve or surface). Based on the distances between reference and discrete points, the second step adopts a density function defined by a sorted distance sequence to select the normal points without setting a threshold artificially. After the two-step pre-process, weighted total least square is performed on the selected point set to obtain the estimation value. By disposing of the anomalous nodes in each independent support domain, multiple outliers can be suppressed within the whole domain. Furthermore, the suppression of multiple continual outliers is possible by adopting asymmetric support domain and introducing previous estimation points. The proposed method shows great robustness and accuracy in reconstructing the simulation and experiment data.
Meso-scale modelling of the thermo-mechanical response for concrete with complex-shaped aggregates in early age
2022, Construction and Building Materials
Self-restraint stress produced in early age is a matter of interest associated with cracking of concrete. Mesoscopic modelling nowadays is one of the effective approaches to investigate internal stresses, deformation, damage of concrete at much smaller scale. However, grid discretization and mesoscopic properties calibration are still challenging issues that prevent fast pre-processing and require extremely dense meshes for accurate solutions. In this paper, a thermo-mechanical model required only regular-element discretization is proposed by developing a diffuse meshing technique to analyze the evolution of self-restraint stress. Cross-scale numerical validations are carried out to calibrate the mesoscopic parameters, along with verifying the feasibility of the proposed model. Furthermore, the effect of simplified aggregate mesostructure on the thermo-mechanical behavior of concrete is evaluated through comparisons with the results obtained by considering complex-shaped aggregate using the proposed diffuse element model. The results show the thermo-mechanical mismatch between different components is the main reason for producing the self-restraint stress, and aggregate meso-structure have nonnegligible influence on the global response or local behavior.
Implicit fast sweeping method for hyperbolic systems of conservation laws
2021, Journal of Computational Physics
Implicit time-accurate methods are often used to integrate stiff problems where explicit schemes impose severe time step restrictions. This paper presents an efficient numerical framework based on the fast sweeping method (FSM) for solving linear and nonlinear hyperbolic systems of conservation laws. The solution at each discrete location is computed by sweeping the numerical domain in several predetermined directions that follow the causality of the characteristic families. The use of a fractional step strategy eliminates the need for a solution selection criterion while one-sided stencils limit the number of sweeps to at most $2^{d}$ for d space dimensions. This work focuses on the first-order implicit upwind method since it constitutes the building block for high-order conservative schemes. For problems where the degree of stiffness evolves over time, implicit-explicit hybridization can be accomplished with the same algorithm by simply switching the stencil at each time level. As opposed to traditional implicit solvers, the sweeping method does not require a local time linearization of the fluxes thereby preserving the nonlinear stability properties of the original implicit scheme. It also avoids the large computational and memory requirements associated with solving large block-diagonal systems of equations. A series of one- and two-dimensional test cases are presented for the inviscid Burgers' equation and the reactive Euler equations. The results indicate that the implicit FSM can allow for a major reduction in the number of time steps even in the presence of discontinuous solution profiles.
Sparse-Grid Implementation of Fixed-Point Fast Sweeping WENO Schemes for Eikonal Equations
2024, Communications on Applied Mathematics and Computation
Multichannel segmentation of planar point clouds using evolving curves
2023, Computational and Applied Mathematics

View all citing articles on Scopus

^f1: [email protected]

¹: Research supported by NSF DMS-9706566.

²: Research supported by NSF and DARPA under Grants NSF DMS-9706827 and NSF DMS-9615854.

View full text

Regular ArticleImplicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method

Abstract

Graph. Models Image Process

Comput. Vision Image Understand.

J. Comput. Phys.

J. Comput. Phys.

J. Comput. Phys.

J. Comput. Phys.

J. Comput. Phys.

Axioms and fundamental equations of image processing

Arch. Ration. Mech. Anal.

A new Voronoi-based surface reconstruction algorithm

Proc. SIGGRAPH'98

Automatic reconstruction of surfaces and scalar fields from 3D scans

SIGGRAPH'95 Proceedings

Using partial differential equations to generate free-from surface

Comput. Aided Geom. Design

Geometric structures for three dimensional shape reconstruction

ACM Trans. Graphics

Regular Article
Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method