Contribution à la Segmentation et à la ... - Patrice Dargenton

N° d'ordre 94 ISAL 0106
Année 1994 T H E S E présentée devant L'INSTITUT NATIONAL DES SCIENCES APPLIQUEES DE LYON pour obtenir LE GRADE DE DOCTEUR SPECIALITE : INGENIERIE INFORMATIQUE par DARGENTON Patrice Contribution à la Segmentation
et à la Reconnaissance de l'Ecriture Manuscrite Soutenue le 14 décembre 1994 devant la Commission d'Examen
Jury MM. C. BELLISSANT - Président
J.-P. CRETTEZ - Rapporteur
H. EMPTOZ
Y. LECOURTIER - Rapporteur
Y. ROBERT
Mme N. VINCENT REMERCIEMENTS : Je tiens à exprimer toute ma reconnaissance à :
Monsieur C. BELLISSANT, professeur à l'Université de Grenoble, qui me
fait l'honneur de présider ce jury. Monsieur H. EMPTOZ, professeur à l'INSA de Lyon, directeur du LISPI
et de l'équipe Reconnaissance des Formes et Vision, pour m'avoir accueilli
au sein de son équipe dynamique. C'est grâce à son soutien et ses
encouragements que ce travail a vu le jour. Madame N. VINCENT, maître de Conférences, agrégée à l'INSA de Lyon,
pour avoir dirigé ce travail. Je tiens à la remercier pour l'aide précieuse
qu'elle m'a apportée et pour le travail considérable qu'elle a consacré au
suivi et à l'élaboration de la thèse. Monsieur J.-P. CRETTEZ, de l'Ecole Nationale Supérieure Telecom
Paris, pour avoir accepté d'être rapporteur de cette thèse, et pour les
conseils qu'ils m'a donnés. Monsieur Y. LECOURTIER, professeur à l'Université de Rouen, pour
avoir accepté d'être rapporteur de cette thèse, et pour l'intérêt qu'il
porte à mes travaux. Monsieur Y. ROBERT, professeur à l'Ecole Normale Supérieure de Lyon,
pour avoir accepté de faire partie de ce jury. Je tiens également à remercier ici l'ensemble de l'équipe
Reconnaissance des Formes et Vision du LISPI, parmi laquelle j'ai passé ces
quatre années dans un cadre de travail agréable et très enrichissant. Cette
ambiance conviviale et sympathique ainsi que les nombreux échanges d'idées
ont été fructueux et ont contribué à cette synergie qui fait que l'équipe
est plus que la somme individuelle de ses membres. CONTRIBUTION À LA
SEGMENTATION ET À LA RECONNAISSANCE DE L'ECRITURE MANUSCRITE Par
Patrice DARGENTON
INTRODUCTION La reconnaissance de l'écriture manuscrite est le vieux rêve de tous
ceux qui ont eu besoin d'entrer des données dans un ordinateur. Il remonte
à plus d'une trentaine d'années. Aujourd'hui, il existe plusieurs domaines
dans lesquels la reconnaissance de l'écriture manuscrite est attendue avec
impatience, par exemple dans le tri automatique du courrier, le traitement
automatique de dossiers administratifs, des formulaires d'enquêtes, ou
encore l'enregistrement des chèques bancaires.
Ces applications montrent clairement les spécificités du domaine de
la reconnaissance de l'écriture manuscrite par rapport à celui de la
reconnaissance optique des caractères (OCR : Optical Character Recognition)
qui concerne les caractères imprimés ou dactylographiés. Il est nécessaire
de distinguer également la reconnaissance en ligne (on-line) de l'écriture
manuscrite, qui relève plutôt de l'interfaçage entre l'homme et
l'ordinateur (un stylo spécial est connecté à la machine et ne fonctionne
que sur une tablette sensible), de la reconnaissance hors ligne (off-line).
Seule la reconnaissance hors ligne sera considérée dans ce travail.
Quelques systèmes de reconnaissance de l'écriture manuscrite ont été
réalisés et sont opérationnels à ce jour. Cependant, ils sont spécifiques à
un domaine précis et sont encore limités. Par exemple, en ce qui concerne
la poste, la reconnaissance de l'écriture manuscrite, contrairement à celle
des caractères imprimés, se limite au code postal en chiffres ainsi qu'à la
ville en caractères majuscules.
La reconnaissance universelle de l'écriture manuscrite par
l'ordinateur est du domaine de la fiction pour quelques années encore. Tous
les chercheurs sont confrontés à un problème difficile et incontournable,
celui de la segmentation. La segmentation fait partie du processus de
prétraitement et d'extraction de l'information, qui est un préalable à
toute reconnaissance. Nous y avons consacré près de la moitié de notre
travail.
Dans un premier chapitre, une analyse des méthodes et outils de la
reconnaissance des textes manuscrits sera présentée. Ensuite, nos travaux
de recherche, orientés en particulier sur l'utilisation des transformées,
seront exposés dans le cadre d'une étude de la segmentation (chapitre II)
suivant une approche globale.
Cette étude, si elle a ouvert de nouvelles voies de recherche, a
cependant montré la nécessité de compléter les résultats obtenus par un
approfondissement de la reconnaissance au niveau de la lettre. Nous
proposerons donc dans le troisième chapitre une méthode de reconnaissance
basée sur les graphes structurels.
Nous présenterons alors des perspectives que nous envisageons pour la
reconnaissance des mots manuscrits (chapitre IV) avant notre conclusion.
CHAPITRE I
METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES MANUSCRITS
[pic]
CHAPITRE I. METHODES ET OUTILS ACTUELS DE LA RECONNAISSANCE DES TEXTES
MANUSCRITS
Introduction
L'extraction de l'information est la première étape de la
reconnaissance. Elle est réalisée à l'aide de l'extraction des primitives,
qui sont des informations élémentaires. La primitive est l'outil de la
reconnaissance.
Nous traiterons en premier lieu de l'extraction des primitives dans
le cas général, c'est-à-dire quel qu'en soit le niveau (lettre, mot ou
texte). Dans une seconde partie, nous nous concentrerons sur l'exploitation
de ces primitives pour la reconnaissance des mots manuscrits. Nous
présenterons une synthèse des méthodes de reconnaissance que nous avons
élaborée à partir d'une étude bibliographique sur plusieurs systèmes de
reconnaissance.
Dans la troisième partie, nous présenterons les différentes
stratégies qui sont généralement mises en oeuvre pour exploiter les
méthodes exposées précédemment. 1. Les primitives, outils de la reconnaissance
Il n'est pas dans nos intentions de reprendre une étude qui maintes
fois a été faite mais seulement de rappeler certains outils, auxquels nous
ferons souvent appel par la suite. Auparavant, nous préciserons les
objectifs ainsi que la problématique de l'extraction de l'information.
1.1. Les objectifs de l'extraction des primitives Au cours de l'extraction des primitives, plusieurs objectifs, qui
précèdent la reconnaissance, peuvent être envisagés. Les principaux
objectifs que nous définirons dans la perspective de la reconnaissance de
l'écriture manuscrite sont : l'analyse, la segmentation, le paramétrage, la
modélisation, le codage et la classification.
- L'Analyse, dont la définition littérale est "la décomposition d'un
tout en ses parties", consiste généralement en l'extraction d'un ensemble
d'attributs caractéristiques du texte. Concrètement, l'analyse d'un texte
manuscrit consiste à recueillir des informations statistiques telles que la
disposition des lignes d'écriture, leur orientation, leur régularité,
l'espacement des mots et des lettres, la régularité et l'inclinaison des
lettres, l'épaisseur du trait, ainsi que la ligature des lettres à
l'intérieur des mots. L'objectif de l'analyse peut aboutir éventuellement à
l'identification du scripteur, le signifiant [LORETTE 92], plutôt que
directement à la reconnaissance du texte, le signifié.
- La Segmentation désigne la séparation de l'information en ses
éléments constitutifs afin de les identifier isolément. La définition de la
segmentation est donc assez proche du sens littéral du mot analyse. On
parle de sur-segmentation lorsque l'élément constitutif est lui-même
fragmenté, et de sous-segmentation lorsque plusieurs éléments constitutifs
n'ont pas pu être isolés. Dans le cas de la reconnaissance des mots, les
éléments constitutifs sont naturellement les lettres du mot. Il est
nécessaire de distinguer la segmentation logique de la segmentation
physique du document [LORETTE 92]. Les éléments logiques sont les éléments
sémantiques composant le texte, c'est-à-dire les lettres ou les mots, ils
ne correspondent pas toujours aux éléments physiques qui sont liés aux
pixels de l'image. L'extraction des composantes connexes (cf. § 1.4.1.) est
un exemple typique de segmentation physique.
- Le Paramétrage consiste à établir une liste d'attributs représentés
par une variable binaire (attribut présent ou absent) ou multivaluée
(proportionnelle à l'importance de l'attribut), qui ont été détectés et
évalués dans l'image. A la différence de l'analyse, le paramétrage ne
concerne qu'un mot ou qu'une lettre en vue de sa reconnaissance.
- La Modélisation est la construction d'une représentation
approximative de la forme entière. A la différence du paramétrage,
l'objectif est la réduction de l'informati