Modélisation et Reconnaissance des formes
Introduction
Marie-Odile Berger
http://members.loria.fr/moberger
September 18, 2018
M.-O. Berger Intro MRF September 18, 2018 1 / 45
Objectifs du cours
I cadre général: la reconnaissance et l’identification des formes
I forme= image nuage de points, signal de parole, des capteurs...
I Quelque problèmes:
I reconnaitre la présence d’un objet/des objets dans une image (mais pas
seulement)
I localiser ces objets dans l’image
I connaitre précisément sa position géométrique (ex: robotique, conduite
automatisée...)
I tenir compte de l’incertain sur l’identificaton pour effectuer une action
But
modéliser des formes, les reconnaitre, les localiser...
en tenant compte de l’incertain, des connaissances a priori, des données
(exemples) disponibles
M.-O. Berger Intro MRF September 18, 2018 2 / 45
Concepts de base de la RF
Objectif: Doter les machines des capacités de l’homme à reconnaı̂tre des
caractères, des objets, des sons, des signes des signaux temporels...
Deux grands objets d’étude:
I Étudier de quelle manière l’être humain effectue cette reconnaissance
(touche à des domaines comme psychologie, physiologie, biologie)
I Viser le développement de théories et de techniques permettant
d’effectuer certaines tâches de reconnaissance (domaines:
informatique, statistique, mathématiques)
M.-O. Berger Intro MRF September 18, 2018 3 / 45
Qu’est ce qu’une forme?
I Exemples de formes: empreintes digitales, écriture manuscrite,
visages, parole, images, des objets temporels...
I La RF consiste à étudier comment les machines peuvent
I apprendre à extraire des structures d’intérêt,
I prendre des décisions en observant un environnement
I reconnaı̂tre, décrire ou classifier des formes
M.-O. Berger Intro MRF September 18, 2018 4 / 45
Historique
Au départ, la RF est surtout du traitement du signal
I test de la présence d’un signal
I identification de sources multiples
I traitement de la parole
et progressivement, on a envisagé des tâches plus complexes...
M.-O. Berger Intro MRF September 18, 2018 5 / 45
L’humain fait beaucoup de choses:
reconnaı̂tre
I des visages
I des sons
I des formes
et ceci indépendamment
I du point de vue sous lesquels on les observe
I des conditions d’observation
I de leur variabilité
Mais le domaine est en forte progression depuis 2012.
M.-O. Berger Intro MRF September 18, 2018 6 / 45
Quelques exemples en images
M.-O. Berger Intro MRF September 18, 2018 7 / 45
exemple: segmentation
Figure: segnet: A Deep Convolutional Encoder-Decoder Architecture for Image
Segmentation [Badrinarayanan 2016]
demo
M.-O. Berger Intro MRF September 18, 2018 8 / 45
Détection précise ou approximative?
Détéction de piétons [Andriluka CVPR 2009]: on peut se contenter de
détecter des boites contenant des piétons
M.-O. Berger Intro MRF September 18, 2018 9 / 45
Détection précise ou approximative?
Où avoir une estimation précise de la position du corps
M.-O. Berger Intro MRF September 18, 2018 10 / 45
Joint reconstruction and semantic segmentation [Hane
CVPR 2013]
M.-O. Berger Intro MRF September 18, 2018 11 / 45
Quelques exemples classiques de RF
Problème Entrée Sortie
Analyse de documents image du document mots, graphique
Filtres internet Emails classification en SPAM
Analyse du langage naturel texte informations sémantiques
Reconnaissance de la parole spectrogramme mots
Recherche multimédia son, images, vidéo Ident. d’évènements
Reconnaissance biometrique empreintes digitales, iris authentification
Identifications de défauts images pièces au rebut
Surveillance médicale signaux (ECG, temp) émission d’alertes
Identification et suivi vidéo trajectoire de la cible
M.-O. Berger Intro MRF September 18, 2018 12 / 45
Les controverses de la RF (1)
cognitivistes contre comportementalistes
I faut-il s’inspirer de nos connaissances sur la perception humaine pour
concevoir des systèmes d’inspiration cybernétique.
I le comportementaliste ne cherche pas à analyser le concept mais
essaie de collecter un maximum de prototypes différents pour en
extraire des régularités et des moyens de classification
M.-O. Berger Intro MRF September 18, 2018 13 / 45
Les controverses de la RF (2)
Apprentissage / représentation
Étant donné un ensemble de formes caractérisant une classe, doit on
I utiliser une représentation sophistiquée des formes (ce qui nécessite
souvent des connaissances explicites sur le domaine)
I travailler directement sur les données sans a priori (tout repose sur le
processus de classification)
M.-O. Berger Intro MRF September 18, 2018 14 / 45
Les modèles de la RF
I RF statistique
I RF syntaxique ou structurelle
I Systèmes à base de connaissances
Dans ce cours, on parlera surtout de RF statistique. D’autres modules du
master envisagent les autres aspects.
La RF est à la confluence de plusieurs domaines: maths, stats, probas,
apprentissage, biologie, informatique, parallélisme
M.-O. Berger Intro MRF September 18, 2018 15 / 45
Un système de reconnaissance des formes
l’approche conventionnelle:
I Les caractéristiques des données sont extraites (de manière statique)
indépendamment du processus de classification
M.-O. Berger Intro MRF September 18, 2018 16 / 45
Un système de reconnaissance des formes
l’approche par réseaux convolutionnels (CNN): extraction des
caractéristiques et entrainement du classifieur ne sont pas dissociées:
M.-O. Berger Intro MRF September 18, 2018 17 / 45
Quelques exemples de CNNs
I Reconnaissance d’objet Demo Berkeley
M.-O. Berger Intro MRF September 18, 2018 18 / 45
conventionnel/CNN
I Les CNN etle Deep Learning font l’objet d’un module dans AVR (E.
Vincent/J. Fix) Voir aussi les intervention de Yann Le Cun au collège
de France.
I Questions communes à tous les systèmes: on cherche une fonction de
classification minimisant une métrique qualifiant la distance entre les
resultats obtenus et les résultats souhaités
I Quelle distance utiliser? comment calculer le minimum? La solution est
elle sensible à la présence de données aberrantes?
I Tout ne peut se résoudre par les CNN qui demandent beaucoup de
données d’apprentissage!
M.-O. Berger Intro MRF September 18, 2018 19 / 45
Les problèmes de la RF statistique
I Collecter des données
I Représenter les données d’entrée (souvent de taille importante): →
Extraire les caractéristiques de ces données pour réduire la dimension
du problème
I Modéliser les classe d’objets
I Choisir une procédure adéquate pour classifier un objet d’après son
vecteur de caractéristiques. Évaluer la qualité du classifieur
M.-O. Berger Intro MRF September 18, 2018 20 / 45
Collecter les données
I But :Amasser des données représentatives d’un phénomène et
également des données permettant ultérieurement de tester le
système de RF
I Problème: Comment savoir que l’on a assez de données ? (Sont elles
bien représentatives du phénomène?)
I A ce propos, consulter l’article 2018 de Sciences et Avenir:
Intelligence artificielle : la reconnaissance faciale est-elle misogyne et
raciste ?
M.-O. Berger Intro MRF September 18, 2018 21 / 45
Représenter les données
Objectifs: réduire la taille du problème en décrivant la donnée par
quelques caractéristiques discriminantes (valeurs semblables pour des
motifs semblables, valeurs différentes pour des motifs différents)
I dépendance du domaine et des connaissances a priori sur le domaine
(formes paramétrables)
I invariance souhaitable vis à vis de l’espace de mesure (invariances en
général vis à vis de rotation, translation et changement d’échelle).
Invariance souhaitable vis à vis d’occultation partielle ou de
déformations.
I souhait d’une représentation compacte pour accélérer la
reconnaissance
I Note: avec les CNN, une forme d’invariance vient de l’introduction
dans les données d’apprentissage de diverses données donnant lieu à
la meme interprétation
M.-O. Berger Intro MRF September 18, 2018 22 / 45
Caractériser les données: exemple 1
caractéristiques possibles: aire, périmètre, compacité, histogramme . . .
M.-O. Berger Intro MRF September 18, 2018 23 / 45
Caractériser les données: exemple 2
Empreinte: extraire des données caractéristiques comme les birfurcations
et les points terminaux.
M.-O. Berger Intro MRF September 18, 2018 24 / 45
Caractériser les données: exemple 3
les modèles d’apparence [cootes95]: plutôt que de caractériser des images
de visages par l’extraction de caractéristiques a priori (lèvres, nez, yeux...)
extraire directement des caractéristiques communes aux images à partir
d’un groupe d’exemples.
Représentation linéaire des variations d’un ensemble de formes par rapport
à la forme moyenne (voir le cours sur l’ACP et les modèles linéaires):
Figure: (1): extrait de la base de données. (2): les modes extraits
M.-O. Berger Intro MRF September 18, 2018 25 / 45
Caractériser les données: exemple 3
Figure: représentation d’une forme en utilisant 1, 2, 3 ... modes
M.-O. Berger Intro MRF September 18, 2018 26 / 45
Modèle et représentation des classes
Il existe de nombreuses façons de représenter des classes. L’objectif est
d’avoir une représentation compacte et de faciliter l’identification de la
classe d’appartenance d’un nouvel exemple.
Quelques représentations fréquentes:
I représentation de la classe par la base des exemples: cout du test
d’appartenance prohibitif car on passe tous les éléments en revue.
I représentation d’une classe par une distribution de probabalité
(souvent paramétrique) suivie par les exemples exemples (Gaussienne
par exemple)
I connaissance des fonctions de séparations des classes (frontières
linéaires, quadratiques ...)
M.-O. Berger Intro MRF September 18, 2018 27 / 45
Modèle génératif versus modèle discriminant
I Modèles génératifs:
I Basé sur l’étude de P(x|Class). On décrit la classe sans chercher à
regarder ce qui différencie cette classe des autres classes.
I exemple: ACP
I Modèles discriminants:
I on cherche à maximiser la qualité de la classification sur une base
d’apprentissage.
I exemple: SVM (hyperplan séparateur), perceptron, (erreurs),..
M.-O. Berger Intro MRF September 18, 2018 28 / 45
Exemple de représentation des classes
Étant donnés un certain nombre d’exemples des objets à reconnaı̂tre, étant
donné un nouvel objet x, on veut affecter x à l’une des classes.
On peut:
I ne pas structurer la base des exemples et mesurer la concordance la
meilleure entre l’objet et les exemples de la classe (pattern matching)
I Produire une représentation statistique de la base (moyenne,
variance) et l’utiliser pour la reconnaissance
M.-O. Berger Intro MRF September 18, 2018 29 / 45
En présence de données aberrantes
Le contrôle d’une forme de régularité des classes ou des distributions,
permet d’éviter de créer des frontières inutilement complexes, risquant de
refléter uniquement le bruit...
Gérer les données incorrectes, rares ou bruitées est un problème
important de la RF.
M.-O. Berger Intro MRF September 18, 2018 30 / 45
Quelques problèmes importants
I Avoir des outils statistiques/probabilistes/numériques permettant
I de détecter des mesures invalides/inadaptées: théorie des tests
I de travailler dans un espace de dimension réduite: réduction de la
dimensionnalité
I des moyens de grouper/modéliser des données similaires (une classe
d’objets) avec des critères dépendant de l’application: plus proche
voisin, classification, modélisation linéaire, méthodes probabilistes
I d’estimer les paramètres caractéristiques d’une mesure, sa classe étant
connue: théorie de l’estimation
I Des mesures atypiques ou erronées peuvent être présentes dans les
données → faire en sorte qu’elles n’influencent pas le processus de
reconnaissance (notion de robustesse)
M.-O. Berger Intro MRF September 18, 2018 31 / 45
La RF en fonction des connaissances disponibles:
objectif: à partir de données numériques (image, parole, capteur, signal),
étudier,caractériser ou classifier le phénomène ayant donné lieu à ces
observations
Réseaux neurones
M.-O. Berger Intro MRF September 18, 2018 32 / 45
Contenu du cours
Notions abordées dans ce cours:
I Données et incertitudes
I Représentation des données
I Modélisation et prise en compte de l’incertain
I Tests adéquation mesure/modèle
I Modélisation linéaire
I l’analyse en composante principales (ACP), l’analyse en composantes
indépendantes (ACI), l’analyse linéaire discriminante (ALD)
I Exemples de systèmes de reconnaissance de visage basés sur des
classifieurs linéaires (ADABOOST)
I Estimation
I Les bases de l’estimation paramétrique
I Estimation robuste
I Algorithme EM
I Quelques problèmes de reconnaissance des formes dans le domaine de
l’image
M.-O. Berger Intro MRF September 18, 2018 33 / 45
Part I
Représenter les données
M.-O. Berger Intro MRF September 18, 2018 34 / 45
Problèmes de représentation
I la taille: Les données sont rarement de taille raisonnable
(spectrogramme, images,. . . ) → il faut adopter une représentation
des données de taille raisonnable avec le moins possible de perte
d’information
I l’invariance: les données peuvent être enregistrées dans des repères
différents (ex orientation différente). Les données peuvent aussi être
des mesures indirectes d’un même phénomène: les mesure ne sont
donc pas directement semblables même si elles concernent un même
phénomène
I Utiliser des mesures invariantes (ou le plus possible) pour caractériser
des formes.
I dans les cas complexes, il n’y a pas de caractéristiques évidentes
résumant au mieux les données et tenant compte des variations
d’apparence. Celles ci doivent être apprises.
M.-O. Berger Intro MRF September 18, 2018 35 / 45
Comment caractériser l’invariance?
Il peut y avoir de simples mouvements de l’objet, des changements de
points de vue, des changements d’illumination, des occultations....
M.-O. Berger Intro MRF September 18, 2018 36 / 45
Problème (malédiction (*)) de la dimension
*: terme inventé par Richard Bellman pour parle de la difficulté de
travailler avec des données appartenant à des espaces de grande
dimension.
I Représenter une forme par un vecteur de caractéristiques de petite
taille permet de limiter la complexité des processus
I Un grand vecteur de caractéristiques peut avoir tendance à modéliser
l’accessoire (le bruit) plutôt que l’essentiel des données.
I malédiction: il faut énormément de données pour obtenir une bonne
estimation. Soient 100 observations d’un phénomène faites dans
l’intervalle [0, 1]. Pour réaliser dans [0, 1]10 une couverture
équivalente à celle des 100 points il faudrait 10010 = 1020
observations, ce qui est la plupart du temps inenvisageable.
M.-O. Berger Intro MRF September 18, 2018 37 / 45
Exemples de représentation: descripteurs de Fourier
A la différence des moments géométriques qui ne nécessitent pas de
segmentation, les descripteurs de Fourier sont calculés à partir du contour
de la forme.
si f (x) est une périodique de période T , on définit les coefficients an et bn
par
RT RT
a0 = 2/T 0 f (x)dx, an = 2/T 0 cos(2πnx/T )f (x)dx
RT
bn = 2/T 0 sin(2πnx/T )f (x)dx
f peut être approximée par
X X
a0 + an cos(2πnx/T ) + bn sin(2πnx/T )
en se limitant en pratique à un certain nombre de termes.
M.-O. Berger Intro MRF September 18, 2018 38 / 45
Représentation: descripteurs de Fourier
Exemples d’approximations successives par série de Fourier:
M.-O. Berger Intro MRF September 18, 2018 39 / 45
Représentation: descripteurs de Fourier
Propriétés utiles des descripteurs de Fourier:coeffs de f (x − τ ).
an0 = an cos(2πnτ /T ) − bn sin(2πnτ /T )
bn0 = an sin(2πnτ /T ) + bn cos(2πnτ /T )
Il n’ y a pas d’invariance par translation, mais le module des coefficients
est invariant.
Troncature :
La limitation en pratique à un certain nombre de termes n’est pas
forcément évidente: une marche nécessite une infinité de coefficients pour
être bien représentée.
intérêt: une modélisation hiérarchique en terme de détails assez naturelle
M.-O. Berger Intro MRF September 18, 2018 40 / 45
Exemple de représentation: signatures
Utiliser des représentations moins constructives mais effectivement
invariantes à des groupes de transformations.
Exemple: codage de la pente
Balayer un contour. Construire la distribution f (x), ou l’histogramme de
l’angle polaire de la tangente à la courbe.
En utilisant comme codage le module de la transformée de Fourier de
f , on a l’invariance par rotation (rotation: addition d’une constante à
l’angle polaire)
M.-O. Berger Intro MRF September 18, 2018 41 / 45
Signatures
Autre exemple: utiliser l’angle du contour par rapport au rayon issu du
centre de gravité et passant par ce point.
Inconvénient: dans tous les cas, deux formes différentes peuvent partager
la même signature
Remarque: l’invariance à des transformations 2D peut être prise en compte
à deux niveaux:
I dans le descripteur: on a en général une description plus pauvre mais
qui permet une recherche rapide des éléments ressemblants. Il reste à
faire un peu de ménage parmi les candidats.
I dans le processus de recherche/classification: on recherche les
éléments ressemblants modulo un groupe de transformations défini.
M.-O. Berger Intro MRF September 18, 2018 42 / 45
Bibliographie I
S. Agarwal and D. Roth.
Learning a sparse representation for object detection.
In Proceedings of 7th European Conference on Computer Vision, Copenhagen
(Denmark), 2002.
Mykhaylo Andriluka, Stefan Roth, and Bernt Schiele.
Pictorial structures revisited: People detection and articulated pose estimation.
In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June
2009.
Best Paper Award Honorable Mention by IGD.
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.
Segnet: A deep convolutional encoder-decoder architecture for image
segmentation.
CoRR, abs/1511.00561, 2015.
M.-O. Berger Intro MRF September 18, 2018 43 / 45
Bibliographie II
T.F. Cootes, C.J. Taylor, D.H. Cooper, and J. Graham.
Active shape models -their training and application.
Computer Vision and Image Understanding, 61(1):38–59, 1995.
R. O. Duda and P. E. Hart.
Pattern Classification and Scene Analysis.
Wiley-InterScience, 1973.
C. HÃne, C. Zach, A. Cohen, R. Angst, and M. Pollefeys.
Joint 3d scene reconstruction and class segmentation.
In 2013 IEEE Conference on Computer Vision and Pattern Recognition, pages
97–104, June 2013.
A. K. Jain, R. P. W Duin, and J. Mao.
Statistical Pattern Recognition: A Review.
IEEE Transactions on PAMI, 22(1):4–37, January 2000.
M.-O. Berger Intro MRF September 18, 2018 44 / 45
Bibliographie III
Yann LeCun, Fu-Jie Huang, and Leon Bottou.
Learning Methods for Generic Object Recognition with Invariance to Pose and
Lighting.
In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition,
Washington, DC (USA), 2004.
L. Rabiner.
A tutorial on hidden markov models and selected applications in speech
recognition.
Proc. IEEE, 77:257–286, 1989.
A. Webb, editor.
Statistical Pattern Recognition.
wiley, 2002.
M.-O. Berger Intro MRF September 18, 2018 45 / 45
