Thème Proposition d'un modèle de classificateur logique ...Dédicace : Merci Allah (mon dieu) de m'avoir donné la capacité d'écrire et de réfléchir, la force d'y croire, la

N° d’ordre :

N° de série :

République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche

Scientifique

UNIVERSITÉ D’EL-OUED

FACULTÉ DES SCIENCES ET DE TECHNOLOGIE

Mémoire de fin d’étude Présenté pour l’obtention du diplôme de

MASTER ACADEMIQUE

Domaine : Mathématique et Informatique

Filière : Informatique

Spécialité : Systèmes Distribués et Intelligence Artificielle

Présenté par: Melle Ben Guessoum Imane

Thème

Soutenu le 25 juin 2014

Devant le jury composé de :

Mr. Guia Sana MA (B) Univ. El Oued Président

Mr kholladi Nadjoua MA (B) Univ. ElOued Examinateur

Mr. ZAIZ Faouzi MA (B) Univ. ElOued Rapporteur

Année universitaire 2013 – 2014

Proposition d'un modèle de classificateur logique, application

à la reconnaissance du texte arabe imprimé.

Dédicace :

Merci Allah (mon dieu) de m'avoir donné la capacité d'écrire

et de réfléchir, la force d'y croire, la patience d'aller jusqu'au

bout du rêve et le bonheur de lever mes mains vers le ciel et

de dire " Ya Kayoum "

Ma mère, qui a œuvré pour ma réussite, de par son amour,

son soutien, tous les sacrifices consentis et ses précieux

conseils, pour toute son assistance et sa présence dans ma vie,

reçois à travers ce travail aussi modeste soit-il, l'expression

de mes sentiments et de mon éternelle gratitude.

Mon père, qui peut être fier de trouver ici le résultat de

longues années de sacrifices et de privations pour m'aider à

avancer dans la vie. Puisse Dieu faire en sorte que ce travail

porte son fruit ; Merci pour les valeurs nobles, l'éducation et

le soutient permanent venu de toi.

Mon frère fofo qui n’a cessé d'être pour moi des exemples

de persévérance, de courage et de générosité.

Mes professeurs qui doivent voir dans ce travail la fierté

d'un savoir bien acquis.

Je dédie ce travail

Remerciements :

La première personne que je tiens à remercier est mon

encadrant Mr. ZAIZ Faouzi, pour l’orientation, la confiance, la

patience qui m’a constitué un apport considérable sans lequel ce

travail n’aurait pas pu être mené au bon port. Qu’il trouve dans

ce travail un hommage vivant à sa haute personnalité.

Je tiens à exprimer mes sincères remerciements à tous les

professeurs qui m’ont enseignés et qui par leurs compétences j’ai

soutenu dans la poursuite de mes études.

Enfin, je remercie tous ceux qui, de près ou de loin, sont

contribué à la réalisation de ce travail.

I

Table de matières

Table de matières...................................................................................................................... I

Liste des figures...................................................................................................................... IV

Liste des tableaux....................................................................................................................VI

Abréviations, concepts et définitions.................................................................................. VII

Introduction générale ..............................................................................................................1

Chapitre01 :

Table des matières

Introduction ................................................................................................................................ 4

I. Description général de système de reconnaissance............................................................. 4

I.1 Différents aspects de l'OCR ......................................................................................... 6

I.1.2 Reconnaissance globale ou analytique :................................................................... 7

II.1.2 Approches de reconnaissance ............................................................................... 7

I.2 Nature des traits caractéristiques ................................................................................. 8

I.2.1 Caractéristiques topologiques ou métrique .............................................................. 8

I.2.2 Caractéristiques structurelles ................................................................................... 8

I.2.3 Caractéristiques statistiques ..................................................................................... 9

I.2.4 Caractéristiques globales ou locales ........................................................................ 9

I.2.5 Superposition des modèles et corrélation .............................................................. 10

I.3 Problèmes liés à l’OCR : ........................................................................................... 11

I.4 Organisation générale d'un système de reconnaissance ............................................ 12

I.4.1 Phase d’acquisition : .............................................................................................. 13

II Etude de la langue Arabie: ................................................................................................ 14

II.1 Calligraphie et typographie arabe : ............................................................................ 14

II.2 Alphabet arabe : Données graphiques ....................................................................... 17

II.3 Avancées en OCR arabe ............................................................................................ 17

II.3.1 Prétraitements ..................................................................................................... 17

II.3.2 La segmentation ................................................................................................. 18

II.3.3 Extraction des primitives, classification ............................................................. 19

II.3.4 Post-traitement ................................................................................................... 20

Conclusion : .............................................................................................................................. 20

Chapitre02 :

Contenu

Introduction .............................................................................................................................. 22

I. Segmentation de documents ............................................................................................. 22

I.1 Segmentation de la page : .......................................................................................... 23

I.2 Segmentation d’un bloc de texte en lignes : .............................................................. 23

I.3 Segmentation des lignes en mots : ............................................................................. 23

I.4 Segmentation des Mots en caractères ........................................................................ 24

I.5 Structure physique et structure logique : ................................................................... 24

I.6 Stratégies de segmentation ........................................................................................ 25

I.6.1 Segmentation de l’écriture : ................................................................................... 26

I.7 Composition du mot .................................................................................................. 29

II

Table de matières

II. Extraction de caractéristiques du texte : ........................................................................ 30

II.1 Caractéristiques structurelles : ................................................................................... 30

II.2 Caractéristiques statistiques ....................................................................................... 31

II.2.1 Le niveau de caractère : ...................................................................................... 31

II.2.2 Le niveau de bloc de texte : ................................................................................ 33

II.3 Extraction de primitives ............................................................................................. 34

II.3.1 Technique de Zoning .......................................................................................... 34

II.3.2 Moments invariants ............................................................................................ 35

II.3.3 Transformée de Hough ....................................................................................... 35

II.3.4 Profils et contours ............................................................................................... 35

II.3.5 Méthodes de transformation linéaire de l’espace de primitives ......................... 36

Conclusion ................................................................................................................................ 36

Chapitre03 :

Table des matières

Introduction .............................................................................................................................. 38

I. K Plus Proches Voisins ..................................................................................................... 38

I.1 Algorithme de classification par k-PPV [37] [38]: .................................................... 39

I.2 Principe de fonctionnement ....................................................................................... 40

I.3 Domaine application : ................................................................................................ 42

II. Machines à Vecteurs de Support ................................................................................... 42

II.1 Données séparables linéairement : ........................................................................... 43

II.2 Données séparables non linéairement : .................................................................... 43

II.3 Notions de base: Hyperplan, marge et support vecteur ............................................. 43

II.4 Algorithme de classification par SVM: ..................................................................... 45

III. Les avantages et les inconvénients du SVM et KNN: .................................................. 46

Conclusion : .............................................................................................................................. 47

Chapitre04 :

Table des matières

Introduction .............................................................................................................................. 49

I. Méthode proposée : FLC (Fast Logic Classifier) ............................................................. 49

I.1 Cahier des charges ..................................................................................................... 49

I.2 Schéma du classificateur FLC ................................................................................... 50

I.2.1 Apprentissage ......................................................................................................... 52

I.2.2 Classification ............................................................................................................ 52

II. Schéma général du système .............................................................................................. 54

II.1 Acquisition ................................................................................................................. 54

I.2 Prétraitement: ............................................................................................................. 55

II.3 Segmentation ............................................................................................................. 55

II.3.1 Extraction des PAWs ......................................................................................... 55

II.3.2 Segmentation des CNVs ..................................................................................... 56

II.3.3 Segmentation des CNHs ..................................................................................... 57

II.4 Extraction des caractéristiques: ................................................................................. 59

II.4.1 Les moments de Hu : .......................................................................................... 59

III

Table de matières

II.5 Classification ............................................................................................................. 61

II.5.1 Apprentissage ......................................................................................................... 61

II.5.2 Décision / Classification ........................................................................................ 62

A. Classification exacte .................................................................................................. 62

B. Classification approchée ............................................................................................ 63

C. Raisonnement ............................................................................................................ 64

III. Résultats et bilan : ......................................................................................................... 64

III.1 Choix du langage de programmation : ...................................................................... 64

III.2 Interface et Fenêtres : ................................................................................................ 65

III.3 Test et résultat: ........................................................................................................... 66

Conclusion : .............................................................................................................................. 67

Conclusion et perspectives......................................................................................................68

Bibliographie...........................................................................................................................69

IV

Liste des figures

Liste des figures

Chapitre01 :

Table des matières Figure 1.1 : Processus de production et de reconnaissance de documents [38] ....................................4

Figure 1.2 : Etapes de la reconnaissance de documents [38]. ...............................................................5

Figure 1.3 : Différents aspects de l'OCR ..............................................................................................7

Figure 1.4 : Différents systèmes, représentations et approches de reconnaissance ........................... 11

Figure 1.5 : Schéma général d'un système de reconnaissance de caractères ..................................... 13

Figure 1.6 : Effet de certaines opérations de prétraitement [1]. ......................................................... 14

Figure 1.7: Exemple d’écriture arabe montrant la ligne de base [91]................................................. 17

Figure 1.8: Exemple d'histogrammes horizontaux et d'une fausse ligne de texte qui en résulte ........ 19

Figure 1.9: Exemple de chevauchement de PAWs respectivement de droite à gauche entre : «م, ر » et

20 .......................................................................................................................................... .[1] « ف, ر»

Chapitre02 :

Figure 2.1 : Illustration du processus de segmentation ..................................................................... 22 Figure 2.2 : Détection des différentes zones d'une page de document. ............................................. 23

Figure 2.3 : Segmentation de texte en lignes. .................................................................................... 23

Figure 2.4 : Segmentation de Ligne en Mots. ................................................................................... 24

Figure 2.5 : Segmentation de Mot en Caractères. ............................................................................. 24

Figure 2.6 : Hiérarchie des méthodes de segmentation selon R.G.Casey ......................................... 26

Figure 2.7:Segmentation à base du squelette ..................................................................................... 26

Figure 2.8: Extrema du contour supérieur et inférieur sont associés, et reliés par une corde ........... 27

Figure 2.9: Segmentation à partir d’histogrammes de projection selon plusieurs directions ........... 27

Figure 2.10: Segmentation à base de fenêtre glissante : découpage du mot en bandes verticales ..... 28

Figure 2.11: Processus de composition. ............................................................................................ 29

Figure 2.12: caracteristiques structurelles dans un mot ecrit en arabe. ............................................. 30

Figure 2.13: la taille de caractère. ..................................................................................................... 32

Figure 2.14: les tailles d'un mot. ....................................................................................................... 32

Figure 2.15: les caractères gras. ........................................................................................................ 32

Figure 2.16: Le soulignement. .......................................................................................................... 33

Figure 2.17: La position. ................................................................................................................... 34

Figure 2.18: Technique de Zoning ................................................................................................... 35

Figure 2.19: Primitives topologique (a) histogrammes des projections horizontales et verticales ; (b)

les 4 profils : haut, bas, droite et gauche .topologique ......................................................................... 36

V

Liste des figures

Chapitre03 :

Table des matières Figure 3.1 : Apprentissage à base d'exemple de KNN [34]................................................................ 38

Figure 3.2 : Notion de voisinage de la méthode KPPV, exemple avec k=10 .................................... 49

Figure 3.3 : Processus de classification par KNN. ............................................................................. 40

Figure 3.4 : Exemple de classification par KNN. ............................................................................... 41

Figure 3.5 : Classifieurs binaires par SVM. ....................................................................................... 42

Figure 3.6 : Frontière de décision linéaire. ......................................................................................... 43

Figure 3.7: Frontière de décision non linéaire. ................................................................................... 43

Figure 3.8: Exemple d’un hyperplan séparateur [31]. ........................................................................ 44

Figure 3.9: Exemple multitude d’hyperplan [31]. .............................................................................. 44

Figure 3.10: Règle de Classification : y = signe (wx + b) ................................................................. 45

Chapitre04 :

Table des matières Figure 4.1 : Schéma du classificateur FLC......................................................................................... 51

Figure 4.2 : Classificateur FLC .......................................................................................................... 53

Figure 4.3 : Schéma général du système. ........................................................................................... 54

Figure 4.4 : Exemple de prétraitement, a) image brute, b) image près-traitée ................................... 55

Figure 4.5 : Exemple de segmentation de l’image du mot اقرأ" (segmentation des PAWs).. ............. 55

Figure 4.6 : Exemple de caractères de taille L1 et de taille L2. ......................................................... 56

Figure 4.7: Exemple de caractère de composition de segments simple et complexe.. ....................... 56

Figure 4.8: Exemple d’application des règles de segmentation des CNVs ....................................... 57

Figure 4.9: Illustration de types de segments. .................................................................................... 57

Figure 4.10: Illustration de points de Division et de Fusion .............................................................. 58

Figure 4.11: Différents niveaux d'extraction de caractéristiques. ...................................................... 58

Figure 4.12: Le PAW « محمد » après marquage des segments porteur de caractères. ......................... 58

Figure 4.13: Illustration des deux phases utilisées de classification. ................................................. 61

Figure 4.14: Exemple de classification exacte. .................................................................................. 63

Figure 4.15: a) Résultat par classification exacte, b) Résultat par classification approchée. ............. 63

Figure 4.16: Illustration de la fenêtre principale de l'application. ...................................................... 65

Figure 4.17: Illustration du chargement d'une image ........................................................................ 66

VI

Liste des tableaux

Liste des tableaux

Chapitre01 :

Table des matières Tableau 1.1: Les différentes formes de caractères selon la position dans le mot [1]. ...........................1

Tableau 1.1: Les caractères additionnels, (b) et (c) Hamza et Med et les positions qu'elles occupent

avec Alif, Waw et Ya. [1]. ........................................................................................................................4

Tableau 1.1: Les quatre formes des caractères « ain » et « he » en fonction De leur position dans la

chaîne de caractère. ..................................................................................................................................1

Chapitre02 :

Table des matières Tableau 2.1: Les différentes formes de caractères selon la position dans le mot [1]. ........................ 33

Chapitre03 :

Table des matières Tableau 3.1: Les avantages et les inconvénients du SVM et KNN [34]. ........................................... 46

Chapitre04 :

