Abstract
From LRDE
A
Transducers are used in many contexts, such as speech recognition or in order to measure the similarity between proteins. This research shows the implementation in Vcsn of several algorithms allowing to manipulate the transducersand thus solve these problems. First an algorithm to transform a transducer into a weighted automaton that can be easily evaluated is presented. The synchronization algorithm was then implemented, leading to the computation of the edit-distance transducer and its evaluation. +
Nash equilibria computation in finite games is a problem which is known to be PPAD-complete, which means it currently seems impossible to find an efficient solution ; worst case complexity of well known algorithms is in '"`UNIQ--math-00000007-QINU`"' for any game of size '"`UNIQ--math-00000008-QINU`"'. For this reasonresearch in this domain currently focuses on '"`UNIQ--math-00000009-QINU`"'-equilibria, situations which approximately satisfy the conditions of a Nash equilibrium. The emphFictitious Play algorithm fits in this approach. At each iteration of this algorithm, each of the players “strengthens” the strategy that has the highest utility in the current context. For some specific game classes this algorithm converges to a Nash equilibrium, therefore providing an efficient approximation method. However, convergence can only be proved for a small amount of game classes. It is therefore useful to study other algorithms (based on Fictitious Play) in order to find other convergence cases. In this study, we will focus on the alternate Fictitious Play algorithm, in which only one player at a time strengthens one of his strategies : the player which is the “further” from his maximum payoff. +
Alternating automata add a universal branching to the existential branching from non-deterministic automata. Büchi alternating automata are exponentially more concise than non-deterministic Büchi automata. Additionally, they are well suited to translate linear temporal logic as their size is proportional to the translated formula. This work aims to add alternating automata support to Spot. This will make Spot compatible with other tools producing or using aternating automata, and allow future algorithms working on alternating automata to be implemented. +
Une des parties d'une chaîne de reconnaissance de caractères est la classification des caractères à proprement parler : ils peuvent être en majusculesminuscules ou bien être des chiffres. Dans notre casnotre OCR calcule un descripteur à base d'ondelettes pour chacune des images de caractère. Ce sont ces descripteurs que nous classifions. L'étape de classification est actuellement basée sur un algorithme des k plus proches voisins (k-NN) multi-classe. Sachant que l'étape d'évaluation dépend fortement de la taille de la base d'entraînement, cette dernière peut être modifiée afin d'améliorer les scores. Notre travail se concentre sur ces possibles améliorations de la base d'entraînement. vspace*1.05cm +
Vaucanson est une bibliothèque dont un des buts est de permettre un accès facilité à des automates et aux algorithmes qui leur sont associés. Elle met donc à notre disposition plusieurs algorithmes standard (et d'autres moins conventionnels) tels que la déterminisation, le calcul des états accessibles etc. L'un de ces algorithmes est la composition de transducteurs. Celui-ci n'est pas d'une nature aisée à aborder et son implémentation dans Vaucanson est perfectible. Améliorer l'implémentation d'un tel algorithme est alors un bon moyen de mettre à l'épreuve certains choix de conception dans Vaucanson. +
Spot est une bibliothèque de model checking developée au LRDE. Sa force est d'utiliser les Automates de Büchi Generalisés basés sur les transitions (TGBA), plutôt que les Automates de Büchi basés sur les Transitions (TBA) très utilisés dans les autres model checkers. Les TGBA nous permettent de produire des automates très petits représentant une formule rendant toutes les étapes suivantes du model checking plus rapide. Comme Spot met l'accent sur l'utilisabilité et la personnalisation des outils, une attention particulière est portée sur l'interfaçage avec d'autres programmes. La question de transformer un TGBA en TBA (appelé dégeneralization) sans perdre en performance est donc centrale. Cette présentation a pour but de montrer une analyse des outils de dégénéralisation présents dans Spot et de proposer des moyens pour les améliorer. +
En vérification formelle à l'aide d'ω-automates, la construction d'automates plus petits réduit beaucoup le temps d'exécution et la consommation mémoire d'opérations coûteuses telles que le produit synchronisé. La minimisation d'ω-automates étant un problème NP-complet, nous concentrons notre travail sur les opérations de réduction. Spot possède déjà une méthode de réduction par simulation fonctionnant pour tous les automates existentiels ayant n'importe quelle condition d'acceptation. Cette méthode utilise une simulation à un pas reposant sur la signature des états. L. Clemente et R. Mayr proposent une méthode de réduction par simulation à n pas ne fonctionnant que pour les automates de Büchi et montrent que l'augmentation de ce nombre de pas peut améliorer la réduction. Nous essayons une généralisation de l'opération de réduction existante dans Spot pour qu'elle fonctionne avec des simulations à n pas reposant sur la signature des états. Nous présentons également comment étendre la réduction existante afin qu'elle fonctionne également pour les automates alternants. +
Calculer le flux optique a de nombreuses applications telles que l'estimation de mouvement ou un premier pas vers l'inpainting vidéo. L'équation du flux optique ne peut pas être résolue telle quelle à cause du problème de fenêtrage (deux inconnues pour une seule équation). Un ensemble d'algorithme essaie de résoudre cette équation en se basant sur une stratégie globalec'est-à-dire en essayant d'avoir des petites variations dans le flux. Le premier d'entre eux est l'algorithme d'Horn-Schunck. Celui-ci, même s'il marche dans de nombreux cas, a plusieurs inconvénients, y compris celui d'être lent et de ne pas pouvoir trouver les grands déplacements. Dans le but de résoudre ces problèmesplusieurs stratégies ont été développées. Nous présenterons la méthode et analyserons les bénéfices apportés en appliquant une stratégie multi-échelle à l'algorithme d'Horn-Schunck. +
Vaucanson 2 est une jeune plate-forme de manipulation d'automates née des cendres de Vaucanson. Ce redémarrage à zéro a été fortement encouragé par quelques problèmes de conception : difficultés à gérer trop de templates et trop de niveaux d'imbrication de ceux-ci, qui tendent à obfusquer le code quand les concepts templates ne sont pas clairement définis ; des limitations de performances due à une approche de "généralisation" ; etc. Vaucanson 2 entend apprendre des erreurs de son prédecesseur, et dans ce but, un vrai travail de conception doit être fait. Les templates doivent être utilisés pour la performance (évitant un usage abusif de fonctions virtuelles) afin de pouvoir préférer la généricité plutôt que la généralité, tout en conservant une flexibilité lors de l'exécution. Vaucanson 2 prétendra aussi à une compilation dynamique de code (types d'automates et algorithmes) et de le charger en tant que bibliothèque dynamique. Ces simples problèmes amènent à des architectures de distribution complexes et d'effacement de type, qui doivent être testés dans un environnement simulé. +
L'algorithme de Safra permet de construire des automates de Rabin déterministes à partir d'automates de Büchi non-déterministes. Il existe une variante à cette méthode qui permet de construire des automates à parités déterministes. Cependant, ces méthodes produisent des automates avec 2^O(nlogn) états. Il existe des améliorations qui permettent de réduire le nombre d'états dans beaucoup de cas. Nous présentons deux nouvelles stratégies pour aider à réduire le nombre d'états final. La première stratégie utilise les composantes fortement connexes et utilise cette information pour suivre des chemins de Safra différents. La deuxième stratégie utilise l'information retournée par la bisimulation pour retirer des états équivalents. Ceci permet d'éviter de parcourir plusieurs chemins équivalents et ainsi de réduire le nombre d'états final. On montre que nos stratégies permettent souvent de construire des automates déterministes avec moins d'états et que ces automates reconnaissent toujours le même language. On donne des benchmarks pour voir le gain apporté par nos stratégies et on utilise un outil appelé ltl2dstar qui produit des automates de Rabin déterministes à partir de formules LTL pour comparer nos résultats. +
We propose a new edge-based method dedicated to image segmentation. The last few years have shown the development of image processing with connected filters. Indeedcontour-preserving properties of connected operators are highly desired for image segmentation. The connected operators-based segmentation methods usually proceed in two steps. They first compute an attribute on the connected components and filter the components of which attribute do not satisfy a criterion. In these methods, attributes are actually computed on the pixels of connected components. We propose a new union-find based algorithm that enables evaluation of attributes on connected component edges so that we can finally compute an attribute on their contours. We therefore introduce edges-based attributes and propose some of them that evaluate a connected components energy. We finally perform an edge-based attribute filtering to produce a new image segmentation method. +
Probabilistic model checkers usually rely on deterministic automata as the uniqueness of each path simplifies the probabilistic calculation. Unfortunatelythere are not many LTL translators that produce deterministic automata. Moreover, the automata produced by Spot, a model checker library, are not always deterministic. A classical powerset construction cannot always determinize '"`UNIQ--math-00000003-QINU`"'-automata. However, by memorizing the accepting paths, Safra's construction is able to convert a nondeterministic Büchi automaton into a deterministic Rabin automaton. This change of acceptance condition is necessary as deterministic Büchi automata are less expressive than the nondeterministic version. By implementing this construction, Spot will be able to determinize any automata and compute its complement. In this report, we will see how to efficiently implement the Safra construction and how to expand it to also determinize transition-based generalized Büchi automata. +
SCOOL is a domain-specific language (DSL) designed to make high-level C++ development easier. Based on SCOOP, a paradigm mixing generic and object-oriented programming, it features static resolution of member function calls and powerful concept checking. Previously, a standard container library had been made in pure C++ using SCOOP. Howeverthis implementation required high control of the C++ techniques of SCOOP. With SCOOL, we can achieve this by leaving the hard work to the C++ translator. Focusing on the development of the library with SCOOL and the essential changes to the language and its compiler, we will compare the native and DSL solutions and assess that SCOOL is well-fitted for generic application prototyping. +
Cxx has achieved to support classic object-oriented and generic programming, but some modelisation problems remain recurrent and difficult to solve. Scoop is a static Object-Oriented paradigm. The paradigm provides virtual methods, argument covariance, virtual types and multi-methods statically typed without extending the language. Scoop uses its own Cxx library in order to make easier to design a library with this paradigm. +
FIXME +
FIXME +
L'extraction des différentes structures d'un document numérisé se base sur la mise en place d'une chaîne de traitements constituée d'un certain nombre d'étapes primordiales afin d'optimiser la qualité du rendu final. L'étude de la mise en page du document, à savoir la localisation des lignes de texte et des paragraphesconstitue le coeur même de la chaîne puisque le rendu obtenu est étroitement corrélé avec les zones de texte données en entrée à l'OCR. Ainsi, nous présenterons une méthode hybride d'analyse de mise en page développée dans le cadre du projet SCRIBO. +
Vaucanson est une bibliothèque C++ de manipulation d'automates finis. Par rapport à son concurrent principal, OpenFST, Vaucanson souffre d'importants problèmes de performances. Afin d'améliorer les performances de Vaucanson, il est nécessaire d'avoir des outils appropriés pour analyser le comportement de la bibliothèque en termes d'utilisation de temps CPU et de gestion de la mémoire. Jusqu'en Mars 2009, il n'existait pas d'outils de ce type pratiques à utiliser avec Vaucanson. CBS (C++ Benchmarking Suite) est une suite d'outils d'analyse de performances pour projets C++. Ces outils permettent de mesurer, d'afficher, et de comparer l'utilisation de ressources (temps, mémoire), dans un format accessible à l'utilisateur. Ils sont utilisés pour analyser Vaucanson afin de réécrire les algorithmes les moins efficaces. +