X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/e81bd9912542bc52e4b0fd1206e0b6f9b93a5fda..refs/heads/master:/THESE/Chapters/chapter2/chapter2c.tex

diff --git a/THESE/Chapters/chapter2/chapter2c.tex b/THESE/Chapters/chapter2/chapter2c.tex
index a41ecee..8d9e79d 100644
--- a/THESE/Chapters/chapter2/chapter2c.tex
+++ b/THESE/Chapters/chapter2/chapter2c.tex
@@ -1,27 +1,27 @@
 \section{Les techniques de rÃ©duction de bruit}
-La trÃ¨s grande majoritÃ© des algorithmes de rÃ©duction de bruit fait l'hypothÃ¨se que la perturbation est de type gaussien, mÃªme si le dÃ©veloppement des systÃ¨mes d'imagerie radar et mÃ©dicale a favorisÃ© l'Ã©tude des bruits multiplicatifs du type \textit{speckle} ou \textit{Poisson}.
+La trÃ¨s grande majoritÃ© des algorithmes de rÃ©duction de bruit fait l'hypothÃ¨se que la perturbation est de type additif gaussien, mÃªme si le dÃ©veloppement des systÃ¨mes d'imagerie radar et mÃ©dicale a favorisÃ© l'Ã©tude des bruits multiplicatifs du type \textit{speckle} ou \textit{Poisson}.
 Un trÃ¨s grand nombre de travaux proposant des mÃ©thodes de rÃ©duction de ces bruits ont Ã©tÃ© menÃ©s, ainsi que beaucoup d'Ã©tats de l'art et d'Ã©tudes comparatives de ces diverses techniques. Aussi nous focaliserons nous 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 \cite{coil}, 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. 
-L'indice de qualitÃ© le plus employÃ© pour mesurer la similaritÃ© entre deux images est le PSNR (pour Peak Signal to Noise Ratio). Il est exprimÃ© en dÃ©cibels (dB) et se calcule en appliquant la formule  
+L'indice de qualitÃ© le plus employÃ© pour mesurer la similaritÃ© entre deux images est le PSNR (pour Peak Signal to Noise Ratio). Il est exprimÃ© en dÃ©cibels (dB) et est dÃ©fini par
 \[ PSNR = 10log_{10}\left(\frac{D^2}{\displaystyle\frac{1}{N}\sum_{k < N}\left(v_k - u_k\right)^2}\right)\]
 si l'on cherche Ã  Ã©valuer le PSNR de l'image observÃ©e $\bar{v}$ par rapport Ã  l'image de rÃ©fÃ©rence $\bar{u}$. Le nombre $D$ reprÃ©sente la dynamique maximale des images, e.g 255 pour des images en niveaux de gris codÃ©s sur 8 bits. 
 
-Cet indicateur seul est cependant insuffisant pour caractÃ©riser convenablement la qualitÃ© de dÃ©bruitage d'un filtre, mesure hautement subjective. Un indice global de similaritÃ© structurelle (MSSIM pour Mean Structural Similarity Index) a Ã©tÃ© proposÃ© par Wang \textit{et al.} \cite{Wang04imagequality} et permet, en conjonction avec le PSNR, de garantir une mesure de qualitÃ© plus en rapport avec la perception visuelle. Le MSSIM prend ses valeurs dans l'intervalle $[0;1]$ avec une similaritÃ© d'autant plus grande que la valeur est proche de 1.  
+Cet indicateur seul est cependant insuffisant pour caractÃ©riser convenablement la qualitÃ© de dÃ©bruitage d'un filtre, mesure hautement subjective. Un indice global de similaritÃ© structurelle (MSSIM pour Mean Structural Similarity Index) a Ã©tÃ© proposÃ© par Wang \textit{et al.} \cite{Wang04imagequality} et permet, en conjonction avec le PSNR, de fournir une mesure de qualitÃ© plus en rapport avec la perception visuelle. Le MSSIM prend ses valeurs dans l'intervalle $[0;1]$ avec une similaritÃ© d'autant plus grande que la valeur est proche de 1.  
 
 \begin{figure}
   \centering
   \subfigure[Sans bruit]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/ny256.png}}
   \subfigure[Bruit gaussien $\sigma=25$, PSNR=22.3~dB MSSIM=0.16]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/ny256_gauss25.png}}
   \subfigure[Bruit impulsionnel 25\%, PSNR=9.48~dB MSSIM=0.04]{\label{ny-sap}\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\%.}
+  \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}\label{sec-op-base}
 \subsubsection{Le filtre de convolution}
 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
+Si la fonction dÃ©finissant le masque de convolution est notÃ©e $h$, l'expression gÃ©nÃ©rale de la valeur de sortie estimÃ©e au 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}
@@ -30,7 +30,7 @@ Dans les applications les plus courantes, $h$ est Ã  support bornÃ© et de forme
  La figure \ref{fig-ny-convo} prÃ©sente les rÃ©sultats de la convolution par deux masques dÃ©bruiteurs \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 l'effet d'un masque gaussien $h_{g3}$. 
 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_{5}=\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_{g3}= \begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}\]  
