BIMA Bases de l’IMAgerie Énoncés de TD/TME …webia.lip6.fr/~thomen/Teaching/BIMA/td-tme/Livret2_4I600_2016.pdf · Énoncés de TD/TME Séances 6-10 Master 1 Informatique - Spécialité

BIMA : Bases de l’IMAgerie

Énoncés de TD/TMESéances 6-10

Master 1 Informatique - Spécialité IMAgerieUniversité Pierre et Marie CurieAnnée Universitaire 2016-2017

Table des matières

6 Harris 36.1 TD 6 : Détecteurs de Coins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36.2 TME 6 : Détecteur de Harris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

7 Descripteurs Image 97.1 TD 7 : Extraction de Descripteurs Image . . . . . . . . . . . . . . . . . . . . . . 97.2 TME 7 : Quantification Couleur - Recherche par le Contenu . . . . . . . . . . . . 11

8 Analyse des Données 148.1 TD 8 : Analyse en Composantes Principales (ACP) . . . . . . . . . . . . . . . . . 14

8.1.1 Annexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158.2 TME 8 & 9 : Reconnaissance de Visages par Eigenfaces . . . . . . . . . . . . . . 16

8.2.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168.2.2 Analyse par eigenface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178.2.3 Base de données de visages . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Analyse Discriminante 259.1 TD 9 : Analyse Discriminante Linéaire . . . . . . . . . . . . . . . . . . . . . . . . 259.2 TME 9 : Fin du TME sur Eigenfaces . . . . . . . . . . . . . . . . . . . . . . . . . 28

10 Segmentation 2910.1 TD 10 : Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2910.2 TME 10 : Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Semaine 6

Détection de Points d’Intérêt

6.1 TD 6 : Détecteurs de Coins

Exercice 1 — Détecteur de MoravecOn considère une image I et une fenêtre W de taille Wx×Wy. La variation moyenne d’intensitéEu,v(x1, y1), entre la région W centrée au pixel (x1, y1) et la région W centrée au pixel(x1 + u, y1 + v), (u, v) ∈ Z2, est définie ainsi (voir figure 6.1) :

Eu,v(x1, y1) =

Wx2∑

k=−Wx2

Wy2∑

l=−Wy2

[I(x1 + k + u, y1 + l + v)− I(x1 + k, y1 + l)]2 (6.1)

Figure 6.1 – Détecteur de Moravec

UE Bases de l’IMAgerie Master 1 Informatique - Spécialité IMA

L’algorithme de détection de points d’intérêt (coins) de Moravec [4] est ainsiformulé :

— En utilisant une fenêtreW de taille 3×3, on calcule Eu,v(x, y) (équation 6.1) pour chaquepixel (x, y) de l’image, pour tous les déplacements possibles : modèle à 8 voisins :{(1, 0); (1, 1); (0, 1); (−1, 1); (−1, 0); (−1,−1); (0,−1); (1,−1)}.

— On calcule une "carte des coins" en calculant en chaque pixel : C(x, y) = minu,v Eu,v(x, y).— On effectue une détection de maxima locaux pour effetuer la détection finale.

Exemple : On considère l’image I suivante :

I =

255 255 255 255 255 255 255 255 255 255 255255 255 255 255 255 255 255 255 255 255 255

255 255 255 255 255 255 255 255 0 255 255255 255 255 255 255 255 255 255 255 255 255

255 255 255 255 255 255 255 255 255 255 255

0 255 0 0 0 0 255 255 255 255 255

0 0 0 0 0 0 255 255 255 255 2550 0 0 0 0 0 255 255 255 255 2550 0 0 0 0 0 255 255 255 255 255

1. Calculer Eu,v(x, y) puis C(x, y) aux pixels encadrés de l’image précdente.2. Que repésentent les différents points choisis dans l’image ?3. Discuter les performances du détecteur de Moravec.

Exercice 2 — Détecteur de HarrisHarris & Stephens [2] proposent de modifier le détecteur de Moravec comme suit :

1. Introduction une fenêtre Gaussienne : w(x, y) = 1√2πσ2

e−x2+y2

2σ2 , donnant la nouvelle for-

mulation E1u,v(x, y) =

∑x,y∈W

w(x, y)× [I(x+ u, y + v)− I(x, y)]2

2. On effectue un développement limité à l’odre 1 pour calculer I(x+ u, y + v) :

I(x+ u, y + v) = I(x, y) + u · ∂I∂x

+ v · ∂I∂y

+O(u2, v2) ≈ I(x, y) + u · Ix + v · Iy (6.2)

1. Montrer alors qu’on a alors E1u,v(x,y) = (u,v) ·M · (u,v)T, avec :

M =

∑

x,y∈Ww(x, y) · I2

x

∑x,y∈W

w(x, y) · Ix Iy∑x,y∈W

w(x, y) · Ix Iy∑


y

=

[A CC B

]

2. La matrice M , appelée matrice d’auto-corrélation, représente la structure locale de lafonction E1(x, y) au voisinage du pixel (x, y). Harris & Stephens [2] proposent d’effectuerla décomposition en valeurs propres (λ1, λ2) de E1 (fig 6.2a). Pour limiter la complexitédu calcul, Harris propose le critère R(x, y) suivant (fig 6.2b)). :

R(x, y) = det(M)− k · [trace(M)]2 (6.3)

SEMAINE 6. HARRIS 4 UPMC


(a) Valeurs propores (b) Critère De Harris

Figure 6.2 – Détecteur de Haaris

det(M) = AB − C2 = λ1 · λ2, trace(M) = A+B = λ1 + λ2.Monter l’équivalence entre les figures 6.2a) et 6.2b).

3. Montrer que le détecteur de Harris est ainsi invariant en rotation et auxvariations affines de luminosité. Est-il invariant à l’échelle ?(a) Proposer une méthode (simple) permettant de rendre le détecteur de Har-

ris capable de détecter des points à plusieurs échelles différentes.



6.2 TME 6 : Détecteur de Harris

L’objectif du TME est de mettre au point un détecteur de points d’intérêts parla méthode d’Harris et Stephens [2].On rappelle que le détecteur de Harris consiste à estimer une "carte des coins" de l’image, encalculant en chaque pixel la grandeur :

R(x, y) = det(M)− k · [trace(M)]2 (6.4)

k ∈ [0.04; 0.06] en pratique (voir [2]). M est la matrice d’auto-corrélation de l’image :

M =

∑


x

∑x,y∈W

w(x, y) · Ix Iy∑x,y∈W

w(x, y) · Ix Iy∑


y

=

[A CC B

]

où w(x, y) = 12πσ2 ·e

(x−xc)2+(y−yc)2

2σ2 est un masque Gaussien centré sur la fenêtre d’analyse W .On approximera les dérivées directionnelles Ix et Iy avec l’un (au choix) des masques suivants :

Gx Gy

Masques Gradient

0 0 01 0 −10 0 0

