Abstract
From LRDE
T
Tarjan Union-Find algorithm (TUFA) aims to build, given an image, a tree representation modeling the equivalence classes following a given relation. It can be derived to define filters on those tree representations. TUFA is currently used in Milena, our image processing library, to implement connected filters. For example, closing and opening related to area, volume, or height which are useful to clean an image while preserving contours. This important property provides a nice advantage in comparison to the classical opening and closing based on erosion and dilation. Another advantage of TUFA is that it can be used for algorithms which feature the domain disjointness property. This document presents how new connected filtersin particular self-dual, have been introduced into Milena. +
Milena est la bibliothèque de traitement d'image générique de la plate-forme Olena. Cette bibliothèque a pour but d'être performante tout en restant simple. L'introduction dans Milena de nouveaux types d'images basés sur des graphes a mis en évidence des problèmes de modélisation qui sont un frein pour sa généricité. Par exemple, nous avons toujours considéré que "les images ont des points". Néanmoinscertains types d'images possèdent des sites qui ne sont pas des points (mais des arrêtes, faces, ou même des ensembles de points). Une autre supposition erronée était de considérer que les sites étaient toujours localisés par un vecteur (càd, (x,y) dans le plan 2D). Cette supposition est fausse lorsque l'on manipule des sites qui ne sont pas "Pointwise". Il etait donc nécessaire de modifier les types d'images utilisés dans Milena et les propriétés qui leur sont associées. Pendant ce séminaire, nous présenterons une nouvelle classification d'images permettant de résoudre ces problèmes. +
Spot est une bibliothèque qui manipule des ω-automates dont les conditions d'acceptation sont exprimées avec au plus 32 ensembles d'acceptation. Puisque la condition d'acceptation du produit de deux automates doit utiliser la somme de leurs ensembles, on ne peut pas construire des produits dont les opérandes utilisent plus de 32 ensembles au total. Une opération typique sur les automates est de calculer L(Atimes B)neemptyset pour décider si L(A) intersecte L(B). Lorsqu'elle est implémentée par empty(product(A, B))le calcul du produit limite le nombre d'ensembles d'acceptation que A et B peuvent utiliser. On propose une nouvelle fonction empty(A, B) qui réalise le test de vacuité de Atimes B sans construire un automate et donc sans limite sur les conditions d'acceptation. L'outil ltlcross peut maintenant comparer des automates pour un total supérieur á 32 ensembles d'acceptation. +
Il existe une hiérarchie de propriétés temporellesdéfinie par Manna et Pnueli (1990). Cette hiérarchie contient entre autres les classes de récurrence et persistence. Savoir si une formule de logique temporelle à temps linéaire (LTL) f est récurrente (respectivement persistente) est intéressant car cela guarantit que f peut être traduit en un automate de Büchi déterministe (respectivement en un automate de co-Büchi). Auparavant, Spot, une bibliothèque de manipulation de formules LTL avait une unique façon de tester l'appartenance d'une formule aux classes de persistence ou récurrence. Grâce à nos précédents travaux présentés dans emphA co-Büching Toolbox +
Here is a method to differentiate text from non-text inside a picture using descriptors inspired by data compression algorithms. The major goal of this approch is to compute a signal that will allow a learning system (like knn or svn) to classify text and background of an image. To compute this signal a wavelet based method, similar to the one used in png or jpeg compression format, will be used. Another point that will be discussed is what kind of wavelet gives the best results and with what kind of learning system.These descriptors will then be compared whith other descriptors that are not wavelet based. Finaly the various way to reduce the time spent to compute the descriptors will be presented like the wavelet lifting. +
The Tree of Shapes is an useful image transform used to process digital images in a self-dual way. It can be computed using several approaches available on the literature though no comparison of those algorithms exists yet. We provide a comparison of the existing algorithms from the computation time and space occupation point of view. We also study further the quasi-linear algorithm based on the union-find providing a parallel version and use a slight modification of the intermediate representation of images it manipulates to improve both its practical computation times and space requirements. +
In speaker recognition, deep neural networks (DNN) have recently proved to be more efficient than traditional gaussian mixture models (GMM) for collecting Baum-Welch statistics that can be used for i-vector extraction. However, this type of architecture can be too slow at evaluation time, requiring a GPU to achieve real-time performance. We show how triphone posteriors produced by a time delay neural network (TDNN) can be used to create a more lightweight supervised GMM serving as a universal background model (UBM) inside the i-vector framework. The equal error rate (EER) obtained with this approach is compared to those obtained with traditional GMM-based UBM. +
Dividing a picture into area of interest is called picture segmentation, it is useful in particular to point out cancerous cells in medical imaging. The emphWatershed Transform provides such a segementation and can be implemented in many ways. Here we will focus on the emph Topological Watershed, a performant algorithm producing results with nice properties. In this report, we will show how this algorithm had been implemented in Milena, the C++ generic image processing library of Olena, developed at the LRDE. We will first see how to treat usual image format and then generalize it to trickier formats like pictures mapped on general graphs. +
Vaucanson is a finite state machine manipulation platform for automata and transducers. Usage highlighted the overly complex interface for the automaton manipulation. Therefore, a new approach to its definition was considered involving the concept of automaton kinds. The former Vaucanson development team initiated this series of fundamental changes which concluded in the implementation of the labels-are-letters kind. Still, these changes put the library in a transitional state. newline In the continuation of their work and in order to restore both the robustness and genericity of Vaucanson, we will introduce two new kinds into the library: labels-are-words and labels-are-series. This work may lead to a series of changes involving both algorithm rewriting and data structure modifications which will allow simpler yet more powerful automata manipulation. +
Vaucanson is a finite-state machine manipulation platform for automata and transducers. Usage and development highlight complexity and ineffectual. Active work on specifications and design have been undertaken to introduce, in the core of Vaucanson, easier mechanism to the library manipulation and development. The version 2.0 is, today in development. This report presents the 2.0 version of Vaucanson and his usability with the portage of two algorithms: Evaluation of word in automata and determinization of automata. Next, we show the new design profit compared to Vaucanson 1.4 related to the speedup. +
Spot repose sur l'approche automate du emphmodel checking. La bibliothèque permet de vérifier des propriétés exprimées en logique temporelle à temps linéaire (LTL) sur une modélisation d'un système représentée par un automate de Büchi généralisé basé sur les transitions (TGBA). Spot propose actuellement deux algorithmes de traduction de LTL en TGBAune des deux étapes principales de l'approche automate. Nous présentons une nouvelle traduction en TGBA d'une logique LTL qui a été étendue en y ajoutant des opérateurs représentés par des automates finis. Cette traduction permet à Spot de vérifier des propriétés qui n'étaient pas exprimables auparavant. +
Spot est une bibliothèque de model checking qui permet de vérifier des propriétés exprimées en logique temporelle à temps linéaire (LTL) sur des modèles représentés par des automates de Büchi généralisés basés sur les transitions (TGBA). Spot propose actuellement deux algorithmes de traduction de LTL en TGBA, une des étapes principales de l'approche automate. Nous présentons une nouvelle traduction en TGBA d'une LTL étendue dont les opérateurs sont représentés par des automates finis, permettant ainsi à Spot de vérifier des propriétés qui n'étaient pas exprimables auparavant. Nous présenterons aussi de quelles fac cons nous pourrions intégrer certaines fonctionnalités de PSL (Property Specification Language) à notre extension. +
En vérification formelle de la logique temporelle linéaire (LTL) à l'aide d'ω-automates, la négation d'une formule LTL est traduite en ω-automate. La construction d'un automate plus petit réduit beaucoup le temps d'exécution et la consommation mémoire des opérations suivantes de la chaîne de traitement de la vérification formelle. Müller et Sickert ont présenté une méthode efficace pour traduire n'importe quelle formule LTL en un petit automate déterministe. Cette méthode consiste à découper la formule en trois ensembles de sous-formules qui appartiennent respectivement au fragment de sureté ou de garantie, au fragment d'équité et au reste. Ils traduisent ensuite individuellement ces ensembles de sous-formules en automates déterministes qu'ils combinent par la suite. Spot peut déjà traduire les formules d'obligation en automates déterministes minimaux. Les formules d'obligation étant un surensemble des formules de sureté et de garantie, on généralise la traduction de Müller et Sickert en remplaçant le fragment de sureté ou de garantie par le fragment d'obligation. En ce qui concerne le fragment d'équité, ils ont présenté un algorithme de traduction efficace qui produit de petits automates déterministes. Ils ont également présenté comment construire efficacement un produit de ces automates avec d'autres automates. Nous présentons comment nous implémentons ces deux méthodes dans Spot. +
Vaucanson permet de manipuler des automates finis. La modélisation de ces objets occupe donc une place centrale dans la généricité de la bibliothèque. Nous voulons pouvoir étendre cette modélisation pour supporter de nouveaux types et spécialiser des comportements afin d'améliorer les performances. Nous exposerons ce qui peut être considéré comme un véritable nud gordien dans la modélisation actuelle: Vaucanson est par exemple incapable de choisir une implémentation pour un automate en fonction d'une de ses propriétés. La solution apportée restaure alors une modélisation saine et empêchera des erreurs de conception lors de la recherche de spécifications des algorithmes. Finalementnous exposerons, entre autre, une série de spécialisations du concept d'automate, ainsi qu'un ensemble d'améliorations du modèle qui étaient autrefois trop coûteuses à mettre en place. +
L'application de filtres morphologiques sur une image en niveaux de gris permet d'en faire disparaître certaines parties et d'en mettre en valeur d'autres. De ce fait, en choisissant un élément structurant adapté, il est possible d'éliminer certains éléments d'une carte comme le texte et de reformer les lignes discontinues. Un banc de filtres a été défini permettant de récupérer les lignes fines de l'image, frontières des parcelles, et ce, quelle que soit leur orientation. Sur l'image résultante, un algorithme de partage des eaux peut mettre en évidence les parcelles recherchées. Par ailleurs, l'application d'un algorithme de seam carving permet de retirer, en pré-traitement, d'éventuelles lignes de quadrillage. +
Transducers are used in many fields, such as linguistics to model phonological rules, regular expressionsspecification languages, speech recognition... When working with transducers, one of the most indispensable tools is composition. As such, it is essential to implement it in Vaucanson 2 in an efficient way. This report will introduce the ground work to bring about transducers composition, and then its implementation and optimization. The composition is viewed here as a special case of the product of automata with spontaneous transitions, so three algorithms for this product are exposed here, as well as some essential implementation concepts. +
Vaucanson is a library dedicated to finite automaton manipulation devlopped by the Research and Development Laboratory of EPITA (LRDE). This project aims at providing its users with a great variety of automaton typesincluding transducers. This report suggests an implementation of generic transucers, which accept automaton labeled by tuples of languages. +
Vaucanson est une bibliothèque dédiée à la manipulation d'automates finis développée par le Laboratoire de Recherche et Developpement de l'EPITA (LRDE). Ce projet tient à offrir à ses utilisateurs une large variété de types d'automates, notamment les transducteurs. Ce rapport propose une implémentation de transducteurs génériques, qui peuvent accepter des automates étiquetés par des n-uplets de langages. +