Department 1 website
The Department Algorithms, Computation, Geometry and Image regroups six teams (ABC, ADAGIO, ALICE, CARAMEL, MAGRIT, VEGAS) that share scientific interests on these topics. Beside algorithms which is a common center of interest to all these teams (and of course to some teams of other departments as well), there are various centers of interest common to several teams. Geometry plays an important role in most teams, i.e., ADAGIO, ALICE, CARAMEL, MAGRIT, and VEGAS. Symbolic and algebraic computing is of common interest of CARAMEL and VEGAS, image is of interest to ADAGIO, ALICE and MAGRIT, combinatorics and complexity also concerns several groups as ADAGIO, CARAMEL, and VEGAS, certified computing (in a sense that requires computing with arbitrary precision integers or floating-point numbers) is also of common interest to CARAMEL, VEGAS, ADAGIO, and ALICE. The main common interest of ABC with the other groups is the algorithmic culture they share, though there is also some more technical connexions with other groups.
ABC: Machine learning, bioinformatics and statistics
The ABC team contributes to three different fields: machine learning, bioinformatics and statistics. Our main scientific goal is to develop the theory and practice of supervised and unsupervised learning. We focus on the theory of multi-class pattern recognition, deriving uniform convergence results which primarily deal with multi-class kernel machines such as multi-class support vector machines (M-SVMs). Our applications are in the field of biological sequence processing. More precisely, we develop theoretical bounds on the risk of classifiers, methods of model selection, multi-class support vector machines, methods for robust data mining and methods for statistical processing of biological sequences (e.g., prediction of the secondary structure of proteins).
ADAGio: Applying Discrete Algorithms to Genomics and Imagery
The general goal of ADAGio is to develop efficient algorithms on discrete structures, such as strings, trees, graphs, maps, polyominoes, etc. This development comes through deep theoretical studies of combinatorial properties of those structures. Our distinguished application areas are discrete geometry and bioinformatics, in which discrete models play a crucial role. A particular attention is drawn to creating experimental software implementing algorithms we develop.
ALICE: Geometry and Light
ALICE studies some fundamental aspects of Computer Graphics. More specifically, we study the interaction of light with the geometry of the objects. The lighting problem consists in designing accurate and efficient numerical simulation methods for the light transport equation. The geometrical problem consists in developing new solutions to transform and optimize geometric representations. Our original approach to both issues is to restate the problems in terms of numerical optimization. We try to develop solutions that are provably correct, scalable and numerically stable. Besides Computer Graphics, we have cooperations with researchers and people from the industry, who experiment applications of our general solutions to various domains, comprising CAD, industrial design, oil exploration, plasma physics...
CARAMEL: Computer Arithmetics
The CARAMEL team conducts research in computer arithmetics. The goal is to push forward the possibilities to compute efficiently with objects having an arithmetic nature. This includes integers, real and complex numbers, polynomials, finite fields, and even more complicated objects such as algebraic curves. The main application domains are cryptography and computer algebra systems. CARAMEL studies arithmetics at various abstraction levels, from most low-level software or hardware implementation of basic building blocks to complicated high-level algorithms like integer factorization or point counting. Studying the interactions between low-level and high-level algorithms are of utmost importance for arithmetic applications, yielding important improvements that would not be possible with a vision restricted to low- or high-level algorithms.
MAGRIT : Visual Augmentation of Complex Environments
The Magrit team carries out researches in the field of computer vision, with a focus on augmented reality applications. Augmented reality is a relatively new field. It aims at augmenting the user's perception by adding in his field of view elements that improves his comprehension of his environment. Applications of this concept are plentiful and concern medical gesture assistance, learning and maintenance systems, cultural heritage, audiovisual... In order to integrate information at the right place in the user's field of view, whatever his motion, the observer's viewpoint has to be computed at every instant. Moreover, reconstructing, even partially, the observed environment is necessary to manage occlusions between the added objects and the scene or to take light interreflexions into account. Only elementary commercial applications of this concept exist to date. These applications are only effective in environments with limited user action which are furthermore often instrumented (landmarks). Many challenges remain to be tackled so as to address applications in complex environments. The Magrit team research aims at proposing robust solutions to the two main issues faced in augmented reality: viewpoint computation and reconstruction of the scene elements necessary to set up the application.
VEGAS: Effective Geometric Algorithms for Surfaces and Visibility
The main scientific focus of our group is the design and implementation of technology-independent, robust and efficient geometric algorithms for 3D visibility and low-degree algebraic surfaces. Meeting our computational objectives requires mathematical tools that are both geometric and algebraic. In particular, we need further knowledge of the basic geometry of lines and surfaces in a variety of spaces and dimensions as well as to adapt sophisticated algebraic methods, often computationally prohibitive in the most general setting, for use in solving seemingly simple geometric problems.