+Nous nous focaliserons sur les techniques en lien avec les travaux que nous avons menés et qui ont donné lieu à des implémentations efficaces susceptibles de fournir des éléments opérationnels rapides pour le prétraitement des images.
+
+La figure \ref{fig-ny-noises} montre une image de synthèse issue de la base de test COIL \ref{adresse}, supposée sans bruit et qui sera considérée comme référence, ainsi que deux versions bruitées, respectivement avec un bruit gaussien d'écart type 25 et un bruit impulsionnel affectant 25\% des pixels.
+\begin{figure}
+ \centering
+ \subfigure[Sans bruit]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/ny256.png}}
+ \subfigure[Bruit gaussien $\sigma=25$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/ny256_gauss25.png}}
+ \subfigure[Bruit impulsionnel 25\%]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/ny256_sap25.png}}
+ \caption{Images 256$\times$256 en niveau de gris 8 bits utilisées pour l'illustration des propriétés des filtres. a) l'image de référence non bruitée. b) l'image corrompue par un bruit gaussien d'écart type $\sigma=25$. c) l'image corrompue par un bruit impulsionnel à 25\%.}
+\label{fig-ny-noises}
+\end{figure}
+
+\subsection{Les opérateurs de base}
+\subsubsection{Les algorithmes de voisinage}
+L'opération la plus employée dans les procédés de traitement d'image est sans doute la convolution. Selon les valeurs affectées aux coefficients du masque, le filtrage par convolution permet de réaliser bon nombre de traitements comme la réduction de bruit par moyennage ou noyau gaussien ou encore la détection de contours.
+Si la fonction définissant le masque de convolution est notée $h$, l'expression générale de la valeur estimée de pixel de coordonnées $(i,j)$ est donnée par
+\begin{equation}
+\widehat{u}(x, y) = \left(\bar{v} * h\right) = \sum_{(i < H)} \sum_{(j < L)}v(x-j, y-i)h(j,i)
+\label{convoDef}
+\end{equation}
+Dans les applications les plus courantes, $h$ est à support borné et de forme carrée et l'on parle alors de la taille du masque pour évoquer la dimension du support.
+ La figure \ref{fig-ny-convo} présente les résultats de la convolution par deux masques \textit{moyenneurs} $h_3$ et $h_5$ de taille différentes, appliqués à l'image corrompue par un bruit gaussien : on voit la diminution des fluctuations mais aussi le flou apporté et qui rend les contours d'autant moins définis que la taille du masque est grande. La troisième image montre le résultat de la convolution de l'image de référence par un masque \textit{dérivateur} $h_{dx}$ selon l'axe horizontal. On y constate la mise en évidence, incomplète, des contours.
+Les matrices définissant les masques sont les suivantes :
+
+\[h_3=\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}, h_{25}=\frac{1}{25}\begin{bmatrix}1&1&1&1&1\\1&1&1&1&1\\1&1&1&1&1\\1&1&1&1&1\\1&1&1&1&1\end{bmatrix}, h_{dx}= \begin{bmatrix}0&0&0\\-1&1&0\\0&0&0\end{bmatrix}\]
+
+\begin{figure}
+ \centering
+ \subfigure[Moyenneur 3$\times$3]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy3.png}}
+ \subfigure[Moyenneur 5$\times$5]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy5.png}}
+ \subfigure[Dérivateur horizontal]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_2dx.png}}
+\caption{.}
+\label{fig-ny-convo}
+\end{figure}
+
+Le filtrage médian \ref{médian\_tukey} est également une opération très employée en prétraitement pour sa simplicité et ses propriétés de préservation des contours alliées à une capacité de réduction de bruit gaussien importante.
+La valeur du niveau de gris de chaque pixel est remplacée par la médiane des niveaux de gris des pixels voisins. Un des intérêts de ce filtre réside dans le fait que la valeur filtrée est une des valeurs du voisinage, contrairement à ce qui se produit lors d'une convolution. Un autre est de bien filtrer les valeurs extrêmes et par conséquent de trouver naturellement son application dans la réduction du bruit impulsionnel.
+Toutefois, la non-linéraité de cette technique et sa complexité n'en ont pas fait un filtre très utilisé jusqu'à ce que des implémentation efficaces soient proposées, en particulier le filtre à temps de calcul ``constant'' décrit dans \ref{medianO(1)}. Il est à noter que le filtrage médian est souvent appliqué en plusieurs passes de voisinage restreint.
+La figure \ref{fig-ny-median} montre la réduction de bruit impulsionnel obtenu grâce au filtre médian, dans trois conditions distinctes : median 3$\times$3 en une ou deux passes, puis médian 5$\times$5.
+\begin{figure}
+ \centering
+ \subfigure[Médian 3$\times$3 une passe]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3.png}}
+ \subfigure[Médian 3$\times$3 deux passes]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3x2.png}}
+ \subfigure[Médian 5$\times$5 une passe]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med5.png}}
+\caption{Réduction du bruit impulsionnel par filtre médian.}
+\label{fig-ny-median}
+\end{figure}
+
+Le filtre bilatéral \ref{bilatéral\_filter} est une composition d'opérations que l'on peut voir comme un filtre de convolution dont les coefficients ne dépendraient pas uniquement de la position du pixel courant par rapport au pixel central, mais également de la différence de leurs intensités (cas des images en niveaux de gris).
+Si l'on note $\Omega_k$ le voisinage du pixel d'indice $k$, l'expression générale du niveau de gris estimé est donnée par
+\[\widehat{u_k}=\displaystyle\frac{\sum_{p\in \Omega_k}\left(F_S(x_p, x_k)F_I(v_p, v_k)v_p\right)}{\sum_{p\in\Omega_k }\left(F_S(x_p, x_k)F_I(v_p, v_k)\right)} \]
+où $F_S$ et $F_I$ sont les fonctions de pondération spatiale et d'intensité. Classiquement, $F_S$ et $F_I$ sont des gaussiennes de moyennes nulles et d'écarts type $\sigma_S$ et $\sigma_I$.
+Ce filtre se prête également bien à une utilisation en plusieurs passes sans flouter les contours. Des approximations séparables du filtre bilatéral, comme celle proposée dans \ref{bilateral-sep}, permettent d'obtenir des vitesses d'exécution plus élevées que les versions standard. Une variante à temps de calcul constant à même été proposée en 2008 par Porikli \ref{dans bilateral-sep ref 1 porikli}.
+Ce filtre permet un bon niveau de réduction de bruit gaussien, mais au prix d'un nombre de paramètres plus élevé à régler, ce qu'illustre la figure \ref{fig-ny-bilat} où le filtrage de la même image a été réalisé avec 9 combinaisons de $\sigma_S$ et $\sigma_I$.
+\begin{figure}
+ \centering
+\subfigure[$\sigma_S=1.0$ et $\sigma_I=0.1$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_01.png}}
+\subfigure[$\sigma_S=1.0$ et $\sigma_I=0.5$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_05.png}}
+\subfigure[$\sigma_S=1.0$ et $\sigma_I=1.0$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_1.png}}\\
+\subfigure[$\sigma_S=2.0$ et $\sigma_I=0.1$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_01.png}}
+\subfigure[$\sigma_S=2.0$ et $\sigma_I=0.5$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_05.png}}
+\subfigure[$\sigma_S=2.0$ et $\sigma_I=1.0$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_1.png}}\\
+\subfigure[$\sigma_S=5.0$ et $\sigma_I=0.1$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_01.png}}
+\subfigure[$\sigma_S=5.0$ et $\sigma_I=0.5$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_05.png}}
+\subfigure[$\sigma_S=5.0$ et $\sigma_I=1.0$]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_1.png}}\\
+\caption{Réduction de bruit gaussien par filtrage bilatéral de voisinage 5$\times$5. $\sigma_S$ et $\sigma_I$ sont les écarts type des fonctions gaussiennes de pondération spatiale et d'intensité.}
+\label{fig-ny-bilat}
+\end{figure}
+
+
+Beaucoup d'autres algorithmes basés sur des moyennes locales efféctuées sur des voisinages de formes diverses, variables et/ou adaptatives afin de sélectionner le plus finement possible les pixels pris en compte dans le calcul de la valeur filtrée.
+Le principal défaut de ces techniques dites de réduction de variance est de générer des aplats dans les zones homogènes et des marches d'escalier dans les zones de transition douce (staircase effect), ces dernières pouvant être considérablement atténuées comme il a été montré dans \ref{staircase-effect}.
+
+\subsubsection{Les algorithmes par dictionnaire}
+Il s'agit ici de décrire l'image à débruiter en utilisant une base de fonctions permettant de décomposer l'image en une combinaison linéaire des éléments de cette base. Les bases les plus employées sont les ondelettes \ref{mallat2009-deladallep15, daubechie} ainsi que les fonctions sinusoïdales (DCT \ref{irfu}). Les éléments de la base peuvent être prédéterminés ou bien calculés à partir des données de l'image, par exemple en s'appuyant sur une analyse en composantes principales \ref{Aharon-2006 deladallep67}.
+
+\subsection{Les techniques avancées}
+Les techniques de réduction de bruit les plus efficaces sont aujourd'hui celles qui reposent sur les propriétés d'auto-similarité ds images, on les appelles aussi les techniques par patchs. L'idée principale est, comme pour les techniques classiques à base de de voisinage, de rechercher un ensemble de pixels pertinents et comparables afin d'en faire une moyenne. Cependant, dans le cas des techniques à patchs, la recherche de cet ensemble ne se limite pas à un voisinage du pixel central, mais fait l'hypothèse qu'il existe des zones semblables au voisinage du pixel central, réparties dans l'image et pas nécessairement immédiatement contigues.
+Le moyennage s'effectue alors sur l'ensemble des ces zones identifiées.
+L'algorithme des Non-Local Means (NL-means \ref{nl-means}) fut le premier de cette lignée à être proposé, mais bien d'autres suivirent comme le BM3D et ses variantes qui représentent actuellement l'état de l'art en terme de qualité de débruitage \ref{bm3D}.
+ Les différences entre ces algorithmes résident essentiellement dans la méthode de recherche et d'identification des patchs similaires, incluant la possiblité de forme et taille variables. Une telle recherche est d'autant plus coûteuse en temps de calcul qu'elle est effectuée sur une zone étendue autour du pixel central et cela représente le principal inconvénient de ces techniques qui peuvent présenter des temps d'exécution prohibitifs dans l'optique d'un traitement en temps réel.
+
+\section{Les implémentations GPU des algorithmes de filtrage}
+Le fabricant de processeurs graphiques Nvidia, seul type d'équipements dont nous disposons, fournit des implémentations performantes de certains prétraitements et algorithmes de filtrage.
+%TODO
+%Ajouter qq mots sur FFT, DCT utilisés dans irfu et que nous n'avons pas cherché à améliorer.
+C'est en particulier le cas de la convolution qui a fait l'objet d'une étude et d'une optimisation poussées pour déterminer la combinaison de solutions apportant la plus grande vitesse d'exécution \ref{convolution-soup-gtc09}. L'étude a testé 16 versions distinctes, chacune présentant une optimisation particulière quant-à l'organisation de la grille de calcul, aux types de transferts entre l'hôte et le GPU ainsi qu'au types de mémoire employé pour le calcul sur le GPU. Les résultats montrent que l'emploi de texture comme mémoire principale pour le stockage des images à traiter apporte un gain d'environ 50\% par rapport à l'utilisation de la mémoire globale. Par ailleurs, les transactions par paquets de 128 bits apportent également une amélioration sensible, ainsi que l'emploi de la mémoire partagée comme zone de travail pour le calcul des valeurs de sortie. Le traitement de référence effectué pour les mesures est la convolution générique (non séparable) d'une image 8 bits de 2048$\times$2048 pixels par un masque de convolution de 5$\times$5 pixels, expression que l'on raccourcira déronavant en \textit{convolution 5$\times$5}.
+Le meilleur résultat obtenu dans les conditions détaillées précédemment, sur architecture GT200 (carte GTX280) est de 1.4~ms pour le calcul, ce qui réalise un débit global de 945~MP/s lorsque l'on prend en compte les temps de transfert aller et retour des images (1.5~ms d'après nos mesures).
+Nous continuerons d'utiliser cette mesure de débit en \textit{Pixels par seconde} pour toutes les évaluations à venir ; elle permet en particulier de fournir des valeurs de performance indépendantes de la taille des images soumises au traitement.
+
+Le filtre médian n'a pas fait l'objet d'autant de publications, peut-être en raison des implémentations CPU performantes et génériques que l'on a déjà évoquées \ref{median0(1)}. Néanmoins, une bibliothèque commerciale (LibJacket, ArrayFire) en propose une implémentation GPU dont nous avons pu mesurer les performances pour un masque de 3$\times$3 et qui est également prise comme référence par Sanchez \textit{et al.} pour évaluer les performances de leur propre implémentation appelée PCMF \ref{median sanchez x2}. Sur architecture GT200 (GTX260), les performances maximales de ces deux versions sont obtenues pour un masque de 3$\times$3 pixels avec respectivement 175~MP/s pour libJacket et 60~MP/s pour PCMF.
+La figure \ref{fig-compare-jacket-pcmf}, tirée de \ref{median sanchez}, montre que le débit permis par la libJacket décroit très vite avec la taille du masque pour passer à 30~MP/s dès la taille 5$\times$5, alors que le PCMF décroit linéairement jusqu'à la taille 11$\times$11 où il permet encore de traiter quelque 40~MP/s.
+Plus récemment, Sanchez \textit{et al.} ont actualisé leurs mesures sur architecture Fermi (GPU C2075) en comparant leur PCMF à la version ré-écrite en C de libJacket, nommée ArrayFire. Les courbes sont celles de la figure \ref{fig-compare-arrayfire-pcmf}, où l'on constate que les variations selon la taille du masque demeurent comparables, avec toutefois des valeurs de débit augmentées, avec près de 185~MP/s pour ArrayFire et 82~MP/s pour PCMF. Il faut aussi noter que certains codes sont plus performants sur l'ancienne architecture GT200 que sur la plus récente Fermi ; c'est le cas pour l'implémentation du médian incluse dans la bibliothèque ArrayFire et nous reviendrons sur les raisons de cette perte de performances constatée au passage à une architecture plus récente dans le chapitre consacré à notre implémentation du filtre médian.
+
+Le filtre bilatéral a été plus abordé et un certain nombre de publications font état d'implémentations véritablement rapides. Il est néanmoins parfois difficile de les comparer sans disposer des codes sources, en raison de conditions de test très variables, en particulier en ce qui concerne le modèle de GPU et la taille du masque . Ceci étant précisé, on peut prendre comme référence initiale la version proposée par Nvidia dans le SDK CUDA et nommée ``ImageDenoising''. Elle permet d'exécuter sur GPU GTX480 un filtre bilatéral 7$\times$7 sur une image, déjà en mémoire GPU, de 1~MPixels en 0.411~ms.