Table des matières Tableau 4.1: Comparaison entre les classificateurs .......................................................................... 50

Tableau 4.2: Résultats de test ......................................................................................................... 67

VII

Liste des codes

Abréviations :

OCR Reconnaissance optique de caractères HTML L'Hypertext Markup Language AOCR Reconnaissance Optique de Caractères Arabic PAW le corps du caractère ACP l’Analyse en Composantes Principales ADL l’Analyse Discriminante Linéaire KPPV K Plus Proches Voisins SVM les Machines à Vecteurs de Support GIF Graphics Interchange Format BMP Bitmap JPEG Joint Photographic Experts Group CNVs des Caractères de Nature Verticale CNHs des Caractères de Natures Horizontale IA Inteligencia Artificial FLC Fast Logic Classifier OVD un Vecteur de Description d’Objets MVD Model Vector Descriptor MDB Model Data Base CI Indexe de la Caractéristique CV Valeur de la Caractéristique CL Class Label XS Taille de vecteur donnée X NE trouver le Nombre d’élection MVS Taille de Vecteur Modèle CE trouver la Classe Elue MV Vecteur Modèle

1

Introduction générale

Les recherches sur la reconnaissance des caractères arabes exposent un domaine qui

s’étend rapidement et indéfiniment évoquées par une place aussi importante dans les deux

dernières décennies. C’est ainsi que la reconnaissance des caractères arabes constitue

aujourd’hui une préoccupation dont la pertinence est incontestée par la communauté de

chercheurs qui ont dévoués leurs efforts à réduire les contraintes et à élargir le royaume de la

reconnaissance des caractères arabes.

Ecrire pour communiquer a été de tous les temps une préoccupation première de l’homme.

L’écrit a été, et restera, l’un des grands fondements des civilisations et le monde par

excellence de conservation et de transmission du savoir. Malgré les avancées d’autres moyens

de communication te que l’audiovisuel, nombreuses sont les applications dont l’existence

commence sur le papier, plus particulièrement dans le bureautique, en publication assistée par

ordinateur (pour faciliter la composition à partir d’une sélection de plusieurs documents), dans

la poste (lecture des adresses et tri des automatique), dans les banques (traitement des

chèques, des factures). Cependant malgré les progrès technologiques, le clavier reste encore

un moyen obligé de communication avec l’ordinateur.

On considère que la reconnaissance est en-ligne si les données sont acquises

dynamiquement pendant l’écriture. Souvent, une tablette graphique et un stylo électronique

sont utilisés par un utilisateur. Par contre, la reconnaissance est hors-ligne lorsque l’image

source est le résultat d’un scanner ou une base d’images.

La phase de classification est l’une des phases très importante dans le processus de

reconnaissance. Pour cela, pas mal de classificateur de natures différentes sont développés.

Ces classificateurs ne prennent pas en charge l’interaction et la communication entre le

système de classification et l’instructeur ou le maître (correction et confirmation des résultats

de classification).

Les classificateurs connus permet d’assigner une étiquette de classe quel que soit les

valeurs du vecteur caractéristique donnée (une décision approchée). Dans la réalité, l’être

humain est capable de donner trois différentes décisions : décision certaine positive (je suis

sur que l’objet est A), décision approchée (l’objet semble à A), décision certaine négative

(l’objet est inconnu).

L’objectif de ce mémoire est de proposer un système de reconnaissance de l’écriture arabe

imprimée hors-ligne. Ce système s’appuie sur une méthode de classification logique dans la

phase de classification.

2

Introduction générale

Dans chapitre un, on trouve un rappel sur quelques notions de bases d'OCR. Ainsi que les

différentes étapes nécessaires pour la réalisation d'un système de reconnaissance de l'écrit,

suivie par une étude de l'OCR et la langue arabe.

Le second chapitre présente un panorama sur une phase cruciale dans le processus de

reconnaissance : la segmentation du texte en général. En décrivons le processus de l'étape de

la détection des objets dans une page, à la segmentation des blocs de texte en lignes puis en

mot puis en caractères. Nous mettons l'accent sur les méthodes utilisées dans ce type de

segmentation.

Chapitre trois va mettre l'accent sur deux méthodes de classification choisies à base de

noyau : Machines à Vecteurs de Support (SVM) et KNN (K-Nearest Neighbor).

Le quatrième chapitre constitue notre contribution, il s'agit d'un algorithme permettant la

classification logique à base des votes, suivie des tests et résultats obtenus.

Enfin, une conclusion pour discuter les résultats obtenus en utilisant le classificateur

logique, et propose quelques perspectives pour ce travail.

Chapitre01 :

Table des matières

Introduction

Description général de système de reconnaissance

Différents aspects de l'OCR

Nature des traits caractéristiques

Problèmes liées à l'OCR

Organisation générale d'un système de reconnaissance

Etude de la langue Arabe

Calligraphie et typographie arabe

Alphabet arabe : Données graphique

Avancées en OCR arabe

Conclusion

4

Chapitre : 01 Reconnaissance de l’écriture

Introduction

Chaque jour, et d’une manière intuitive, les hommes accomplirent des tâches de

discernement des objets de forme connu. Par exemple, nous distinguons facilement, un

triangle d’un cercle, un tigre d’un chat, le visage d’un enfant et celui d’un vieux.

Pour ces tâches simples, l’homme est considéré comme un système relativement parfait

comparé aux systèmes de reconnaissance artificielle.

L'objectif de ce chapitre consiste à introduire et de présenter un état de l'art du domaine

de la reconnaissance de document arabe, -ce qui nous permettra de situer le problème d'OCR

depuis plusieurs années.

I. Description général de système de reconnaissance

On désigne par reconnaissance de formes (ou parfois reconnaissance de motifs) un

ensemble de techniques et méthodes visant à identifier des motifs à partir des données brutes

afin de prendre une décision dépendant de la catégorie attribuée à ce motif. On considère que

c'est une branche de l’intelligence artificielle qui fait largement appel aux techniques

d’apprentissage automatique et aux statistiques.

Mais Le problème ici :

Situer la reconnaissance par rapport à la production de document.

Situer la reconnaissance de caractère par rapport à la reconnaissance de document.

Production et reconnaissance :

La reconnaissance de documents est le processus inverse de la production. [La figure1.1]

Figure 1.1 : Processus de production et de reconnaissance de documents [38].

Forme

logique Forme

physique

Forme

image

Forme

papier

édition formatage restitution impression

Reconnaissance de la

structure logique


structure physique

Saisie

au scanner

5


Etape de prétraitement

Dans le but d’automatiser la reconnaissance de l’écriture, il faut préparer le travail de la

machine. Beaucoup d'efforts ont été consacrés aux étapes préliminaires, qui sont nécessaires à

la reconnaissance, parmi lesquelles on peut noter : la binarisation, le redressement et

la squelettisation …etc.[3]

La reconnaissance de la structure physique

Consiste d'une part à la détection et la classification des différentes zones de l'image en

texte, graphique, table, formule, dessin ou photo et d'autre part à la découpe du texte en

colonnes, paragraphes, lignes, mots et signes [38].

la reconnaissance de la structure logique

Consiste à faire un étiquetage logique aux différents objets de la structure physique et à

réorganiser ces objets conformément au flux de lecture [38].

Figure 1.2 : Etapes de la reconnaissance de documents [38].

Image brute

(Matrice de pixels)

Image épurée

(Limites de caractères)

Structure physique

Structure logique

Filtrage

Redressement

Lissage

Squelettisation

Binarisation

Détection de zones

Classification des zones

Segmentation du texte

Détection de zones

Classification des zones

Segmentation du texte

Prétraitement


structure physique


structure logique

6


Structures de documents

La connaissance de la structure du document à traiter est une nécessité puisque nous

allons l'exploiter durant la phase de reconnaissance. Elle permet de définir une stratégie de

lecture, de segmentation et d'identification des entités de base [31].

Dans un document écrit nous pouvons distinguer deux niveaux de structuration [31]:

La structure physique, qui résulte de la mise en page.

La structure logique, qui précède la mise en page et se rapporte plutôt au continu.

Une autre variante de classification de structure de documents, en les classant par la notion

niveau de complexité [38]:

Structure simple, document contenant des objets simple.

Structure complexe, document contenant des objets complexe.

I.1 Différents aspects de l'OCR

Il n'existe pas de système universel d'OCR qui permet de reconnaître n'importe quel

caractère dans n'importe quelle fonte. Tout dépend du type de données traitées et bien

évidemment de l'application visée. Il existe plusieurs modes de classification des systèmes

OCR parmi lesquels on peut citer:

- Les systèmes qualifiés de « en-ligne » ou « hors-ligne » suivant le mode d'acquisition.

- Les approches globales ou analytiques selon que l'analyse s'opère sur la totalité du mot, ou

par segmentation en caractères.

- Les approches statistiques, structurelles ou stochastiques relatives aux traits caractéristiques

extraits des formes considérées. [4]

Acquisition

Reconnaissance

Approches

Approches En-Ligne / Hors-ligne

Approches Analytique / Globale

Globale/ Analytique

Approches statistiques, structurelles ou stochastiques.

Outils d’acquisition: - scanner => Hors-ligne = Papier Électronique = Images Document - stylo électronique => En-Ligne

= Tracé Dynamique

Figure 1.3 : Différents aspects de l'OCR.

7


I.1.1 Type d'acquisition

Ce sont deux modes différents d'OCR, ayant chacun ses outils propres d'acquisition et

ses algorithmes correspondants de reconnaissance.

La reconnaissance En-Ligne (on-uine)

Ce mode de reconnaissance s'opère en temps réel (pendant l'écriture). Les symboles sont

reconnus au fur et à mesure qu'ils sont écrits à la main.

La reconnaissance hors-ligne (off-line) :

Elle démarre après l'acquisition, elle convient aux documents imprimés et les manuscrits

déjà rédigés.

I.1.2 Reconnaissance globale ou analytique :

L’approche globale :

Considère le mot comme une seule entité et le décrit indépendamment des caractères qui le

constituent. Cette approche présente l’avantage de garder le caractère dans son contexte

avoisinant, ce qui permet une modélisation plus efficace des variations de l’écriture et des

dégradations qu’elle peut subir.

Cependant cette méthode est pénalisante par la taille mémoire, le temps de calcul et la

complexité du traitement qui croient linéairement avec la taille du lexique considéré, d’où

une limitation du vocabulaire [07].

L’approche analytique :

Contrairement à l’approche globale, le mot est segmenté en caractères ou en fragments

morphologiques significatifs inférieurs au caractère appelé graphèmes. La reconnaissance du

mot consiste à reconnaître les entités segmentés puis tendre vers une reconnaissance du mot,

ce qui constitue une tâche délicate pouvant générer différents types d’erreurs [08]. Un

processus de reconnaissance selon cette approche est basé sur une alternance entre deux

phases : la phase de segmentation et la phase d’identification des segments.

II.1.2 Approches de reconnaissance

Durant les dernières décennies, beaucoup de méthodes de segmentation ont été

développées dans le but d'avoir un système de reconnaissance de caractères plus

robuste. Malgré tous les efforts, la situation reste loin d'atteindre les ambitions. En se basant

sur le processus de segmentation, deux approches ont été appliquées [32]:

8


Approche globale

L'approche globale essaye de reconnaître la représentation intégrale des mots de

l'image d'entée [32] et de le décrire indépendamment des caractères qui le constituent.

Cette approche présente l’avantage de garder le caractère dans son contexte avoisinant,

ce qui permet une modélisation plus efficace des variations de l’écriture et des dégradations

qu’elle peut subir [10].

Approche analytique

L'approche analytique au contraire de celle présentée précédemment, isole les

différents caractères des mots [32]. L'idée de base de l'approche analytique est de

segmenter l'image du mot en entrée en caractères ou en fragments morphologiques

significatifs inférieurs au caractère appelés graphèmes. La reconnaissance du mot

consiste à reconnaître les entités segmentées puis tendres vers une reconnaissance du mot, ce

qui constitue une tâche délicate pouvant générer différents types d’erreurs.

I.2 Nature des traits caractéristiques

La nature des caractéristiques varie d'une approche à une autre. Généralement, les

caractéristiques peuvent être classés en cinq groupes principaux [1, 6, 39] :

• trait caractéristiques topologiques,

• trait caractéristiques structurelles,

• trait caractéristiques statistiques,

• trait globales ou locales, et superposition des modèles et corrélation.

I.2.1 Caractéristiques topologiques ou métrique

Ce type de primitives est basé sur des densités de pixels. On peut par exemple projeter des

images de tailles différentes dans une matrice de taille fixe. Les caractéristiques extraites sont

les valeurs des cellules de cette matrice. Dans ce type de primitives, on compte également

les profils et histogrammes. Pour maintenir un vecteur de taille fixe, on divise l’image en

un nombre fixe de bandes horizontales et verticales. Les caractéristiques sont les moyennes

des valeurs sur ces bandes [39].

I.2.2 Caractéristiques structurelles

Elles ressemblent beaucoup aux primitives topologiques. La différence est qu'elles

sont généralement extraites non pas de l'image brute mais à partir du squelette ou du contour

9


de la forme en donnant ses propriétés globales et locales. mais de boucles ou de

cycles dans une représentation filiforme du caractère. Parmi ces caractéristiques on peut

citer [6]:

• Les traits et les anses dans les différentes directions ainsi que leurs tailles.

• Les points terminaux.

• Les points d’intersections.

• Les boucles.

• Le nombre de points diacritiques et leur position par rapport à la ligne de base.

• Les symboles diacritiques et les zigzags (hamza).

Plusieurs autres caractéristiques peuvent être tirées, suivant qu’ils soient extraits d’une

courbe, un trait ou un segment de contour.

I.2.3 Caractéristiques statistiques

Les caractéristiques statistiques décrivent une forme en terme d’un ensemble de

mesures extraites à partir de cette forme. Les caractéristiques utilisées pour la

reconnaissance de textes arabes sont [1]:

• Le zonage consiste à superposer une grille n×m sur l’image du caractère et pour

chacune des régions résultantes, calculer la moyenne ou le pourcentage de points en

niveaux de gris, donnant ainsi un vecteur de taille n×m de caractéristiques.

