Nous proposons une méthode de groupement en clusters d'objets multidimensionnels étendus, basée sur un modèle de co^ut adaptatif aux requêtes, pour accélérer l'exécution des requêtes spatiales de type intervalle (e.g., intersection, inclusion). Notre travail a été motivé par l'émergence de nombreuses applications de dissémination sélective d'informations posant de nouveaux défis au domaine de l'indexation multidimensionnelle. Dans ce contexte, les approches d'indexation existantes (e.g., R-trees) ne sont pas adaptées aux besoins applicatifs tels que scalabilité (beaucoup d'objets avec des dimensions élevées et des extensions spatiales), performance de recherche (taux élevés de requêtes), performance de mise à jour (insertions et suppressions fréquentes d'objets) et adaptabilité (à la distribution des objets et des requêtes, et aux paramètres systèmes). Dans notre méthode, nous relâchons plusieurs propriétés spécifiques aux structures d'indexation arborescentes classiques (i.e. équilibrage de l'arbre et du partitionnement, englobement minimal des objets) en faveur d'une stratégie de groupement basée sur un modèle de co^ut adaptatif. Ce modèle de co^ut tient compte des caractéristiques de la plateforme d'exécution, de la distribution spatiale des objets et surtout de la distribution spatiale des requêtes. Plus précisément, la distribution des requêtes permet de déterminer les dimensions les plus sélectives et discriminantes à utiliser dans le regroupement des objets. Nous avons validé notre approche par des études expérimentales de performance impliquant de grandes collections d'objets et des requêtes d'intervalles avec des distributions uniformes et non-uniformes.

.

La première partie du document constitue une revue de la situation actuelle de la documentation automatique et de la bureautique. La seconde partie présente des éléments sur la nature de la documentation automatique en bureautique et des propositions pour la réalisation de systèmes. On présente successivement les methodes de documentation automatique, des systèmes et des expériences, l'indexation, la classification, le classement.

Nos travaux ont été motivés par un problème pratique visant à rechercher des objets au sein d'images et en particulier dans des bases d'images de fresques médiévales. Les outils développés devront aider les historiens de l'art dans leur travail quotidien en leur fournissant la possibilité de retrouver et de caractériser des images ou des objets similaires dans l'ensemble des images dont ils disposent. Cette étude se situe par conséquent dans le cadre de la recherche d'images par le contenu. Pour résoudre ce problème, les méthodes classiques sont inefficaces car elles caractérisent les images globalement sans prendre en compte l'arrangement des objets qui les compose. La méthode proposée décrit l'image par un graphe pyramidal considérant alors l'image composée d'objets complexes en relation les uns avec les autres. Un algorithme de segmentation multi-échelles génère un ensemble de partitions cohérentes entre elles isolant ainsi les objets puis leurs parties. Les graphes d'adjacence des différents niveaux sont alors liés les uns avec les autres pour obtenir le graphe pyramidal de l'image. Au sein de cette structure de représentation de haut-niveau, nous avons ensuite cherché à caractériser chaque région le plus correctement possible à partir de sa couleur, sa texture et sa forme. Divers algorithmes sont enfin proposés pour utiliser de manière combinée ces description des objets ainsi que l'information spatiale et pyramidale de la représentation pour déterminer la similarité entre images et détecter des objets semblables au sein de la base d'images. De nombreux exemples expérimentaux illustrent ce manuscrit et montrent que cette approche est globalement plus performante que les systèmes existants.

