Reconnaissance
de Formes
Master Informatique
Option : MID
[Link] 2018-2019
Introduction :
– Le cours introduit les méthodes quantitatives en Intelligence
Artificielle qui sont à la convergence de différents domaine:
– Reconnaissance de formes, analyse de données, apprentissage
automatique, etc…
– Elles sont exploitées en reconnaissance d’images, de la parole,
pour la prévision boursière et les moteurs de recherche etc…
– Le cours décrit les fondements de ces techniques et la
programmation de cas pratique.
2
Introduction :
– Perception physiologique, physique, notions de
capteurs, de représentation, de classification, méthode de
reconnaissance, notions d’apprentissage ; les capteurs en
perception et reconnaissance ; les méthodes de
reconnaissance de formes ; classification, aspect probabilités,
fonctions discriminantes, hiérarchie‐groupement,
reconnaissance syntaxique ;
– Applications de la reconnaissance des formes.
3
Besoins
o Modéliser les données.
o Visualiser des données.
o Trouver des similarités entre données.
o Prévoir.
o Prendre des décisions.
4
Préliminaires
o L'idée de construire des machines capables de simuler
des êtres humains afin de les aider dans certaines tâches,
voire de les remplacer, était antérieure aux ordinateurs.
o Ce qui a permis d'étendre le spectre des tâches à simuler
en ajoutant celles dont l'exécution relève de facultés mentales
comme la perception et le raisonnement.
5
Définitions :
• « La RdF s’intéresse à la conception et à la réalisation de
systèmes (matériels et logiciels) capables de percevoir, et dans
une certaine mesure, d’interpréter des signaux captés dans le
monde physique » J.P. Haton
• Concevoir des systèmes automatiques ou semi‐automatiques
qui reconnaissent les formes qu’on leur présente.
• L’homme est le plus parfait des systèmes de RdF.
• Reconstitution sur « machine » des fonctions typiquement
humaines:
» Perception
» analyse et représentation
» interprétation
• Compréhension automatique (IA)
6
Préliminaires
• Le problème que cherche à résoudre la
reconnaissance des formes :
– Est d'associer une étiquette à une donnée qui
peut se présenter sous forme d'une image ou d'un
signal ou autre.
– Des données différentes peuvent recevoir la
même étiquette, ces données sont les réalisations
ou les exemplaires de la classe identifiée par
l'étiquette.
7
Préliminaires
• Par exemple, le son /a/ prononcé par différents
locuteurs conduit à des signaux différents mais ces
différences ne sont pas significatives du point de vue
de l'identification du son, ces signaux sont des
réalisations de la classe /a/.
• De même, l'écriture manuscrite du caractère A
varie d'un scripteur à l'autre mais le lecteur
identifiera le caractère A pour chacune de ces
réalisations.
8
Préliminaires
• Des méthodes générales ont été
développées en reconnaissance des formes
pour extraire automatiquement des
informations des données sensibles afin de
caractériser les classes de formes
(apprentissage) et d'assigner
automatiquement des données à ces classes
(reconnaissance).
9
Préliminaires
• Parallèlement aux travaux sur les méthodes de
reconnaissance, se développaient le traitement
d'image, la vision par ordinateur, et le traitement de
la parole.
• Ces domaines ont focalisé le problème de la
reconnaissance sur des données spécifiques, mais
par ailleurs ils ont permis de situer la reconnaissance
dans un processus plus vaste d'interprétation
d'image ou de compréhension de la parole
impliquant des niveaux de perception et des
connaissances propres au domaine.
10
Applications de la RdF
11
Applications
12
Applications
13
Applications
Guidage
Automatique
14
Applications
15
Applications
Détection de Défauts 16
Applications
Lecture Automatique de Documents
17
Applications
Lecture Automatique de Documents
18
Applications
19
Applications
20
Applications
21
Détection du visage
22
Applications
Reconnaissance d’expressions
faciles
Colère, fâché, irrité
Dégouté, écœuré
Peur
Triste
Sourire
Surpris
Etc…
23
Détection de la pupille
24
Applications de la RdF
25
Applications de la RdF
26
Applications de la RdF
27
Applications de la RdF
28
Applications de la RdF en Image
29
Le schéma de la reconnaissance
des formes
• Intuitivement, la RdF peut être vue comme un
« système » :
• Entrée x : données brutes obtenues par des
capteurs
» Images, séquences d’images, images 3D ,etc.
» Autres signaux : 1D (ECG), sons, parole, …
• Sortie y : classification de ces données en
fonction de ce qu’elles contiennent
30
Le schéma de la reconnaissance
des formes
31
Le schéma de la reconnaissance
des formes
32
Le schéma de la reconnaissance
des formes
33
Le schéma de la reconnaissance
des formes
• On s'appuie sur le schéma classique d'un processus de reconnaissance de
formes pour décrire les principaux traitements à effectuer et leurs
objectifs.
Buts des étapes du schéma :
– Numérisation : obtenir une représentation des données à traiter qui soit
manipulable en machine.
– Prétraitement : élimination des bruits, normalisation, re‐échantillonnage,
amélioration des contrastes, etc.
– Calcul des représentations : obtenir une représentation des données
compatible avec les outils d'apprentissage et de décision utilisés.
– Apprentissage : à partir d'un ensemble d'exemplaires, construire une
représentation des classes.
– Analyse : assigner une forme inconnue à une classe.
• Post‐traitement : valider les décisions de l'analyse sur la base de
connaissances (du domaine).
34
Le schéma de la reconnaissance
des formes
35
Le schéma de la reconnaissance
des formes
• Dans la pratique, un système de reconnaissance
des formes s'éloigne souvent de ce schéma. Des
traitements en amont sont souvent nécessaires pour
isoler la forme à reconnaître de son contexte, ce qui
en soit est un problème de reconnaissance
(segmentation forme/fond, délimitation d'une forme
dans un ensemble).
• Des traitements ultérieurs sont aussi utiles pour
valider les décisions et éventuellement les remettre
en cause.
36
Le schéma de la reconnaissance
des formes
• Le caractère séquentiel du processus de reconnaissance, tel
qu'il est présenté, n'est pas toujours la meilleure option.
• Ainsi, une erreur dans la segmentation de la forme à
reconnaître augmente forcément le risque d'une mauvaise
reconnaissance. Il est possible d'introduire une boucle dans le
processus, remettant en cause la segmentation après analyse
des résultats de la reconnaissance. Il est aussi possible de
fusionner segmentation et reconnaissance.
• C'est le cas en écriture où la segmentation en lettres d'un mot
cursif(plume) peut être couplée à la reconnaissance des suites
de lettres formant un mot lexicalement valide (même principe
pour la segmentation d'un signal de parole en phonèmes).
37
Les méthodes de la RdF
• Les méthodes de la RdF sont souvent
regroupées en grandes classes identifiées par
statistique, syntaxique, structurelle, hybride
(une combinaison des autres).
• A ces classes correspondent différentes
manières de représenter les exemplaires et les
classes et différentes méthodes pour
l'apprentissage et la reconnaissance.
38
Les méthodes de la RdF
• La première façon d'aborder la simulation d'une
reconnaissance humaine consiste en un traitement
entièrement automatisé où le "maître" à simuler étiquette les
réalisations qui seront utilisées pour l'apprentissage et pour la
validation de la reconnaissance.
• Les méthodes statistiques et syntaxiques répondent à cette
démarche. La difficulté à apprendre automatiquement les
descriptions qui caractérisent les classes a conduit à
demander à l'expert (le maître devient l'expert) d'expliciter
ces descriptions, d'aider à construire la représentation des
classes et les critères de décision.
39
Les méthodes de la RdF
• Les systèmes à base de connaissances tentent de
reproduire les conditions dans lesquelles l'expert
prend sa décision. Il doit donc pouvoir raisonner à
partir de ce qu'il voit (perception) et de ce qu'il sait
(connaissance).
• Chaque nouvelle démarche dans l'évolution de la
RdF ne signifie pas un remplacement des démarches
et méthodes passées mais un enrichissement de
l'ensemble des méthodes dans lequel il faudra
trouver celles qui sont les mieux adaptées au
problème à traité.
40
Décisions
• Le problème de l'assignation d'une donnée à une classe
peut se poser de différentes manières. On distingue le cas où
des données étiquetées par un maître sont disponibles du cas
où aucun moyen pour connaître les classes d'appartenance
des données n'existe.
• Dans ce dernier cas, le traitement automatique doit faire
apparaître des groupements de données. Il faut spécifier les
représentations et une mesure de distance dans l'espace de
représentation qui soient les mieux appropriées pour mettre
ces groupements en évidence.
41
Décisions
• Dans le cas de la simulation d'une reconnaissance humaine, le
maître existe et la décision peut prendre deux formes :
• Discrimination / Caractérisation.
• Pour la discrimination, il s'agit d'assigner une forme inconnue
à une des classes possibles (exemples de la reconnaissance
des caractères, des phonèmes).
• Dans le cas de la caractérisation, il s'agit de décider si une
forme possède les caractéristiques d'une classe ou non
(exemple : décider si un électrocardiogramme appartient à la
classe "normal", rechercher un mot clé dans une séquence
parlé).
42
Décisions
• La validation de ces méthodes se fait par comparaison
des résultats de la reconnaissance automatique aux étiquettes
données par le maître.
• On en tire donc les taux de reconnaissance et les taux
d'erreur. On peut aussi avoir des taux de rejet qui
correspondent à la décision de ne pas classer la forme.
• Le système en évaluant un critère de décision peut
assigner une forme à une classe mais il peut aussi déterminer
avec quelle confiance il effectue cette décision. Si le critère de
décision prend des valeurs très proches pour plusieurs
classes, la confiance dans la décision est faible.
43
Décisions
• Le rejet est très important dans les applications, il va être
modulé en fonction d'impératifs de risque et de cout.
• Par exemple, il est très couteux de faire des erreurs sur la
lecture des adresses postales et encore plus sur les montants
des chèques, on préférera donc augmenter les taux de rejet
quitte à baisser les taux de reconnaissance.
• Par contre, la surveillance médicale nécessite de fort taux
de reconnaissance et surtout de ne pas prendre le risque de
rater un événement critique en confondant des données
anormales avec des données normales. Là encore, il faudra
ajuster les seuils de décisions en fonction du risque et
préférer des alarmes intempestives à des erreurs de non
détection de cas critiques. 44
Décisions
• La décision finale est en général le résultat de plusieurs
décisions intermédiaires qui peuvent être organisées
hiérarchiquement.
• On distingue une hiérarchie d'affinement où l'identité de la
forme à reconnaître sera précisée à mesure que le processus
se déroule.
• Une première étape de segmentation permet de décider
qu'un sous‐ ensemble des données enregistrées constitue une
des formes du domaine, les étapes suivantes consistent à
mesurer et évaluer des caractéristiques de cette forme pour
parcourir une hiérarchie de classes du sommet aux feuilles qui
correspondent aux décisions finales.
45
Prétraitement
• Les données brutes issues des capteurs sont les
représentations initiales des données à partir desquelles des
traitements permettent de construire celles qui seront
utilisées pour la reconnaissance.
• Les données brutes sont bruitées, elles contiennent des
informations parasites, et elles n'explicitent pas les
informations utiles pour la reconnaissance.
• Par exemple, l'information sur la forme des objets à
reconnaître est contenue dans le tableau de pixels résultant
de la numérisation d'une image mais des traitements seront
nécessaires pour, par exemple, séparer la forme du fond et
suivre son contour.
46
Prétraitement
• Les prétraitements sont utiles pour éliminer des bruits qui
peuvent être dus au capteur ou à des interférences avec
d'autres sources de signaux (la parole en milieu sonore,
l'encre du verso qui traverse le papier et dont la trace est
visible sur la feuille du manuscrit, les fonds imagés des
chèques, etc.).
47
Prétraitement
• Le traitement du signal et le traitement d’'image sont les
principales sources pour les méthodes de prétraitement :
filtrage (des bruits hautes fréquences, par exemple),
amélioration des contrastes, extraction de contours ou de
squelettes, modélisation du signal temporel, extraction des
primitives, etc.
•
48
Prétraitement
• Les prétraitements et l'apprentissage ont des buts
communs qui consistent à éliminer les informations parasites
et à conserver les informations pertinentes pour la
reconnaissance. La limite entre prétraitement et
apprentissage relève des possibilités des méthodes
d'apprentissage utilisées.
49
Représentation
• Le système de reconnaissance de formes doit posséder des
classes et des représentations des formes à classer.
• Les types de représentation sont déterminés par les
méthodes utilisées. Les contenues des représentations sont
déterminées par les buts de la reconnaissance.
• Certains types de représentation sont mieux appropriés à
exprimer certains contenus. Par exemple, une variabilité intra‐
classe qui se présente comme une répartition aléatoire des
caractéristiques de la forme autour de valeurs fortement
probables, sera bien représentée par des modèles
statistiques. Par contre, les structures (les relations entre
composantes d'une forme) peuvent plus facilement
s'exprimer par des représentations structurelles. 50
Représentation
• On appelle caractéristique(ou descripteur) une
information qui peut être mesurée sur la donnée à
reconnaître. Par exemple : l'amplitude moyenne d'un
signal sur une fenêtre temporelle, l'énergie dans une
bande de fréquence, le rapport hauteur sur largeur
d'un caractère manuscrit, le niveau de gris moyen
d'une zone d'image etc.
• On appelle primitive une composante élémentaire
d'une forme, les primitives ne sont pas
décomposables. Par exemple : un segment de droite,
une boucle ...
51
Combinaison de Classifieurs
Cas facile Cas difficile
52
Combinaison de Classifieurs
• Pourquoi Combiner des Classifieurs?
• Constats:
– Il n’existe pas de « meilleur » classifieur capable de traiter (apprendre)
n’importe quelle distribution des données d’apprentissage.
– Aucun Classifieur ne peut discriminer suffisamment correctement un
ensemble important de classes.
– Le « réglage » d’un Classifieur est un problème extrêmement difficile
(on procède souvent par essai/erreur).
– Importance des choix initiaux…
• Intérêts de la combinaison de Classifieurs:
– Distribuer les caractéristiques sur des classifieurs adaptés.
– Exploiter la complémentarité entre classifieurs.
– Prendre en compte les performances de chacun des classifieurs.
– Réduire l’importance des choix initiaux…
– Diviser pour mieux régner… 53
Combinaison de Classifieurs
• Comment Combiner des Classifieurs?
• Disposant d’un ensemble de L classifieurs, comment les
agencer pour fiabiliser une prise de décision?
• Solution?
• Dépend de la façon dont on veut faire interagir les classifieurs
• Indépendamment les uns des autres (vote?)
• Elimination d’hypothèses (décisions dépendantes)
• Coopération de classifieurs (chacun résout un problème…)
•…
• Architectures
• – Séquentielle ou série
• – Parallèle
• – Hybride (mixte séquentielle et parallèle, avec bouclage, avec
interaction,…) 54
Combinaison de Classifieurs
• Combinaison Séquentielle (ou Série)
• Organisation en niveaux successifs de décision permettant de
réduire progressivement le nombre de classes possibles.
• A chaque niveau: un seul classifieur prend en compte la
réponse fournie par le classifieur placé en amont pour:
– Traiter les rejets
– Confirmer la décision obtenue à l’étage précédent
55
Combinaison de Classifieurs
• Combinaison Parallèle
• Les classifieurs opèrent indépendamment les uns des
autres puis on fusionne leurs réponses respectives.
• Recherche d’un consensus entre les classifieurs pour
aboutir à une décision unique.
56
Combinaison de Classifieurs
• Combinaison Hybride : Le beurre… et l’argent
du beurre…
• Combinaison des avantages des architectures
séquentielles et parallèles.
– Réduction de l’ensemble des classes possibles
– Recherche d’un consensus entre les classifieurs
57
Merci
58
