Quelques filtres lisseurs de base (I)
• Cas d’images bruitées (e.g. gaussien, impulsionnel) prétraitement : ‘lissage’
• Filtrage linéaire– Moyennage
– exemples
1...11
............
1...11
1...11
12K
418291841880132801829132218132291880132801841829184
1344
1
2712141272718323832187
1232576957321214386984693814123257695732127183238321872712141272
1279
1
Linéaire gaussien, paramètre e.g. =1.0, =1.6
Bruit gaussien =30
Filtre moyenne 33
Filtre Gaussien =1.0
Quelques filtres lisseurs de base (II)
• Filtrage non linéaire– De Nagao
– SNN (Symetric Nearest Neighbor)
• Filtrage d’ordre– Médian (p pixels, p≤|Vs|)
Algorithme :1) Calcul de l’histogramme sur le voisinage Vs
2) Tri des valeurs du voisinage3) Sélection E le plus compact |E|=p4) Sélection de la valeur de E à l’ordre considéré
Bruit gaussien =30
Filtre de Nagao Filtre médian 33
• Image S15.ppt.zip
Bruit gaussien =20Image non bruitée Gaus. =20 filtre gaus. =2.5
‘S&P’ 0% filtre médian 7x7
=20 + ‘S&P’ 0% filtre Nagao
Filtrage : exercices• Que font les filtres à noyau de convolution suivants
(prenez un exemple numérique si nécessaire)
• Quelle est la condition sur les coefficients pour que le filtrage soit passe-bas
• Décomposer le filtre 2D de noyau
sous forme du produit de convolution de 2 filtres 1D
• En déduire un moyen efficace, en nombre d’opérations par pixel, d’implémenter les filtres précédents
111
111
111
91
121
242
121
161
121
2122
121
161
22
2
22
2 4
1
aaba
abbab
aaba
baab
Détection de contours :approche générale
• Objectif• Méthodes dérivatives
Utilisation du gradientCalcul de l’image du gradient
Calcul de l’image de la norme du gradient
Calcul de l’image de la direction du gradient
Seuillage (avec hystérésis) de l’image de la norme du gradient
Elimination des non maxima locaux dans la direction du gradient
Fermeture des contours
Utilisation du laplacienCalcul de l’image du laplacien
Calcul de l’image de la norme du gradient
Calcul de l’image binaire Iz des passages par zéro du laplacien
Application du masque binaire Iz à l’image de la norme du gradient
Seuillage (avec hystérésis) de l’image de la norme du gradient |Iz
Elimination des non maxima locaux dans la direction du gradient
Fermeture des contours
, par filtrage linéaire passe-haut
111
181
111
010
141
010
• Gradient
Sobel c=2Prewitt c=1
Opérateur MDIF
• Laplacien
4-connexité 8-connexité
11
000
11
c
c
101
0
101
cc
01010
12021
13031
12021
01010
01110
12321
00000
12321
01110
• Opérateurs ‘différence d’opérateurs’– Gradient intérieur, grad. extérieur– Gradient morphologique– Laplacien morphologique
• Convergence vers gradient et laplacien euclidiens si élément structurant = boule eucl. centrée et rayon 0
xxxgxxxg SSSS ,
xxxg SSmS xgxgx SS
mS
et morphologiques
• Dilatation / érosion de fonctions
– Cas particulier g(x)=0 xRnD
– PropriétésCroissance par rapport à f, Extensivité / anti-extensivité (si origine incluse dans support de g), Croissance / décroissance par rapport à g, Commutations.
xygyfxfy
g nR
sup
yfxfDxy
g
nR
inf
xygyfxfy
g nRinf
yfxf
Dxyg
nR
sup
par filtrage optimal (I)• Critères de Canny
(i) Bonne détection, (ii) bonne localisation, (iii) faible multiplicité des maxima dus au bruit
Filtre impulsionnel à réponse finie (RIF)
• Filtre de Deriche : RII
Dérivée directionnelle en x = Image*h(x)*f(y)Dérivée directionnelle en y = Image*h(y)*f(x)
• Filtre de Shen - Castan
yfxheyexyxf yxX ..1...
4,
3
yfxhexeyyxf xyY ..1...
4,
3
Filtre de lissage puis application d’un opérateur
différentiel
xfxfyfex
xeyxf xy
X 12
2...
2..
2,
yfyfxfey
yeyxf yx
Y 12
2...
2..
2,
par filtrage optimal (II)• Implantation du filtre de dérivation de Deriche
Décomposition entre 1 partie causale et 1 anti-causale
R1[i]=c.e-.I[i-1]+2.e-.R[i-1]-e-2.R[i-2]
R2[i]=-c.e-.I[i+1]+2.e-.R[i+1]-e-2.R[i+2]
R[i]=R1[i]+ R2[i]
• Implantation du filtre de lissage de Deriche Décomposition entre 1 partie causale et 1 anti-causale
R1[i]= b.I[i]+ b.e-.(-1).I[i-1]+2.e-.R[i-1]-e-2.R[i-2]
R2[i]= b.e-.(+1).I[i+1]-b.e-2.I[i+2]+2.e-.R[i+1]-e-2.R[i+2]
R[i]=R1[i]+ R2[i]
0 si0
0 si..
i
ieicih
i
0 si..
0 si0
ieic
iih i
221
11
...21
..
zeze
zeczh
22 ...21
..
zeze
zeczh
221
11
...21
.1.1
zeze
zebzf
22
22
...21
..1.
zeze
zezebzf
e
ec
21
2
2
.21
1
ee
eb
Exemples de et .
B1
|| MM (B1)
B2
|| MM (B2)|| Prewitt
|| Sobel || MDIF
MM (B1) MM (B2) masque
Deriche =1
Deriche =2
Deriche =3
Shen =0.5 Shen =1
Détection de contoursSeuillage avec hystérésis
– Détection des pixels de valeur ≥ sh
– Ajout des pixels de valeur ≥ sb et qui 1 composante connexe ayant au moins 1 pixel de valeur ≥ sh (utilisat° d’1 pile pour créer les composantes connexes)
Détection des maxima locaux de la norme du gradient dans la direction du gradient
Autres cas :
2;
4
4;0
0;
4
4;
2
1,1.tan1,.tan11 jijiM
1,1.tan1,.tan12 jijiM
(i,j-1) (i,j) (i,j+1)
(i+1,j-1)
(i-1,j+1)
Fermeture de contours• Construction d’1 « look-up table » permettant
d’indexer les pixels candidats à la fermeture pour chaque configuration.Codage configuration : où xi=1 si contour, 0 sinon
Ex. T[16]=1 ; T[136]=1 ; T[8]=1
• Algorithme de fermeture : – Pour chaque extrémité trouvée lors du balayage de
l’image :• Construction du sous-arbre de tous les chemins possibles
de longueur p et du coût associé à chaque nœud : somme des normes des gradients en chaque point du chemin
• Sélection du nœud de coût maximum• Prolongation du contour
12304765
12304765
12304765
7
0
2.i
iixV
Exemple
Prewitt Sobel MDIF masque
Deriche =1
Deriche =2
Deriche =3
Shen =0.5 Shen =1
Après fermeture
de contours
Contours : exercices (I)• Pour la norme du gradient, on utilise l’une des trois
normes suivantes :
Comparer les valeurs obtenues par N1, N2 et N3 si l’on calcule le gradient discret avec 2x=[-1 0 1] et 2y=t[-1 0 1]Même question si le gradient discret est obtenu l’application du filtre de Sobel En déduire que N3 est la norme la mieux adaptée dans le premier cas, et N1 ou N2 dans le deuxième cas.
• Ecrire les équations aux différences pour les 3 masques utilisés pour estimer le laplacien discret :
121
242
121
yxN
1 222 yxN
yxN
,max3
010
141
010
111
181
111
Contours : exercices (II)• Calculer le gradient et le laplacien morphologique
dans les cas d’images suivants :
Interpréter et commenter
• Effectuer un seuillage avec hystérésis sur :
• Donner les formules d’interpolation des gradients en M1 et M2 pour la détection des maxima locaux de la norme du gradient dans la direction du gradient , pour les différents cas de
00001111
00001111
00001111
00001111
11110000
11110000
11110000
11110000
01233210
12344321
23455432
34566543
34566543
23455432
12344321
01233210
00001210
00001210
00001210
01101210
01101210
00001210
00001210
00001210
00001010
00001020
00000010
01101120
01100030
00000020
01012210
00000000
Classification : objectifs• Mettre en évidence les similarités/
dissimilarités entre les ‘objets’ (e.g. pixels)• Obtenir une représentation simplifiée (mais
pertinente) des données originales
Définitions préalables• Espace des caractéristiques d (sS, ysd)
• Espace de décision = ensemble des classes (sS, xs), = {i, i[1,c] }
• Règle de décision ( = d(ys) )
• Critère de performance
sx~
Ex. de classification non paramétrique• Classification k-ppv (plus proches voisins)
On dispose d’un ensemble (de ‘référence’) d’objets déjà labelisésPour chaque objet y à classifier, on estime ses k ppv selon la
métrique de l’espace des caractéristiques, et on lui affecte le label majoritaire parmi ses k ppv
Possibilité d’introduire un rejet (soit en distance, soit en ambiguïté)
Très sensible à l’ensemble de référence
• Exemples : 1-ppv 3-ppv 5-ppv
k-ppv (
/24
)
Connaissance des caractéristiques des classes
• Cas supervisé– Connaissance a priori des caractéristiques des classes
– Apprentissage à partir d’objets déjà étiquetés (cas de données ‘complètes’)
• Cas non supervisé Définition d’un critère, ex. :
- minimisation de la probabilité d’erreur- minimisation de l’inertie intra-classe maximisation de l’inertie inter-classes
Définition d’un algorithme d’optimisation
Estimation de seuils (cas supervisé)• Image = ensemble d’échantillons suivant une loi de
distribution de paramètres déterminés par la classeex. : distribution gaussienne
• Cas 1D (monocanal), si seuil de séparation des classes i et i+1, probabilité d’erreur associée :
– Maximum de vraisemblance
– Maximum A Posteriori
2
2
2exp
2
1 ,,,
i
is
iississ
yxyPxRy
isisisisE xxPxxPP 11~~
dyy
dyy
P
i
i
si
i
is
ii
iE .ln
2exp.ln
2exp
2
2
121
21
dyy
dyy
P
i
i
si
i
ii
s
ii
iiE .ln
2exp..ln
2exp.
2
2
121
21
1
21
2
21
21 '..
ii
iiiiis
1
121
221
2221
21
2221
21 .
.ln.2....'
ii
iiiiiiiiiiiiii
Algorithme des c-moyennes (cas non sup.)
• Initialisation (itération t=0) : choix des centres initiaux (e.g. aléatoirement, répartis, échantillonnés)
• Répéter jusqu’à vérification du critère d’arrêt :– t++– Labelisation des objets par la plus proche
classe
– Mise à jour des centres par minimisation de l’erreur quadratique :
– Estimation du critère d’arrêt (e.g. test sur #ch(t) )
21tiss yminargx~
i
t
Ssss
t tt x,xch# 1
itsxSs
siti y,k,i
: 11
Remarques :
# de classes a priori
Dépendance à l’initialisation
c =3
c =4
c =5
=30
c =2
=60
Classification : exercices (I)Soit l’image à deux canaux suivante :
• Soit les pixels de référence suivants : label 1 : valeurs (1,03;2,19) (0,94;1,83) (0,59;2,04)label 2 : valeurs (2,08;0,89) (2,23;1,16) (1,96;1,14)Effectuer la classification au k-ppv.Commentez l’introduction d’un nouveau pixel de référence de label 1 et de valeurs (1,32;1,56)
2,48 1,68 2,24 2,55 2,36 1,64 2,20 1,42
1,68 1,96 2,43 1,95 1,61 2,23 1,55 2,50
1,57 1,65 1,92 2,34 1,41 2,45 1,50 2,28
2,53 1,42 2,11 2,08 2,24 1,96 2,27 1,63
1,32 0,80 1,20 0,59 0,94 1,36 1,59 0,94
1,03 1,14 1,26 1,04 0,83 1,10 1,09 0,64
1,55 1,52 0,40 0,55 1,30 1,33 0,95 0,50
1,13 0,70 0,76 1,16 0,56 1,60 0,64 1,06
1,33 0,67 0,55 1,32 0,80 1,42 1,44 1,23
0,51 0,95 0,81 1,04 1,03 1,16 1,42 0,43
0,45 0,43 1,35 0,91 1,21 1,55 1,53 0,60
1,44 1,18 0,83 0,89 0,58 1,14 1,47 1,06
1,56 1,52 1,78 2,04 1,79 2,50 1,72 1,83
2,19 2,14 1,76 2,49 1,46 1,41 1,80 2,31
1,68 2,54 1,62 2,44 2,41 2,40 2,56 2,48
2,19 2,35 2,28 1,95 1,51 2,24 2,53 1,50
Classification : exercices (II)Sur l’image à deux canaux précédente :
• Déterminer les seuils de décision pour chacun des canaux si l’on suppose 2 classes gaussiennes de caractéristiques respectives :canal 1 : (1,1)=(2.0,0.38), (2,2)=(1.0,0.34)
canal 2 : (1,1)=(1.0,0.36), (2,2)=(2.0,0.39)
Effectuer la classification par seuillage.
• Effectuer la classification c-means pour c=2Comparer avec les résultats précédentsComparer avec la classification c-means pour c=3
• Que pensez-vous de rajouter un terme markovien ? Considérez le cas d’un seul canal, ou celui des deux canaux utilisés de façon conjointe.
Classification bayésienne d’images
Formulation du problème
• Les images observées correspondent à la réalisation y d’un champ aléatoire Y = {Ys, sS}, S ensemble des ‘sites’, |S| = pixels, Ys ;
un autre champ aléatoire X = {Xs, sS}, celui des ‘étiquettes’ ou ‘labels’ des classes, dont la réalisation x est cachée, Xs, || = labels ou classes ;
• Le but de la classification est d’accéder à x connaissant y.
Avant les modèles markoviens• Calcul de la fonction de décision optimale pour estimer x
sachant y irréalisable simplifications :
• Pour tout sS, estimation de xs sachant ys classification aveugle,
• Pour tout sS, estimation de xs sachant {ys, sVS} classifications contextuelles
PyPyPxSs sss ./maxarg/maxarg ,
Modèles markoviensPb : estimer x connaissant y définir :
(i) un modèle ‘d’attache aux données’, i.e. reliant X et Y,
ET (ii) un modèle a priori pour X, i.e. favorisant certains types de solutions
Modélisation des interactions (locales) entre les sites
• Définition des interactions locales déf. d’un système de ‘voisinage’ :
• Et du système de ‘cliques’ associé, i.e. soit singletons, soit ensembles de sites tous voisins les uns des autres
sts VsVsVt,St,s et
4-connexité :
8-connexité :
Cliques d’ordre 2
Cliques d’ordre 3
Cliques d’ordre 4
Champs de Markov – champs de Gibbs
• X est un champ de Markov
où
• X est un champ de Gibbs de potentiel associé au système de voisinage Vs, sS
avec (C ens. cliques)
stStxx ts ,,
),/()/( stsssss VtxxXPxxXP
)(exp)( xUZ
xXP 1
Cc
sc csxUxU ),()(
Exemple de distribution a posteriori• Y gaussien conditionnellement aux classes
• Loi a priori = modèle de Potts (i,j) =
P(X=x / Y=y) = P(Y=y / X=x).P(X=x)/P(Y=y)
ss
sx
x
xssss
yyxU
.ln
., 2
2 2
20
tstsc xxxxU ,.., 21
Ss Vttsx
x
xs
ss
s
s xxy
Z,ln
.exp
21
22
2
12
Estimation du MAP (I)• Recuit simulé (Kirkpatrick, 1983) sur algorithme
de Métropolis
A partir de x0 la configuration initiale, et de T la température initiale,Répéter tant que le compteur est > et T0 : xk étant la config. courante
• Mettre le compteur à 0• Pour tous les sites s S :
– tirer ls selon la loi uniforme dans ,– poser xt = xt
k, tS:ts, et xs = ls,
– calculer U=
– si U < 0 alors – sinon :
» tirer z selon la loi uniforme dans [0,1]» si z < exp(- U / T), alors
– si xsk+1 xs
k incrémenter le compteur de 1• Poser T = .T
csCc
skt
kscstsc VtxxUVtxxU
:,,,~,~
ktt xx ~
sx~
xxk ~1
xxk ~1
sksssss yxUyxU ,,~ 00
Estimation du MAP (II)• Recuit simulé sur échantillonneur de Gibbs
A partir de x0 la configuration initiale, et de T la température initiale,Répéter tant que le compteur est > et T0 : xk étant la config. courante
• Mettre le compteur à 0• Pour tous les sites s S :
– poser xt = xtk, et xt
k+1 = xtk tS:ts,
– Pour chaque i de ,» poser xs = i,» calculer pi =
– tirer z selon la loi uniforme dans [0,1],
– Trouver j minimum tel que – Poser xs
k+1 = j,– si xs
k+1 xsk incrémenter le compteur de 1
• Poser T = .T
csCc
stscsss VtxxUyxUT :
,~,~,~exp 01
ktt xx ~
sx~
11 i i
ji i pzp .