next up previous
suivant: Classification monter: Rehaussement de la classification précédent: Introduction

Sous-sections

Recherche d'information sur des bases d'images

Un système de recherche d'information est constitué principalement de deux outils : l'outil d'indexation et l'outil de recherche.

La performance du système de recherche d'images dépend notamment de l'indexation des images qui doit permettre de retrouver la sémantique associée à l'image, du modèle de représentation qui doit être efficace et de la mesure de similarité qui doit permettre de retrouver les documents pertinents.

Indexation des images

Les premiers systèmes de recherche d'images proposaient un processus de recherche basé uniquement sur des descriptions textuelles, les images étant indexées manuellement. Mais l'indexation manuelle des images est une tâche fastidieuse et nécessite un temps non-négligeable. De plus, les résultats des interrogations dépendent de l'ensemble des mot-clés disponibles et de la subjectivité humaine. Contrairement aux documents textuels, l'image ne porte pas de sémantique directement accessible à la machine. C'est pourquoi depuis les années 90, de nombreux travaux de recherche ont été menés pour développer l'indexation automatique d'images par le contenu. La difficulté principale est d'extraire des descripteurs visuels suffisamment significatifs pour permettre de retrouver la sémantique associée à l'image.

Pour qu'un système de recherche d'images soit performant, il faut que l'indexation logique soit pertinente et que l'indexation physique permette un accès rapide aux documents recherchés [BK02].

Indexation logique

L'indexation logique consiste à extraire et à modéliser les caractéristiques de l'image qui sont principalement la forme, la couleur et la texture. Chacune de ces caractéristiques pouvant être considérée pour l'image entière ou pour une région de l'image (localisation spatiale et segmentation en régions d'intérêt [Smi02]).

Forme Les techniques de modélisation sont classées en deux catégories. L'approche « contour » décrit une région au moyen des pixels situés sur son contour (figure 1 page [*] image `edges'). L'approche « région »  considère une région par rapport aux caractéristiques des pixels que cette région contient.

Couleur La couleur est en général définie au moyen de triplets numériques permettant de coder l'intensité de ces composantes. On distingue les espaces de couleurs définis selon des propriétés optiques comme RGB(Red, Green, Blue), et ceux basés sur la perception humaine des couleurs comme HSV(Hue, Saturation, Value). Pour modéliser la distribution des couleurs, on utilise généralement un histogramme indiquant l'intensité d'une couleur en abscisse, et le nombre de pixels en ordonnée (figure 1 page [*]). Pour des questions de performance, on réduit souvent le nombre de couleurs (l'histogramme d'une image codée sur 24 bits possèdera 16 millions de couleurs).

Texture Une texture peut être caractérisée par les attributs de contraste, de directionalité, de régularité et de périodicité du motif. Dans le cadre de la recherche par le contenu, elle permet de distinguer des zones de couleurs similaires, mais de sémantique différente (par exemple, le bleu du ciel et le bleu de la mer).

Indexation physique

L'indexation physique consiste à déterminer une structure efficace d'accès aux données pour trouver rapidement une information. De nombreuses techniques basées sur des arbres (arbres-B, arbres-R, arbres quaternaires, ...) ont été proposées, mais ces techniques souffrent de faiblesses dues notamment à la multi-dimentionnalité de l'indexation logique (recherche sur plusieurs caractéristiques à la fois : forme, couleur, texture,...) et au grand volume de données. Une technique visant à réduire l'espace de recherche pour améliorer la rapidité est le clustering. Elle consiste à regrouper les données qui sont en relation en fonction de certains critères.

Les principaux systèmes actuels de recherche d'images par le contenu sont QBIC[Nib93], MARS[Rui97], VisualSeek[SC96], SurfImage[NMMB98] et NeTra[MM99]. Ils se basent principalement sur les caractéristiques visuelles, et n'utilisent que peu ou pas les indices textuels.

