Description

Sicentific program

Convergent Metrics for Digital Calculus

The main idea of the project is to combine recent results of convergence of geometric estimators and to inject them into the discrete exterior calculus, in order to develop a convergent digital calculus onto objects, surfaces and curves that comes from digitization in finer and finer regular grids. This new calculus is validated and experimented in three domains of applications of variational methods: image analysis, geometry processing and shape optimization.

General objectives and main issues

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 digital curves and surfaces embedded into a 2D or 3D space, it approaches the expected result of standard calculus, even when refining the discrete domain toward the limit continuous domain. To sum up, today’s discrete calculus is generally not convergent on subsets of regular digital spaces like digital surfaces and, even on smoother domains, most problems involving second-order derivatives are not convergent without extra hypotheses.
The CoMeDiC project aims at filling the gap between discrete and standard calculus for subsets of the digital space Zn.

Methodology

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.

Main results

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 [1]
  • Gauss digitization and integration over digital surfaces [2]
  • 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 [3][4]
  • Identification of optimal shapes for spectral problems in dimension 4 [AO17]
  • Optimal partitions 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[5]
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 [3]
  • 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 [4]
  • Digital confidence map for the reconstruction of tubular objects from partial or damaged scans [6][7]
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, 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.

 

Related bibliography

[1] Lachaud, J. -O., Provençal, X. & Roussillon, T. (2017) Two plane-probing algorithms for the computation of the normal vector to a digital plane. IN Journal of mathematical imaging and vision, ..
[Bibtex]
@article{Lachaud:2016-tcs,
author = {J.-O. Lachaud and X. Proven{\c{c}}al and T. Roussillon},
title = {Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital Plane},
journal = {Journal of Mathematical Imaging and Vision},
year = {2017},
note = {Accepted. To appear.}
}
[2] Lachaud, J. -O. & Thibert, B. (2016) Properties of gauss digitized shapes and digital surface integration. IN Journal of mathematical imaging and vision, 54.162-180.
[Bibtex]
@article{lachaud2016properties,
title={Properties of Gauss digitized shapes and digital surface integration},
author={Lachaud, J.-O. and Thibert, B.},
journal={Journal of Mathematical Imaging and Vision},
volume={54},
number={2},
pages={162--180},
year={2016},
publisher={Springer}
}
[3] Foare, M., Lachaud, J. -O. & Talbot, H. (2016) Image restoration and segmentation using the ambrosio-tortorelli functional and discrete calculus Cancun, Mexico, .
[Bibtex]
@InProceedings{Foare:2016-icpr,
author  = {Foare, M. and Lachaud, J.-O. and Talbot, H.},
title = {Image restoration and segmentation using the Ambrosio-Tortorelli functional and discrete calculus},
booktitle  = {Proc. 23th International Conference on Pattern Recognition (ICPR2016)},
address  = {Cancun, Mexico},
year = {2016},
}
[4] [doi] Coeurjolly, D., Foare, M., Gueth, P. & Lachaud, J. -O. (2016) Piecewise smooth reconstruction of normal vector field on digital data. IN Comput. graph. forum, 35.157-167.
[Bibtex]
@article{Coeurjolly:2016-pg,
author = {D. Coeurjolly and
M. Foare and
P. Gueth and
J.-O. Lachaud},
title = {Piecewise smooth reconstruction of normal vector field on digital
data},
journal = {Comput. Graph. Forum},
volume = {35},
number = {7},
pages = {157--167},
year = {2016},
url = {http://dx.doi.org/10.1111/cgf.13013},
doi = {10.1111/cgf.13013},
timestamp = {Thu, 10 Nov 2016 09:12:45 +0100},
biburl = {http://dblp.uni-trier.de/rec/bib/journals/cgf/CoeurjollyFGL16},
bibsource = {dblp computer science bibliography, http://dblp.org},
note = {Proc. of Pacific Graphics 2016}
}
[5] Foare, M., Lachaud, J. -O. & Talbot, H. (2016) Numerical implementation of the ambrosio-tortorelli functional using discrete calculus and application to image resoration and inpainting Cancun, Mexico, .
[Bibtex]
@InProceedings{Foare:2016-rrpr,
author  = {Foare, M. and Lachaud, J.-O. and Talbot, H.},
title = {Numerical implementation of the Ambrosio-Tortorelli functional using discrete calculus and application to image resoration and inpainting},
booktitle  = {Proc. 1st Workshop on Reproducible Research in Pattern Recognition (RRPR2016)},
address  = {Cancun, Mexico},
year = {2016},
}
[6] Kerautret, B., Krähenbühl, A., Debled-Rennesson, I. & Lachaud, J. -O. (2016) Centerline detection on partial mesh scans by confidence vote in accumulation map Cancun, Mexico, .
[Bibtex]
@InProceedings{Kerautret:2016-icpr,
author = {Kerautret, B. and Kr{\"a}henb{\"u}hl, A. and Debled-Rennesson, I. and Lachaud, J.-O.},
title = {Centerline Detection on Partial Mesh Scans by Confidence Vote in Accumulation Map},
booktitle  = {Proc. 23th International Conference on Pattern Recognition (ICPR2016)},
address  = {Cancun, Mexico},
year = {2016}
}
[7] Kerautret, B., Krähenbühl, A., Debled-Rennesson, I. & Lachaud, J. -O. (2016) On the implementation of centerline extraction based on confidence vote in accumulation map Cancun, Mexico, .
[Bibtex]
@InProceedings{Kerautret:2016-rrpr,
author = {Kerautret, B. and Kr{\"a}henb{\"u}hl, A. and Debled-Rennesson, I. and Lachaud, J.-O.},
title = {On the Implementation of Centerline Extraction based on Confidence Vote in Accumulation Map},
booktitle  = {Proc. 1st Workshop on Reproducible Research in Pattern Recognition (RRPR2016)},
address  = {Cancun, Mexico},
year = {2016}
}