Séminaire de recherche A3SI
(2012-2013)

Jeudi 6 juin 2013

Analyse morphologique de nuage de points: application à l'histopathologie numérique
Nicolas Loménie - Université Paris Descartes
Abstract: A la fin des années 1990, des problématiques d'analyse de nuages de points stéréoscopiques pour des applications de robotique mobile m'ont conduit à étudier les alpha-objets de H. Edelsbrunner qui permettent de définir de façon formelle un spectre de formes associé à un nuage de point sur la base d'une triangulation de Delaunay. De façon heuristique, nous avons développé des méthodes de filtrage de formes associé à des nuages de points géométriques. Progressivement, nous avons établi un cadre plus théorique sur la base de la morphologie mathématique pour tirer pleinement profit des ce algorithmes. Dernièrement, nous avons également travaillé sur des applications plus liées au raisonnement spatial comme la représentation des représentations spatiales ou l'analyse de nuage de points extraits d'image histopathologiques.
Bibliographie:
Nicolas Loménie, Daniel Racoceanu: Point set morphological filtering and semantic spatial configuration modeling: Application to microscopic image and bio-structure analysis. Pattern Recognition 45(8): 2894-2911 (2012)
Nicolas Loménie, Georges Stamon: Morphological mesh filtering and alpha-objects. Pattern Recognition Letters 29(10): 1571-1579 (2008)
Logiciel Plugin ImageJ: http://www.math-info.univ-paris5.fr/~lomn/Data/MorphoMesh.zip

Slides

Jeudi 30 mai 2013

Sampling and Motion Reconstruction in Three-dimensional X-ray Interventional Imaging
Hélène Langet - Philips Research
Abstract: Medical imaging has known great advances over the past decades to become a powerful tool for the clinical practice. It has led to the tremendous growth of interventional radiology, in which medical devices are inserted and manipulated under image guidance through the vascular system to the pathology location and then used to deliver the therapy. In these minimally-invasive procedures, X-ray guidance is carried out with C-arm systems through two-dimensional real-time projective low-dose images. More recently, three-dimensional visualization via tomographic acquisition has also become available.
This work tackles tomographic reconstruction in the aforementioned context. More specifically, it deals with the correction of motion artifacts that originate from the temporal variations of the contrast-enhanced vessels and thus tackles a central aspect of tomography: data (angular) sampling. The compressed sensing theory identifies conditions under which subsampled data can be recovered through the minimization of a least-square data fidelity term combined with sparse constraints. Relying on this theory, an original reconstruction framework is proposed based on iterative filtered backprojection, proximal splitting, l1-minimization and homotopy.
This framework is derived for integrating several spatial and temporal penalties. Such a strategy is shown to outperform the analytical filtered backprojection algorithm that is used in the current clinical practice by reducing motion and sampling artifacts in well-identified clinical cases, with focus on cerebral and abdominal imaging. The obtained results emphasize one of the key contributions of this work, that is the importance of homotopy in addition to regularization, to provide much needed image quality improvement in the suggested domain of applicability.

Jeudi 16 mai 2013

Atelier doctotants

Salient Level Lines Selection Using the Mumford-Shah Functional
Yongchao Xu, LIGM-ESIEE-A3SI, EPITA
Abstract: Many methods in mathematical morphology have been proved to be very useful for pattern analysis and recognition. Some of them rely on the morphological notion of shapes, i.e., connected components of level sets. Selecting meaningful level lines (boundaries of level sets) yields to simplify images while preserving intact salient structures. Many image simplification and/or segmentation methods are driven by the optimization of an energy functional, for instance the Mumford-Shah functional. Here, we propose a very fast locally optimal solution of the piecewise-constant Mumford-Shah functional, subordinated to the tree of shapes. Our method provides as result a simplified image containing a selected family of level lines organized in a tree hierarchy through an inclusion relationship. The image simplification process can thus be seen as a shape-based morphological filtering. Experimental results demonstrate the efficiency, usefulness, and robustness of our method, when applied to image simplification, pre-segmentation, and detection of affine regions with viewpoint changes.

Light Clustering for Photo-Realistic Rendering
Norbert Bus, LIGM-ESIEE-A3SI
Abstract: Rendering realistic images requires a numerical solution for the rendering equation. One way to obtain such a solution is to place virtual light sources (VPL) in the environment where light would be reflected and render the image simply with these lights without accounting for reflected light directly. To obtain a correct image typically hundreds of thousands of such virtual light sources are necessary and this enormous number of lights introduces high complexity. To cope with this, the so-called light-cuts method clusters the VPLs into groups of lights. I will present our proposed solution which utilizes the geometric well-separated pair decomposition for spatial clustering.

