Techniques d'indexation et recherche
multimédia
Chap5-Evaluation des performances des SRI
Amira BELHEDI [Link]@[Link]
Fadoua MHIRI [Link]@[Link]
Wafa ABID [Link]@[Link]
ISTIC 2021-2022
Plan du chapitre
• Notions de rappel et précision
• Mesures de similarité utilisées dans les systèmes
de recherche d’images par le contenu
2/32
Introduction
• Comment déterminer le système qui satisfait au
mieux l’utilisateur ?
• Comparer les SRI de manière théorique
– Problème non résolu, pas de modèle générique
Tester les résultats d’un système
3/32
Introduction
• Un SRI doit satisfaire un besoin d’information d’un
utilisateur (les documents pertinents)
– Pertinence utilisateur: satisfaction de l’utilisateur
– Pertinence système: estimation de l’efficacité du
système
• Pertinence utilisateur ≠ pertinence système
• But de l’évaluation: comparer les deux
• Rapprocher pertinence système et pertinence
utilisateur
4/32
Processus d’évaluation
• Mesurer la performance d’un SRI sur les même
données
5/32
Processus d’évaluation
• Collection de test = collection des documents
– Réaliste
– Couverture des problèmes
• Définir un ensemble de requêtes sur ce corpus
(requêtes résolues)
– Réaliste
– Evaluable
• Déterminer exhaustivement les données
– Pertinence pour chaque requête
– Manuellement (pertinence binaire)
6/32
Notion de Rappel et Précision
• Evaluation de la performance d’un SRI par le calcul
des deux mesures suivantes :
– Rappel
– Précision
7/32
Rappel et Précision
ensemble P (documents pertinents) Rappel:
Combien d’éléments pertinents
sont sélectionnés?
Précision:
Combien de candidats sélectionnées
Sont pertinents?
=
ensemble S (retour du système) 8/32
9/32
Rappel et Précision
• Exemple de calcul de la Précision et du Rappel
– Nombre total des documents pertinents dans la
collection = 10
– Nombre de documents retournées par le SRI = 20
– Nombre de documents, retournées par le système, qui
sont pertinents pour l’utilisateur = 7
– Rappel =
– Précision =
10/32
Rappel et Précision
• Pourquoi ne pas considérer seulement le rappel
comme mesure d’évaluation
– Le rappel évalue la capacité d’un système à renvoyer
TOUS les documents pertinents
– Renvoyer tous les documents de la collection permet
d’obtenir 100% de rappel
ce n’est pas compatible avec le degré de satisfaction
de l’utilisateur
11/32
Rappel et Précision
• Pourquoi ne pas considérer seulement la précision
comme mesure d’évaluation
– La précision évalue la capacité d’un Système à
renvoyer SOURTOUT les documents pertinents
– Renvoyer un seul document pertinent suffit à obtenir
100% de précision
ce n’est pas compatible avec le degré de satisfaction
de l’utilisateur
12/32
Rappel et Précision
• Le rappel augmente avec le nombre de réponses
• La précision diminue avec le nombre de réponses
• Utiliser la courbe Rappel/Précision pour caractériser
un SRI
13/32
Autres mesures d’évaluation
• Précision à plusieurs points de Rappel
• Précision moyenne (MAP)
• Précision à N documents
14/32
Précision à plusieurs points de Rappel
• Calcul de la précision à plusieurs points de Rappel
15/32
Précision à plusieurs points de Rappel
• Une requête donne une liste ordonnées de documents
– Calculer Précision/Rappel à N documents
16/32
Exercice
• Nous souhaitons évaluer un
système de recherche
d'information. Le système testé
renvoie les réponses suivantes:
• Supposons qu’il y a dans l'ensemble de tous les
documents, 10 documents jugés pertinents pour la
requête Q.
• Ce SRI renvoie 5 documents parmi ces 10 (1,2,3,6,9)
17/32
Exercice
• Calculer la précision à plusieurs points de rappel du
système (remplir le tableau ci-dessous)
• Dessiner la courbe précision à plusieurs points de
rappel
10 documents
jugés pertinents
pour la requête
Q.
18/32
Corrigé
• Calcul de la précision à plusieurs points de rappel du
système
19/32
Corrigé
• Courbe de précision à plusieurs points de rappel
20/32
Précision moyenne (MAP)
• Il arrive parfois que deux courbes de deux SRI se
croisent dans ce cas, il est difficile de dire quel
système est meilleur
• Solution: la précision moyenne comme mesure
d’évaluation d’un SRI
• La précision moyenne est une moyenne de précision
sur un ensemble de points rappel
21/32
22/32
Autres mesures de similarité
• Pour la recherche d’images par le contenu,
d’autres mesures de similarité sont utilisées
– Distance euclidienne
– Distances entre histogrammes
– Distances quadratiques
– Distances entre distributions
23/32
Distance euclidienne
• Où p est le paramètre de la norme
• L2 norme est la distance euclidienne
24/32
Distance entre histogrammes
• La distance euclidienne peut être appliquée sur des
histogrammes
• Il existe des mesures spécifiques aux histogrammes:
– Intersection d’histogramme
– Distance de Minkowski
– Distance quadratique
– …
25/32
Distance entre histogrammes
• Intersection d’histogramme
26/32
Distance du Minkowski
• Soient h1 et h2 deux histogrammes
• La distance de Minkowski avec le paramètre r :
r
dr = Σ | h1 (i ) −2 h (i ) |
i∈C
• La distance entre une image
rouge et une image rouge
vif est la même que entre
une image rouge et image
bleu
•Limitée dans le cas de changements de couleur parce que
toutes les colonnes sont comparées individuellement
27/32
Distance quadratique
• Evaluer la relation entre les différentes couleurs
• Soit A une matrice qui exprime la similarité des paires
entre la couleur i et la couleur j: (ai,i = 1 et ai,j = aj,i ):
T
dA(h1, h2) = (h1 − h2) · A · (h1 − h2)
k k
= Σ Σ (h1 (i ) − 2 h (i ))1 (h (i 2) −
h j∈C
(j ))
i∈C
28/32
Exercice 1
• Soit les deux images I1 et I2
• noir0
• gris100
• blanc 200 Image I1 Image I2
1. Calculer la distance de quadratique de leurs histogrammes
• distance quadratique:
k k T
dA(h1, h2) =
=Σ Σ (h1 (i ) − 2 h (i ))1 (h (i 2) −
h j∈C
(j ))
i∈C
• h1={1,8,16} h2={1,10,14}
• d (h , h )= (8-10)((8-1)+(8-10)+(8-14))+(16-14)((16-1)+(16-10)+(16-14))
A 1 2
• =2(7-2+2)+6(15+6+2)=14+23*6=14+138=152
29/32
Matrice de cooccurrence (texture)
•A partir de la matrice de cooccurrence, il est possible
de définir plusieurs descripteurs (Mesures de
Haralick), tels que:
•Mesures de Haralick est présentée dans le chapitre 3
30/32
Exercice 1
• Soit les deux images I1 et I2
• noir0
• gris100
• blanc 200 Image I1 Image I2
1. Calculer la distance de Minkowski de leurs histogrammes
• distance de Minkowski: dr =Σ | h 1(i ) − h (ir ) |
on prend r=1 2 i∈C
2. Calculer la mesure de Haralick de leurs matrices de cooccurrence
(pour la distance d=1 et la direction horizontale angle = 0°).
• mesure de Haralick
31/32
Exercice 1
3. Calculer le module du Gradient de chaque image. Ne pas calculer
de valeurs pour les bords de l’image.
Module du Gradient = |Gradient en X| + |Gradient en Y|
-1
-1 0 1
0
Gx
1
Gy
4. En déduire quel descripteur est le mieux adapté pour indexer les images
I1 et I2.
32/32
Correction exercice 1
1. Distance de Minkowski de h1 et h2
Distance_ Minkowski= |1-1| + |10-8| + |16-4| = 4
Matrice de cooccurrence normalisée
2. Mesure de Haralick de I2 (d=1 et angle = 0°)
Matrice de cooccurrence normalisée
de I1 (d=1 et angle = 0°)
0 100 200
0 100 200 0 0 1/20 0
0 0 1/20 0
100 0 5/20 0
100 1/20 4/20 3/20
200 1/20 4/20 9/20
200 0 3/20 8/20
Mesure de Haralick= Mesure de Haralick=
(1002+1002 +3x1002+ 3x1002 )/20 (1002+2002 +4x1002) / 20
= 80000/20=4000 = 90000/20=4500
33/32
Correction exercice 1
Image I1
• Gradient en X Gradient en Y Module du Gradient
x x x x x x x x x x x x x x x
x -100 0 100 x x -100 -200 -100 x x 200 200 200 x
x -200 0 200 x x 0 0 0 x x 200 0 200 x
x -100 0 100 x x 100 200 100 x x 200 200 200 x
x x x x x x x x x x x x x x x
Image I2
• Gradient en X Gradient en Y Module du Gradient
x x x x x x x x x x x x x x x
x 0 -100 -100 x x 0 0 0 x x 0 100 100 x
x -200 -100 100 x x 0 0 0 x x 200 100 100 x
x 0 -100 -100 x x 0 200 0 x x 0 300 100 x
x x x x x x x x x x x x x x x
34/32
Correction exercice 1
• Distance de Minkowski égale à 4 valeur très faible
l’histogramme n’est pas le bon descripteur pour indexer I1 et I2
• Mesure de Haralick des deux matrices de cooccurrence est assez
proches (4000 et 4500)
• Le module du Gradient des deux images ^permet de les différencier
• Le descripteur le plus adapté, dans le cas de ces images, est le
Gradient
35/32
