CSI Seminar 2014-07-10
From LRDE
VAUCANSON
10h30 Recherche de mots synchronisants dans un DFA – ANTOINE PIETRI
Le problème de recherche de mots synchronisants les plus courts possibles est un problème important qui a beaucoup d’applications (orienteurs mécaniques, problème de coloration de route, vérification de modèles, bioinformatique, 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 possibles en temps polynomial. Dans cet exposé, nous comparerons les différentes approches utilisées par les algorithmes principaux les plus connus (Glouton et Cycle, SynchroP et SynchroPL), en termes de complexité spatiale et temporelle, et les résultats effectifs (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.
11h00 Composition de transducteurs dans Vaucanson 2 – VALENTIN TOLMER
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, 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.
OLENA
11h30 Détection de logotypes et autres invariants caractéristiques à l’aide de descripteurs SIFT – ANTHONY SEURE
La détection d’éléments discriminants dans une image est un sujet très actif de vision par ordinateur. Aujourd’hui, les applications sont très diverses, allant de la robotique à la photographie numérique assistée. Notre exposé se concentrera sur la détection de logotypes dans des images naturelles. Pour ce faire, nous nous basons sur Olena, une plateforme libre, générique et performante de traitement d’images afin d’implémenter un détecteur de points clés : les descripteurs SIFT.
12h15 Inpainting d’images couleur – NICOLAS ALLAIN
L’inpainting est une technique de traitement d’images. Son but est de reconstruire une zone d’une image sans connaître l’aspect originel de ladite image. Il existe deux grandes familles de méthodes d’inpainting : l’une est basée sur la prolongation des zones à fort contraste, l’autre sur la synthèse de textures. Ce procédé est utile dans le cas de sous-titres incrustés dans une vidéo ou de texte dans une image. Un inpainting est également utilisé sur des images dégradées, abîmées, ou présentant un objet non désiré. Notre but est de reconstruire le fond caché par du texte précédemment segmenté. Nous étudions la méthode de Khodadadi basée sur l’ordre dans lequel les pixels dégradés de l’image sont reconstruits via une synthèse de texture. Nous utilisons le critère de l’erreur quadratique moyenne pour évaluer nos résultats. Nous analysons les résultats obtenus, les améliorations effectuées, et les progrès obtenus.
12h45 Utilisation du clustering pour la reconnaissance
de caractères – ANTOINE LECUBIN
Nous présenterons une méthode d’amélioration de la classification dans l’application de reconnaissance de caractères du laboratoire basée sur le groupement des caractères en classes. Nous verrons d’abord comment déterminer et imbriquer les groupes de caractères les plus intéressants à classer ensemble grâce à un algorithme de clustering appliqué aux données fournies par le descripteur à base d’ondelettes. Puis nous nous pencherons sur l’adaptation de la phase de classification pour qu’elle s’effectue en plusieurs temps et prenne en compte ces groupements. Enfin nous nous intéresserons à l’évolution du taux de reconnaissance obtenue grâce à cette méthode.
SPEAKER ID
14h30 Regroupement de locuteur à base de Self- Organizing Map – JEAN-LUC BOUNTHONG
Les i-vectors représentent actuellement l’état de l’art dans le domaine de la vérification du locuteur. Des résultats intéressants sont obtenus à partir de classifieurs tel que la distance cosinus (CD). Cependant, un tel classifieur nécessite un apprentissage supervisé et devient donc inutilisable avec une base de données sans étiquette. Dans cette étude, nous explorerons une méthode à base de Self-Organizing Map (SOM) pour étiqueter une base de données quelconque. L’objectif étant de fournir une méthode pour entraîner les classifieurs supervisés sur une base de données non étiquetée. Nous allons aussi comparer l’efficacité de notre méthode avec d’autres méthodes telles que Infomap, Markov Clustering et Girvan- Newman.
15h00 Le partitionnement de Newman-Girvan pour
les systèmes de reconnaissance du locuteur – JIMMY YEH
La distance cosinus est la méthode de décision la plus utilisée, elle nécessite une base d’apprentissage étiquetée afin d’appliquer des algorithmes supervisés. Pour augmenter la taille de la base de développement et dans le but de réduire les coûts de constitution de ces bases, l’utilisation de données non étiquetées pour l’entraînement du système devient nécessaire. Le but de ce travail est de tester le partitionnement de Newman-Girvan afin d’étiqueter les i-vectors inconnus.
15h30 L’algorithme de partitionnement de Markov
pour les systèmes de reconnaissance du locuteur – FANNY RIOLS
Grâce à des méthodes d’apprentissage supervisé (la Distance Cosinus avec l’Analyse Discriminante Linéaire et la méthodeWithin Class Covariance), des progrès significatifs ont été réalisés dans ce domaine. Cependant, de récentes recherches proposent d’utiliser une base de données non étiquetées d’i-vectors, afin d’augmenter la taille de l’ensemble des données d’entraînement et de réduire le coût de constitution de cette base. C’est pourquoi nous basons notre étude sur l’espace des i-vectors, et travaillons ainsi avec des méthodes d’apprentissage non supervisé. Dans cette étude, nous utilisons une méthode de partitionnement, le processus de Markov Clustering (MCL), afin de regrouper de façon naturelle les ivectors qui représentent un même locuteur dans un ensemble d’entités. L’algorithme MCL est un algorithme de partitionnement non supervisé rapide et extensible, basé sur la simulation de flux stochastiques dans les graphes. Le résultat du partitionnement est utilisé dans le système supervisé standard de vérification du locuteur pour évaluer les performances. Nous allons aussi comparer celles-ci avec d’autres méthodes de regroupement, comme l’Infomap, le Self-Organizing Map et Girvan Newmann.
16h15 Détection de communautés avec l’algorithme
de l’Infomap – MICKAEL SAADA
Les récentes recherches sur les i-vectors proposent d’utiliser des données non étiquetées pour augmenter la taille des données d’entraînement et par la même occasion réduire les coûts de la collecte de ces données. C’est pourquoi nous basons notre étude dans l’espace des i-vectors et travaillons sur des méthodes non supervisées. Dans cette étude, nous explorerons la méthode de l’Infomap qui permet de trouver les structures communautaires dans des réseaux afin d’étiqueter des données non étiquetées. Le but de cette méthode est de maximiser la modularité d’un graphe en associant les paires de sommets qui maximisent la modularité. Cet algorithme est divisé en 3 parties : un algorithme "glouton", le recuit simulé et l’algorithme du heat-bath. Nous allons aussi comparer l’efficacité de notre méthode avec d’autres méthodes telles que Markov Clustering, Grivan-Newman et Self-Organizing Map.
SPOT
16h45 Un Feedback Arc Set pour Spot – ALEXANDRE LEWKOWICZ
Spot est une bibliothèque extensible pour le model checking qui utilise les automates de Büchi généralisés à transitions acceptantes. Il contient de nombreux algorithmes de pointes. Dans cet exposé, nous nous concentrons sur deux de ses algorithmes qui construisent des automates avec plus de transitions que nécessaire. En pratique ces constructions utiliseraient moins de transitions si elles pouvaient calculer un feedback arc set (FAS), c’est-à-dire un ensemble de transitions à retirer du graphe pour le rendre acyclique. Dans l’absolu, on veut un FAS minimal, mais ce problème est NP-difficile. Nous adaptons et améliorons une heuristique proposée par Eades et al. qui permet une construction en temps linéaire. Nous montrons comment cet algorithme bénéficie à la complémentation d’automates de Büchi déterministes et la traduction d’automates de Rabin en automates de Büchi. En fonction de l’automate traité on remarque une amélioration montant jusqu’à 31%. Ces résultats varient beaucoup selon le nombre de cycles et d’états acceptant.