Séminaire de recherche A3SI
(2008-2009)

Le 10 juillet 2009

Tubular Structure Segmentation based on Minimal Path Method and Anisotropic Enhancement
Fethallah Benmansour - Ceremade, Université Paris Dauphine
Abstract: We present a new interactive method for tubular structure extraction. The main application and motivation for this work is vessel tracking in 2D and 3D images and Stenosis grading. The basic tools are minimal paths solved using the fast marching algorithm. This allows interactive tools for the physician by clicking on a small number of points in order to obtain a minimal path between two points or a set of paths in the case of a tree structure. Our method is based on a variant of the minimal path method that models the vessel as a centerline and surface. This is done by adding one dimension for the local radius around the centerline. The crucial step of our method is the definition of the local metrics to minimize. We have chosen to exploit the tubular structure of the vessels one wants to extract to built an anisotropic metric giving higher speed on the center of the vessels and also when the minimal path tangent is coherent with the vessel's direction. This measure is required to be robust against the disturbance introduced by noise or adjacent structures with intensity similar to the target vessel. We obtain promising results on noisy synthetic and real 2D and 3D images.

Contrast invariant optical flow computation with application to disparity estimation
Luis Garrido - Université Pompeu Fabra, Barcelone
Abstract: Most of the optical flow computation approaches in the literature are based on the constant luminance hypothesis, which assumes that the object's luminance is constant along its motion trajectory. In our work we propose to use the geometric information of the level lines present in the image to compute the optical flow. This geometric information is invariant to contrast changes, and thus, the estimated optical flow also is invariant to contrast changes. Motion is estimated using both a parametric and non-parametric approach. Whereas the parametric approach is solved using conjugate gradient techniques, the non-parametric approach has to be solved using large-scale optimization techniques. In order to improve computational efficiency, a multigrid scheme is used. Several experiments comparing the proposed method with the classical constant luminance hypothesis approach will be presented. Its application to aerial disparity estimation will be finally shown.

Jeudi 18 juin 2009

Atelier doctotants

Les rotations dans les espaces discrets 2D et 3D
Yohan Thibault
Résumé : Les rotations dans les espaces discrets sont indispensables pour de nombreuses applications comme le traitement d'image, la vision par ordinateur... Dans cet exposé, nous allons discuter des problèmes qui apparaissent lors des rotations dans les espaces discrets et des solutions que nous avons proposées. Nous allons dans un premier temps présenter les problèmes liés à l'utilisation des rotations dans les espaces discrets, comme celui de l'approximation due à la discrétisation. Ensuite nous allons introduire l'ensemble des angles charnières, qui sont des angles particuliers permettant de caractériser la rotation dans les espaces discrets. Nous verrons comment utiliser les angles charnières en 2D puis en 3D pour réaliser des rotations n'utilisant que des calculs entiers. Pour les rotations en 3D, un autre problème apparaît, celui de l'axe de rotation, si celui-ci est mal choisi, il est impossible de garder des calculs en entiers malgré les angles charnières. Finalement nous présenterons nos travaux sur les n-tuplets pythagoriciens (ou axes pythagoriciens) qui sont une extension des triplets pythagoriciens.

Modélisation et rendu temps-réel de brouillard hétérogène à l'aide d'ondelettes B-Spline quadratiques
Anthony Giroud
Résumé : Les brouillards hétérogènes sont souvent modélisés par une superposition de couches de densités différentes ou à l'aide de systèmes de particules. Cependant, ces couches ne permettent qu'une variation verticale de la densité, et les systèmes de particules se révèlent souvent très gourmands en temps de calcul lors du rendu de scènes en extérieur. Au cours de cette exposé, nous présenterons une méthode simple pour le rendu de brouillard hétérogène en temps réel. La densité du brouillard, qui définit sa fonction d'extinction, est tout d'abord modélisée dans une base de fonctions B-Spline. Une transformée en ondelettes est ensuite appliquée sur cette fonction de façon à en obtenir une décomposition à la fois en temps et en fréquences. Les données résultantes servent enfin au rendu temps réel du brouillard à l'aide du GPU.

