**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.