Dans cette th{è}se, nous nous int{é}ressons {à} la repr{é}sentation et {à} la classification de structures spatiales dans le cadre de la reconnaissance de mod{è}les de paysages agricoles sur des images satellites. Nous avons d{é}fini, lors d'une phase d'acquisition des connaissances, des mod{è}les de paysages sous forme de classes dans un syst{è}me de repr{é}sentation des connaissances par objets. Les classes sont reli{é}es entre elles par des relations spatiales qualitatives. Les relations spatiales sont des classes dont les instances lient d'autres classes. Les classes de relations sont organis{é}es dans une hi{é}rarchie ayant une structure de treillis permettant de repr{é}senter la sp{é}cialisation, l'implication, la disjonction et la conjonction de relations. Nous avons choisi un treillis de Galois qui permet de mettre en {é}vidence le lien entre relations et conditions n{é}cessaires {à} la v{é}rification des relations sur l'image. Gr{â}ce {à} cette structure, nous avons propos{é} un algorithme de recherche de l'ensemble minimum des conditions qui permet de r{é}duire le nombre d'op{é}rations sur les images. Des algorithmes ont {é}t{é} aussi propos{é}s pour repr{é}senter les propri{é}t{é}s math{é}matiques des relations. Nous proposons d'ajouter au langage quatre facettes permettant de repr{é}senter la quantification des relations spatiales. Nous avons modifi{é} l'op{é}ration qui associe un mod{è}le {à} une entit{é} pour prendre en compte la quantification des relations dans la classification des structures spatiales. Le syst{è}me de reconnaissance a {é}t{é} implant{é} dans le langage \yafool et mis en \oe{}uvre sur des cartes de la r{é}gion Lorraine.