• caractéristiques de lieu géométrique: en utilisant la méthode Loïc qui est basée sur

le calcul du nombre de segments blancs et de segments noirs le long d’une ligne

verticale traversant la forme, ainsi que leurs longueurs.

• La méthode des moments : les moments d’une forme par rapport à son centre de gravité

sont invariants par rapport à la translation et peuvent être invariants par rapport à la

rotation. Ils sont aussi indépendants de l’échelle.

I.2.4 Caractéristiques globales ou locales

Les primitives globales cherchent à représenter au mieux la forme générale d’un

caractère et sont donc calculées sur des images relativement grandes. Les primitives locales

sont calculées lors d’un parcours des pixels de l’image avec un pas d’analyse qui dépend

de la modélisation, du type de primitive et de la taille de l’image [1,6].

01


I.2.5 Superposition des modèles et corrélation

La méthode de ‘template matching’ appliquée à une image binaire (en niveaux de

gris ou squelettes), consiste à utiliser l’image de la forme comme vecteur de

caractéristiques pour être comparé à un modèle (template) pixel par pixel dans la

phase de reconnaissance, et une mesure de similarité est calculée [1].

Figure 1.4 : Différents systèmes, représentations et approches de reconnaissance [1].

Reconnaissanc

e analytique

Reconnaissanc

e globale

A

P

P

R

O

C

H

E

S

Y

S

T

E

M

E

OCR REPRESENTATION

STATISTIQUE

STRUCTURELLE

SYNTAXIQUE

STOCHASTIQUE

En-ligne Hors-ligne

Mono scripteur

Multiscipteurs

Omniscipteurs

Texte Documen

t

Manuscri

t

Imprimé

Mono scripteur

Multiscipteurs

Omniscipteurs Vocabulair

e

Sans limite Large Réduit

Mono fonte

Multifonte

Omnifonte

00


I.3 Problèmes liés à l’OCR :

La tâche de l’OCR n’est pas aisée, divers problèmes compliquent le processus de

reconnaissance, parmi lesquels on peut citer [07]:

La qualité du document : un document télécopié ou photocopié plusieurs fois est plus

difficile à traiter que la copie originale.

L’impression : un document composé est des meilleures qualités qu’un document

dactylographié qui, à son tour, est plus clair qu’un texte issu d’une imprimante matricielle.

Une imprimante à jet d’encre peut introduire des tâches d’encre et un étalement des

caractères, une imprimante laser peut générer des lignes ou des fonds …

La discrimination de la forme : selon le style de la fonte utilisée, son corps et sa

graisse…, le caractère change de graphisme. Le nombre de formes est d’autant plus important

que le nombre de styles d’écriture est élevé. De plus, plusieurs caractères présentent une forte

ressemblance tels que :

- pour l’arabe : ه et ,صد et م,ر et و

- pour le Latin : U et V, O et 0, S et 5, Z et 2.

Le support de l’information, tel que le papier, joue également sur les performances de

la reconnaissance par sa qualité : son grammage, sa granulation et sa couleur.

L’acquisition : la numérisation en temps réel introduit souvent des distorsions dans

l’image. Dans le cas hors-ligne la qualité du texte numérisé est un compromis entre les

variations de la position (inclinaison, translation, rétrécissement…), la propreté de la vitre du

dispositif de numérisation et sa résolution.

Les variations des dimensions : un « pitch » de 10, 12 ou de 16 … (10, 12 ou 16 cpi

(caractère per inch)). Un pitch de 10 implique des caractères plus grands aussi bien en

largeur qu’en hauteur que ceux d’un pitch de 12.

01


En plus de ces problèmes un système OCR devrait être capable de distinguer entre un

texte et une figure, de reconnaître les caractères ligaturés et d’être indépendant des variations

de l’espace aussi bien inter-mots que de l’interligne.

Les problèmes posés par la reconnaissance optique de l’écriture manuscrite, sont plus

complexes que ceux liés à l’écriture imprimée. Les erreurs de lecture dans le cas du manuscrit

sont dues aux variations infinies de l’écriture de nature aléatoire qui dépendent de facteurs

particuliers du scripteur et des conditions de l’écriture.

I.4 Organisation générale d'un système de reconnaissance

La reconnaissance de l'écrite manuscrite s'intéresse à identifier correctement l'entrée d'une

image du texte écrit sur papier scannée ou photographié [40], en la convertissant en un texte

sous forme d'un fichier informatique en format d'édition telle HTML ou Latex [38].

Typiquement, quel que soit le système de reconnaissance du manuscrit, il fait appel des

phases suivantes [1, 40] :

Acquisition

Prétraitement

Segmentation

Classification

Matrice de

pixels

Limite des

caractères

Apprentissage Reconnaissance

Caractères

reconnus Modèles de

caractère

Post-traitement

Figure 1.5 : Schéma général d'un système de reconnaissance de caractères.

01


I.4.1 Phase d’acquisition :

La phase d’acquisition consiste à capter l’image d’un texte au moyen des capteurs

physiques (scanner, caméra,…) et de la convertir en grandeurs numériques adaptés au

système de traitement, avec un minimum de dégradation possible.

I.4.2 Phase de prétraitement

Le prétraitement consiste à préparer les données issues du capteur à la phase suivante. Il

s’agit essentiellement de réduire le bruit superposé aux données et essayer de ne garder que

l’information significative de la forme représentée. Le bruit peut être dû aux conditions

d’acquisition (éclairage, mise incorrecte du document, …) ou encore à la qualité du document

d’origine. Parmi les opérations de prétraitement généralement utilisées on peut citer :

l’extraction des composantes connexes, le redressement de l’écriture, le lissage, la

normalisation et la squelettisation (figure I.6).

I.3.3 Phase de segmentation :

Dans cette phase les différentes parties logiques d’une image sont extraites. A partir

d’une image acquise il y’a d’abord séparation des blocs de texte et des blocs graphiques, puis

à partir d’un bloc de texte il y’a extraction des lignes, ensuite à partir de ces lignes sont

extraits le mot puis les caractères (ou parties du caractère) .Cette phase va être revue en

détails dans le chapitre 02.

I.3.4 Phase d’analyse ou d’extraction des caractéristiques :

C’est l’une des étapes les plus délicates et les plus importantes en OCR. La

reconnaissance d’un caractère passe d’abord par l’analyse de sa forme et l’extraction de ses

traits caractéristiques (primitives) qui seront exploités pour son identification.

Figure 1.6 : Effet de certaines opérations de prétraitement [1].

04


I.3.5 Phase de classification :

La classification dans un système OCR regroupe deux tâches : l’apprentissage et la

reconnaissance et décision. A cette étape les caractéristiques de l’étape précédente sont

utilisées pour identifier un segment de texte et l’attribuer à un modèle de référence

I.3.6 Phase de post-traitement :

L’objectif du post-traitement est l’amélioration du taux de reconnaissance des mots

(par opposition au taux de reconnaissance du caractère). Cette phase est souvent implémentée

comme un ensemble d’outils relatifs à la fréquence d’apparition des caractères dans une

chaîne, aux lexiques et à d’autres informations contextuelles.

II Etude de la langue Arabe:

Nous présentons les caractéristiques morphologiques de l’écriture arabe. Ensuite nous

exposons les principaux travaux développés en OCR arabe, tout en soulevant les problèmes

majeurs rencontrés dans ce domaine.

II.1 Calligraphie et typographie arabe :

L’arabe est écrit par plus de cent millions de gens, dans plus de vingt pays différents.

L’écriture arabe a été développée à partir d’un type d’Araméen. La langue araméenne

comporte moins de consonants que l’arabe, alors de nouvelles lettres ont été créée en ajoutant

des points aux lettres déjà existantes. D’autres petites marques appelées diacritiques sont

utilisées pour indiquer de courtes voyelles, mais elles ne sont généralement pas utilisées

[11].

De plus l’alphabet arabe comprend d’autres caractères additionnels tels que « ة» et «ال», de

ce fait, certains auteurs considèrent que l’alphabet arabe comprend plutôt 31 lettres que 29.

La considération du symbole « ~» qui s’écrit uniquement sur le support du caractère «ا»,

fait apparaître d’autres graphismes (Tableaux 1.2.c et 1.2.d). L’écriture arabe a ainsi plusieurs

spécificités que nous citons ci-après.

05


L’arabe est une écriture consonantique qui utilise un alphabet de 28 lettres (Tableau 1.1)

La hamza «ء » a une orthographe spéciale qui dépend de règles grammaticales, ce qui

multiplie les formes nécessaires à sa représentation, puisqu’elle peut s’écrire seule ou sur

le support de trois voyelles ( alif, waw et ya) dont elle suit le code (Tableau 1.2.c).

caractère Position

Initiale médiane finale Isolé

Alif ا ـا Beh ب ـب ـبـ بـ Teh ت ـت ـتـ تـ Theh ث ـث ـثـ ثـ Jim ج ـج ـجـ جـ Ha ح ـح ـحـ حـ Kha خ ـخ ـخـ خـ Del د ـد Thel ذ ـذ Ra ر ـر Zey ز ـز Sin س ـس ـسـ سـ Chin ش ـش ـشـ شـ

Sad ص ـص ـصـ صـ

Dhad ض ـض ـضـ ضـ

Tad ط ـط ـطـ طـ

Dha ظ ـظ ـظـ ظـ

Ayn ع ـع ـعـ عـ

Ghayn غ ـغ ـغـ غـ

Fa ف ـف ـفـ فـ

Qaf ق ـق ـقـ قـ

Kaf ك ـك ـكـ كـ

Lam ل ـل ـلـ لـ

Mim م ـم ـمـ مـ

Noun ن ـن ـنـ نـ

He ه ـه ـهـ هـ

Waw و ـو

Ya ي ـي ـيـ يـ

Tableau 1.1: Les différentes formes de caractères selon la position dans le mot [1].

caractère Position


Alif+med آ ـآ Alif+hamza

Teh أ ـأ

إ ـإ Waw+hamza ؤ ـؤ Ya+hamza ئ ـئ ـئـ ئـ

(a)

caractère Position


Ta ة ـة Lamalif ال ـال

(b)

caractère Position


Lamalif+med آل ـآل Lamalif+hamza أل ـأل

إل ـإل

(c)

Tableau 1.2: (a) Les caractères additionnels, (b) et (c)

Hamza et Med et les positions qu'elles occupent avec

Alif, Waw et Ya. [1].

06


De plus l’alphabet arabe comprend d’autres caractères additionnels tels que « ة» et «ال»,

de ce fait, certains auteurs considèrent que l’alphabet arabe comprend plutôt 31 lettres que 29.

La considération du symbole « ~» qui s’écrit uniquement sur le support du caractère «ا», fait

apparaître d’autres graphismes (Tableaux 1.1.a et 1.1.c). L’écriture arabe a ainsi plusieurs

spécificités que nous citons ci-après.

Un trait caractéristique de l’écriture arabe est la présence d’une ligne de base

horizontale dite encore lige de référence ou d’écriture. C’est le lieu des caractères d’une

même chaîne (figure 1.8).

Les caractères arabes s’écrivent de façon cursive, de droite vers la gauche, aussi bien

dans le cas de l’imprimé que du manuscrit.

Les dimensions des caractères (chasse et hauteur) sont variables, même s’il s’agit des

différentes formes d’un caractère (Tableau 1.1).

La forme d’une lettre écrite dépend de son contexte et le dessin du glyphe associé

diffère selon que le caractère apparaît en position initiale, médiane ou isolée dans une

chaîne de caractères (Tableau 1.3).

II.2 Alphabet arabe : Données graphiques

L’alphabet arabe n’a qu’un système d’écriture dans lequel les lettres sont liées ou ne

sont pas liées entre elles selon des règles précises. Il existe différents styles d’écriture, mais

Figure 1.7: Exemple d’écriture arabe montrant la ligne de base [91].

Tableau 1.3 : Les quatre formes des caractères « ain » et « he » en fonction

De leur position dans la chaîne de caractère.

07


dans aucun d’eux il est possible de juxtaposer des lettres totalement isolées les unes des

autres. Il n’y a pas de lettres d’imprimerie en arabe, il n’y a que des caractères typographiques

copiés de l’écriture manuscrite. Le caractère arabe est en effet dessiné non pas en fonction des

contraintes géométriques des procédés de composition pour imprimerie, mais en fonction de

la main et d’une esthétique visuelle héritée de la calligraphie. La fonctionnalité et la lisibilité

sont sacrifiées à l’esthétique calligraphique qui substitue l’élégance à la clarté [1,12].

II.3 Avancées en OCR arabe

La reconnaissance l’écriture arabe (AOCR : Arabic OCR) remonte aux années 70,

depuis, plusieurs solutions ont été proposées. Elles sont aussi variées que celles utilisées

dans le latin. Dès les premiers travaux de reconnaissance de l’écriture arabe, les deux

modes de reconnaissance, statique et dynamique ont été considérés .L’intérêt a été

d’autant porté sur les travaux dans le domaine de l’écriture manuscrite que l’écriture

imprimée. Cependant les travaux en-ligne restent relativement peu nombreux.

II.3.1 Prétraitements

La littérature montre que les opérations de prétraitements connues en traitement

d’images, ne sont pas toutes appropriées à l’Arabe Ce qui nécessite de proposer d’autres

prétraitements qui prennent en compte les caractéristiques particulières de l’écriture arabe

[10].

Le problème lié est que des boucles risquent d’être bouchées ou ouvertes. En plus, les

points diacritiques peuvent être éliminés à la suite de certaines opérations de prétraitements ou

encore confondus avec du bruit. En effet, les prétraitements peuvent altérer surtout la forme

des points diacritiques de manière à les confondre avec du bruit s’ils sont trop amincis. Ils

peuvent également être accolés au corps du caractère associé à cause d’une dégradation ou

d’une normalisation de taille [39].

Une mauvaise squelettisation, peut aussi posée des problèmes particulièrement dans le

cas du manuscrit, par exemple deux points peuvent être considérer comme un seul. Très

souvent, dans les deux cas nous obtenant un segment de droite. Pour ces raisons, dans la

plupart des travaux, les points sont éliminés au début du traitement [39].

08


Les étapes suivantes du traitement sont donc effectuées sur le corps du caractère (ou du

PAW), ainsi le nombre de formes considérées est réduit sensiblement, la phase de