Modèle classique de représentation des documents

Pour les documents textuels, il existe des représentations efficaces. Soit $D=\{d_1, d_2, \dots, d_i ,\dots, d_m\}$ un ensemble de documents (le corpus) et $T=\{t_1, t_2, \dots, t_j, \dots, t_n\}$ un ensemble de mot-clés décrivant (indexant) ces documents, les principaux modèles de recherche d'information pour des documents textuels sont le modèle booléen, le modèle vectoriel et le modèle probabiliste [BYRN99].

Exemple _exemple   Nous présentons ici un exemple de corpus qui nous servira aussi dans la suite de ce rapport. $T=\{Communication, T\acute{e}l\acute{e}phonie, Multim\acute{e}dia,
M\acute{e}dia, Radio, T\acute{e}\-l\acute{e}\-vision\}$, $D=\{d_1,d_2,d_3\}$, $T_{d_1}=\{Communication\}$, $T_{d_2}=\{Radio\}$ et $T_{d_3}=\{T\acute{e}l\acute{e}pho\-nie,Radio\}$ .


Modèle booléen

Chaque document $d$ est représenté par un ensemble de termes non-pondérés sous la forme d'une expression logique :
\begin{displaymath}
d\ = t_{j_1} \wedge t_{j_2} \wedge \dots \wedge t_{j_p},
\end{displaymath} (1)

ce qui signifie que les termes $t_{j_1},\ t_{j_2},\ \dots\ ,t_{j_p}$ sont présents dans le document et que les autres termes $t_{j_a}$ sont absents du document(noté $\neg t_{j_a}$).

La requête q est une expression booléenne dont les termes sont reliés par les opérateurs de conjonction$(\land)$, disjonction$(\lor)$ ou de négation$(\neg)$.

Un document $d$ correspond à une requête $q$ s'il vérifie l'implication logique :

\begin{displaymath}
d\ \to\ q.
\end{displaymath} (2)

Exemple _exemple   Si l'on cherche les documents qui contiennent les mots Téléphonie ou Radio sans Multimédia, alors on a $d_1=Communication$, $d_2=Radio$, $d_3=T\acute{e}l\acute{e}phonie \land Radio$, $q\ =\ T\acute{e}l\acute{e}phonie\ \lor\ (Radio\ \land\ \neg Multim\acute{e}dia)$ et $d_1 \not\to q$, $d_2 \to q$, $d_3 \to q$. La réponse à la requête $q$ est $\{d_2,d_3\}$.

Ce modèle ne permet pas de pondérer les mots dans le document. Un document est soit pertinent, soit non pertinent, par conséquent les réponses ne sont pas ordonnées. L'expression de la requête est dépendante de l'utilisateur, car le 'et' et le 'ou' ne corresponde pas tout à fait au `$\land$' et `$\lor$'.

Le modèle booléen est actuellement très peu utilisé, et souvent c'est sous la forme d'une extension du modèle[SFW83].


Modèle vectoriel

Le modèle vectoriel ([Sal71], [SL68]) représente un document $d_i$ et une requête $q$ par un vecteur dans un espace à $n$ dimensions :
\begin{displaymath}
\vec{d_i}=(\omega_{1,i},\ \omega_{2,i},\ \dots,\ \omega_{j,i},\ \dots,\ \omega_{n,i})
\end{displaymath} (3)


\begin{displaymath}
\vec{q}=(\omega_{1,q},\ \omega_{2,q},\ \dots,\ \omega_{j,q},\ \dots,\ \omega_{n,q})
\end{displaymath} (4)

$\omega_{j,i} \in [0,1]$ est le poids du terme $t_j$ dans le document $d_i$ et $\omega_{j,q} \in [0,1]$ est le poids du terme $t_j$ dans la requête q.

La formule la plus classique pour calculer le poids est la suivante :

\begin{displaymath}
\omega_{j,i}=tf_{j,i} \times \log\frac{m}{m_j}
\end{displaymath} (5)

