Convergent Metrics for Digital Calculus – CoMeDiC

The general idea is to define well-chosen metrics for discrete calculus that make it converge toward continuous values. This approach is now becoming possible due to recent advances in digital geometry on multigrid convergent estimators. Digital calculus then addresses variational problems involving domains such as digital surfaces, curves, graphs living in a higher dimensional ambient space, as well as problems involving discontinuities or subtle boundary conditions. This project addresses theoretical problems like the definition of a sound digital calculus, the study of appropriate estimators for metrics, the statement of convergence properties. It is also concerned with its efficient numerical implementation. It studies variational problems that present difficulties to standard numerical methods, such as problems with discontinuities or free boundaries, or problems involving domains of codimension greater or equal to one as surfaces or curves. Lastly, this project focuses on three domains of application for digital calculus — image analysis, digital geometry processing and shape optimization — both to guide and nourish theoretical developments, as well as to serve as testbed for digital calculus.

The team gathers mathematicians and computer scientists, with
expertises in variational modeling, discrete calculus, digital
geometry, shape optimisation, geometric measure theory, image analysis
and geometry processing.

1 Digital Calculus : convergence, variational models, computation issues

1.1 Metric definitions and convergence of digital operators

- Convergent Laplace-Beltrami operator on digital surfaces [CCLR16, CCLR17]
- Computation of the normal vector to a digital plane by local plane-probing [LPR17]
- Gauss digitization and integration over digital surfaces [LT16]
- Digital normal and curvature estimators by integral invariants [LCL17]

1.2 Adaptation of variational problems to digital calculus

- Discretization of Ambrosio-Tortorelli functionnal by discrete calculus [FLT16a,CFGL16]
- Identification of optimal shapes for spectral problems in dimension 4 [AO17]
- Optimal partitions optimales for manifold lengths by phase-field method [BO16]
- Optimisation of geometric objects under variational formulation, regularity and geometry [DPMSV16,MTV17,MPLPV] and uncertainty formulations [BV]

1.3 Performance issues in digital calculus

- Discrete Exterior Calculus package in open-source DGtal library (dgtal.org)
- image restoration tool based on discrete calculus with a reproducible research label [FLT16b]

2 Applications of digital calculus to various variational problems

2.1 Digital calculus for image analysis

- Piecewise smooth regularization for image restoration with AT functional [FLT16a]
- Morphological and geodesic filters preserving image edges [DCDSN17]

2.2 Digital calculus for geometry processing

- Biclustering for non-isometric shape matching [GSTOG16]
- Anisotropic regularization of normal vector field over digital surfaces with AT functional [CFGL16]
- Digital confidence map for the reconstruction of tubular objects from partial or damaged scans [KKDR16a,KKDR16b]

2.3 Digital calculus for shape optimisation

- Discretization of the Eucliden Steiner tree problem [BOO16]
- Numerical calibration of optimal Steiner trees [MOV17]
- Construction of reflectors with constraints by optimal transport [dCMT16]

Outstanding features:

The DGtal project (http://dgtal.org), a library and set of tools for digital geometry, has received the « software award » at the prestigious Symposium on Geometry Processing 2016 (June 20th-24th, 2016, Berlin). The price acknowledge a high quality open-source software dedicated to the geometry processing of shapes. The collaborative DGtal project has become crucial in the international digital geometry community with many contributions from various teams in this topic.

Perspectives:

We are working both on the fundamental aspects of digital calculus and on its possible fields of applications. For instance, we study several forms of convergence, some based on normal currents et on the convergence of discrete forms, some others based on the convergence of operators or specific variational problems. Numerical issues are also studied, for instance with multi-scale approaches.
Concerning applications, we are studying how discrete calculus can be used to regularize discrete objects so as to achieve linear reconstructions that are close both in terms of positions and in terms of normals to their associated continuous objects. Along the same lines, we examine how we can inject lengths and curvatures into variational problems in 2D and 3D image processing methods, while trying to limit the combinatorial explosion of existing approaches. Last, we look at how classical Euclidean shape optimisation problems can be discretized, namely the 3D honeycomb conjecture.

Over the period T0-T18 (10/2015 - 4/2017):
- 3 articles in international journals (involving several CoMeDiC partners)
- 10 articles in international journals (involving one CoMeDiC partner)
- 1 book chapter
- 3 communications to international conferences (involving several CoMeDiC partners)
- 5 communications to international conferences (involving one CoMeDiC partner)
- 2 articles on arXiv or HAL

Discrete exterior calculus has emerged in the last decade as a powerful framework for solving discrete variational problems in image and geometry processing. It simplifies both the formulation of variational problems and their numerical resolution, and is able to extract global optima in many cases. However nothing guarantees that, on digital data like 2D or 3D images, digital curves and surfaces, it approaches the expected result of standard calculus, even when refining the discrete domain toward the limit continuous domain.

The CoMeDiC project aims at filling the gap between discrete calculus and standard calculus for subsets of the digital space Z^n. The general idea is to define well-chosen metrics for discrete calculus that make it converge toward continuous values. This approach is now possible due to recent advances in digital geometry on multigrid convergent estimators. Digital calculus then addresses variational problems involving domains such as digital surfaces, curves, graphs living in a higher dimensional ambient space, as well as problems involving discontinuities or subtle boundary conditions.

This project addresses theoretical problems like the definition of a sound digital calculus, the study of appropriate estimators for metrics, the statement of convergence properties. It is also concerned with its efficient numerical implementation. It studies also variational problems that present difficulties to standard numerical methods, like problems with discontinuities or free boundaries, or problems involving domains of codimension greater or equal to one as surfaces or curves. Last, this project focuses on three domains of application for digital calculus --- image analysis, digital geometry processing and shape optimisation --- both to guide and nourish theoretical developments, as well as to serve as testbed for digital calculus.