Les modèles de connaissances à objets (MCO) souffrent d'une surcharge dans l'utilisation de leur langage de représentation associé. Si ce langage a pour objectif d'être adapté à la représentation informatique d'un domaine d'application, nous montrons qu'il n'est pas pertinent de l'utiliser pour définir des structures de données, certes utiles pour la représentation du domaine, mais dépourvues de signification directe dans ce domaine (ex. une matrice dans le domaine de l'astronomie). Cette thèse propose un système de types à deux niveaux, appelé METÈO. Le premier niveau de METÈO est un langage pour l'implémentation de types abstraits de données (ADT) qui sont nécessaires à la description minimale des éléments pertinents du domaine d'application. Ainsi, METÈO libère le langage de représentation d'une tâche à laquelle il n'a pas à s'adapter. Le second niveau de METÈO traite de l'affinement des ADT opéré dans la description des objets de représentation. Nous rappelons les deux interprétations des objets de représentation: l'intension d'un objet est une tentative de description de ce que cet objet dénote dans le domaine d'application: son extension. L'équivalence généralement admise entre ces deux aspects de l'objet est une illusion, et contribue de plus à annihiler une des véritables finalités d'un modèle de connaissances: aider une caractérisation des plus précises d'un domaine d'application. Ainsi, les types du second niveau de METÈO s'attachent à la représentation et la manipulation des intensions des objets, indépendamment de leurs extensions. L'interprétation en extension des objets est effectuée par l'utilisateur, METÈO gère en interne les descriptions de ces objets alors dénuées de leur signification, et le MCO peut alors se concentrer sur la coopération entre ces deux aspects des objets, considérés non-équivalents dans cette étude. METÈO contribue ainsi à clarifier le rôle de chaque partenaire impliqué dans la construction et l'exploitation d'une base de connaissances. Plus généralement, METÈO jette un pont entre les spécificités des MCO et les techniques usuelles de programmation de structures de données manipulables. Un prototype de METÈO a été développé pour un couplage avec le MCO TROPES

La thèse se situe dans le domaine de l'analyse latticielle de données dans la situation, très générale, ou des objets de nature diverse sont décrits par des variables de types divers ; on fait simplement l'hypothèse (réaliste) selon laquelle chaque variable prend ses valeurs dans un treillis. Les problèmes de traitement de telles données (extraction de connaissance) reviennent souvent à chercher à obtenir des familles de Moore de type particulier, par exemple arborescent, et donc à imposer des contraintes structurelles. Dans ce cadre, nous étudions d'abord les familles de Moore particulières que sont les hiérarchies, dont nous caractérisons la base canonique d'implications. Pour ce faire, nous introduisons un nouveau type de relations binaires sur les parties d'un ensemble, appelées (\em relations d'emboitement). Nous les mettons en correspondance bi-univoque avec les familles de Moore quelconques, établissons leur lien avec l'une des relations flèche, et revenons sur leurs propriétés dans le cas hiérarchique, ou elles sont d'abord apparues. Dans une seconde partie, nous nous intéressons à la correspondance de Galois associée à un tableau binaire (auquel les données du type indiqué ci-dessus peuvent toujours être ramenées). Nous examinons alors les contraintes à imposer à un tableau binaire pour que les fermés obtenus appartiennent à des familles de Moore prescrites, ou de type voulu. On obtient alors des relations binaires dites (\em bifermées). Etant donnés deux espaces de fermeture $(E, \varphi)$ et $(E', \varphi')$, une relation est bifermée si toute ligne de sa représentation matricielle correspond à un fermé par $\varphi$, et toute colonne à un fermé par $\varphi'$. Nous établissons l'isomorphisme entre l'ensemble des relations bifermées et celui des correspondances de Galois entre les deux treillis de fermés induits par $\varphi$ et $\varphi'$. Dans le cas fini, on en déduit des algorithmes efficaces pour l'ajustement d'une correspondance de Galois à une application quelconque entre deux treillis, ou pour le calcul du supremum de deux polarités. Dans une troisième partie, nous appliquons les résultats précédents à l'étude de l'introduction de contraintes classificatoires sur un tableau de données. Nous revenons sur divers usages des correspondances de Galois (ou des couples application résiduée / résiduelle) dans les modèles et les méthodes de la classification. Ceux-ci sont revisités dans l'optique d'une présentation unifiée fondée sur les bifermées, et, en prenant en compte les résultats de la première partie, des voies sont tracées pour la définition de nouvelles méthodes. Ces parties sont précédées d'une synthèse sur les treillis et les correspondances de Galois.

Nous abordons, par une modélisation à base de graphes, deux problèmes de structuration de données. Phylogénie: Nous utilisons la famille de graphes associée à une dissimilarité pour définir la notion nouvelle de distance triangulée, plus générale qu'une distance additive d'arbre. Nous proposons un algorithme d'ajustement de données à une distance triangulée par triangulation des graphes associés. Nous introduisons pour cela le concept nouveau de sous-triangulation maximale, afin de prendre en compte la sous-évaluation intrinsèque des données phylogénétiques. Nous procédons ensuite à une étude théorique complémentaire. Analyse Formelle de Concepts: Nous codons une relation binaire R et son treillis des concepts L(R) par un graphe non orienté co-biparti G(R). Nous montrons que les éléments de L(R) sont en bijection avec les séparateurs minimaux de G(R), et que les chaînes maximales de L(R) sont en bijection avec les triangulations minimales de G(R). Des procédés algorithmiques appliqués à G(R) trouvent ainsi leurs correspondants dans L(R). En particulier, des treillis de taille polynomiale peuvent être obtenus à partir de L(R), par plongement de G(R) dans un graphe faiblement triangulé. Nous mettons ensuite en évidence un ordre de domination sur les modules complets maximaux de G(R), domination qui s'hérite quand on parcourt une chaîne maximale de L(R). Une structure de données, la table de domination, gère dynamiquement les relations de domination. Nous utilisons cette table pour deux applications algorithmiques: - Mise à jour d'une sous-hiérarchie de Galois matérialisant une hiérarchie d'héritage orienté-objet; - Génération efficace d'un treillis des concepts.

