Frank Nielsen
Computational Information Geometry in Dually Flat Spaces
[transparents]

High-dimensional noisy datasets encoding heterogeneous feature vectors abound in many real-world applications. On one hand, practitioners face the crucial problem of choosing the best-suited distance allowing them to use their algorithmic toolboxes. On the other hand, theoreticians are focusing on recovering the intrinsic dimensionality and underlying topology of datasets, and focus on learning the appropriate distance.
In the first part of the lecture, we start by presenting recent advances of the celebrated k-means clustering algorithm (G-means++ that learns the proper number of clusters using a careful seeding). We then present broad generalizations of k-means: convex k-means and Bregman k-means that preserve the centroid relocation scheme. We introduce the notion of Bregman divergences and Bregman information, and explain the fundamental convex duality arising from Legendre-Fenchel transformation. We describe the 1-to-1 map from Bregman divergences to statistical exponential families that allows one to design easy expectation-maximization soft-clustering algorithms.
In the second part of the lecture, we present the underlying geometry induced by a convex contrast function: Dually flat spaces generalizing the traditional Euclidean geometry. We explain how the standard notions of bisectors/projection/orthogonality and geodesics extend, and present generalizations of common algorithms and data-structures in computational geometry: smallest enclosing ball, space partitions for nearest neighbor queries, Voronoi and regular triangulations, etc. We then restate these results under the auspices of information geometry.
Finally, we conclude with other wide class of distances (eg., f-divergences, f-Jensen reminders, alpha-divergences) with their corresponding curved geometries.

Vin de Silva
Topology in the 21st century: nonlinear statistics, sensor networks, and other applications
[transparents]

Since the publication of the persistent homology algorithm, by Edelsbrunner, Letscher and Zomorodian in 2000, classical algebraic topology has undergone a 21st century renaissance, emerging as a field of applied mathematics. In the first part of the lecture, I will discuss several modern applications of algebraic topology, from nonlinear statistics to sensor networks. In the second part of the lecture, I will discuss persistent homology and its newest variant, zigzag persistence.

Rolf Schneider
Random tessellations and polytopes
[transparents]

The general aim of the two lectures is an introduction to random mosaics in Euclidean space and to some geometric extremal problems for the random polytopes defined by their typical cells and faces. The emphasis is on relations to convex geometry, since some classical results for convex bodies have surprising applications to the solution of these problems. Beginning with the early work of R. Miles and G. Matheron, Poisson processes in the space of hyperplanes in d-dimensional Euclidean space have been a prominent subject of stochastic geometry. A large part of our talks is devoted to the tessellations generated by such hyperplane processes and, in particular in the homogeneous case, to their average cells and faces. Various types of average faces can be considered, distinguished by different weights. The extremal cases characterize particularly simple hyperplane processes, like isotropic ones or those with only linearly independent directions of the hyperplanes. A second class of problems deals with the phenomenon that average cells of large size (with different interpretations) may approximate certain definite shapes, with high probability. There are also results of this type for Voronoi and Delaunay mosaics.

Frédéric Chazal
Introduction aux méthodes de réduction de la dimension
[transparents]

Les techniques de réduction de la dimension sont utilisées dans de nombreux domaines (apprentissage, compression, visualisation de données,...) nécessitant le traitement d'informations représentées par des données dans des espaces de grande dimension. Même si la réduction de la dimension ne constitue pas un sujet nouveau, il est à l'origine d'intenses recherches et d'une littérature abondante motivées par le besoin d'analyser les quantités croissantes de données disponibles dans tous les domaines scientifiques et économiques.
D'un point de vue général, les méthodes de réduction de la dimension visent à plonger des données (typiquement des nuages de points) échantillonnées dans des espaces de grande dimension dans des espaces de petite dimension tout en préservant leurs propriétés métriques ou géométriques intrinsèques. De nombreuses techniques et algorithmes, utilisant des outils mathématiques variés (probabilités, statistique, géométrie, analyse harmonique,...) ont été proposés.
L'objectif de ce cours est de fournir une petite introduction au vaste sujet de la réduction de dimension en présentant quelques méthodes choisies possédant des motivations géométriques.