Un algorithme efficace pour le calcul de l'épaisseur latticielle en toute dimension
Emilie Charrier
Résumé : L'épaisseur d'un ensemble de points S de Z^d par rapport à un treillis Lambda (dite épaisseur latticielle) correspond à l'épaisseur arithmétique minimale de S pour toutes les directions entières représentées dans le treillis. Nous décrirons durant cet exposé un nouvel algorithme pour le calcul exact de l'épaisseur latticielle d'un ensemble de points dans Z2. Cet algorithme est linéaire en la taille de l'ensemble de points. Par ailleurs, nous décrirons comment cet algorithme peut être étendu en toute dimension grâce à une approche gloutonne qui s'avère efficace en pratique.

Jeudi 11 juin 2009

Towards a real-time visual memory
Julien Pilet - Hideo Saito Laboratoy, Keio University, Japan
Abstract: Recent visual object retrieval techniques achieve impressive results, based on clustering local image descriptors. The so-called visual words are used to index the images of a database, and queries can be conducted with a bag-of-word model. However, the computation burden of existing algorithms prevent them to be applied on live video streams, mostly due to feature extraction time. To address this issue, we propose to rely on a fast combination of feature detection and tracking. We then use feature tracks as visual words. During a training stage, we use tracks to observe the instability of descriptors. Our algorithm then establishes a stabilized visual vocabulary. Our learning approach to visual words fits particularly well video sequences, because it allows not only a single descriptor, but also its whole history tracked over several frames, to contribute to the visual word selection.
As a result, our system is able to query a database in real-time with live images. Indexing of user selected images is perceptually immediate. However, our system is currently implemented 100% on CPU and performance could be improved by adapting it to GPU. We will present the state of our efforts to do so, including the architecture of a scale invariant feature detector designed for parallel computation.

Vendredi 5 juin 2009

Some Recent Developments in Hyperconnectivity
Michael Wilkinson - Institute for Mathematics and Computing Science, University of Groningen
Abstract: Hyperconnectivity is a generalization of connectivity, and unlike the latter, allows overlap of structures. One problem is finding relevant hyperconnectivities is developing useful hyperconnectivity classes. Two will be explored here: (i) viscous hyperconnectivity, which is closely related to reconstruction with reconstruction criteria, and (ii) k-flat hyperconnectivity, which uses overlapping pseudo-flat zones in the grey-scale case. A fast viscous hyperconnected reconstruction algorithm is presented with application to cartoon-texture decomposition of images, together with a k-flat attribute filtering algorithm based on the Max-Tree. The latter shows much promis in separation of galaxies from stars in astronomical images.

Jeudi 14 mai 2009

A scale-space toggle operator for multiscale image simplification/segmentation
Neucimar J. Leite - Institute of Computing, University of Campinas, Brazil
Abstract: The scale-space theory is a multiscale representation approach in which the inherent multiresolution nature of real-world images is represented by embedding the original signal into a family of simplified signals, created by successively and monotonically removing the image structures across scales. We consider in this presentation notions of toggle mappings and scaled structuring functions to define a morphological toggle operator having interesting properties of a scale-space transformation. As we will illustrate, these properties conduce to a well-controlled image extrema simplification, which can be used in problems involving, for instance, image segmentation and binarization.

Copy of the slides

Jeudi 7 mai 2009