0 1 00 0 00 −1 0

Masques Prewitt

1 0 −11 0 −11 0 −1

1 1 10 0 0−1 −1 −1

Masques Sobel

1 0 −12 0 −21 0 −1

1 2 10 0 0−1 −2 −1

Récupérer les fonctions suivantes permettant de réaliser :

— convolution_separable(I,hx,hy) qui effectue le produit de convolution discret 2d entreune image I et un masque de convolution séparable, i.e. qui peut être décomposé en deuxmasque 1d hx et hy. L’intérêt de la séparabilité est d’accélérer les calculs. Dans ce TME,on aura besoin uniquement d’effecter des convolution avec des filtres séparables.

— gauss1d(N) qui permet de créer un masque gaussien mono-dimensionnel de taille N .L’écart type σ du masque sera déterminé de sorte que σ = bN−1

6 c, où bxc est la partieentière de x.

— [JAff] = affichePts(I,Rb,echelle) qui affiche les points détectés dans l’image I, àpartir de la carte binaire Rb et de l’échelle utilisé.



Exercice 1 — Calcul du critère de Harris

1. Mettre au point une méthode caculR(I, echelle), qui renvoie la carte des coins R(x, y)(équation 6.4), à partir d’une image I et pour une échelle (i.e. taille de fenêtreW ) donnée.On utilsera ici k = 0.04. Cette méthode effectuera les opérations suivantes :

(a) Calcul des dérivées directionnelles Ix et Iy, en utilisant la fonctionconvolution_separable(I,hx,hy) fournie. On utilisera ici le masque simple Gradient(voir au début).

(b) Calcul de I2x, I2

y et Ix · Iy.(c) Convolution de chacune des images précédentes (I2

x, I2y et Ix · Iy) par un masque

Gaussien de taille N, afin d’obtenir les éléments de la matrice M .(d) Calcul de det(M(x, y)) et trace(M(x, y)).

(e) Calcul deR(x, y) = det(M)− k · [trace(M)]2. On utilsera ici k = 0.04.

2. Interprétation de la carte des coins :— Mettre au point un script exo1 qui permet de visualiser la carte des coins R sur l’image

"house.jpg". On utilisera ici une fenêtre de taille W = 15 pixels.— Interpréter en fonction des structures présentes dans l’image (coins, zones homogènes,

contours). Vérifier que le critère de Harris fournit une méthode pour détecter conjoin-tement contours et coins.

Exercice 2 — Mise en place du détecteur de HarrisÀ partir de la carte des coins R(x, y) calculée comme indiqué à l’exercice 1, on demande de

mettre en place les fonctions pour détecter les coins.1. Mettre au point une méthode Rb = seuilleR(R,S), qui binarise la carte des coins R en

fonction d’un seuil S.2. Mettre au point une méthode Rnms = nms(R,Rb) qui effectue une suppresion de non

maxima locaux à partir de la carte des coins R et de sa version binariée Rb. On utiliseral’algorithme suivant :— Pour chaque pixel (x, y), on teste dans un voisinage (x ± 1, y ± 1) si R(x, y) est un

maximum local.— Si ce n’est pas le cas, on effectue : Rb(x, y)← 0

3. Évalutation du détecteur de coins— Mettre au point un script exo2 qui effectue la détection de points d’intérêt sur l’image

"house.jpg". On utilisera ici une fenêtre de taille W = 15 pixels.— Visualiser les résultats en utilisant la méthode affichePts(I,Ib,echelle).— Analyser les performances du détecteur en faisant varier le seuil de détection.

4. Question Bonus (pour la fin) : Une méthode simple pour effectuer une détection multi-échelle consiste à calculer le critère de Harris pour différentes échelles, et à effectuer lasuppression de non-maxima conjointement dans le plan image et dans l’espace échelle.Tester cette méthode sur l’image "house.jpg".



Exercice 3 — Propriétés du détecteur de HarrisOn va évaluer la robustesse (i.e. invariance) du détecteur de Harris par rapport à certaines

transformations.1. Mettre en place un script exo3 qui effectue la détection de points d’intérêt sur les deux

images contenues dans les matrices "toyHorse1.mat" et "toyHorse2.mat" fournies, à uneéchelle de W = 15 pixels.

2. Quelle est la dynamique pour chacune de ces deux images ?3. Quelles sont les transformations principales entre les deux images ?4. Avec un seuil de détection fixe, est-il possible avec la chaîne de traitement actuelle d’être

invariant :— À la rotation ? Pourquoi ?— Aux transformations affines de luminosité ? Pourquoi ?

— Faire en sorte d’avoir un seuil de binarisation dépendant de la dynamique de l’image(voir TD).

— Valider le fait qu’on peut ainsi détecter sensiblement les mêmes points dans lesdeux images "toyHorse1.png" et "toyHorse2.png".


Semaine 7

Extraction de descripteurs Image

7.1 TD 7 : Extraction de Descripteurs Image

Exercice 1 — Images Intégrales

Une image intégrale Iint(x, y) consiste à former au pixel (x, y) la somme des valeurs desniveaux de gris I(x′, y′) à gauche et au-dessus du pixel (x, y) :

Iint(x, y) =∑

x′≤x, y′≤y,

I(x′, y′) (7.1)

Les images intégrales ont été utilisées pour calculer efficacement des caractéristiques, parexemple le descripteur SURF [1] (variante du descrpiteur SIFT, plus compacte et rapide à cal-culer), ou encore les ondelettes de Harr pour la détection de visages [7].

(a) Iint(x, y) (b) (c) Iθint(x, y) (d)

Figure 7.1 – Image intégrale (a) et somme dans une zone rectangulaire (b). Cas orienté : (c),(d)

1. Proposer un algorithme en une passe et linéaire en nombre de pixels pour calculer Iint(x, y).2. Montrer qu’il est possible de calculer la somme des valeurs à l’intérieur d’une zone rec-

tangulaire A∑

x′,y′∈AI(x′, y′) (figure 7.1b)) à partir de Iint(x, y), en effectuant uniquement

quatre opérations.


Une variante d’image intégrale consiste à calculer des sommes dans des régions rectangu-laires orientées, e.g. à π

4 (figure 7.1c)) :

Iθint(x, y) =∑

y′≤y, y′≤y−|x−x′|,

I(x′, y′) (7.2)

3. Proposer un algorithme en une passe pour calculer Iθint. Quelle est sa complexité ?4. Comment calculer efficacement la somme des valeurs dans la zones A de la figure 7.1d) ?

Exercice 2 — Détecteur de blobsUn détecteur de blobs est un filtre qui vise à extraire d’une image les régions dont la répartition

des niveaux de gris correspond à une distribution Gaussienne (normalisée en σ0) :

G(x0,y0,σ0)(x, y) =1

2πσ0e−

(x−x0)2+(y−y0)2

2σ0 (7.3)

