**Parameter-free analysis of digital surfaces**
([version française](these.md.html))
Thesis
===============================================================================
We are seeking a PhD student:
- for three years, starting date: September 2019,
- [LIRIS](https://liris.cnrs.fr/) lab, Lyon, France,
- gross salary: around 2100 euros/month (part of the ANR project
[PARADIS](http://perso.liris.cnrs.fr/tristan.roussillon/paradis.html)),
- supervision: [Tristan Roussillon](http://perso.liris.cnrs.fr/tristan.roussillon),
associate professor in Computer Science at [INSA Lyon](https://www.insa-lyon.fr/en/insa-lyon),
and another member of the project.
Applicants should hold a Master's degree in computer science (or Mathematics),
with a background in graphics, 3D, computer vision, image or geometry.
A strong programming skill is required.
By the end of the thesis, the PhD student will become an expert in geometric inference
and digital surface analysis. He/She will contribute to open-source projects like
[DGtal](https://dgtal.org/) and will be able to disseminate his/her results to diverse audiences.
**To apply**, interested applicants are requested to send to
[Tristan Roussillon](http://perso.liris.cnrs.fr/tristan.roussillon)
(tristan - dot - roussillon - at - liris.cnrs.fr) as soon as possible and
before June 10th 2019, an up-to-date Curriculum Vitae,
transcripts of master grades, at least one potential reference
(supervisor of a training period for instance).
Context
===============================================================================
3D volumes come from the segmentation of magnetic resonance, X-ray tomographic or micro-tomographic images.
They are also generated in scientific modelling and by voxel editors.
We are interested in the geometry of volume boundaries, called *digital surfaces* (Fig. [snow]).
![ [^syntax] Figure [snow]: "ice-air" interface in a micro-tomographic image of snow.](SnowE2_DigitalData.png
width="400px" )
Keeping the digital nature of the data is an advantage
to use efficient spatial data structures such as voxel octree,
to perform constructive solid geometry operations,
to do integer-only and exact computations, etc.
A drawback is its poor geometry, because at any resolution a digital surface is only
made up of quadrangular surface element
whose normal vector is parallel to one axis.
Many tasks in computer graphics, vision and 3D image analysis require a richer geometry:
rendering, surface deformation for simulation or tracking, precise geometric measurements, etc.
To perform relevant geometric tasks and to benefit from the above-mentioned advantages
in the same time, we need to enhance the geometry of digital surfaces by estimating
extra data for each surfel, like a *normal vector* (Fig. [normal]). In order to estimate
a relevant normal vector, the surface geometry within a patch around each
surface element should be gathered. There are numerous methods, but almost all of them require
at least one parameter that controls the size of the patch, which does not always reveal the local geometry.
![ [^syntax] Figure [normal]: Normal estimates onto a digital surface.](normal.png
width="300px" )
Objectives
===============================================================================
We would like to work with a surface patch of adaptive size, which will be typically
a piece of digital plane that locally fits the digital surface. In order to fulfill
this objective, the main challenge is not really to recognize a piece of digital plane,
but more to find which surface patch should be given as input to recognition algorithms.
One alternative is to use a _plane-probing_ algorithm that decides on-the-fly which
data points should be taken into account to make growing a piece of digital plane tangent
to the surface by construction (see Fig. [pattern] and [#LPR19],[#LPR17],[#LPR16b],[#LPR16a]).
![ Figure [pattern]: Piece of digital plane onto a digital surface and its normal vector,
equal to the normal vector of the computed triangular facet. ](pattern.gif width="300px")
- A first objective is to derive, from _plane-probing_ algorithms, efficient, accurate and
parameter-free estimators of local and first-order geometric quantities: normal vector
(and surfel area as a by-product), distance to boundary, voxel coverage.
- A second objective is to study the multigrid convergence of these estimators. Indeed,
most of the time, when we are working with a digital surface, we are interested in the
geometry of a continuous shape whose digitization is the input 3D volume. We expect that
a given geometric quantity, such as a normal vector, computed at a point of a digital
surface is close to the one of the underlying continuous shape at a close enough point.
An estimator is multigrid-convergent if its accuracy depends on the resolution: the higher
the resolution, the more accurate the estimator.
- Finally, plane-probing algorithms provide normal vector and position information,
which may be useful for many applications in graphics such as polyhedral
approximation, surface fairing or digital surface visualization. A third objective is
to investigate at least one of these applications.
References
================================================================================
[#LPR19]: T. Roussillon, J.-O. Lachaud.
[Digital Plane Recognition with Fewer Probes](https://hal.archives-ouvertes.fr/hal-02087529).
21st IAPR International Conference on Discrete Geometry for Computer Imagery, Mar 2019.
[#LPR17]: J.-O. Lachaud, X. Provençal, T. Roussillon.
[Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital
Plane](https://hal.archives-ouvertes.fr/hal-01621516).
Journal of Mathematical Imaging and Vision, Vol. 59, No. 1, p.23 – 39, Sep 2017.
[#LPR16b]: J.-O. Lachaud, X. Provençal, T. Roussillon.
[Computation of the normal vector to a digital plane by sampling signicant
points](https://hal.archives-ouvertes.fr/hal-01621492).
19th IAPR International Conference on Discrete Geometry for Computer Imagery, Apr 2016.
[#LPR16a]: J.-O. Lachaud, X. Provençal, T. Roussillon.
[An output-sensitive algorithm to compute the normal vector of a digital
plane](https://hal.archives-ouvertes.fr/hal-01294966).
Journal of Theoretical Computer Science Vol. 624, p.73–88, Apr 2016.
[^syntax]: Snow data acquired by 3SR Lab and CEN/CNRM - GAME URA 1357/Météo-France - CNRS,
[DigitalSnow project](https://projet.liris.cnrs.fr/dsnow/), thanks to David Coeurjolly for the images.