GAIA seminar@LIX

13 mars 2008, INRIA Rocquencourt
par Frank Nielsen, École Polytechnique, Sony CSL

La photographie computationnelle a connu un essor considérable ces dernières années avec l'adoption massive par le grand public du tout numérique. L'avènement des appareils photos numériques s'est surtout tout d'abord cantonné à imiter l'argentique afin de pouvoir mieux rattraper ses caractéristiques fondamentales comme la résolution et qualité d'image. Toutefois, la photographie computationnelle offre de toutes autres nouvelles possibilités inédites et vise ainsi à redéfinir complètement la notion de "photographie" elle-même en repensant à la fois la manière de capturer, organiser, traiter et partager sur le réseau les photos et vidéos. La photographie computationnelle est ainsi devenue rapidement un véritable domaine porteur de recherche en informatique qui s'appuie et développe dans un cycle vertueux créatif les domaines de la vision par ordinateur, du traitement moderne de l'image, de l'infographie et des techniques d'apprentissage et classification par ordinateur, pour n'en citer que les principaux.

Dans cet exposé, je donnerai un aperçu des principales directions de la photographie computationnelle en présentant quelques techniques modernes du traitement du signal et décrivant la conception de nouveaux systèmes de capteurs, d'éclairages et d'optiques computationnels. Je parlerai ensuite de la représentation post-pixel des images et des techniques d'interprétation d'image pour une photographie intelligente.

By Steve Oudot (INRIA Futur). WEDNESDAY 16th JANUARY 10h30 (LIX Ecole Polytechnique)

Abstract: Manifold reconstruction has been extensively studied among the computational geometry community for the last decade or so, especially in two and three dimensions. Recently, significant improvements were made in higher dimensions, leading to new methods to reconstruct large classes of compact subsets of Euclidean space $\R^d$. However, the complexities of these methods scale up exponentially with d, which makes them impractical in medium or high dimensions, even for handling low-dimensional submanifolds. In this talk, we will introduce a novel approach that stands in-between classical reconstruction and topological estimation, and whose complexity scales up with the intrinsic dimension of the data. Specifically, our algorithm combines two paradigms: greedy refinement, and topological persistence. It builds a set of landmarks iteratively, while maintaining nested pairs of complexes, whose images in $\R^d$ lie close to the data, and whose persistent homology eventually coincides with the one of the underlying shape. When the data points are sufficiently densely sampled from a smooth $m$-submanifold of $\R^d$, our method retrieves the homology of the submanifold in time at most $c(m)n^5$, where $n$ is the size of the input and $c(m)$ is a constant depending solely on $m$. It can also provably well handle a wide range of compact subsets of $\R^d$, though with worse complexities. Along the way to proving the correctness of our algorithm, we will present new results on \v Cech, Rips, and witness complex filtrations in Euclidean spaces. Specifically, we will show how previous results on unions of balls can be transposed to \v Cech filtrations. Moreover, we will propose a simple framework for studying the properties of filtrations that are intertwined with the \v Cech filtration, among which are the Rips and witness complex filtrations. Finally, we will investigate further on witness complexes and quantify a conjecture of Carlsson and de Silva, which states that witness complex filtrations should have cleaner persistence barcodes than \v Cech or Rips filtrations, at least on smooth submanifolds of Euclidean spaces.

By Frederic Cazals. January 21 15pm (LIX Ecole Polytechnique)

This talk will address two topics mixing geometric algorithms and structural biology. First, we shall present an analysis of hot residues at protein-protein interfaces, based upon the shelling of Voronoi interfaces. More precisely, we shall discuss the relationship between active residues, conserved residues, and the geometry / topology of Voronoi models of protein - protein interfaces. Second, we shall present a greedy algorithm and its approximation bound for the problem of selecting a collection of conformers best representing a larger collection of conformers. As this selection process is central for flexible docking algorithms, we shall present results for the particular cases of flexible loops.

by Frederic Chazal. WEDNESDAY JANUARY 16th 2008 10:30am (LIX, ECOLE POLYTECHNIQUE)

---

La caractérisation de structures géométriques dans des masses de données représentées par des nuages de points (souvent en grande dimension) est un enjeu important en analyse de données. Lorsqu?on étudie des données en grande dimension, il est souvent supposé qu?elles sont échantillonnées au voisinage d?une « forme » de petite dimension. Il est alors important de disposer de méthodes permettant d?inférer les propriétés topologiques et géométriques d?une telle forme. Les méthodes actuelles supposent essentiellement que les formes recherchées sont des variétés lisses et ne permettent généralement pas d?inférer des propriétés locales de ces formes. Elles se révèlent également inopérantes lorsqu?il s?agit de traiter de grosses masses de données. En pratique, il apparait souvent que les données échantillonnent des formes plus complexes que des sous-variétés. Il est alors important de pouvoir caractériser des propriétés géométriques locales (singularités, arêtes vives, strates,?) de ces formes. Dans cet exposé, nous introduirons une famille de mesures associée à chaque compact de $\R^n$ qui porte des informations géométriques sur le compact. Nous montrerons un résultat de stabilité qui permet d?obtenir un algorithme de calcul robuste de ces mesures pour des nuages de points. Nous montrerons aussi quelques conséquences de ce résultat concernant les mesures de courbures.

In this talk, we generalize the notions of centroids and barycenters to the broad class of information-theoretic distortion measures called Bregman divergences. Bregman divergences are versatile, and unify quadratic geometric distances with various statistical entropic measures. Because Bregman divergences are typically asymmetric, we consider both the left-sided and right-sided centroids and the symmetrized centroids, and prove that all three are unique. We give closed-form solutions for the sided centroids that are generalized means, and design a provably fast and efficient approximation algorithm for the symmetrized centroid based on its exact geometric characterization that requires solely to walk on the geodesic linking the two sided centroids. We report on our generic implementation for computing entropic centers of image clusters and entropic centers of multivariate normals, and compare our results with former ad-hoc methods.