Thèse CIFRE Reconnaissance et comparaison de structure de

- application aux documents administratifs -

Thèse CIFRE

Reconnaissance et comparaison de structure de documents

2

Plan

1. Présentation de l’entreprise

2. Présentation du sujet

3

Introduction

Prestation de service en dématérialisation

AG2R, AIRBUS, ARCHIVES DEPARTEMENTALES, BOUYGUES TELECOM, CAPGEMINI, CEA, DASSAULT AVIATION, FRANCE TELECOM, IBM, IONIS, IPECA, LYONNAISE DES EAUX, SNCF, SNECMA, THALES GROUP…

Références commerciales

4

Quelques chiffres

3 millions d’images numérisées par mois (très variable)

270 salariés

1400 scans / heure / opérateur (max)

92 scanners couleurs (microformes, plan, A0, A3, A4, binarisation à la volé, redressement, couleur et noir et blanc simultané, …)

5

Numérisation + traitement des fichiers

• Etapes de prestations: récupération, préparation, numérisation, traitements d'images, OCR, indexation, contrôle, importation dans une GED…

•Nature des documents: papiers noir et blanc, couleur, diapositives, microformes, plans, registres, journaux, affiches, plaques de verre...

Dématérialisation

6

Types de documents numérisés

Globalement : •Documentations techniques (75%)•Documents RH (10%)•Facture (3%)•Note de frais (3%)•Bulletin de salaire (1%)•Registres d’état civil (0,05%)•Plans cadastraux (0,005%) • …

Grandes variations, dépendant des prestations et de l’activité (archive ou flux)• Archive (90%)• Flux (10%) -> cible de la thèse

7

Types de documents numérisés

En moyenne, un document est composé de 10 pages.

15% des pages sont identifiés (1ères pages)

La quasi-totalité des pages sont traitées : détection d’anomalies.

Détection de pages blanches pour les versos (->50% des pages).

8

Type de problèmes rencontrés

• Problèmes généraux : Chaque prestation est très différente. Grande variation des documents dans le temps.

• Problèmes dues à l’OCR : Qualité des documents (impression matricielle, annotations, pliures,

texte vertical, écriture blanche et fond noir) Autres (mélange des langues , présence d’images dans les pages,

texte sur les images, texte en manuscrit )

• Problèmes dues au traitement d’image : Qualité des documents (transparence, rotation) Autres (détection de couleur, binarisation)

9

Type de problèmes rencontrés

• Détection couleur

10

• Page blanche, page non-blanche

Type de problèmes rencontrés

11

Plan

1. Présentation de l’entreprise

2. Présentation du sujet

Introduction2.1 Analyse2.2 Classification

12

Introduction

Traitement de document

Référence : [1]

Analyse Classification Compréhension

13

Introduction

•1960-2000 : traitement de document = OCR.

•2000-2010 : traitement = séparation du texte des graphiques, OCR, analyse, identification, classification...

• Analyse de document: reconstruction de la mise en page d’un document à partir de l’image papier.

• Classification de document: association d’un document à une classe (prédéfinie) en lui affectant le label correspondant.

• “Compréhension” de document : association de labels à plusieurs parties du document.

Référence : [1]

14

Etapes du traitement

AnalysePrétraitement (redressement, restauration, nettoyage) Segmentation en blocs (RSLA, composantes connexes)Analyse des blocs (caractéristiques pixels)

ClassificationChoix et représentation des descripteursComparaison

Référence : [2]

15

2.1.1.Prétraitement• Redressement.[2] : RLSA puis Hough

sous-échantillonagepuis Hough ->

Référence : [2]

Analyse

16

2.1.2.Segmentation en blocs RSLA (Run Length Smoothing Algorithm)

Référence : [2]

Analyse

17

2.1.3. Analyse des blocs

Méthode de classification du bloc : texte, graphique ou image.• Lignes -> ratio hauteur largeur• Image : entropie du niveaux de gris• Texte et graph -> densité de pixels noir

Référence : [2]

Analyse

18

Classification

2.2.1. Problématique

-> Définition de l’espace document et de l’ensemble des classes

Les classes peuvent être basées sur le fond (similitude des contenues) et/ou la forme (similitude visuelle).

Ex. : une classe « document détérioré », une classe « facture »

Référence : [3]

19

Classification