Adaptive Structure from Motion with a contrario model estimation
Pierre Moulon, LIGM-ENPC-IMAGINE
Abstract: Structure from Motion (SfM) algorithms take as input multi-view stereo images (along with internal calibration information) and yield a 3D point cloud and camera orientations/poses in a common 3D coordinate system. In the case of an incremental SfM pipeline, the process requires repeated model estimations based on detected feature points: homography, fundamental and essential matrices, as well as camera poses. These estimations have a crucial impact on the quality of 3D reconstruction. We propose to improve these estimations using the a contrario methodology. While SfM pipelines usually have globally fixxed thresholds for model estimation, the a contrario principle adapts thresholds to the input data and for each model estimation. Our experiments show that adaptive thresholds reach a signi ficantly better precision. Additionally, the user is free from having to guess thresholds or to optimistically rely on default values. There are also cases where a globally-fixed threshold policy, whatever the threshold value is, cannot provide the best accuracy, contrary to an adaptive threshold policy.

Reconstruction d'image en présence de bruit gaussien dépendant par un algorithme Explicite-Implicite à métrique variable
Audrey Repetti, LIGM-Signal
Résumé : Le but de ce travail est de reconstruire une image dégradée par un opérateur linéaire et perturbée par un bruit additif gaussien dont la variance dépend linéairement de l'image originale. La fonction d'attache aux données considérée (obtenue grâce à une estimation par maximum a posteriori ) est non convexe et la fonction de régularisation est non lisse. Nous proposons de résoudre ce problème grâce à un algorithme Explicite-Implicite (Forward- Backward, FB) accéléré par l'introduction d'une métrique variable. Cette métrique est choisie suivant la théorie de la Majoration-Minimisation, ce qui constitue un avantage significatif par rapport aux travaux existant où ce choix est souvent fait de manière empirique. L'algorithme présenté permet plus généralement de traiter la somme d'une fonction (non nécessairement convexe) différentiable et d'une fonction (non nécessairement différentiable) convexe. Nous montrons sa convergence en utilisant des résultats récents de l'analyse non lisse. Nos résultats de simulations illustrent l'accélération produite sur la vitesse de convergence du critère ainsi que celle des itérées. Les courbes de convergence obtenues montrent que notre algorithme se compare favorablement à l'algorithme FB classique et à ses formes accélérées telles que FISTA.
Travail commun avec E. Chouzenoux, J.-C. Pesquet

Jeudi 25 Avril 2013

Advancing (i) graphical model inference and (ii) blind image deconvolution
Nikos Komodakis - IMAGINE - LIGM - ENPC - ECP
Abstract: In this talk I will briefly discuss two different topics.

The first one refers to the fundamental problem of graphical model inference, in which case I will present a very general optimization algorithm that aims at dealing with one of the core difficulties of inference in graphical models: the existence of the so-called inconsistent cycles. In particular, I will explain how one can achieve this goal by resorting to the use of a dynamic hierarchy of linear programming relaxations that is constructed by applying an operation called cycle-repairing.

The second problem I will discuss is that of blind image deconvolution, which is a highly ill-posed (and thus very challenging) task. In this case, I will present an optimization-based blind image deconvolution method that relies on imposing a discrete MRF prior on the deconvolved image. I will show that this leads to a very efficient and effective deblurring algorithm that can handle even very challenging cases involving the inference of large and complicated blur kernels.

Jeudi 18 Avril 2013

Enumeration of small topological and geometric (n_k)-configurations
Vincent Pilaud - CNRS - LIX - Ecole Polytechnique
Abstract: An (n_k)-configuration (P,L) is a set P of n points and a set L of n lines in the (projective) plane such that their point-line incidence graph is k-regular: each point of P is contained in k lines of L, and reciprocally each line of L contains k points of P. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines, or just combinatorial lines. Famous examples are Pappus' and Desargues' Theorems, which are geometric (9₃)- and (10₃)-configurations respectively.
In this talk, I will present recent progress on the enumeration of topological and geometric (18₄)- and (19₄)-configurations. These instances are of particular interest: 18 is the first value of n for which geometric (n₄)-configurations exist, and 19 is one of the only four values of n for which the existence of geometric (n₄)-configurations remains open.
Joint work with Jürgen Bokowski (Darmstadt).

