\chapter{Prétraitement des données}
\label{ch:pretreat}

%\section{Introduction}

Nous décrivons dans ce chapitre les prétraitements standard utilisés pour les documents textuels et les images. Ils constituent les premières étapes de nombreuses tâches effectuées sur les collections de documents, comme l'accès à l'information, la catégorisation et le clustering. Certains de ces prétraitements sont de plus utilisés pour les tâches d'extraction d'information.

\begin{sloppypar}
\section{Prétraitement~des~données \\ textuelles}
\end{sloppypar}

Dans cette partie, nous allons présenter l'ensemble des prétraitements utilisés pour construire la représentation d'un document au sein d'une collection. Ces prétraitements comprennent la \textit{segmentation} des séquences de caractères présents dans les documents en mots distincts, la \textit{normalisation} des mots, opération qui consiste à fournir une \textit{forme canonique} pour chaque mot, et le \textit{filtrage} qui vise à supprimer les mots les moins représentatifs. Nous renvoyons les lecteurs intéressés par ce sujet à l'ouvrage \citep{amini-gaussier-book}.
%fréquents\footnote{Nous réservons le nom \textit{terme} pour désigner les mots normalisés restant après l'étape du filtrage.}. Ces processus sont schématisés par le cube grisé dans la figure~\ref{chap2:fig:index}. 

%\subsection{Motivations}
\subsection{Segmentation}

La segmentation (en anglais \textit{tokenisation}) \index{segmentation}\index{tokenisation} consiste à séparer une suite de caractères en mots. On distingue parfois mot et \textit{type} pour rendre compte du fait qu'un même mot (qu'on appelle alors \textit{type}) peut apparaître plusieurs fois dans un même document ; chacune de ces occurrences correspond à un \textit{mot}. Dans l'exemple suivant~:

\smallskip
\begin{tabular}{l c l}
 & {\small \textit{l'importance de retrouver l'information pertinente}} & ~~~~ \\
\end{tabular}

\smallskip
nous avons 7 mots:

\smallskip
\begin{tabular}{l c l}
& \{{\small  \textit{l', importance, de, retrouver, l', information, pertinente}}\} & ~~~~\\
\end{tabular}

\medskip
mais seulement 6 types, puisqu'il y a deux instances de \{\textit{l'}\}. %Après filtrage par un antidictionnaire (section~\ref{chap2:sec:stoplist}), il ne restera plus que 4 termes \{\textit{importance, retrouver, information, pertinente}\}.

La segmentation est une étape difficile et cruciale puisqu'elle risque, si elle est mal réalisée, d'avoir un impact négatif direct sur la représentation obtenue pour chaque document. Une bonne segmentation dépend de la prise en compte des spécificités de la langue des textes traités. Pour certaines langues asiatiques, comme le chinois, les mots dans un texte ne sont pas séparés par des espaces et la segmentation est dans ce cas une tâche difficile. Pour les langues indo-européennes, la tâche de segmentation est plus aisée puisque l'espace et les signes de ponctuation donnent une première indication de séparation entre les différents éléments lexicaux. Néanmoins, chaque langue de ce groupe linguistique a sa spécificité propre et une simple segmentation par des espaces et des signes de ponctuation conduit généralement à des résultats d'indexation médiocres. Par exemple, pour le français, nous avons :
\begin{itemize}
\item \vspace{2mm} les composés lexicaux à trait d'union comme  \textit{chassé-croisé}, \textit{peut-être}, \textit{rendez-vous}, etc.
\item \vspace{2mm} les composés lexicaux à apostrophe comme \textit{aujourd'hui}, \textit{prud'homme}, etc.
\item \vspace{2mm} les expressions idiomatiques comme \textit{au fait}, \textit{poser un lapin}, \textit{tomber dans les pommes}, etc.
\item \vspace{2mm} les formes contractées comme \textit{Gad'zarts (les gars des Arts et Métiers)}, \textit{M'sieur}, etc.
\item \vspace{2mm} les sigles et les acronymes comme \textit{K7, A.R., CV, càd, P.-V.}, etc.
\end{itemize}

\medskip

