Soutenance mémoire
Principes généraux sur l’analyse de documents structurés
Documents structurés
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. Dans cette thèse, nous nous intéressons à un type de document structuré bien particulier : les plans d’architecture 2D.
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 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. 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 est largement utilisé pour la production des dessins techniques. FINALE . permet la composition des partitions musicales. Google SketchUp 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 Nous détaillons dans la section suivante les principales techniques pour ces systèmes de reconnaissance.
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.
|
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
IV Prototypage et expérimentations
5 Prototypage : implémentation d’IMISketch sur les plans d’architecture manuscrits
5.1 Description des règles grammaticales
5.2 Dimension du contexte local de recherche
5.3 Impact de l’utilisation des polygones
5.4 Les cas d’ambigüité
5.4.1 Ambigüité structurelle
5.4.2 Ambigüité en reconnaissance de forme
6 Expérimentations
6.1 Base de données
6.2 Test unitaire : apport de l’interactivité pour la reconnaissance de documents structurés
6.3 Test unitaire : sollicitation de l’utilisateur et interfaçage
6.3.1 Expérimentation : impact de la présentation de l’information sur la qualité de leur correction par des utilisateurs
6.3.1.1 Condition séparée
6.3.1.2 Condition intégrée
6.3.1.3 Condition séquentielle
6.3.2 Discussion
6.4 Test unitaire : gestion de la combinatoire liée aux primitives
6.5 Test unitaire : méthode basée sur une exploration hybride : largeur – profondeur
6.6 Évaluation globale de la méthode IMISketch
6.7 Test unitaire : apport de l’utilisation d’un classifieur incrémental
6.8 Conclusion
V Conclusion
