\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram}
\graphicspath{{xups98-03_figures}}
\setcounter{tocdepth}{2}
%\XUPScorrections
\usepackage{xups98-03}


\begin{document}
\frontmatter
\title[Mathématiques appliquées
et traitement du signal]{Rencontre des~mathématiques~appliquées
et~du~traitement~du~signal}
\author[\initial{S.} \lastname{Mallat}]{\firstname{Stéphane} \lastname{Mallat}}
\address{Centre de Mathématiques Appliquées,
École Polytechnique, 91128 Palaiseau Cedex}
\email{stephane.mallat@ens.fr}
\urladdr{https://www.di.ens.fr/~mallat/}

\thanks{Journées X-UPS 1998. Analyse de Fourier et traitement d'images. Prépublication du Centre de mathématique de l'École polytechnique, 1998}

\maketitle
\tableofcontents

\mainmatter
\section{Au-delà de Fourier}

La transformée de Fourier a longtemps dominé le traitement du
signal, laissant peu de place à de nouveaux
outils mathématiques.
Jusqu'aux années 70, les signaux étaient le plus souvent des
enregistrements de paroles ou de sons, modélisés
par des réalisations de processus gaussiens. En conséquence,
les algorithmes linéaires étaient considérés comme optimaux.
En ajoutant une hypothèse de stationnarité, on se retrouve
dans le pré carré des opérateurs de convolution, qui
sont diagonalisés par la transformée de Fourier.

La situation a complètement changé avec le développement du
traitement d'images dans les années 80. Les images sont mal
modélisées par des processus gaussiens, et les composantes
transitoires telles que les contours sont souvent
plus importantes que les propriétés stationnaires.
L'utilisation d'algorithmes non linéaires est devenue
néces\-saire, ce qui a ouvert le traitement du signal
aux mathématiques modernes. Au-delà des applications
classiques pour la transmission, le codage et la
restauration, le traitement du signal s'est aussi
engagé dans le traitement de l'information,
notamment pour la reconnaissance vocale
et la vision par ordinateur.

La construction de représentations compactes est à la
base de nombreux problèmes de traitement du signal
et de l'information. Une repré\-sen\-tation compacte caractérise
l'approximation d'un signal (fonction) avec peu de paramètres,
qui peuvent être des coefficients de décomposition dans
une base ou dans un \og dictionnaire\fg plus large.
Des traitements non linéaires complexes peuvent souvent
s'implémenter par
des algorithmes simples et rapides dans de telles
représentations. L'utilisation de représentations compactes
est un outil que l'on retrouve dans de nombreuses
branches des mathématiques.
Nous montrons que l'étude d'applica\-tions à la compression
d'images, au débruitage et à la modélisation stochastique
de signaux nécessite d'utiliser des résultats récents
en théorie de l'approximation, en analyse harmonique,
en théorie des opérateurs, en statistique et en probabilités.

\section{Représentations compactes}

L'élaboration de représentations compactes est clairement
utile pour le codage de signaux, mais elle est aussi nécessaire
pour réduire la complexité des problèmes de classification
et d'identification pour des signaux de grandes tailles.

\subsection{Modèles d'images}

L'interprétation bayésienne du monde considère un signal $f(x)$
comme la réalisation d'un processus stochastique $F(x)$.
La mesure de l'erreur introduite par un algorithme se fait
en moyenne relativement à la distribution de probabilité
de $F$.
Les images \og naturelles\fg sont des réalisations de processus
non-gaussiens, et il n'y a pas encore de modèle stochastique
qui incorpore la diversité de scènes complexes incluant
contours et textures, telle que dans l'image \ref{Lena}(a).
Cela explique l'utilisation de modèles plus pauvres mais plus
réalistes, qui représentent les signaux comme des fonctions appartenant
à un ensemble $\bS$ de $\Ld [0,1]^d$, sans imposer de condition
a priori sur leur distribution de probabilité dans cet ensemble.
Pour un problème particulier, on essaye alors de minimiser l'erreur
maximum pour les signaux dans $\bS$, ce que l'on appelle un
problème {\it minimax}. La discrétisation d'un signal
$f$ avec $N$ échantillons est simplement une
projection dans un sous-espace de dimension $N$.

De nombreuses images, dont l'image
\ref{Lena}(a), ont une variation totale bornée.
Sur $[0,1]$ la variation totale de $f(x)$ mesure la
somme des amplitudes de ses oscillations
\[
\|f\|_\TV = \int |f' (x)|\, d x < +\infty.
\]
La variation totale d'une image sur $[0,1]^2$ est définie par
\[
\|f\|_\TV = \iint |\grad f (x)|\, d x \leq C.
\]
Cette norme a une interprétation géométrique simple, basée
sur les courbes de niveaux de l'image. Soit
\[
\Omega_t = \{ (x,y) \in \R^2~:~f(x,y) > t \}.
\]
Si $H^1(\partial \Omega_t) $ est la mesure de
Hausdorff mono-dimensionnelle de la frontière de $\Omega_t$ alors
\begin{equation}
\label{BoundVariPerimet}
\|f\|_\TV = \int_{-\infty}^{+\infty} H^1(\partial \Omega_t)\, dt.
\end{equation}
Une image à variation bornée a aussi une amplitude bornée,
et appar\-tient donc à un ensemble du type
\begin{multline}
\label{BouvnDVtwo}
\bS_\BV = \textstyle\big\{f~:~ \|f\|_\TV = \iint |\grad f (x)|\, d x \leq C,\\
\textstyle\|f\|_\infty = \sup_{x \in [0,1]^2} |f(x)| \leq C \big\}.
\end{multline}
Les images dans $\bS_\BV$ ont des courbes de niveau qui sont
presque toutes de longueur finie.
Bien que simple, ce modèle est suffisant pour illustrer les
idées principales et les difficultés pour construire des
représentations d'images.
Des classes plus restreintes d'images,
telles que des textures homogènes, sont mieux modélisées par
des processus aléatoires tels que
des champs de Markov, qui sont étudiés dans la
section \ref{proce-sec}.

\subsection{Représentations par approximations}

Une représentation compacte de $f \in \Ld [0,1]^d$ peut s'obtenir
en tronquant sa décomposition dans une base
orthonormale $\bB = \{ g_m \}_\mN$
\[
f = \sum_{m=0}^{+\infty} \lb f, g_m \rb \, g_m.
\]
Comprendre la performance de représentations compactes dans une
base est un sujet central de la théorie de l'approximation.
Nous expliquons pourquoi il est nécessaire d'utiliser des
représentations non linéaires, mais une introduction
plus complète est donnée dans \cite{DeVore98}.

Une approximation linéaire de $f$ à partir de $M$
produits scalaires
$\lb f, g_m \rb$ est une projection orthogonale dans l'espace
$\V_M$ engendré par~$M$~vecteurs de $\bB$, disons les $M$ premiers,
\[
f_M = P_{\V_M} f = \sum_{m=0}^{M-1} \lb f, g_m \rb \, g_m.
\]
L'erreur d'approximation maximum sur un ensemble de signaux
$\bS$ est
\[
\epsilon_l (\bS,M) = \sup_{f \in \bS} \|f - f_M \|^2 =
\sup_{f \in \bS} \sum_{m=M}^{+\infty} |\lb f, g_m \rb|^2.
\]
Une telle représentation est efficace si
$\epsilon_l (\bS,M)$ a une décroissance rapide lorsque
$M$ augmente, et donc si
$|\lb f, g_m \rb|$ a une décroissance rapide lorsque $m$ croît.
Cela dépend du choix de $\bB$ relativement à~$\bS$.
Par exemple, les fonctions uniformément régulières sont bien
approximées par
$M$ sinusoïdes de basses fréquences dans une base de Fourier
$\{\Exp^{i 2 \pi m x} \}_\mZ$ de $\Ld [0,1]$.
Si $\bS$ est inclus dans une boule d'un espace de
Sobolev $\W^s [0,1]$ de fonctions de période $1$ alors la décroissance
des coefficients de Fourier aux hautes fréquences implique que
$\epsilon_l (\bS,M) = O(M^{-2s})$ \cite{DeVore98}.
Les fonctions à variation bornée peuvent avoir des discontinuités,
et ne sont pas bien approximées dans une base de Fourier.
On démontre que dans une boule
$\bS_\BV$ de fonctions à variation bornée, la décroissance la
plus rapide qui puisse être obtenue dans une base $\bB$ est
$\epsilon_l (\bS_\BV,M) \sim M^{-1}$ \cite{DeVore98}.


Pour améliorer ce résultat, il est nécessaire d'utiliser une
représentation plus adaptée au signal, qui projette $f$ sur
$M$ vecteurs sélectionnés en fonction de $f$
\begin{equation}
\label{NONlinEapr}
f_M = \sum_{m \in I_M} \lb f, g_m \rb \, g_m.
\end{equation}
Comme $\|f - f_M\|^2 = \sum_{m \nin I_M} |\lb f, g_m \rb|^2$,
la meilleure approximation est obtenue en sélectionnant dans
$I_M$ les $M$ vecteurs dont l'amplitude des produits scalaires
$|\lb f, g_m \rb|$ est maximum.
Cette approximation dépend de $2M$ paramètres, les $M$ indexes
dans $I_M$ et les $M$ coefficients $\{\lb f, g_m \rb \}_{m \in I_M}$.
Soit $c_k = \lb f, g_{m_k} \rb$ le coefficient dont l'amplitude
est de rang $k$
\[
|c_k| \geq |c_{k+1}|\quad\mbox{pour $k \geq 1$}.
\]
L'erreur d'approximation est
\[
\|f - f_M\|^2 = \sum_{k=M+1}^{+\infty} |c_k|^2
\]
et
\[
\epsilon_n (\bS,M) = \sup_{f \in \bS} \|f - f_M\|^2.
\]
Cette erreur dépend de la vitesse de décroissance des coefficients ordonnés
$|c_k|$ pour les signaux dans $\bS$. Dans la base $\bB$, une boule
$\wlp$ de rayon $C$ est définie par
\begin{equation}
\label{weak-LPball}
\bS_{\wlp} = \{ f~:~|c_k|= |\lb f, g_{m_k}\rb| \leq C \, k^{-1/p} \}.
\end{equation}
On vérifie facilement que
$\bS \subset \bS_\wlp $ pour un $C > 0$ et $p < 2$
si et seulement si
$\epsilon_n (\bS,M) = O( M^{1-\sfrac 2 p})$.
La difficulté principale de l'approximation non linéaire est
de calculer le $p$ minimum et la base correspondante
$\bB$ telle que
$\bS \subset \bS_\wlp $. Une telle base est dite
{\it optimale} pour l'approximation non linéaire de $\bS$.
Les bases inconditionnelles sont des exemples de bases
optimales.

Une base orthonormale $\bB$ est
une base {\it inconditionnelle} d'un sous-espace de Banach
$\BB \subset \Ld [0,1]^d$ s'il existe $A$ tel que
pour toute suite de signes
$s_m \in \{-1,1\}$ et $f \in \BB$
\[
\|f\|_\BB =
\bigg\|\sum_{m=0}^{+\infty} \lb f, g_m \rb \, g_m\bigg\|_\BB \leq
A \bigg\|\sum_{m=0}^{+\infty} s_m\, \lb f, g_m \rb \, g_m\bigg\|_\BB.
\]
Le fait que $\|f\|_\BB < +\infty$ ne dépend donc que des
amplitudes
$|\lb f, g_m \rb |$, et peut être relié à une condition sur
la décroissance des coefficients ordonnés.
On démontre \cite{DeVore98} que si
$\bB$ est une base inconditionnelle de
$\BB$ alors c'est une base optimale pour l'approximation non linéaire
d'une boule
$\bS = \{ f~:~\|f\|_\BB \leq C \}$ de $\BB$.

\subsection{Grille adaptative par ondelettes}

Les bases d'ondelettes ont d'importantes applications en mathématiques
et en traitement du signal car elles permettent de construire
des représentations compactes pour de larges classes de fonctions.
Les premières bases d'ondelettes orthonormales de
$\LD$ furent introduites par
Strömberg et Meyer \cite{Meyer92c}.
L'interpré\-tation par multirésolution des bases d'ondelettes
donne un cadre général pour construire pratiquement toutes
les ondelettes qui engendrent une base orthonormale de $\LD$
\cite{Mallat89b}.
Cela permet aussi d'introduire un algorithme rapide qui
nécessite que $O(N)$ opérations pour calculer $N$ coefficients
en ondelettes \cite{Mallat98}.
Daubechies \cite{Daubechies92} a découvert des ondelettes à support
compact, et les bases résultantes ont été adaptées
à $\Ld [0,1]^d$. Nous résumons ici les résultats principaux.

\Changel

Une bases orthonormale d'ondelettes de $\Ld [0,1]$ est une famille
de fonctions
\[
\bB = \Bigl(
\{ \phi_\ln \}_{0 \leq n < 2^l}~\cup~
\{ \psi_\jn \}_{j\geq l, 0 \leq n < 2^j}\Bigr).
\]
A la résolution $2^l$,
les {\it fonctions d'échelles} $\{ \phi_\ln \}_{0 \leq n < 2^l}$
engendrent un espace $\V_l$ qui inclut les polynômes de degré
$q$, pour un certain $q \geq 0$.
Les ondelettes $\psi_\jn$ aux hautes résolutions $2^j > 2^l$
sont donc orthogonales aux polynômes de degré $q$.
Les ondelettes $\psi_\jn$ dont le support est inclus dans
$]0,1[$ sont obtenues par dilatation et translation d'une
ondelette \og mère\fg $\psi$:
\[
\psi_\jn (t) = \sqrt {2^j}\, \psi(2^j t - n ).
\]
Les ondelettes de bord sont modifiées pour maintenir leur support
à l'intérieur de
$[0,1]$.

Une approximation linéaire de $f$ à partir de $M = 2^J > 2^l$
ondelettes et fonctions d'échelle est calculée en gardant tous les
coefficients aux résolutions $2^j < 2^J$:
\[
f_M = \sum_{n=0}^{2^l}
\lb f, \phi_\ln \rb\, \phi_\ln +
\sum_{j=l}^{J-1} \sum_{n=0}^{2^j}
\lb f, \psi_\jn \rb\, \psi_\jn.
\]
La première somme donne une approximation grossière de $f$
à la résolution $2^l$, et chaque somme partielle
$\sum_{n=0}^{2^j} \lb f, \psi_\jn \rb\, \psi_\jn$ apporte les
\og détails\fg qui améliorent cette approximation de la résolution~$2^{j}$ à la résolution $2^{j+1}$.
Si $f$ est continue,
cette approximation linéaire à la résolution $2^J$
est essentiellement
équivalente à une approximation sur une grille uniforme
calculée en interpolant les échantillons
$\{f(2^{-J} n) \}_{0 \leq n < 2^J}$.
Comme une approximation de Fourier linéaire, cette appro\-ximation
est précise si et seulement si
$f$ est uniformément régulière.
On obtient de mauvaises approximations
pour des fonctions ayant des singularités, telles que les fonctions
à variations bornées.

Une approximation non linéaire par ondelettes garde les $M$
coefficients d'am\-plitude maximum.
L'amplitude de $|\lb f, \psi_\jn \rb|$ dépend de la régularité
locale de $f$.
Supposons que
l'ondelette mère $\psi$ soit $\bC^{q+1}$ et qu'elle soit
orthogonale aux polynômes de degré $q$.
On démontre alors \cite{Meyer92c} que
$f$ est uniformément Lipschitz $\alpha < q+1$ sur un intervalle $[a,b]$
si et seulement s'il existe $A > 0$ tel que pour tout
$\psi_\jn$ dont le support est inclus dans $[a,b]$ (modulo des
problèmes de bord)
\[
|\lb f, \psi_\jn \rb| \leq A\, 2^{-(\alpha+1/2)j}.
\]
Dans les domaines où la régularité lipschitzienne $\alpha$ est grande,
$|\lb f, \psi_\jn \rb|$ a une décroissance rapide lorsque la
résolution $2^j$ augmente. A haute résolution $2^j$,
les grands coefficients apparaissent dans le voisinage des
singularités, où
$0 \leq \alpha < 1$.
Un plus grand nombre de coefficients en ondelettes est gardé
au voisinage des singularités. Cette approximation
est équivalente à un échantillonnage sur grille adaptative dont la
résolution est augmentée au voisinage des singularités.

L'impact des bases d'ondelettes en analyse fonctionnelle vient
du fait qu'elle sont des bases inconditionnelles
d'une large famille d'espaces, appelés espaces de {\it Besov}.
Bien que l'espace $\BV$ de fonctions à variations bornées n'admette
aucune base inconditionnelle, $\BV$ peut être encadré par deux
espaces de Besov.
Cela permet de démontrer que
les bases d'ondelettes sont optimales pour approximer
les fonctions d'une boule $\bS_\BV$. On peut montrer que
l'ensemble $\bS_\BV$ est inclus dans la boule
$\wlp$ (\ref{weak-LPball}) pour
$p = 2/3$ mais pas pour $p < 2/3$ \cite{DeVoreJP92}.
Donc
$\epsilon_n (\bS_\BV,M) = O(M^{1 - 2/p}) = O( M^{-2})$.
Lorsque $M$ augmente, la décroissance asymptotique de
$\epsilon_n (\bS_\BV,M)$ est donc plus rapide que
l'erreur de n'importe
quelle approximation linéaire utilisant $M$ paramètres,
qui décroît au mieux comme $M^{-1}$.

En deux dimensions, les bases d'ondelettes sont construites
avec 3 ondelettes mères, $\psi^k$ pour $1 \leq k \leq 3$,
qui sont dilatées et translatées
\[
\psi^k_\jn (x) = \psi^k_{j,(n_1,n_2)} (x_1,x_2)
= 2^j\, \psi^k (2^j x_1 - n_1, 2^j x_2 - n_2).
\]
Des modifications appropriées sont faites aux bords de telle sorte
que le support soit maintenu dans $[0,1]^2$. Une ondelette
$\psi^k_\jn$ a un support carré de taille proportionnelle
à $2^{-j}$, et centré près de
$2^{-j} n = (2^{-j} n_1, 2^{-j} n_2)$.
Une base orthonormale d'ondelettes de
$\Ld [0,1]^2$ est obtenue en incluant des fonctions
d'échelles qui engendrent un espace de basse résolution
\begin{equation}
\label{WaveBas2D}
\bB = \Bigl(
\{ \phi_\ln \}_{2^{-l} n\in [0,1)^2}~\cup~
\{ \psi^k_\jn \}_{j \geq l, \,2^{-j} n\in [0,1)^2, \,
1 \leq k \leq 3 } \Bigr).
\end{equation}

Une image discrète est un tableau de $N^2$ points (pixels),
avec $N = 512$ pour l'image \ref{Lena}(a).
La base d'ondelettes (\ref{WaveBas2D})
se discrétise pour définir une base orthonormale d'images ayant
$N^2$ pixels. Les coefficients en ondelettes de l'image
\ref{Lena}(a) sont montrés en \ref{Lena}(b).
Chaque sous-image donne la valeur de
\[
\{|\lb f, \psi^k_\jn \rb|\}_{2^{-j}n \in [0,1)^2}
\]
pour $j$ et $k$ fixés. Le nombre de coefficients en ondelettes
pour chaque sous-image est $2^{2j}$.
Le module de
chaque coefficient $|\lb f, \psi^k_\jn \rb|$ est représenté
par un point, qui est d'autant plus sombre que cette valeur
est grande.
Ces sous-images sont organisées par triplets, correspondant aux
indexes $1 \leq k \leq 3$. Les ondelettes pour $k=1,2,3$
sont sensibles aux variations de l'image selon dif\-férentes
orientations.
La~plupart des points sont blancs, ce qui signifie que la
majorité des coefficients d'ondelettes sont quasiment nuls.
Les quelques grands coefficients sont localisés là où l'intensité
de l'image varie brutalement, le long d'un contour ou sur
une texture.

\deuxps{MallatFig1a.pdf}{coef_Lena_4niv_seuil1.pdf}{5cm}{1cm}{5cm}{(a):
Image originale $f$. (b): Amplitude des coefficients $|\lb f,
\psi^k_\jn \rb|$ dans une base d'ondelettes. Les sous-images
correspondent à des résolutions $2^j$ et des orientations $k$
différentes (voir texte).} {Lena}

Une approximation linéaire à partir de
$M = 2^{2J}$ ondelettes est calculée en gardant tous les
coefficients aux résolutions $2^j < 2^J$.
Cette approximation sur une grille uniforme est particulièrement
inefficace pour des images ayant des discontinuités, ce qui
est souvent le cas. Pour une boule $\bS_\BV$ d'images
à variations bornées (\ref{BouvnDVtwo}), on démontre que
$\epsilon_l (\bS_\BV,M) = A > 0$.
Le maximum de l'erreur d'approximation ne décroît pas vers
zéro lorsque $M$ augmente.

Une approximation non linéaire est bien plus efficace car
elle garde les coefficients en ondelettes près des singularités
(\ref{BoundVariPerimet}). En particulier, on peut montrer
que $\bS_\BV$ est inclus dans une boule
$\bS_{wl^1}$ \cite{CohenDPX98} et donc que
$\epsilon_n (\bS_\BV,M) = O( M^{-1})$.
Une grille adaptative d'ondelettes donne une bien meilleure
approximation qu'une grille uniforme, et aucune autre
base orthonormale ne peut améliorer la vitesse de décroissance
de l'erreur d'approximation sur une boule $\bS_\BV$.

\Changelback

\subsection{Compression de signaux}

La transmission rapide de signaux au travers de canaux
à débit limité comme Internet, et le stockage de signaux
de grande taille, nécessitent d'effectuer une compression
en introduisant une erreur aussi faible que possible.
Le codage efficace d'un signal avec un nombre minimum de bits
utilise des représentations compactes.

Les ingénieurs en traitement du signal n'ont pas attendu
que les mathématiciens étudient les propriétés des
approximations non linéaires pour coder efficacement
des sons et des images dans des bases orthonormales.
C'est en 1986 que fut implémenté
le premier algorithme de
codage d'images dans une base d'ondelettes
\cite{WoodsO86}, avant même que ces bases ne soient étudiées en
mathématiques.
En effet, l'algorithme rapide de décomposition dans une base
d'ondelettes s'implémente avec un banc de filtres, qui fut
initialement introduit en traitement du signal pour
{\it multiplexer} des signaux (agréger plusieurs signaux
en un seul) \cite{CroisierEG76}. Une théorie des bancs de filtres
discrets a été élaborée en traitement du signal
\cite{VetterliK95}, mais ce n'est que plus tard que la connexion
avec les bases orthonormales d'ondelettes fut établie \cite{Mallat89b}.
Bien que les mathématiques soient arrivées plus tard, l'analyse
des performances de ces codeurs d'images demande d'utiliser des
résultats récents de la théorie de l'approximation, et
ceux-ci ouvrent des directions nouvelles pour des améliorations
potentielles.

Les signaux dans $\bS$ sont discrétisés et approximés à la résolution~$N$, ce qui signifie qu'ils appartiennent à un espace de dimension~$N$.
Un codage par transformée décompose $f$ dans une base orthonormale
$\bB = \{ g_m \}_\ZmN$
\[
f = \sum_{m=0}^{N-1} \lb f, g_m \rb \, g_m,
\]
et approxime chaque coefficient
$\lb f, g_m \rb$ par une valeur {\it quantifiée}, qui
est codée sur le moins de bits possibles.
Un quantificateur uniforme de pas $\Delta$ approxime chaque
$x\in \R$ par $Q(x) = k \Delta$,
avec $k \in \Z$ et $|x - Q(x)| \leq \Delta/2$.
Le signal quantifié résultant est
\[
\tilde f = \sum_{m=0}^{N-1} Q(\lb f, g_m \rb) \, g_m.
\]
Le problème est de minimiser la
{\it distorsion} maximum
$d(\bS,R) = \sup_{f \in \bS} \|f - \tilde f\|^2$ pour un nombre maximum
de bits $R$ alloués pour coder $\tilde f$.


\deuxps{MallatFig2a.pdf}{MallatFig2b.pdf}{5cm}{1cm}{5cm}{(a):
Image codée avec $0.25$ bits/pixel, en quantifiant les
coefficients en ondelettes de l'image \ref{Lena}.
(b): Image codée avec $0.125$ bits/pixel.}{Lena2}


Le calcul de la distorsion d'un codage par transformée est reliée à un
problème d'approximation non linéaire.
Soit $M$ le nombre de coefficients plus grands que $\Delta/2$
et $f_M$ l'approximation non linéaire de $f$ à partir de ces
$M$ coefficients
\[
f_M = \sum_{|\lb f, g_m \rb| > \Delta/2}
\lb f, g_m \rb \, g_m.
\]
Comme $Q(x) \!=\! 0$ quand $|x| \!<\! \Delta/2$, et que
$|x - Q(x)| \!\leq\! \Delta /2$, la dis\-torsion est
\begin{equation}
\label{DistorDON1}
d(f,R) = \|f - \tilde f \|^2 \leq \|f - f_M\|^2 +
M \,\frac {\Delta^2} 4.
\end{equation}
Supposons que $\bS$ soit inclus dans une boule $\bS_\wlp$
(\ref{weak-LPball})~de~rayon~$C$, avec $p \!<\! 2$,
si bien que $\|f \!-\! f_M \| \!=\! O(M^{1-2/p})$.
On note~\hbox{$M_0 \!=\! C^p (\Delta/2)^{-p}$}.
Comme
$|c_k| \!=\! |\lb f, g_{m_k}\rb| \!\leq\! C \,k^{-1/p}$, nécessairement
\hbox{$M \!\leq\! M_0$}. On vérifie aussi que
\begin{equation}
\label{DistorDON}
\begin{split}
d(\bS,R) &= \sup_{f \in \bS} d(f,R)\\[-5pt]
&\leq \sup_{f \in \bS} \|f - f_{M_0}\|^2 +
M_0 \,\frac {\Delta^2} 4 ~ = O(M_0^{-2/p + 1}).
\end{split}
\end{equation}
La distorsion totale dépend donc essentiellement de l'erreur
d'approximation non linéaire.
Pour optimiser le codage par transformée, il faut minimiser le
nombre de bits $R$ nécessaires pour coder les~$N$ valeurs
$\{Q(\lb f, g_m \rb)\}_\ZmN$ lorsque $f \in \bS$.
Pour de forts taux de compression, $N \gg M_0 \geq M$, auquel cas
une grande proportion $\psfrac {N-M} N$
des coefficients est annulée par la quantification.
Un codage entropique utilise des mots binaires
plus courts pour représenter les coefficients qui apparaissent
le plus souvent.
Sachant que $\bS \subset \bS_{\wlp}$, on peut construire un
tel code, qui nécessite au plus
$R \sim M_0 \,\log_2 \Psfrac {M_0} N$ bits \cite{Mallat98}.
On déduit de (\ref{DistorDON}) que
$d(\bS,R) = O(R^{1-2/q})$ pour tout $q > p$.

La décroissance de $d(\bS,R)$ est maximisée dans une base
$\bB$ qui est optimale pour l'approximation non linéaire de $\bS$,
car une telle base minimise l'exposant
$p$ tel que $\bS \subset \bS_\wlp$. En particulier, les
bases d'ondelettes sont optimales pour les images à variations
bornées et l'exposant minimum est $p=1$.
Les figures \ref{Lena2}(a,b) sont les images $\tilde f$ obtenues
en quantifiant les coefficients en ondelettes de la figure
\ref{Lena}(b). Elles sont codées respectivement avec
$\sfrac R N = 0.25$ bits/pixel et $0.125$ bits/pixel,
en optimisant le codage des coefficients nuls
\cite{Shapiro93}. L'image originale \ref{Lena}(a) est
codée avec $8$ bits/pixel, donc les taux
de compression sont respectivement $32$ et $64$.
Pour $0.25$ bits/pixel, l'erreur de distorsion n'est pratiquement
pas visible mais devient apparente pour $0.125$ bits/pixel.

\Changel

Le choix de la base dépend entièrement de la nature des signaux
dans $\bS$.
Pour des sons, des bases différentes doivent être choisies afin
d'approximer efficacement les structures oscillantes de
durées variables.
La figure \ref{greasy} montre l'enregistrement du mot
\og greasy\fg. Le~standard Dolby pour la compression audio utilise
une base de cosinus locale. Une telle base est
construite à partir d'une fonction paire
$w(t)$, que l'on appelle une {\it fenêtre}, dont le support est
inclus dans $[-l,l]$ et qui est translatée afin de couvrir l'axe
temporel:
\[
\sum_{p=-\infty}^{+\infty} |w(t -p \,l) |^2 = 1.
\]
Malvar \cite{Malvar92}, Coifman et Meyer \cite{CoifmanM91}
ont démontré qu'en imposant d'autres propriétés de symétrie
sur $w(t)$, la multiplication par des fonctions cosinus
engendre une base orthonormale de $\LD$
\begin{equation}
\label{localCosinBas}
\left\{ g_{p,k} (t) = \frac 1 {\sqrt {l}} \,w (t - p\,l )\,
\cos \Bigl( \pi k \, (l^{-1} t - p) \Bigr) \right\}_{\kN,\pZ}.
\end{equation}
Comme dans le cas des images, la performance d'un codage audio
dans une telle base dépend de la capacité à approximer les
sons avec peu de vecteurs de cette base.
Cependant, les meilleures mesures de distorsion audio ne sont pas des normes
$\LL^2$. Des techniques de masquage sont utilisées par les
ingénieurs pour introduire des erreurs de quantification qui
sont au-dessous des seuils de perception
\cite{Mallat98}, mais celles-ci
sont bien plus difficiles à comprendre mathématiquement.

\unps{MallatFig3.pdf}{8cm}{Enregistrement du son
\og greasy\fg échantillonné à $16$kHz.}{greasy}


\Changelback

\Subsection{Géométrie et représentations adaptatives}
\label{geom-sec}

Les bases d'ondelettes sont optimales pour représenter
la classe générale des images à variations bornées,
mais de meilleures approximations peuvent être obtenues
en utilisant la régularité géométrique des images.
La formule de variation totale (\ref{BoundVariPerimet}) montre
que les lignes de niveau d'une image à variation bornée ont
des longueurs presque toujours finies.
Cependant, cela n'impose aucune condition sur la régu\-larité
de ces lignes de niveau.
Dans l'image \ref{Lena}(a),
les contours sont le plus souvent des courbes régulières dans
le plan de l'image, ayant une faible courbure.
Comprendre comment utiliser cette régularité est
fondamental pour le traitement d'images.
Cela a notamment motivé de nombreux travaux
utilisant des équations différentielles partielles
non linéaires pour modifier la courbure des lignes de
niveau dans les images
\cite{LionsM93,OsherR90,ShapiroT93}.
Cette nouvelle branche du traitement d'images mathématique
a donné lieu à des applications intéressantes pour le
débruitage de la segmentation d'images. Cependant, nous
ne suivrons pas cette ligne de pensée, qui n'utilise pas
de fa\c{c}on explicite une représentation compacte des images.

Pour comprendre l'importance de la régularité géométrique,
nous consi\-dèrerons un exemple simple,
$f = \One_\Omega$, qui est la fonction indicatrice d'un
ensemble $\Omega$.
La frontière $\partial \Omega$ de $\Omega$ est une courbe
différentiable de longueur finie, dont la courbure
est bornée. Si le support carré de
$\psi^k_\jn$ n'intersecte pas $\partial \Omega$ alors
$\lb f, \psi^k_\jn \rb = 0$.
Les ondelettes $\psi^k_\jn$ sont translatées sur une grille
uniforme d'intervalle $2^{-j}$ et ont un support carré de taille
proportionnelle à $2^{-j}$, comme l'illustre la figure \ref{Omega}(a).
A la résolution $2^j$, il y a $O(2^j)$ ondelettes $\psi^k_\jn$ dont le
support intersecte $\partial \Omega$.
Les $M$ coefficients en ondelettes d'amplitude maximum, sélectionnés
par une approximation non linéaire, sont aux résolutions
$2^j \leq 2^{J} \sim M$. Les coefficients non sélectionnés produisent
une erreur $\|f - f_M\|^2 \sim M^{-1}$.

\deuxps{MallatFig4a.pdf}{MallatFig4b.pdf}{3.5cm}{2cm}{4.5cm}{(a):
Les ondelettes $\psi_\jn$ sont translatées sur une grille d'intervalle
$2^{-j}$, et ont un support carré proportionnel à $2^{-j}$.
Pour $f = \One_\Omega$, les points les plus sombres correspondent aux
ondelettes $\psi_\jn$ telles que $\lb f, \psi_\jn\rb \neq 0$. (b): Une
approximation linéaire par morceau de
$f = \One_\Omega$ est optimisée en choisissant le long
de la frontière des triangles qui sont étroits dans la direction
où $f$ est discontinue.}{Omega}

Une meilleure approximation linéaire par morceau s'obtient avec
une triangulation adaptative de $[0,1]^2$, utilisant $M$ triangles
\cite{DRippa93}. Comme la courbure de
$\partial \Omega$ est bornée, cette frontière peut être couverte
par $M/2$ triangles ayant une petite largeur proportionnelle
à $M^{-2}$ le long de la normale à $\partial \Omega$,
et une longueur d'ordre $M^{-1}$
le long de la tangente à $\partial \Omega$.
L'intérieur et l'extérieur de $\Omega$ sont couverts par $M/2$
grands triangles, comme l'illustre la figure \ref{Omega}(b).
Une fonction $f_M$ linéaire sur chaque triangle peut approximer
$f = \One_{\Omega}$ avec une erreur
$\|f - f_M\|^2 = O(M^{-2})$.
Cette erreur d'approximation est concentrée sur les triangles
qui intersectent la frontière $\partial \Omega$ et leur faible
largeur produit une erreur plus petite qu'avec des ondelettes
dont les supports sont carrés.
L'erreur est réduite car la représentation est adaptée aux
propriétés géométriques de $\partial \Omega$.

Construire un pont entre les contraintes géométriques et
des appro\-ximations adaptatives est un des problèmes fondamentaux
du \hbox{traitement} d'images.
Le système visuel humain est très sensible aux structures géométriques
telles que des \og coins\fg ou la régularité des contours
\cite{Marr82,Mumford91}. Les illusions de Kanizsa de la
figure \ref{Kanizsa} illustrent ce phénomène. Le contour
triangulaire est perceptible alors que l'intensité de l'image reste
constante au
milieu.
Cette illusion s'explique en imposant des contraintes géométriques
sur l'interprétation (modélisation) des images.
Par ailleurs, on sait \cite{Daugmann80} que les \og neurones simples\fg
du cortex visuel effectuent une décomposition de l'image sur
une famille de fonctions qui ressemblent à des ondelettes, mais
qui forment une famille plus redondante qu'une base et donc
offrent plus de flexibilité.
Cela semble indiquer que notre cerveau traverse constamment ce pont
entre l'analyse fonctionnelle et la géométrie.


\deuxps{MallatFig5a.pdf} {MallatFig5b.pdf}{4cm}{2cm}{5.2cm}{Les contours
apparents de ces triangles sont perceptibles dans des domaines où l'image
reste uniformément blanche.}{Kanizsa}

S'adapter à la géométrie des images peut s'interpréter comme un
exemple particulier d'un problème plus général d'approximation
adaptative. Une base est une famille complète dans un espace
fonctionnel, mais est souvent trop petite pour utiliser au mieux
la diversité des structures apparaissant dans un signal complexe.
Des approximations plus précises sont obtenues avec
$M$ vecteurs sélectionnés dans un dictionnaire plus large
$\bD = \{ g_\gamma \}_{\gamma \in \Ga}$, qui peut inclure
un nombre infini de bases.
Cela suit la même logique, qui motive une personne à élargir son
vocabulaire afin de former des phrases plus précises
et plus concises.
Pour la reconnaissance, il est aussi important de construire
des représentations qui satisfont certains invariants
relativement à des translations ou des transformations affines.
Cela impose davantage de conditions sur le dictionnaire \cite{MallatZ93}.
Un dictionnaire pour des images peut être construit avec des ondelettes
dont le support a une élongation et une orientation qui peuvent
varier arbitrairement.
Comme pour les triangles allongés de la figure
\ref{Omega}(b), la famille d'ondelettes choisie peut s'adapter à la
géométrie des courbes de niveau de l'image. De même,
les signaux audio sont mieux approximés dans un
dictionnaire de bases de cosinus locaux
(\ref{localCosinBas}), où la taille $l$ de la fenêtre
peut être adaptée à la durée des composantes du sons:
attaques, harmoniques, vibrato...

Une représentation adaptative est construite à partir d'un dictionnaire
$\bD$ en sélectionnant $M$ vecteurs $\{ g_{\gamma_k} \}_{1 \leq k \leq M}$
pour approximer $f$ avec une somme partielle
\[
f_M = \sum_{k=1}^{M} \alpha_k \, g_{\gamma_k}.
\]
En l'absence d'orthogonalité,
trouver les $M$ vecteurs qui minimisent
$\|f - f_M\|$ produit une explosion combinatoire.
Des algorithmes \hbox{gloutons} de poursuites ont été développés pour
éviter cette explosion
\cite{MallatZ93}. Ils sélectionnent les vecteurs
$g_{\gamma_k}$ un par un, en minimisant à chaque étape l'erreur
d'approximation. La performance de
ces algorithmes est cependant loin d'être optimale
\cite{DonohoC95,DeVore98}. Dans des dictionnaires
composés de bases orthonormales qui peuvent être structurées
dans des arbres,
Coifman and Wickerhauser \cite{CoifmanW92} ont développé un
algorithme rapide qui effectue une sélection \og reasonable\fg bien que
non-optimale des $M$ vecteurs d'approximation.
Il n'y a cependant pas de résultat de théorie
de l'approximation qui permette d'analyser la performance
de ces algorithmes hautement non linéaires, ou d'améliorer leur
précision.

Augmenter la taille du dictionnaire a un coût.
Plus le dictionnaire est grand, plus il faut de paramètres pour
caractériser l'index
$\gamma_k$ de chaque vecteur sélectionné.
Pour une erreur d'approximation fixée, en choisissant un dictionnaire
trop large, on augmente le nombre total de paramètres qui caractérisent
l'approximation $f_M$.
Trouver des dictionnaires de taille optimale est un autre problème
ouvert.

\section{Débruitage par seuillage}

La suppression d'un bruit, additionné lors de la mesure d'un signal
ou durant sa transmission, est un problème important où les
représentations compactes jouent un rôle crucial.
Dans une base qui transforme le signal en quelques coefficients
de grande amplitude plus un petit reste, une grande partie du
bruit est facilement supprimée avec un seuillage qui annule les
coefficients les plus petits.
Une version similaire a été utilisée pour enlever le
bruit des images de télévision, depuis les années 60.
Cependant, ce n'est que récemment que
Donoho et Johnstone \cite{DonohoJ94} ont développé les mathématiques
permettant de démontrer que ces estimateurs de seuillage sont
quasiment optimaux dans des représentations compactes, ce qui
a ouvert de nouvelles applications.

On note $f[n]$ les $N$ coefficients qui caractérisent
la projection de $f(x)$ sur un espace de dimension $N$.
On mesure des données bruitées
\begin{equation}
\label{DenoisPb}
D[n] = f[n] + W[n],
\end{equation}
où les coefficients $W[n]$ du bruit sont des variables aléatoires
gaussiennes indépen\-dantes. On dit alors que $W$ est un {\it bruit blanc}.
La figure \ref{DenoiseLena}(a) montre un exemple.
Un estimateur $F$ de $f$ est calculé en appliquant un opérateur $L$
sur les données, $F = L \,D$.
Le risque de cette estimation est
\[
r(L,f) = \Esp \{\|f - L D\|^2\}.
\]
On veut minimiser le risque maximum pour un ensemble $\bS$ de
signaux
\[
r(L,\bS) = \sup_{f \in \bS} r(L,f).
\]
Le but est de trouver un opérateur $L$ qui approche le risque
minimax
\[
r_o (\bS) = \inf_{L} r(L,\bS).
\]

Pour approcher l'optimum minimax, on sépare
les problèmes de représentation et d'estimation.
On construit d'abord une représentation en
décomposant $D = f + W$ sur une base orthonormale
$\bB = \{g_m \}_\ZmN$:
\[
\lb D,g_m\rb \,=\, \lb \f,g_m\rb + \lb W,g_m\rb.
\]
Un estimateur de seuillage est alors défini par
\begin{equation}
\label{estim-withtheta}
F = L_t D = \sum_{m=0}^{N-1} \theta_{T} (\lb D,g_m\rb ) \, g_m,
\end{equation}
avec $\theta_T(x) = x\,\One_{|x| > T}$.
Il annule tous les coefficients plus petits que~$T$, et garde
les autres. Le seuil $T$ est choisi comme étant juste au-dessus de
$\max_{0 \leq m < N} |\lb W,g_m\rb|$, avec une forte probabilité,
pour que $\theta_{T} (\lb D,g_m\rb ) = 0$ si
$\lb f,g_m\rb \approx 0$.

Comme $W$ est un bruit gaussien de variance $\sigma^2$,
dans n'importe quelle base $\bB$, les coefficients du bruit
$\lb W, g_m \rb$ sont des variables aléatoires gaussiennes
indépendantes de même variance $\sigma^2$.
Soit $M$ le nombre de coefficients tels que
$|\lb f, g_m \rb| \geq \sigma$, et $f_M$ l'approximation non linéaire
(\ref{NONlinEapr})
de $f$ calculée avec ces $M$ vecteurs.
Si $T = \sigma\, \sqrt {2 \log_\Exp N}$ alors
Donoho and Johnstone ont montré \cite{DonohoJ94} que
\[
r(L_t,f)
\leq (2 \log_\Exp N + 1)\,
\Bigl( \|f - f_M \|^2 + (M+1)\,\sigma^2
\Bigr).
\]
Cette borne supérieure est similaire à la
distorsion
(\ref{DistorDON1}) d'un codage par transformée.
Le risque est réduit en choisissant une base où il~y~a un petit nombre $M$ de grands coefficients d'amplitude supérieure
à~$\sigma$, qui produisent une petite
erreur d'approximation $\|f - f_M\|$.
Une fois de plus, le problème est de trouver une représentation
compacte et précise.
L'image \ref{DenoiseLena}(b) est une estimation calculée en
seuillant les coef\-fi\-cients en ondelettes de l'image bruitée
en (a).


\deuxps{MallatFig6a.pdf}{MallatFig6b.pdf}{5cm}{1cm}{5.5cm}{(a): Image
dégradée par l'addition d'un bruit blanc gaussien.
(b): Estimation par seuillage dans une base d'ondelettes.}{DenoiseLena}

La performance asymptotique d'un estimateur de seuillage est
calculée tandis que la résolution $N$ des mesures tend vers
$+\infty$. Pour un ensemble $\bS_0$ de signaux
$f(x)$, on définit une base orthonormale $\bB_0$ qui est
optimale pour l'approximation non linéaire.
Si $\bS_0$ est une boule dans un espace $\BB$ alors
on peut choisir $\bB_0$ comme étant une base inconditionnelle de
$\BB$. L'ensemble $\bS$ des signaux discrétisés est obtenu
par une projection dans un espace de dimension $N$. Ces signaux
sont décomposés dans une base discrétisée $\bB$ calculée
à partir de $\bB_0$ avec la même projection.
Lorsque que $N$ augmente, on démontre \cite{DonohoICM94} que
l'estimateur de seuillage est presque optimal au sens où
\begin{equation}
\label{Thresh-opt}
r(L_t,\bS) \leq O(\log N)\, r_o (\bS).
\end{equation}
Ce résultat s'applique aux signaux discrets provenant d'espaces
de Besov, décomposés dans une base d'ondelettes discrète.
Il reste aussi valable pour un ensemble $\bS_\BV$ de fonctions
à variations bornées, car~$\BV$ est encadré par deux espaces de Besov qui sont proches.
Dans ce cas, lorsque $N$ augmente,
le risque de l'estimateur de seuillage a une décroissance
plus rapide que le risque de n'importe quel estimateur linéaire.

L'efficacité d'un estimateur de seuillage dépend fondamentalement
de la représentation. Pour utiliser les propriétés
des structures complexes, telles que la régularité géométrique
des contours d'une image, le seuillage doit être calculé
dans des représentations plus flexibles, comme l'explique la
section \ref{geom-sec}.
L'optimalité minimax dans de telles représentations
adaptatives est encore mal comprise.


\section{Processus à interaction limitée}
\label{proce-sec}

Pour de nombreux problèmes de classification, dont la
reconnaissance de la parole et la discrimination de textures visuelles,
le signal observé est modélisé comme étant
la réalisation d'un processus qui doit être caractérisé.
Ceci est particulièrement difficile car le processus est souvent
non gaussien et non stationnaire, et une seule réalisation donne
peu d'informations pour l'identification.
Il est donc nécessaire de caractériser de tels processus avec
peu de paramètres pouvant être estimés avec peu de données.
Après l'étude de processus gaussiens non stationnaires, nous considérons
un modèle plus général basé sur les champs de Markov.

\Subsection{Processus gaussiens non stationnaires}
\label{Gauss-sec}

Les processus aléatoires gaussiens donnent des modèles utiles pour
de nombreuses classes de signaux, dont les enregistrements
de parole. Un processus gaussien $X(t)$ de moyenne
nulle pour $t \in \R$, est entièrement caractérisé par sa
covariance
\[
k(t,s) = \Esp \{X(t)\,X(s)\},
\]
qui est le noyau de l'opérateur de covariance $K$:
\begin{equation}
\label{IntegKernOp}
K f (t) = \int_{-\infty}^{+\infty} k(t,s)\,f(s)\,ds.
\end{equation}
Pour estimer cette covariance avec peu de réalisations,
il est nécessaire de réduire le nombre de coefficients
qui décrivent le noyau.
Cela peut être fait avec une base orthonormale
$\bB = \{ g_m \}_\mZ$ dans laquelle la matrice
\begin{equation}
\label{Kernel-coeffic}
\lb K g_m, g_n \rb = \int_{-\infty}^{+\infty}
\int_{-\infty}^{+\infty} k(t,s)\,g_m(s)\,g_n (t)\,ds\,dt
\end{equation}
a une décroissance rapide hors-diagonale.
Ces valeurs sont les coefficients de décomposition de
$k(t,s)$ dans une base orthonormale séparable
$\{g_n (t)\,g_m(s)\}_\nmZ$ de $\LDD$.

Trouver une représentation compacte pour cette matrice
revient à appro\-ximer
$k(t,s)$ avec peu de vecteurs dans une base séparable.
Si les coefficients de la matrice ont une décroissance rapide
hors de la diagonale, alors $K$ est bien approximée
(avec une norme sup ou de Hilbert Schmidt) par une matrice
à bande étroite $\tilde K$ dans $\bB$. Si~cette matrice
est positive, c'est la covariance d'un processus
gaussien~$\tilde X$ qui approxime $X$
\cite{MallatPZ96}.
Comme $\tilde K$ est représenté par une matrice bande dans $\bB$,
pour tout $m \in \N$ il existe un voisinage
$\bN_m$ qui inclut un nombre fini d'entiers tels que
si $n \nnin \bN_m$ alors
\[
\lb \tilde K g_m, g_n \rb = \Esp \{\lb \tilde X, g_m \rb\,
\lb \tilde X, g_n \rb\} = 0.
\]
Comme $\lb \tilde X, g_m \rb$ et $\lb \tilde X, g_n \rb$
ont une probabilité jointe gaussienne, ils sont indépendants
car non corrélés.
Dans la base $\bB$, les coefficients de~$\tilde X$
sont dépendants seulement dans de petits voisinages,
ce qui est un exemple particulier de champ de Markov.

Pour étudier les propriétés de $K$, on l'écrit sous forme d'opérateur
pseudo-différentiel \cite{Meyer92c}.
Soit
\[
\hat f (\om) = \int_{-\infty}^{+\infty}
f (s)\, \Exp^{-i\om s} \, ds
\]
la transformée de Fourier de $f$.
Le {\it symbole} de l'opérateur $K$ est
\[
\beta(t,\om) = p.v. \int_{-\infty}^{+\infty}
k (t,t-s)\, \Exp^{-i\om s} \, ds.
\]
En appliquant la formule de Parseval à
(\ref{IntegKernOp}), on obtient
\[
K f (t) = \frac 1 {2 \pi} \int_{-\infty}^{+\infty}
\beta(t,\om)\,\hat f(\om)\,\Exp^{i \om t}\, d\om.
\]
Par exemple, si $\beta(t,\om) = \sum_{p=0}^P a_p (t) \,(i \om)^p$
alors
$K = \sum_{p=0}^P a_p (t) \,(\frac{d} {dt})^p$
est un opérateur différentiel avec des coefficients variables.
Le processus $X$ est stationnaire si $k(t,s) = k(t-s)$, auquel cas
$\beta(t,\om) = \beta(\om)$ est le spectre de
$K$.
La transformée de Fourier est donc l'outil idéal pour
caractériser les processus gaussiens stationnaires.
Pour les processus non-stationnaires, il faut relier les
propriétés de $X(t)$ aux propriétés de
$\beta (t,\om)$, afin de déduire une base dans laquelle $K$ peut être
approximée par une matrice bande.

Les processus localement stationnaires $X(t)$ apparaissent dans de nombreux
systèmes physiques, pour lesquels les mécanismes qui produisent
les fluctuations aléatoires changent lentement dans le temps ou
dans l'espace \cite{priestley65}.
Sur de courts intervalles de temps $l$,
de tels processus peuvent être approximés par des processus stationnaires.
C'est le cas pour les signaux de parole et de nombreux sons.
Sur des intervalles suffisamment courts,
la gorge se comporte comme un résonateur stationnaire, qui est excité
par une source de bruit stationnaire.
Des processus localement stationnaires s'obtiennent en imposant
qu'il existe $A > 0$ tel que pour tout $j,k \geq 0$
\[
|\partial_t^k \partial_\om^j \beta (t,\om)| \leq A \, l^{j-k}.
\]
On démontre \cite{MallatPZ96} l'existence d'une base de
cosinus locaux (\ref{localCosinBas}) dans laquelle l'opérateur
$K$ est bien approximé par une matrice à bande étroite.
La taille $l$ de chaque fenêtre correspond à la taille des
intervalles de stationnarité.
Lorsque la taille $l(t)$ des intervalles de stationnarité varie
dans le temps, ce qui est le cas des signaux audio,
la covariance a des propriétés plus complexes et souvent n'appartient
pas aux familles classiques d'opérateurs pseudo-différentiels.
Selon la régularité de $l(t)$, on peut construire
des bases de cosinus locaux avec des fenêtres de longueurs adaptées,
qui définissent des représentations compactes de
tels opérateurs \cite{MallatPZ96}.


Les multifractales sont d'autres modèles importants de signaux, ayant des
propriétés d'auto-similarité \cite{MuzyBA94}.
Parmi les nombreux exemples, mentionnons les séries économétriques
telles que l'indice Dow Jones, des données physiologiques dont
certains enregistrements cardiaques, les fluctuations électromagnétiques
des radiations galactiques, certaines textures d'images, la
densité du trafic automobile...
Un mouvement brownien fractionnaire $X(t)$ d'exposant de
Hurst $H$ est un exemple canonique de processus gaussien fractal.
Ses incréments sont stationnaires, et il est auto-similaire au
sens où
$s^{-H} X(s t)$ a la même distribution de probabilité que
$X(t)$, pour tout $s > 0$.
Le symbole de la covariance $K$ de $X$ est
$\beta(t,\om) = \lambda \,|\om|^{-2H-1}$. Cela correspond à un
opérateur de Calderón-Zygmund de la première génération
\cite{Meyer92c}, dont on sait qu'il a une décroissance rapide dans
une base d'ondelettes.
En traitement du signal, les browniens fractionnaires sont souvent
approximés par un processus
$\tilde X$ dont la covariance $\tilde K$ est
diagonale dans une base d'ondelettes, ce qui donne un algorithme
rapide de synthèse \cite{MuzyBA94}.
Des conditions générales sur
$\partial_t^k \partial_\om^j \beta (t,\om)$ peuvent être établies
pour garantir que $K$ ait une décroissance rapide hors-diagonale
dans une base d'ondelettes \cite{JaffardB97}.
Les processus browniens multifractionnaires sont des exemples dont
les exposants de Hurst varient dans le temps:
$\beta (t,\om) = \beta_0(t)\, |\om|^{-2H(t)-1}$.
Des estimations précises de
$\beta_0 (t)$ et $H(t)$ s'obtiennent dans des bases d'ondelettes.

\enlargethispage{\baselineskip}%
Lorsque le processus est uniformément localement stationnaire ou
multifractal, la base qui comprime la matrice de covariance
est connue à l'avance. Pour des processus plus complexes, cette
base doit aussi être estimée, à partir de certaines informations
a priori.
Ceci est un problème d'approximation adaptive, similaire à celui
décrit dans la section \ref{geom-sec}, bien que
l'on approxime un opérateur plutôt qu'une fonction.
Des algorithmes de recherche de meilleure base ont été
introduits pour effectuer de telles approximations pour
des opérateurs de covariance \cite{MallatPZ96},
mais ces techniques ne sont qu'un premier pas dans un domaine
qui demande un travail de recherche plus approfondi afin
de comprendre les propriétés des estimateurs statistiques
résultants.


\Subsection{Champs de Markov sur des représentations adaptées}

La caractérisation et synthèse de textures visuelles est un
des problèmes les plus difficiles de la vision bas-niveau.
Des textures visuelles homogènes, telles que du bois, du marbre,
ou toute autre, sont stationnaires mais non gaussiennes.
La Figure \ref{Textures} montre deux exemples.
Il est nécessaire de modéliser de tels processus avec peu
de \hbox{paramètres} afin de pouvoir les identifier à partir d'une
seule réalisation. Ceci est possible car le système visuel humain
peut le faire.
L'importance de ce problème va bien au-delà de la discrimination
des textures visuelles. En effet, de nombreuses classes de signaux
telles que les séries financières ou les mesures de vitesse d'un champ
turbulent, ne peuvent être approximées par des processus gaussiens.
Il est nécessaire de construire un cadre suffisamment général, incluant
des processus qui peuvent modéliser de tels signaux.

Les champs de Markov sont devenus un outil attractif pour
modéliser les textures visuelles, grâce au travail de
Geman et Geman \cite{GemanG84}, qui ont introduit un algorithme
de relaxation stochastique pour échantillonner des distributions
de Gibbs.
Pour simplifier la présentation, nous nous restreignons à des
vecteurs aléatoires $X(n)$, où $n \in \Z^d$ varie sur une grille
$\bG$ de taille $N$. On définit un système de voisinages
$\bN = \{ \bN_n \}_{n \in \bG}$ tel que
$n \nnin \bN_n$, et $m \in \bN_n$ si et seulement si $n \in \bN_m$.
Pour tout $\bG_0 \subset \bG$, on note
$X(\bG_0)$ l'ensemble des valeurs prises par $X$ sur $\bG_0$.
On dit que $p(X)$ est la distribution de probabilité
d'un {\it champ de Markov aléatoire} relativement $ \bN$ si\vspace*{-3pt}
\[
p\bigl(X(n)~|~X(\bG-\{n\})\bigr) =
p\bigl(X(n)~|~X(\bN_n) \bigr).
\]
Un sous-ensemble $C$ de $\bG$ est appelé une clique si chaque
paire d'éléments dans $C$ sont des voisins. Soit
$\cal C$ l'ensemble de toutes les cliques. Si $X$ prend ses valeurs
sur un alphabet fini alors le théorème de
Hammersley-Clifford démontre que $p(X)$ est un champ
de Markov si et seulement s'il peut être écrit sous la forme d'une
{\it distribution de Gibbs} relativement à $\bN$\vspace*{-3pt}
\[
p(X) = \frac 1 Z \exp \Bigl[- \sum_{C \in \mathcal{C}} \phi_C (X)
\Bigr],
\]
où $Z$ est une constante de normalisation et $\phi_C$ est une
{\it fonction potentielle} qui dépend seulement des valeurs de $X$
dans la clique $C$.
Les modèles de Markov ont des propriétés intéressantes pour
la discrimination de texture et la restauration d'images, mais
un succès limité à cause de la difficulté d'incorporer
les interactions longues portées des pixels de certaines images.
Plusieurs approches ont été introduites pour contourner ce problème,
dont les techniques de renormali\-sa\-tion~\cite{Gidas89}.

Mumford et Zhu \cite{MumfordZ97} ont introduit un point de vue
différent en créant des champs de Markov sur des
représentations comprimées de~$X$,
plutôt que sur les échantillons $X(n)$.
Soit $\bD = \{ g_\gamma \}_{\gamma \in \Ga}$ un dictionnaire de
vecteurs, qui peut être une base orthogonale ou
plus redondante.
Soit $X_\gamma = \lb X, g_\gamma \rb$.
Un système de voisinage
$\bN = \{ \bN_\gamma \}_{\gamma \in \Ga}$ est définit sur $\Ga$.
Par exemple, si $\bD = \{ \psi^k_\jn \}_{k,j,n}$ est une base
d'ondelettes en deux dimensions,
l'index $\gamma = (k,j,n)$ définit l'orientation~$k$, la résolution
$2^j$ et la position $2^{-j} n$ de l'ondelette.
Un voisinage $\bN_{(k,j,n)}$ inclut typiquement les
ondelettes $\psi^{k'}_{j',n'}$ telles que $|j-j'| \leq 1$ et dont
la position $2^{-j'} n'$ est proche de $2^{-j} n$.
Les propriétés de multirésolution des bases d'ondelettes
permettent de construire des champs de Markov qui
incluent des interactions à courte et longue portées.

Pour construire un champ de Markov $X$ à partir de signaux
observés
$\{X^{\obs}_p\}_{0 \leq p < P}$, on effectue des mesures moyennées sur
$M$ cliques $\{ C_m \}_{0 \leq m < M}$, avec des fonctions
potentielles $\phi_{C_m}$,
\[
\mu^{\obs}_{C_m} = \frac 1 P \, \sum_{p=1}^{P} \phi_{C_m}
(X^{\obs}_p ).
\]
Si $X$ est stationnaire alors on calcule la moyenne empirique
sur tous les $\phi_{C_m}$ qui effectuent les mêmes opérations
en des points différents de l'image. Ces moyennes empiriques sont
des estimations de $\Esp \{ \phi_{C_m} \}$ pour le modèle
$X$ que l'on construit. Le plus souvent, les cliques
ont au plus deux éléments $C = \{\gamma, \gamma' \}$.
Des mesures de covariance correspondent à
$\phi_C (X) = X_\gamma \,X_{\gamma'}$. Cependant, des fonctions
potentielles différentes peuvent être utiles, telles que des moments
d'ordre $p$
\begin{equation}
\label{lpCovarC}
\phi_C (X) = |X_\gamma|^p \,|X_{\gamma'}|^p\quad\mbox{pour $p > 0$}.
\end{equation}

\quatps{MallatFig7a.pdf}{MallatFig7b.pdf}{MallatFig7c.pdf}{MallatFig7d.pdf}{4cm}
{1cm}{4.5cm}
{(a): Observation d'une texture uniforme. (b): Réalisation d'un modèle
de Markov par ondelettes calculé à partir de (a). (c): Le centre montre
un exemple de texture. (d): Le centre est identique a (c), tandis que
la périphérie est la réalisation d'un modèle de Markov par ondelettes,
calculé à partir de (c).} {Textures}

Le {\it principe d'entropie maximum} suggère de choisir $p(X)$
qui maximise l'entropie
\[
p(X) = {\rm arg}\, \max \Big\{- \int p(X) \,\log p(X) \, dX \Big\}.
\]
sous les contraintes
\begin{equation}
\label{ConstRans}
\Esp \{ \phi_{C_m} (X) \} \!=\!
\int\! \phi_{C_m} (X) \,p(X) \,dX = \mu^{\obs}_{C_m}\quad
\mbox{pour $1 \leq m \leq M$}.
\end{equation}
La distribution d'entropie maximum $p(X)$ est la plus
\og uniforme\fg étant donné les contraintes imposées par
les observations
$\mu^{\obs}_{C_m}$. \hbox{Aucune} \og information\fg supplémentaire n'est
donc introduite par le \hbox{modèle}.
La solution est calculée avec les multiplicateurs de Lagrange
\begin{equation}
\label{Gibb-parame}
p(X,\Lambda) = \frac 1 {Z(\Lambda)} \,\exp
\biggl(- \sum_{m=1}^M \lambda_m \, \phi_{C_m} (X)\biggr).
\end{equation}
Le vecteur de paramètres $\Lambda = \{\lambda_m \}_{1 \leq m \leq M}$
est caractérisé uniquement par les contraintes (\ref{ConstRans}),
si les fonctions potentielles satisfont une propriété d'indépendance
linéaire.

Si $\phi_{C_m} (X)$ sont des mesures de covariance
alors (\ref{Gibb-parame}) est une distribution de probabilité
gaussienne, et si $\bD$ est une base orthonormale alors
$\Lambda$ est calculée en inversant une matrice bande.
La maximisation de l'entropie est une
optimisation convexe \cite{GemanG84},
mais pour des fonctions potentielles générales
$\phi_{C_m}$, le vecteur $\Lambda$ ne peut être calculé analytiquement.
Les algorithmes numériques obtiennent
$\Lambda$ en estimant
$\Esp_{p(X,\Lambda)} \{ \phi_{C_m} (X ) \}$ à chaque itération, puis
en modifiant $\Lambda$ avec une descente de gradient afin de
satisfaire les conditions (\ref{ConstRans}).
Le calcul de
$\Esp_{p(X,\Lambda)} \{ \phi_{C_m} (X) \}$ est fait avec un
échantillonneur de Gibbs ou un algorithme de Monté Carlo, ce
qui nécessite beaucoup d'opérations.


Mumford et Zhu \cite{MumfordZ97} et Portilla et
Simoncelli \cite{SimoncelliP97}, utilisent de tels
champs de Markov pour construire un modèle à
partir d'une seule réalisation d'une texture.
Le modèle de Markov de Portilla et Simoncelli est calculé
sur une base d'ondelettes,
avec des contraintes sur la covariance et sur des moments
(\ref{lpCovarC}) avec $p=1$.
La texture \ref{Textures}(a) est l'unique observation utilisée pour
calculer les paramètres $\Lambda$ du modèle, avec une hypothèse
de stationnarité.
La figure \ref{Textures}(b) montre une réalisation du modèle de
Markov par ondelettes.
Cette réalisation est remarquablement proche de la texture originale,
au sens où elles ne peuvent pas être distinguées visuellement
en moins de $10^{-1}$ secondes (vision préattentive).
Un modèle similaire de Markov par ondelettes est calculé
à partir de la texture
de \og texte\fg de la figure~\ref{Textures}(c).
L'image \ref{Textures}(d) inclut
une réalisation de ce modèle de Markov à la périphérie de
la texture (c), que l'on ne distingue pas du centre par
vision \og préattentive\fg.

Les champs de Markov offrent un cadre général pour construire
des processus ayant des interactions locales dans une
représentation appropriée.
La validité de ces modèles dépend du choix de la représentation
et des fonctions potentielles $\phi_C$.
Comprendre comment optimiser ces deux composantes et analyser
les propriétés de tels champs de Markov sur des espaces
fonctionnels est un autre sujet ouvert.
\enlargethispage{-2\baselineskip}
\pagebreak[2]

\backmatter
\bibliographystyle{jepplain+eid}
\bibliography{xups98-03}
\end{document}
