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 .