Vers les réseaux mobiles de quatrième génération et d'accès véhiculaire
Rola Naja, ESIEE, Département Informatique
Résumé : Ce séminaire porte sur trois grandes problématiques : La première problématique concerne la gestion des ressources. En effet, avec l'augmentation du nombre d'utilisateurs mobiles et l'évolution rapide des réseaux mobiles sans fil, les demandes des utilisateurs en termes de qualité de service (QoS) deviennent de plus en plus exigeantes. La gestion de la ressource radio est de loin le problème critique des réseaux mobiles sans fil d'autant plus que l'interface radio représente le goulet d'étranglement dans ces réseaux. Dans cette optique, un protocole d'allocation de ressources doit pouvoir gérer efficacement la bande passante tout en fournissant la qualité de service à différentes classes de service. La deuxième problématique est axée sur le problème de la mobilité verticale. En effet, un protocole de mobilité efficace doit empêcher la terminaison forcée de l'appel et permettre l'exécution des applications d'une manière transparente à la mobilité. Nos travaux réalisés portent sur la gestion de la mobilité en utilisant la théorie des jeux dans les réseaux multiservices sans fil. Les environnements qui sont visés dans ce travail concernent les réseaux de troisième et quatrième génération. Finalement, la troisième problématique est focalisée sur l'accès sans fil dans les environnements véhiculaires. En effet, le grand développement et l'évolution rapide dans le domaine des technologies sans fil ont redu possible de repenser le modèle de conduite automobile en introduisant la notion de coopération entre les véhicules. Le succès de l'introduction de la technologie 802.11p dans le domaine véhiculaire est fortement corrélé à la mise en oeuvre de services et d'applications réalistes à forte valeur ajoutée pour l'utilisateur final. Nous nous focalisons sur la conception des systèmes coopératifs d'assistance à la conduite pour l'amélioration de la sécurité routière et nous accordons un intérêt particulier à la qualité de service et la mobilité au sein des réseaux véhiculaires.

Jeudi 30 avril 2009

Differential Aberration Correction (DAC) Microscopy: a New Molecular Ruler
Pascal Vallotton, CSIRO Mathematical & Information Sciences
Abstract: Since Foerster and Stryer, biologists know how to use FRET (Fluorescence Resonance Energy Transfer) to measure nanometer-scale distances within proteins and molecular complexes; so everything is good! Or is it? FRET in fact fails to provide information when the two sites of interest lie beyond 10 nm. Even when they do not, a number of experimental parameters including the orientation of the probes, their exact spectral overlap or the value of the local refraction index between them render the precise determination of distances a non-trivial exercise. Here we present a simple technique, called Differential Aberration Correction (DAC) microscopy, which is not afflicted by these issues. We demonstrate the principle of the methodology on fluorescent microspheres.

Jeudi 9 avril 2009

Atelier doctotants

Parallel Image Thinning Trough Topological Operators Using Multi-core/Multi-thread Architectures
Ramzi Mahmoudi (ESIEE)
Abstract: We present a concurrent implementation of a powerful topological thinning operator. This operator is able to act directly over grayscale image without modifying their topology. We introduce a new parallelization methodology combining SDM-strategy and thread's coordination basis which allows efficient parallelism for a large class of topological operators including skletonisation, crest restoring, 2D and 3D object smoothing and watershed. Distributed work during thinning process is done by a variant number of threads. Tests on 2D grayscale image (512*512), using shared memory parallel machines (SMPM) equipped with an octo-core processor (Xeon E5405 running at a cadency of 2Ghz), showed an enhancement of 6.2 with a maximum achieved cadency of 125images/s using 8 threads.

Extraction de structures tubulaires sur un espace 4D
Mickaël Péchaud (ENPC)
Résumé : Nous proposons une nouvelle méthode permettant d'extraire des structures tubulaires à partir d'images 2D, par exemple des routes dans des images aériennes ou vaisseaux dans des images médicales. Notre travail est basé sur le calcul de plus courts chemins (géodésiques) sur un espace de dimension 4 permettant d'encoder l'orientation et le rayon des structures tubulaires. Ces géodésiques suivent avec précision le milieu des structures tubulaires, fournissent son rayon, et permettent de gérer correctement les intersections.