Les propriétés des réseaux routiers varient considérablement d'un milieu géographique à l'autre. Elles peuvent donc être utilisées pour classer et rechercher de tels environnements. Dans ce travail, nous proposons de classer ces environnements à l'aide d'attributs géométriques et topologiques, calculés à partir des réseaux routiers. Les limites des méthodes d'extraction des routes en milieu urbain dense ont été contournées par la segmentation des zones urbaines et le calcul d'une seconde série d'attributs géométriques et topologiques calculés sur ces masques urbains. Les imagettes formant notre base de données proviennent d'images du satellite SPOT5 de résolution 5m et ont une taille de 512x512 pixels. L'ensemble des attributs géométriques et topologiques, calculés à partir des réseaux routiers et des masques urbains permettent de répartir les imagettes dans des classes géographiques prédéfinies. Afin de réduire la dimension des attributs qui peut nuire aux performances de la classication, un dispositif de sélection des attributs a été mis en place. Il repose sur une analyse linéaire discriminante de Fisher et une classication 'un contre tous' par séparateur à vastes marges (SVM). L'impact de la résolution spatiale et de la taille des images sur les différents attributs a été étudié sur une base de données constituée d'images à 10 m de résolution ainsi que sur une base de données à 5m de résolution pour des imagettes de taille de 256x256 pixels. L'approche a permis la classification complète d'images SPOT5 à partir des imagettes qu'elles contiennent. Dans ce cas, un SVM 'un contre tous' avec un noyau Gaussien, a été utilisé pour classer la scène dans son intégralité.

Nous abordons dans ce mémoire le problème délicat de l'indexation de plans vidéo et en particulier l'indexation automatique par le contenu sémantique. L'indexation est l'opération qui consiste à extraire une signature numérique ou textuelle qui décrit le contenu de manière précise et concise afin de permettre une recherche efficace dans une base de données. L'aspect automatique de l'indexation est important puisque nous imaginons bien la difficulté d'établir les signatures manuellement sur de grandes quantités de données. Jusqu'à présent les systèmes automatiques d'indexation et de recherche d'images ou de vidéos se sont concentrés sur la description et l'indexation du contenu purement visuel. Les signatures permettaient d'effectuer une recherche principalement sur les couleurs et les textures des images. A présent, le nouveau défi est d'ajouter à ces signatures une description sémantique du contenu de manière automatique. Un éventail des techniques utilisées pour l'indexation du contenu visuel est tout d'abord présenté. Ensuite nous introduisons une méthode pour calculer une signature précise et compacte à partir des régions des images clefs des plans. Il s'agit d'une adaptation de l'analyse de la sémantique latente qui fut initialement introduite pour indexer le texte. La tâche délicate de la recherche par le contenu sémantique est ensuite abordée. Les expériences sont conduites dans le cadre de l'évaluation TRECVID qui nous permet d'obtenir une grande quantité de vidéo avec leurs annotations. Nous poursuivons la classification sémantique en étudiant la fusion de systèmes de classification. Finalement nous introduisons une nouvelle méthode d'apprentissage actif.

Aujourd'hui, l'accès aux documents dans les bases de données, d'archives et sur Internet s'effectue principalement grâce à des données textuelles : nom de l'image ou mots-clés. Cette recherche est non exempte de fautes plus ou moins graves : omission, orthographe, etc. Les progrès effectués dans le domaine de l'analyse d'images et de l'apprentissage automatique permettent d'apporter des solutions comme l'indexation et la recherche à base des caractéristiques telles que la couleur, la forme, la texture, le mouvement, le son et le texte. Ces caractéristiques sont riches en informations et notamment d'un point de vue sémantique. Cette thèse s'inscrit dans le cadre de l'indexation automatique par le contenu sémantique des documents multimédia: plans vidéo et images-clés. L'indexation consiste à extraire, représenter et organiser efficacement le contenu des documents d'une base de données. L'état de l'art du domaine est confronté au «fossé sémantique» qui sépare les représentations visuelles brutes (bas-niveau) et conceptuelles (haut-niveau). Pour limiter les conséquences de cette problématique, nous avons introduit dans le système plusieurs types de descripteurs, tout en prenant à notre avantage les avancées scientifiques dans le domaine de l'apprentissage automatique et de la ``fusion multi-niveaux''. En effet, la fusion est utilisée dans le but de combiner des informations hétérogènes issues de plusieurs sources afin d'obtenir une information globale, plus complète, de meilleure qualité, permettant de mieux décider et d'agir. Elle peut être appliquée sur plusieurs niveaux du processus de classification. Dans cette thèse, nous avons étudié la fusion bas-niveau (précoce), la fusion haut-niveau (tardive), ainsi qu'à un niveau décisionnel basé sur l'ontologie et la similarité inter-concepts dit de raisonnement. Les systèmes proposés ont été validés sur les données de TRECVid (projet NoE K-Space) et les vidéos de football issues d'Orange-France Télécom Labs (projet CRE-Fusion). Les résultats révèlent l'importance de la fusion sur chaque niveau du processus de classification, en particulier, l'usage de la théorie des évidences.

