Cette thèse traite dela mise en correspondance de séquences appliquée au word spotting (localisation de motsclés dans des images de documents sans en interpréter le contenu). De nombreux algorithmes existent mais très peu d’entre eux ont été évalués dans ce contexte. Nous commençons donc par une étude comparative de ces méthodes sur plusieurs bases d’images de documents historiques. Nous proposons ensuite un nouvel algorithme réunissant la plupart des possibilités offertes séparément dans les autres algorithmes. Ainsi, le FSM (Flexible Sequence Matching) permet de réaliser des correspondances multiples sans considérer des éléments bruités dans la séquence cible, qu’ils se situent au début, à la fin ou bien au coeur de la correspondance. Nous étendons ensuite ces possibilités à la séquence requête en définissant un nouvel algorithme (ESC : Examplary Sequence Cardinality). Finalement, nous proposons une méthode d’appariement alternative utilisant une mise en correspondance inexacte de chaines de codes (shape code) décrivant les mots. / This thesis deals with sequence matching techniques, applied to word spotting (locating keywords in document images without interpreting the content). Several sequence matching techniques exist in the literature but very few of them have been evaluated in the context of word spotting. This thesis begins by a comparative study of these methods for word spotting on several datasets of historical images. After analyzing these approaches, we then propose a new algorithm, called as Flexible Sequence Matching (FSM) which combines most of the advantages offered separately by several other previously explored sequence matching algorithms. Thus, FSM is able to skip outliers from target sequence, which can be present at the beginning, at the end or in the middle of the target sequence. Moreover it can perform one-to-one, one-to-many and many-to-one correspondences between query and target sequence without considering noisy elements in the target sequence. We then also extend these characteristics to the query sequence by defining a new algorithm (ESC : Examplary Sequence Cardinality). Finally, we propose an alternative word matching technique by using an inexact chain codes (shape code), describing the words.

Previous investigations have sought to determine how listeners might locate word boundaries in the speech signal for the purpose of lexical access. Cutler (1990) proposes the Metrical Segmentation Strategy (MSS), such that only full vowels in stressed syllables and their preceding syllabic onsets are segmented from the speech stream. I report the results of several experiments which indicate that the listener segments the minimal word, a phonologically motivated prosodic constituent, during processing of the speech signal. These experiments were designed to contrast the MSS with two prosodic alternative hypotheses. The Syllable Hypothesis posits that listeners segment a linguistic syllable in its entirety as it is produced by the speaker. The Minimal Word Hypothesis proposes that a minimal word is segmented according to implicit knowledge the listener has concerning statistically probable characteristics of the lexicon. These competing hypotheses were tested by using a word spotting method similar to that in Cutler and Norris (1988). The subjects' task was to detect real monosyllabic words embedded initially in bisyllabic nonce strings. Both open (CV) and closed (CVC) words were embedded in strings containing a single intervocalic consonant. The prosodic constituency of this consonant was varied by manipulating factors affecting prosodic structure: stress, the sonority of the consonant, and the quality of the vowel in the first syllable. The assumption behind the method is that word detection will be facilitated when embedded word and segmentation boundaries are coincident. Results show that these factors are influential during segmentation. The degree of difficulty in word detection is a function of how well the speech signal corresponds to the minimal word. Findings are consistently counter to both the MSS and Syllable hypotheses. The Minimal Word Hypothesis takes advantage of statistical properties of the lexicon, ensuring a strategy which is successful more often than not. The minimal word specifies the smallest possible content word in a language in terms of prosodic structure while simultaneously affiliating the greatest amount of featural information within the structural limits. It therefore guarantees an efficient strategy with as few parses as possible.

Dans cette thèse, nous avons proposé une approche analytique multi-échelle pour le word spotting dans les documents manuscrits. Le modèle proposé fonctionne selon deux niveaux différents. Un module de filtrage global permettant de définir plusieurs zones candidates de la requête dans le document testé. Ensuite, l’échelle de l’observation est modifiée à un niveau inférieur afin d’affiner les résultats et sélectionner uniquement ceux qui sont vraiment pertinents. Cette approche de word spotting est basée sur des familles généralisées de filtres de Haar qui s’adaptent à chaque requête pour procéder au processus de spotting et aussi sur un principe de vote qui permet de choisir l’emplacement spatial où les réponses générées par les filtres sont accumulées. Nous avons en plus proposé une autre approche pour l’extraction de texte du graphique dans les bandes dessinées. Cette approche se base essentiellement sur les caractéristiques pseudo-Haar qui sont générées par l’application des filtres généralisés de Haar sur l’image de bande dessinée. Cette approche est une approche analytique et ne nécessite aucun processus d’extraction ni des bulles ni d’autres composants. / The presented thesis follows two directions. The first one disposes a technique for text and graphic separation in comics. The second one points out a learning free segmentation free word spotting framework based on the query-by-string problem for manuscript documents. The two approaches are based on human perception characteristics. Indeed, they were inspired by several characteristics of human vision such as the Preattentive processing. These characteristics guide us to introduce two multi scale approaches for two different document analysis tasks which are text extraction from comics and word spotting in manuscript document. These two approaches are based on applying generalized Haar-like filters globally on each document image whatever its type. Describing and detailing the use of such features throughout this thesis, we offer the researches of document image analysis field a new line of research that has to be more explored in future. The two approaches are layout segmentation free and the generalized Haar-like filters are applied globally on the image. Moreover, no binarization step of the processed document is done in order to avoid losing data that may influence the accuracy of the two frameworks. Indeed, any learning step is performed. Thus, we avoid the process of extraction features a priori which will be performed automatically, taking into consideration the different characteristics of the documents.

