Séminaire de recherche A3SI
(2013-2014)

Lundi 7 juillet 2014 (2 exposés, 10h-12h)

Transfert de couleurs adaptatif par transport optimal relaxé
Julien Rabin, GREYC, Université de Caen
Résumé : Le transfert de couleurs consiste à modifier automatiquement les couleurs d'une image en s'inspirant d'une ou de plusieurs autres images données en exemple, tout en préservant la géométrie de l'image originale. De nombreuses approches ont été proposées dans la littérature qui consistent à manipuler directement la palette de couleurs (ou l'histogramme) de l'image traitée. Dans cet exposé, nous nous intéresserons en particulier aux méthodes qui exploitent le cadre du transport optimal de masse afin de définir une correspondance exacte entre les distributions couleurs des images traitées.
Bien que ce type d'approche soit tout à fait approprié d'un point de vue statistique, nous verrons que ces approches sont très couteuses en temps d'exécution et peuvent conduire à de mauvais résultats (apparition d'artefacts) en raison de l'absence de prise en compte de la géométrie des images.
Nous proposerons dans cette présentation une généralisation de ces méthodes permettant :
- un temps d'exécution rapide, grâce des approximations par modèles paramétriques et des estimations par maximum a posteriori;
- une régularisation spatiale combinée au dans domaine couleur pour préserver la géométrie et le constraste;
- une relaxation convexe et automatique des contraintes de correspondance des couleurs, de manière à s'adapter au contenu des images.

Toward Fast Transform Learning
François Malgouyres, Université de Toulouse
Abstract: The dictionary learning problem aims at finding a dictionary of atoms that best represents an image according to a given objective. The most usual objective consists of representing an image or a class of images sparsely. Most algorithms performing dictionary learning iteratively estimate the dictionary and a sparse representation of images using this dictionary. Dictionary learning has led to many state of the art algorithms in image processing. However, its numerical complexity restricts its use to atoms with a small support since the computations using the constructed dictionaries require too much resources to be deployed for large scale applications.
In order to alleviate these issues, this paper introduces a new strategy to learn dictionaries composed of atoms obtained as a composition of K convolutions with S-sparse kernels. The dictionary update step associated with this strategy is a non-convex optimization problem. We reformulate the problem in order to reduce the number of its irrelevant stationary points and introduce a Gauss-Seidel type algorithm, referred to as Alternative Least Square Algorithm, for its resolution. The search space of the considered optimization problem is of dimension KS, which is typically smaller than the size of the target atom and is much smaller than the size of the image. The complexity of the algorithm is linear with regard to the size of the image.
Our experiments show that we are able to approximate with a very high accuracy many atoms such as modified DCT, curvelets, sinc functions or cosines when K is large (say K=10). We also argue empirically that, maybe surprisingly, the algorithm generally converges to a global minimum for large values of K and S.

Jeudi 3 juillet 2014

Human-robot interaction
Vita Beran, Université technique de Brno
Abstract: The seminar introduces wide area of robotics with the focus on interaction between human and robots. The talk will include service robotics topics, the robotic system parts overview and selected results improving sensory data processing methods developed with focus on real-time execution and working in on-line manner (video on-line segmentation and fast depth map segmentation for indoor scenes). Seminar will include preliminary results of experiments with PR2 robot manipulator control for grabbing task comparing gamepad and gesture-based (using Leap Motion device) interaction. During the talk, Robo@FIT research group and its platform will be also briefly introduced.

Mercredi 2 juillet 2014