classification devient moins complexe et plus rapide. Pour retrouver l’identité exacte du

caractère une fois son corps identifié, un algorithme d’assemblage corps/points est utilisé

[7,13].

II.3.2 La segmentation

La reconnaissance de caractères améliore l'interaction homme machine. Pour cette

raison, un système de reconnaissance de caractères arabes réussi est extrêmement bénéfique,

et son succès ne peut être accomplit sans qu'il ait surmonté la difficulté de la phase de

segmentation [32].

Pour reconnaître un PAW il faut d’abord l'extraire de la page, donc, nous supposons

qu'une décomposition de la page est préalablement faite, ce qui consiste à retrouver la

structure physique du document en délimitant les différentes parties homogènes (texte,

graphe, photographie …) [38].

Segmentation de texte en lignes

La segmentation de texte en lignes utilise souvent une projection horizontale afin

d'extraire les lignes. Cependant la présence des points/diacritiques complique cette extraction

et conduit parfois à la fusion des paragraphes [41].

Ce problème a lieu quand l’interligne est pris comme un seuil fixe calculé par une simple

moyenne des différents interlignes (figure 1.12). Pour remédier à ce problème, l'utilisation

d'un seuillage adaptatif est la solution. [38].

Figure 1.8: Exemple d'histogrammes horizontaux et d'une fausse ligne de texte qui

en résulte [1].

Fausse ligne de texte

09


Segmentation de ligne en mots et PAWs

La segmentation de ligne en mots et PAWs est réalisée en déterminant les histogrammes

de projection verticale des différentes lignes de texte. Cependant, cette méthode pose des

problèmes quand les PAWs se chevauchent verticalement (figure 1.10) [1]. Dans ce cas,

d’autres techniques sont utilisées telles que la détermination du contour, du squelette, ou

encore des composantes connexes. Le choix de la technique est souvent guidé par la méthode

d’analyse [41].

Segmentation de PAWs en caractères

La segmentation en caractères constitue la tâche la plus délicate de la reconnaissance de

l’écriture arabe. Les difficultés rencontrées à ce niveau sont du même type que celles

affrontées lors de la reconnaissance du latin manuscrit, mais souvent plus complexes à cause

de la diversité des formes du caractère arabe, de la courte liaison qui existe entre les caractères

successifs, de l’allongement des ligatures horizontales et de la présence des ligatures

verticales [1].

II.3.3 Extraction des primitives, classification

Les synthèses des travaux étudiés, montre que les différents types de primitives

(structurelles, géométriques, statistiques, transformations globales, corrélations…) et les

différentes méthodes de classification (statistiques, structurelles, syntaxique…) qui existent

dans la littérature, ont été pratiquement toutes utilisées dans la description de l’écriture arabe.

Souvent, quatre arbres de décision sont élaborés, afin de déterminer l’identité du caractère

selon sa position dans le PAW [13].

Les classifier connexionnistes constituent un nouveau paradigme en reconnaissance de

formes, les travaux utilisant cette approche en AOCR, sont relativement récents. Les modèles

utilisés par la majorité des travaux, appartiennent à la famille des réseaux à couches. Le

principe des réseaux à couches est de transmettre l’information recueillie sur une couche

d’entrée vers une couche de sortie qui exprime la réponse du réseau [13, 14].

Figure 1.9: Exemple de chevauchement de PAWs respectivement de

droite à gauche entre : « ر, م » et « ر, ف » [1].

11


Par ailleurs, peu de travaux ont utilisés des méthodes de classification hybrides. Les

études récentes en OCR recommandent cette approche, toutefois le choix ainsi que nombre de

classifier, qui devraient être complémentaires, dépend de l’application considérée [38].

II.3.4 Post-traitement

Des vérifications contextuelles classiques telles que la recherche dans un dictionnaire,

les probabilités d’occurrence de bigame et de trigramme…, sont appliquées dans les différents

travaux qui prévoient un post-traitement. La méthode du dictionnaire est traditionnellement

simplifiée pour accélérer la recherche et réduire la complexité du calcul : le dictionnaire est

construit à partir de mots réduit à leurs racines, les suffixes et les préfixes sont éliminés.

Cependant des modèles sont élaborés afin de spécifier la relation racine suffixe préfixe [39].

Par ailleurs, le post-traitement, malgré l’amélioration des scores qu’il peut apporter,

n’est pas très utilisé en AOCR, ce qui peut s’expliquer par le manque de dictionnaires de

validation et de statistiques élaborées par rapport au vocabulaire de référence. Or les

statistiques sont relatives à l’application considérée et au vocabulaire de test [39].

Conclusion :

Dans ce chapitre, nous avons présenté certains concepts généraux liés à la

reconnaissance optique des caractères, en précisant les principales méthodes de

reconnaissance.

Nous avons aussi énuméré les principaux problèmes rencontrés par l’OCR. Ensuite nous

avons abordé les différentes étapes intervenant dans la conception d'un système de

reconnaissance de caractères et nous avons précisé qu’il existait différentes issues pour

aborder ce domaine.

Dans la section suivante, nous allons examiner différentes façons d'expliquer

segmentation et l'extraction de caractéristiques.

Chapitre 02:

Table des matières

Introduction

Segmentation de documents

Niveaux segmentation de la page

Structure physique et structure logique

Stratégies de segmentation

Composition du mot

Extraction des caractéristiques du texte

Caractéristiques structurelles

Caractéristiques statistiques

Extraction de primitives

Conclusion

22

Chapitre : 02 Segmentation et extraction des caractéristiques de l’écriture

Introduction

La segmentation est nécessaire pour pouvoir traiter correctement la masse de données

multimédias véhiculées toute la journée à travers le monde. De nombreuses techniques ont été

trouvées, certaines plus performantes que d’autres, mais comme nous allons le voir, le plus

souvent destinées à un domaine particulier.

Dans ce chapitre, nous allons vous expliquer la plus importante étape Avant d'entrer et

expliquer la méthode de classification Qui est la segmentation et extraction de caractéristique.

I. Segmentation de documents

Dans cette section, nous allons voir les différents niveaux de segmentation, les

différentes structures d’un document et les stratégies de segmentation.

Généralement, nous pouvons distingués quatre niveaux de segmentation, comme suit:

Segmentation de la page,

Segmentation de texte en lignes,

Segmentation de lignes en mots,

Segmentation de mots en caractères.

Page

Texte Image

Ligne Ligne

Caractère Caractère

…etc

…

…

Schéma

Mot Mot …

Figure 2.1 : Illustration du processus de segmentation.

22


I.1 Segmentation de la page :

Cette étape permet de localiser dans chaque page, les zones d’information conformément

à leur apparence physique. Elle est associée généralement à l’étiquetage logique qui consiste à

déterminer la nature du media représenté dans chaque zone (texte, graphique,

photographie...etc.).

Une étude détaillée sur les techniques utilisées dans l’analyse de documents se trouve

dans : ([16], [20], [19], [15], [18] et [17]).

I.2 Segmentation d’un bloc de texte en lignes :

Cette étape consiste à séparer les différentes lignes du texte pour en extraire les mots puis

les caractères composants les mots. La plupart des études proposées dans ce domaine

s’appuient sur une décomposition de l’image en composantes connexes [30].

I.3 Segmentation des lignes en mots :

La segmentation en mots est réalisée en déterminant l’histogramme des projections

verticales des lignes pour détecter les espaces entre les mots et pouvoir les séparer. Cependant

cette technique peut ne pas être efficace dans certains cas où les mots se chevauchent (cas par

exemple de l’écriture arabe).

Page

Texte Image …etc Schéma

Figure 2.2 : Détection des différentes zones d'une page de document.

Texte

Ligne Ligne …

Figure 2.3 : Segmentation de texte en lignes.

22


I.4 Segmentation des Mots en caractères

La segmentation des caractères est une opération qui tente de décomposer une image de

séquence de caractères (mot) en sous-images de symboles individuels [44]. C’est l’un des

processus de décision dans un système de reconnaissance optique de caractères. Son but est de

décider si un motif isolé d’une image est correct ou non [42].

I.5 Structure physique et structure logique :

Dans le domaine de l'analyse de documents, nous pouvons identifier deux types

de recherches : l'analyse de composition, et l'interprétation du document.

Ces deux systèmes de traitement permettent de faire la distinction entre une

information physique (correspondant aux objets physiques présents dans le document) et une

information logique (liée à l'interprétation de l'organisation des objets du document) [38].

Le premier niveau de données accessibles au système d'analyse est la structure

physique du document. Il concerne la répartition spatiale de l'information du document.

La structure logique se rapporte au sens de cette organisation. La connaissance de la

structure physique permet de déduire la structure logique si les règles de présentation et

de composition sont claires et connues [43].

Ligne

Mot Mot …

Figure 2.4 : Segmentation de Ligne en Mots.

Caractère Caractère …

Mot

Figure 2.5 : Segmentation de Mot en Caractères.

22


I.6 Stratégies de segmentation

Certains auteurs parlent de segmentation interne et externe, dépendant de si la

segmentation se fait séparément ou simultanément avec la reconnaissance. D’autres auteurs

utilisent les termes straight segmentation et segmentation recognition, pour exprimer le même

sens que précédemment [1].

Selon le point de vue de Casey et L’écoine, la classification des méthodes suivant

l’utilisation ou non de la reconnaissance durant la phase de segmentation n’est pas une bonne

classification [44]. Parce que nous pouvons par exemple utiliser un correcteur d’orthographe

comme post-processeur et dans ce cas il peut suggérer de substituer une lettre sortie par le

classifier par deux lettres, et cela est en fait une utilisation d’une segmentation de la sous

image [45].

Selon lui la distinction entre les méthodes est basée sur comment la segmentation et la

classification interagissent dans tout le processus. Dans l’exemple précédent par exemple la

segmentation intervient en deux temps. Une fois avant la classification et une seconde fois

après la classification.

Après examen des méthodes, il les classifie en trois stratégies de segmentation, plus

d’autres méthodes hybrides à base des trois stratégies de base [13,44]:

Approche analytique explicite, dans laquelle les segments sont identifiés à base de

propriétés de ressemblance de caractères. Elle utilise une technique de découpage de l’image

en composants significatifs elle est appelée dissection. [44,46]

Approche analytique implicite, dans laquelle le système cherche des composants qui

correspondent à son alphabet dans l’image. [49,46]

Approche globale, dans lesquelles le système essaye de reconnaître le mot comme un

tout. Evitant ainsi le besoin de segmentation en caractères. [13, 47,46]

A cela, s'ajoute les approches hybrides combinant dans des proportions différentes de ces

trois approches élémentaires.

22


I.6.1 Segmentation de l’écriture :

Les graphèmes sont des images extraites de l’image à segmenter. Passer d’une seule image

à une séquence de graphèmes pose le problème de la taille de ces éléments. Ils ne doivent pas

être trop petits afin d’être statistiquement significatifs, et pas trop gros afin de ne pas dépasser

la taille d’une lettre. Il est en effet important qu’un graphème donné soit une sous partie d’une

seule lettre : cette condition est nécessaire pour construire un modèle de mot comme étant la

concaténation de modèles de lettres [50].

A. Segmentation à partir du squelette

A partir du squelette, on cherche à repérer certains motifs, pour en déduire les candidats

de points de coupures. La détection de ces motifs introduit des calculs de courbures et

d’angles, qui sont comparées à des seuils ajustés de manière à obtenir le résultat désiré [90].

X.Dupré [46] souligne que cette approche est erronée dans environ 10% des cas. Les

configurations difficiles à segmenter sont celles pour lesquelles les lettres sont souvent

enchevêtrées, comme les ”tt”, ou les lettres `a liaison haute (’b’, ’o’, ’v’, ’w’) avec leur

successeur [50].

Figure 2.6: Hiérarchie des méthodes de segmentation selon R.G.Casey [48].

Analytique Globale

Explicite Implicite Mixte Programmation

dynamique Modèle de

Markov

Fenêtrage Extraction

primitives

Modèle

Markovien

caché

non Markovien

Hybride

22


B. Segmentation à partir du contour

La segmentation à partir du contour consiste à déterminer les meilleurs points candidats

de coupure entre graphèmes, en s’appuyant sur les extrema locaux du contour, qui sont

associées selon un critère de proximité (voir figure 2.8) [50].

Comme la segmentation en graphèmes à partir du contour nécessite de nombreux

ajustements avant de trouver les critères de décision. Cette mise au point par tâtonnements est

le point commun de nombreux traitements d’images liés à la reconnaissance de l’écriture

manuscrite. Faciles à ajuster lorsque la qualité de l’écriture est bonne, ces prétraitements

peuvent avoir des comportements tout `a fait erratiques lorsque l’écriture est de mauvaise

qualité [50].

C. Segmentation à partir des histogrammes

La segmentation en utilisant des histogrammes est méthode proposée par B. Yanikoglu et

P. Sandon [46]. Elle consiste à calculer des histogrammes de projection dans plusieurs

directions proches de la verticale [12]. Les droites choisies sont celles qui interceptent le

Figure 2.7: Segmentation à base du squelette [50].

Figure 2.8: Extrema du contour supérieur et inférieur sont associés, et reliés par

une corde [50].

22


Figure 2.9: Segmentation à partir d’histogrammes de projection selon

plusieurs directions [50].

proches de la verticale.

moins de pixels noirs, avec une contrainte d’espacement régulier dans l’image (voir figure

2.9) [9].

Néanmoins, Cette méthode montre des limites lorsque les lettres sont très proches ou

enchevêtrées.

D. Segmentation basée sur des réservoirs

X. Dupré étend à l’écriture cursive la technique à base de réservoirs initialement

appliquée à la segmentation de chiffres liés. Il souligne que les règles de décision sont plus

difficiles à mettre en place dans le cas des lettres, car ces dernières sont de tailles variables

[50].

E. Segmentation basée sur les fenêtres glissantes

Le principe est d'utiliser une fenêtre mobile de largeur variable en découpant l’image en

bandes verticales. Ce découpage peut être régulier ou non, éventuellement avec recouvrement

partiel des bandes successives (voir figure 2.10). Ce qui permet de trouver des séquences de