Rappel : le Laplacien ∆ d’une image s’écrit I s’écrit ∆I = ∂2I∂x2 + ∂2I

∂y2

1. Montrer que argx,y

min ∆[G(x0,y0,σ0)(x, y)

]= {x0, y0}.

Interprétation : les minima du Laplacien d’une image Gaussienne correspondent à laposition du centre de la Gaussienne (x0, y0)

Généralisation :On considère maintenant une image convoluée avec le noyau gaussien L = I ? G(x0,y0,σ0).On rappelle que dans ce cas la convolution et la dérivation sont commutatifs, i.e. :∆L = ∂2L

∂x2 + ∂2L∂y2 = I ? ∂2G

∂x2 + ∂2G∂y2 = I ?∆G. On admettra le résultat suivant :

— Si I = G(x0,y0,σ0) et si on effectue la convolution par un noyau Gaussien de taillevariable G(x0,y0,σ), alors arg

x,y,σmin max ∆ [σ · L(x, y, σ)] = {x0, y0, σ0} [3].

2. Montrer que G(x0,y0,σ0) vérifie l’équation de la chaleur : ∂G∂σ = 12∆G.

3. En déduire que G(kσ) − G(σ) ≈ ∆G · (k − 1)σ. Conclure sur la possibilité de mettre aupoint un détecteur de blobs multi-échelle en convoluant une image par un filtre effectuantune différence de Gaussiennes.

SEMAINE 7. DESCRIPTEURS IMAGE 10 UPMC


7.2 TME 7 : Quantification Couleur - Re-cherche par le Contenu

L’objectif du TME consiste à :— Mettre au point un descripteur couleur de chaque image d’une base de données.— Utiliser ce descripteur dans une application de recherche par le contenu dans cette base :

identification des images de la base les plus similaires à une requête.

Exercice 1 — Calcul d’histogrammes HSVOn va représenter chaque image de la base par un histogramme couleur, dans l’espace HSV.Cet espace colorimétrique est dit perceptuel, i.e. deux couleurs d’apparence similaire auront desvecteurs HSV proches (plus que dans l’espace RGB par exemple).

