Soutenance mémoire
Notion de document structuré
Un «document structuré» désigne un document ayant une structure prédéfinie bien établie. Il est composé d’un ensemble de symboles. L’agencement spatial et les positionnements relatifs des éléments du document offrent une information complémentaire et essentielle à l’interprétation du document. Cette information est une caractéristique principale qui distingue les symboles d’un document structuré à des symboles isolés. Les différentes techniques de reconnaissance de tel document se basent principalement sur cette information. Selon Hilaire [79], les éléments structurés sont composés de :
– traits : généralement l’arc de cercle, le cercle complet, et la ligne droite. Ces courbes sont caractérisées par un ensemble d’attributs tel que l’épaisseur, le style, la couleur, etc ;
– texte : manuscrit ou imprimé ;
– photos.
Généralement, les documents structurés prennent l’une des formes suivantes :
– Document imprimé : c’est un document déjà dessiné par un logiciel de dessin technique et imprimé.
– Document vectoriel : c’est document numérique dessiné par des logiciels de dessin vectoriel
– Document manuscrit : c’est un document dessiné à main levée (croquis) Les problématiques d’interprétation diffèrent d’un type de document à un autre. La qualité de dessin avec un logiciel est nettement meilleure qu’un croquis dessiné à main levée. Dans la littérature, les documents structurés sont de nature très variée. Citons par exemple les diagrammes d’automate à états finis, les partitions de musique, les diagrammes de classe UML, les formules mathématiques, les plans d’architecture, etc.
Plans d’architecture 2D
Le plan d’architecture est un document structuré caractérisé par le fait qu’il résulte presque systématiquement de la superposition de plusieurs couches graphiques. Chaque couche est intéressante pour un professionnel particulier, mais pas nécessairement pour un autre. Nous pouvons résumer un plan d’architecture 2D en trois couches graphiques :
– Une première couche englobe les parties liées aux fondations du bâtiment (maçonnerie). Généralement, cette couche est représentée par un trait épais hachuré.
– Une deuxième couche qui englobe les éléments architecturaux eux-mêmes fenêtres, portes, murs…). Cette couche est souvent représentée par un trait beaucoup plus fin que celui de la premièère couche.
– Une troisième couche comportant des divers symboles ou éléments de construction de dernière œuvre (prise de courant, sanitaires, VMC, carrelage…).
Nous nous concentrons dans la suite de cette étude uniquement sur les plans d’architecture destinés aux clients, c’est-à-dire les plans ne contenant qu’un ensemble d’information jugé utile pour le client (figure 1.3) correspondant aux couches 1 et 2. Pour des raison du cadre applicatif du projet ANR, nous commençons par interpréter les plans d’architecture dessinés à main levée sur une feuille de papier. Ces croquis sont généralement des ébauches de conception dessinés par l’utilisateur pour des opérations de métrage, relevés et aménagement de l’intérieur, etc.
Composition de documents structurés
La composition de document consiste à construire un document structuré et d’aller vers le monde numérique d’une façon cohérente. Plusieurs options sont offertes à l’utilisateur pour composer son document technique. La première solution proposée pour dessiner un document est d’utiliser des logiciels basés sur une interaction souris via une interface «WIMP» . Ces logiciels classiques (traditionnels) sont basés sur une interaction graphique orientée souris et boutons. La figure 1.4 illustre quelques exemples de logiciels utilisés pour la composition des documents structurés. Généralement, l’utilisateur sélectionne les symboles à insérer dans son document à travers une interface graphique contenant tous les symboles. Les exemples de tel logiciels sont nombreux. Nous citons par exemple MICROSOFT OFFICE VISIO pour la composition des diagrammes divers, AUTOCAD (Figure 1.4(a)) est largement utilisé pour la production des dessins techniques. FINALE (Figure 1.4(b))permet la composition des partitions musicales. Google SketchUp (figure 1.4(c)) est logiciel de composition des plans d’architecture. Bien que ces logiciels sont généralement très aboutis, ils sont souvent fastidieux à utiliser pour des utilisateurs novices. A la fin de la composition avec ces logiciels, le document sera bien propre et manipulable.
Une deuxième solution consiste à dessiner un document d’une façon libre, sans imposer des contraintes particulières à l’utilisateur. Cette solution nécessite un système de reconnaissance déclenché après la composition pour bien interpréter le document. Une dernière solution est d’utiliser des logiciels de composition permettant la reconnaissance du document en temps réel. Le système de reconnaissance est intégré dans la phase de composition. Nous intéressons dans la suite de cette partie à ces deux dernières solutions.
Composition libre de documents structurés
Dans la littérature, il existe plusieurs cas d’usages pour la composition libre des documents structurés ainsi que des techniques assurant la passage du document dessiné sous sa forme numérique interprétée.
Usages et propriétés
La composition libre d’un document est la façon la plus rapide et la plus simple pour construire un croquis. Cette possibilité permet à l’utilisateur de composer son document sans des contraintes particulières. Cette composition est effectuée soit sur une feuille papier soit sur une tablette PC via un stylet électronique.
L’avantage de cette composition est la conservation du processus créatif de l’utilisateur. En fait, la séparation entre la connaissance et le moteur de reconnaissance permet de donner toute la liberté à l’utilisateur pour dessiner son document. L’utilisateur dessine son document comme il le souhaite, sans qu’aucune contrainte ne lui soit imposée. L’utilisateur doit seulement respecter les règles générales concernant un type de document donné. Il peut, par exemple, commencer un symbole sans avoir fini le précédent. De plus, tous les éléments constituant un document structuré sont omniprésents : le contexte structurel pour interpréter un symbole est disponible quand le processus d’analyse entre en jeu. Cette séparation diminue l’importance du temps d’analyse sur la qualité des systèmes de reconnaissance. Cependant ces système n’offrent pas d’interaction. Ceci favorise la propagation de mauvaises interprétations durant la phase de reconnaissance, car les systèmes de reconnaissance ne détectent pas d’une manière progressive les erreurs d’interprétation.
Système de reconnaissance : rétroconversion
Étant donné un document structuré, la rétroconversion de ce document est le processus qui vise à en trouver une représentation numérique, manipulable par l’ordinateur, la plus proche possible de celle que son concepteur. Contrairement à l’interprétation en-ligne à la volée, la rétroconversion a pour but de reconnaitre un document après sa composition. Le processus d’analyse est généralement déclenché par l’utilisateur. La figure 1.6 montre un exemple d’interprétation a posteriori : le système n’intervient qu’à la fin de la production du document. Le système essaie d’interpréter les tracés et de les transformer en des symboles.
Si le document à rétroconvertir est une image, c’est-à-dire un document numérisé (scanné), le signal manipulé est dit hors-ligne, et la rétroconversion est dite «rétroconversion hors-ligne». Ceci signifie que le système a accès à l’information au niveau pixel. Le signal hors-ligne peut représenter à la fois des formes manuscrites et des formes non-manuscrites. La rétroconversion peut également être introduite pour les documents en-ligne, c’est-à-dire des documents constitués d’un ensemble de tracés dessinés par un stylo électronique. Nous nous focalisons ici sur la rétroconversion hors-ligne. La rétroconversion, dans la suite de cette thèse, désigne l’interprétation en-ligne a posteriori et l’interprétation hors-ligne.
La rétroconversion hors-ligne des documents structurés a fait l’objet de plusieurs travaux de recherches. Plusieurs techniques ont été développées pour la reconnaissance de documents structurés spécifiques, c’est-à-dire qu’elles ont été conçues pour un domaine spécifique. La rétroconversion des partitions musicales a fait l’objectif de plusieurs travaux de recherche [92] [112] [133]. Contrairement à ces méthodes, notre but est de développer une méthode générique capable d’interpréter les documents de différents domaines, même si notre méthode sera appliquée initialement sur les plans d’architectures. Plusieurs travaux ont été développés pour la rétroconversion des plans d’architecture. Shio propose le prototype Sketch plan [147] [12] pour l’interprétation hors-ligne des plans d’architecture manuscrits. Valveny et Marti [162] utilisent la correspondance de modèle déformable pour reconnaître symboles architecturaux manuscrits. Messmer [116] a proposé une méthode basée sur le réseau de contraintes consistant à rechercher l’isomorphisme dans un sous graphes afin d’extraire les descripteurs d’un symbole. Cette méthode a été utilisé pour les plan d’architecture dessinés à main levée. Dans les approches basées sur le réseau de contraintes, les symboles graphiques sont représentés par un ensemble de contraintes de descripteurs géométriques. Ces contraintes sont propagées à travers l’hiérarchie du réseau. L’un des avantages des réseaux de contraintes est la possibilité d’avoir une méthode incrémentale capable d’ajouter de nouvelles classes de symboles. Malgré les efforts de Ah Soon [5] pour rendre la méthode plus claire et plus directe en utilisant la description des symboles par les contraintes de Pasternak [125], l’implémentation de cette méthode reste très complexe. Dosch [54] s’est basé sur cette technique pour la reconnaissance des plans d’architecture. Lladós [105] propose une méthode structurelle pour la reconnaissance des symboles et des textures. Cette méthode a été appliquée à des plans d’architecture imprimés ou dessinés à la main. Elle est basée sur les techniques des correspondances de chaînes. Lladós considère les symboles et les textures comme un ensemble de régions, c’est-à-dire des formes convexes dans le graphique, avec un agencement particulier. Ahmed [7] propose également une méthode pour la rétroconversion des plans d’architecture basée sur trois étapes principales : la première phase est la phase de segmentation. Cette étape permet de détecter les murs externes (les murs dessinés par des traits épais) et séparer le texte des graphiques. La deuxième est une phase d’analyse structurelle. Elle consiste à détecter les murs dessinés par des traits fins. La troisième phase est la phase sémantique permettant la détection des portes, fenêtres et les chambres en utilisant les descripteurs SURF [7] [18]. Dosh [54] a utilisé ces mêmes étapes pour la reconstruction des plans d’architecture en 3D. Nous pouvons citer également les méthodes de reconnaissances de schéma [29] [125] [75] [93] [14]. Toutes ces méthodes sont spécifiques et ne sont pas interactive. L’utilisateur a besoin d’un passage après la phase de rétroconversion pour corriger les éventuelles erreurs. De plus, les méthodes proposées ne peuvent pas prendre en compte des nouveaux symboles durant l’analyse. L’utilisateur est obligé de définir tous les symboles pouvant exister dans le document lors de la conception du système.
|
Table des matières
INTRODUCTION
I Principes généraux sur l’analyse de documents structurés
1 Concepts généraux
1.1 Documents structurés
1.1.1 Notion de document structuré
1.1.2 Plans d’architecture 2D
1.2 Composition de documents structurés
1.2.1 Composition libre de documents structurés
1.2.1.1 Usages et propriétés
1.2.1.2 Système de reconnaissance : rétroconversion
1.2.2 Composition de documents structurés numériques par un logiciel de reconnaissance en temps réel orientée stylo
1.2.2.1 Usages et propriétés
1.2.2.2 État de l’art des systèmes de reconnaissance avec l’interprétation à la volée
1.2.3 Bilan et conclusion
2 Processus et principe de la rétroconversion
2.1 Prétraitement
2.2 Analyse
2.3 Analyse : extraction des primitives
2.3.1 Méthodes existantes
2.3.2 Choix des primitives
2.4 Analyse : analyse des primitives
2.4.1 Approches basées sur des heuristiques
2.4.2 Approches basées sur les statistiques
2.4.3 Approches structurelles
2.4.3.1 Graphes
2.4.3.2 Grammaires
2.4.3.2.a Grammaires à base d’opérateurs
2.4.3.2.b Grammaires à base de fonctions
2.5 Analyseur : type d’analyse
2.5.1 Analyse ascendante
2.5.2 Analyse descendante
2.5.3 Analyse mixte
2.5.4 Choix du type d’analyse
2.6 Interactivité : interprétation des documents et gestion d’erreurs
2.6.1 Méthodes existantes
2.6.2 Caractéristiques de l’interaction «homme-document»
2.6.2.1 Le moment de la sollicitation
2.6.2.2 La présentation des hypothèses d’interprétation
2.7 Discussion et choix du formalisme
II Principes spécifiques : Grammaires de multi-ensembles à contraintes pilotées par le contexte
3 Grammaires de multi-ensembles à contraintes pilotées par le contexte
3.1 Description formelle des GMC-PC
3.1.1 Vision globale du document
3.1.1.1 Syntaxe
3.1.1.2 Préconditions
3.1.1.3 Postconditions
3.1.2 Vision locale des éléments interprétés : les contraintes
3.1.2.1 Contraintes structurelles
3.1.2.2 Contraintes statistiques
3.2 Évaluation d’une production GMC-PC
3.2.1 Degré d’adéquation des préconditions
3.2.2 Degré d’adéquation des contraintes
3.2.3 Déduction du degré d’adéquation d’une production et d’une interprétation
3.3 Techniques de rejet
3.4 Limitation de GMC-PC
3.5 Bilan
III Contribution : la méthode IMISketch
4 Description de la méthode IMISketch
4.1 Prétraitement : extraction des primitives
4.2 Modélisation des connaissances a priori
4.2.1 Grammaires GMC-PC
4.2.2 Classifieur
4.3 Construction des arbres d’analyse
4.3.1 Définition du contexte local de recherche
4.3.2 Construction des arbres d’analyse
4.3.2.1 Construction en largeur des arbres d’analyse
4.3.2.2 Optimisation de la construction des arbres d’analyse
4.3.2.2.a Contraintes structurelles pour l’exploration en largeur
4.3.2.2.b Construction hybride des arbres d’analyse
4.4 Prise de décision
4.4.1 Calcul des scores
4.4.2 Validation de la reconnaissance
4.4.2.1 Validation de la reconnaissance structurelle
4.4.2.2 Validation de la reconnaissance graphique
4.5 Bilan
CONCLUSION
Télécharger le rapport complet