points de segmentations potentiels qui seront confirmés ou non par la reconnaissance de

caractères [12].

En variant la taille de la fenêtre et sa position, on obtient plusieurs séquences de points

de segmentation qui seront analysées par le système de reconnaissance. L'analyse du contenu

de la fenêtre peut se faire directement sur les pixels de l'image ou peut s'opérer sur le

regroupement de primitives de bas niveau. Cette méthode nécessite deux étapes [46]:

1. génération d'hypothèse de segmentation (séquences de points de segmentation obtenus

par le fenêtrage),

22


2. choix de la meilleure hypothèse de l'étape de la reconnaissance (validation).

Cette technique présente l’avantage d’être simple, robuste au bruit, et est indépendante de

la connexité. Néanmoins, la largeur de la fenêtre d'observation n'est pas facile à déterminer a

priori et il faut gérer les conflits entre les différentes hypothèses envisagées [6]. De plus, la

séquence générée d'images contient beaucoup de bruit (recouvrement de deux lettres

successives). C’est également vrai dans le cas des lettres superposées verticalement, mais qui

ne se touchent pas nécessairement : une barre de ’t’ avec la lettre suivante, ou les descendants

comme ’ ر ’ ou ’ و ’ en arabe [50].

I.7 Composition du mot

La composition est le processus inverse de la segmentation, durant lequel le mot est

construit à l'aide des différentes étiquettes (labels) de caractères obtenus après la phase de

classification plus un dictionnaire contenant les modèles des mots [47].

Chaque étiquette est comparée avec l'étiquette du mot du dictionnaire tant que la

séquence de ces étiquettes nous répétons l'opération sur l'étiquette suivante sinon le mot

considéré comme connu et l'étiquette en cours de traitement est pris pour la construction d'un

nouvel mot (voir figure 2.11) [52].

Zone des ascendants

Zone des descendants

Zone des corps h

l

Figure 2.10: Segmentation à base de fenêtre glissante : découpage du mot

en bandes verticales [50].

23


II. Extraction de caractéristiques du texte :

Pour extraire les caractéristiques de texte, nous les divisons par deux niveaux. Les

niveaux de caractère et le niveau de bloc de textes.

II.1 Caractéristiques structurelles :

Les caractéristiques structurelles décrivent une forme en termes de sa topologie et sa

géométrie en donnant ses propriétés globales et locales. Parmi ces caractéristiques on peut

citer. Caractéristiques globales structurelles suivantes qui sont en totalité 9 :

Le nombre de hampes dans chaque composante connexe.

Le nombre de jambages dans chaque composante connexe.

Le nombre de boucles dans chaque composante connexe.

Nombre de points en haut et bas pour une composante connexe.

Acquisition, Prétraitement, Segmentation

Extraction des caractéristiques

Mot

Caractères

Vecteurs des caractéristiques

Classification

Vecteur 1 Vecteur 2 Vecteur 3

Labels de caractères

Composition

Label 1 Label 2 Label 3

Modèles

des mots

Dictionnaire

Mot reconnu دـجـم

Figure 2.11: Processus de composition.

23


Les primitives structurelles permettent la description des propriétés géométriques et

topologiques de la forme à analyser. La faible sensibilité au bruit et aux variations des styles

d’écriture rend cette famille de primitives largement utilisée pour la représentation

locale ou globale des formes [24] [26] [27].

Cependant, l’extraction des primitives structurelles n’est pas toujours facile. Elle

peut être faite sur l’image de la forme, le contour ou le squelette, les opérations de la

morphologie mathématique peuvent également être utilisées [28] [29].

Il existe plusieurs primitives structurelles, leur sélection dépend du problème traité

(par exemple, l’écriture considérée : arabe, chinoise…), on peut citer : le nombre de

point finaux, d’embranchement ou d’intersection, la hauteur et la largeurs

des mots, nombre et type des concavités (∪ ,∩ ,⊃ ,⊂), la taille et la position des

boucles, le nombre et la position des points diacritiques, taille, position et type des

lignes (–, |, /, \), le nombre des ascendants et descendants, etc.

Hampers Boucles

Hamza

Deux points en hauts

Deux points liés en bas

Point unique bas

Jambage

Figure 2.12: caracteristiques structurelles dans un mot ecrit en arabe.

.

22


II.2 Caractéristiques statistiques

II.2.1 Le niveau de caractère :

A.. La taille :

Nous pouvons mesurer facilement la taille de caractère en comptant le nombre de pixels

de hauteur du caractère. Dans [10], les auteurs utilisent la profile de projection

pour distinguer la taille.

B. La couleur : nous pouvons aussi déterminer facilement la couleur de caractère. Dans

chaque transparent, le texte a une couleur dominante,

Nomme de taille

Type 1, 2,3 T1 Taille 1

Type 4 T2 Taille 2

Type 5 T3 Taille 3

C. La fonte :

La détermination la fonte de caractères est très difficile car il y a beaucoup de fonte et il y

a les fontes très similaires. Nous devons avoir une liste des fontes échantillons distingués et en

assez petite quantité. Comme la couleur, chaque transparent a une fonte dominant. Les textes

ont la fonte spéciale, ses rôle est spécial aussi.

D. La graisse :

Les caractères gras sont plus larges que ceux autres en même fonte et taille.

Pour déterminer la graisse, nous devons déterminer d’abord la taille et la fonte de texte.

Figure 2.13: la taille de caractère.

.

Figure 2.14: les tailles d'un mot.

.

Tableau 2.1:Table la taille de caractère.

.

22


E. L’italique :

Nous pouvons utiliser la profile de projection pour reconnaître l’italique de caractère. Pour

plusieurs de lettres, comme b, d, h, quand utiliser la profile de projection, elles très grandes au

début ou à la fin. Le compositeur peut utiliser l’italique pour écrire les mots importants, les

annotations.

F. Le soulignement :

Nous pouvons découvrir facilement le soulignement de caractère.

Normalement, le soulignement est la caractéristique d’un mot ou un groupe de mot. Les

compositeurs accentuent les mots par le soulignement.

G. Les caractères majuscules :

Les caractères majuscules ont normalement plusieurs de lisières droites. Nous pouvons

profiter cette caractéristique pour déterminer les caractères. Nous pouvons aussi

considérer les caractères majuscules sont les caractères séparés qui n’ont pas des relations

avec ceux en minuscule. Les compositeurs utilisent les caractères majuscules pour écrire les

titres, les abréviations.

Figure 2.16: Le soulignement.

.

Figure 2.15: les caractères gras.

.

22


II.2.2 Le niveau de bloc de texte :

A. L’alignement :

Un bloc de texte peut être rangé à droit, à gauche ou au milieu. Pour déterminer

l’alignement, nous pouvons comparer le début des lignes dans le bloc ou comparer la distance

de chaque côté de l’image au texte.

B. La position :

Pour connaître que le bloc est rangé au début ou à la fin du page, nous pouvons

comparer la distance de le bord supérieur et le bord inférieur au texte.

C. L’espacement :

C’est facilement pour compter l’espacement entre les mots et celui entre les lignes. Pour

l’espacement entre les lignes, normalement, nous comptons le rapport de l’espacement entre

deux lignes et la taille de caractères.

II.3 Extraction de primitives

L’étape d’extraction de primitives consiste à extraire l’information la plus

discriminante pour la tache de reconnaissance, cette étape est critique et influe

fortement sur la performance du système de reconnaissance. En effet, l’utilisation d’un

classifieur performant ne peut compenser une représentation mal adaptée ou peu

discriminante. La difficulté de cette étape provient du fait que la qualité d’une

représentation ne peut se juger que sur un problème particulier, et qu’il n’existe pas de

Figure 2.17: La position.

.

22


méthodologie pour la sélection d’un ensemble de primitives le plus discriminant pour

un problème donné.

II.3.1 Technique de Zoning

Elle consiste à diviser l’image du mot, le contour ou le squelette en plusieurs

zones et à effectuer une extraction de caractéristiques pour chacune d’elles.L’utilisation

de cette technique permet la localisation de l’extraction de caractéristiques et parfois

l’augmentation du pouvoir discriminant des primitives .[21]

II.3.2 Moments invariants

Les moments invariants proposés par Hu représentent une famille de primitives

statistiques largement utilisée dans la reconnaissance de l’écriture. Ces primitives sont

invariantes par translation, rotation et changement d’échelle. Les moments invariants

donnent une information globale de la distribution des pixels du caractère au tour de son

centre de gravité [22].

II.3.3 Transformée de Hough

La transformée de Hough est une méthode d’extraction de primitive largement

utilisée dans le domaine de la reconnaissance de forme. Elle est capable d’extraire des

lignes droites, des courbes, et n’importe quelle autre forme exprimée sous forme d’une

équation de paramètres [23]. Les deux essentielles étapes de cette méthode sont : – un

mapping des pixels de la forme de l’espace de l’image vers un espace de paramètres

(dépend du caractéristique à extraire). – et une extraction de primitives sur cet espace.

II.3.4 Profils et contours

Le contour et le squelette contiennent toute l’information pertinente du caractère, il

semble donc naturel de coder ces deux représentations et de les utiliser comme

Figure 2.18: Technique de Zoning

.

.

22


primitives. Le contour peut être codé par le codage de Freeman, les courbes de Bezier

ou les courbes de B-Splines [23].

II.3.5 Méthodes de transformation linéaire de l’espace de primitives

Pour augmenter la performance de la classification, un changement de l’espace de

représentation des primitives est souvent appliqué. Les méthodes de transformation

linéaire offrent une réduction de la dimension des primitives, et dans de bonnes

conditions, ils offrent également une augmentation du taux de reconnaissance [23]. Parmi

ces méthodes on cite : l’Analyse en Composantes Principales (ACP) et l’Analyse

Discriminante Linéaire (ADL).

Conclusion

Dans ce chapitre nous avons essayé d’exposer les différentes méthodes utilisées dans la

segmentation du texte. Ces méthodes ont connu beaucoup de progrès ces dernières années.

Des techniques variées influencées par l’évolution dans les domaines tels que la

reconnaissance de la parole et la reconnaissance en ligne des caractères ont émergés.

Dans le chapitre suivant, nous allons présenter quelques méthodes de classification à

base de noyau (Kernel).

Figure 2.19 : Primitives topologique (a) histogrammes des projections horizontales et

verticales ; (b) les 4 profils : haut, bas, droite et gauche .topologique

.

.

Chapitre03 :

Introduction

K Plus Proches Voisins

Algorithme de classification par k-PPV

Principe de fonctionnement

Domaine application

Machines à Vecteurs de Support

Données séparables linéairement et non linéairement

Notions de base: Hyperplan, marge et support vecteur

Algorithme de classification par SVM

Les avantages et les inconvénients du SVM et KNN

Conclusion

83

Chapitre : 03 Méthodes de classification à base de fonction noyau

Introduction

Les méthodes d’apprentissage dites à noyaux (ke rnel-based methods) sont actuellement

très en vogue. Cela n’est pas le fruit du hasard puis qu’elles sont à la convergence de plusieurs

points de vue différents.

Nous décrivons dans la suite deux points de vue qui conduisent aux méthodes à noyaux.

Nous les exposons en ordre d’abstraction croissante. C’est aussi, à peu près, l’ordre dans

lequel les méthodes à noyau x en apprentissage ont été considérées dans les travaux de

recherche

I. K Plus Proches Voisins

Une méthode d’apprentissage non paramétrique, c’est-à-dire elle ne demande pas

une phase d’apprentissage de paramètres. Ce type de classifieur non paramétrique est

mis en œuvre, particulièrement, dans le cas où l’on ne dispose pas de connaissances a priori

sur la distribution de probabilité des classes [51]. les auteurs suggèrent l’utilisation d’un

KPPV comme une première tentative dans un nouveau problème de classification.

Figure III.1: Apprentissage à base d'exemple de KNN [34].

Un KPPV est basé sur l’hypothèse que les points proches dans l’espace de

primitives sont susceptibles d’appartenir à la même classe [51] Son principe de décision

consiste tout simplement à calculer la distance d’une forme inconnue x à tous les

échantillons fournis.

Puis on sélectionne les k plus proches échantillons et on affecte x à la classe

majoritaire parmi ces k échantillons (Figure 3.2). Le choix de l’entier k et de la

métrique de distance jouent un rôle primordial dans la méthode KPPV.

Figure 3.1: Apprentissage à base d'exemple de KNN [34].

83


En pratique, choisir k entre 5 et 10 donne de bons résultats pour la plupart des ensembles

de données de faible dimension [51].La distance euclidienne, la distance de

Mahalanobis et celle de Hamming sont des exemples de métriques largement utilisées.

I.1 Algorithme de classification par k-PPV [37] [38]:

L’objectif de l’algorithme est de classé les exemples non étiquetés sur la base de leur

similarité avec les exemples de la base d’apprentissage

Paramètre : le nombre k de voisins

Contexte : un échantillon de (L) documents classés en C = c1, c2, ..., cn classes.

Entrée : un enregistrement Y

Déterminer les k plus proches exemples de Y en calculant les distances.

Combiner les classes de ces k exemples en une classe c

Sortie : la classe de Y est c(Y)=c.

Figure 3.2: Notion de voisinage de la méthode KPPV, exemple avec k=10

04


I.2 Principe de fonctionnement

Le principe de cet algorithme de classification est très simple. On lui fournit:

• un ensemble de données d’apprentissage D

• une fonction de distance Y

• et un entier k

Documents

(texte, schémas, tableaux …)

Sortie

(Le texte t associé à la classe c)

Transformer texte

(En vecteur t = (x1, x2, ..., xm))

Déterminer

(Les KNN textes du texte t

Selon une métrique de distance)

Combiner

(Les classes de ces k exemples en une

classe c)

Figure 3.3: Processus de classification par KNN.

04


Pour tout nouveau point de test x, pour lequel il doit prendre une décision, l’algorithme

recherche dans D les k points les plus proches de x au sens de la distance Y, et attribue x à la

classe qui est la plus fréquente parmi ces k voisins

Fonctions noyau kernel :

√∑ ( )

Euclidean

∑| |

Manhattan

(∑(| |)

)

⁄

Minkowski

Exemple:

• Dans l’exemple suivant, on a 3 classes et le but est de trouver la valeur de la classe de