Découvrir des renversements de tendances entre deux cubes de données offre aux utilisateurs une connaissance nouvelle et intéressante lors des fluctuations de l'univers réel modélisé : quelles sont les nouveautés ? Quelle tendance apparaît ou disparaît ? Nous introduisons le nouveau concept de Cube Émergent. Il capture les renversements de tendances en mettant en œuvre une contrainte d'émergence (conjonction de contrainte monotones et antimonotones). Les bordures, classiques en fouille de données, sont reprises pour le Cube Émergent. Dans un second temps, nous proposons un nouveau couple de bordures pour optimiser à la fois l'espace de stockage et le temps de calcul. Cette nouvelle représentation fournit une caractérisation simple de la taille du Cube Émergent aussi bien que des outils de classification et de navigation dans les cubes. La connexion entre les bordures classiques et celles proposées est formellement établie en utilisant le concept de cube transversal. Connaître la taille du Cube Émergent est d'un grand intérêt, en particulier pour ajuster au mieux la contrainte d'émergence sous-jacente. Cette problématique est traitée en étudiant une borne supérieure et en caractérisant la taille exacte du Cube Émergent. Deux stratégies sont proposées pour estimer rapidement cette taille : la première est basée sur une estimation analytique, sans accès à la base de données, la seconde s'appuie sur un comptage probabiliste utilisant les bordures proposées comme entrée de l'algorithme proche de l'optimal HYPERLOGLOG. Grâce à la particulière efficacité de cet algorithme, plusieurs itérations peuvent être réalisées pour calibrer au mieux la contrainte d'émergence. De plus, des nouvelles représentations réduites et sans perte d'information du Cube Émergent sont proposées en utilisant le concept de fermeture cubique.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Cette thèse est composée de deux contributions à l'étude des bases de données : (i) la première contribution porte sur l'amélioration de la compréhension, par l'étude formelle, de la tension entre les fonctionnalités de cohérence et de confidentialité. Cette tension permet, dans certaines situations, d'utiliser les contraintes d'intégrité (cohérence) pour révéler des secrets (confidentialité) et donc réaliser des fraudes. L'étude fixe tout d'abord un cadre général de recherche en donnant une définition formelle des notions de secret, révélation et fraude. Puis, une occurrence particulière, et originale, de tension est formalisée selon une méthode inspirée des méthodes de programmation. Cette occurrence s'est avérée liée aux treillis de Galois. (ii) la deuxième contribution porte sur la spécification et l'implémentation d'une fonctionalité originale : le classement d'objets selon leur histoire. A cette fin, l'étude répond successivement aux trois questions : qu'est-ce que l'histoire d'un objet, comment exprimer des propriétés sur l'histoire des objets, et comment les vérifier efficacement ? L'expression est réalisée par des formules de logique temporelle et la méthode de vérification repose sur la traduction de ces formules en expressions régulières puis en automates d'états finis. L'implémentation réalisée utilise cette méthode de classement pour classer a posteriori des objets du langage prototypique NewtonScript.