Jeudi 11 avril 2013

Modélisation statistique et classification du mouvement humain à partir des séquences vidéo
Mounim A. El Yacoubi - Institut Mines-Telecom / Telecom SudParis

Résumé : La recherche en traitement automatique de séquences vidéo connaît actuellement un essor sans précédent. Cela s'explique, d'une part, par la chute spectaculaire des prix de caméras et d'ordinateurs, associée à l'amélioration continue des performances de ces derniers pour le traitement et le stockage de données gourmandes comme la vidéo, et d'autre part, par l'intérêt énorme suscité par les applications liées à la vidéosurveillance, l'e-Santé, et à l'exploitation du contenu vidéo sur Internet, etc. Dans cet exposé, nous présenterons les méthodes de traitement automatique de séquences vidéo que nous avons développées dans les dernières années dans le laboratoire Intermedia de Telecom SudParis. Ces méthodes seront abordées dans le contexte général de la théorie de la reconnaissance statistique de formes. Deux applications concrètes seront discutées, en l'occurrence, la reconnaissance d'actions et d'activités humaines pour l'e-Santé et la reconnaissance de personnes par leurs démarches (Gait Recognition) pour la vidéo surveillance.

Jeudi 4 avril 2013

Un cadre combinatoire pour la profondeur simpliciale colorée
Frédéric Meunier - CERMICS - Ecole des Ponts ParisTech

Résumé : Le théorème de Carathéodory coloré, dû à Bárány, affirme que si l'on se donne d+1 ensembles de points S_1,...,S_{d+1} dans R^d, chacun d'eux contenant l'origine dans son enveloppe convexe, alors il est possible de choisir un point p_i dans chaque S_i et d'avoir encore l'origine dans l'enveloppe convexe des p_i. L'enveloppe convexe des p_i est alors appelée "simplexe coloré contenant l'origine". Le nombre de simplexes colorés contenant l'origine est la "profondeur simpliciale colorée" de l'origine.
Une question qui a reçu une attention particulière est celle de savoir quelle est la plus petite profondeur simpliciale colorée possible dans le cas où chaque S_i est de cardinalité d+1. Le théorème de Bárány montre qu'elle vaut au moins 1. La valeur minimale mu(d) qu'elle peut prendre a été étudiée par Deza et al., Bárány et Matousek, et Stephen et Thomas, qui ont montré que mu(d) vaut toujours au moins (d^2+2d+1)/2 et au plus d^2+1. La conjecture que mu(d) vaut d^2+1 a été vérifiée en dimensions 1, 2 et 3.
Dans cet exposé, nous améliorons la borne inférieure et montrons que mu(d) vaut toujours au moins (d^2+7d-16)/2. Nous montrons également que mu(4)=17, et donc que la conjecture est vraie en dimension 4. Les preuves utilisent des hypergraphes particuliers spécialement conçus pour ce problème - les systèmes octaédriques, dont l'étude a été récemment suggérée par Bárány. Quelques résultats théoriques les concernant seront également présentés.

Jeudi 28 février 2013

Atelier doctotants

Saliency transformation and reordering hierarchies based on external constraints
Ravi Kiran, LIGM-ESIEE-A3SI
Abstract:In this study we propose to modify a given hierarchy by fusing its saliency with any general external function defined on the same support. We will use in particular the distance function of some ground truth associated with the input hierarchy of segmentations. This transformation results in a new or reordered saliency function with classes not present in the original hierarchy, and which generates classes closer to the ground truth. This is achieved by defining a basic transformation, the Class opening, which reduces a set of arcs into a closed contour. We demonstrate how this transform can compose an input saliency and any other function by operations of addition, multiplication. This class opening satisfies a semi-group structure based on certain conditions on the saliency and external function. Results are demonstrated over the Berkeley Dataset.

Recalage Linéaire à l'aide de graphes d'ordres supérieurs
Vivien Fécamp, Ecole Centrale Paris
Résumé : Nous présentons ici une nouvelle approche capable de résoudre le recalage linéaire iconique entre deux images. Notre approche est fondée sur un modèle graphique local d'ordres supérieurs, superposé à l'image. Les variables cachées correspondent a des vecteurs de déplacement. La linéarité globale de la transformation est assurée par les contraintes d'ordre 3 et 4. La formulation est modulaire vis-à-vis de la métrique du terme d'attache aux données, et de la transformation recherchée (rigide, similarité, affine). L'inférence est réalisé sur le graphe grâce à la méthode de décomposition duale.