Jean-Claude Léon
Quels besoins en topologie pour la représentation des objets au cours du processus de développement de produits ?
[transparents]

Afin de situer le contexte du développement de produits, quelques concepts clés sont présentés pour mettre en évidence la multi-représentation de composants et de sous-systèmes. La diversité des formes des composants et sous-systèmes permet de caractériser des besoins et des limites des modeleurs actuels pour les traiter efficacement au cours d’un processus de développement de produits.
L’analyse, effectuée sous l’angle de concepts fondamentaux conduit à identifier des besoins relatifs à des modèles possédant des singularités non-variété et une décomposition de frontière comportant également des configurations non-variétés.
Sur la base des besoins identifiés, des premiers résultats de travaux sont présentés en abordant le cas de complexes simpliciaux décrivant des 2-variétés soumises à des transformations générant des singularités non-variété. L’étude des 1-cycles définis en topologie algébrique permettant de caractériser la forme d’objets possédant des singularités non-variété est illustrée.
De même, la génération de configurations non-variété requises pour la décomposition de la frontière d’un objet est abordée et illustrée sous la forme de description à l’aide d’hypergraphes.

Résumés des exposés

Francis Lazarus, Dominique Attali, Marc Glisse, Samuel Hornus, Dmitriy Morozov
Simplification de fonctions sur les surfaces via la persistance
[transparents]

Soit f une fonction scalaire définie sur une surface triangulée S. On sait associer à f un ensemble de points du plan, appelé diagramme de persistance, en lien avec les variations topologiques des sous-ensembles de niveaux de la forme S_t= f ^-1(]-,t]) : un point (x,y) du diagramme encode l'apparition de classes d'homologie dans S_x qui disparaissent (deviennent bordantes) dans S_y. Les points (x,y) proches de la diagonale du plan correspondent ainsi à des évènements d'apparitions/disparitions de courte "durée" |x-y|. Une epsilon-simplification de f est une fonction g sur S dont le diagramme de persistance est celui de f privé des points epsilon-proches de la diagonale. Dit autrement g préserve les évènements topologiques d'une durée au moins epsilon.

On montre comment calculer efficacement, dans un cadre combinatoire, une epsilon-simplification de f qui soit de plus epsilon-proche de f.

Steve Oudot, Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas
Proximité des modules de persistance et de leurs diagrammes
[transparents]

La persistance topologique s'est imposée comme l'un des concepts clés pour l'étude des fonctions à valeurs réelles définies sur des espaces topologiques. La validité de l'approche repose sur la propriété fondamentale que les diagrammes de persistance de fonctions proches sont également proches. Toutefois, les résultats de stabilité existants se restreignent au cas des fonctions continues définies sur des espaces triangulables.

Dans cet exposé, nous introduirons de nouveaux résultats de stabilité qui ne souffrent pas de ces limitations. Plus précisément, nous nous placerons à un niveau algébrique directement, où nous introduirons les notions de discrétisation d'un module de persistance et de fonction de pixélisation associée. Ces notions nous permettront de définir une mesure de proximité entre modules de persistance, et de montrer comment on peut interpoler entre deux modules de persistance, donnant ainsi un caractère très géométrique à notre travail (malgré le parti pris de se placer à un niveau purement algébrique).

Nous pensons que ces nouveaux concepts et outils peuvent éclairer la théorie de la persistance d'un nouveau jour, en plus de simplifier grandement les preuves et de permettre le développement de nouvelles applications. Parmi les apports essentiels de notre travail, citons le fait que travailler directement au niveau algébrique permet de comparer les diagrammes de persistance de fonctions définies sur des espaces topologiques distincts, chose impossible jusquà présent.

Primoz Skraba, Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot
Analyse de champs scalaires définis sur des nuages de points
[transparents]