Cette thèse s'intéresse aux systèmes de recherche d'images par le contenu, où le but est de rechercher les images les plus similaires à une image requête fournie en exemple. Pour cela, il est d'abord nécessaire de décrire les images stockées dans la base. L'objectif est de traduire la similarité visuelle entre images en une simple notion de proximité spatiale entre descripteurs. Ainsi, pour retrouver les images similaires à l'image requête, il suffit de retrouver les descripteurs les plus proches du descripteur de l'image requête. Ce mode de recherche, appelé recherche de plus proches voisins, est cependant extrêmement coûteux même lorsque les techniques s'indexation multidimensionnelles sont utilisées. Les performances de celles-ci se dégradent exponentiellement lorsque la dimension des descripteurs augmente (phénomène de la malédiction de la dimension). Il s'avère toutefois que l'on peut fortement réduire le coût de ces recherches en effectuant des recherches approximatives. Le principe est alors de négocier une réduction du temps de réponse contre l'introduction d'imprécisions durant la recherche. Ce travail reprend ce principe et propose une nouvelle méthode de recherche approximative de plus proches voisins qui permet un contrôle fin et intuitif de la précision de la recherche. Ce contrôle s'exprime au travers d'un seul paramètre qui indique la probabilité maximale de ne pas trouver un des plus proches voisins recherchés. Dans le but d'évaluer rigoureusement ses performances dans le cadre d'un système réel, la méthode proposée a été ensuite intégrée dans un système de recherche d'images pour la détection de copies. Les expérimentations effectuées montrent que la méthode proposée est efficace, fiable et son imprécision n'a qu'un impact mineur sur la qualité des résultats finaux.

Les flux de télévision sont structurés : ils sont en effet composés de programmes successifs (journaux, films, magazines, etc.) et entrecoupés par des inter-programmes (publicités, bandes annonces, parrainages, etc.). Dès que les flux sont diffusés sur les ondes, ils perdent malheureusement toute information de structure. La problématique de la délinéarisation automatique est de retrouver la structure des flux TV, avec en particulier le début précis et la fin précise de chaque programme, à partir des signaux audiovisuels reçus et des métadonnées éventuellement fournies par les chaînes TV. Cette thèse présente un système complet de délinéarisation automatique rigoureusement évalué sur quatre semaines de flux TV réels, pour deux chaînes de télévision différentes. Les travaux se basent sur la propriété de répétition des inter-programmes. Cette propriété est exploitée à travers la détection de toutes les répétitions d'un flux grâce à une technique de clustering des images clés du flux. Ces répétitions servent à la création de segments qui sont ensuite classés en segments de programme ou en segments d'inter-programme suivant les caractéristiques des répétitions et les relations entre les segments. Pour cela, le système utilise la programmation logique inductive. Une fois les segments classés, les segments de programme appartenant à un même programme sont étiquetés et réunifiés grâce aux métadonnées éventuelles. En l'absence de métadonnées, les segments de programme d'un même programme peuvent être seulement réunifiés grâce à des similarités visuelles.

Nous présentons dans ce document l'ensemble de nos travaux concernant l'appariement, la modélisation et l'indexation des images. Cet ensemble de techniques concourt au développement d'un système de reconnaissance automatique d'images. Dans un premier temps, nous présentons diverses méthodes d'appariement d'images adaptées spécifiquement aux images structurées, texturées en niveaux de gris ou en couleur. Nous montrons comment faire coopérer ces méthodes dans le cas d'images difficiles. La deuxième partie est consacrée à la modélisation d'images et de concepts visuels, modélisation qui repose sur une technique de regroupement hiérarchique. La taille des groupes formés est calculée par une méthode basée sur l'entropie. L'indexation des images occupe la fin du mémoire. Deux cas sont étudiés : celui du stockage des données en mémoire vive, cas pour lequel nous fournissons des résultats de complexité, et celui du stockage en mémoire auxiliaire, qui reste encore largement à explorer. Le tout est largement illustré de cas concrets et ouvre de nombreuses pistes de travail.