$tf_{j,i}$ est la fréquence du mot clé $t_j$ dans le document $d_i$ et $m_j$ le nombre de documents du corpus indexés par le mot clé $t_j$. Elle est appelée TF-IDF[SB88].

Exemple _exemple   $d_1=(\omega_{1,1},0,0,0,0,0)$, $d_2=(0,0,0,0,\omega_{5,2},0)$ et $d_3=(0,\omega_{2,3},0,0,\omega_{5,3},0)$.


Modèle probabiliste

Le modèle probabiliste [RJ76] essaye d'estimer la probabilité qu'un utilisateur a de trouver un document $d$ pertinent. Ce modèle suppose qu'il y a un sous-ensemble $R$ de documents que l'utilisateur veut retrouver parmi ceux disponibles, les autres documents $\overline{R}$ étant considérés non-pertinents. Un document $d$ et une requête $q$ sont représentés par un vecteur comme dans le modèle vectoriel, mais les poids sont binaires. Si $P(R\vert\vec{d})$ est la probabilité que le document $d$ soit pertinent pour la requête $q$ et si $P(\overline{R}\vert\vec{d})$ est la probabilité que le document $d$ ne soit pas pertinent pour la requête $q$, alors la similarité entre le document $d$ et la requête $q$ est :
\begin{displaymath}
sim(d,q)=\frac{P(R\vert\vec{d})}{P(\overline{R}\vert\vec{d})}.
\end{displaymath} (6)

Ce modèle est difficile à mettre en oeuvre en raison du calcul de probabilité initiale.

Mesure de similarité

Pour mesurer la similarité entre deux documents $x$ et $y$ (ou bien entre un document $x$ et une requête $y$) représentés par des vecteurs multi-dimensionels $\vec{x}=(x_1,x_2,\cdots,x_n)$ et $\vec{y}=(y_1,y_2,\cdots,y_n)$, on a coutume de prendre l'inverse ou l'opposé d'une distance comme les distances $L_p$ ou Kullback-Leibler, ou bien directement un cosinus.


Distance $L_p$


\begin{displaymath}
L_p(x,y)=\left(\sum_{j=1}^{n}(x_j-y_j)^p\right)^{\frac{1}{p}}\ \ \ \ \ \ \ \ \ \ \ \ p\ \in [1,\infty[
\end{displaymath} (7)

Pour $p=2$, elle correspond à la distance euclidienne qui est la plus utilisée.


Distance de Kullback-Leibler

La divergence de Kullback-Leibler(KL) entre deux distributions de probabilité $x$ et $y$ est aussi connue sous le nom d'entropie relative :
\begin{displaymath}
KL(x,y)=\sum_{j=1}^{n}x_j\log\frac{x_j}{y_j}.
\end{displaymath} (8)

De plus, comme $KL(x,y) \neq KL(y,x)$, on définit la distance de Kullback-Leibler(DKL) (1951) comme :

\begin{displaymath}
DKL(x,y) = DKL(y,x) = KL(x,y) + KL(y,x).
\end{displaymath} (9)

C'est la meilleure mesure pour la recherche d'information dans les grandes bases de données[MM02].


Similarité par cosinus

Cette mesure de similarité généralement associée au modèle vectoriel (1.2.2) correspond au cosinus de l'angle formé par les vecteurs $\vec{x}$ et $\vec{y}$ dans l'espace multi-dimentionnel.
\begin{displaymath}
sim(x,y)=cos(\vec{x},\vec{y})=
\frac{\sum_{j=1}^{n}x_j\times...
...}
{\sqrt{\sum_{j=1}^{n}x_j^2}\times\sqrt{\sum_{j=1}^{n}y_j^2}}
\end{displaymath} (10)


next up previous
suivant: Classification monter: Rehaussement de la classification précédent: Introduction
Tollari Sabrina 2003-06-10