Le récent développement de la Fabrication Additive de pièces métalliques permet d'élaborer directement des structures à partir de modèles 3D. En particulier, la technologie "Electron Beam Melting" (EBM) permet la fusion sélective, couche par couche, de poudres métalliques. Elle autorise la réalisation de géométries très complexes mais apporte de nouvelles contraintes de fabrication.Ce travail se concentre sur la caractérisation géométrique et mécanique de structures treillis produites par cette méthode. Les pièces fabriquées sont comparées au design initial à travers des caractérisations par tomographie aux rayons X. Les propriétés mécaniques sont testées en compression uni-axiale. Pour les poutres de faibles épaisseur, la différence entre la structure numérique et celle fabriquée devient significative. Les écarts au design initial se traduisent pour chaque poutre par un concept de matière mécaniquement efficace. D'un point de vue modélisation, ce concept est pris en compte en remplaçant la poutre fabriquée par un cylindre avec un diamètre mécaniquement équivalent. Ce diamètre équivalent est utilisé dans des simulations et optimisations "réalistes" intégrant ainsi les contraintes de fabrication de la technologie EBM.Différentes stratégies sont aussi proposées pour réduire la proportion de volume "inefficace" et améliorer le contrôle de la taille des poutres, soit en jouant sur les paramètres procédé et les stratégies de fusion, soit en effectuant des post-traitements. / The recent development of Additive Manufacturing for the fabrication of metallic parts allows structures to be directly manufactured from 3D models. In particular, the "Electron Beam Melting" (EBM) technology is a suitable process which selectively melts a powder bed layer by layer. It can build very complex geometries but brings new limitations that have to be quantified.This work focuses on the structural and mechanical characterization of lattice structures produced by such technology. The structural characterization mainly rely on X-ray tomography whereas mechanical properties are assessed by uni-axial compression. The geometry and related properties of the fabricated structures are compared with the designed ones. For small strut size, the difference between the designed structure and the produced one is large enough to impact the desired mechanical properties. The concept of mechanical efficient volume is introduced. For the purpose of simulation, this concept is taken into account by replacing the struts by a cylinder with a textit{mechanical equivalent diameter}. After validation, it has been used into "realistic" simulation and optimization procedures, thus taking into account the process constraints.Post-treatments (Chemical Etching and Electro-Chemical Polishing) were applied on lattice structures to get rid of the inefficient matter by decreasing the surface roughness. The control of the size of the fabricated struts was improved by tuning the process strategies and parameters.

