Images and geometry

Heads: Jean Cousty and Stéphane Sabourau

Fields of research

The isometric embedding of a square flat torus in 3D space. © Borrelli, Jabrane, Lazarus, Thibert

Digital imagery and geometry are closely related, cross-fertilizing domains. New branches of geometry provide both theoretical and algorithmic models for the processing, analysis and synthesis of images ; in return computer imagery, in its variety of applications, constitutes a remarkable experimental field and a source of challenging problems. Computer vision, discrete geometry, discrete topology and computational geometry are relatively new branches of mathematics that recently appeared under the impulse of the development of computer science. They take part in the theoretical study of shape models and/or partial differential equation which can be handled by computers, as well as transformations that can be applied to these models.

Scene parsing with hierarchical convolutional nets

3D photography deals with the problem of recovering three-dimensional shapes from images ; it has always been one of the most investigated problem by computer vision scientists. Based on the principle of stereovision, it boils down to two separate problems : (i) the camera calibration problem consisting in estimating the geometric parameters of the cameras that took the images, and (ii) the shape reconstruction problem which estimates the geometry of the observed objects, given the images and the parameters of the cameras. Recently, giant steps have been done in Multiple View Stereovision. The Imagine group of LIGM is a recognized team in 3D modeling from images. It has recently proposed reconstruction methods that are considered as the best available ones, on the basis of public benchmarks. Yet, key issues are still open, mainly : (i) the design of a globally optimal calibration method and (ii) the ability to handle very large scale datasets like the ones of urban modeling.

In image theory, equations of evolution can be used to flow the level set of the isophotes. Such evolution flow is useful for image restoration (noise reduction, deblurring) and segmentation (object recognition). This field of research has for instance important applications to MRI images segmentation using metaheuristics, as well as applications to medical images sequences.

Mathematical morphology is a discipline which establishes a theoretical framework for the study of a broad class of non-linear operators acting on images or more generally on multidimensional signals. During the last decate, the A3SI of LIGM actively contributed to the evolution and the enrichment of this field, both on theoretical and algorithmic aspects, as well as by developing various applications.

Today’s challenges in image processing require to solve problems of large dimension (especially in 3D or 3D+t applications) for which it is useful to employ efficient sparse representations of available data. In general, the latter representations rely on overcomplete extensions of wavelet bases, which are often designed according to some geometrical considerations (e.g. dual-tree transforms, curvelets, bandlets,…). In recent years, many efforts have been made in order to optimally build such representations based on the observation models and the desired sparsity of the solution. A very promising approach has been developed advocating for learning automatically the relevant dictionary for data representation. This is generally done by resorting to some techniques from mathematical optimization and unsupervised learning that amount to minimizing a cost function, which is not necessarily differentiable or convex. A number of algorithms for accomplishing this task have been proposed in the literature, but their properties — particularly those related to their convergence—are not always well understood.

Bandit problems in machine learning are concerned with optimizing a sequence of actions in face of uncertainty when the actions also impact the information retrieved by the agent (or decision maker). The agent must choose between following what seems to be the best choice in view of the past (“exploit”) or testing (“exploring”) some alternative, hoping to discover a choice that beats the current best choice. This exploration-exploitation trade-off arises in a wide range of applications including advertizement, economics, games, optimization. It can be a central building block of larger systems, like in evolutionary programming and reinforcement learning, in particular in large state space Markovian Decision Problems. Current state-of-the-art algorithms in bandit problems address two extreme situations : the i.i.d. One and the adversarial one, and focuses on maximizing the cumulative reward. The Bézout Labex’s teams aim to address more realistic settings and objectives.

Scientific program of the Bézout Labex

This theme is mainly concerned by still open mathematical problems that are raised by major applications of computer imagery, such as 3D photography and medical image analysis. For example, a fundamental subject is the study of relationship between the approximate discrete model and geometric invariants computed on smooth shapes (such as conformal parametrizations, mean curvature, Gauss curvature, or umbilic points). In this theme, researchers in image analysis and computer vision specialists of the team A3SI of LIGM will interplay with experts in geometric analysis of the LAMA.

In 3D photography, three-dimensional reconstruction from simple photographs may be obtained through the stereovision principle. It consists in finding, in various digital images of a scene taken from different viewpoints, the pixels corresponding to the same point in the real scene. New approaches have been developed to obtain a complete three-dimensional reconstruction of an object from a series of images taken around the object. Rather than tackling the ambiguous matching problem, the Labex aim at finding a shape which, globally, realizes the best possible fit with the measures, while satisfying a-priori constraints on the scene (as the regularity of the object’s surfaces). This approach leads naturally to a socalled variational formulation, that is to say, finding a minimum energy configuration for an energy functional to be defined. It is based on the tools of mathematical optimization, as well as those of differential geometry.

