Abstract
From LRDE
C
La grammaire du standard du C++ n'ayant pas été conçue pour etre aisément analysable, son utilisation dans le cadre de la manipulation de programme est comparable à la complexité de l'AST généré par celle-ci. Le rôle de Centaur au sein de Transformers est ainsi de fournir une infrastructure générique permettant de manipuler et de synthétiser cet AST : les transformations de programmes sont simplifiées gràce a un accès plus aisé aux informations contenues dans l'arbre syntaxique et ses annotations. Grâce à cette bibliotheque, les tâches répétitives et souvent génératrices d'erreurs, comme l'énumération des éléments d'un conteneur ou la recherche des classes parentes d'une classe, seront factorisées par un ensemble de fonctions correspondant à un modèle modulaire et extensible. +
The C++ standard grammar was not thought to be easily parsable so its use in the context of program handling can be compared to the complexity of the AST generated by it. The aim of Centaur inside Tranformers is to propose a generic framework allowing to manipulate and digest this AST : program transformations are simplified thanks to an easier access to the parse tree data and its annotations. Thanks to this library, repetitive and error-prone tasks like enumerating a container's elements or the parent classes lookup of a class will be factorized by a function set corresponding to an extensible and modular model. +
Climb est une bibliothèque de traitement d'images générique développée en Lisp. Les voisinages sont representés sous la forme d'ensemble de sites (site-set) pour permettre des manipulations génériques sur de multiples types d'images. En parallèle de ce concept, une étude des voisinages pondérés est effectuéeexpliquant différents moyens d'étendre le concept d'une écriture unique des algorithmes pour les exécuter sur différents types de paramètres. Trois implémentations sont proposées, décrites et comparées au niveau de leur généricité et de leur expressivité. +
Climb is a generic image processing library developed in Lisp. Neighborhoods are represented as site-set to allow generic manipulation over multiple pictures type. Along these concepts, a study of weighted neighborhood representation is done, showing how we can extend the concept of writing algorithms once and running them over different parameters type. Three implementations are proposed, described and compared on both genericity and expressivity. +
La programmation orientée contexte est un paradigme prometteur pour prendre en compte les problématiques transverses dans le logiciel. Ce paradigme permet de spécialiser les classes et les méthodes en fonction du contexte. Cependant, il ne traite pas la coercitionc'est-à-dire la conversion d'un objet existant dans un certain contexte vers une nouvelle représentation dans un autre contexte. Nous montrons en quoi ce manque est critique, en fournissant des exemples extraits de Climbune bibliothèque de traitement d'images écrite en Common Lisp. Nous proposons des solutions pour la coercition automatique d'objets, et nous les analysons en termes de simplicité et de généricité. +
The Olena project provides a generic library for image processing, Milena. We want this library to feature many value types so that the user can always choose the relevant types for his application. For instance, we provide many grey-level types, many color types, etc. This seminar focuses on how we implement color types in Milena. There are different color spaces (RGB, HSI, and so on) and several possible encodings for the same color space (rgb_3x8, rgb_f, etc.). One objective of ours is to make things easy for the user. In particular, we want the user to handle color values without being concerned of internal mechanisms. For instance, in conversion formulas, we do not want to see the details of implementation (division by 255). +
go2pins est un outil utilisé pour interfacer un programme Go avec des outils de vérification formelle. À l'aide d'une série de transformations, un programme Go est compilé vers un programme au comportement identique, mais exposant une interface permettant d'itérer dans l'espace d'états de celui ci. Cependantgo2pins ne gère actuellement pas les programmes utilisant des goroutines, qui permettent l'exécution parallèle de fonctions. Dans ce rapport, nous présentons les solutions envisagées pour implémenter ce comportement dans go2pins, ainsi que les problèmes rencontrés. +
Comparaison entre le Fictitious Play et le Fictitious Play Alterné dans le cadre des jeux à somme nulle +
L'algorithme du Fictitious Play est un procédé d'apprentissage itéré utilisé dans le cadre de la recherche des équilibres de Nash. Son principe est simple : à chaque itération, chacun des joueurs “renforce” celle de ses stratégies pures qui est la plus efficace face à ses adversaires. Pour certains jeux, cet algorithme converge vers un équilibre de Nashfournissant ainsi un algorithme d'approximation efficace. La convergence ne peut toutefois être prouvée que pour un nombre limité de cas. L'algorithme du emphFictitious Play Alterné (présenté l'année dernière) en est une variante dans lequel seul le joueur le plus “éloigné” de son gain optimal renforce sa stratégie la plus efficace. Cette étude se focalisera sur une comparaison de l'efficacité de ces deux algorithmes dans le cadre des jeux à somme nulle et abordera également les notions de classification des jeux nécessaires à la réalisation de cet objectif. +
A l'heure actuelle, l'espace des i-vecteurs est devenu l'état de l'art pour les systèmes de reconnaissance du locuteur. La distance cosinus (CD) est la méthode de décision la plus utilisée. Elle utilise l'analyse discriminante linéaire (LDA) et la Within-Class Covariance Normalization (WCCN) afin de compenser globalement le canal. Le but de ce travail est de compenser localement le canal avant d'appliquer la CD. L'idée est de créer un graphe des i-vecteurs partitionné à l'aide d'algorithmes de détection de communautés, puis de projeter les segments test et target dans ce dernier. On sélectionne uniquement leur voisinage pour entrainer la LDA et la WCCN. Les résultats seront comparés avec la méthode de compensation globale. +
Model checking is a field of formal verification which aims to automatically test the behavior of a system with the help of logic formulae. Spot is a model checking library which relies on one technique: the automata-theoretic approach. In this approach, both system and formula are expressed with Büchi automata, which are automata on infinite words. Spot provides several algorithms to deal with these automata, with model checking as objective. However, an algorithm is missing: the complementation of Büchi automata. Because of its high complexity this algorithm is rarely used in practical, but it does not lack theoretical interests. We will present an implementation of this algorithm in Spot. +
Model checking is a field of formal verification which aims to automatically test the behavior of a system with the help of temporal logic formulae. Spot is a model checking library which relies on one technique: the automata-theoretic approach. In this approach, both system and formula are expressed with Büchi automata, which are automata on infinite words. Spot provides several algorithms to deal with these automata, with model checking as objective. An operation for automata was recently added in Spot : the complementation. Research of algorithms for this operation is still relevant today, since there is still no algorithm reaching the theoretical optimal bound. We will present two recent complementation algorithms implemented in Spot. +
Climb is a generic image processing library designed to be used for rapid prototyping. The implementation of two component trees algorithms impacts Climb in several ways: the definition of values is extended, new site sets are added and debugging utilities are improved. A detour is taken to understand the Chaining design pattern popularized by the Javascript jQuery library. The pattern is adapted to both the image processing domain and Common Lisp and is extended to introduce a parallel notation as well as better control flows. +
Pattern recognition and object detection are very important stakes in image processing. Many solutions have been provided; nevertheless the one based on component trees seems to be the most promising. A component tree allows to work on connected components at different gray-levels in the image. Thanks to this tree, we can use attributes as criteria to identify components, such a component being an object in the image. During this seminar, we present a component tree implementation, how to deal with attributes, different methods dedicated to component identification and a general processing chain that leads to object recognition. +
Les transducteurs sont utilisés dans beaucoup de contextes, comme la reconnaissance de parole ou le calcul de la similitude entre protéines. Un des algorithmes fondamentaux pour les manipuler est la composition. Ce travail présente l'algorithme basique de compositionpuis son extension à des transducteurs à transitions spontanées. Une adaptation paresseuse de l'algorithme est ensuite proposée, à la fois pour la composition et pour le pré-traitement (insplitting). Nous montrons ensuite que la version naïve de la composition variadique ne réduit pas la quantité de calculs nécessaires. Enfindes mesures de performances comparent l'implémentation de la composition dans Vcsn à celle d'OpenFST. +
Les transducteurs sont utilisés dans beaucoup de domaines, comme par exemple en linguistique pour modéliser des règles phonologiques, pour les expressions régulières, pour des languages de spécification, pour de la reconnaissance vocale... Quand on les manipule, un outil pour le moins indispensable est la composition. En tant que tel, il est essentiel de l'implémenter dans Vaucanson 2, de manière efficace. Ce rapport va présenter les fondations sur lesquelles s'appuie la composition de transducteurs, puis son implémentation et son optimisation. La composition est considérée ici comme un cas particulier du produit d'automates à transitions spontanées, donc trois algorithmes de produit sont présentés ici, suivi de concepts d'implémentation essentiels. +
Pour représenter un système par un automate, il faut sauvegarder toutes les valeurs des variables du système pour chaque état de l'automate. Cela peut prendre beaucoup de place en mémoire lorsqu'il y a beaucoup de variables et/ou d'états, et de fait ralentit le temps d'exécution à cause des défauts de cache. Pour contourner ce problème dans Spot, on utilise une simple compression du tableau contenant les variables d'un étatet ce pour chaque état, ce qui réduit la mémoire utilisée et aussi le temps d'exécution. Dans ce rapport, nous présentons une structure de données qui améliore la compression des variables en utilisant la redondance des valeurs présentes dans différents états, et les différents problèmes rencontrés lors de son ajout dans Spot. +
Computing optical flow can be a first step towards video inpainting. In such cases, one has to deal with video sequences where some parts, the ones to be inpainted, are missing. On the other hand, the optical flow can be computed either locally or globally. Global methods generally show better results. In the case of sequences with missing areas, the computation with global methods is not straightforward due to the lack of information in some regions. In this technical report, we introduce a method combining both global and local algorithms in order to compute the optical flow in such sequences, leading to an efficient and simple way to compute video inpainting. +
At the end of this decade will arise C++0x and with it the new “concept” paradigm. Concepts provide abstract types as well as all the equipment to adapt concrete types to their abstraction, just like Static library, a part of Olena project, does. We compare these two approacheshighlighting their respective strengths and weaknesses, in order to lay the foundations for the integration of concepts into SCOOP. In fact, concepts will simplify the client code and bring some new features to SCOOP. +