LRDE Seminar: 24 May 2006, EPITA, Amphi P004

MARKOV

14h00 : Classement de pages Web -- Johan Oudinet^?

Les moteurs de recherche ordonnent les pages de leur index pour répondre rapidement et efficacement aux requêtes des internautes.

Le critère pour établir cet ordre doit être indépendant de la requête et il doit refléter la "popularité" de chaque page. Cette notion abstraite de "popularité" est appliquée par des algorithmes qui se basent sur la structure de l'index. Le "PageRank" est le plus connu et le plus utilisé.

Après avoir présenté le fonctionnement du "PageRank", nous décrirons des algorithmes plus rapides et peut-être même plus pertinents que le "PageRank".

OLENA

14h30 : Taxonomie des images dans Olena -- Christophe Berger^?

Olena est une bibliothèque générique de traitement d'images. Il est important qu'elle puisse offrir à ses utilisateurs tous les outils nécessaires à leurs besoins. Ceci se traduit par une réflexion sur la modélisation de la bibliothèque au regard des types d'images qu'elle doit supporter.

Nous allons présenter les types d'images élémentaires que nous souhaitons intégrer à Olena ainsi que les types, appelés "morpheurs", qui nous permettent d'étendre la gamme des types d'images. Nous caractériserons les propriétés des différents types d'images et nous proposerons une modélisation à l'aide du paradigme SCOOP 2. Finalement nous présenterons l'intégration de ce travail dans Olena.

15h00 : Segmentation temps réel -- Nicolas Widynski^?

En traitement d'images, la segmentation a pour but de partitionner l'image en plusieurs régions, selon des critères de sélection.

Le but est généralement d'extraire des objets caractéristiques de l'image en vue d'effectuer un traitement particulier sur ces régions, ou tout simplement de simplifier l'image. Bien souvent, les méthodes d'extraction nécessitent un à priori sur certaines caractéristiques des objets, et ne sont donc pas génériques.

Le domaine d'application est vaste : médical (extraction de tumeur, segmentation du cerveau,...), reconnaissance humaine (main, iris,...), suivi d'objets (bien souvent de personnes). Dans la littérature, il existe beaucoup de méthodes dévouées à la segmentation d'images. Quelques-unes fonctionnent en un temps réel, dédiées le plus souvent au suivi d'objets dans les séquences d'images.

Nous proposons de comparer plusieurs méthodes de segmentation temps réel. Nous étudierons tout d'abord des algorithmes classiques (watershed, watersnake, snake) que nous opposerons à une seconde approche, tout à fait différente, basée sur les opérateurs connectés.

VAUCANSON

15h45 : Automates et performance -- Guillaume Lazzara

Passer d’une théorie mathématique à une implémentation sur machine n’est pas toujours évident. Bien souvent d’ailleurs, l’implémentation la plus intuitive n’est pas la plus performante.

Les automates n’échappent pas à cette règle. Étant capable de pousser les machines au-delà de leurs limites, optimiser leur implémentation et les algorithmes associés est une réelle nécessité.

C’est donc dans cet esprit que nous vous présenterons les problèmes de performances liés aux automates booléens, ainsi qu’une étude des méthodes les plus pertinentes qui pourraient être utilisées à l’avenir dans Vaucanson.

16h15 : Synchronisation des transducteurs -- Guillaume Leroi

Un transducteur est un automate qui pour une entrée reconnue donne une certaine sortie. On peut voir ces objets comme des automates dont les transitions au lieu d'ëtre étiquetées par une lettre sont étiquetées par un couple de lettres, voir un couple de mots. Ces transducteurs peuvent représenter des relations par exemple.

Le but de la synchronisation est de ramener des transducteurs étiquetés par des mots à des transducteurs étiquetés par des lettres dans le but de pouvoir calculer des intersections de relations, ou bien déterminiser le transducteur en considérant les couples de lettres comme des lettres d'un autre alphabet.

Nous présenterons deux algorithmes; l'un permettant de déterminer si un transducteur est synchronisable, et l'autre de synchroniser un transducteur.

16h45 : Fermeture d’un automate -- Matthieu Varin^?

Les transitions spontanées sont très utiles dans le cadre de la manipulation d'automates. Cependant, il arrive bien souvent que l'on ait besoin de les supprimer. On peut citer les cas de la déterminisation d'automates, l'évaluation dans Z, ... La suppression des transitions spontanées s'appelle la fermeture de l'automate. Il existe deux types de fermeture : avant et arrière. Une implémentation de la fermeture existe déjà dans Vaucanson. Cette implémentation est basée sur la méthode décrite par Jacques SAKAROVITCH dans son livre 'Éléments de théorie des automates' (pages 87 - 88). C'est une variante optimisée qui est proposée pour ce séminaire. Celle-ci pose des problèmes dans le cas d'automates sur Z que nous allons aborder.
to top