Programme: 2010-2011

Alexander Gepperth (21/06/2011)

• Titre:
  From intelligent vehicles to developmental learning
• Résumé:
  
  The presentation has two goals: one the one hand, it should give an overview over my past scientific work, and on the other hand outline my research plans at ENSTA.

  In the first part of the presentation I will describe my major work of the past year about biologically inspired top-down control of object detection in challenging scenarios, especially inner-city traffic. Inner-city traffic is a good test scenario for object detection since it unites many prominent challenges in a very pronounced way. Apart from the preceptual problems of outdoor environments, image information is inherently ambiguous: windows may look like cars, trees can look like pedestrians or vice versa. One of my fundamental research assumptions is that human environment perception achieves the required disambiguation by relying strongly on learned models (which I term "system-level models") that integrate multiple modalities and processing steps. To state this more bluntly: I assume that it is really the combination of algorithms and modalities that achieves high performance, not so much the individual algorithms themselves. Consequently, I will describe my work on the discovery and application of system-level models in a large-scale vehicle detection system. This system was developed and tested in collaboration with colleagues at Honda Research Institute. The main scientific focus is on enhancing "bottom-up" visual object detection by "top-down" influences based on various types of multi-modal scene context, the special point being that top-down signals are obtained from system-level models that are trained on-line. An extensive evaluation in complex inner-city environments under a range of adverse conditions (rain, night, snow) conclusively showed that a very significant increase in detection as well as generalization performance can be achieved in this way. I will briefy discuss developmental aspects of this system, explaining how laser sensors can be used to bootstrap the complete training process of visual object detection.

  In the second part of the presentation, I will explain my research plans for developmental learning in both automotive and robotic scenarios. The foundation for this research is the idea that, in the absence of direct supervision, a major driving force for learning is predictive utility (see [2] for background). Put in a simplified way, a "good" concept allows to predict other (internal) quantities, whereas a "bad" concept does not. This mechanism should be equally valid at the low level where "good" features allow to predict the position of other features, whereas high-level concepts like object categories allow, e.g., the prediction of affordances or categories from other modalities. I propose a two-stage neural learning algorithm implementing statistical learning as well as predictive utility and discuss its embedding into hierarchical, multimodal processing systems which develop in an incremental way by interaction with their environment. Such agents will initially be realized by simulated vehicles but also by real robots in the mid term.

Stéphane Bazeille (09/06/2011)

• Titre:
  Mobile Robots Autonomous Navigation Using Vision And Odometry
• Résumé:
  
  This talk will present my work on topo-metrical mapping and autonomous navigation in topo-metric maps. We have developed localization and mapping methods by combining appearance based loop-closure detection with the metrical information given by the odometry. It allows the robot to build consistent topo-metrical maps of its environment and makes autonomous navigation tasks light and robust. The main idea is to use the odometry to navigate while correcting our position as often as possible using visual information.

Isabelle Puaut (17/05/2011)

• Titre:
  Estimation de pires temps d'exécution (WCET - Worst-Case Execution Times): des architectures mono-coeurs aux systèmes multi-coeurs
• Résumé:
  
  Les systèmes temps-réel strict nécessitent de respecter leurs contraintes de temps dans tous les scéarios d'exécution, y compris le pire. Ainsi, les méthodes de vérification d'ordonnançabilité se basent sur la connaissance du pire temps d'exécution de chaque tâche du systèmes. Cette présentation dresse un état de l'art de l'existant en terme de méthodes d'estimation de pires-temps d'exécution (en anglais WCET, pour Worst-Case Execution Times). Après une brève une présentation des défis liés à l'estimation des WCET et une classification des grandes familles de techniques d'estimation (statiques, dynamiques) d'estimation des WCET, nous nous concentrerons sur les méthodes d'estimation opérant par analyse statique des programmes. Nous insisterons tout particulièrement sur l'analyse dite de bas-niveau (niveau matériel) car les éléments matériels d'amélioration des performances tels que les caches ou l'exécution pipelinée nécessitent le développement de méthodes d'analyse adaptées. En particulier, nos travaux les plus récents sur le support d'architectures multi-coeurs seront présentés.

Omer Nguena-Timo (04/05/2011)

• Titre:
  Sélection des cas de test des systèmes temporisés modélisés par des VDTA.
• Résumé:
  
  Le test est une activité importante du cycle de développement logiciel. Nous considérons le test de conformité qui consiste à vérifier que les sorties observables d'une implantation sont celles définies dans la spécification. La spécification est décrite à l'aide du modèle VDTA que nous avons introduit. Le modèle VDTA (Variable Driven Timed Automata) est adapté pour décrire des systèmes temporisés à entrées/sorties. Nous présenterons la relation de conformité adaptée pour ce modèle, un algorithme de test à la volée et un algorithme de sélection des tests à base des objectifs de test.

Olivier Bouissou (26/04/2011)

• Titre:
  Probabilistic affine forms - A first step towards the static analysis of probabilistic numerical programs