+\[h_3=\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}, h_{5}=\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_{g3}= \frac{1}{16}\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}\]  
 
 \begin{figure}
   \centering
@@ -45,9 +45,10 @@ Lorsque la matrice $h$ dÃ©finissant le masque peut s'Ã©crire comme le produit de
 
 
 \subsubsection{Le filtre mÃ©dian}
-Le filtrage mÃ©dian \cite{tukey77} 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 du 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 \og constant \fg{} dÃ©crit par Perreault et Hebert \cite{4287006}. Il est Ã  noter que le filtrage mÃ©dian est souvent appliquÃ© en plusieurs passes de voisinage restreint.
+Le filtrage mÃ©dian \cite{tukey77} est Ã©galement une opÃ©ration trÃ¨s employÃ©e en prÃ©-traitement pour sa simplicitÃ© coneptuelle et ses propriÃ©tÃ©s de prÃ©servation des contours alliÃ©es Ã  une capacitÃ© de rÃ©duction du 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 dans un voisinage donnÃ©. 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. 
+Le filtre mÃ©dian est aussi un estimateur robuste de la valeur moyenne permettant de bien s'affranchir des perturbations prÃ©sentant, dans le voisinage,  des valeurs trÃ¨s Ã©loignÃ©es de la moyenne. Par consÃ©quent, il trouve aussi son application dans la rÃ©duction du bruit impulsionnel.
+Toutefois, la non-rÃ©gularitÃ© et l'importance du temps de calcul de cette technique 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 \og constant \fg{} dÃ©crit par Perreault et Hebert \cite{4287006}. Il est Ã  noter que le filtrage mÃ©dian est souvent appliquÃ© en plusieurs passes de voisinage restreint, car cela permet d'obtenir des niveaux de dÃ©bruitage semblables Ã  ceux permis par des voisinages plus grands, mais avec des temps de calcul rÃ©duits.
 La figure \ref{fig-ny-median} montre la rÃ©duction de bruit impulsionnel obtenu sur l'image  \ref{ny-sap} grÃ¢ce au filtre mÃ©dian, dans trois conditions distinctes : mÃ©dian 3$\times$3 en une ou deux passes, puis mÃ©dian 5$\times$5.
 \begin{figure}
   \centering
@@ -60,7 +61,7 @@ La figure \ref{fig-ny-median} montre la rÃ©duction de bruit impulsionnel obtenu
 
 
 \subsubsection{Le filtre bilatÃ©ral}