Image segmentation and restoration can be described by a transition phase model. It has been observed that the segmentation limit process converges to minimal surfaces. Interestingly, the Allen-Cahn and Cahn-Hilliard (AC/CH) equations, exactly describe the change of transition phase. This problem is related with the energy whose Euler-Lagrange equation is a scaled version. There are links between the ROF model and this energy. Recent works shed new light on transition phase theory and the Labex Bézout’s teams expect to apply these new techniques in ROF model.

Mathematical morphology is a non-linear image theory developed in both discrete and continuous settings. There are many links between flow evolution and morphology, for instance PDEs for image levelings used in image processing. Under some circumstances, efficient discrete hierarchical levelings can be associated with total variation optimizations, and so link back to the AC/CH and ROF models. The Labex is interested in studying the links between these approaches. Overall, this field of study is important to theoreticians and practitioners alike since it may unify many points of view under a single umbrella, providing an elegant framework and efficient algorithms.

Twisted Pseudospheres © Nicholas Schmitt

Designing sparse representations adapted to the available data and the investigation of the suitable optimization algorithms (for instance, proximal methods, stochastic optimization) is an active area of research. In this context, it is of central interest to explore the possibility of parallelization of algorithms in order to reduce the computational burden. Being closely related to sparsity issues, the optimization methods should be able to cope with non-smooth cost functions. The methods of continuous optimization—often used in this context—may be complemented by methods of discrete optimization such as graph cuts. In the LIGM and the LAMA, research expertises in the fields of continuous and combinatorial optimization are both present. The combination of these techniques may result in a higher efficiency of algorithms and allow to relax some assumptions (convexity of the cost function, for instance). Another topic of interest is to consider more sophisticated cost functions than those currently employed in the solution of imaging problems which often rely on relatively “low-level” variational or statistical models. In particular, it would appear of main interest to take into account more accurate geometrical informations on the objects present in the target images.

A highly promising alternative to the optimization techniques for sparse recovery is based on Bayesian statistics and the use of posterior mean in conjunction with a sparsity favoring prior. The computation is then done by a stochastic algorithm and the thorough study of which both from theoretical and empirical standpoints is a challenging task for future research.

In machine learning, a bandit policy is usually assessed in terms of cumulative regret, that is the difference between the cumulative reward obtained by the policy and the cumulative reward of the best constant action. The Bézout’s teams will particularly study alternative notions of regret and their associated optimal policies, and specifically how to design a policy with low cumulative regret with respect to all strategies having a (small but) fixed number of switches between actions.

Valorization of results, transfer, and expertise

Regarding 3D photography, reconstructing 3D models for single buildings or whole areas has applications in many domains : construction, cinema, video games, virtual tourism, heritage preservation, etc. Semantically rich 3D models as well as image analysis can be used to draft or supplement building information models (BIM) that are increasingly used in the construction industry, not only for new buildings but also for building renovation, in particular to plan and optimize energy savings. Concerning this domain the Bézout Labex has on-going or starting collaborations with Bouygues, Saint-Gobain, the Centre Scientifique et Technique du Bâtiment (CSTB) as well as the Institut Géographique National (IGN). Other collaborations include Arts et Métiers Paris Tech for the reconstruction of the Cluny abbey as well as Mikros Image (a movie production company).

PET (Positron Emission Tomography) image after reconstruction by proximal methods

Fields of research

Image segmentation and restoration finds applications in almost all fields of image analysis and processing. In the domain of biomedical image analysis more particularly, the Labex will develop collaborations with both academic and industrial partners, in France and abroad, extending our already existing network of relationships : Henri Mondor Hospital and Faculty of Medicine (Créteil), University College (London), CSIRO (Australia), Siemens Corporate Research (Princeton), General Electric Healthcare (Buc), Sanofi (Toulouse), Sagem.

Concerning sparse representations in image analysis, the research activity finds numerous applications in inverse problems such as image denoising, restoration and reconstruction. In particular, the LIGM has developed collaborations in the area of functional MRI, Positron Emission Tomography and microscopic imaging. Due to the high dimension of the considered problems, this research sub-theme should also benefit from cross-fertilization with the ideas developed in the theme “High-dimensional phenomena”.

The Bézout teams’ research in machine learning is expected to contribute to its application fields : computer vision, economics, games, optimization and reinforcement learning.