l’exemple inconnu x.

• On prend la distance Euclidienne et k=5 voisins

• Des 5 plus proches voisins, 4 appartiennent à ω1 et 1 appartient à ω3, donc x est

affecté à ω1, la classe majoritaire

Figure 3.4: exemple de classification par KNN.

04


I.3 Domaine application :

L’algorithme kNN est utilisé dans de nombreux domaines :

La reconnaissance de formes.

La recherche de nouveaux bio-marqueurs pour le diagnostic.

Algorithmes de compression.

Analyse d’image satellite

Marketing ciblé

II. Machines à Vecteurs de Support

Parmi les méthodes à noyaux, inspirées de la théorie statistique de l’apprentissage de

Vladimir Vapnik, les machines à vecteurs de support (SVM) constituent la famille la plus

connue .Les SVM sont des classifieurs binaires par apprentissage supervisé destinés à

résoudre des problèmes de discrimination ou de régression (prédiction).

Les SVM ont été développé comme un algorithme de classification binaire supervisée.

Il s'avère particulièrement efficace de par le fait qu'il peut traiter des problèmes mettant

en jeu de grands nombres de descripteurs, qu'il assure une solution unique (pas de

problèmes de minimum local comme pour les réseaux de neurones) et il a fourni de bons

résultats sur des problèmes réels [34].

Figure 3.5: classifieurs binaires par SVM.

08


II.1 Données séparables linéairement :

Si tous les points associés aux données peuvent être séparés correctement par une

frontière linéaire (hyperplan).

II.2 Données séparables non linéairement :

Si tous les points associés aux données peuvent être séparés correctement par des

cercles ou frontière non linéaire

Figure 3.6: Frontière de décision linéaire.

.

Figure 3.7: Frontière de décision non linéaire.

.

00


II.3 Notions de base: Hyperplan, marge et support vecteur

Pour deux classes d’exemples donnés, le but de SVM est de trouver un classificateur

qui va séparer les données et maximiser la distance entre ces deux classes. Avec SVM, ce

classificateur est un classificateur linéaire appelé hyperplan. Dans le schéma qui suit, on

détermine un hyperplan qui sépare les deux ensembles de points [31].

Les points les plus proches, qui seuls sont utilisés pour la détermination de l’hyperplan, sont

appelés vecteurs de support.

Figure 3.8: Exemple d’un hyperplan séparateur [31].

Figure 3.9: Exemple multitude d’hyperplan [31].

04


Il est évident qu’il existe une multitude d’hyperplan valide mais la propriété remarquable

des SVM est que cet hyperplan doit être optimal. Nous allons donc en plus chercher parmi les

hyperplans valides, celui qui passe « au milieu » des points des deux classes d’exemples.

Intuitivement, cela revient à chercher l’hyperplan le « plus sûr » [49].

II.4 Algorithme de classification par SVM:

Algorithme du Perceptron (Algorithmes Linéaires Simples)

Données : {(xi,yi)}i=1...n

x dans Rd

(x est un vecteur dans un espace de dimension d) vecteur de traits

y dans {-1, +1} étiquette de la classe (classe 1 (+1) et classe 2 (-1))

Question:

Trouver une frontière linéaire : wx + b (équation de l'hyperplan) telle que la règle

de classification associée donne une probabilité d'erreur minimale

règle de classification (décision):

– y = signe (w x + b) qui signifie :

– si wx + b > 0 alors y = +1

– si wx + b < 0 alors y = -1

Trouver un hyperplan (w,b) dans Rd+1

qui classe aussi bien que possible les

données (points)

Progressivement : un point à la fois, en modifiant les poids si nécessaire

III. Les avantages et les inconvénients du SVM et KNN: Figure 3.10: Règle de Classification : y = signe (wx + b)

04


Classificeur Les Avantages Inconvénients

KNN

Possibilité de faire du rejet (K/2 ≤m

≤K)

Mise en œuvre très simple.

Convergence indépendante de la

distance.

Possibilité de tenir compte des

coûts.

Apprentissage rapide

Méthode facile à comprendre

Complexité de l’algorithme de décision

proportionnel à N.

Performances mal connues quand N

est fini.

Prédiction lente car il faut revoir tous

les exemples à chaque fois.

méthode gourmande en place mémoire

Sensible aux attributs non pertinents et

corrélés

Particulièrement vulnérable au fléau

de la dimensionnalité.

SVM Les SVM possèdent des fondements

mathématiques solides.

Les exemples de test sont comparés

juste avec les supports vecteur et non

pas avec tous les exemples

d’apprentissage.

Décision rapide. La classification

d’un nouvel exemple consiste à voir

le signe de la fonction de décision

f(x).

Classification binaire d’où la nécessité

d’utiliser l’approche un-contre-un.

Grande quantité d’exemples en entrées

implique un calcul matriciel important .

Temps de calcul élevé lors d’une

régularisation des paramètres de la

fonction noyau.

Tableau 3.1 : Les avantages et les inconvénients du SVM et KNN

04


Conclusion :

Dans ce chapitre, nous présenterons les modèles de classification par noyau (KNN et

SVM). Ces méthodes de classification est basée sur la recherche d’un hyperplan qui donné

classification approchée, Il a été démontré dans l'étude précédente qu'il y a beaucoup de

problèmes qui nous empêchent d'obtenir ce que nous voulons. Dans la section suivante, nous

allons proposer une solution pour ces problèmes.

Chapitre04 :

Introduction

Méthode proposée : FLC (Fast Logic Classifier)

Cahier des charges

Schéma du classificateur FLC

Schéma général du système

Acquisition

Prétraitement

Segmentation


Classification

Le système apprentissage

System de Raisonnement

Résultats et bilan

Choix du langage de programmation

Interface et Fenêtres

Test et résultat

Conclusion

49

Chapitre : 04 Méthode proposée FLC (Fast Logic Classifier)

Introduction

Dans le chapitre précédent nous avons présenté deux méthodes de classification. La

première SVM, inspirées de la théorie statistique de l’apprentissage de Vladimir Vapnik

introduite en 1995, et la deuxième KNN (K Nearest Neighbor). Dans ce chapitre nous allons

présenter la méthode de classification que nous proposons, ainsi qu'une conception par

affinement successif du système en donnant son architecture générale, puis nous détaillons en

étudiant séparément chacun de ses composants, ensuite nous allons voir les résultats obtenus,

bilan et comparaison avec d'autres méthodes.

I. Méthode proposée : FLC (Fast Logic Classifier)

L’idée générale de la méthode, repose sur le développe d’un classificateur qui est capable

de simuler au maximum les décisions prise par l’être humain :

1. décision certaine : je suis sûr de ma décision ou l’objet en question est A; et

2. décision incertaine : je ne suis pas sûr de la décision prise ou l’objet en question semble

à A (je pense que c’est A).

I.1 Cahier des charges

Comme nous avons déjà dit, le classificateur à développer doit permettre de répondre aux

différentes exigences de simulation de la classification naturelle de l’être humain. Nous avons

proposés les points suivants :

1) Le classificateur utilise seulement les connecteurs (opérateurs) logique ET/OU.

2) Le classificateur doit contenir un mécanisme de décision pour basculer entre les deux

phases : Apprentissage et Test.

3) Le classificateur doit être capable d’utiliser un Vecteur de Description d’Objets (OVD :

Object Vector Descriptor) qui peut :

A. être de la même taille du vecteur du modèle (OVD=MVD : Model Vector Descriptor).

B. être de taille supérieur du vecteur du modèle (OVD>MVD : Model Vector

Descriptor). Il faut étendre la base des modèles (MDB : Models Data Base).

C. être de taille inférieur du vecteur du modèle (OVD<MVD : Model Vector Descriptor).

Il faut demander une description plus détaillée si nécessaire.

D. être construit des éléments en deux parties : Indexe de la caractéristique (CI :

Characteristic Index), et valeur de la caractéristique (CV : Characteristic Value).

50


E. être avec des valeurs de caractéristiques définit par énumération ou par intervalle.

4) Le classificateur doit contenir une couche d’accélération (Compression, hiérarchie).

5) Le classificateur doit être capable de faire des décisions certaines (exactes) et des décisions

incertaines (approchés).

6) Le système est structuré pour qu’il fonctionne sous trois modes :

A. Apprentissage : le système initialise la base des modèles par des couples vecteur et

étiquette de classe (Xi, Yi).

Xi : représentent le vecteur caractéristique d'un caractère.

Yi : l'étiquette des classes.

B. Test : le système classifie de nouveaux exemples (Xi, Yi). En donnant l’étiquette de

classe pour confirmer la classification.

C. Utilisation : le système classifie de nouveaux exemples (Xi). Sans donner l’étiquette de

classe.

Critère de comparaison entre les classificateurs :

Classificateur

Critère de comparaison

KNN

SVM FLC

Fonction de classification Oui Oui Non

Basculer entre Apprentissage Décision Non Non Oui

Etiquette de la caractéristique Non Non Oui

Caractéristiques par valeur unique Oui Oui Oui

Caractéristiques par énumération Non Non Oui

Caractéristiques par intervalle Non Non Oui

Gestion de compression Non Non Oui

Gestion d’hiérarchie Non Non Oui

OVD > MVD Non Non Oui

OVD < MVD Non Non Oui

Décision certaine Non Non Oui

Décision incertaine Oui Oui Oui

I.2 Schéma du classificateur FLC

Principalement, le classificateur contient six couches, à savoir :

1) Raisonnement : elle contient l’ensemble des règles de gestion de classification.

Tableau 4.1: Comparaison entre les classificateurs

51


2) Apprentissage : elle consiste de faire la gestion de la phase d’apprentissage, et

pratiquement la création de la base des modèles.

3) Classification ou Test: elle consiste à faire la gestion de la phase de test.

4) Vote : permet de faire l’attribution d’une étiquette de classe (CL : Class Label).

5) Calcule : calcule la distance logique entre les vecteurs de test et les vecteurs modèles.

6) Accélération : permet d’accélérer le processus de classification par la gestion de la

base des modèles selon deux points :

A. Compression des descriptions des classes modèles.

B. Gestion de la hiérarchie de définition des objets.

En plus, une couche supplémentaire mais très importante c’est la couche instructeur qui se

compose de trois candidats possible :

1) Personne : présente le cas où l’instructeur est un être humain.

2) Unité IA Interne : présente le cas où l’instructeur est un programme (agent) interne

par rapport à la machine contenant le classificateur.

3) Unité IA Externe : présente le cas où l’instructeur est un programme (agent) externe


La figure 1 illustre la relation entre ces couches.

Instructeur

Personne Unité IA interne Unité IA

externe

Raisonnement

Gestionnaire de

Classification Gestionnaire

d’Apprentissage

Vote

Calcule

X Y X Y

Base des

Modèles

Accélération

Apprentissage

Classification

Figure 4.1 : Schéma du classificateur FLC

52


I.2.1 Apprentissage

La phase d’apprentissage c’est la phase dans laquelle le système initialise et fait la mise à

jour de la base des modèles.

A. Création de la base des modèles

Dans cette phase, le système fait la création ou l’initialisation de la base des modèles. Il

prend en entrée les vecteurs de description et les étiquettes des classes à apprendre, et les

sauvegarde dans la base des modèles.

Durant ça, l’instructeur peut donner des vecteurs de description d’une classe séparés. Le

système convertit à l’aide de la couche accélération ces vecteurs en mode de représentation

par énumération ou en mode de représentation par intervalle pour compresser la définition de

la classe. En plus, parfois l’instructeur peut donner deux ou plusieurs vecteurs de la même

valeur. Dans ce cas, le système sauvegarde une seul copie.

B. Mise à jour de la base des modèles

Dans certain cas, il est nécessaire de faire la mise à jour de la base des modèles par des

nouveaux exemples. Par exemple, dans le cas où le système fait une décision incertaine ou

approchée, ou dans le cas où le système demande d’apprendre de nouvelles caractéristiques.

I.2.2 Classification

Nous pouvons remarquer depuis le schéma présenté ci-dessus que la phase de

classification se compose trois couches, à savoir :

1. Gestionnaire de Classification ;

2. Vote ; et

3. Calcule.

En plus, elle se communique avec la couche raisonnement.

A. Gestionnaire de Classification

Cette couche est liée en haut par la couche raisonnement, et en bas par les deux couches :

vote et calcule. Elle permet de faire la gestion de la classification et la communication avec

l’instructeur pour réapprendre ou confirmer une décision. Le schéma ci-dessous présente les

détails de ce gestionnaire.

53


Classification

Instructeur

Personne Unité IA interne Unité IA externe

Raisonnement

Gestionnaire de Classification

Vote

Calcule

MVS

Non

X Y

Base des

Modèles

Oui 1

Apprendre des nouvelles indexes et

valeurs des caractéristiques. M-à-j

de la base.

1

Demande d’enrichissement de la

description du vecteur descripteur

(plus de caractéristiques).

2

Non

XS<MVS

2

Préparer la matrice de vote

Décision

certaine = CE

CE= trouver la classe élue

NE= trouver le nombre d’élection

XS=NE

Calcule de la

distance entre X et

MV

Oui

Oui

3 Demande de confirmation de

classification.

3

Existe un

instructeur

?

Oui

Non

4

XS>MVS

No

Décision

incertaine = CE

Confirmation de classification.

4

Calcule des votes

Confirmation positive de classification.

Mise à jour de la base des modèles.

5

Confirmation

positive

Confirmation négative de classification.


6

5

Oui

Non

6

Y'

7

Correction du résultat de classification.


7

Figure 4.2 : Classificateur FLC

XS : Taille du Vecteur donnée X.

MVS : Taille du vecteur modèle

CE : trouvé la classe élue

NE : trouver le nombre d’élection

MV : vecteur modèle

54


B. Vote :

Cette couche consiste à préparer la matrice de vote en calculant la distance entre les deux

vecteurs X et MV. En plus, elle permet de trouver la classes élue et le nombre d’élections

pour chacune des classes par l’intermédiaire de la couche de calcule des votes.

C. Calcule :

Cette couche consiste à faire les calculs nécessaires pour les couches supérieurs : calcule de

la distance entre les vecteurs et calcule des votes.

II. Schéma général du système

