Thèse numérisée par la Direction des bibliothèques de l’Université de Montréal / While content selection has been intensively explored in the sentence extraction approach to automatic swnmarization, there is generally little work on the other process of content condensation. To understand this process of condensation, we propose a partial typology based on whether a linguistic unit is replaced, deleted, compressed into fewer essential units, or combined with another unit. Four important categories of condensation processes: generalization, deletion, compression, and aggregation, including their inverse processes, e.g. insertion, and expansion, which were occasionally observed, are proposed. To guide the usage of the same tenu for similar operations, we borrow definitions from linguistics. The type and function of the linguistic units involved are also discussed. We carried out an empirical analysis of 57 author-written abstracts of on-line journal articles in entomology, tracing each abstract sentence back to the plausible source sentences in the corresponding full text. Unlike other studies which focus on the resultant abstract, our study focuses on the processes leading to the production of abstract sentences from corresponding full-text sentences. We do not, however, propose an algorithm for abstracting, or account for all the conditions under which individual condensation operations may apply. While a range of substitutes were used in abstracting, about half of the stems of lexical units in our abstracts share the same stem as their source words, or are their derived forms. Only a small proportion of substitutes were synonyms, and the rest were (quasi-)synonyms, or imprecise equivalents. Authors tend to use less technical forms in abstracts possibly in anticipation of non-specialist abstract readers. Numerical expressions are rendered less precise although no less accurate: absolute numbers and decimals are rounded off, and percentages replaced by ratios or fractions. These observations are consistent with the "new" context of an abstract where only the gist of a document s content need be re-conveyed. Among the linguistic units commonly deleted are metadiscourse phrases, and segments of text (e.g. parenthetical texts, and apposed texts), which provide details and precision in the full text, but are out of place in an abstract. Redundancies inserted for various reasons, or units deemed to be implicit to the comprehension of targeted readers are also often removed. While deletion is an important sub-process of condensation, we observed some instances of adding experimental and other details to compact more information into abstract. The expansion or "unpacking" of compact linguistic units was also observed. The secondary role of inverse processes observed calls for a review of the meaning of condensation from "not giving as much detail or using fewer words" to include the adding of information in order to make a unit of text informatively compact. Among the linguistic units compressed are verbal complexes containing a support verb, or a catenative. Like semantically empty support verbs (e.g. X caused decreases in Y = X reduced Y), some catenatives too may be deleted without significant changes in meaning to the verbal complex (e.g. X was allowed to hatch E-e X hatched). Redundancy in meaning between an adjective and a noun in a noun phrase, e.g. functional role, may be removed, and the phrase compressed to just the stem of the adjective, i.e. function. While not frequently occurring in the corpus studied, the compression of such units may be described by rules, and hence, might be operationalized for automatic abstracting. Aggregation, the combining of units of text within or between sentences, is an important sub-process of condensation. Two-thirds of sentences in abstracts studied were written using multiple sentences, and more sentences were combined without than with the use of an explicit sign, such as a connective, a colon or a semi-colon. If research in summarization is to progress beyond sentence selection, then we must work towards: (a) a clear distinction between operations that are condensation processes, and those that are not; (b) bringing operationally similar processes together under the same designation, and (c) a greater understanding of sub-processes constitutiiig condensation. To this end, our provisional typology for condensation, the range of type of linguistic units involved and their functions sets the first step to advance research into content condensation. We have only just begun to identify the condensation sub-processes in operation during abstracting. The factors that are critical on the interplay of these processes still need to be investigated.

Dans cette thèse, nous abordons le problème de la segmentation des images de documents en proposant de nouvelles approches pour la détection et la classification de leurs contenus. Dans un premier lieu, nous étudions le problème de l'estimation d'inclinaison des documents numérisées. Le but de ce travail étant de développer une approche automatique en mesure d'estimer l'angle d'inclinaison du texte dans les images de document. Notre méthode est basée sur la méthode Maximum Gradient Difference (MGD), la R-signature et la transformée de Ridgelets. Nous proposons ensuite une approche hybride pour la segmentation des documents. Nous décrivons notre descripteur de trait qui permet de détecter les composantes de texte en se basant sur la squeletisation. La méthode est appliquée pour la segmentation des images de documents numérisés (journaux et magazines) qui contiennent du texte, des lignes et des régions de photos. Le dernier volet de la thèse est consacré à la détection du texte dans les photos et posters. Pour cela, nous proposons un ensemble de descripteurs de texte basés sur les caractéristiques du trait. Notre approche commence par l'extraction et la sélection des candidats de caractères de texte. Deux méthodes ont été établies pour regrouper les caractères d'une même ligne de texte (mot ou phrase) ; l'une consiste à parcourir en profondeur un graphe, l'autre consiste à établir un critère de stabilité d'une région de texte. Enfin, les résultats sont affinés en classant les candidats de texte en régions « texte » et « non-texte » en utilisant une version à noyau du classifieur Support Vector Machine (K-SVM) / In this thesis I discuss the document image segmentation problem and I describe our new approaches for detecting and classifying document contents. First, I discuss our skew angle estimation approach. The aim of this approach is to develop an automatic approach able to estimate, with precision, the skew angle of text in document images. Our method is based on Maximum Gradient Difference (MGD) and R-signature. Then, I describe our second method based on Ridgelet transform.Our second contribution consists in a new hybrid page segmentation approach. I first describe our stroke-based descriptor that allows detecting text and line candidates using the skeleton of the binarized document image. Then, an active contour model is applied to segment the rest of the image into photo and background regions. Finally, text candidates are clustered using mean-shift analysis technique according to their corresponding sizes. The method is applied for segmenting scanned document images (newspapers and magazines) that contain text, lines and photo regions. Finally, I describe our stroke-based text extraction method. Our approach begins by extracting connected components and selecting text character candidates over the CIE LCH color space using the Histogram of Oriented Gradients (HOG) correlation coefficients in order to detect low contrasted regions. The text region candidates are clustered using two different approaches ; a depth first search approach over a graph, and a stable text line criterion. Finally, the resulted regions are refined by classifying the text line candidates into « text» and « non-text » regions using a Kernel Support Vector Machine K-SVM classifier

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.

