Sujet de thèse: Grammaire 2D pour l’analyse de documents mis en page

 

Directeurs de thèse : David Janin

 

Courriels : janin@labri.fr

 

Équipe: Méthodes Formelles

 

 

Description synthétique du sujet

 

A partir d'un document numérisé, constitué de blocs graphiques (image, caractères, lignes) positionnés les uns par rapport aux autres sur un plan, on souhaite expliciter la structure logique du document: titre, sous-titre, intertitre, date, article, paragraphe, illustrations, etc... Pour cela, on se propose de développer un formalisme de grammaire 2D prendrait en entrée des structures 2D uniquement définies à l'aide d'unités lexicales (bloc graphiques) agencées selon deux types de concaténations : la concaténation horizontale, ou la concaténation verticale, les dimensions des structures étant automatiquement/implicitement ajustées pour permettre ces concaténations.

 

Description détaillée du sujet:

 

Dans l'industrie de la documentation, des efforts humains considérables sont investis dans la restructuration de  documents numérisés. Plus précisément, à partir d'un document numérisé, constitué de blocs graphiques (image, caractères, lignes) positionnés les uns par rapport aux autres sur un plan, il s'agit d'expliciter la structure logique du document: titre, sous-titre, intertitre, date, article, paragraphe, illustrations, etc... Par bien des côtés, cette analyse s'apparente à l'analyse syntaxique pratiquée sur les mots, la différence essentielle étant ici l'agencement planaire des blocs graphiques.

En faisant abstraction des indications de positionnement réelles, en ne retenant que des indications de positionnements relatifs (à coté, au-dessus), on se propose de développer un formalisme de grammaires 2D qui prendrait en entrée des structures 2D uniquement définies à l'aide d'unités lexicales agencées selon deux types de concaténations :

·  la concaténation horizontale,

·  la concaténation verticale,

les dimensions des structures étant automatiquement/implicitement ajustées pour permettre ces concaténations.

 

Le sujet pourrait alors se développer parallèlement selon les axes suivants :

Etude théorique des grammaires existantes (« picture grammars ») où à développer (voir références) : définitions possibles, congruences naturelles et implicites sur les structures d'entrées, forme normale induite des arbres de dérivations, propriétés de décidabilité, classes adhoc de grammaires permettant une analyse en temps linéaire,

Etude de la structure de document réels : application de ces grammaires à l'étude de documents réels (journaux, factures, textes juridiques....), définition de grammaires appropriées pour diverses classes de documents,

Spécification et codage d'un analyseur 2D, mise en oeuvre sur des exemples concrets.

 

Ce sujet, qui trouve son contexte théorique en théorie des langages, dans l’équipe Méthodes Formelles, a un champ d’application en analyse et structuration d’image, dans l’équipe Image et Son. C’est donc un sujet de nature transversale aux équipes du LaBRI. Le doctorant devra participer aux réunions des deux équipes.

Notons par ailleurs la complémentarité de ce sujet avec un sujet proposé en analyse d’images par Nicholas Journet, du LaBRI, qui se propose de développer des techniques d’analyse plus inhérente aux problématiques « images », comme une sorte d’analyse lexicale (2D) que l’étude des grammaires (2D) que nous proposons enrichirait et compléterait naturellement. Retenons cependant qu’il y a là, sans aucun doute, matières à deux thèses parfaitement indépendantes.

 

Bibliographies :

 

[1] Bottoni, Paolo and Labella, Anna, Pointed pictures, Journal of Visual Languages and Computing, 18 : 523 – 536, 2007.

 

[2] Costagliola, Gennaro and Chang, Shi-Kuo, Using Linear Positional Grammars for the LR Parsing of 2-D Symbolic Languages, Grammars 2: 1–34, 1999.

 

[3] Coüasnon, Bertrand, Segmentation et reconnaissance de documents guidées par la connaissance a priori :application aux partitions musicales, Thèse de Doctorat, Université de Rennes I, France, 1996

 

[4] Coüasnon, Bertrand, DMOS, a generic document recognition method: application to table structure analysis in a general and in a specific way, Internationnal Journal of Documentation Analysis, 8(2) : 111-122, 2006

 

[5] Crespi Reghizzi , Stefano and Pradella, Matteo, Tile rewriting grammars and picture languages, Theoretical Computer Science, v.340 n.2, p.257-272, 27 June 2005

 

[6] Journet, Nicholas, Analyse d'images de documents anciens : une approche texture, Thèse de Doctorat, Université de La Rochelle, France, 2006

 

[7] Robadey, Lyse, Une méthode de reconnaissance structurelle de documents complexes basée sur des patterns bidimensionnels, Thèse de Doctorat, Institut d'Informatique de l'Université de Fribourg, Suisse, 2001

[8] Yamamoto, Y. and Morita, K., Two-dimensional uniquely parsable isometric array grammars. Int. J. Pattern Recogn. Artif. Intell. v6. 301-313.