L’objectif de notre système est la classification par la logique, pour ce faire, il passe par

une succession d’opérations : instructeur, raisonnement et apprentissage et classification,

Mais avant d'aborder le classifieur.

II.1 Acquisition

Dans cette phase, l’image traiter est obtenue à l’aide d’un outil d’acquisition (caméra,

scanner,…etc) et sauvegarder sous un format d’image connue GIF, BMP, JPEG...etc.

Figure 4.3 : Schéma général du système.

Interfaces Acquisition

Image brute

Vecteur caractéristiques

Classification

Résultat final

Prétraitement

Segmentation


55


I.2 Prétraitement:

Cette phase consiste à filtrer l’image brute en suivant cet algorithme :

1. Binairisation de l’image ;

2. Remplacer chaque pixel noir entouré par des pixels blancs par un pixel blanc ;

3. Remplacer chaque pixel blanc entre deux pixels noir, que ce soit verticalement ou

horizontalement, par un pixel noir.

II.3 Segmentation

La phase de segmentation permet d’extraire les différents caractères du mot, pour la réaliser

on passe par trois étapes :

1. Segmentation du mot (Extraction des PAWs) ;

2. Segmentation des caractères de nature verticale (CNVs);

3. Segmentation des caractères de natures horizontale (CNHs).

II.3.1 Extraction des PAWs

Dans la phase de segmentation on utilise la nuance en couleur - noir/blanc - de l’image

épurée pour obtenir les différents segments composants le mot ou le caractère.

La figure 4.5 illustre cette tâche.

Prétraitement

Figure 4.4 : Exemple de prétraitement, a) image brute, b) image près-traitée

Figure 4.5 : Exemple de segmentation de l’image du mot "اقرأ (segmentation des PAWs).

56


Cette technique ne segmente pas le mot complet en caractères, comme le cas du cadre 4,

mais permet d’extraire les lignes continues (syllabes et ponctuations).

II.3.2 Segmentation des CNVs

Dans cette étape, le système utilise les deux facteurs suivant :

1. la différence de taille entre les caractères pour pouvoir extraire les caractères liés de

nature verticale, tels que : ،ك ا، ل .

2. la forme du caractère simple ou complexe.

Actuellement, nous pouvons définir les règles suivantes :

A)- Un point de fusion vertical est considéré comme point de liaison de deux caractères si elle

est entre :

1. deux segments de taille L1 simple ou complexe.

2. un segment de taille L1 simple ou complexe et un segment de taille L2.

3. deux segments de taille L2 où l’un est complexe.

B)- Un segment de taille L2 simple liée à :

1. Un point de fusion vertical à gauche est considéré comme une dent de type 1 ( بـ ).

2. Deux points de fusion vertical est considéré comme une dent de type 2 ( ـبـ ).

3. Un point de fusion vertical à droite est considéré comme une dent de type 3 (ـب).

C)- Un segment de taille L1 simple liée à :

1. Un point de fusion vertical à gauche est considéré comme une dent de type 4 (لـ ).

2. Deux points de fusion vertical est considéré comme une dent de type 5 ( لــ ).

3. Un point de fusion vertical à droite est considéré comme une dent de type 6 ( ـا ).

Figure 4.6 : Exemple de caractères de taille L1 et de taille L2.

Formes de caractère

de taille L2 et de

nature simple

Formes de caractère de

taille L2 et de nature

complexe

Figure 4.7 : Exemple de caractère de composition de segments simple et complexe.

57


Ces dents vont être utilisées par une pile de lecture horizontale. Si on applique ces règles sur

l’image présentée par la figure 5, nous allons obtenir les segments d’image suivants :

II.3.3 Segmentation des CNHs

Pour pouvoir segmenter le reste des mots qui contient des CNHs et extraire les

caractéristiques nous avons utilisé une méthode de suivi (tracking). En définissant deux types

de segments, comme suit:

1. Segment de type 1 : c'est un segment qui commence par un vecteur de pixels ne

possède pas de liaisons avec d'autres segments.

2. Segment de type 2 : c'est un segment qui commence par un vecteur de pixels lié à un

autre segment.

En prenant aussi, que chaque segment est étiqueté comme suit:

S (Seg_Type, Marker, Num_Seq, Num_Seg_Prec)

Tel que:

Seg_Type : le type du segment,

Marker : un marqueur qui va contenir la description et les caractéristiques du segment,

Num_Seq : le numéro de séquence du segment,

Seg_Prec: le numéro du segment qui précède ce segment.

Avec les deux opérations suivantes :

1. Division, notée: D(s) → s1,s2;

2. Fusion, notée: F (s1, s2) → s.

On aura par conséquent les trois types de points suivants :

Figure 4.8: Exemple d’application des règles de segmentation des CNVs.

Segment de type 2 Segment de type 1

Figure 4.9 : Illustration de types de segments.

58


1. Point de Division,

2. Point de Fusion,

3. Point de Division et de Fusion.

Figure 4.10 : Illustration de points de Division et de Fusion.

Ces segments sont sauvegardés dans une liste. Maintenant, il suffit de faire un balayage de

l'image du PAW source suivant la direction de lecture plus un autre balayage de bas en haut et

en respectant les règles suivantes:

1. le premier segment ou le dernier segment détecté est marqué comme segment porteur

de caractère,

2. une opération de division ou de fusion avec un segment marqué comme porteur de

caractère simple (niveau 1, voir figure 11), élimine la marque,

3. une opération de division ou de fusion avec un segment marqué comme porteur de

caractère complexe (niveau 2), lance la division en deux du segment indiqué et fait

évalué l'ensemble de segments en traitement comme des segments de niveau 3, alors

un caractère est obtenus.

Figure 4.11 : Différents niveaux d'extraction de caractéristiques.

Figure 4.12 : Le PAW "محمد" après marquage des segments porteur de caractères.

S (1, 0, -1)

S (2, 2, 1)

S (1, 1, -1)

S (2, 4, 3)

S (1, 3, 1)

Point de Fusion & de division

Point de division

Point de Fusion

Segment

Entre_Segment

Caractère

Niveau 1

Niveau 2

Niveau 3

Emplacement de division

Segments

porteurs de

caractère simple

Segments

porteurs de

caractère de

niveau 2

59


II.4 Extraction des caractéristiques:

Nous avons adopté une façon différente de fonctions d'extraction, une méthode basée sur

intensités des pixels de l'image, ou une fonction.

Moments de l'image sont utiles pour décrire des objets après segmentation. De simples

propriétés de l'image que l'on retrouve par moments d'image incluent zone (ou intensité

totale), son centre de gravité, et des informations sur son orientation.

II.4.1 Les moments de Hu :

Dans le traitement d’images, la vision par ordinateur et les domaines reliés la méthode

des moments est très utile pour l’analyse d’image. Hu a dérivé ces expressions des invariants

algébriques appliquées à la fonction de génération des moments sous une transformation de

rotation. Elles sont constituées des groupes des expressions des moments centralisées non

linéaires. Le résultat est un ensemble des invariants des moments orthogonaux absolues, qui

peuvent être utilisés dans l’identification invariant à l’échelle, position et rotation. Des

propriétés simples de l’image sont obtenues par les moments de l’image incluant la surface,

l’intensité totale et autres informations concernant l’orientation. Ils sont calculés des

moments centralisés normalisés supérieur à l’ordre de trois. Ils sont calculés par les équations

suivantes :

Les moments centraux peuvent être représentés par l'équation suivante

∫ ∫ ( ) ( )

∑∑(

)

(

) ( )( )( )( )

Si f (x, y) est une image numérique, que l'équation précédente devient,

∑∑( ) ( ) ( )

60


Les moments centraux de l'ordre jusqu'à 3 sont:

⁄ ⁄

⁄ ⁄

⁄ ⁄

Les 8 les moments sont :

( )

( ) ( )

( ) ( )

( )( )[( ) ( )

]

( )[ ( ) ( )

]

( )[( ) ( )

] ( )( )

( )( )[( ) ( )

] ( )[ (

) ( )

]

[( ) ( )

] ( )( )( )

61


II.5 Classification

La phase de classification se divise en deux sous phases : Apprentissage et Test ou

Décision. La première consiste à initialiser la base des modèles, autant que la deuxième

consiste à assigner une classe pour chaque nouveau exemple donnée (vecteur caractéristique).

II.5.1 Apprentissage

Cette phase consiste à initialiser ou créer la base des modèles en sauvegardant les

caractéristiques des différents caractères.

Figure 4.13 : Illustration des deux phases utilisées de classification.

Données d'Apprentissage

(Xi,Yi)

Données de Test

(Xi,Yi)

Acquisition

Pré-traitement

Segmentation

Extraction

de caractéristiques

Base des modèles

des caractères

Classification

Acquisition

Pré-traitement

Segmentation

Extraction

de caractéristiques

Label d'une classe

Test Apprentissage

62


II.5.2 Décision / Classification

Elle consiste à utiliser les caractéristiques extraites dans la phase précédente pour attribuer

une classe en de basant sur les données de la base des modèles. Dans la réalité, cette phase se

divise en deux parties :

1. Classification exacte ; et

2. Classification approchée.

A. Classification exacte

Dans ces cas, le système compare le vecteur donnée X avec un vecteur modèle MV et

trouve que tous les caractéristiques de X coïncide avec les caractéristiques de MV. Selon ces

informations le système considère que sa décision est certaine (exacte). Parce que, la taille de

X est égale à la taille de MV (XS=MVS).

Comme exemple, considérons les données suivantes des caractères (ب، هـ، ي) sauvegardées

dans la base des modèles :

Ba_i: C1 63 C2 217 C3 4211 C4 19 C5 -6841 C6 -201 C7 -4954 C8 -38

Ba_i C1 63 C2 217 C3 4209 C4 22 C5 -6478 C6 -196 C7-4482 C8 -49

Ba_i C1 63 C2 277 C3 4186 C4 17 C5 -7013 C6 -204 C7-5376 C8 -30

Ya_i C1 53 C2 314 C3 2218 C4 17 C5 -1210 C6 -9 C7 -3629 C8 -27

Ya_i C1 53 C2 311 C3 2160 C4 C5 1271 C6 -7 C7 -3653 C8 -23

Ya_i C1 53 C2 316 C3 2271 C4 37 C5 -1204 C6 -14 C7 -3189 C8 -30

Ya_i C1 63 C2 234 C3 2910 C4 165 C5 -1913 C6 -3 C7 5189 C8 75

Ha_i C1 40 C2 277 C3 2251 C4 455 C5 3628 C6 91 C7 -4137 C8 -23

Ha_i C1 40 C2 294 C3 2261 C4 413 C5 3213 C6 82 C7 -3628 C8 -29

Ha_i C1 41 C2 296 C3 2254 C4 500 C5 4124 C6 103 C7 -4516 C8 -15

Ensuite, le vecteur caractéristique X suivant :

Ba_i C1 63 C2 277 C3 4186 C4 21 C5 -7013 C6 -204 C7-5376 C8 -30

Nous pouvons remarquer par une simple comparaison des données des vecteurs que les

caractéristiques du vecteur X coïncident exactement avec les caractéristiques du troisième

modèle du caractère Ba.

63


B. Classification approchée

Malheureusement, parfois à cause de la position du papier à scanner ou d’un changement

des caractères, nous pouvons tomber dans le cas où les caractéristiques sont proches mais se

diffèrent en valeur de celle de la base des modèles.

Par exemple, prenons le vecteur X suivant :

Ha_i C1 41 C2 285 C3 2283 C4 435 C5 3720 C6 94 C7 -2903 C8 -44

Pour ce vecteur, il n’est pas possible de faire une classification exacte parce que les valeurs

sont proches mais se diffèrent de celles des modèles du caractère Ha. Pour cela, on essaye de

réaliser un calcule distance à l’aide d’une fonction noyau.

Dans notre travail, nous avons utilisé une distance de Manhattan : qui calcule la somme des

valeurs absolues des différences entre les coordonnées de deux points:

d(x,y)=|xi-yj|.

63 277 4186 21 -7013 -204 -5376 63

Ba Ba Ba Ba Ba Ba Ba Ba

Ya Ya Ha Ya

Figure 4.14 : Exemple de classification exacte.

Vecteur X

Liste des

candidats

41 285 2283 435 3720 94 -2903 -44

Ha

Figure 4.15 : a) Résultat par classification exacte, b) Résultat par classification approchée.

Vecteur X

Liste des

candidats

41 285 2283 435 3720 94 -2903 -44

Ha

Vecteur X

Liste des

candidats Ha Ha Ha Ha Ha Ha Ha

b)

a)

64


Premièrement, le système utilise verticalement une fonction min pour choisir le candidat

le plus proche à chacune des caractéristiques. Ensuite, il utilise horizontalement une fonction

max pour choisir la classe élue.

C. Raisonnement :

Comme nous avons montré dans le schéma du classificateur FLC, un instructeur peut être :

1) Personne : présente le cas où l’instructeur est un être humain.

2) Unité IA Interne : présente le cas où l’instructeur est un programme (agent) interne


3) Unité IA Externe : présente le cas où l’instructeur est un programme (agent) externe

ou une autre machine par rapport à la machine contenant le classificateur.

Par conséquent, le rôle de la couche raisonnement c’est de faire le :

A. Choix d’instructeur adéquat (personne ou unité d’IA Interne ou Unité d’IA Externe);

B. Choix du mode de communication le plus approprié;

1. Parole (microphone et haut-parleur);

2. Message ;

3. Signal (clavier et écran) ;

C. Changement du mode de communication.

III. Résultats et bilan :

Cette section, présentera le choix du langage de programmation, les différentes interfaces

et fenêtres principales du système, les tests et résultats obtenus.

III.1 Choix du langage de programmation :

Dans ce travail, nous avons choisis comme environnement de programmation le langage

JAVA qui possède une richesse et offre une grande simplicité de manipulation d'images, soit

en acquisition ou en génération des fichiers images.

Ce langage possède des avantages très intéressants tel que :

La portabilité des logiciels ;

La réutilisation de certaines classes déjà développées ;

La possibilité d’ajouter à l’environnement de base des composants fournis par

l’environnement lui-même ;

La quasi-totalité de contrôle de windows (boutons, boites de saisies, listes déroulantes,

menus …etc.) qui sont représentés par classes;