Étant donné une fonction f définie sur un espace métrique X, connu seulement au travers d'un échantillon fini de points L, est-il possible de récupérer de l'information structurelle à propos de f à partir de ses seules valeurs aux points de L ainsi que des distances entre points ? Nous fournissons une réponse affirmative à cette question. Plus précisément, en nous basant sur des résultats récents sur la stabilité des diagrammes de persistance, nous introduisons une nouvelle construction algébrique, fondée sur une paire de familles de complexes simpliciaux emboîtés bâtis sur les points de l'échantillon L, à partir de laquelle il est possible d'approximer fidèlement le diagramme de persistance de f. Nous dérivons de cette construction une série d'algorithmes pour l'analyse de champs scalaires à partir de nuages de points. Ces algorithmes sont simples conceptuellement et faciles à implanter, ils jouissent de bornes de complexité raisonnables, et enfin sont fournis avec des garanties théoriques. Afin d'illustrer ces qualités, nous présentons des résultats expérimentaux obtenus dans des applications en clustering, en segmentation de formes géométriques, ainsi qu'en réseaux de capteurs.

Boris Thibert, Frédéric Chazal, David Cohen-Steiner, André Lieutier
Stabilité des mesures de courbure
[transparents]
 
Ce travail étudie l'estimation de la courbure d'ensembles compacts échantillonnés. Nous montrons que les mesures de courbures moyenne, de Gauss et anisotropes des offsets d'un compact K suffisamment "régulier", i.e. à mu-reach strictement positif, sont stables : elles peuvent être estimées par les mesures de courbures des offsets de tout compact K' suffisamment proche de K pour la distance de Hausdorff. Nous explicitons le calcul de ces mesures de courbures dans le cas où K' est un nuage de points dans R³. Ces résultats fournissent en particulier un cadre permettant de définir formellement des notions de courbures robustes pouvant être effectivement calculées.

Quentin Mérigot
Inférence géométrique pour des mesures
[transparents]
 
Le problématique générale de l'inférence géométrique est de retrouver les caractéristiques géométriques ou topologiques d'un objet inconnu -- comme les normales, la courbure, les nombres de Betti -- étant donnée une approximation par un nuage de point. Une approche très générale est de définir ces quantités pour une famille large de compacts qui contienne aussi bien les objets limites que leurs approximations, et de prouver qu'elles sont continues en le compact, voire localement constantes.

La fonction distance à compact K -- qui associe à tout point de l'espace ambiant sa distance à K -- est un des outils utilisés en inférence géométrique, au travers des voisinages tubulaires, de l'axe médian, des mesures de bord, etc. L'application qui à K associe sa fonction distance est continue dans le sens où si K et K' sont deux compacts proches au sens de Hausdorff, leurs fonctions distance respectives sont proches en norme infinie. En revanche, dès que K' contient un outlier, sa fonction distance change radicalement et ne peut donc plus être utilisée pour l'inférence.

Le but de cet exposé est de souligner l'intérêt de la notion de mesure -- au sens de distribution de masse -- pour prendre compte ce phénomène d'outliers. Nous introduisons une notion de fonction distance à une mesure qui possède des propriétés de régularité très similaires à celles de la fonction distance à un compact. Nous démontrons de plus que si deux mesures sont proches au sens du transport optimal, leurs distances associées sont proches en norme infinie. Pour le transport optimal entre mesure, l'ajout d'un petit nombre d'outlier (eg. 5% de la masse initiale) correspond à une petite perturbation de la mesure originale: ainsi, la fonction distance à la mesure perturbée sera proche de la fonction distance originale, et peut être utilisée pour l'inférence de propriétés géométriques de la mesure originale.

Pierre Reiss
Test Point Polyhèdre = une analogie électromagnétique
[transparents]

L'algorithme et son sous-jacent théorique sont illustrés ici.
Il appartient a une classe d' algorithmes caractérisés par une minimisation des coûts de calcul.

