INDEXATION des IMAGES

INDEXATION des IMAGES

Marine Campedel

www.tsi.enst.fr/~campedel

mars 2005

Plan du cours

Introduction

Indexation par le texte

Indexation par le contenu

Extraction des caractéristiques

Organisation des caractéristiques

Comparaison des caractéristiques

Interaction avec l’utilisateur

Évaluation des systèmes d’indexation

Conclusion

Introduction

Quelques chiffres :

INA : 500 000 h video + 600 000 h audio + 2

000 000 de photos

82 Milliards de photos par an dans le monde

390 Millions d’images indexées par Google

4250 films commerciaux par an (UNESCO)

Motivations :

Conservation d’un patrimoine (culturel, scientifique,…)

Valorisation en facilitant l’accès et l’exploration

Exploitation commerciale (photos numériques, TV

numérique, …)

Introduction : quelles images ?

biomédical, satellitaires, photos, 2D ou 3D,…

3 catégories générales

Images d’art (auteur, titre,…)

Images documentaires (reliées à un texte)

Images ordinaires

Centres d’intérêts actuels :

Audio-vidéo, multimédia, 3D

Introduction

Acteurs industriels

QBIC (IBM), Virage, Netra

NewPhenix (CEA)

Acteurs académiques

VisualSeek (Columbia), …

IMEDIA (INRIA, Rocquencourt), RETIN (ETIS,

Cergy), KIWI (Insa, Lyon),…

Nombreux projets européens et nationaux

Introduction

Objectif de l’indexation : faciliter l’accès à des

bases de données en extrayant une information

synthétique.

Fouille de données (Data Mining), Extraction de

connaissances, Vision artificielle

Catalogue, classification et indexation : quelles

différences ?

Indexation textuelle ou par le contenu ?

Introduction

1980 : Annotation textuelle des images

1990 : Indexation par la couleur, la forme et la texture

1993 : Requête en utilisant la similarité des images

1997 : Requête par images exemplaires et mesure de la pertinence (relevance feedback)

2000 : apprentissage sémantique et adaptation à l’utilisateur

Enjeux actuels : annotation interactive, formalisation de la connaissance (ontologies), grosses bases de données (problèmes de stockage, de vitesse d’accès,…), données hétérogènes, …

Indexation d’images à partir du texte

Texte

meta-données : type d’image, titre, auteur, conditions de prises de vue,…

Annotations humaines

Avantages :

exploite les outils d’indexation textuelle, prise en compte plus aisée des aspects sémantiques.

Inconvénients :

vocabulaire limité

difficultés de l’annotation : définition du vocabulaire, temps d’annotation >> temps réel, subjectivité, etc.

Indexation d’images à partir du texte

Ontologies

Nécessité de définir un langage de description

Limité par le contexte de production

Limite l’utilisation

Définition d’ontologies : modélisation du contexte (objets/concepts et relations entre eux) de façon à lever toute ambiguïté d’interprétation

« Le problème fondamental est de respecter la diversité des langages et des

représentations du monde, tout en permettant l'échange d'information.[…]

Identifier, modéliser les concepts d'un domaine, pertinents pour une/des

applications, Se mettre d'accord, au sein d'une communauté, sur les

termes employés pour se référer à ces concepts. »

Taxonomie / Nomenclature

Réduction couramment utilisée : Classification

Exemple : Corine Land cover

Surfaces artificielles

Surfaces cultivées

Forêts et espaces semi naturels

Surfaces humides

eau

Usine urbaine

Transports …

Réseaux routiers

Ports Aéroports …

Indexation par le contenu : principe (1/2)

Modèles étiquetésCaract.+ étiquettes

Images

Extraction de caractéristiques

Caractéristiques

Requêtesutilisateur

ApprentissageNon supervisé

Apprentissagesupervisé

Modèles

Sélection de caractéristiques

Principe (2/2)

Off-line : production d’indexes issus de l’analyse

du contenu des images

Extraction de caractéristiques pertinentes

Réduction de la dimensionnalité

Organisation par classification

On-line : gestion des requêtes d’un utilisateur

« Gap sémantique »

Relevance feedback

Extraction de caractéristiques (1/2)

Caractéristiques :

Spécifiques : points saillants, minuties,…

Générales : couleur, texture, forme

Globale ou locale :

Blocs arbitraires, segmentation, information

topologique

Extraction de caractéristiques (2/2)

Problème de représentation

Caractéristiques numériques, symboliques,

graphes,…

Invariances

Translation, rotation, homothétie,

non-linéaires ?

Similarité de l’information (1/5)

Visuellement similaires ?



Deux images seront comparées par l’intermédiaire des caractéristiques extraites

Sim( Im1, Im2 ) = Sim( f(Im1), f(Im2) ), avec f la fonction d’extraction des caractéristiques

Mesures de similarités, distances

(A) s( x, x ) = s( y, y ) > s( x, y )

(B) s( x, y ) = s( y, x )

(C) d( x, x) = 0

(D) d(x,y) = 0 x = y

(E) d(x, y) <= d(x,z) + d(z,y)

(F) d(x,y) <= max( d(x,z), d(z,y) )

similarité

dissimilarité

distance

Ultra-métrique


Distance euclidienne

Distance euclidienne généralisée