• Résumé:
  
  In the context of numerical software verification, a major difficulty is to handle correctly and precisely the inputs of the program. These inputs are given by sensors and suffer from two kinds of uncertainty: their value lie within a non deterministic range and they are affected by a probabilistic noise. Thus, if one wants to rigorously and precisely model such sensors, it is necessary to mix, in the static analysis of programs, non-deterministic and probabilistic behaviors. In this talk, I will present the first results we obtained in this direction. More precisely, I will present how P-Boxes can be seen as an abstract domain in the sense of the abstract interpretation theory and why they suffer from the same drawbacks as intervals. Then I will present an evolution of affine sets that include both probabilistic and non-deterministic behaviors, while keeping a good precision by considering linear relations between variables.

Adrien Angeli (13/04/2011)

• Titre:
  Combination of structure and appearance information for efficient keyframe retrieval
• Résumé:
  
  It is now well understood that reliable incremental SfM or SLAM can only be achieved if the associated problem of loop-closure detection is appropriately handled. Recent advances in purely visual topological place recognition have demonstrated that operation over vast scale or very long periods of time was feasible at a manageable cost, using techniques inspired by context-based information retrieval. Such approaches however neglect most, if not all, of the geometry information provided by the estimated structure of the scene. Yet, this information is crucial for robust loop-closure detection when the level of perceptual aliasing is high, or to enable recognition across significant viewpoint variations. The integration of feature-based map information into the topological framework of place recognition is however not trivial, nor is the problem of combining appearance and structure information at a low level for loop-closure detection. Also, with the advent of dense SfM and SLAM solutions, new challenges have arisen: though in theory it is expected that the availability of dense scene models should improve place recognition performance, it is not clear how all the provided information should be in practise efficiently summarised to enable affordable computational cost, especially in the case of live operation. In this talk, we will present recent achievements on the combination of structure and appearance information for efficient keyframe retrieval, demonstrating improved performance over purely appearance-based solutions in the case of significant viewpoint variations. We will also present on-going work on efficient dense keyframe characterisation and matching, with an emphasis on our latest developments on the shape description front. Finally, we will end the presentation with prospects about potential applications of reliable SLAM and place recognition to semantic mapping and autonomous indoor navigation and free space mapping using vision as the unique sensing modality.

Tali Sznajder (12/04/2011)

• Titre:
  Synthèse de systèmes distribués ouverts
• Résumé:
  
  Le problème de synthèse, aussi appelé problème de Church, consiste à produire automatiquement un programme à partir de sa spécification. La spécification est la description des comportements corrects attendus du système, et est décrite par une formule logique (typiquement, en logique temporelle). Le programme à synthétiser doit fonctionner pour un système ouvert, c'est-à-dire pour un système en interaction avec un environnement incontrôlable. Il est représenté par une fonction mettant en relation la suite d'entrées reçues avec les sorties à produire. Dans le cas de systèmes centralisés, le problème est décidable, et des outils commencent à être développés.
  Le problème peut également se poser dans le cas de systèmes distribués, c'est-à-dire de systèmes constitués de plusieurs processus coopérant, et interagissant avec un environnement "hostile". Dans ce cas là, le problème revient à synthétiser un programme pour chaque processus du système, et il est indécidable en général.
  Je présenterai dans cet exposé mes travaux sur ce dernier problème : en particulier, j'ai cherché à comprendre les causes d'indécidabilité, afin de poser les restrictions les plus naturelles possibles afin d'obtenir des sous-classes décidables.

Benoît Robillard (05/04/2011)

• Titre:
  Vérification formelle et optimisation de l'allocation de registres
• Résumé:
  
  La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.
  L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisament importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.
  Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. La nature des travaux présentés dans cet exposé est double : d'une part la vérification formelle d'algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part la définition de nouveaux algorithmes optimisants pour cette étape de compilation.
  Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous présenterons ainsi la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing, et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle.
  Nous aborderons ensuite l'étude de deux représentations intermédiaires de programmes, dont la forme SSA, et l'exploitation de leurs propriétés pour proposer de nouvelles approches de résolution optimale de l'élimination des copies, l'une des optimisations opérées lors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères graphiques tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes.

Jean-Philippe Tarel et Aurélien Cord (29/03/2011)

• Titre:
  Aperçus sur l'analyse des images routières au LEPSIS et LIVIC
• Résumé:
  
  Le Lepsis et le Livic sont deux équipes de l'Ifsttar qui travaillent sur l'analyse des images routières à partir d'une ou plusieurs caméras embarquées sur un véhicule. Deux types applications sont traitées : le diagnostique des infrastructures et les aides à la conduite. Après une présentation des grands axes de travail de ces deux équipes, nous détaillerons deux types de méthodes récentes permettant de faire :

  • la détection des panneaux et l'estimation de leur saillance
  • la restauration des images en conditions dégradées, pluie et brouillard

Mathieu Dubois (22/03/2011)

• Titre:
  Temporal Bag-of-Words: a generative model model for visual place recognition