Cette thèse se situe dans le contexte des modèles logique de Recherche d'Information (RI). Le travail présenté dans la thèse est principalement motivé par l'inexactitude de l'hypothèse sur l'indépendance de termes. En effet, cette hypothèse communément acceptée en RI stipule que les termes d'indexation sont indépendant les un des autres. Cette hypothèse est fausse en pratique mais permet tout de même aux systèmes de RI de donner de bon résultats. La proposition contenue dans cette thèse met également l'emphase sur la nature déductive du processus de jugement de pertinence. Les logiques formelles sont bien adaptées pour la représentation des connaissances. Elles permettent ainsi de représenter les relations entre les termes. Les logiques formelles sont également des systèmes d'inférence, ainsi la RI à base de logique constitue une piste de travail pour construire des systèmes efficaces de RI. Cependant, en étudiant les modèles actuels de RI basés sur la logique, nous montrons que ces modèles ont généralement des lacunes. Premièrement, les modèles de RI logiques proposent normalement des représentations complexes de document et des requête et difficile à obtenir automatiquement. Deuxièmement, la décision de pertinence d->q, qui représente la correspondance entre un document d et une requête q, pourrait être difficile à vérifier. Enfin, la mesure de l'incertitude U(d->q) est soit ad-hoc ou difficile à mettre en oeuvre. Dans cette thèse, nous proposons un nouveau modèle de RI logique afin de surmonter la plupart des limites mentionnées ci-dessus. Nous utilisons la logique propositionnelle (PL). Nous représentons les documents et les requêtes comme des phrases logiques écrites en Forme Normale Disjonctive. Nous argumentons également que la décision de pertinence d->q pourrait être remplacée par la validité de l'implication matérielle. Pour vérifier si d->q est valide ou non, nous exploitons la relation potentielle entre PL et la théorie des treillis. Nous proposons d'abord une représentation intermédiaire des phrases logiques, où elles deviennent des noeuds dans un treillis ayant une relation d'ordre partiel équivalent à la validité de l'implication matérielle. En conséquence, nous transformons la vérification de validité de d->q, ce qui est un calcul intensif, en une série de vérifications simples d'inclusion d'ensembles. Afin de mesurer l'incertitude de la décision de pertinence U(d->q), nous utilisons la fonction du degré d'inclusion Z, qui est capable de quantifier les relations d'ordre partielles définies sur des treillis. Enfin, notre modèle est capable de travailler efficacement sur toutes les phrases logiques sans aucune restriction, et est applicable aux données à grande échelle. Notre modèle apporte également quelques conclusions théoriques comme: la formalisation de l'hypothèse de van Rijsbergen sur l'estimation de l'incertitude logique U(d->q) en utilisant la probabilité conditionnelle P(q|d), la redéfinition des deux notions Exhaustivité et Spécificité, et finalement ce modèle a également la possibilité de reproduire les modèles les plus classiques de RI. De manière pratique, nous construisons trois instances opérationnelles de notre modèle. Une instance pour étudier l'importance de Exhaustivité et Spécificité, et deux autres pour montrer l'insuffisance de l'hypothèse sur l'indépendance des termes. Nos résultats expérimentaux montrent un gain de performance lors de l'intégration Exhaustivité et Spécificité. Cependant, les résultats de l'utilisation de relations sémantiques entre les termes ne sont pas suffisants pour tirer des conclusions claires. Le travail présenté dans cette thèse doit être poursuivit par plus d'expérimentations, en particulier sur l'utilisation de relations, et par des études théoriques en profondeur, en particulier sur les propriétés de la fonction Z. / This thesis is situated in the context of logic-based Information Retrieval (IR) models. The work presented in this thesis is mainly motivated by the inadequate term-independence assumption, which is well-accepted in IR although terms are normally related, and also by the inferential nature of the relevance judgment process. Since formal logics are well-adapted for knowledge representation, and then for representing relations between terms, and since formal logics are also powerful systems for inference, logic-based IR thus forms a candidate piste of work for building effective IR systems. However, a study of current logic-based IR models shows that these models generally have some shortcomings. First, logic-based IR models normally propose complex, and hard to obtain, representations for documents and queries. Second, the retrieval decision d->q, which represents the matching between a document d and a query q, could be difficult to verify or check. Finally, the uncertainty measure U(d->q) is either ad-hoc or hard to implement. In this thesis, we propose a new logic-based IR model to overcome most of the previous limits. We use Propositional Logic (PL) as an underlying logical framework. We represent documents and queries as logical sentences written in Disjunctive Normal Form. We also argue that the retrieval decision d->q could be replaced by the validity of material implication. We then exploit the potential relation between PL and lattice theory to check if d->q is valid or not. We first propose an intermediate representation of logical sentences, where they become nodes in a lattice having a partial order relation that is equivalent to the validity of material implication. Accordingly, we transform the checking of the validity of d->q, which is a computationally intensive task, to a series of simple set-inclusion checking. In order to measure the uncertainty of the retrieval decision U(d->q), we use the degree of inclusion function Z that is capable of quantifying partial order relations defined on lattices. Finally, our model is capable of working efficiently on any logical sentence without any restrictions, and is applicable to large-scale data. Our model also has some theoretical conclusions, including, formalizing and showing the adequacy of van Rijsbergen assumption about estimating the logical uncertainty U(d->q) through the conditional probability P(q|d), redefining the two notions Exhaustivity and Specificity, and the possibility of reproducing most classical IR models as instances of our model. We build three operational instances of our model. An instance to study the importance of Exhaustivity and Specificity, and two others to show the inadequacy of the term-independence assumption. Our experimental results show worthy gain in performance when integrating Exhaustivity and Specificity into one concrete IR model. However, the results of using semantic relations between terms were not sufficient to draw clear conclusions. On the contrary, experiments on exploiting structural relations between terms were promising. The work presented in this thesis can be developed either by doing more experiments, especially about using relations, or by more in-depth theoretical study, especially about the properties of the Z function.

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.