TERI : Traitement et
reconnaissance d’images
Cours Master 2 IAD Cours Master 2 IAD
Isabelle Bloch ENST / Département Signal & Images Florence Tupin ENST / Département Signal & Images Antoine Manzanera – ENSTA / Unité d’Électronique et d’Informatique
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
TERI – Objectifs du cours
L’objectif du cours « Traitement et Reconnaissance d’Images » est de proposer une formation de base en analyse d’images et reconnaissance des formes.
Il est a destiné à tous les élèves suivant le Master IA et Décision ; les liens entre l’Image, la Vision et l’Intelligence Artificielle seront abordés à plusieurs reprises.
On présentera les connaissances de base sur les images discrètes (théorie de l’information), leur représentation (structures discrètes), et leur exploitation (filtrage et amélioration). L’analyse automatique des images sera développée à travers un problème phare : celui de la segmentation d’images.
On abordera également des notions de plus haut niveau sur la compréhension automatique du contenu des images (classification et reconnaissance des formes). Le cours s’accompagnera d’une partie pratique : TP sur machine + TD exercices. Enfin, une ouverture sur les applications et les débouchés industriels sera présentée.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 2
TERI – Planning du cours
* Cours 1 : Introduction + échantillonnage (4h) (Antoine Manzanera)
* Cours 2 : Filtrage et détection de contours (3h) (Antoine Manzanera)
* Cours 3 : Introduction à la segmentation (2h) (Antoine Manzanera)
* Cours 4 : Perceptions et modèles (2h) (Antoine Manzanera)
* Cours 5 : Reconnaissance des formes et classification (4h) (Florence Tupin)
* TP Machines : TP Introduction à l’image (4h) (Florence Tupin – Nicolas Loménie)
* TD Exercices : Séance de travaux dirigés (4h) (Séverine Dubuisson)
* Cours 6 : Descripteurs d’images (2h) (A. Manzanera)
* Cours 7 : Applications du traitement d’images (2h) (F. Tupin)
Détails pratiques, Organisation des examens, Supports de cours,… :
http://www.tsi.enst.fr/~bloch/P6Image/TERI.html
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 3
Introduction au TI – Plan du cours
I Développement du TI et domaines connexes
I1 Historique du Traitement d’images (TI) I2 TI et vision par ordinateur I3 TI et Intelligence Artificielle I4 TI et perception visuelle II Introduction aux images numériques
II1 Modalités II2 Vocabulaire II3 Échantillonnage et quantification III Les modèles formels du TI
III1 Le modèle linéaire : la convolution… III2 Le modèle fréquentiel : la transformée de Fourier, l’échantillonnage… III3 Le modèle statistique : l’histogramme, la quantification, l’entropie,… III4 Le modèle différentiel : gradients, isophotes, équations différentielles,… III5 Le modèle ensembliste : morphologie mathématique,… III6 Le modèle discret : maillage, connexité, distances,…
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 4
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
1950
2005
Historique du Traitement d’Images
Images de chambre à bulles
Restauration
EMPIRISME
Amélioration
VISION ACTIVE
RECONSTRUCTIONISME Caractères typographiés
MORPHOLOGIE
Classification
Imagerie satellite
MATHEMATIQUE Imagerie médicaleet aérienne Télesurveillance
et armement
EDP & SCALE SPACE
Contrôle qualitéDétection
Poursuite
Indexation
page 5 Reconstruction
Robotique mobile
Localisation
Gestion des données multimedia
Compression
TI & vision par ordinateur
Vision industrielle Vision robotique
- Environnement connu / contrôlé
- Contraintes de temps
- Contraintes de qualité
- Environnement non contrôlé /hostile
- Contraintes d’énergie
- Action / Adaptation
Traitement d’Images Multimedia Adéquation Algorithme Architecture
- Humain dans la boucle
- Contraintes d’espace
- Protection des contenus
- Prise en compte de la machine
- Compromis temps/énergie/espace
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 6
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Sc ène Codage / compression
Calcul de gradient
Détection de contours
Filtrage
Acquisition
Traitement ∑p∈S
Systèmes à base de TI
page 7
Transmission
Amélioration
Analyse
Compréhension
Segmentation
Ux∈I g
f I x
Extraction d’attributs
∂ ∂I
x p
Décodage / restitution
TI & Intelligence Artificielle
Dans la conception moderne de l’Intelligence Artificielle dite située (i.e. mise en situation) ou incarnée (i.e. introduite dans un « acteur »), la machine agit sur le monde extérieur, éventuellement se déplace, et aussi perçoit son environnement pour pouvoir s’y adapter.
La vision est une source extrêmement riche d’information, qui permet à la machine de se localiser, reconnaître des objets ou des personnes, à un coût faible, une énergie raisonnable, et de manière passive (i.e. sans émettre de signal).
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 8
TI & Intelligence Artificielle
Réciproquement, le traitement d’image et la vision tirent parti des connaissances et des techniques d’intelligence artificielle pour gérer l’adaptation à un environnement changeant, l’information incertaine, les systèmes hétérogènes de connaissances et les différents niveaux de prise de décision.
Apprentissage
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 9
Représentation de l’incertain
Modélisation des connaissances
Raisonnement et décision
TI & perception visuelle
Une difficulté fondamentale de la vision artificielle vient du manque de connaissance profonde des mécanismes qui régissent la compréhension des images dans la nature. La vision humaine est en effet extrêmement performante (déplacement, lecture, reconnaissance), mais nous n’avons aucun retour conscient sur la mécanismes mis en jeu (à la différence du jeu d’échec par exemple). En cela l’étude des mécanismes physiologiques et psychologiques de la vision sont une source très importante d’information, et d’inspiration.
- Exemples :
- ● Traitements rétiniens / traitements corticaux.
- Mécanisme d’accentuation des contrastes.
- Multirésolution et rétine.
- Vision des batraciens.
- …/…
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 10
TI & perception visuelle
Exemple : l’illusion de l’échiquier. Plusieurs mécanismes sont en jeu, du très bas niveau (renforcement local des contrastes) au très haut niveau (interprétation de l’ombre et reconnaissance d’un échiquier)
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 11
TI & perception visuelle
Exemple : l’illusion de l’échiquier. Plusieurs mécanismes sont en jeu, du très bas niveau (renforcement local des contrastes) au très haut niveau (interprétation de l’ombre et reconnaissance d’un échiquier)
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 12
I1 Types d’images, de capteurs
Phénomène physique Grandeur mesurée Capteur
Émission et réflexion de la lumière visible
Réflectivité, luminance,…
CCD, CMOS, Barrettes CCD,…
CCD, CMOS, Barrettes CCD,…
Rayonnement infrarouge
Luminance IR (chaleur), …
Bolomètres,…
Bolomètres,…
Écho ultra sonore
Distance, densité de tissus,…
Échographie, sonar,…
Échographie, sonar,…
Résonance magnétique
Présence d’un corps chimique,… IRM, RMN,…
Écho électromagnétique
Distance, spécularité de surfaces,..
Radar, SAR,…
Radar, SAR,…
Absorption des rayons X
Densité de tissus,…
Radiographie, tomographie,…
Radiographie, tomographie,…
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 13
Images numériques
x
R(x,y) I(x,y)
y
La quantification désigne la limitation du nombre de valeurs différentes que peut prendre I(x,y).
L’échantillonnage est le procédé de discrétisation spatiale d’une image consistant à associer à chaque zone rectangulaire R(x,y) d’une image continue une unique valeur I(x,y). On parle de souséchantillonnage lorsque l’image est déjà discrétisée et qu’on diminue le nombre d’échantillons.
Une image numérique est une image échantillonnée et quantifiée.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 14
Pixels et niveaux de gris
O
Largeur
i
Indice de colonne
j
Hauteur
Le pixel [i,j]
I[i,j] = N
Indice de
ligne Une image numérique I
N ∈ [Nmin,Nmax]
Valeur Niveau de gris
(Nmax Nmin) = nombre de niveaux de gris Log2(Nmax Nmin) = dynamique
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 15
Échantillonnage et quantification
Résolution…
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 16
…spatiale :
…tonale :
Échantillonnage
Quantification
256×256 128×128 64×64 32×32
6 bits 4 bits 3 bits 2 bits 1 bit
Échantillonnage et information
L’échantillonnage est une étape fondamentale qui doit tenir compte du contenu informationnel pertinent de l’image à analyser. Sur l’exemple ci contre, en 1d, le signal échantillonné « ressemble » à une sinusoïde de fréquence 8 fois plus faible :
Ce phénomène appelé aliasing est encore pire en 2d, car il affecte la fréquence et la direction des structures périodiques. Imaginons par exemple qu’on souhaite échantillonner l’image correspondant aux bandes noires cicontre :
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 17
Échantillonnage et information
Avec un échantillonnage adapté, l’image numérique fait apparaître des structures conformes à l’information présente dans l’image :
Mais en considérant seulement 1 échantillon sur 2, une structure différente apparaît, dont l’analyse (ici des bandes verticales, plus épaisses) ne sera pas conforme à la réalité de l’objet :
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 18
Échantillonnage et information
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 19
Et sur une image naturelle :
Image originale Image souséchantillonnée
Un exemple, sur une image de synthèse :
Quantification et information
La quantification peut également faire apparaître des distortions dans les images :
Comme pour l’échantillonnage, il existe des règles pour déterminer la bonne quantification (le bon nombre de bits) pour coder les images numériques. L’une dépend du capteur, et de sa capacité effective à observer des signaux de valeurs différentes : le rapport signal sur bruit. Le rapport signal sur bruit est défini à partir du rapport entre l’amplitude des niveaux de gris mesurables par le capteur (nmax nmin) et le niveau du bruit, en gros l’écarttype sn de la perturbation aléatoire qui affecte les niveaux de gris. En prenant le logarithme, on a le nombre de bits utile au capteur pour coder les images.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 20
Quantification et information
Outre les capacités du capteur, le nombre de bits réellement nécessaires pour coder une image varie d’une image à l’autre, en fonction de leur contenu informationnel. Ce nombre dépend de l’entropie, définie à partir de la distribution des niveaux de gris de l’image (cf plus loin, modèle statistique).
E=∑−pilog2 pi iN Où N est le nombre de niveaux de gris présents, pi est la proportion (0 < pi < 1) de points de l’image ayant pour niveau de gris i. Cette grandeur représente le nombre moyen de bits par pixel nécessaires pour coder toute l’information présente. Elle est utilisée dans les techniques de compression sans perte pour adapter le volume de donnée des images à leur contenu informationnel.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 21
III Modèles et outils fondamentaux
Dans la suite, on présente une introduction aux outils d’analyse d’images numériques les plus courants. Pour des raisons didactiques, la présentation est organisée selon les principaux modèles mathématiques qui ont été employés pour traiter les images. Ces différents modèles ne sont cependant ni exclusifs ni cloisonnés, et la séparation ne sera pratiquement plus visible dans les cours suivants. Aux différents modèles présentés correspondent un certain nombre d’outils fondamentaux, qui se sont révélés au cours du temps plus ou moins incontournables, que ce soit d’un point de vue pratique ou théorique. Citons : la convolution, la transformée de Fourier, l’histogramme, les pyramides, la corrélation, la transformée en toutourien, les ondelettes… Nous donnons dans la suite de ce cours une introduction aux outils les plus basiques ou les plus courants. Les autres seront traités ou approfondis dans la suite du cours TERI, ou dans les autres cours optionnels.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 22
III1 : Le modèle linéaire
Dans le modèle linéaire, la structure mathématique sousjacente est l’Espace Vectoriel. Les opérateurs fondamentaux sont ceux qui préservent la structure d’espace vectoriel, c’estàdire les applications linéaires :
f I J=f If J f I = f I
Pour les images, ces opérateurs correspondent aux convolutions :
La convolution :
C’est l’opérateur de base du traitement linéaire des images. Apparue très tôt dans les premiers systèmes d’analyse d’images sous forme empirique et justifiée par des considérations d’implantation, ce n’est que plus tard qu’on a fourni des justifications physiques et fait le lien théorique avec les filtres et le traitement du signal.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 23
Antoine La Convolution Soit I une image numérique. Soit h une fonction de [x1,x2]×[y1,y2] à valeurs réelles. La convolution de I par h est définie par :
I∗h[x,y]=∑x2 ∑y2
h[i,j]⋅I[x−i,y− j]
i=x1
j=y1
La fonction h est dite noyau de convolution Propriétés de la convolution :
x
COMMUTATIVITÉ
h∗g=g∗h
y
ASSOCIATIVITÉ
h∗g∗k=h∗g∗k=h∗g∗k
Les nouvelles valeurs du pixel sont calculées par produit scalaire entre le noyau de convolution et le
DISTRIBUTIVITÉ / +
h∗gk =h∗gh∗k
voisinage correspondant du pixel.
MANZANERA Cours TERI – Master IAD UPMC Paris 6page 24
h[x,y]
Antoine La Convolution Exemple :
1/152
24 Pour calculer une convolution, on remplace la valeur de chaque pixel par la valeur du produit scalaire entre les valeurs du noyau de convolution et les valeurs du voisinage du pixel considéré (par rapport à l’origine (0,0) du noyau de convolution). Attention : implémentation « parallèle ».
MANZANERA Cours TERI – Master IAD UPMC Paris 6page 25
55511111116161616111111115 5 5
161616242424161616165 5 5 11 11 11
16 16 1616
11 11 1111 5 5 5
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Le modèle fréquentiel tend à décrire l’image en termes de structures périodiques, en la décomposant dans une base de fonctions périodiques simples, comme des sinusoïdes :
La transformée de Fourier :
Outil fondamental d’analyse en traitement du signal, le pendant bidimensionnel de la TF et sa version discrète peut être appliqué avec profit aux images numériques. Si son utilisation en tant qu’outil analytique et algorithmique s’est estompée en traitement d’images au profit d’approches mieux adaptées à la localisation spatiale des fréquences (ondelettes), elle reste un outil théorique et pédagogique important : la formalisation du phénomène de l’aliasing et des contraintes d’échantillonnage en est un exemple (voir cours Espace d’échelles).
III2 : Le modèle fréquentiel
page 26
Transformée de Fourier
La transformée de Fourier permet la décomposition d’un signal f en combinaison linéaire de sinusoïdes complexes, dont les coefficients F[u,v] dit coefficients de Fourier, fournissent des informations sur les fréquences (u,v) et permettent des manipulations dans le domaine fréquentiel.
Transformée de Fourier discrète bidimensionnelle :
(x,y) sont les coordonnées du domaine spatial
Directe : F[u,v]=∑w−1h−1
∑f [x,y]e−2iuxvy/wh x =0
y=0
(u,v) sont les coordonnées du domaine fréquentiel
Inverse :
f [x,y]= wh 1w−1∑∑h−1
F[u,v]e2iuxvy/wh
u=0
v=0 Propriétés de la transformée de Fourier (1) :
ÉCRITURE SOUS FORME MODULE / PHASE
F [u,v]=∥F [u,v]∥ei [ u,v]
PÉRIODICITÉ
F [u,v]=F [uw,vh]
SYMÉTRIE Si F est la transformée de Fourier d’une fonction réelle f :
F [u,v]=F [−u ,−v] et donc : ∥F [u,v]∥=∥F [−u ,−v]∥ et [u,v]=−[−u ,−v ] Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 27
Transformée de Fourier
Propriétés de la transformée de Fourier (2) :
si
{ f f f 12[ [ [ x x x ,y ,y ,y ] ] ] F F F 12 [u,v [u,v [u,v]}
]
]
LINEARITÉ
a⋅f 1[ x,y]b⋅f 2 [ x,y] a⋅F 1[u,v]b⋅F 2[u,v]
CORRESPONDANCE CONVOLUTION / PRODUIT
f 1[ x,y]∗ f 2[ x,y] F 1[u,v ]⋅F 2[u,v]
f 1[ x,y]⋅f 2[ x ,y ] F 1[u,v ]∗F 2[u,v]
page 28 TRANSLATIONS SPATIALES / FRÉQUENTIELLES
DÉRIVATION
THÉORÈME DE PARSEVAL ∂ f [ x,y ∂ x ]
iuF[u,v ] et
∂ f [ x,y]
∂ y ivF[u,v] f [ x−x’,y−y’ ] F [u,v]⋅e−2i ux ‘vy ‘ /wh f [ x,y]⋅e2iu’ xv’ y/ wh F [u−u’ ,v−v’ ]
w−1 ∑h−1∑x=0 y=0
∥f [ x,y]∥2= wh 1w−1∑h ∑−1∥F [u,v]∥2
u= 0
v=0 Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Module Phase
u
Image
v
v
u
f [ x,y] ln ∥F [u,v]∥ [u,v]
TF
QUIZZ Transformée de Fourier
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Attribuez à chaque image son spectre de Fourier
(1) (2) (3) (4)
(a) (b) (c) (d)
QUIZZ Transformée de Fourier
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Attribuez à chaque image son spectre de Fourier
(1) (2) (3) (4)
(a) (b) (c) (d)
III3 : Le modèle statistique
On s’intéresse dans ce modèle aux propriétés statistiques des images : la distribution des valeurs prises par les pixels, la corrélation existant entre des pixels spatialement proches, la fréquence d’occurrence de certaines structures spatiales… Les mesures statistiques fournissent des grandeurs et fonctions empiriques sur lesquelles peuvent s’appuyer des modèles probabilistes utilisés par les algorithmes d’analyse d’images.
Par exemple, le modèle des champs de Markov considère l’image comme la réalisation d’un champ aléatoire (chaque pixel correspondant à une variable aléatoire), où la valeur prise par un pixel ne dépend que de celle de ses voisins (selon une topologie discrète donnée, voir plus loin).
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 31
III3 : Le modèle statistique
Un autre exemple remarquable d’analyse statistique est l’utilisation des matrices de co occurrence, habituellement utilisées pour caractériser les textures.
j La matrice de cooccurrence Mv associée au vecteur v, est la matrice de taille N x N ( N est le nombre de niveaux de gris), tel que Mv(i,j) représente la fréquence du couple de valeurs (i,j)
i
v i j
parmi les couples de pixels (x,x+v).
Ces techniques, et d’autres exemples de modèles statistiques seront présentées plus en détail dans les prochains cours. Dans le cadre de cette introduction, nous développerons seulement le premier outil statistique d’analyse des images : l’histogramme.
L’histogramme :
Outil de base pour l’étude des capteurs ou de la dynamique d’une scène, il est utilisé par certains opérateurs d’analyse. On retiendra cependant qu’il ne faut pas considérer l’histogramme comme une caractéristique fondamentale de l’image dans la mesure où on peut le transformer radicalement sans changer significativement l’image.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 32
Antoine Histogramme
W
H
L’histogramme représente la répartition des pixels en fonction de leur niveau de gris. Il fournit diverses informations comme les statistiques d’ordre (voir ci contre), l’entropie (voir précédemment), et peut permettre d’isoler des objets.
Min Médian Max MANZANERA Cours TERI – Master IAD UPMC Paris 6page 33
H(x)
HC(x)
H(x) est le nombre de pixels dont le niveau de gris est égal à x.
Histogramme cumulatif normalisé
Effectif relatif
HC(x) est le taux de pixels dont le niveau de gris est inférieur à x.
Niveau de gris
∑x
H x HC x=i=٠
W×H
Effectif
Histogramme
Niveau de gris
Traitement à base d’histogramme
On présente dans la suite quelques traitement d’analyse effectués uniquement à partir de l’histogramme. Retenons que certains de ces traitements sont souvent calculés au niveau des capteurs, et qu’en général leur pertinence est très intimement liée aux conditions d’acquisition.
(1) Normalisation
→ exploiter toute la dynamique de codage.
(2) Égalisation
→ équilibrer la dynamique de codage et augmenter le contraste.
(3) Segmentation
→ simplifier l’image en regroupant les pixels selon leurs valeurs.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 34
Histogramme : normalisation
La normalisation d’histogramme, ou expansion de dynamique, est une transformation affine du niveau de gris des pixels de telle sorte que l’image utilise toute la dynamique de représentation.
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 35
- D : dynamique
- Nmin : la plus petite valeur dans l’image
- Nmax : la plus grande valeur dans l’image
f new[x,y]= f [x,y]−Nmin⋅ 2 D−1
Nmax−Nmin
image d’origine f[x,y]
expansion de dynamique fnew[x,y] Nmax Nmin 2D 1
histogramme d’origine histogramme normalisé
Pour rendre la normalisation moins sensible aux valeurs marginales (outliers), on utilise généralement un paramètre , 0<<1,et on prend :
Nmin∈HC−1 Nmax∈HC−11−
Histogramme : égalisation
L’égalisation d’histogramme est une transformation des niveaux de gris dont le principe est d’équilibrer le mieux possible la distribution des pixels dans la dynamique (Idéalement, on cherche à obtenir un histogramme plat).
- La technique classique consiste à rendre « le plus linéaire possible » l’histogramme cumulé de l’image en utilisant la transformation suivante :
f new[ x,y]=2D−1⋅HC wh
f [ x,y]
- D : dynamique
- (w,h) : dimension de l’image
- HC(.) : histogramme cumulé
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 36
Histogramme de f Histogramme de fnew
Original f[x,y] Histogramme
Histogramme cumulé de f
cumulé de fnew
Après égalisation fnew[x,y]
Le résultat est une augmentation globale du contraste dans l’image. Notez dans l’exemple cidessus l’accentuation des défauts avec la mise en évidence du bruit spatial fixe (effet de tramage) de l’imageur infrarouge.
Histogramme : segmentation
Il existe des techniques de segmentation basées sur un regroupement des niveaux de gris à partir de l’histogramme. Ces techniques sont rarement efficaces car elles ne considèrent que la valeur des pixels sans tenir compte de critères géométriques ou topologiques (voir cours Segmentation). Par exemple, la méthode cidessous calcule un certain nombre de quantiles à partir de l’histogramme cumulé, les regroupe par classes en fonction d’un critère de distance, puis attribut la même étiquette aux pixels dont la valeur est la plus proche d’une classe donnée :
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 37
Histogramme Image originale
cumulé avec agrégation des quantiles
Image segmentée
III4 : Le modèle différentiel
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 38
Dans le modèle différentiel, on considère l’image comme une fonction continue f(x,y), dont on étudie le comportement local à l’aide de ses dérivées. Une telle étude, fondée sur la formule de Taylor, n’a de sens que si la fonction f a une certaine régularité, ce qui constitue le problème clef des méthodes différentielles.
Au premier ordre, on peut ainsi associer à chaque point (x,y) un repère propre (t,g), où le vecteur t donne la direction de l’isophote (ligne de variation minimale) et g la direction orthogonale, celle du gradient. ∇I ∇I ggGrâce au plongement dans le continu, le modèle différentiel permet en outre d’exprimer un grand nombre d’opérations d’analyse en termes d’équations aux dérivées partielles (EDP), ce qui permet de donner un fondement
t t
mathématique satisfaisant aux traitements et aussi de fournir des méthodes pour les calculer, par des schémas numériques de résolution. φ
x
y
φ
x
y
III5 : Le modèle ensembliste
En morphologie mathématique, l’image est considérée comme un ensemble, dont on étudie les propriétés en fonction de relations locales avec un ensemble de référence (élément structurant) en termes d’intersection et d’inclusion (relations en toutourien).
B∩X =∅
B⊂X
B∩X ≠∅
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 39
Érosion et Dilatation
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 40
Les transformations morphologiques sont définies à partir des 2 opérateurs ensemblistes de base que sont l’érosion et la dilatation
Original (Matisse 1952) B X ={x ∈R2 ;B x∩X ≠∅} B X ={x ∈R2 ;B x⊂X }
(élément structurant : disque)
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Érosion et Dilatation
L’érosion et la dilatation, et par suite l’ensemble des transformations morphologiques, se généralisent des ensembles (Images binaires) aux fonctions (Images en niveaux de gris) par l’intermédiaire des ensembles de niveaux :
I n={x ∈R٢ ;I x n }
MIN MAX
Original (Man Ray 1924) B I
BI (élément structurant : losange)
page 41
III6 : Le modèle discret
La géométrie discrète est une discipline au moins aussi ancienne que le traitement d’images. Alors que le modèle différentiel considère les structures géométriques (courbes, surfaces, droites, etc) comme des approximations numériques de leurs homologues continues, ou que le modèle fréquentiel traduit la discrétisation en termes de perte d’information, le modèle discret, lui, intègre l’espace échantillonné comme cadre mathématique, et s’efforce de donner un cadre formel aux structures géométriques discrètes : définition, propriétés, théorèmes,…
Quelle est la distance
Qu’estce qu’un trou ? Qu’estce qu’une entre les 2 points ?
droite ?
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 42
Antoine Pavages du plan Un pavage du plan est une partition du plan en cellules élémentaires (pixels). Il n’existe que 3 pavages réguliers du plan :
triangulaire carré hexagonal
… mais de nombreux pavages irréguliers :
MANZANERA Cours TERI – Master IAD UPMC Paris 6page 43
Antoine Pavages du plan D’autres pavages irréguliers du plan…
MANZANERA Cours TERI – Master IAD UPMC Paris 6page 44
Pavage apériodique de Penrose
Pavage périodique d’Escher
Pavages et maillages
A tout pavage du plan on peut associer un graphe où les sommets (noeuds) représentent les cellules élémentaires, et où les arêtes représentent la relation d’adjacence entre les cellules (2 cellules sont adjacentes si elles ont un côté en commun). Un tel graphe est un maillage du plan.
Les pavages et les maillages réguliers sont duaux :
Pavage triangulaire Pavage carré Pavage hexagonal
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 45
Maillage triangulaire Maillage carré Maillage hexagonal
Questions :
représentation dans Z2 ?
combien de directions ?
récursivité ?
Maillage et connexité
Les relations topologiques dans les images discrètes sont définies à partir de la relation de connexité induite par le graphe du maillage (X,S), où X représente les sommets et S les arêtes. X⊂Z2;S⊂X 2
Soient x et y 2 points de X, par définition x et y sont voisins si :
x≈y⇔x,y∈S
maille carrée 4connexe
maille carrée 8connexe
maille triang. 6connexe
maille triang. 6connexe
La clôture transitive de la relation de voisinage est une relation d’équivalence « il existe un chemin connexe entre x et y » :
x~y⇔∃{x1,…, x n}/ x≈x1,… , xi≈xi1,… ,x n≈y Les classes d’équivalence de cette relation s’appellent les composantes connexes de X
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
Topologie dans la maille carrée
Dans la maille carrée, la notion de trou dans un objet X (X ⊂Z2), qui doit correspondre à une composante connexe finie du complémentaire Xc, n’est pas bien définie…
Ce problème est lié à la validité du théorème de Jordan, selon lequel une courbe simple fermée sépare le plan en 2 composantes connexes, dont une bornée.
…sauf si l’on considère des connexités différentes pour X et pour Xc :
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
8connexité 4connexité
(8,4)connexité
(4,8)connexité Questions :
combien de composantes connexes, combien de trous compte l’image cicontre
Le théorème de Jordan est vérifié pour ces connexités.
en (8,4)connexité ? en (4,8)connexité ?
Métrique dans la maille carrée
Le graphe du maillage induit également une distance dans le plan discret, la distance entre 2 points x et y étant définie par la longueur du plus court chemin connecté entre x et y. En pondérant toutes les arêtes du maillage par la valeur 1, on trouve :
distance de la 4connexité
1 distance de la 8connexité d ٤ x,y=∣x١ −y١∣∣x٢−y٢∣
1 1
d ٨x,y=max∣x١ −y١∣,∣x٢−y٢∣
On peut aussi pondérer différemment les arêtes du maillage 8connexe, voire utiliser des maillages plus complexes (i.e. des voisinages plus grands) :
4
7 11 35 distance du chamfrein (3,4)
distance du chamfrein (5,7,11)
Questions :
calculer les distances d4(x,y), d8(x,y), dch(3,4)(x,y), dch(5,7,11)(x,y) entre les 2 points x et y cicontre : x
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
y
Conclusion
A retenir pour ce cours : Équivalence convolution / multiplication
image numérique
modèle linéaire échantillonnage modèle fréquentiel
quantification histogramme convolution Filtres différentiels
Ondelettes
Corrélation
– ACP représentation fréquentielle
connexité et distance discrètes modèle différentielmodèle
…/…
statistique
Morphologie EDP / Ensemble de niveaux
statistique modèle ensembliste
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 49
Sources et bibliographie Liens utiles
Livres :
- J.P. Cocquerez et S. Philipp « Analyse d’images : filtrage et segmentation » Masson 1995
- R.C. Gonzalez et Woods « Digital Image Processing 2d edition » Addison Wesley 2002
- A. Rosenfeld et A.C. Kak « Digital picture processing » Academic Press London 1982.
- H. Maître (ss la direction de) « Le traitement des images » Hermes Lavoisier IC2 2003.
- J.R. Parker « Algorithms for Image Processing and Computer Vision » Wiley & Sons 1997.
- S. Bres, J.M. Jolion, F. Lebourgeois « Traitement et analyse des images numériques» Hermes Lavoisier 2003
- I.T. Young, J.J. Gerbrands et L.J. Van Vliet « Fundamentals of Image Processing » Université de Delft. (sur internet : http://www.ph.tn.tudelft.nl/~lucas/publications/1995/FIP95TYJGLV/FIP2.2.pdf)
- D. Lingrand « Introduction au Traitement d’images » Vuibert 2004
Pages web :
- Telesun – INSA : http://telesun.insalyon.fr/~telesun/
- Univ. de Delft : http://wwwict.its.tudelft.nl/html/education/courses/
- Projet Marble : http://www.icbl.hw.ac.uk/marble/vision/low/fundamentals/intro.htm
- CVOnLine Univ. d’Édimbourg : http://www.dai.ed.ac.uk/CVonline/
Antoine MANZANERA Cours TERI – Master IAD UPMC Paris 6
page 50
télécharger gratuitement Traitement et reconnaissance d’images