Le traitement automatique de documents consiste en la transformation dans un format compréhensible par un système informatique de données présentes au sein de documents et compréhensibles par l'Homme. L'analyse de document et la compréhension de documents sont les deux phases du processus de traitement automatique de documents. Étant donnée une image de document constituée de mots, de lignes et d'objets graphiques tels que des logos, l'analyse de documents consiste à extraire et isoler les mots, les lignes et les objets, puis à les regrouper au sein de blocs. Les différents blocs ainsi formés constituent la structure géométrique du document. La compréhension de documents fait correspondre à cette structure géométrique une structure logique en considérant des liaisons logiques (à gauche, à droite, au-dessus, en-dessous) entre les objets du document. Un système de traitement de documents doit être capable de : (i) localiser une information textuelle, (ii) identifier si cette information est pertinente par rapport aux autres informations contenues dans le document, (iii) extraire cette information dans un format compréhensible par un programme informatique. Pour la réalisation d'un tel système, les difficultés à surmonter sont liées à la variabilité des caractéristiques de documents, telles que le type (facture, formulaire, devis, rapport, etc.), la mise en page (police, style, agencement), la langue, la typographie et la qualité de numérisation du document. Dans ce mémoire, nous considérons en particulier des documents numérisés, également connus sous le nom d'images de documents. Plus précisément, nous nous intéressons à la localisation d'informations textuelles au sein d'images de factures, afin de les extraire à l'aide d'un moteur de reconnaissance de caractères. Les factures sont des documents très utilisés mais non standards. En effet, elles contiennent des informations obligatoires (le numéro de facture, le numéro siret de l'émetteur, les montants, etc.) qui, selon l'émetteur, peuvent être localisées à des endroits différents. Les contributions présentées dans ce mémoire s'inscrivent dans le cadre de la localisation et de l'extraction d'informations textuelles fondées sur des régions identifiées au sein d'une image de document.Tout d'abord, nous présentons une approche de décomposition d'une image de documents en sous-régions fondée sur la décomposition quadtree. Le principe de cette approche est de décomposer une image de documents en quatre sous-régions, de manière récursive, jusqu'à ce qu'une information textuelle d'intérêt soit extraite à l'aide d'un moteur de reconnaissance de caractères. La méthode fondée sur cette approche, que nous proposons, permet de déterminer efficacement les régions contenant une information d'intérêt à extraire.Dans une autre approche, incrémentale et plus flexible, nous proposons un système d'extraction d'informations textuelles qui consiste en un ensemble de régions prototypes et de chemins pour parcourir ces régions prototypes. Le cycle de vie de ce système comprend cinq étapes:- Construction d'un jeu de données synthétiques à partir d'images de factures réelles contenant les informations d'intérêts.- Partitionnement des données produites.- Détermination des régions prototypes à partir de la partition obtenue.- Détermination des chemins pour parcourir les régions prototypes, à partir du treillis de concepts d'un contexte formel convenablement construit.- Mise à jour du système de manière incrémentale suite à l'insertion de nouvelles données / Document processing is the transformation of a human understandable data in a computer system understandable format. Document analysis and understanding are the two phases of document processing. Considering a document containing lines, words and graphical objects such as logos, the analysis of such a document consists in extracting and isolating the words, lines and objects and then grouping them into blocks. The subsystem of document understanding builds relationships (to the right, left, above, below) between the blocks. A document processing system must be able to: locate textual information, identify if that information is relevant comparatively to other information contained in the document, extract that information in a computer system understandable format. For the realization of such a system, major difficulties arise from the variability of the documents characteristics, such as: the type (invoice, form, quotation, report, etc.), the layout (font, style, disposition), the language, the typography and the quality of scanning.This work is concerned with scanned documents, also known as document images. We are particularly interested in locating textual information in invoice images. Invoices are largely used and well regulated documents, but not unified. They contain mandatory information (invoice number, unique identifier of the issuing company, VAT amount, net amount, etc.) which, depending on the issuer, can take various locations in the document. The present work is in the framework of region-based textual information localization and extraction.First, we present a region-based method guided by quadtree decomposition. The principle of the method is to decompose the images of documents in four equals regions and each regions in four new regions and so on. Then, with a free optical character recognition (OCR) engine, we try to extract precise textual information in each region. A region containing a number of expected textual information is not decomposed further. Our method allows to determine accurately in document images, the regions containing text information that one wants to locate and retrieve quickly and efficiently.In another approach, we propose a textual information extraction model consisting in a set of prototype regions along with pathways for browsing through these prototype regions. The life cycle of the model comprises five steps:- Produce synthetic invoice data from real-world invoice images containing the textual information of interest, along with their spatial positions.- Partition the produced data.- Derive the prototype regions from the obtained partition clusters.- Derive pathways for browsing through the prototype regions, from the concept lattice of a suitably defined formal context.- Update incrementally the set of protype regions and the set of pathways, when one has to add additional data.