1. Mettre au point une fonction iv=quantification(v, K) qui effectue une quantificationuniforme d’une valeur v ∈ [0; 1] avecK intervalles, i.e. renvoie l’intervalle de quantificationiv correspondant à v.Indication : pour v ∈ [0; 1[, floor(v ·K) + 1 renvoie l’intervalle de quantification iv ∈{1;K}. Si on veut considérer v ∈ [0; 1], il faudra considérer séparemment le cas v = 1, etrenvoyer dans ce cas iV = K.

2. Mettre au point une fonction [Iq,histo]=quantificationImage(I, nH,nS,nV), qui àpartir d’une image I de taille N × M au format HSV et du nombre d’intervalles dequantification nH,nS et nV souhaités pour H, S et V, renvoie :— L’image Iq : une image de taille N ×M × 3 qui contient pour chaque pixel les indices

de quantification en H, S et V.— L’histogramme 3D histo de taille nH ×nS×nV qui compte le nombre de pixels pour

chaque bin de quantification (iH, iS, iV ).3. Mettre au point une fonction histon= normalisehisto(histo) qui normalise un histo-

gramme 1D histo, à partir de la norme `2 (i.e. euclidenne).4. Utiliser le script testHSVHisto comme squelette pour calculer l’ histogramme HSV nor-

malisé d’une image de la base. Vous devez insérer vos fonctions quantificationImage etnormalisehisto précédentes. Ce script effectue les opérations suivantes :(a) Ouverture d’une image et conversion RBG→HSV (fonction rgb2hsv de matlab).(b) Calcul de palette couleur pour l’affichage(c) Quantification de l’image, puis visualisation de l’image quantifiée à partir de la palette(d) Transformation de l’histogramme 3D → histogramme 1D, normalisation de l’histo-

gramme 1D et visualisation de cet histogramme(e) Affichage des 5 couleurs dominantes présentes dans l’image à partir de l’histogramme

normaliséExemple : Tester ce script sur l’image "Paysages67.png" avec nH = 12, nS = 3 etnV = 8. Vérifier que vous obtenez une image quantifiée conforme à celle de la figure 7.2b),ainsi qu’un histogramme normalisé et les couleurs dominantes présentées aux figures 7.2c)et 7.2d), respectivement. Faire varier le nombre de bins de quantification nH, nS et nVet analyser l’évolution de l’image quantifiée. Présenter les résultats sur différentes imagesde la base.



a) ’Paysages67.png’ b) ’Paysages67.png’ quantifiée

c) histogramme HSV (288 bins) d) 5 couleurs dominantes

Figure 7.2 – Calcul d’histogrammes HSV

Exercice 2 — Similarité entre images : recherche par le contenu

1. Utiliser le script similaritySearch comme squelette pour calculer les histogrammes HSVpour l’ensemble de 1040 images de la base. Ce script sauvegardera l’ensemble des descrip-teurs calculés (ListHist.mat). Vous pourrez ensuite les charger et ne pas les recalculer(variable bcompute).

2. La similarité entre deux images de la base sera calculée par le produit scalaire entre leurshistogrammes HSV normalisés. Mettre au point une fonction sim=calculSimilarites()qui calcule la matrice de similarité (taille 10402) de l’ensembles des images de la base.— Mettre en place un script pour calculer la matrice de similarité pour l’ensemble de la

base, et la visualiser (comme une image). Commenter la forme de la matrice.3. Tester l’ensemble du script similaritySearch dans lequel les fonctions adéquates auront

été introduites. Vérifier que l’on obtient le résultat suivant sur l’image requête ’Lion-tigre1.png’ (indexQuery=350, figure 7.3). Tester le script sur d’autres images et analyserles résultats. Quelles sont les limitations d’une approche brute basée sur la similaritédans le cas d’applications de recherche par le contenu (par exemple retrouver les imagescontenant des lions ou des tigres dans la base) ?



Figure 7.3 – Exemple de résultat de recherche


Semaine 8

Analyse des Données -Reconnaissance de Visages

8.1 TD 8 : Analyse en Composantes Prin-cipales (ACP)

Exercice 1 — Dérivation du critère de l’ACP— Soit un vecteur aléatoire X ∈ Rd, et g l’estimateur de espérance mathématique de X :

g = 1n

n∑i=1

Xi ≈ E[X] où Xi sont des réalisations de la variable aléatoire X.

— On considère la projection Π de X sur une droite vectorielle V définie par le vecteur −→vunitaire (||−→v || = 1). On note v les coordonnées de −→v dans Rd, on a (voir annexe 8.1.1.1) :Π = vv> et v>v = 1.

— La variance σ2v de X sur V s’écrit :

σ2v(X) =

1

n− 1

n∑i=1

((Π (Xi − g)

)>Π(Xi − g)

) (=

1

n− 1

n∑i=1

||Π(Xi − g)||2)

(8.1)

1. Montrer que σ2v(X) = 1

n−1

n∑i=1

(Xi − g)>vv>(Xi − g)

2. En déduire que σ2v(X) = v> Σ v, où Σ = 1

n−1

n∑i=1

(Xi − g)(Xi − g)> est la matrice de

variance-covariance de X.

Le principe de l’Analyse en Composantes Principales (ACP) consiste à déterminerle vecteur −→v unitaire qui maximise σ2

v(X). On cherche donc v qui maximise v> Σ v, sousla contrainte v>v = 1. {

maxv,λ

v>Σv

s.c. v>v = 1(8.2)


Pour résoudre ce problème, on définit le Lagrangien L(v, λ) (voir annexe 8.1.1.2) :

L(v, λ) = v>Σv − λ(1− v>v) (8.3)

3. En utilisant les conditions nécessaires du 1er ordre données à l’annexe 8.1.1.2, montrer

que la maximisation de 8.3 conduit à :{

Σv = λvv>v = 1

4. En déduire que l’équation 8.3 peut être résolue en diagonalisant la matrice Σ. Quelle estalors la variance σ2

v(X) pour un couple vecteur propre - valeur propre (vi, λi) ?5. Conclusion : proposer une méthode pour déterminer la droite V maximisant la variance

des données définie à l’équation 8.1.

8.1.1 Annexes8.1.1.1 Projection orthogonale sur une droite vectorielle

Dans un espace vectoriel E de dimension finie, la projection orthogonale Π sur une sous-espace S de E est un opérateur linéaire, et peut donc étre représentée par une matrice PS. SoitZ une matrice dont les colonnes forment une base orthonormée du sous-espace S, la projectionorthogonale u = Π(x) d’un vecteur x est donnée par :

u = Π(x) = Z × Z> × x = PS × x (8.4)

Dans le cas de la projection sur une droite vectorielle, on a Z = v où v est un vecteur unitairedirecteur de la droite. La matrice de projection s’écrit donc PS = v × v>.

8.1.1.2 Optimisation sous contraintes : multiplicateurs de Lagrange

On considère X = (x1, ..., xn) ∈ Rn, et le problème suivant : maxXf(X) sous la contrainteh(X) = 0, où f est quadratique en X, et h linéaire. On appelle Lagrangien associé à ce problèmela fonction L(X,λ) :

L(X,λ) = f(X) + λ · h(X) (8.5)

Le Lagrangien permet d’introduire la contrainte dans la fonction objectif avec une certainepénalité λ. On se retrouve ainsi à maximiser une fonction à n + 1 variables (X et λ) sanscontrainte.

On peut montrer que les conditions suivantes (du premier ordre) sont nécessaires pour maxi-miser f sous la contrainte h :

∂L

∂xi= 0 ∀ i

∂L

∂λ= 0

⇔

∂f

∂xi= λ

∂h

∂xi∀ i

h(X) = 0

(8.6)

SEMAINE 8. ANALYSE DES DONNÉES 15 UPMC


8.2 TME 8 & 9 : Reconnaissance de Vi-sages par Eigenfaces

L’objectif du TME est d’étudier les propriétés de la méthode de reconnaissancede visages « eigenfaces ».

On développera un système capable :— d’identifier un visage parmi une base de données de visages de référence— de déterminer si une image contient un visage présent dans la base de données— de reconnaître si une image représente un visage ou nonOn appliquera les outils développés sur la base de visages Yale Face Database.

8.2.1 Principe général

Figure 8.1 – Principe général d’un système de reconnaissance de visages

Le problème de la reconnaissance de visages est défini comme suit : étant donnée une image devisage, on souhaite déterminer l’identité de la personne correspondante. Pour ce faire, il est né-cessaire d’avoir des images de référence, sous la forme d’une base de données de visages de toutesles personnes connues par le système. A chaque visage est associé un vecteur de caractéristiques.Ces caractéristiques sont supposées être invariantes pour une même personne, et différentes d’unepersonne à l’autre. La reconnaissance consiste alors à comparer le vecteur de caractéristiques du



visage à reconnaître avec celui de chacun des visages de la base. Ceci permet de retrouver lapersonne ayant le visage le plus ressemblant, qui est celui dont le vecteur est le plus similaire.

Il existe plusieurs types de méthodes, qui se distinguent par le type de caractéristiques utilisées(voir [5] pour un état de l’art) :

— Les approches par modèles de visage procèdent à une analyse biométrique des visagespour déterminer des mesures telles que la distance entre les yeux, la longueur du nez, laforme du menton...

— Les approches « image » comparent au contraire directement les visages, en les considérantcomme des images, pour lesquelles des mesures de similarité pré-attentives (sans modèlea priori) sont définies.

— Des approches hybrides utilisent les notions de similarité entre images, mais en rajoutantdes connaissances a priori sur la structure d’un visage.

8.2.2 Analyse par eigenfaceLa reconnaissance de visages par eigenfaces est une approche de type « image ». Chaque image

de visage est considérée comme un vecteur dans un espace ayant autant de dimensions que depixels dans l’image. Les caractéristiques de l’image sont extraites par une méthode mathématiquede réduction de dimensionnalité basée sur l’analyse en composante principales (ACP). Cetteapproche a été originellement proposée par Turk et Pentland1 en 1991 [6].

Dans la suite, nous utiliserons la notation italique pour désigner les scalaires (m,K, . . . ) etles vecteurs (x, u), ainsi que le gras pour les matrices (X,Xc,W, . . . ).

On note x les images des visages, resprésentées comme un vecteur à d composantes, et x(i)(i =1..n) le pixel numéro i de cette image. Un ensemble de visages forme donc un nuage de pointsdans un espace Rd. On note xtraink (k = 1..Ntrain) l’image du visage de référence numéro k, etxtestk (k = 1..Ntest) l’image du visage de test numéro k.

On note xmoy la moyenne des visages de référence, ou « visage moyen ». Le principe de laméthode des eigenfaces est de modéliser la différence d’un visage quelconque par rapport à cevisage moyen par un ensemble limité d’images uh, appelées eigenfaces (voir [6]). Une image devisage x ∈ Rd est donc exprimée comme le visage moyen auquel s’ajoute une combinaison linéaired’eigenfaces :

x = xmoy +∑h

ahuh + ε (8.7)

où ah représente le poids de l’eigenface d’indice h dans le visage x, et ε représente l’erreurentre x et son approximation par les eigenfaces. Les coefficients ah jouent un rôle très importantpour la reconnaissance des visages, car ils correspondent aux coordonnées du visage x dans lesous-espace des visages.

La méthode des eigenfaces repose sur le fait que le nombre d’eigenfaces considérées est bieninférieur à la dimension totale de l’espace, ce que l’on appelle « réduction de dimensionnalité ».Les images sont donc analysées dans un sous-espace de dimension réduite, qui représente plusspécifiquement les visages, parmi tous les types d’images possibles.

Le visage moyen étant toujours le même pour une base de référence fixée, nous considè-rerons dans la suite systématiquement chaque visage sous sa forme centrée, c’est-à-dire aprèssoustraction du visage moyen.



8.2.3 Base de données de visagesOn va ici utiliser la base d’images « yalefaces » 1. Dans cette base, les visages ont tous été

traités, afin de les recaler et rogner à la taille 64×64 pixels, de sorte que les images puissent êtrecomparées pixel à pixel.

Cette base contient 120 images en niveaux de gris, représentant les visages de 15 individus.Il y a 8 images par individu, chacune correspondant à une catégorie d’images variant selon lescritères suivants (figure 8.2) :

— variation de l’expression du visage : normal, sad, sleepy, surprised, wink, happy— variation des accessoires : glasses, noglasses,

Figure 8.2 – illustration des catégories de prise de vue

La base d’images est divisée en deux groupes : l’un des groupes va être utilisé comme jeud’entrainement, l’autre groupe comme jeu de test.

La base de référence contient n images, chacune ayant un nombre de pixels d = nl · nc. Pourl’instant, on a 6 images par catégorie dans la base d’entrainement, d’où n = 6 · 15 = 90. Chaqueimage est de taille 64× 64, d’où d = 4096.

Dans la suite, nous manipulerons toujours les images de visage sous la forme de vecteurs,et un ensemble de visages sous la forme d’une matrice dont chaque colonne est un visage. SousMatlab, les images seront stockées dans des matrices de réels (double). En général, les imagesseront stockées dans une matrice X de taille d× n :

X = [x1, ..., xn] (8.8)

Cette matrice sera déclinée en Xtrain et Xtest de tailles d×Ntrain et d×Ntest.On utilisera aussi les vecteurs id et cat, qui contiennent des informations sur le contenu des

images (id(k) et cat(k) sont respectivement l’indice de l’individu de l’image k, et la catégorie àlaquelle appartient l’image). Encore une fois ces vecteurs existeront pour train et pour test.

1. Cette base de visages a été développée à l’université de Yale, voir http://vision.ucsd.edu/content/yale-face-database


http://vision.ucsd.edu/content/yale-face-database

http://vision.ucsd.edu/content/yale-face-database


Exercice 1 — Chargement de la base et centrage des visagesPour charger les images, on chargera simplement le fichier de données Matlab YaleFaces.mat

disponible à l’adresse http://webia.lip6.fr/~robert/cours/bima/data/YaleFaces.mat. Celafourni les matrices et vecteurs Xtrain,Xtest, idtrain, idtest, cattrain, cattest.

1. Mettre au point une fonction pour calculez le visage moyen xmoy.Indication : utiliser la fonction mean de Matlab.

2. Mettre au point une fonction pour centrer les visages.3. Dans un script, charger la base d’images, affichez le visage moyen, ainsi que quelques

visages accompagnés des visages centrés associés. Voici un exemple de résultat attendu :

Figure 8.3 – Visage moyen et centrage de la base


http://webia.lip6.fr/~robert/cours/bima/data/YaleFaces.mat


Exercice 2 — Calcul des Eigenfaces (ACP)La méthode développée par Turk et Pentland [6] définit les eigenfaces comme les axes prin-

cipaux obtenus en effectuant l’Analyse en Composantes Principales des vecteurs associés auxvisages de référence. Les eigenfaces sont ainsi les vecteurs propres de la matrice de co-variance Xc×X>c , de taille d×d, où la matrice Xc de même taille que X représente l’ensembledes visages centrés :

Xc = [x1 − xmoy, ..., xn − xmoy] (8.9)

Chaque ligne de Xc correspond à un pixel p, chaque colonne de Xc correspond à un visage deréférence de numéro k.

Plutôt que d’utiliser la décomposition en valeurs propres, nous utiliserons la décomposition envaleurs singulières (DVS, ou singular value decomposition, SVD en anglais). La DVS décomposela matrice Xc de taille d× d en :

Xc = U× S×V> (8.10)

où U et V sont des matrices orthonormales (U×U> = U>×U = Idd et V×V> = V>×V =Ind ) de tailles respectives d × d et n × n, et S est une matrice d × n nulle partout sauf sur ladiagonale principale.

Cette décomposition présente les propriétés suivantes :— les colonnes de V sont les vecteurs propres de X>c ×Xc

— les colonnes de U sont les vecteurs propres de Xc ×X>c— la diagonale de S contient les valeurs singulières de Xc, égales à la racine carrée des valeurs

propres λk de X>c ×Xc et Xc ×X>c

Sous Matlab, la Décomposition en Valeurs Singulières peut-être calculée par la commande :[u, s, v] = svd(Xc)Dans notre cas, n < d, et les valeurs propres λk de Xc ×X>c sont donc toutes nulles pour

k > n. Nous n’aurons pas besoin des vecteurs propres associés k > n. La commande svd possèdeun mode « économique », qui ne calcule que les vecteurs propres correspondant aux colonnes dela matrice passée en argument :

[u, s, v] = svd(Xc, 0)Cette commande renvoie des matrices U, S et V de taille d× n, n× n et n× n : la matrice

U a été tronquée à ses n premières colonnes.

U = [u1, ..., un] (8.11)

1. Mettre au point une fonction [U,lambdas] = eigenfaces(Xc), qui à partir des imagescentrées de la base d’entraînement calcule la matrice U des eigenfaces, et les valeurspropres associés.

2. Dans le script principal, calculer les eigenfaces puis normaliser les valeurs propres afin queleur somme soit égale à 100%.

3. Affichez le visage moyen et les 15 premières eigenfaces (figure 8.4 (a)) et leurs valeurspropres associées. Quelle est l’interprétation de l’image des eigenfaces ?

4. Tracer la courbe de la somme cumulée des valeurs propres normalisées (figure 8.4 (b)),afin de voir combien de variation est capturée par les K premières eigenfaces. Combiend’eigenfaces sont nécessaires pour obtenir une « bonne » reconstruction ?



(a) 15 premières eigenfaces (b) somme cumulée des valeurs propres

Figure 8.4 – Eigenfaces

Exercice 3 — Projection dans le sous-espace des visagesDans la suite, nous utiliserons un nombre réduit d’eigenfaces afin de modéliser l’espace de

visages représenté sous la forme de la base WK des K premiers vecteurs propres :

WK = [u1, ..., uK ] (8.12)

Notez que les colonnes forment une base orthonormée, donc W>K ×WK = IKd .

La projection d’une image dans le sous-espace des visages se fait simplement ensoustrayant le visage moyen et en effectuant le produit scalaire de l’image obtenue avec chaqueeigenface. Ceci donne les coordonnées de l’image test dans le sous-espace des visages, qui est dedimension K.

Chaque visage possède donc plusieurs représentations :— Son image d’origine, représentée par un vecteur x dans Rn— Les coordonnées de l’image projetée z dans la base des eigenfaces, {ah}, h ∈ {1;K}

(sous-espace des visages) :z = W>

K × (x− xmoy) (8.13)

— Son image reconstruite dans l’espace d’origine Rn, x :

x = xmoy +∑h

ahuh = xmoy + WK × z (8.14)

L’erreur de reconstruction est est définie comme la distance entre une image et l’imagereconstruite associée :

Erecons(x) = ||x− x||2 =

√∑p

(x(p)− x(p))2 (8.15)



1. Mettre au point une fonction z = calculeProj(x,x_moy,K,W), qui à partir d’une imagex et de l’image moyenne xmoy calcule les coordonnées z dans le sous-espace WK (tronquéà la dimension K) des visages.

2. Mettre au point une fonction x_r = reconstruction(z,x_moy,W,K), qui à partir d’uneimage de la projection d’une image dans le sous-espace des visage de dimension K calculeles coordonnées de l’image projetée dans l’espace Rn de départ.

3. Mettre au point une fonction Er = erreur_Reconstruction(x_r,x), qui calcule l’erreurde reconstruction entre x et x.

4. Mettre au point une fonction affiche_Reconstruction(x_r,x), qui affiche l’image ini-tiale et la reconstruction obtenue pour plusieurs valeurs de K (par exemple, K = 5, 10,25, 50, 90).

5. Dans le script principal, tester les fonctions précédentes en affichant le résultat de laprojection/reconstruction pour plusieurs images (de la base d’entraînement et de test). Lafigure 8.5 montre le résultat de la reconstruction pour l’image 50 de la base d’appentissage.Pour l’image 55 de la base d’apprentissage, quelle est l’erreur de reconstruction pourK = n = 90 ? L’image est-elle identique à sa reconstruction ? Même question pour l’image17 de la base de test.

6. Conclusion : Y a-t-il une différence en terme de reconstruction entre les visages issus dela base d’entraînement et ceux issus de la base de test ? Pourquoi ?

7. Question bonus : Tracez l’évolution de la moyenne de l’erreur de reconstruction des visagesde test lorsque K varie de 1 à N . Cette évolution est-elle cohérente avec la somme cumuléeprécédemment calculée (exercice 2, question 4) ?

Figure 8.5 – Exemple de reconstruction pour l’image 50 d’apprentissage



Exercice 4 — Reconnaissance de visage : identificationA chaque visage de référence xtraink est associée une identité, sous la forme d’un numéro

idtrain(k). Nous chercherons dans cette partie à identifier un visage xtest à partir des visages deréférence.

La méthode la plus simple consiste à comparer la projection ztest du visage test xtest avecla projection ztraink de chaque image de référence xtraink (voir Fig 8.6). La dissimilitude entre lesdeux est quantifiée par la distance dans le sous-espace Ek(xtest) :

Ek(xtest) = ||ztest − ztraink ||2 (8.16)

Figure 8.6 – Projection d’une image J sur le sous-espace des visages et comparaison avec unvisage de référence Ik, dans le cas K = 2.

En évaluant cette distance pour chaque visage de référence, on peut déterminer le visage deréférence xtraink le plus proche du visage test xtest. Son identifiant idtrain(k) permet alors lareconnaissance du visage de test.

1. Quel est l’intérêt de calculer la distance Ek(xtest) dans le sous-espace des visages plutôtque dans l’espace de départ ?

2. Mettre au point une fonction D = calculMatDist(Xc_train,Xc_test,W,K), qui à partirde l’ensemble des images centrées d’apprentissage (Xtrain

c , taille d×Ntrain), de l’ensembledes images centrées de test (Xtest

c , taille d ×Ntest), des eigenfaces W et de leur nombreconservé K calcule la matrice de distance entre les visages de test et de train (tailleNtest ×Ntrain).

3. Mettre au point une fonction id_test_hat = identification(D), qui à partir de lamatrice des distances calcule le vecteur id

testde taille Ntest donnant l’indice du visage de

train le plus proche de chaque visage de test.

4. Dans le script prinicpal, calculer pour K = 30 le taux d’identification en comparant idtest

aux labels idtest. Faire ensuite varier K, et tracer la courbe du nombre de visages reconnusen fonction de K. Expliquer la forme de la courbe obtenue. Quelle valeur de K peut-onprendre pour avoir une bonne reconnaissance et un temps de calcul faible ?

5. Bonus : pour K = 30, calculez pour chaque visage du jeu de référence sa distance dansle sous-espace par rapport à l’ensemble des visages de référence. On pourra par exemplevisualiser le résultat sous la forme d’une image de matrice. Que constate-t-on ?



6. Bonus : Quelles sont les distances min et max entre deux visages de la même classe (mêmepersonne) ? Entre deux visages de classes différentes ? Si on veut mettre en place un seuilθ pour détecter la présence d’un visage inconnu, quelles indications nous apportent lesvaleurs min/max précédentes ?

Exercice 5 — Classification visage/non-visageJusqu’à présent, nous nous sommes attachés à comparer des images de visage entre elles.

Mais la méthode fournit des informations que nous n’avons pas encore utilisées. En particulier,l’erreur de reconstruction peut être utilisée pour vérifier qu’une image est bien une image devisage. Lorsqu’une image contient autre chose qu’un visage (image de fleur, une personne vue enentier, une image aléatoire...), nous dirons qu’il s’agit d’un « non-visage » (base noface).

Figure 8.7 – Illustration des cas possibles de classification d’une image : cas 1,2) Z proche dusous-espace : il s’agit d’un visage cas 3,4) Z loin du sous-espace : il ne s’agit pas d’un visage cas1) Z visage identifié cas 2) Z visage inconnu cas 3) risque d’identifier Z avec un visage alors qu’iln’en est pas un.

1. Calculer l’erreur de reconstruction des images de la base et des images de test de la basevisages (pour K = 30), et tracer la courbe de l’erreur dans les 2 cas. Calucler l’erreurmoyenne dans les deux cas, ainsi que l’erreur min pour les non-visages, et l’erreur maxpour les visages. Quel conclusion pouvez-vous en tirer ?

2. Visualiser l’erreur de reconstruction en affichant l’image originale et l’image reconstruitepour 10 images de la base de visages, et pour les 10 images de la base de non-visages.Commentaire ?


Semaine 9

Analyse Discriminante

9.1 TD 9 : Analyse Discriminante LinéaireSoit un vecteur aléatoire X ∈ Rd. On considére un ensemble de n réalisations Xi de X,

i ∈ {1;N}. On considère également un ensemble d’étiquettes Yi associées à chaque Xi, corres-pondant à l’annotation de K classes : Xi ∈ Ck ⇔ Yi = k (k ∈ {1;K}).

L’Analyse Discriminante Linéaire (ADL) consiste à déterminer des facteurs discrimi-nants, combinaisons linéaires des variables descriptives d’origine, qui prennent des valeurs lesplus proches possible pour des éléments de la même classe, et les plus éloignées possible entreéléments de classes différentes. Mathématiquement, l’ADL se formule comme la recherche de laprojection des données de manière à avoir :

— Une variance intra-classe minimale— Une variance inter-classe maximale

Exercice 1 — Décomposition de la variance totale

Soit g un estimateur l’espérance mathématique de X : g =1

N

N∑i=1

Xi. On note Nk le nombre

d’éléments de la classe k (Nk = card(Ck)) et gk le centre de gravité de la keme classe : gk =1

Nk

∑i∈Ck

Xi.

La variance totale des données de la maniére suivante :

σ2(X) =1

N

N∑i=1

(Xi − g)> (Xi − g) =1

N

K∑k=1

∑i∈Ck

(Xi − g)> (Xi − g) (9.1)

On note SS(k) =1

N

∑i∈Ck

(Xi − g)> (Xi − g)

1. Montrer que SS(k) peut se décomposer sous la forme :

SS(k) =1

N

[∑i∈Ck

(Xi − gk)>(Xi − gk)

]+NkN

(gk − g)>(gk − g) (9.2)


2. En déduire que la variance totale σ2(X) peut se décomposer sous la forme :σ2(X) = σ2

b (X) + σ2w(X), où :

— σ2w =

K∑k=1

NkNσ2k,w est la moyenne (pondérée) des variances intra-classe (« within »), la

variance intra-classe classe étant définie par : σ2k,w =

1

Nk

∑i∈Ck

(Xi − gk)>(Xi − gk).

— σ2b =

K∑k=1

NkNσ2k,b avec σ2

k,b = (gk − g)>(gk − g) est la variance des moyennes gk des

classes (variance inter-classe, « between »).

Exercice 2 — Variance Projetée et solution de l’ADLOn considère la projection Π de X sur une droite vectorielle V définie par le vecteur −→v

unitaire (||−→v || = 1). On note v les coordonnées de −→v dans Rd, on a : Π = vv> et v>v = 1.

Rappel : La variance totale projetée sur V s’écrit : σ2v = v>Σv, avec Σ = 1

n−1

n∑i=1

(Xi−g)(Xi−g)>

(TD ACP).1. Montrer que la variance intra-classe projetée sur V s’écrit : σ2

v(w) = v>Wv, avec :

— W =1

N

K∑k=1

NkWk

— Wk =1

Nk

∑i∈Ck

(Xi − gk)(Xi − gk)>

2. Montrer que la variance inter-classe projetée sur V s’écrit : σ2v(b) = v>Bv, avec :

— B =1

N

K∑k=1

Nk(gk − g)(gk − g)>

3. La variance projetée se décompose aussi sous la forme : σ2v = σ2

v(w) + σ2v(b), puisque les

points projetés sont toujours des points deRd. L’Analyse Discriminante Linéaire consiste àchercher l’axe V maximisant σ2

v(b) et minimisant σ2v(w). En déduire que la droite recherchée

vérifie J(v) = maxv

(v>Bv

v>Σv

)4. On remarquera que J(v) est invariant aux transformations v ← αv (changement d’échelle).

On peut donc choisir v tel que v>Σv = 1. Écrire alors le Langrangien correspondant auproblème d’optimisation sous contraintes.En utilisant la technique des multiplicateurs de Lagrange (TD ACP), montrer qu’une

condition nécessaire à la maximisation de J(v) =

(v>Bv

v>Σv

), sous la contrainte v>Σv = 1,

est : Bv = λΣv, avec λ =v>Bv

v>Σv.

Indication : on admettra que∂(v>Bv

)∂v

= 2Bv et∂(v>Σv

)∂v

= 2Σv.

5. Conclusion : En déduire que la détermination de l’ADL consiste à diagonaliser Σ−1B,le vecteur propre de valeur propre maximale définissant l’axe solution de l’ADL.

SEMAINE 9. ANALYSE DISCRIMINANTE 26 UPMC




9.2 TME 9 : Fin du TME sur Eigenfaces


Semaine 10

Segmentation - découpage/fusion

10.1 TD 10 : Segmentation

Exercice 1 — Principe du découpage

1. À partir de l’exemple vu en cours proposer un algorithme récursif de segmentation pardécoupage qui produit un Quadtree (arbre 4-aire).

2. Illustrer le fonctionnement de l’algorithme sur l’image 64 × 64 suivante (chaque élémentde la grille représente un carré 8× 8) :

On construira au fur et à mesure l’arbre 4-aire.3. Quel prédicat de découpage peut-on utiliser pour segmenter correctement cette image ?


4. Calculer les moyennes et variances de chaque feuille de l’arbre (les niveaux de gris dufond, du carré et du rectangle sont respectivement à 150, 50 et 100).

5. On considère la même image à laquelle nous ajoutons un bruit gaussien de moyenne nulleet de variance 25. Quel seuil faut-il appliquer pour obtenir le même Quad-tree qu’auxquestions précédentes ?

Exercice 2 — Implémentation

1. Pour représenter un découpage Quadtree d’une image, nous utilisons une matrice creusedont chaque élément représente un bloc (une feuille du Quadtree) et telle que :— la position d’un élément donne la position du bloc correspondant dans l’image— la valeur d’un élément donne la taille du bloc correspondant. Le bloc est nécessairement

carré.Donner la représentation en matrice creuse pour l’exemple de l’exercice précédent.

Matrices creusesUne matrice creuse est une représentation compacte en mémoire des matrices : seulsles éléments non nuls sont représentés en mémoire. Une telle matrice se définie avec lafonction sparse. L’appel :

A = sparse ( 100 , 3 0 ) ;

créé une matrice A creuse de taille 100 par 30. L’appel :

B = f u l l (A) ;

reconstruit une matrice pleine à partir d’une matrice creuse. La plupart des opérateurset fonctions matlab travaillent indifféremment sur des matrices pleines ou creuses. Pouraccéder de façon transparente aux éléments d’une matrice creuse, on utilisera la fonctionfull. Exemple :

>> A = sparse ( 2 , 3 ) ;>> A(1 ,1 ) = 2 ;>> Aans =

(1 ,1 ) 2>> A(1 ,2 )ans =

Al l ze ro sparse : 1−by−1>> f u l l (A( 1 , : ) )ans =

2 0 0

2. Proposer un prédicat de découpage basé sur l’homogénéité des régions et écrire la fonctionMatlab récursive qui implémente l’algorithme précédent avec comme sortie la représenta-tion en matrice creuse vue dans la question précédente. Cette fonction aura la signaturesuivante :

function S = qtdecomp ( I , thresh , mindim)%%% Rea l i s e un decoupage en Quad Tree de l ’ image I .%%% thre sh e s t l e s e u i l qu i dec l enche l e decoupage .%%% mindim e s t l a t a i l l e minimale des b l o c s e t

SEMAINE 10. SEGMENTATION 30 UPMC


Exercice 3 — Fusion des blocs d’un Quadtree

1. À partir de l’exemple de fusion vu en cours, écrire un algorithme de fusion des régionsd’un Quadtree.

2. Un tel algorithme est-il implantable (à un coût raisonnable) dans Octave ? Quelles sontles difficultés ?

3. Pour la suite de cet exercice, nous optons pour un algorithme de fusion plus simple : tousles pixels des régions vérifiant le prédicat d’homogénéité seront mis à la valeur 1, les autrespixels auront la valeur 0. Répondez aux questions suivantes :— Quelle propriété statistique auront les pixels ayant l’étiquette 1 ?— Est-possible d’obtenir des pixels étiquettés à 1 qui soit isolés ?— A-t-on une région étiquettée à 1 ou plusieurs ?— Quelle est la taille minimale de chaque région connexe ?

4. À l’aide de la fonction qtgetblk, écrire la fonction function [F] = fusion( S, I , thresh) quiapplique l’algorithme de fusion proposé à la question précédente. S est la matrice creusereprésentant le Quadtree, I est l’image à fusionner et thresh est le seuil d’homogénéité.Voici la documentation Matlab de la fonction qtgetblk :

[ va l s , r , c ] = qtge tb lk ( I , S , dim) r e tu rn s in va l s an arrayconta in ing the dim−by−dim blocks in the quadtree decomposit ion o fI . S i s the sparse matrix returned by qtdecomp ; i t conta in s thequadtree s t r u c tu r e . va l s i s a dim−by−dim−by−k array , where k i s thenumber o f dim−by−dim blocks in the quadtree decomposit ion ; i f the reare no b locks o f the s p e c i f i e d size , a l l outputs are returned asempty matr i ce s . r and c are ve c to r s conta in ing the row and columncoo rd ina t e s o f the upper l e f t co rne r s o f the b locks .

Exercice 4 — Fusion globaleNous souhaitons modifier le code précédent pour que l’ensemble des pixels segmentés reste

homogène en distribution de niveaux de gris. Pour cela, on veut s’assurer que lorsqu’on fusionneun nouveau bloc, l’ensemble des blocs déjà fusionnés reste homogène en distribution de niveauxde gris, c’est-à-dire que leur écart-type reste en dessous d’un seuil.

1. Soit deux régions R1 et R2 de moyenne et écart-type respectivement notés µ1, σ1, µ2 etσ2. Calculer l’écart-type de R1 ∪R2.

2. Modifier la fonction fusion de façon à réaliser la fusion d’un bloc si l’écart-type de l’en-semble des blocs étiquetté à 1 est plus petit que le seuil thresh. Cette nouvelle fonctionsera nommée fusiong (fusion globale).



10.2 TME 10 : SegmentationPour ce TME, on peut récupérer les m-files et images du répertoire ~bereziat/bima y com-

pris les fichiers qtdecomp.m et qtgetblk.m.

Exercice 1 — Expérimentation du découpage

1. Notre algorithme est limité aux images carrées dont les dimensions sont en puissance de2. Nous souhaitons lever cette limitation.Soit une image de dimension quelconque. Calculer la plus petite valeur n telle que 2n soitplus grand que la largeur et la hauteur de l’image.Écrire la fonction function J = expand( I) qui retourne la plus petite image carrée dontla taille est une puissance de deux et qui contient, à partir de l’élément (1, 1), l’image I.Les pixels supplémentaires sont mis à la moyenne de l’image I.Indication : utiliser les fonctions log2 et floor.

2. Écrire une fonction n = numreg(S) qui permet de compter le nombre de régions/blocsdans un découpage Quadtree S.

Indication : utiliser la fonction find appliquée au Quadtree !

3. Écrire la fonction function [Q] = quaddraw(I,S) qui, données une image I et sa repré-sentation Quadtree en matrice creuse S, retourne l’image I à laquelle on superposera unquadrillage rouge représentant la décomposition Quadtree. Ainsi Q(i, j) contient soit levecteur (255, 0, 0) si le pixel (i, j) est au bord d’une région du Quadtree, soit le vecteur(g, g, g) avec g tel que g = I(i, j).

Indication : on s’inspirera de la fonction fusion vue en TD pour obtenir la liste desblocs, et on remplira, bloc par bloc, l’image à produire.

4. Dans un m-file split.m, réunir les instructions pour :— lire une image— étendre cette image à une taille en puissance de 2— réaliser le découpage en Quadtree selon le critère d’homogénéité,— afficher l’image retournée par la fonction quaddraw.Tester le m-file sur un nombre significatif d’images (au moins trois) : pour chaque expé-rience, produire un fichier split_xxx.m spécifique.

Exercice 2 — Expérimentation de la fusion

1. Compléter le m-file split.m avec l’algorithme de fusion vu en TD pour créer un m-filesplitmerge.m.On utilisera la fonction bwlabel pour attribuer un indice distinct pour chaque composanteconnexe de l’image retournée par la fonction fusion et la fonction label2rgb pour obtenirune représentation colorée.

2. Tester l’algorithme sur un nombre significatif d’images en trouvant, pour chaque image,le paramétrage optimal.

3. Même question avec l’algorithme de fusion globale. Comparer les résultats des deux algo-rithmes sur un même jeu de données. A chaque expérience de comparaison fusion locale



et fusion globale doit correspondre un fichier splitmerge_xxx.m dédié.



Bibliographie

[1] H. Bay, A. Ess, T. Tuytelaars, and L. Vangool. Speeded-up robust features (surf). ComputerVision and Image Understanding, 110(3) :346–359, June 2008.

[2] C. Harris and M. Stephens. A combined corner and edge detector. In Proc. Fourth AlveyVision Conference, pages 147–151, 1988.

[3] T. Lindeberg. Scale-Space Theory in Computer Vision. Kluwer, December 1993.[4] Hans Moravec. Obstacle avoidance and navigation in the real world by a seeing robot rover. In

tech. report CMU-RI-TR-80-03, Robotics Institute, Carnegie Mellon University and doctoraldissertation, Stanford University, number CMU-RI-TR-80-03. September 1980.

[5] S.A. Sirohey, C.L. Wilson, and R. Chellappa. Human and machine recognition of faces : Asurvey. 1994.

[6] Matthew Turk and Alex Pentland. Eigenfaces for recognition. J. Cognitive Neuroscience,3(1) :71–86, 1991.

[7] P.A. Viola and M.J. Jones. Robust real-time face detection. IJCV, 57(2) :137–154, May 2004.

BIBLIOGRAPHIE 34 UPMC

Documents

BIMA Bases de l’IMAgerie Énoncés de TD/TME …webia.lip6.fr/~thomen/Teaching/BIMA/td-tme/Livret2_4I600_2016.pdf · Énoncés de TD/TME Séances 6-10 Master 1 Informatique - Spécialité