Total Variation Dictionary Model and Dictionary Learning for Image Recovery
Tieyong Zeng, Hong Kong Baptist University
Abstract: Image restoration plays an important role in image processing, and numerous approaches have been proposed to tackle this problem. This talk presents a modified model for image restoration, that is based on a combination of Total Variation (TV) and Dictionary approaches. Since the well-known TV regularization is non-differentiable, the proposed method utilizes its dual formulation instead of its approximation in order to exactly preserve its properties. The data-fidelity term combines the one commonly used in image restoration and a wavelet thresholding based term. Then the resulting optimization problem is solved via a first-order primal-dual algorithm. Numerical experiments demonstrate the good performance of the proposed model. Moreover, we replace the classical TV by the nonlocal TV regularization, which results in a much higher quality of restoration. We then turn to the dictionary learning problem for image recovery. Various numerical results on non-Gaussian noises and image decompression illustrate the superior performance of our approach.

Vendredi 27 juin 2014

Geometric separators and their applications
Nabil Hassan Mustafa, A3SI, LIGM, ESIEE
Abstract: Given a graph G=(V,E), a separator is a set of vertices of G whose removal partitions the graph into two smaller sets with no edges between the two sets. A celebrated result of Lipton-Tarjan from 1979 shows the existence of separators of small size in planar graphs. Since then, separators have found many uses in the design of exact and approximate algorithms for optimization problems. Recently Adamaszek-Wiese proved the existence of a wide variety of separators for geometric objects. Using these, they presented QPTAS for weighted independent set of polygonal regions. Building on their ideas, we now present a QPTAS for geometric set-cover problems. This talk will present this result, as well as survey the use of separators in algorithmic design.

Jeudi 19 juin 2014

Atelier doctotants

Une nouvelle méthode de binarisation hybride basée sur l'algorithme Kmeans
Mahmoud Soua, LIGM, ESIEE
Résumé : Dans le cadre de l'élaboration d'un système OCR robuste, nos recherches portent sur deux volets principaux. D'abord, une contribution algorithmique qui améliore la qualité d'extraction du texte à partir des images couleurs scannées. Ensuite, une amélioration du temps d'exécution de ces algorithmes en exploitant des architectures multi-coeurs. Dans un premier temps, nous avons proposé une nouvelle méthode de binarisation qui combine des approches locales et globales et qui se base l'algorithme de classification Kmeans (HBK). En effet, la binarisation des documents est une étape de traitement fondamentale pour la reconnaissance optique de caractères (OCR). Le coté hybride de la méthode proposée permet de bien séparer localement le texte du fond et d'éviter les effets de bords et les artefacts. D'après nos expériences, la méthode HBK améliore la qualité de binarisation par rapport à plusieurs méthodes dans la littérature.

Continuously indexed Potts models on unoriented graphs with applications to urban modelling
Loïc Landrieu, LIGM, IMAGINE
Résumé : We present an extension of the classical continuous time Markov chains to undirected graphical models. This is achieved by constructing an homogeneous Potts process indexed by the continuum of points forming the edges of the graph. We show that our parameterization satisfies Kolmogorov consistency, and that classical inference and learning algorithms can be applied.
We then apply our model to a problem from geomatics, namely that of labelling city blocks automatically with a simple typology of classes (e.g. collective housing) from simple properties of the shape and sizes of buildings of the blocks.

Improved algorithm for hitting sets
Norbert Bus, LIGM, ESIEE
Abstract: Computing small-sized hitting sets for geometric objects is a basic combinatorial problem in geometry. In this talk we present new results on a fundamental problem: given a set of disks D and a set of points P in the plane, compute a small-sized subset of P that hits all the disks in D. We present an improved approximation algorithm for this problem, which computes a 14-approximation in near-linear time. The main technical result is an improved algorithm, as well as new combinatorial bounds on epsilon-nets for disks. We present empirical evidence contrasting our algorithm with previous work.

Reporté - date à définir