Il se fonde sur une étude soignée des changements d'état, le long de la droite verticale passant par le point testé, par rapport au polyèdre : dehors, dessus, dedans. Il prend en compte une tolérance de distance. Contrairement à beaucoup d' autres implementations, la droite n'est pas remise en cause au cas ou un sommet ou une arête est rencontrée.

L'idée de base est liée à la détermination du signe du flux d'un vecteur à travers une spire électromagnétique 3D.

Guillaume Batog
Evènements visuels de polyèdres
[transparents]

Etant donné une scène de polyèdres dans l'espace, il s'agit de caractériser l'ensemble des points de l'espace depuis lesquels la topologie de la silhouette change par un léger déplacement du point d'observation. En introduisant une stabilité de type isotopique, cette étude se ramène à la caractérisation des rayons instables dont un premier catalogue sera présenté. Ces résultats pourront servir de base théorique pour l'élaboration d'algorithmes de calculs de visibilité 3D, de calculs d'ombres, de reconnaissance de formes,...

Stéphane Rivière
Diagrammes de Voronoi d'ordre k pour les droites
[transparents]

Étant donné un ensemble de n points (sites) dans le plan donné, nous étudions les ensembles de droites plus proches de k sites que des autres. Cela forme une partition de l'espace des droites du plan en faces, arêtes et sommets que nous appelons diagramme de Voronoi d'ordre k pour les droites. Ce diagramme peut être visualisé et étudié plus facilement grâce à l'utilisation d'une relation de dualité entre points et droites.
Nous décrivons la structure de ce diagramme, établissons des relations entre ce diagramme et les k-sets qui permettent de calculer sa taille, et donnons un algorithme de calcul. Nous montrons aussi comment passer du diagramme d'ordre k au digramme d'ordre k-1.

Nader Salman
High resolution surface reconstruction from overlapping multiple-views
[transparents]

Three-dimensional reconstruction of real world scenes from sequences of overlapping images is a topic of much interest in Computer Vision, Computer Graphics and Computational Geometry. Its application areas range from preservation of historical heritage to virtual reality walkthroughs through computer animation, movie production and e-commerce. However, reconstructing real world models of sufficient quality with respect to different target applications is still an extremely challenging, time consuming and costly process.

We will present a novel approach to recover automatically simplicial models of complex scenes from a set of images taken from various view points around the scene. The models sought after are either surface meshes or 3D meshes of the objects in the scene.

We first use an existing automatic, greedy, feature based, stereo algorithm to extract a quasi-dense set of 3D points from the located images. The output of the located frame processing step is a set of tracks, where each track is a 3D point associate to a list of frames (or camera positions) where the point is visible.

Our algorithm starts with the input sequence of calibrated images provided with the corresponding set of tracks. It first preprocesses the tracks to eliminate outliers and filter noise. Then, it performs a contrast analysis of the located frames in order to detect contour edges. These contours are then used as constraints to build 2D Delaunay triangulations in the image planes from which a soup of 3D triangles (so-called "conformal soup") is obtained by lifting the 2D constrained triangulations in the 3D scene coordinates. The triangles of this soup are processed to project onto homogeneous regions of the images in which they are seen, thus respecting the detected contours. Finally, it reconstructs the scene surface out of this filtered triangle soup, thus generating a triangular mesh of the scene. We show reconstruction results on real scene examples.

Pooran Memari
Reconstruction de formes à partir de coupes
[transparents]

Nous considérons le problème de la reconstruction d'un objet 3D O, à partir de ses intersections avec un ensemble de plans en position arbitraire, appellées coupes. Nous présentons un algorithme qui permet de reconstruire la topologie de l'objet à partir des coupes données. Ensuite, nous prouvons que l'objet reconstruit est homéomorphe à O si certaines conditions d'échantillonnage sont vérifiées.

Jean-Marie Favreau, Vincent Barra
Calcul du lacet non trivial le plus court d'une surface
[transparents]