-Le filtre bilatÃ©ral \cite{710815} 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). 
+Le filtre bilatÃ©ral \cite{710815} est une composition d'opÃ©rations que l'on  peut voir comme un  filtre de convolution dont les coefficients dÃ©pendent de la position du pixel considÃ©rÃ© par rapport au pixel central, mais dÃ©pendent Ã©galement de la diffÃ©rence entre leurs deux niveaux de gris (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$.
@@ -88,7 +89,9 @@ L'un de ces algorithmes cherche dans l'image bruitÃ©e, une portion de la ligne d
   
 
 \subsubsection{Les algorithmes de filtrage par dictionnaire}
-Ces algorithmes font l'hypothÃ¨se qu'il est possible 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 \cite{Mallat:2008:WTS:1525499, Daubechies:1992:TLW:130655} ainsi que les fonctions sinusoÃ¯dales (DCT \cite{1093941,strang1999discrete}). 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 ou aprÃ¨s apprentissage \cite{elad2006image}. Le principe du dÃ©bruitage est de considÃ©rer que le bruit est dÃ©corellÃ© des fonctions de la base et donc reprÃ©sentÃ© par les petits coefficients de la dÃ©composition, que l'on peut annuler. Diverses politiques de seuillage peuvent alors Ãªtre appliquÃ©es selon le type d'image et le modÃ¨le de bruit ayant chacune ses propres avantages et inconvÃ©nients. L'intÃ©rÃªt principal de ces mÃ©thodes est de bien restituer les transitions rapides (grande Ã©nergie), mais elles gÃ©nÃ¨rent en revanche des artefacts dus aux possibles grands coefficients de bruit. 
+Ces algorithmes font l'hypothÃ¨se qu'il est possible 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 \cite{Mallat:2008:WTS:1525499, Daubechies:1992:TLW:130655} ainsi que les fonctions sinusoÃ¯dales (DCT \cite{1093941,strang1999discrete}). 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 ou aprÃ¨s apprentissage \cite{elad2006image}. On considÃ¨re que le bruit, blanc, est dÃ©corellÃ© des fonctions de la base, son Ã©nergie est ainsi rÃ©partie uniformÃ©ment sur tout l'espace de dÃ©composition, contrairement au signal informatif. Le principe du filtrage est alors de supprimer les composantes Ã  faible Ã©nergie, reprÃ©sentÃ©es par les petits coefficients de la dÃ©composition.
+
+ Diverses politiques de seuillage peuvent alors Ãªtre appliquÃ©es selon le type d'image et le modÃ¨le de bruit ayant chacune ses propres avantages et inconvÃ©nients. L'intÃ©rÃªt principal de ces mÃ©thodes est de bien restituer les transitions rapides (grande Ã©nergie), mais elles peuvent en revanche gÃ©nÃ©rer des artefacts, par exemple lorsque la PDF du bruit partage avec le signal une composante d'Ã©nergie Ã©levÃ©e. 
 La figure \ref{fig-ny-dwt} illustre cela en montrant le rÃ©sultat du dÃ©bruitage obtenu par dÃ©composition en ondelettes et seuillage  \og dur \fg{} : lorsque la valeur du seuil croÃ®t, des aplats apparaissent et sont visuellement gÃ©nants bien que les valeurs des indices de qualitÃ© n'aient pas diminuÃ© significativement.
 Certains algorithmes rÃ©cents, en particulier ceux utilisant une base d'ondelettes adaptative, comme dans \cite{elad2006image} sont proches, en terme de qualitÃ©, de l'Ã©tat de l'art du domaine, avec souvent un avantage liÃ© Ã  des vitesses d'exÃ©cution assez rapides.
 
@@ -135,7 +138,7 @@ L'opÃ©ration de convolution a fait l'objet d'une Ã©tude et d'une optimisation po
 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 dorÃ©navant 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 reprÃ©sente 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.
+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Ã©pendamment de la taille des images soumises au traitement\footnote{Dans la pratique, le dÃ©bit dÃ©pend peu de la taille de l'image, pour les images suffisamment grandes que nous traitons. Le dÃ©bit croit lÃ©gÃ¨rement avec la taille de l'image en raison des transferts plus efficaces.}.
 
 \subsection{Le filtre mÃ©dian}\label{sec-median}
 On connaÃ®t peu de versions GPU du filtre mÃ©dian, peut-Ãªtre en raison des implÃ©mentations CPU performantes et gÃ©nÃ©riques que l'on a dÃ©jÃ  Ã©voquÃ©es (voir par exemple \cite{4287006}) et dont le portage sur GPU ne laisse pas entrevoir de potentiel, ou bien reste Ã  inventer. NÃ©anmoins, une bibliothÃ¨que commerciale (LibJacket et 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 \cite{6288187}. 
@@ -175,12 +178,12 @@ Le principe est de prÃ©-charger les valeurs utiles au bloc de threads dans la m
 
 \begin{figure}
   \centering
-  \includegraphics[width=10cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png}
+  \includegraphics[width=12cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png}
 \caption{Illustration du prÃ©-chargement en mÃ©moire partagÃ©e mis en \oe uvre dans \cite{zheng2011performance} pour l'implÃ©mentation, entre autres, du filtre bilatÃ©ral. a) en vert le bloc de threads associÃ© aux pixels centraux. b-e) les blocs de pixels successivement prÃ©-chargÃ©s en mÃ©moire partagÃ©e. f) la configuration finale de la ROI en mÃ©moire partagÃ©e.}
 \label{fig-prefetch-zheng}
 \end{figure}
 
-Cette recette est ensuite appliquÃ©e dans l'implÃ©mentation d'un filtre bilatÃ©ral et d'un filtre Ã  moyennes non locales (NL-means). Concernant le filtre bilatÃ©ral, les auteurs prÃ©-calculent aussi les coefficients de la pondÃ©ration spatiale, alors que ceux de la pondÃ©ration d'intensitÃ© restent calculÃ©s Ã  la volÃ©e.
+Cette mÃ©thode empirique de prÃ©-chargement est ensuite appliquÃ©e dans l'implÃ©mentation d'un filtre bilatÃ©ral et d'un filtre Ã  moyennes non locales (NL-means). Concernant le filtre bilatÃ©ral, les auteurs prÃ©-calculent aussi les coefficients de la pondÃ©ration spatiale, alors que ceux de la pondÃ©ration d'intensitÃ© restent calculÃ©s Ã  la volÃ©e.
 Ces deux optimisations permettent un gain de 20\% sur le temps de calcul du filtre bilatÃ©ral pour arriver Ã  0.326~ms dans les mÃªmes conditions que ci-dessus (bilatÃ©ral 7$\times$7 sur image 1~MP). Toutefois, le dÃ©bit global ne progresse pas (132~MP/s) en raison de la prÃ©pondÃ©rance des temps de transfert annoncÃ©s Ã  7,5~ms pour l'image de 1~MP, alors qu'ils n'Ã©taient que de 7,1~ms dans les conditions dÃ©crites par Nvidia.
 
 Ce travail d'optimisation ne perd toutefois pas son intÃ©rÃªt dans la mesure oÃ¹, si le filtre fait partie d'une chaÃ®ne de traitement entiÃ¨rement exÃ©cutÃ©e par le GPU, le transfert des donnÃ©es n'a besoin d'Ãªtre effectuÃ© qu'une seule fois en tout dÃ©but et en toute fin de traitement.  