LPE Puissance : un nouveau cadre de segmentation d'image comprenant les Graph Cuts, Random Walker et forêts de poids optimal
Camille Couprie (ESIEE)
Résumé : Nous proposons l'extension d'un formalisme regroupant des algorithmes d'optimisation classiques en segmentation d'image avec marqueurs. Représentant une image par un graphe pondéré, les graph cuts, le random walker, et les forêts de plus court chemins peuvent s'exprimer au moyen d'une même fonction d'énergie avec différents choix possibles pour un paramètre q agissant comme exposant sur les différences entre deux noeuds voisins. En introduisant un nouveau paramètre p définissant une puissance pour les poids des arêtes, nous élargissons ce formalisme aux lignes de partage des eaux (LPE), qui sont les forêts de poids optimal. Nous proposons alors une nouvelle classe d'algorithmes de segmentation, que nous appelons ``LPE puissance'', en fixant p de manière à produire une forêt de poids optimal, mais en permettant la variation de la puissance q. Nous montrons que les LPE puissance ont un très bon comportement en pratique. Placer la ligne de partage des eaux dans ce cadre de minimisation d'énergie ouvre également de nouvelles possibilités pour l'utilisation de termes unitaires dans les algorithmes de LPE traditionnels, et pour l'utilisation de la LPE en optimisation de modèles, au delà du champ d'application de la segmentation d'image.

Optimal consensus set for digital line and plane fitting
Rita Zrour (ESIEE)
Abstract: We present a method for fitting a digital line (resp. plane) to a given set of points in a 2D (resp. 3D) image in the presence of outliers. One of the most widely used methods is Random Sample Consensus (RANSAC). However it is also known that RANSAC has a drawback: as maximum iteration number must be set, the solution may not be optimal. To overcome this problem, we present a new method that uses a digital geometric model for lines and planes in a discrete space. Such a digital model allows us to efficiently examine all possible consensus sets, which guarantees the solution optimality and exactness.

Jeudi 2 avril 2009

Surfaces de Riemann discrètes
Christian Mercat, Institut de Mathématiques et de Modélisation de Montpellier
Résumé : Une surface discrète, donnée par un maillage ou un ensemble de voxels, peut se comprendre comme une surface de Riemann discrète. Cette théorie généralise beaucoup de résultats de la théorie continue. Il y en a deux versions, l'une linéaire, l'autre quadratique, qui s'interprète géométriquement comme des polygones similaires ou des motifs de cercles, et partagent une condition d'intégrabilité. Cette intégrabilité permet d'exprimer explicitement la fonction de Green et une base des fonctions holomorphes comme polynômes et exponentielles.

Jeudi 26 mars 2009

Ordres totaux finis et treillis pilotes
Jean Serra, UPE, LIGM, A3SI, ESIEE
Résumé : Le travail exposé a pour but de structurer les données spatio-temporelles multivariées en vue de traitements morphologiques. Il peut s'agir d'imagerie couleur, satellitaire, ou de données composites. Le cas des images en couleur, et de leurs treillis, qui est un excellent paradigme de la situation multi-dimensionnelle, conduit à  trois questions :
1/ Pour ne pas créer de "fausses" valeurs, faut-il obligatoirement un treillis fini ? On montre que les treillis de parties finies, un peu plus généraux, sont aussi valables, et compatibles avec les translations.
2/ Peut-on s'affranchir, au moins partiellement, de l'ordre total ? On montre qu'entre l'ordre marginal (produit des ordres totaux de chaque composante) et lexicographique (total) s'insère une gradation d'ordres pilotes, où certaines variables, mais pas toutes, sont reliées par ordre total.
3/ Comment échapper à  l'arbitraire de l'origine du cercle (idem pour la surface de la sphère, du tore, etc.) ? On construit pour ce faire un ordre total, mais non lexicographique, dit de Voronoï. Son expression générale est donnée, ainsi que son expression dans les espaces digitaux à  une et deux dimensions.
Enfin, on applique les réponses à  ces questions à  une série d'exemples à  2, 3, et 4 dimensions portant sur la couleur, et sur les composantes principales des images multi-spectrales.

Copie des transparents