Dans ce cas, lorsque nous indexons un texte en français, nous ne souhaitons pas, par exemple, que le mot \textit{aujourd'hui} soit séparé en \textit{aujourd} et \textit{hui} alors que nous voulons que les mots \textit{un homme} et \textit{l'homme} soient indexés sous le même terme, \textit{homme}. Ce problème devient même extrême avec l'allemand, où les noms composés s'écrivent sans espace ; par exemple le mot \textit{Rindfleischetikettierungsüberwachungsaufgabenübertragungsgesetz} doit, a priori, être séparé en dix mots avant d'être indexé : \textit{Rind} (boeuf) + \textit{Fleisch} (viande) + \textit{Etikettierung} (étiquetage) + \textit{Überwachung} (surveillance) + \textit{Aufgabe} (tâche) + \textit{Übertragung} (transmission) + \textit{Gesetz} (droit). Pour les langues européennes, différents logiciels de segmentation commerciaux existent. Le but de certains d'entre eux est de réaliser une analyse plus poussée du texte en associant aux mots d'une phrase leur fonction grammaticale. La segmentation dans ces cas est une étape préliminaire à cette analyse. On peut citer ici le logiciel \textit{TreeTagger} \citep{schmid:1994} qui est en libre accès et est couramment utilisé pour cette tâche\footnote{\url{http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/}}.

\subsection{Normalisation et filtrage}

La normalisation \index{normalisation textuelle} est le processus qui transforme toutes les variantes d'un même mot (utilisation de majuscules ou minuscules, forme singulier ou pluriel,...)  sous une forme normale ou canonique de façon à ce que les documents qui contiennent les mêmes mots soient représentés par les mêmes \textit{termes}. Un terme est la forme du mot (ou du type) conservée dans la représentation du document. Par exemple, après normalisation, les formes \textit{Information} et \textit{information} seront représentées par le même terme (par exemple \textit{information}) ; les requêtes formées par un de ces mots donneront alors le même résultat. 

Il existe deux types de normalisation : la normalisation \textit{textuelle} et la normalisation \textit{linguistique}.

\subsubsection{Normalisation textuelle}
La normalisation textuelle rend les mots d'une même famille sous une forme canonique en effectuant quelques transformations superficielles sur les séquences de caractères. L'exemple précédent avec \textit{P.V.} constitue un cas de normalisation textuelle. Cette opération dépend de la langue considérée ; les règles communément utilisées en français pour ce type de normalisation sont décrites ci-après. 

\paragraph{Les ponctuations} Les ponctuations sont en général supprimées. Le trait d'union, qui peut être présent dans des mots composés ou être utilisé comme marque de césure à la fin d'une ligne, fait parfois l'objet d'un traitement particulier si l'on dispose de listes de mots le comportant\footnote{De telles listes peuvent être compilées à partir de ressources existantes ou extraites à partir de corpus de grande taille.} : si le mot est présent dans la liste, le trait d'union est conservé ou remplacé par un espace, sinon il est supprimé.