Algèbre Géométrique et Informatique Graphique
Laurent Fuchs, XLIM-SIC, Université de Poitiers
Résumé : Cet exposé présente l'algèbre géométrique qui est une alternative à la représentation usuelle des objets géométriques et de leurs transformations. Ce formalisme s'est particulièrement développé en informatique graphique depuis une quinzaine d'années.
Le choix de la représentation des objets géométriques est une question importante en informatique graphique. De ce choix dépend la façon dont sont développés les algorithmes de manipulation des objets géométriques et les transformations géométriques que l'on peut leur appliquer. Il est bien connu que l'utilisation de l'algèbre linéaire se révèle mal adaptée dans certaines situations. Pour contourner les problèmes rencontrés, différentes approches ont été proposées ; les coordonnées homogènes, les coordonnées de Plücker, les quaternions, les espaces de Grassmann etc. Aucune de ces approches ne peut, à elle seule, exprimer la totalité des manipulations géométriques nécessaires. Cela oblige, à d'incessants aller-retour pour la représentation d'un même objet géométrique et les connexions entre ces approches ne sont pas toutes évidentes. Il semble que l'on ait à faire à un agrégat de formalismes dans lequel on peine parfois à s'y retrouver.
L'algèbre géométrique intègre et étend en dimension ces différents formalismes (coordonnées de Plücker, quaternions, nombres complexes, produit vectoriel). On obtient ainsi un langage de haut niveau pour décrire les algorithmes géométriques. Cette algèbre est une interprétation géométrique de l'algèbre de Clifford. Ce point de vue géométrique sur l'algèbre de Clifford a été réactivé par le physicien américain D. Hestenes dans les années 60. Son intérêt en informatique graphique n'a cessé d'être démontré depuis une quinzaine d'années. L'idée est de développer un "calcul" (une algèbre) géométrique afin de faire le lien entre le langage synthétique de la géométrie (où l'on parle de points, de droites, de cercles, etc.) et le langage analytique de la géométrie (où l'on exprime un calcul sur des coordonnées). De cette façon, on peut utiliser les objets géométriques (directions, points, droites, plans, cercles et sphères) comme des primitives de calcul. La principale difficulté de mise en oeuvre de l'algèbre géométrique vient de la dimension de l'espace vectoriel utilisé. Il existe cependant des méthodes efficaces pour l'implanter.

Jeudi 3 avril 2014

Atelier doctotants

Tubular Structure Filtering by Ranking Orientation Responses of Path Operators
Odyssée Merveille, LIGM, ESIEE
Abstract: Thin objects in 3D volumes, for instance vascular networks in medical imaging or various kinds of fibres in materials science, have been of interest for some time to computer vision. Particularly, tubular objects are everywhere elongated in one principal direction - which varies spatially - and are thin in the other two perpendicular directions. Filters for detecting such structures use for instance an analysis of the three principal directions of the Hessian, which is a local feature. In this article, we present a low-level tubular structure detection filter. This filter relies on paths, which are semi-global features that avoid any blurring effect induced by scale-space convolution. More precisely, our filter is based on recently developed morphological path operators. These require sampling only in a few principal directions, are robust to noise and do not assume feature regularity. We show that by ranking the directional response of this operator, we are further able to efficiently distinguish between blob, thin planar and tubular structures. We validate this approach on several applications, both from a qualitative and a quantitative point of view, demonstrating noise robustness and an efficient response on tubular structures.

Image Parsing with Graph Grammars and Markov Random Fields
Mateusz Kozinski, LIGM, IMAGINE
Abstract: Existing approaches to parsing images of objects featuring complex, non-hierarchical structure rely on exploration of a large search space combining the structure of the object and positions of its parts. The latter task requires randomized or greedy algorithms that do not produce repeatable results or strongly depend on the initial solution. To address the problem we propose to model and optimize the structure of the object and position of its parts separately. We encode the possible object structures in a graph grammar. Then, for a given structure, the positions of the parts are inferred using standard MAP-MRF techniques. This way we limit the application of the less reliable greedy or randomized optimization algorithm to structure inference. We apply our method to parsing images of building facades. The results of our experiments compare favorably to the state of the art.

Vers un arbre des formes pour les images multivariées: problèmes, pièges et pistes
Edwin Carlinet, LIGM, EPITA
Résumé : En offrant une représentation morphologique, hiérarchique et auto-duale d'une image, l'arbre des formes fournit une structure puissante qui s'adapte à de nombreuses applications de traitement d'images. L'arbre des formes reflète l'organisation des composantes d'une image du point de vue de l'inclusion de ses lignes de niveaux. Alors qu'une représentation topographique d'une image en niveaux de gris existe, son extension aux images multivariées (couleurs, multi-spectrales...) pose problème. Dans cet exposé, nous allons étudier les pistes pour étendre l'arbre des formes aux images en couleurs en présentant les approches classiques mais aussi en proposant de nouvelles approches. Ces différentes pistes seront évaluées à travers du débruitage afin de mettre en évidence leurs forces et leurs faiblesses.

Interactive Global Illumination for Games using Topological Information
Laurent Noël, LIGM, UPEM
Abstract: Indirect Illumination is a key element to achieve realistic rendering. Unfortunately, since computing this effect is costly, there are few methods that render it with real time frame rates. In this paper we present a new experimental method based in virtual point lights and topological information about the scene to render indirect illumination at interactive frame rate.

Vendredi 28 mars 2014

The Flutter Shutter Provides a Blind Uniform Motion Blur Deconvolution Filter
Yohann Tendero, UCLA
Abstract: This talk is about a revolutionary camera concept called "flutter shutter". Flutter shutter cameras promised to increase the image quality when photographing moving objects. The talk gives a mathematical theory and formulas that answer the questions on these recent camera designs. The theory is also proved to be valid for the "motion invariant photography": the only other competitor of the "flutter shutter". An unexpected consequence of this theory is the existence of a filter that makes blind uniform motion blur deconvolution well posed for moderate blurs.

Jeudi 27 mars 2014

Calibration of Ultra-Wide Fisheye Lens Cameras by Eigenvalue Minimization
Kenichi Kanatani, emeritus professor at Okayama University (Japan)
Abstract: I present a new technique for calibrating ultra-wide fisheye lens cameras by imposing the constraint that collinear points be rectified to be collinear, parallel lines to be parallel, and orthogonal lines to be orthogonal. Exploiting the fact that line fitting reduces to an eigenvalue problem in 3-D, I do a rigorous perturbation analysis to obtain a practical calibration procedure. Doing experiments, I point out that spurious solutions exist if collinearity and parallelism alone are imposed. My technique has many desirable properties. For example, no metric information is required about the reference pattern or the camera position, and separate stripe patterns can be displayed on a video screen to generate a virtual grid, eliminating the grid point extraction processing.

Jeudi 13 février 2014

Évaluation (sans vérité terrain) de méthodes de segmentation d'images médicales
Frédérique Frouin, UPMC
Résumé : Le groupe MEDIEVAL, soutenu par le GDR Stic Santé et regroupant une dizaine de laboratoires français, a eu pour objectif le développement de stratégies d'évaluation de méthodes de segmentation d'images médicales. En pratique le travail a porté sur une base de données expertisée d'examens d'IRM cardiaques acquis sur 45 sujets. L'objectif clinique est de définir les contours endocardiques et épicardiques du ventricule gauche afin d'estimer des paramètres cliniques tels que le volume ventriculaire en télésystole et en télédiastole, le volume myocardique et la fraction d'éjection du ventricule gauche.
Dans une première étape, différentes méthodes de segmentation 3D et 4D, issues de différents laboratoires, ont été appliquées à cette base de données et comparées au tracé réalisé par un expert. Différents critères d'évaluation ont été proposés pour comparer les méthodes : des critères classiquement utilisés en traitement d'images (indice de Dice, distance entre contours) et un critère statistique permettant d'évaluer la qualité de l'estimation d'un paramètre clinique, critère que nous avons proposé pour classer différentes méthodes de segmentation sans faire l'hypothèse de l'existence d'un tracé de référence (eRWT extended Regression Without Truth). Les hypothèses sous-jacentes à cette approche et la méthode d'estimation seront présentées. Les résultats obtenus sur l'exemple précité illustrent l'intérêt de cette méthode.
Dans un second temps, nous avons combiné par la technique STAPLE différentes approches de segmentation pour utiliser les complémentarités pouvant exister entre les différentes méthodes de segmentation d'images et définir une stratégie optimale adaptée à chaque patient. Les résultats montrent l'intérêt de cette démarche. Nous terminerons en présentant une approche alternative de combinaison de différents jeux de segmentation, appelée forme mutuelle, dont l'estimation repose sur une approche variationnelle, en cours d'évaluation dans le groupe MEDIEVAL.

Mercredi 29 janvier 2014

Qualification et quantification de l'aptitude au changement des territoires Indiens
Joan Perez et Jean Grebert, Renault France
Résumé : L'Inde est souvent perçue par les grandes entreprises occidentales comme un des nouveaux eldorados des pays émergents de part ses processus d'urbanisation et son industrialisation croissante. Mais, la réalité Indienne est tout autre. En valeur absolue, la population indienne a augmenté de 181 millions d'habitants entre 2001 et 2011 contre 79,5 millions pour le nombre de travailleurs à temps plein. De plus, le système agraire intensif en zone rurale a contribué à établir une concurrence féroce entre agriculteurs tout en réduisant le nombre de propriétaires terriens. Ainsi, l'augmentation du niveau de vie liée à la croissance économique ne sera pas distribuée de façon homogène sur un territoire où les clivages socio-économiques sont déjà accentués par un système hermétique de castes. De surcroit, l'Inde est un espace qui possède une histoire urbaine longue et complexe. Il en résulte une multitude de systèmes urbains fonctionnels aux caractéristiques internes et externes variées. La délimitation avec l'espace rural devient de plus en plus difficile à définir, mais surtout impossible à généraliser à l'ensemble de ce pays du fait de son immensité.
Cette étude s'insère dans un programme de recherche plus vaste financé par Renault et ayant pour objectif l'étude des transformations socio-économiques et des niveaux de vie des ménages indiens comme préalable à une redéfinition des politiques de pénétration commerciale dans le subcontinent. Dans cette étude, chacun des 640 districts de l'Union Indienne est considéré comme un écosystème jouissant d'un potentiel de transformation socio-économique et territoriale. Cet article a pour objectif de caractériser par une classification multivariée de type Bayésien le degré de réaction au changement d'état de ces écosystèmes. L'hypothèse étant qu'il est possible de déterminer à quel degré un district indien est propice à l'innovation et, dans le cas de cet article, au passage in situ à un type fonctionnement plus "moderne". Plusieurs cas de figures regroupent ces observations : du district faisant partie intégrante d'une agglomération au district non-urbanisé. Les résultats préliminaires obtenus en étudiant la dynamique décennale 2001-2011 par la caractérisation bayésienne des facteurs internes (variables socio-économiques, consommation, emploi, urbanisation, etc.) et externes (degré de métropolisation, appartenance à des macrostructures urbaines, etc.) des 640 districts indiens seront présentés ainsi que les différents axes de recherche de l'entreprise Renault en Inde.

Jeudi 16 janvier 2014

Learning Graphs for Matching
Minsu Cho - INRIA/ENS, projet WILLOW
Abstract: Establishing correspondences between two sets of visual features is a key problem in computer vision, with applications in tasks such as image retrieval, shape matching, and object recognition. The correspondence problem is often formulated as a graph matching task to model spatial relationships among feature points. This results in a quadratic assignment problem, which requires approximate solutions. Indeed, many of the previous works have focussed on developing fast and accurate algorithms in this context. The graph model used for matching in these works is, however, either hand-crafted or only learned partially, and the problem of learning the structure of the model remains a challenging issue. This talk will present an effective scheme to parameterize the graph model, and learn its structural attributes for visual object matching. To this end, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. We demonstrate the effectiveness of our approach on synthetic and real image datasets. This is joint work with Karteek Alahari and Jean Ponce.

Vendredi 6 décembre 2013

Embeddings of simplicial complexes - a survey from a computational viewpoint
Uli Wagner - Institut für Theoretische Informatik ETH Zürich
Abstract: Graph planarity is a basic theme in graph theory as well as in discrete and computational geometry.
The analogous questions in higher dimensions, i.e., embeddings of finite simplicial complexes into Euclidean spaces, are a classical topic in topology, and more recently, have also become the subject of systematic study from a computational viewpoint.
In this talk, we survey recent results concerning the algorithmic question of deciding whether a given k-dimensional complex K embeds into d-space.
The computational complexity of this problem depends in an interesting way on the parameters (k,d), and different ranges of these parameters require methods from different areas, including 3-manifold theory, classical piecewise-linear topology, and homotopy theory.
The necessary topological notions will be introduced along the way.
Joint work with Martin Čadek, Marek Krčál, Jiří Matoušek, Eric Sedgwick, Francis Sergeraert, Martin Tancer, Lukas Vokřínek

Mercredi 6 novembre 2013

Local image analysis using higher-order Riesz transforms
Ross Marchant, James Cook University / CSIRO Computational Informatics
Abstract: The Reisz transform is a mathematical operator that has been the subject of recent image analysis research. It can be used to model local image structure as a superposition of sinusoids, where phase describes feature type (line or edge) and amplitude describes feature strength. The advantage of this split of identity is that local symmetry can be analysed separately from overall intensity.
In this talk, we introduce an expanded set of signal models based on the Riesz transform. The single sinusoidal model of the monogenic signal is modified to have a residual component, allowing higher-order Reisz transforms to be included in the derivation. This improves the parameter estimation and leads to a method of detecting junctions and corners.
Following on, a multi-sinusoidal model consisting of any number of sinusoids is described, allowing features consisting of any number of lines or edges to be analysed. To find the sinusoid parameters, a recent method from super-resolution theory is applied.
Finally, junctions and corners are not well modelled by sinusoids. To analyse these features we propose a model consisting of the superposition of a 2D steerable wavelet at multiple amplitudes and orientations. This component wavelet corresponds to either a line segment or an edge segment, depending on the feature of interest.

Jeudi 24 octobre 2013

Learning the Graph of Relations Among Multiple Tasks
Andreas Argyriou, Ecole Centrale Paris
Abstract: Multitask learning can be defined as the problem of learning multiple supervised tasks jointly, in the presence of relations among the tasks. In particular, some widely studied problems in machine learning, statistics, data mining and signal processing, like matrix completion and recommendation systems, can be viewed within the framework of multitask learning. More generally, multitask learning has found a diverse range of applications from collaborative filtering and recommendation problems like Netflix to finance, to text classification, to clustering etc.
In this talk, we propose multitask Laplacian learning, a new method for jointly learning clusters of closely related tasks. Unlike standard multitask methodologies, the graph of relations among the tasks is not assumed to be known a priori, but is learned by the multitask Laplacian algorithm. Our algorithm builds on reproducing kernel methods and exploits an optimization approach for learning a continuously parameterized kernel. A subproblem involves a semidefinite program of a particular type, for which we develop an algorithm based on Douglas-Rachford splitting. Multitask Laplacian learning can find application in cases in which tasks are related with each other to varying degrees, some strongly, others weakly. Our experiments highlight such cases in which multitask Laplacian learning outperforms state of the art multitask methods. They also demonstrate that our algorithm partitions the tasks in clusters, each of which contains well correlated tasks.
(Joint work with Ruocong Zhang and Stephan Clemencon)