Vendredi 13 février 2009

Generalized Lifting for Image compression
Philippe Salembier, Technical University of Catalonia
Abstract: In this talk, we discuss the use of Generalized Lifting (GL) for lossy image compression. First, we will briefly introduce the GL and its relation with nonlinear wavelet decomposition. Then, the potential of the method for image compression will be studied. Furthermore, several strategies leading to the definition of a realistic scheme for generic image compression will be proposed and analyzed. The first one is based on a global statistical modeling of the data whereas the second approach relies on an adaptive pdf estimation of the local probability density function. Finally, the current limitations of the various schemes will be discussed and future work will be highlighted.

Copy of the slides

mardi 13 janvier 2009

Mise en correspondance et groupement multiple de points d'intérêt de paires d'images
Julien Rabin, TSI, Telecom ParisTech
Résumé : De nombreuses applications en vision par ordinateur, telles que la reconnaissance d'objet ou le recalage d'image, requièrent la mise en correspondance puis le groupement de points d'intérêt ayant été extraits à  partir de différentes images. La comparaison de ces points d'intérêt est en pratique réalisée à  l'aide de descripteurs locaux, tels que les SIFT, composés d'histogrammes d'orientation du gradient. Une nouvelle mesure de dissimilarité se basant sur une distance de transport (Earth's Mover Distance) et adaptée à  la circularité des histogrammes sera tout d'abord définie pour la comparaison des SIFT. Nous proposerons ensuite un critère de mise en correspondance, inspiré des méthodes a contrario, qui permet d'évaluer le degré de significativité des appariements testés et fournit des seuils de validation qui s'adaptent automatiquement à  la complexité et à  la diversité des données. Enfin, nous présenterons un travail en cours sur le groupement de telles mises en correspondance, inspiré du critère de selection, dit de rigidité, proposé par Moisan et Stival [IJCV 04] pour les méthodes de type RANSAC dans le cas des transformations épipolaires. Nous verrons comment adapter ce critère de rigidité aux transformations planes, permettant d'envisager une sélection automatique de modèle de transformation. Nous proposerons une nouvelle méthode de groupement adaptée aux cas des transformations multiples (occurrences multiples d'un objet, plusieurs objets en mouvements...). (travail commun avec Julie Delon et Yann Gousseau)

Jeudi 8 janvier 2009

Topology-preserving fast marching and level sets methods for brain image segmentation
Pierre-Louis Bazin, Johns Hopkins University
Abstract: Atlas-based segmentation techniques are often employed to encode anatomical information for the delineation of multiple structures in magnetic resonance images of the brain. One of the primary challenges of these approaches is to efficiently model qualitative and quantitative anatomical knowledge without introducing a strong bias toward certain anatomical preferences when segmenting new images. Topology can be used to describe the continuity of structures, as well as the relationships between structures, and is often a critical component in cortical surface reconstruction and deformation-based morphometry. I will present several topology-preserving techniques for topology correction of continuous functions, fuzzy segmentation of brain structures in health or with lesions, and thalamic parcellation. The methods combine topology control with fast marching, level set and tissue classification techniques to handle robustly multiple image contrasts, high levels of noise and gain field inhomogeneities, and variable anatomies.

Jeudi 4 décembre 2008

Atelier doctotants

Spatialisation du son pour la réalité virtuelle
Patrice Bouvier (UPEMLV)
Résumé : Une fois rappelés les tenants et aboutissants de toute expérience en réalité virtuelle, j'axerai mon exposé sur un domaine de la réalité virtuelle souvent négligé au profit de l'image : le rendu sonore. Dans un premier temps je présenterai les apports d'une restitution sonore dans un environnement virtuel, puis pour une meilleure compréhension de la suite de l'exposé j'expliquerai les mécanismes sous-jacents à  la localisation d'un son dans l'espace. J'exposerai alors les méthodes et les technologies mises en oeuvre pour la spatialisation de l'environnement sonore, enfin je présenterai quelques résultats et projets de notre équipe.

Towards high-resolution multiview stereovision
Vu Hoang Hiep (ENPC)
Abstract: Boosted by the Middlebury challenge, the precision of dense multi-view stereovision methods has increased drastically in the past few years. Yet, most methods are adapted to this challenge and could not handle large-scale data sets taken under uncontrolled conditions. In this paper, we propose a multi-view stereo pipeline able to deal at the same time with very large-scale scenes while still producing highly detailed reconstructions within very reasonable time. The keys to these benefits are twofold: (i) a graph-cuts based global optimization that transforms a dense point cloud into a visibility consistent mesh, followed by (ii) a mesh-based variational refinement that captures small details, smartly handling photo-consistency, regularization and adaptive resolution. Our method has been tested on numerous large-scale outdoor scenes. The accuracy of our reconstructions is also measured on the recent dense multi-view benchmark proposed by Strecha /et al/., showing our results to compare more than favorably with the current state-of-the-art.

Segmentation techniques for the analysis of electron nano-tomography images
Lazlo Marak
Abstract: Electron nano-tomography is an imaging technique utilising electrons in a transmission electron microscope (TEM). The TEM is equipped with a tiltable stage and incrementally rotated under the flux of electrons. Each projection is recorded and standard tomography software packages can be used to derive and produce a full 3D image. Nano-tomography images however have a number of characteristics that make it more challenging to analyse than standard X-ray tomograms. Due to sample preparation constraints, samples are often thin in one direction only (i.e. flat, but not fibre-like). This physically limits the range of angles of possible projections from 0 to only 140 degrees. The result is an incomplete tomography reconstruction with good image characteristics (strong edges, high SNR) along the equator of the sample, but poor characteristics near the poles. In an image analysis perspective, filtering and segmentation techniques must be adapted to cope with this situation. In particular, for segmentation, it is important to be able to interpolate over missing data at the poles in a controlled fashion, using for instance shape constraints. In this article we describe such a framework based on a minimal surface approach. We illustrate with applications to a number of bio-materials analysis problems.

Semantic Lattices for Multiple Annotation of Images
Anne-Marie Tousch (ENPC)
Abstract: We address the problem of describing precisely an object present in an image. The starting point is a semantic lattice defining all possible coherent object descriptions through inheritance and exclusion relations. This domain knowledge is used in a learning process which outputs a set of coherent explanations of the image valued by their confidence level. Our first contribution is to design this method for multiple complexity level image description. Our secondary focus is to develop rigorous evaluation standards for this computer vision task which, to our knowledge, has not been addressed in the literature despite its possible use in symbolic annotation of multimedia database. A critical evaluation of our approach under the proposed standards is presented on a new appropriate car database that we have collected.

Ventredi 17 octobre 2008

Formulating and Solving Continuous PDEs on Graphs with Application to Image Segmentation and Clustering
Leo Grady, Siemens Corporate Research
Abstract: The widespread variational methods of computer vision follow the pattern of establishing an energy for which the (local or global) minimum solution represents the desired segmentation, registration, filtering, etc. However, this energy is typically formulated in continuous space (with a continuous gradient), while the solving/testing operations are performed on a discrete computer. Ideally, we could reformulate our energy in terms of combinatorial operators that may be efficiently solved using combinatorial optimization techniques. The primary barrier to such a reformulation has not been the lack of established mathematics for translating between continuous and combinatorial operators, but rather a lack of familiarity in the computer vision community with the methods to produce the corresponding combinatorial operators.
I will begin by reviewing the correspondence between combinatorial and continuous differential operators and provide several examples showing how traditional theory translates exactly to the combinatorial domain.
This theory will then be applied to segmentation applications to develop the random walker algorithm and a fully combinatorial version of the Mumford-Shah functional. Traditional, level set based, solutions of the continuous Mumford-Shah functional will be thoroughly compared with an optimization of the combinatorial Mumford-Shah to demonstrate the superiority of this combinatorial formulation.