65


III.2 Interface et Fenêtres :

On lançant le logiciel nous allons voir premièrement une image d’entrée (splash window)

suivie de la fenêtre principale comme nous montre la figure4.16.

L'application peut être utilisée suivant:

Test : Pour tester et calculer le taux de reconnaissance, et éventuellement utiliser Aya.

Load (chargement): Charger une image de document contenant les exemples de la

classe choisis (l'un des formes primitives de caractère.

Figure4.16:Illustration de la fenêtre principale de l'application.

66


Scan : L’onglet Scan et paramètres du scanner.

III.3 Test et résultat:

Nous avons choisis quelques exemples .Ces exemples sont scannés à l'aide d'un scanner

EPSON CX3400 et avec une résolution entre 150 et 300 dpi, et Mustek ScaneExpress

1248UB et avec une résolution entre 600 et 19200 dpi (H) et 1200 et 19200 dpi (V).

Figure4.17: Illustration du chargement d'une image.

67


Caractère Nombre Exemples Taux de reconnaissance

Caractères

simples

%99.99 91 ا

%99.99 15 ح

%99.99 72 د

%99.99 20 ر

Caractères

ambigües

%99.99 02 ع

%99.99 24 ى

%99.99 34 و

%99.99 02 ح

Caractères

composées

%99.99 27 ج

%99.99 33 ذ

%99.99 27 غ

%99.99 79 ي

%99.99 27 ؤ

Conclusion :

Nous avons présenté dans ce chapitre la description du classificateur logique proposée,

ainsi que les différentes étapes qui peuvent conduire à une conception convenable d’un

système de reconnaissance de caractères arabe imprimés à base d’un classificateur logique.

Tableau 4.2: Résultats de test.

68

Conclusion et perspectives

Jusqu’aujourd’hui, et malgré la multitude et la variété des efforts intensifs réalisés pour

améliorer la qualité de classification des classificateurs, aucun classificateur n’est jugé fiable à

100. Ces classificateurs laissent à coté la possibilité de basculer entre les deux phases :

apprentissage et décision, en plus, elle ne donne qu’une décision incertaine ou approchée. La

qualité de classification d’un système de reconnaissance est influencée par deux phases

principales : la phase d’extraction et la phase de classification.

Dans notre travail, nous avons présenté une méthode de classification logique qui prend en

charge l’interaction classificateur/instructeur et permet de donner des décisions plus poche à

celles prises par l’être humain (certaine et incertaine). Cette interaction permet de maximiser

le taux de reconnaissance à l’aide des opérations : confirmation et correction.

L’intégration de ces mécanismes serait d’un apport considérable, tant au niveau

simplification de la tâche de l’AOCR, qu’aux niveaux validation et portabilité des produits

réalisés.

Par ce travail nous espérons avoir couvert une grande partie concernant le domaine de

recherche en classification, et pouvoir contribuer à l'évolution des recherches.

Perspectives

Le travail que nous avons réalisé durant ce mémoire, constitue une étape et un premier

apport pour l’amélioration de la phase de classification, cependant nous pensons qu'il peut

être amélioré, et étendu par les points suivants:

Ajouter un accélérateur au système pour gagner du temps de calcul, basé sur deux

sous-phases : compression et hiérarchie;

Améliorer le contrôleur logique (raisonneur) et le tester en utilisant des agents ;

Le taux de classification est très influencé par le descripteur utilisé, alors il vaut mieux

intégrer un descripteur au système.

Bibliographie

Bibliographie

[01] S. Haitaamar :" segmentation de texte en caractère pour le Reconnaissance optique de l'écriture

arabe" .Université EL-HADJ LAKHDHAR Batna, Juillet 2007.

[02] P. Smrž et al :" Offline Recognition of Cursive Handwritten Czech text". Université de

Masaryk, Février 1998.

[03] BOUGAMOUZA Fateh. "ontribution à Contribution à la reconnaisa reconnaisa connaissance

automatique de l’écriture sance automatique de l’écriture manuscrite arabe", application sur les

montants manuscrite arabe, application sur les montants littéraux des chèques.

[04] N. Ben Amara."Utilisation des modèles de Markov cachés planaires en reconnaissance de l'écriture

arabe imprimée ". Thèse de doctorat, spécialité Génie Electrique, Université des

sciences, des Techniques et de médecine de Tunis II, 1999.

[05] K. I. Kim, K. Jung, and A. K. Jain. "Text information extraction in images and video : a

survey". Pattern Recognition, 37(5) :977–997, 2003. (Cité page 15.)

[06] E.Lecolinet, O. Barett : "Cursive word recognition : Methods and strategies". InNATO/ASI,

Fundamentals in handwriting recognition, Bonas, France June 21 -july 3, 1993.

[07] B. Al-Badr, S.A. Mahmoud : "Survey and bibliography of Arabic optical text recognition".

Signal processing, vol. 41, pp. 49-77, 1995.

[08] E.Lecolinet, O. Barett : "Cursive word recognition : Methods and strategies ". In NATO/ASI,

Fundamentals in handwriting recognition, Bonas, France June 21 -july 3, 1993.

[09] R.G. Casey, E. Lecolinet : "A survey of methods and strategies in character segmentation ".

IEEE Transactions on pattern analysis and machine intelligence, vol. 18, No. 7, pp.

690-7 ,july 1996.

[10] B. Al-Badr , R.M. Haralick : " Symbol recognition without prior segmentation ". onference

SPIE-EI 1994.

[11] P. Burrow : "Arabic handwriting recognition ". Master of science thesis. School of

Informatics, university of Edinburg, England, 2004.

[12] N. Ben Amara et al :" Utilisation des modèles markoviens en reconnaissance de l'écriture arabe:

Etat de l’art". Ecole Nationale d'Ingénieurs de Monastir - 5019 Monastir – TUNISIE,

LORIA-CNRS, Tunisie, Avril 2001.

Bibliographie

[13] J. Park:"Hierarchical character recognition and it's use in handwritten word/phrase recognition".

Thèse de phd, Université de New York, Novembre 1999.

[14] A. Boutarfa :"Reconnaissance de formes 3D par approche neuronale associant la transformée de

Hough en robotique mobile:Application à la productique". Thèse de doctorat Es-Sciences en

électronique industrielle, Université de Batna, 2006.

[15] A.Belaid . "Analyse de documents: de l’image à la représentation par les normes de codage". Cours

de l’INRIA 1997.

[16] T. Hu, R. Ingold. "A mixed approach toward efficient logical structure recognition from document

image ". Electronic publishing, vol.6 (4), pp. 457-468, December 1993.

[17] S. Mao, T. Kanungo." Empirical performance evaluation of page segmentation algorithms".

Proc. SPIE on document recognition and retrieval, vol. 3967, pp. 303-314, 2000.

[18] Y.Y. Tang, M. Cheriet, J. Liu,J.N. Said,C.Y.Suen ."Document analysis and recognition by

computers ". Handbook of pattern recognition and computer vision Chap 8, Editeurs:

C.H. Chen, I.P. Pau et P.S.P. Wang.

[19] R.M. Haralick. "Document image understanding: geometrical and logical layout ". IEEE. Proc.

International conference on computer vision and pattern recognition, vol. 8, pp. 385-

390, 1994.

[20] K. Etemad, D.Doermann , R.Chellappa ."Page segmentation using decision integration and

wavelet packets". International conference on pattern recognition, 1994.

[21] F. Grandidier, R. Sabourin, Ch. Y. Suen. " Quelques techniques pour l’amélioration du

pouvoir discriminant de primitives discrètes". Conférence Internationale Francophone sur

l’Ecrit et le Document, CIFED 04, juin 2004.

[22] L.Heutte, T.Paquet, J.V.Moreau, Y.Lecourtier, C.Olivier. "A structural/statistical feature

based vector for handwritten character recognition". Pattern Recognition Letters 19, pp. 629

– 641, 1998.

[23] M.Cheriet , N.Kharma , L.C.Liu and C.Y.Suen." Character recognition systems, A guide for

students and practioners". Published by John Wiley & Sons, Inc.,Hoboken,

New Jersey.2007.

[24] J.J.Oliveira , J.de Carvalho, C.Freitas, and R.Sabourin. "Feature sets evaluation for

handwritten word recognition". 8th International Workshop on Frontiers of

Handwriting Recognition, IWFHR’8, pp. 446 – 451, Niagara-on-the-Lake, CA,

August 6-8, 2002.

[25] N.Cristianini, J.Shawe-Taylor ."An Introduction to Support Vector Machines and Other rnel-

based Learning Methods". Cambridge University Press, 2000.

Bibliographie

[26] M.S.Khorsheed. "Off-Line Arabic Character Recognition – A Review". Pattern Analysis &

Applications 5, pp.31 – 45, 2002.

[27] B.Al-Badr, S.A.Mahmoud. "Survey and bibliography of Arabic optical text recognition". Signal

Processing 41, pp. 49-77, 1995.

[28] T. Kanungo and R.M.Haralick. "Character recognition using mathematical morphology",

Proc. of USPS Fourth Advanced Technology Conference,Washington,D.C., pp. 973 –

986, 1990.

[29] E.J.Erlandson, J.M.Trenkle and R.C.Vogt. "Word-level recognition of multifont Arabic text

using a feature-vector matching approach".In Proc.SPIE,Document Recognition III, Luc M.

Vincent; Jonathan J. Hull; Eds., volume 2660, pages 63 – 70, March 1996.

[30] A. Bennasri, A. Zahour, B. Taconet. "Extraction des lignes d’un texte manuscrit arabe".

Vision interface 99, Trois-Rivières, Canada, 19-21 mai 1999.

[31] Mohamadally Hasan,Fomani Boris :" SVM machine a vecteurs de support ou separateur a vaste

marge ".BD Web, ISTY3,Versailles St Quentin, France, janvier 2006.

[31] J.Y.Ramel :"Lecture automatique des partitions musicales ".Mémoire de DEA ingénierie

informatique, LISPI-Equipe de Reconnaissance des Formes et Diagnostics, Université

Lyon 1, France, 1993.

[32] Shubair A et al."Offline Arabic handwritten word segmentation using rotational Invariant segments

features". The international Arab journal of information technology, Vol. 5, No. 2,

April 2008.

[34] P.Mahé :"Noyaux pour graphes Et Support Vector Machines pour Le criblage virtuel de molécules".

Rapport de stage,DEA MVA 2002/2003, Septembre 2003

[35] Bhupendra M.Chaudhari, Abhay B.Nehete, Kantilal P.Rane and Ulhas B. Shinde,

“Efficient Feature Extraction Technique for Signature Recognition”, International Journal of

Advanced Engineering & Application (IJAEA), pp. 64-70, January 2011.

[36] Nan Xu, Li Cheng, Yan Guo, Xiaogang Wu and Jiali Zhao,“A Method for Online

Signature Verification Based on Neural Network”, IEEE Trans. of 3rd International

Conference on Communication Software and Networks (ICCSN), Wuhan,China, pp.

357-360, May 2011.

[37] M. K. Hu. “Visual Pattern Recognition by Moment Invariants”, IRE Trans. of Information

Theory, Vol. 8, pp. 179-187, 1962.

[38] L. Robadey."2(CREM): Une méthode de reconnaissance structurelle de documents complexes basée

sur des patterns bidimensionnels ". Thèse de doctorat soumise à la Faculté des Sciences de

l'Université de Fribourg, Suisse, 2001.

Bibliographie

[39] F.Menasri :" Segmentation d’image Application aux documents anciens".Thèse Docteur de

l’Université Paris Descartes en Informatique, France, Juin 2008.

[40] Al-Rashaideh H." Preprocessing phase for Arabic Word Handwritten Recognition".Institut

d'informatique et autimatisme,Tom 6,N01,2006,cmp.11-19, Russie,February 26,2006.

[41] Jawad H. et al. "Componentbased Segmentation of Words from Handwritten Arabic Text"

.International Journal of Computer Systems Science and Engineering 5:1 2009.

[42] A. Soudi, et al :"Arabic Computational Morphologyknowledge –based and Empirical Methods".

Springer,Volume 38,2007.

[43] J. Y. Ramel :"Lecture automatique des partitions musicales ".Mémoire de DEA ingénierie

informatique, LISPI - Equipe de Reconnaissance des Formes et Diagnostics.

Université Lyon 1, France, 1993.

[44] A. Boukharouba , A. Bennia :"Reconnaissance de Caractères Imprimés Omnifonte ".3rd

International Conference: Sciences of Electronic, Technologies of Information and

Telecommunications, Tunisia, March 27-31, 2005.

[45] A. Belaïd :"Reconnaissance automatique de l'écriture et du document".LORIA-CNRS, Campus

scientifique B.P. 239, 54506 Vandoeuvre-Lès-nancy, France.

[46] M. Côté :"Utilisation d'un modèle d'accès lexical et de concepts perceptifs pour la reconnaissance

d'images de mots cursifs". Thèse de Docteur de l'école Nationale Supérieur de

Télecommunications, France, Juin 1997.

[47] S. Quiniou :"Intégration de connaissances linguistiques pour la reconnaissance de Textes anuscrits

enligne ".Thèse de docteur de l’INSA de Rennes mention Informatique, IMADOC –

IRISA, MATISSE,France, 17 décembre 2007.

[48] M. Côté :"Utilisation d'un modèle d'accès lexical et de concepts perceptifs pour la

Reconnaissance d'images de mots cursifs". Thèse de Docteur de l'école Nationale

Supérieur de Télecommunications,France, Juin 1997.

[49] F. B. Samoud, S.S.Maddouri, K.Hamrouni :"Segmentation de chèques bancaires arabes".3rd

International Conference: Sciences of Electronic, Technologies of Information and

Telecommunications, Tunisia, March 27-31, 2005.

[50] F. Menasri :"Segmentation d’image Application aux documents anciens ".Thèse Docteur de

l’Université Paris Descartes en Informatique, France, Juin 2008.

[51] A. "Methodes a noyaux".chapitre14.chap-14-svm.435-485

[52] S.Carbonnel E.Anquetil ."Modélisation et intégration de connaissances lexicales Pour le post

traitement de l’écriture manuscrite enligne". IRISA, INSA, France, Mars 2009.