La classification peut être faite à différent niveaux :- grossière / haut niveau (ex.: bulletin de salaire, facture, doc technique, …)- fine / bas niveau (ex.: bulletin de l’entreprise X ou Y, du salarié, …)

2.2.2. Architecture d’un classificateur

-> 4 aspects caractérisent un classificateur: (a) les propriétés du document et le stade de la reconnaissance(b) le choix et représentations des descripteurs(c) les catégories de modèles et d'algorithmes de classification(d) le mécanismes d'apprentissage.

-> Ces aspects sont interdépendants.

Référence : [3]

20

Architecture d’un classificateur

(a) Stade de la reconnaissance-> la classification peut être effectuée à différents stades du traitement.-> dépend de l'objectif de classification de documents et le type de documents.

Propriétés des documents-> à priori la nature et les propriétés des document seront très variable suivant

les prestations.-> en général : images binarisés .-> selon le DAS02 Working Group [4], des recherches devraient être consacrés

au traitement des images en niveaux de gris et couleurs.

Référence : [3],[4]

21

Architecture d’un classificateur

(b) Choix des descripteurs

- Image (densités de pixels, …)- Structure (relation entre les objets)- Texte (OCR)

Les information structurelles sont souvent liés à la forme du document (et non au fond).

Référence : [3]

!

22

Architecture d’un classificateur

Représentation des descripteurs

• Vecteur• Arbre• Graphique• Règles• …

-> dépend des caractéristiques que l’on souhaite représenterEx. : caractéristiques structurelles => arbre.

Référence : [3]

23

Architecture d’un classificateur

(b) Représentation des descripteurs[5] recommande l'utilisation de certains types de représentations suivant les

caractéristiques du document..

Référence : [3],[5]

Caractéristiques des documentsExemple de

catégories

Représentation

recommandée

Mise en page fortement restreinte, chaque objet a une position fixe. Formulaire, chèques Liste

Mise en page variable mais avec une structure logique forte, les objets

ont une position légèrement variable mais des relations les lies.

Carte de travail,

lettres

Arbre de

données

Mise en page restreinte avec une structure complexe, les objets sont

organisés de manière hiérarchique ou répétés. La structure de la mise

en page est guidée par des lignes et des espaces.

TableauxArbre local et/ou

global

Structure globale prédéfinie mais l'attribution d'espace pour les

différents objets est flexible.Journaux, articles

Un ensemble de

règles

Eléments standard tels que des axes horizontaux et verticaux Histogrammes Graph ou réseau

24

Arbre MXY

Exemple de représentation

25

Graph

Exemple de représentation

26

Classification

(c) Catégories d'algorithmes de classification:• kNN• Réseaux de neurones• HMM• Arbre de décision

(d) Mécanisme d’apprentissage

• Apprentissage base fixe (échantillons)• Apprentissage dynamique

Référence : [3]

27

Classification

Une méthode simple : la classification par comparaison de mise en page.

1) A partir d’échantillons, on créé des regroupements par similarité « visuelle » de mise en page (suivant la nature et la répartition des zones).

2) On compare le fichier à trier avec les différentes structures et on établi un score de similarité (calcul de distance entre la structure du fichier à trier et les structures des classes).

?

Echantillons Classe

création

comparaison

Fichier à trier Classe

28

Bibliographie

1. Esposito, F.; Malerba, D. & Lisi, F.Machine learning for intelligent processing of printed documentsJournal of Intelligent Information Systems, Springer, 2000, 14, 175-19

2. Yin, P.Skew detection and block classification of printed documentsImage and Vision Computing, Elsevier, 2001, 19, 567-579

3. Chen, N. & Blostein, D.A survey of document image classification: problem statement, classifier architecture and performance evaluationInternational Journal on Document Analysis and Recognition, Springer, 2007, 10, 1-16

29

Bibliographie

4. Smith, E.B., Monn, D., Veeramachaneni, H., Kise, K., Malizia,A., Todoran, L., El-Nasan, A., Ingold, R.: Reports ofthe DAS02 working group. Int. J. Doc. Anal. Recognit. 6(3),211–217 (2004)

5. Watanabe, T.: A guideline for specifying layout knowledge. In: Proceedings of Document Recognition and Retrieval VI (IS&T/SPIE electronic imaging), San Jose, CA, 27 January 1999, SPIE Proceedings Series 3651, 162–172 (1999)