Fast and Robust Normal Estimation for Point Clouds with Sharp Features
Alexandre Boulch, LIGM-ENPC-IMAGINE-A3SI
Abstract:This talk presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed-size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise-resistant as state-of-the-art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.

Jeudi 21 février 2013

Image Segmentation with Geometrical Constraints
Frank Schmidt - A3SI - LIGM - ESIEE

Abstract: In Computer Vision we often want to separate the displayed object of interest from its surroundings. It has been shown in the past that modeling foreground and background as a GMM is not enough to solve this problem of image segmentation. We therefore have to incorporate prior knowledge into image segmentation.

In this talk I will speak about my recent work (ECCV 2012) that shows how geometrical constraints can be applied to image segmentation. In particular, I will talk about

• Adding maximal Hausdorff distances to nested multi-label segmentation
• Constraining the distribution of appearances in binary segmentation

• A submodular-supermodular procedure governed by iterated distance maps
• A continuous process of discrete graph cuts called 'line-search cut'

Jeudi 31 janvier 2013

Scene Understanding: What more can we do to better understand scenes?
Karteek Alahari - Willow - INRIA - ENS

Abstract: One of the goals of computer vision is to interpret a scene semantically from an image. This problem has manifested itself in various forms, including, but not limited to, object recognition, 3D scene recovery, and image segmentation. Although tremendous progress has been made in all these tasks, many challenges still remain. This talk focus on two such challenges: (i) Video segmentation; and (ii) Text recognition in scenes.
Video not only provides rich visual cues such as motion and appearance, but also long-range temporal interactions among objects, which are rarely explored. We present a method to capture such interactions and to construct a powerful intermediate-level representation for subsequent recognition. This representation also provides a local depth ordering of objects in the scene. In more recent work, we explore the problem of segmenting people in films.
Scene understanding algorithms have focussed on locating and recognizing objects and regions, such as car, person, sky, road, but have ignored text (which provides useful cues, e.g. geographical location, types of buildings) occurring in scenes. For the scene text recognition problem, we present a framework that exploits bottom-up and top-down cues. The bottom-up cues are derived from individual character detections from the image, while the top-down constraints are obtained from language statistics.
We will show exciting results for these two problems on various public datasets.

Mercredi 23 janvier 2013

From geometric optimization to nerve theorems
Xavier Goaoc - LORIA, INRIA

Abstract: This talk will explore some relations between questions in combinatorial optimzation, generalization of Helly's theorem on the intersection of convex sets, and refinements of the Nerve theorem in topological combinatorics and algebraic topology. It will start from first principles and is based on a joint work with Éric Colin de Verdière (CNRS, ENS) and Grégory Ginot (Univ. Paris 6) available from http://www.loria.fr/~goaoc/papers/multinerve-socg.pdf.

Jeudi 20 décembre 2012

Discrete set-valued continuity and interpolation
Laurent Najman - ESIEE, LIGM, équipe A3SI

Abstract: The main question of this talk is to retrieve some continuity properties on (discrete) T0-Alexandroff spaces. One possible application, which will guide us, is the construction of the so-called "tree of shapes" (intuitively, the tree of level lines). This tree, which should allow to process in the same way maxima and minima, faces quite a number of theoretical difficulties that we propose to solve using set-valued analysis in a purely discrete setting. We also propose a way to interprete any function defined on a grid as a "continuous" function thanks to an interpolation scheme. The continuity properties are essential to obtain a linear algorithm for computing the tree of shapes that we will develop in another talk (joint work with Thierry Géraud).

Jeudi 22 novembre 2012

Local-search techniques for geometric algorithms
Nabil Mustafa - ESIEE, LIGM, équipe A3SI

Abstract: Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local improvement steps. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a local maximum. Its use in designing approximation algorithms was demonstrated in a beautiful paper of Arya-Garg-Khandekar-Meyerson-Munagala-Pandit. Inspired by this paper, a well-known open geometric covering problem was resolved by the use of a local-search technique by Mustafa-Ray. Later on, several other problems were resolved in a similar way. In this talk, I will present the main ideas in all these papers.

Jeudi 4 octobre 2012

La notion de frontière en histoire, en sciences de la terre, en peinture et en musique, vue comme segmentation d'image
Jean Serra - ESIEE, LIGM, équipe A3SI

Résumé

Présentation (pdf)