Le premier prototype que nous avons réalisé, déjà évoqué en 2.2.6, a été développé en C++ en se basant sur la bibliothèque LEDA1. Cette bibliothèque d'outils de mathématiques discrètes fournit entre autre des librairies puissantes de création et de manipulation de graphes étiquetés génériques. Nous l'avons donc choisie après avoir été tenté par GRAS2, qui lui fournit les primitives nécessaires à la gestion de bases de données de graphes, mais s'est révélé trop lourd pour permettre nos expérimentations.
Le premier prototype permet essentiellement de comparer un certain
nombre d'algorithmes de calcul d'isomorphismes de sous-graphes
partiels, c'est à dire des instanciations de graphes potentiels. Il
permet donc de générer un graphe général Strates-IA (sous la
forme d'un unique graphe LEDA) en ayant indépendamment accès à
la base de connaissances, mais aussi à des sous-graphes d'annotation
liés à un flux. Il permet également de générer des graphes
potentiels comme graphes LEDA. Les éléments de graphe
considérés à ce stade se limitent à des doublets
{Type, Nom}, avec Type pouvant prendre les valeurs UAV, EA et EAA. Les
connaissances temporelles liées aux UAV sont gérées dans des tableaux
hors du graphe LEDA, et une extension de la fonction de recherche de
voisins d'un n
ud suivant une relation a été étendu aux relations
temporelles.
L'interface du prototype étant uniquement en mode texte, et permettant en conséquence de ne construire les graphes que de façon fastidieuse et non explicitement liée aux flux audiovisuels, des mécanismes de génération automatique du graphe global, et d'extraction de graphes potentiels à partir de celui-ci, ont permis de générer des graphes de tailles conséquentes.
Les algorithmes d'instanciation de graphes potentiels suivants ont été implantés et testés :
10), mais qui a l'avantage de fournir une base solide
de comparaison.
Le tableau 3.1 résume les caractéristiques principales des algorithmes étudiés.
|
La figure 3.1 présente une copie d'écran de l'affichage d'un graphe potentiel extrait automatiquement d'un graphe global généré automatiquement avec 1000 EAA, 30 flux, 1000 UAV, une moyenne de 2 EA par UAV et 30 % des EA en relation élémentaire avec d'autres EA.
![\includegraphics[width=350pt]{../fig/proto/proto1.eps}](img90.gif) |
Les lignes suivantes montrent un exemple d'une session de recherche d'instances du graphe potentiel de la figure 3.1 permettant de comparer deux algorithmes.
INSTANCIATION du Graphe potentiel : essai_gp1 Quelle methode utiliser ? 0 - La fuite 1 - Algo Ullmann 2 - Algo Ullmann avec fenetre 3 - Algo Propagation 4 - Algo Propagation Cordella 5 - Algo Multi-propagation >5 * Resultat * Il y a 756 instanciations du graphe potentiel essai_gp1 dans le graphe general de la base courante essai L'operation a pris 53 ms. INSTANCIATION du Graphe potentiel : essai_gp1 Quelle methode utiliser ? 0 - La fuite 1 - Algo Ullmann 2 - Algo Ullmann avec fenetre 3 - Algo Propagation 4 - Algo Propagation Cordella 5 - Algo Multi-propagation >1 Taille G :5902 / Taille Gp :10 * Resultat * Il y a 756 instanciations du graphe potentiel essai_gp1 dans le graphe general de la base courante essai L'operation a pris 94555 ms. INSTANCIATION du Graphe potentiel : essai_gp1
Notre premier prototype a donc permis d'atteindre les objectifs que nous nous étions fixés en termes de validation des principes généraux des Strates-IA et d'instanciation de graphes potentiels dans un graphe Strates-IA.
Sur la base de l'expérience acquise au cours du développement du premier prototype, nous avons pu fixer les bases d'un second prototype, qui a été principalement développé au cours du stage de Projet de Fin d'Etude de Elöd Egyed-Zsigmond [86]. Ce prototype SESAME permet de fournir un cadre pour l'expérimentation en vraie grandeur des Strates-IA, c'est à dire l'implantation des principaux concepts présentés, manipulés au sein d'une interface conviviale. Il implante également la sauvegarde des données en XML ainsi que la possibilité de gérer de façon uniforme les graphes Strates-IA comme des graphes LEDA ou bien comme ensemble de fichiers XML [87], voir 5.2.2. Ce prototype a été développé en Visual C++ sous Windows NT, en utilisant LEDA comme librairie fournissant des structures de données aisément utilisables, ainsi que le DirectX MediaFramework de Microsoft et XML4C de IBM Alphaworks. Nous en présentons les principes généraux, ainsi que les principales fonctionnalités.
L'architecture du prototype est fondée sur un graphe Strates-IA, dont
une interface de programmation est disponible et permet un accès à des
fonctions de base. Ce graphe est indépendant de l'application qui
l'exploite, c'est à dire qu'il peut être représenté de manière
quelconque. Ainsi, celui-ci est actuellement représenté comme un
graphe LEDA unique d'objets tels que les UAV, les EA ou les EAAs. La
sauvegarde du graphe se fait en utilisant les primitives de sauvegarde
LEDA associées à des sérialisations des nuds en XML, mais tout a
été prévu afin qu'il soit aisé de porter les structures de données
dans des fichiers XML (voir 5.2.2). L'accès au graphe
Strates-IA est normalisé et passe obligatoirement par l'interface de
programmation.
Le prototype est conçu comme une application stockant ses données dans un graphe Strates-IA. Le principe de l'application est de fournir des vues du graphe qui en autorisent soit la consultation, soit la modification.
Une vue d'un élément du graphe Strates-IA est, de façon générale, la présentation de cet élément (EAA, EA ou UAV) et d'éléments qui sont dans son contexte (déterminé par des graphes potentiels). Tout présentation du graphe Strates-IA passe obligatoirement par une vue d'un de ses éléments et d'éléments contextualisés par rapport à lui.
Par exemple, la présentation de l'annotation d'un flux est une vue d'une UAV annotée par < Flux > . Dans cette vue se retrouvent également les éléments d'annotation et les unités audiovisuelles qui se trouvent dans son contexte d'inclusion temporelle. Une vue d'un élément d'annotation peut être constituée de ses attributs, mais aussi des éléments d'annotation qui sont dans son contexte immédiat (à une distance de 1 dans le graphe).
On essaye ainsi de ne présenter des informations à l'utilisateur que de façon contextuelle. Les vues peuvent cependant être complexes : par exemple, une vue d'une UAV peut consister en un lecteur audiovisuel permettant l'annotation de l'UAV. Une vue de la base de connaissances peut être considérée comme une vue de son EAA racine et de l'arborescence des EAA qui sont dans son contexte suivant la relation de spécialisation, etc.
Le principe des vues du graphe que nous proposons trouve un écho dans le mécanisme propre à Visual C++ des vues de documents.
La figure 3.2 présente quelques vues d'un graphe Strates-IA. Différentes dimensions d'analyse et la base de connaissances se trouvent à gauche. Une vue de l'UAV annotée par < Flux > permet de visualiser les UAV et les EA primitifs qu'elle contient temporellement. Une autre vue, composée entre autre d'un lecteur audivisuel permet d'annoter. Ainsi, sur l'exemple présenté, deux unités audiovisuelles sont en cours de création, la première est définie par l'EAA < EAA:Personnage > et son annotation est complétée à l'aide de < EAA:Entrer >. La seconde est définie par < EAA:Prêtre > et commence à la 23ème seconde du flux.
![\includegraphics[width=\textwidth]{../fig/proto/proto2.2.eps}](img91.gif) |
Nous décrivons ici les fonctionnalités offertes à terme par le prototype SESAME pour l'exploitation des Strates-IA.
L'annotation se fait toujours dans le contexte d'une ou de plusieurs dimensions d'analyse, qui sont en permanence disponibles. La création de nouvelles UAV se fait dans une vue d'UAV telle qu'un lecteur audiovisuel ou une vue en ligne de temps (cf. figure 3.2). Une UAV peut soit être décrite directement par son extension temporelle, soit en en fixant une borne de départ et en suspendant la création effective à la découverte d'une borne d'arrivée.
A la mise en place d'un EA, le système impose de compléter ses attributs marqués comme obligatoires, et propose de compléter les attributs facultatifs. La mise en relation d'EA est une tâche qui peut impliquer la création de nouveaux éléments d'annotation, et l'utilisation d'une valence liée à l'EAA utilisé. L'annotation peut être contrainte par un schéma de description spécifiant les dimensions d'analyse à utiliser et les relations entre celles-ci.
L'exploration du système des Strates-IA passe bien entendu par la présentation contextuelle de ses différents éléments suivants des vues, et le passage d'une vue à l'autre.
La navigation est pilotée par les graphes potentiels qui fournissent des contextes qu'il est possible d'atteindre.
Le système permet de mettre en place la base de connaissances, c'est à dire de spécifier les EAA et leurs relations, ainsi que leurs attributs. Les dimensions d'analyse peuvent être mises en place comme ensemble d'EAA ou/et d'autres dimensions d'analyse. Une interface de mise en place de graphes potentiels permet de construire manuellement les sommets, ou bien de réutiliser (en les abstrayant) des éléments du graphe réel. Les graphes potentiels sont stockés en tant que tels. Ils sont également utilisés pour mettre en place des valences. Une interface similaire à celle permettant de construire des graphes potentiels permet de construire des schémas de description comme graphes de dimensions d'analyse.
Les requêtes au système passent par le choix ou la mise en place
de graphes potentiels caractérisés adaptés à la tâche en
cours. Après instanciation, il est alors possible de visualiser les
résultats, c'est à dire des vues des nuds de sous-graphes
instances mis en évidence par des points de caractérisation.
D'autres requêtes plus générales sont possibles, qui
correspondent à un niveau supplémentaire d'abstraction. Par
exemple il est possible de chercher des unités audiovisuelles telles
qu'elles possèdent dans leur contexte temporel un certain nombre
d'EA (cf. 2.4.2, p. ![[*]](cross_ref_motif.gif)
). Alors
l'utilisateur doit juste spécifier ceux-ci, tandis que le système
se charge de la mise en place des graphes potentiels correspondants et
de la présentation des résultats.
Avec ce prototype, nous avons mis en place les bases nous permettant de tester et d'expérimenter l'annotation et l'utilisation des différents concepts des Strates-IA.
Bien entendu, il reste du travail sur la gestion des différents outils, l'interface graphique, la gestion de l'expérience, etc. Ces principes pourront cependant être implantés de façon aisée à partir du cadre d'étude que nous avons mis en place, tout ajout à l'interface ne relevant que de ce niveau, et non de celui du graphe Strates-IA.
Indépendamment, il sera possible de faire évoluer l'algorithme d'instanciation sans toucher ni à la représentation du graphe ni à l'interface graphique. Le prototype SESAME se révèle donc modulaire dans son organisation, et permettra une évolution dans toutes les directions utiles.
Terminons en disant un mot sur la notion d'assistants dans le système SESAME. Le concept d'assistant a été présenté dans [186], et correspond à un agent informatique aidant l'utilisateur dans ses différentes tâches d'exploitation d'un graphe Strates-IA. Des assistants peuvent se rencontrer à tous le niveaux de tâches de l'utilisateur :
La notion d'assistant a été validée dans le cadre d'un travail sur une autre version du prototype SESAME [163], avec une approche distribuée basée sur CORBA. Un assistant d'annotation image a ainsi été construit dans ce contexte.
Tous ces assistants, présentés ici de façon très générale, ont accès à l'ensemble de connaissances du système, ainsi qu'à d'autres connaissances, par exemple les algorithmes de détection de plans, de reconnaissance de la parole, etc. Les assistants ne font donc pas partie du << système Strates-IA de base >> (i.e. les Strates-IA peuvent être utilisées sans leur aide), mais participent à son exploitation en collaboration avec l'utilisateur. Il possèdent à cet égard une connaissance plus ou moins limitée des mécanismes des Strates-IA, et doivent être considérés comme des agents intelligents, qui s'appuient sur des modèles de connaissances appropriés aux tâches de l'utilisateur qu'ils assistent.