\paragraph{La casse} Une stratégie classique est de réduire les majuscules en minuscules. Cette stratégie est très efficace si l'on dispose de listes de sigles et acronymes auxquels on peut substituer leur forme développée avant d'appliquer les procédures de normalisation. Ainsi, le sigle \texttt{CAS} (Centre d'analyse stratégique) ne sera pas réduit au nom \textit{cas}. Tout comme pour les mots avec traits d'union, de telles listes peuvent être compilées relativement facilement. En l'absence de telles listes, une heuristique souvent utilisée consiste à ne convertir que les majuscules se trouvant en début de phrase. 

\paragraph{Les accents} L'impact des accents et des diacritiques sur le résultat de la recherche est souvent marginal. La règle appliquée consiste généralement à les supprimer (ainsi \textit{ambiguë} devient \textit{ambigue}, \textit{forêt} devient \textit{foret}). La question ici n'est pas de savoir si les requêtes sont linguistiquement bien formées, mais plutôt de tenir compte des habitudes des utilisateurs dans la formulation de leurs requêtes. Par manque de temps, par habitude ou par erreur, les accents sont souvent omis ou mal utilisés. Les supprimer prend alors tout son sens.

\paragraph{Les dates et les valeurs monétaires} Les règles pour normaliser ces types de mots sont assez spéciales et dépendent de la langue et des usages particuliers de chaque pays. Pour certaines langues comme l'anglais d'Amérique du Nord, le problème des dates est même plus compliqué puisque, dans les documents d'une collection, nous pouvons rencontrer des occurrences de \textit{année/mois/jour} ou \textit{mois/jour/année} pour une même date.

\subsubsection{Normalisation linguistique}
La normalisation linguistique consiste à ramener un mot sous une forme canonique en appliquant un certain nombre d'analyses morphologiques. Il existe deux types de normalisation linguistique : la \textit{racinisation} \index{racinisation} et la \textit{lemmatisation}.\index{lemmatisation} 

\paragraph{La \textit{racinisation}} La racinisation cherche à regrouper les différentes variantes morphologiques d'un mot autour d'une même racine (en anglais \textit{stem}). Ce procédé repose sur un ensemble de règles pour supprimer les terminaisons des mots, et il est fortement dépendant de la langue utilisée. Par exemple, les mots français suivants ont la même racine morphologique (en gras)~:

\medskip
\begin{tabular}{l c l}
 ~ & \textit{chanter, chante, chantes, chantent, chanté, chantée, chants} $\Rightarrow$ \textbf{chant}& ~ \\
\end{tabular}

\medskip
La racinisation peut aussi ramener des mots à des formes qui ne sont pas de vrais mots~:

\medskip
\begin{tabular}{l c l}
 ~ & \textit{informer, information, informationnel} $\Rightarrow$ \textbf{inform}& ~ \\
\end{tabular}

\medskip
Les premiers algorithmes de racinisation, appelés \textit{stemmers}, ont été étudiés à partir de la fin des années 1960 et les plus connus sont ceux de \citep{lovins:1968}, \citep{porter:1980} et \citep{paice:1990}. Ces \textit{stemmers} sont conçus pour l'anglais et ils procèdent en traitant les mots par des étapes prédéfinies. À une étape donnée, on détermine si la terminaison d'un mot se trouve dans une liste prédéfinie. Le cas échéant, le stemmer la supprime ou la transforme suivant la règle à appliquer. D'autres algorithmes de racinisation pour d'autres langues ont été conçus suivant le même principe. Pour le français, on peut par exemple citer~:
\begin{itemize}
\item le \textit{stemmer} de \texttt{Carry} \citep{paternostre:2002}, développé dans le cadre du projet \textit{Generic Analyser and Listener for Indexed and Linguistics Entities of Information} (\texttt{GALILEI}) ;
\item le \textit{stemmer} \texttt{Snowball}, disponible sur Internet et dont les règles de racinisation sont expliquées sur la page de téléchargement\footnote{\url{http://snowball.tartarus.org/algorithms/french/stemmer.html}}.
\end{itemize}

\paragraph{La \textit{lemmatisation}} La lemmatisation permet d'obtenir une forme canonique, appelée lemme, pour les différentes variantes flexionnelles d'un mot donné : différentes conjugaisons pour un verbe, variantes de genre et de nombre pour les adjectifs et  variantes de genre pour les noms. Pour les verbes, le lemme correspond (arbitrairement) à l'infinitif, au masculin singulier pour les adjectifs et au masculin pour les noms qui ont des variantes de genre. À noter que les adverbes n'ont pas de variantes flexionnelles et que les autres parties du discours (déterminants, pronoms...) correspondent à des mots vides (non porteurs de sens) en général ignorés (voir ci-après). Au contraire de la racinisation, la lemmatisation fournit toujours un mot attesté et ne regroupe, sous une même forme, que les mots qui diffèrent par des marques flexionnelles ne modifiant pas fondamentalement le sens. Les mots \textit{information} et \textit{informationnel} sont regroupés par racinisation mais pas par lemmatisation.

\subsection{Filtrage}

Un antidictionnaire (\textit{stopword list} en anglais), ou liste de \textit{mots vides}, est une liste de mots qui sont en général présents avec une fréquence élevée dans tous les documents d'une collection et qui n'apportent que peu d'information sur le contenu. Le filtrage par un antidictionnaire est très pratiqué dans la recherche d'information et la classification, supervisée ou non, des documents textuels. En effet, les mots vides ont une distribution identique sur tous les documents d'un corpus, quelles que soient les thématiques considérées ; leur pouvoir discriminant est donc limité. Ce filtrage a été introduit par Luhn \citep{luhn:1958}, un des pionniers en recherche d'information.

\smallskip
Il existe des antidictionnaires indépendants du domaine de la collection que l'on considère et d'autres qui en sont dépendants. 
\begin{itemize}
\item \vspace{2mm} Les antidictionnaires dépendants d'un domaine sont construits en \mbox{triant} d'abord les mots suivant leur nombre total d'apparitions dans la collection et en sélectionnant ensuite tous les mots qui apparaissent plus souvent qu'un seuil fixé manuellement (un mot qui apparaît dans tous les documents de la collection a un contenu informatif faible pour cette collection). Un exemple de mots vides dépendants du domaine est le mot \textit{projet} pour une collection de documents constituée de descriptifs de projets.
\item \vspace{2mm} Pour les antidictionnaires généraux, c'est-à-dire indépendants des domaines considérés, on se repose soit sur la catégorie grammaticale (l'antidictionnaire contiendra alors tous les mots des parties du discours autres que nom, adjectif, verbe et adverbe), soit sur un ensemble de collections de différents domaines d'une langue donnée, ensemble sur lequel on effectue le travail présenté au point précédent.
\end{itemize}

\medskip
Les mots présents dans l'antidictionnaire ainsi constitué sont supprimés des documents du corpus.

\section{Prétraitement des données image \\ ou vidéo}

Les prétraitements au sens le plus strict sont très limités en ce qui concerne les images et les vidéos. Ils comprennent des redimensionnements, avec ou sans modification du rapport d'aspect, associés ou non à des rognages, et des normalisations de brillance et/ou de contraste. Ceux-ci sont très basiques et ils ne seront pas détaillés ici. Dans un sens moins strict, on considère aussi les traitements qui visent à construire des {\em représentations} (ou des abstractions) de leurs contenus visuels. Ce sont des prétraitements par rapport à des tâches de classification par apprentisage classique ou des tâches de recherche par similarité visuelle.

\medskip
On distingue deux types principaux de représentation du contenu visuel~: les représentations \guil{classiques} qui sont obtenues par des transformations algorithmiques directement conçues par des chercheurs ou par des ingénieurs ({\em engineered features}) et les représentations apprises ({\em learned features}) dans lesquelles les transformations elles-mêmes résultent d'un apprentissage par machine, de type supervisé (catégorisation \guil{de bout en bout}) ou non supervisé (auto-encodeurs).

\bigskip
Il existe une littérature très abondante sur les représentations classiques, un très grand nombre de choses ayant été essayées durant les dernières décennies. Nous n'en verrons ici que quelques exemples, les représentations apprises s'étant montrées largement supérieures dans la plupart des domaines d'application. Parmi les représentations classiques, on distingue principalement les globales et celles basées sur une agrégation de représentations locales. Elles sont pour la plupart basées sur des approches statistiques qui visent à capturer des distributions d'éléments pertinents. 

\bigskip
Les propriétés recherchées pour ces représentations sont en général~: (i)~qu'elles consistent en des vecteurs de nombres réels de taille fixe, c'est-à-dire indépendante de la taille de l'image ou de la vidéo représentée et indépendante de la complexité de son contenu~; (ii)~qu'il existe entre elles une métrique associée, euclidienne ou non, qui permette l'évaluation de la similarité des images ou des vidéos représentées~; et enfin (iii)~qu'elles préservent autant que possible les informations relatives au contenu sémantique (par exemple les types d'objets présents) tout en étant aussi robustes ou invariantes que possible par rapport aux variations \guil{accidentelles} comme la taille, l'orientation ou les conditions d'éclairage.

\subsection{Représentations globales}

Nous considérons ici deux exemples de représentations directement calculées sur l'ensemble d'une image ou d'un plan vidéo, correspondant aux deux principales façons de percevoir le contenu visuel : les histogrammes pour représenter les distributions des couleurs et les transformées de Gabor pour représenter les distributions de textures.

\subsubsection{Histogrammes de couleurs}

L'espace de couleurs dans lequel les valeurs des pixels sont codées est partitionné en un nombre donné de régions qui seront les catégories selon lesquelles l'histogramme sera calculé. Ce partitionnement peut être fait de nombreuses façons mais, en général, on considère un espace de couleurs cubique, comme RVB ou YUV, puis on découpe chacune de ses dimensions en intervalles de même taille et on prend comme catégories les produits cartésiens triples de ces intervalles. L'histogramme correspondant est tridimensionnel. Chaque catégorie correspond alors à un petit cube (ou à un petit parallélépipède) de l'espace des couleurs.

\smallskip
Le calcul de l'histogramme d'une image ou d'un plan vidéo (population) consiste alors tout simplement à compter combien de pixels (observations) tombent dans chacune des catégories. Dans la version la plus simple, un pixel donné tombe toujours dans exactement une des catégories. Ceci a toutefois l'inconvénient de faire apparaître des effets de seuillage si beaucoup de pixels tombent près d'une frontière soit d'un côté soit de l'autre. De façon à éviter ces effets de quantification, on considère des histogrammes à catégories floues dans lesquels la \guil{masse} d'un pixel (égale à~1) est répartie dans les catégories adjacentes en fonction de la proximité de la couleur de ce pixel par rapport aux centres de ces dernières.

\smallskip
En général, on normalise les histogrammes de telle sorte que la somme des valeurs ou celle de leurs carrés soit égale à 1. Ceci présente l'avantage de rendre les représentations sous forme d'histogrammes relativement invariantes par rapport à la taille des images sur lesquelles elles sont calculées. En effet, la proportion de pixels d'une couleur donnée ne change pas ou marginalement quand on redimensionne les images. Ces représentations sont également invariantes par symétrie horizontale et verticale et elles sont également relativement robustes par rapport aux déplacements des objets. Par contre, les histogrammes de couleurs ne sont pas invariants par rapport aux changements d'illumination~; pour les y rendre plus robustes, on peut effectuer un prétraitement de normalisation de brillance et/ou de contraste.

\smallskip
Les histogrammes étant des distributions, la distance la plus appropriée pour les comparer est celle dite du $\chi^2$ définie par ${d(x,y)=\sum_i(x_i-y_i)^2/(x_i+y_i)}$. Une autre distance appropriée est celle de Wasserstein, dite \guil{distance du déplaceur de terre} ({\em Earth Mover Distance}) qui correspond au coût de déplacement minimal pour passer d'un histogramme à un autre. Cette distance est assez complexe à calculer en pratique et même la distance du $\chi^2$ est encore assez coûteuse à calculer à cause de la division et du cas particulier fréquent où $x_i$ et $y_i$ sont nuls simultanément. La distance euclidienne n'est pas directement adaptée pour évaluer la similarité des histogrammes, mais elle devient quasiment équivalente à celle du $\chi^2$ si on remplace chaque valeur par sa racine carrée dans les histogrammes et si on les normalise selon la norme $L_2$\footnote{Le problème vient du cas fréquent où une fraction significative des observations tombe dans un petit nombre de catégories, voire dans une seule. Les composantes correspondantes interviennent au carré et masquent en conséquence ce qui est relatif aux autres composantes. Le dénominateur dans la distance du $\chi^2$ rend leur effet linéaire et le passage par une racine carrée a un effet similaire avec la distance euclidienne.}.

\subsubsection{Transformées de Gabor}

Les textures sont localement capturées par des filtres de Gabor. Ces derniers combinent une fonction gaussienne et une onde plane complexe définissant une orientation et une échelle cibles. La fonction gaussienne assure d'une part une capture locale et d'autre part une certaine extension au filtre associé à l'onde plane. Dans la version \guil{circulaire} un filtre de Gabor est défini par trois paramètres~: l'extension moyenne $\sigma$ de la gaussienne, la longueur d'onde $\lambda$ et l'orientation $\theta$ de l'onde plane. Un filtre de Gabor transforme une image d'entrée (réelle et monochrome) $I(i,j)$ en une image filtrée (complexe) selon ces trois paramètres $g(\sigma,\lambda,\theta,I)$ définie par~:
\begin{equation}
g(\sigma,\lambda,\theta,I,i,j)=\frac{1}{2\pi\sigma^2}\sum_k\sum_l e^{\frac{k^2+l^2}{2\sigma^2}}.e^{\frac{k.\cos\theta+l.\sin\theta}{\lambda}}.I(I+k,j+l)
\end{equation}
La somme double sur $k$ et $l$ est étendue jusqu'à ce que l'amplitude de la gaussienne devienne négligeable, c'est-à-dire typiquement entre $\pm 3 \sigma$ et $\pm 5 \sigma$. La version elliptique est similaire avec une expression un peu plus complexe, l'extension $\sigma$ étant différente dans la direction correspondant à la longueur d'onde $\sigma_\lambda$ et dans la direction perpendiculaire $\sigma_\theta$ (figure~\ref{fig:gabor}).

\begin{figure}[htbp]
\centering
\includegraphics[width=.24\textwidth]{./Figs/chapter-Pretraitement/circular.png} \hspace{10mm}
\includegraphics[width=.32\textwidth]{./Figs/chapter-Pretraitement/elliptic.png}
\caption{Filtres de Gabor circulaire (gauche) et elliptique (droite). La zone indiquée correspond à une extension d'un écart-type sur la gaussienne.}
\label{fig:gabor}
\end{figure}

\smallskip
Les écarts-types $\sigma_\lambda$ et $\sigma_\theta$ sont tous les deux choisis proportionnels à la longueur d'onde $\lambda$ de telle sorte que chacun d'entre eux contienne le même nombre de longueurs d'ondesdans leur zone effective et qu'ils aient le même rapport d'aspect. Il n'y a alors plus que deux paramètres indépendants, $\lambda$ et $\theta$, pour définir un filtre. On choisit un nombre fixe de directions (typiquement 8) sur 180 degrés  et un nombre fixe de longueurs d'onde, en général selon une échelle logarithmique, comme illustré sur la figure~\ref{fig:bank}. Le rapport fixe entre $\sigma_\lambda$ et $\lambda$ détermine la sélectivité du filtre selon la longueur d'onde. On la choisit en général de telle sorte que la plage filtrée soit assez large et que les bandes passantes des filtres successifs par rapport à la longueur d'onde soient semi-recouvrantes. De même, le rapport fixe entre $\sigma_\theta$ et $\sigma_\lambda$ détermine la sélectivité angulaire des filtres et on le choisit de telle sorte que les bandes passantes des filtres successifs par rapport à l'orientation soient semi-recouvrantes.

\begin{figure}[htbp]
\centering
\includegraphics[width=\textwidth]{./Figs/chapter-Pretraitement/gabor.png}
\caption{Banc de filtres de Gabor elliptiques avec 8 orientations et 4 échelles, partie réelle.}
\label{fig:bank}
\end{figure}

\smallskip
Les sorties des filtres de Gabor sont des images complètes de nombres complexes. Il est nécessaire de réduire fortement le volume total d'information. Ceci peut être fait de nombreuses façons, la plus courante étant simplement de ne conserver que l'énergie totale obtenue à travers chaque filtre, soit~:
\begin{equation}
E_g(\lambda,\theta,I)=\frac{1}{N}\sum_i\sum_j \mid g(\lambda,\theta,I,i,j) \mid^2
\end{equation}
$N$ est le nombre total de pixels dans l'image. Ceci est une forme d'agrégation des valeurs telles que présentée dans la section~\ref{sec:agregation} ({\em pooling} par moyenne des carrés des amplitudes).

\smallskip
Finalement, si l'on retient $n_\lambda$ échelles et $n_\theta$ orientations, la représentation de la texture d'une image basée sur une transformée de Gabor est un vecteur de $n_\lambda.n_\theta$ valeurs réelles. La similarité entre les images selon cette représentation peut être mesurée par la distance euclidienne ou par l'angle entre les vecteurs. Le choix de l'angle permet une mesure de similarité relativement robuste par rapport aux changements d'illumination puisqu'une augmentation uniforme de l'intensité se traduit par une augmentation uniforme des composantes de la représentation.

\subsection{Représentations locales}

Une des représentations locales les plus populaires est celle associée aux points SIFT ({\em Scale Invariant Feature Transform}) proposée par \cite{lowe:2004}. Dans cette approche, les représentations locales sont liées à des points sélectionnés dans les images, auxquels sont associées une échelle et une orientation déterminées également lors du processus de sélection. Dans ces représentations, un voisinage carré du point considéré, de la taille de l'échelle associée, est décomposé en $4 \times 4$ blocs. Un vecteur de gradient de l'intensité est calculé pour chacun des pixels de ces blocs et un histogramme des directions de ces gradients, discrétisées selon 8~secteurs de~45 degrés chacun, est calculé pour chacun des blocs. La taille totale de ce descripteur est de 128~composantes ($4 \times 4 \times 8$). Il est en général normalisé selon $L_1$ ou $L_2$ de façon à ne pas dépendre de la taille du voisinage retenu (correspondant à l'échelle de détection du point)

\smallskip
Le processus de sélection (ou de détection) des points vise à choisir des points \guil{remarquables} comme des coins, des maximums ou des minimums, des \guil{points triples} (jointures de trois contours), etc. Une autre possibilité est de choisir des points selon une grille régulière et à une ou plusieurs échelles fixes (échantillonnage dense). Dans les deux cas, les points retenus sont caractérisés par l'histogramme par blocs des directions de gradient dans leur voisinage à l'échelle retenue. Ces histogrammes sont en général creux et ils caractérisent bien la position et la direction des différents contours dans le voisinage, ce qui est caractéristique du type de point. La représentation résultante est robuste par rapport à plusieurs facteurs, notamment l'intensité lumineuse puisque celle-ci n'influe pas sur la direction des gradients. La robustesse par rapport aux changements d'échelle est, elle, assurée par la  détermination d'une échelle \guil{naturelle} lors du processus de détection des points. Le voisinage pris en compte peut également être rectifié selon la direction déterminée lors du processus de détection des points de façon à obtenir une représentation robuste aux rotations.

\smallskip
Les représentations des points SIFT ont initialement été introduits en utilisant uniquement la composante de luminance comme cela se faisait classiquement pour la caractérisation des textures et pour la détection des points de contour. Il est possible de calculer de telles représentations sur des images en couleurs, simplement en concaténant celles calculées indépendamment sur chacune des composantes dans un espace de couleurs donné~\citep{vandesande:2010}. De même, il existe des généralisations pour les représentations des plans vidéos avec la détection et la caractérisation de points dans une volume tridimensionnel (deux dimensions d'espace et une dimension de temps), dont la représentation STIP ({\em Spatio-Temporal Interest Points}) proposée par~\cite{laptev:2005}, basée sur des histogrammes de direction de gradient (HOG) et sur des histogrammes de flot optique (HOF) dans le voisinage d'un point détecté.

\subsection{Agrégation de représentations locales}
\label{sec:agregation}

La représentation complète d'une image à base de points SIFT ou d'un plan vidéo à base de points STIP est un ensemble de points détectés avec, pour chacun d'entre eux, ses coordonnées, son échelle, son orientation et sa description locale. L'avantage de ces représentations est qu'elles sont riches, robustes et précises. Elles rendent possibles des mesures de similarité très précises entre des images basées sur des méthodes de type RANSAC (pour pour {\em RANdom SAmple Consensus}) ; ces méthodes itératives permettent de sélectionner des appariements de points respectant des contraintes de cohérence topologiques. Leur inconvénient est le volume de données associées et le temps de calcul des mesures de similarité. Dans le but de retrouver des représentations plus compactes et de taille fixe, associées à des mesures de similarité simples et facilement calculables, des méthodes d'aggrégation ont été proposées, parmi lesquelles les plus populaires sont les \guil{sacs de mots visuels} et les \guil{vecteurs de Fisher}.

\subsubsection{Sacs de mots visuels}

Comme son nom l'indique, l'approche \guil{sacs de mots visuels} consiste à adapter l'approche \guil{sacs de mots} couramment utilisée dans le cas des documents textuels aux images et vidéos. Elle consiste à définir un \guil{vocabulaire visuel} et à représenter les images ou les plans vidéo par des histogrammes d'occurrence des \guil{mots visuels} dans ceux-ci~\citep{sivic:2003,csurka:2004}. Le vocabulaire visuel est construit par un {\em clustering} des représentations locales des points SIFT (resp. STIP) sur l'ensemble des images (resp. plans vidéo) d'une collection d'entraînement. Le clustering peut être réalisé par exemple par la méthode des $k$-moyennes et les mots visuels sont représentés par les centroïdes des clusters trouvés. Pour une image (resp. un plan vidéo) quelconque, les points SIFT (resp. STIP) sont détectés et leurs représentations locales sont calculées. Chaque représentation locale est associée au cluster dont elle est la plus proche du centroïde et on calcule ensuite un histogramme en comptant pour chaque centroïde le nombre de points détectés qui leur sont associés. Ces histogrammes sont généralement normalisés selon la norme $L_1$ ou $L_2$. Comme dans le cas des histogrammes de couleurs, les images ainsi représentées peuvent être comparées en utilisant la distance du $\chi^2$ ou celle de Wasserstein, ou encore la distance euclidienne si un opérateur racine carrée a préalablement été appliqué sur les composants des histogrammes. La taille de la représentation est le nombre de clusters choisis pour la construction du vocabulaire visuel~; elle est typiquement comprise entre 256 et 4096.

\subsubsection{Vecteurs de Fisher}

Dans le cas des représentations à base de vecteurs de Fisher~\citep{sanchez:2013}, la distribution des représentations locales des points SIFT (resp. STIP) extraits d'une collection d'entraînement est modélisée par un mélange de gaussiennes diagonales. Nous ne donnerons pas le détail du calcul ici, mais ce que capture la représentation par vecteurs de Fisher est la façon dont il faut modifier les paramètres des gaussiennes pour ajuster la distribution trouvée sur la collection d'entraînement à la distribution de l'image dont on veut calculer la représentation. Ces représentations sont de taille fixe comme les sacs de mots visuels mais elles sont plus volumineuse et plus précises. Leur taille est égale au nombre de gaussiennes choisies pour modéliser la distribution sur la collection (typiquement de 64 à 256) multiplié par le nombre de composantes dans la description locale (128 dans le cas de points SIFT) et multiplié par deux (une valeur pour la moyenne et une pour la variance). Le fait que ces vecteurs soient de grande dimension présente l'avantage que les méthodes de classification comme les SVM peuvent être appliquées directement dans leur version linéaire.

\subsection{Représentations apprises}

Les réseaux de neurones profonds traitent les images de bout en bout ({\em end-to-end}), c'est-à-dire qu'ils prennent en entrée directement les plans RVB de pixels, seulement après redimensionnement, rognage et soustraction de l'image moyenne. L'extraction des représentations est faite directement par les premières couches du réseau, avec des représentations locales dans les couches de convolution et globales dans les couches complètement connectées. L'avantage est qu'elles sont apprises en même temps que le reste du classificateur et qu'elles sont donc beaucoup plus optimisées que des représentations conçues par ingéniérie comme celles décrites précédemment. De plus, les représentations ainsi apprises sur des corpus variés et de grande taille comme ImageNet~\citep{russakovsky:2015} sont très générales et utilisables pour des tâches très variées et très différentes de celle sur laquelle elles ont été apprises~\citep{razavian:2014}. Ces représentations apprises conduisent à des performances généralement supérieures à celles obtenues avec des représentation classiques, rendant ces dernières obsolètes.

\section{Exercices}
\label{sec:pretraitement-exercices}

\begin{itemize}[itemindent=20mm]
%=======
\Quest{2.1}\textbf{Types \textit{vs} mots}

\noindent Combien y a-t-il de types dans le texte suivant, extrait des \textit{Lettres à un jeune poète} de Rainer Maria Rilke ?

\vspace{0.3cm}
\texttt{\noindent
Celui qui s'efforce de vous réconforter, ne croyez pas, sous ses mots simples et calmes qui parfois vous apaisent, qu'il vit lui-même sans difficulté. Sa vie n'est pas exempte de peines et de tristesses, qui le laissent bien en deçà d'elles. S'il en eût été autrement, il n'aurait pas pu trouver ces mots-là.
}
\vspace{0.3cm}

\noindent Combien y a-t-il de mots pleins dans ce même texte?

\Quest{2.2}\textbf{Impact des prétraitements textuels}

\noindent Les opérations de normalisation et filtrage permettent :

\vspace{0.3cm}
\begin{description}
\item[(a)] rapprocher les documents les uns des autres ;
\item[(b)] éloigner les documents les uns des autres ;
\item[(c)] obtenir une meilleure représentation des documents.
\end{description}
\vspace{0.3cm}

Dans le cas de la recherche d'information, ces opérations sont effectuées sur les requêtes et documents. Dans ce cas, permettent-elles d'améliorer~:

\vspace{0.3cm}
\begin{description}
\item[(a)] la précision du système, c'est-à-dire sa capacité à se concentrer sur des documents pertinents ?
\item[(b)] le rappel du système, c'est-à-dire sa capacité à ne pas rater de documents pertinents ?
\end{description}

\end{itemize}