L’objectif du travail de thèse est de proposer un modèle de représentation des écritures dans les images de documents du patrimoine sans recourir à une transcription des textes. Ce modèle, issu d’une étude très complète des méthodes actuelles de caractérisation des écritures, est à la base d’une proposition de scénario de recherche par similarité de mots, indépendante du scripteur et ne nécessitant pas d’apprentissage. La recherche par similarité proposée repose sur une structure de graphes intégrant des informations sur la topologie, la morphologie locale des mots et sur le contexte extrait du voisinage de chaque point d’intérêt. Un graphe est construit à partir du squelette décrit en chaque point sommet par le contexte de formes, descripteur riche et compact. L’extraction de mots est assurée par une première étape de localisation grossière de régions candidates, décrites par une séquence déduite d’une représentation par graphes liée à des critères topologiques de voisinage. L’appariement entre mots repose ensuite sur une distance dynamique et un usage adapté du coût d’édition approximé entre graphes rendant compte de la nature bi-dimensionnelle de l’écriture. L’approche a été conçue pour être robuste aux distorsions de l’écriture et aux changements de scripteurs. Les expérimentations sont réalisées sur des bases de documents manuscrits patrimoniaux exploitées dans les compétitions de word-spotting. Les performances illustrent la pertinence de la proposition et ouvrent des voies nouvelles d’investigation dans des domaines d’applications autour de la reconnaissance de symboles et d’écritures iconographiques / As more and more documents, especially historical handwritten documents, are converted into digitized version for long-term preservation, the demands for efficient information retrieval techniques in such document images are increasing. The objective of this research is to establish an effective representation model for handwriting, especially historical manuscripts. The proposed model is supposed to help the navigation in historical document collections. Specifically speaking, we developed our handwriting representation model with regards to word spotting application. As a specific pattern recognition task, handwritten word spotting faces many challenges such as the high intra-writer and inter-writer variability. Nowadays, it has been admitted that OCR techniques are unsuccessful in handwritten offline documents, especially historical ones. Therefore, the particular characterization and comparison methods dedicated to handwritten word spotting are strongly required. In this work, we explore several techniques that allow the retrieval of singlestyle handwritten document images with query image. The proposed representation model contains two facets of handwriting, morphology and topology. Based on the skeleton of handwriting, graphs are constructed with the structural points as the vertexes and the strokes as the edges. By signing the Shape Context descriptor as the label of vertex, the contextual information of handwriting is also integrated. Moreover, we develop a coarse-to-fine system for the large-scale handwritten word spotting using our representation model. In the coarse selection, graph embedding is adapted with consideration of simple and fast computation. With selected regions of interest, in the fine selection, a specific similarity measure based on graph edit distance is designed. Regarding the importance of the order of handwriting, dynamic time warping assignment with block merging is added. The experimental results using benchmark handwriting datasets demonstrate the power of the proposed representation model and the efficiency of the developed word spotting approach. The main contribution of this work is the proposed graph-based representation model, which realizes a comprehensive description of handwriting, especially historical script. Our structure-based model captures the essential characteristics of handwriting without redundancy, and meanwhile is robust to the intra-variation of handwriting and specific noises. With additional experiments, we have also proved the potential of the proposed representation model in other symbol recognition applications, such as handwritten musical and architectural classification

Les outils et méthodes d’analyse d’images de documents (DIA) donnent aujourd’hui la possibilité de faire des recherches par mots-clés dans des bases d’images de documents alors même qu’aucune transcription n’est disponible. Dans ce contexte, beaucoup de travaux ont déjà été réalisés sur les OCR ainsi que sur des systèmes de repérage de mots (spotting) dédiés à des documents textuels avec une mise en page simple. En revanche, très peu d’approches ont été étudiées pour faire de la recherche dans des documents contenant du texte multi-orienté et multi-échelle, comme dans les documents graphiques. Par exemple, les images de cartes géographiques peuvent contenir des symboles, des graphiques et du texte ayant des orientations et des tailles différentes. Dans ces documents, les caractères peuvent aussi être connectés entre eux ou bien à des éléments graphiques. Par conséquent, le repérage de mots dans ces documents se révèle être une tâche difficile. Dans cette thèse nous proposons un ensemble d’outils et méthodes dédiés au repérage de mots écrits en caractères bengali ou anglais (script Roman) dans des images de documents géographiques. L’approche proposée repose sur plusieurs originalités. / Word spotting in graphical documents is a very challenging task. To address such scenarios this thesis deals with developing a word spotting system dedicated to geographical documents with Bangla and English (Roman) scripts. In the proposed system, at first, text-graphics layers are separated using filtering, clustering and self-reinforcement through classifier. Additionally, instead of using binary decision we have used probabilistic measurement to represent the text components. Subsequently, in the text layer, character segmentation approach is applied using water-reservoir based method to extract individual character from the document. Then recognition of these isolated characters is done using rotation invariant feature, coupled with SVM classifier. Well recognized characters are then grouped based on their sizes. Initial spotting is started to find a query word among those groups of characters. In case if the system could spot a word partially due to any noise, SIFT is applied to identify missing portion of that partial spotting. Experimental results on Roman and Bangla scripts document images show that the method is feasible to spot a location in text labeled graphical documents. Experiments are done on an annotated dataset which was developed for this work. We have made this annotated dataset available publicly for other researchers.