Abstract
From LRDE
R
This report presents the implementation of an efficient and generic way to generate random weighted automata. To do so, we use a previously established relations between some known sets and the set of accessible DFA with n states. By extending these relations to the weighted case, we generalize the presented algorithm and we show an implementation in the Vcsn platform. +
In this report, we present the implementation of an efficient and generic algorithm to generate random weighted rational expressions, including multitape rational expressions. It support any operators, labels and weights present in Vcsn. This tool allows a better coverage for the tests. We also present a way to generate random paths on weighted automata. +
The Vaucanson library is designed to manipulate automata and transducers. Therefore we need a rational expression parser which deals with transducers. The current rational expression parser only takes as input weighted rational expression. The new parser allows us to specify any kind of weight and any kind of monoid like free monoid product. Both of these features are mandatory if we want to deal with transducers. The new parser is also less restrictive and provides more freedom to the user who can easily change the form of the grammar used to write its expression. +
... Insert an abstract in English here ... +
Le recalage d'images est une technique classique en traitement d'image. Soit A et B deux images représentant le même objet (par exemple une radiographie et une image à résonance magnétique (IRM)), on calcule une transformation de A telle que le recalage de l'objet dans A soit aligné sur l'objet dans B. Typiquement, cette technique peut permettre la lecture simultanée de deux mesures A et B. Cet exposé discutera des procédés de recalage rapide utilisés dans Milena, la bibliothèque C++ générique de traitement d'image de la plate-forme Olena, développée au LRDE. Certaines améliorations seront présentées. +
Dans un précédent rapport nous présentions le test de vacuité bi-bande dans la bibliothèque Spot, qui vérifie que l'intersection des langages de deux ω-automates est vide sans construire leur produitce qui permet de contourner une limitation de Spot sur le nombre d'ensembles d'acceptations de ces automates. Cette opération, lorsque l'intersection n'est effectivement pas vide, est généralement suivie d'une recherche de chemin acceptant sur le produit qui expose un mot qui se trouve dans les langages des deux automates. Nous présentons une nouvelle fonction qui réalise cette recherche de chemin acceptant à partir des données générées par le test de vacuité bi-bande, ce qui nous permet d'utiliser ces nouvelles méthodes dans des algorithmes qui nécessitent la recherche d'un contre-exemple. +
Le probléme de recherche de mots synchronisants les plus courts possible est un probléme important qui a beaucoup d'applications (orienteurs mécaniques, probléme de coloration de route, vérification de modélesbioinformatique, protocoles réseaux, etc.) Un mot synchronisant (ou une séquence de réinitialisation) pour un automate fini déterministe est une séquence d'étiquettes qui envoie n'importe quel état de l'automate d'entrée à un seul et même état. Trouver le plus court mot synchronisant dans un automate général est NP-complet, c'est pourquoi la plupart des algorithmes sont des heuristiques qui cherchent à trouver des mots les plus courts possible en temps polynomial. Dans ce rapport, nous comparerons les différentes approches utilisées par les algorithmes principaux les plus connus (Glouton, Cycle, SynchroP, SynchroPL et FastSynchro), en terme de complexité spatiale et temporelle, et les résultats empiriques (longueur moyenne des mots trouvés, temps utilisé par l'algorithme en moyenne). Nous discuterons aussi des différentes représentations intermédiaires utilisées par ces algorithmes, et comment utiliser les informations qu'elles contiennent. +
Spot est une bibliothèque de manipulation d'ω-automates qui tend à aider la vérification de modèle par ω-automates et le développement d'outils de transformation d'ω-automates. Elle fournit donc de multiples algorithmes avec de multiples implémentations qui fonctionnent sur une grande variété d'ω-automates. Parmi ces algorithmesles tests de vacuité et les recherches de contrexemple sont souvent utilisés pour de diverses raisons. Comme leurs résultats sont liés, ils sont souvent utilisés ensemble. Cependant, il manque à Spot les implémentations de recherche de contrexemple correspondant à certaines implémentations de tests de vacuité qui soient capables de travailler de la même manière sur les mêmes automates. Nous présentons deux implémentations de calcul de contrexemple, qui viennent compléter deux implémentations de tests de vacuité déjà existantes, qui suivent leur sillage et se servent des données dejà accumulées pour construire efficacement des contrexemples. +
Dans le cadre de son partenariat avec l'institut de cancérologie Gustave Roussy, Milena, la bibliothèque de traitement d'image du LRDE, propose une chaîne de traitement dédiée à la reconstruction d'image. Différentes images d'un même objet mais obtenues par différents modes d'acquisitions, sont traitées. Celles-ci sont d'abord simplifiées. On extrait ensuite les objets qu'elles contiennent. La dernière étape consiste à construire une image recoupant les informations des différentes images. Cette chaîne se décrit ainsi en plusieurs étapes : filtrage de l'imagesegmentation, binarisation, recalage d'image multimodales et reconstruction d'image. L'exposé se concentrera essentiellement sur l'etape de segmentation. +
Even if the accuracy of the text localization system developed by the laboratory has strongly increased, one main problem remains the speed. Indeed, the CPU and the memory resources used by the system need to be reduced if we want to be able to use it to extract text from video or embedded it in resource limited devices like smartphones. To achieve this goal, various methods to reduce the memory and CPU consumption can be used. However all of these methods do not give the same results according to the input image and some of them can decrease the accuracy of the final result. The target is to present these methods, their results, and analyze in what kind of situation they can be used. +
Un automate dèterministe peut être minimisè de manière efficace et donne un automate dont le nombre d'états est minimal. L'algorithme de réduction présenté dans ce rapport permet de construire un automate dont le nombre d'états est minimal à partir d'un automate non déterministe dont les poids sont définis sur un semi-anneau qui est un corps. L'algorithme calcule pour cela la base de l'espace vectoriel engendré par la série représenté par l'automate, ce qui permet de construire un automate dont le nombre d'états est égal à la dimension de cette base. L'algorithme se base sur la représentation matricielle des automates et nous amène à résoudre un système d'équations linéaires, ce qui force le semi-anneau de notre série à avoir les propriétés d'un corps. Nous voulons aussi que notre algorithme fonctionne sur des séries dont le semi-anneau est un corps non commutatif ce qui nous empêche d'utiliser les techniques classiques de résolution de systèmes linéaires. Ce rapport montre comment passer outre ces difficultés. Nous verrons enfin comment adapter notre algorithme pour qu'il fonctionne sur Z qui n'est pas un corps mais qui possède des propriétés suffisantes. +
FIXME +
FIXME +
Spot is a library of model checking algorithms which can manage different kinds of '"`UNIQ--math-00000003-QINU`"'-automata. It can also handle testing-automata since Spot 1.0. However, Spot 2.0 introduced a new data structure for automata with generic acceptance conditions that were not available when testing automata where developed. Our goal is to reimplement testing-automata using the more modern data structure. By doing so, we expect to reuse existing algorithms, to reduce the amount code specific to testing automata, and to make testing automata compatible with HOA format. Additionallyour preliminary implementation seems to produce smaller testing-automata than the original one. +
Vaucanson allows you to manipulate finite state machines. So the modeling of these objects plays a central role concerning the genericity of the library. We want to be able to extend the model to support new types and to specialize behaviours in order to improve performances. We will expose what can be considered as a Gordian knot in the actual modeling: for example Vaucanson is unable to choose the implementation of an automaton according to one of its properties. The proposed solution will reinstate a sane modeling and will prevent misconceptions while devising algorithm specifications. Finally, we will describe among other things a collection of specializations of the automaton concept and a set of improvements to the model that were previously too expensive to implement. +
Les réseaux de neurones profonds sont de plus en plus utilisés pour leur capacité à corréler des paramètres concrets afin d'en déduire des caractéristiques abstraites. Le réseau de neurones en goulot en est une forme particulière. Ce travail présente le fonctionnement de ce type de réseau et son utilisation pour le retraitement des Coefficients Cepstraux des Fréquences de Mel dans un système de reconnaissance du locuteur. Il est donc question d'étudier la convergence d'un tel réseau mais aussi la variation des performances du système en entier. +
L'arbre des formes est une transformée d'image utile pour les traitements d'images discrètes de façon auto-duale. Bien qu'il puisse être calculé grâce á plusieurs approches existantes dans la littératureaucune comparaison de ces algorithmes n'a été réalisée jusqu'á présent. Nous réalisons une comparaison de tous ces algorithmes du point de vue de leurs rapidités de calcul et de leurs occupations mémoire. Nous étu- dions aussi la parallélisation de l'algorithme quasi-linéaire et modifions les données qu'il manipule afin d'améliorer ses temps de calculs et son occupation mémoire. +
Program transformation in general purpose languages such as Cxx is tedious because it requires the ast of the transformed program to be manipulated in abstract syntax (that is, in the host language, Cxx here). The code to write is unwieldy and costly to maintain. This object of the seminar is to present the implementation of new concrete syntax program transformation techniques (that isusing directly the language of the transformed program) in a standard Cxx environment. Our approach uses the parser at run-time to apply dynamic transformation rules. A Tiger compiler will be used to support the presentation. +
La transformation de programmes dans des langages généralistes tels que le Cxx est fastidieuse car elle nécessite de manipuler l'ast du programme transform en syntaxe abstraite (c'est-à-dire dans le langage hôte, ici le Cxx). Le code à écrire est lourd et coûteux maintenir. Le but de ce séminaire est de présenter la mise en uvre de nouvelles techniques de transformation de programmes en syntaxe concrète (c'est-à-dire utilisant directement le langage du programme transformé) dans un environnement Cxx standard. Notre approche utilise l'analyseur syntaxique l'exécution pour appliquer des règles de transformation dynamiques. Un compilateur de Tiger servira de support à la présentation. +
Les ω-automates, capables de modéliser des comportements infinis, sont utilisés dans de nombreux domaines dont la vérification de modèle. Les algorithmes utilisés sont en général très coûteux. Pour cette raison, on veut réduire la taille des automates, tout en préservant le langage reconnu en appliquant de nombreuses réductions. L'une d'entre ellesbasée sur les simulations, est très lente. Dans ce rapport, nous allons montrer comment l'accélérer en utilisant des méthodes algorithmiques et de la parallélisation. +