On s'intéresse au découpage optimal d'une surface en un disque. Erickson et al. ont montré [1] que c'était un problème NP-difficile. Nous proposons ici une amélioration en O(n log n + pm log m) de leur algorithme pour le calcul du plus court lacet non séparant, où n est le nombre de points du maillage décrivant la surface, p << n le nombre de points du bord d'un découpage topologique simple, et m << n le nombre de points du plus grand voisinage topologique.
En présentant différents choix de pseudo-distances intégrant des notions de géométrie, et/ou guidées par l'application, nous illustrons comment l'implémentation C++ de l'algorithme de découpage optimal en disque répond à des problèmes pratiques en imagerie médicale ou dans un contexte de synthèse d'images 3D.

[1] Jeff Erickson and Sariel Har-Peled: Optimally Cutting a Surface into a Disk, Discrete & Computational Geometry 31(1):37-59, 2004.

Luis Peñaranda
Sur la topologie de courbes algébriques planes
[transparents]

On considère le problème du calcul de la topologie et de la géométrie d'une courbe algébrique plane. On s'intéresse d'une part à la topologie de la courbe, et d'autre part à sa géométrie telle que la position des points critiques et singuliers. Un défi consiste à calculer efficacement cette information sans avoir besoin de changer le système de coordonnées si la courbe n'est pas en position générique.

Les méthodes existantes, basées sur la décomposition cylindrique algébrique (CAD), utilisent des suites de sous-résultants et des calculs avec des polynômes à coefficients algébriques. Une des nouveautés introduites par notre méthode est le remplacement de ces outils par des bases de Groebner et l'isolation avec des représentations univariées rationnelles (RUR), ayant pour but d'éviter les calculs avec des polynômes à coefficients algébriques et les changements de systèmes de coordonnées. L'utilisation de ces outils donne lieu à différentes options de calcul des multiplicités dans les systèmes et dans les fibres. Notre algorithme isole les points critiques par des boîtes et calcule une décomposition du plan (qui n'est pas une CAD) par des boîtes rectangulaires: cette décomposition engendre une nouvelle approche pour calculer un arrangement de lignes polygonales isotopiques à la courbe d'entrée. On présente aussi un analyse de complexité de notre algorithme.

Finalement, on démontre l'efficacité de notre algorithme avec une implantation. En particulier, elle est capable de gérer des courbes non-génériques de haut degré.

Jean-Daniel Boissonnat, Olivier Devillers, Samuel Hornus
Construction du squelette de Delaunay en dimension quelconque
[transparents]

Nous présentons brièvement une nouvelle implémentation de Delaunay en dimension quelconque supérieure à 3. Nous présentons plus longuement une technique de construction de squelette de Delaunay, ce qui réduit de manière conséquente l'utilisation mémoire.

Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt 
Construction de la triangulation de Delaunay de segments par un algorithme de flip
[transparents]

Étant donné un ensemble S de segments disjoints dans le plan, que nous appelons des sites, une triangulation de segments de S est une partition de l'enveloppe convexe de S en sites, arêtes et faces. L'ensemble des faces est un ensemble maximal de triangles ouverts disjoints tels que les sommets de chaque triangle sont sur trois sites distincts et tels que leurs côtés ouverts ne coupent pas S. Les arêtes d'une triangulation de segments sont les composantes connexes (éventuellement de dimension deux) de l'enveloppe convexe de S privée des sites et des faces de la triangulation. La triangulation de Delaunay de segments de S est celle dont les faces sont inscriptibles dans des cercles vides, c'est-à-dire des cercles dont les intérieurs ne coupent pas S. Cette triangulation est duale du diagramme de Voronoï de segments.

L'objectif de cet exposé est de montrer que toute triangulation de segments donnée peut être transformée, par une suite finie d'améliorations locales, en une triangulation de segments qui a la même topologie que la triangulation de Delaunay de segments. Cet algorithme est une généralisation de l'algorithme dit «de flip» qui transforme une triangulation d'un ensemble de points en triangulation de Delaunay. La principale différence avec l'algorithme de flip classique est que les améliorations locales doivent être calculées sur des régions non convexes. Nous surmontons cette difficulté en utilisant des fonctions localement convexes.