• Résumé:
  
  Nous présntons les travaux menés au LIMSI dans le domaine de la reconnaissance de lieux par un robot mobile. Ces travaux combinent les méthodes BoW avec une caractérisation globale des images grâce à une règle d'intégration simple. Nous montrons les résultats de la méthode sur la base COLD et nous dressons quelques pistes d'améliorations.

Thibault Hilaire (10/03/2011)

• Titre:
  Implantation 'optimale' d'algorithmes de traitement du signal en virgule fixe
• Résumé:
  
  Pour des contraintes de coût et de consommation, la plupart des algorithmes du traitement du signal embarqués sont réalisés numériquement en arithmétique à virgule fixe (arithmétique entière). Cela peut avoir pour principal inconvénient une complexité de mise en oeuvre et une dégradation des performances (dues aux erreurs d'arrondis et de représentation). Dans cet exposé, je présenterai la problématique de l'implantation matérielle ou logicielle de tels algorithmes : il s'agira de trouver, pour un algorithme donné (ici, un filtre), la "meilleure" réalisation en terme de précision numérique, de performances et de coût matériel (consommation, temps de calcul, surface, etc.). On s'appuiera sur l'exploration des réalisations équivalentes (même relation entrées-sorties) et sur une approche analytique du problème. Un exemple concret illustrera la problématique et la démarche présentée.

Pierre Bessiere (15/02/2011)

• Titre:
  Probabilistic models of sensory-motor systems
• Résumé:
  
  We argue that the main problem both living and artificial sensory-motor systems have to face is: How to survive (perceive, reason, learn, decide and act) with incomplete (and uncertain) information ? We propose that subjective (Bayesian) probability, considered as an alternative to logic is the relevant mathematical and operational framework to address this challenge. Consequently, we will try to answer three questions, giving some examples for each of them:

  • How to develop better artifacts using Bayesian reasoning?
  • Is there any biological plausibility of Bayesian reasoning at a macroscopic (behavioral) level?
  • Is there any biological plausibility of Bayesian reasoning at a microscopic (cellular and sub-cellular) level?

Matthieu Garrigues (01/02/2011)

• Titre:
  Parallel ordering for exact and approximate median splitting
• Résumé:
  
  Median filtering has been widely used in computer vision, especially for image denoising. Compared to mean filtering, it preserves contours but it is less trivial to implement. I will present in this seminar some ideas about a new way to compute the exact or approximate median. The goal of our algorithm is to take advantage of the emerging massively parallel architectures like graphic processor units (GPUs).

Mustafa Suphi Erden (11/01/2011)

• Titre:
  How things are going in the BioMechanical Engineering Department at TU Delft
• Résumé:
  
  This talk is intended to introduce the management of interaction and cooperation between the different research groups in the BioMechanical Engineering at Delft University of Technology, The Netherlands. The goal is to overview the practices there and perhaps get some inspirations for arrangements in the same direction at ENSTA. My talk will aim at highlighting the "discussion culture" of the Dutch and the "research management" of my Japanese Professor Tetsuo Tomiyama. In order to achieve this I will briefly introduce the organizational structure and research meetings within the BioMechanical Engineering and within the Intelligent Mechanical Systems group led by Prof. Tomiyama.

Clément Balabriga (03/12/2010)

• Titre:
  Vérification de contraintes temporelles strictes sur des programmes par composition d'analyses partielles
• Résumé:
  
  Les systèmes temps-réel critiques doivent impérativement obéir à des contraintes temporelles strictes. Le respect de ces contraintes doit donc être prouvé, et le calcul de pire temps d'exécution (WCET ou Worst Case Execution Time) joue un rôle important dans cette preuve.
  Le calcul de WCET par analyse statique est généralement réalisé sur un programme entier. Ceci présente deux inconvénients : la plupart de ces méthodes de calcul voient leur temps d'exécution augmenter de manière non linéaire par rapport à la taille de la tâche à analyser, et un problème se pose lorsque cette tâche est constituée de plusieurs composants (dont certains ne sont pas disponibles au moment de l'analyse).
  Il est donc nécessaire d'introduire une approche d'analyse partielle, permettant d'analyser séparément les composants d'un programme, produisant un résultat de WCET partiel pour chaque composant. Ces résultats partiels peuvent ensuite être composés pour obtenir le WCET du programme.
  Le calcul de WCET comporte plusieurs analyses dont les résultats sont exprimés sous forme d'un système ILP, qui doit ensuite être résolu pour obtenir le WCET. Chaque analyse doit être adaptée pour faire de l'analyse partielle. Cette adaptation sera illustrée à l'aide de diverses analyses existantes, et une formulation générale pour l'analyse partielle sera donnée. Il sera ensuite montré qu'il est possible d'utiliser l'analyse partielle afin d'accélérer la résolution ILP. L'expérimentation montre que l'analyse partielle permet de réduire le temps de calcul et de traiter le cas des programmes avec composants, sans rajouter trop de pessimisme.