Malahanobis

Chi2

Similarité en cosinus

Combinaisons linéaires de similarités (ou

distances)


Comparaison des caractéristiques après une transformation Φ

« Truc du noyau »

K(x,y) = < Φ(x), Φ(y)>, K semi-defini positif

D(x,y) = <x,x> + <y,y> -2<x,y> devient

D(Φ(x), Φ(y) ) = K(x,x) + K(y,y) -2K(x,y)

Intérêt : la spécification de K définit implicitement Φ

Intensivement utilisé pour ACP, la discrimination de Fisher, la classification SVM,…

Réduction d’information (1/2)

Réduction de la dimensionnalité

ACP

Algorithmes de sélection

Quantification (forme de clusterisation)

Réduction d’information (2/2)

Sélection : filter/wrapper/embedded

Supervisé, non supervisé

Supervisé, wrapper : SVM-RFE, Fisher,…

Non supervisé, filter : clusterisation des

caractéristiques

Organisation de l’information (1/2)

Classification : données X (caractéristiques) et

label Y

Exemples : kPPV, SVM, Bayes, arbres de

décision (C45.1)

Évaluation d’une classification :

Décompte des erreurs

Validation croisée

Organisation de l’information (2/2)

Clusterisation : données X

Partitionnement : kMeans

Hiérarchique : arbres

Minimiser la distance intra-classes et maximiser

la distance inter-classes

Évaluation : pas évidente

Estimation du nombre de clusters : indexes de

Calinsky, Davies Bouldin, Dunn,…

Mesure de la qualité ?

Gestion de l’information

SGBD Systèmes de Gestion de Bases de

données

Gestion informatique : interaction avec les

requêtes utilisateur, temps d’accès, place

mémoire, …

Relationnel : SQL, mySQL

Objet

Relationnel-objet : Oracle, PostGreSQL

Requêtes

Grande diversité

Les systèmes imposent des types de requête :

Recherche d’une image dans une base

Recherche d’images similaires à une image exemplaire

Recherche d’images similaires à des images exemples et dissimilaires à d’autres

Recherche d’images contenant une région de l’image exemplaire

…

Feedback utilisateur (1/2)

Défaut majeur des systèmes standards :

l’utilisateur doit s’adapter au système

Caractéristiques extraites automatiquement non

intuitives

Fossé entre la formulation des requêtes et le

codage de l’information

Nécessité d’adapter le système à l’utilisateur

Apprentissage : requêtes, mesures de similarités

Feedback utilisateur (2/2)

Modèles étiquetésCaract.+ étiquettes

Images

Extraction de caractéristiques

Caractéristiques

Requêtesutilisateur

ApprentissageNon supervisé

Apprentissagesupervisé

Modèles

Sélection de caractéristiques

Évaluation (1/2)

Graphe de rappel-précision calculé en faisant varier le

nombre de documents sélectionnés

éssélectionndocuments

trouvésdocumentsprécision

et

pertinentsdocuments

trouvésdocumentsrappel

Documents pertinents Documents non pertinents

Documents

sélectionnés

Documents trouvés Documents hors contexte :

bruit

Documents non

sélectionnés

Documents oubliés :

silence

Évaluation (2/2) : autres critères

Exploitation du rang de récupération

Critère de validation de MPEG7

Rank*(k) = rang(k) si < K(q), 1.25K sinon

AVR(q) : moyenne des rangs

MRR(q) = AVR(q) – 0.5( 1 + NG(q) )

NMRR(q) = MRR(q) / ( 1.25K – 0.5(1+NG(q)) )

Critère final : moyenne des NMRR Notations : q = 1 requête ; k = une image pertinente pour la

requête ; NG(q) nombre d’images pertinentes pour la requête ; K limite de rang acceptable

Normalisation : MPEG 7 (1/2)

MPEG : Motion Picture Expert group

MPEG7 : A Multimedia Content Description Interface,

normalisé en 2001

Standard de description du contenu de données

multimédia + interprétation du sens de l’information

S’appuie sur XML (langage à balises)

Un éditeur gratuit d’IBM (pour indexer des videos)

www.alphaworks.ibm.com/tech/videoannex

Normalisation : MPEG 7 (2/2)

Définitions de caractéristiques bas niveau : //www-iplab.ece.ucsb.edu/publications/01IEEEManjunath.htm

Évaluation des caractéristiques sur des bases

étiquetées manuellement

Démonstrations

Images 3D : http://3d.csie.ntu.edu.tw/

Démonstrations

Démonstrations

Ding-Yun Chen, Xiao-Pei Tian, Yu-Te Shen and Ming Ouhyoung, "On Visual Similarity Based 3D Model Retrieval", Computer Graphics Forum (EUROGRAPHICS'03), Vol. 22, No. 3, pp. 223-232, Sept. 2003

Démonstrations www-rocq.inria.fr/imedia/ikona

Feedback utilisateur

Conclusion

Indexation des images : problème non résolu

Experts issus de domaines variés (informatique,

traitement de l’image, psycho visuel, apprentissage

machine, …)

Deux axes à étudier simultanément :

Techniques d’analyse d’image donc d’extraction

et de comparaison de l’information

Pertinence de l’information pour un utilisateur

Produits commerciaux encore basiques … quoique