X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/337bc2017ae0e8ef623077988ea7998f48b3c442..82c062292d36ed7f5cb8e3e913382ca8c47eb379:/THESE/Chapters/chapter2/chapter2.tex

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index 53201d6..7988109 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -2,23 +2,24 @@ L'Ã©tendue des techniques applicables aux images numÃ©riques est aujourd'hui si
 L'intuition nous incite donc Ã  chercher des mÃ©thodes efficaces de prÃ©traitement pour rÃ©duire la puissance du bruit afin de permettre aux traitements de plus haut niveau comme la segmentation, d'opÃ©rer ensuite dans de meilleures conditions.           
 
 Toutefois, il faut Ã©galement considÃ©rer que les opÃ©rations prÃ©alables de rÃ©duction de bruit apportent des modifications statistiques aux images et influent donc potentiellement sur les caractÃ©ristiques que l'on cherche Ã  mettre en Ã©vidence grÃ¢ce au traitement principal. En ce sens, il peut-Ãªtre prÃ©fÃ©rable de chercher Ã  employer des algorithmes de haut niveau travaillant directement sur les images bruitÃ©es pour minimiser les effets des altÃ©rations apportÃ©es par les filtres dÃ©bruiteurs et conserver toute l'information contenue dans les images perturbÃ©es.
-
- Les images auxquelles nous nous intÃ©ressons sont gÃ©nÃ©ralement les images numÃ©riques allant des images naturelles telles que dÃ©finies par Caselles \cite{} aux images d'amplitude isues de l'imagerie radar Ã  ouverture synthÃ©tique (ROS ou en anglais SAR) \cite{}, de l'imagerie mÃ©dicale Ã  ultrasons (echographie) ou encore biologique dans le cas de la microscopie Ã©lectronique. 
+%TODO
+% dire aussi que le prÃ©traitement, Ã§a prend du temps. C'est Ã©vident mais c'est mieux en le disant
+ Les images auxquelles nous nous intÃ©ressons sont gÃ©nÃ©ralement les images numÃ©riques allant des images naturelles telles que dÃ©finies par Caselles \cite{Caselles99topographicmaps} aux images d'amplitude isues de l'imagerie radar Ã  ouverture synthÃ©tique (ROS ou en anglais SAR) \cite{cutrona1990synthetic}, de l'imagerie mÃ©dicale Ã  ultrasons (echographie) ou encore biologique dans le cas de la microscopie Ã©lectronique. 
 Ces dispositifs d'acquisition sont naturellement, et par essence, gÃ©nÃ©rateurs de bruits divers, inhÃ©rents aux thechnologies mises en \oe uvre au sein de ces systÃ¨mes et qui viennent dÃ©grader l'image idÃ©ale de la scÃ¨ne que l'on cherche Ã  reprÃ©senter ou analyser. On sait aujourd'hui caractÃ©riser de maniÃ¨re assez prÃ©cise ces bruits et la section \ref{sec_bruits} en dÃ©taille les  origines physiques ainsi que  les propriÃ©tÃ©s statistiques qui en dÃ©coulent.
 On peut dores et dÃ©jÃ  avancer que la connaissance de l'origine d'une image et donc des propriÃ©tÃ©s des bruits associÃ©s qui en corrompent les informations, est un atout permettant de concevoir des techniques de filtrage adaptÃ©es Ã  chaque situation. Toutefois, la recherche d'un filtre universel, bien qu'encore illusoire, n'est pas abandonnÃ©e, tant les besoins sont nombreux, divers et souvent complexes.    
        
 \section{ModÃ¨le d'image bruitÃ©e}
-On considÃ¨re qu'une image observÃ©e est un ensemble de $N$ observations sur un domaine $\Omega$ Ã  deux dimensions ($\Omega \subset \mathbb{Z}^2$). Ã chaque Ã©lÃ©ment de $\Omega$, aussi appelÃ© \textit{pixel}, est associÃ© un indice unique $k \in [\![1;N]\!]$, une position $x_k=(i,j)_k \in\Omega$ et une valeur observÃ©e $v_k=v(i,j)_k$.
+On considÃ¨re qu'une image observÃ©e, de largeur $L$ pixels et de hauteur $H$ pixels, est un ensemble de $N=HL$ observations sur un domaine $\Omega$ Ã  deux dimensions ($\Omega \subset \mathbb{Z}^2$). Ã chaque Ã©lÃ©ment de $\Omega$, aussi appelÃ© \textit{pixel}, est associÃ© un indice unique $k \in [\![1;N]\!]$, une position $x_k=(i,j)_k \in\Omega$ et une valeur observÃ©e $v_k=v(i,j)_k$.
 La valeur observÃ©e peut, selon les cas, Ãªtre de dimension $1$ pour les images reprÃ©sentÃ©es en niveaux de gris ou de dimension 3 pour les images couleur reprÃ©sentÃ©es au format RVB. Les dimensions supÃ©rieures, pour la reprÃ©sentation des images hyperspectrales n'est pas abordÃ©.
 L'image observÃ©e peut ainsi Ãªtre considÃ©rÃ©e comme un vecteur Ã  $N$ Ã©lÃ©ments $\bar{v}= (v_k)_{k\in [\![1;N]\!]}$.
-Les divers traitements appliquÃ©s aux images observÃ©es ont souvent pour but d'accÃ©der aux informations contenues dans une image sous-jacente, dÃ©barrassÃ©e de toute perturbation, dont nous faisons l'hypothÃ¨se qu'elle partage le mÃªme support $\Omega$ et que nous notons $\bar{u}$.
+Les divers traitements appliquÃ©s aux images observÃ©es ont souvent pour but d'accÃ©der aux informations contenues dans une image sous-jacente, dÃ©barrassÃ©e de toute perturbation, dont nous faisons l'hypothÃ¨se qu'elle partage le mÃªme support $\Omega$ et que nous notons $\bar{u}$. L'estimation de $\bar{u}$ rÃ©alisÃ©e par ces traitements est notÃ©e $\widehat{\bar{u}} = (\widehat{u}_k)_{k\in [\![1;N]\!]}$.
 Le lien entre $\bar{u}$ et $\bar{v}$ peut Ãªtre exprimÃ© gÃ©nÃ©ralement par la relation $\bar{v}=\bar{u}+\sigma\epsilon$, oÃ¹ $\epsilon \in \mathbb{R}^N$ reprÃ©sente le modÃ¨le de perturbation appliquÃ©e Ã  $\bar{u}$ et $\sigma$ reprÃ©sente la puissance de cette perturbation qui a menÃ© Ã  l'observation de $\bar{v}$.
 Dans le cas gÃ©nÃ©ral, $\epsilon$ dÃ©pend de $\bar{u}$ et est caractÃ©risÃ© par la densitÃ© de probabilitÃ© (PDF pour probability density function) $p(v|u)$.
 
-\section{ModÃ¨les de bruit}
+\section{ModÃ¨les de bruit}\label{sec_bruits}
 \subsection{Le bruit gaussien}
 Le bruit gaussien est historiquement le plus Ã©tudiÃ© et celui auquel sont dÃ©diÃ©es le plus de techniques de dÃ©bruitage.
-La gÃ©nÃ©ration des images numÃ©riques au travers les capteurs CMOS et CCD \ref{} est le siÃ¨ge de nombreuses perturbations dues Ã  la technologie de fabrication et Ã  la nature du rayonnement dont ils mesurent l'intensitÃ© en diffÃ©rents zones de leur surface, appelÃ©es \textit{photosites}.
+La gÃ©nÃ©ration des images numÃ©riques au travers les capteurs CMOS et CCD  est le siÃ¨ge de nombreuses perturbations dues Ã  la technologie de fabrication et Ã  la nature du rayonnement dont ils mesurent l'intensitÃ© en diffÃ©rents zones de leur surface, appelÃ©es \textit{photosites} \cite{mancuso2001introduction,theuwissen2001ccd}.
 On distingue en particulier les bruits suivants selon leur origine physique :
 \begin{itemize}
 \item la non uniformitÃ© de rÃ©ponse des photosites.
@@ -27,7 +28,7 @@ On distingue en particulier les bruits suivants selon leur origine physique :
 \item le bruit de lecture
 \item le bruit de non uniformitÃ© d'amplification des gains des photosites.
 \end{itemize}
-Des descriptions dÃ©taillÃ©es des mÃ©canismes concourant Ã  la gÃ©nÃ©ration de ces bruits sont fournies dans \ref{phelippeau p80}  
+On trouve des descriptions dÃ©taillÃ©es des mÃ©canismes concourant Ã  la gÃ©nÃ©ration de ces bruits, entre autres dans \cite{healey1994radiometric} et \cite{kodakccd}.  
 Dans un certain intervalle usuel d'intensitÃ© lumineuse, il est toutefois admis que l'ensemble des ces perturbations peut Ãªtre reprÃ©sentÃ© par un seul bruit blanc gaussien, de type \textit{additif} (AWGN), dont la densitÃ© de probabilitÃ© suit une loi normale de moyenne nulle et de variance $\sigma^2$.
 On a alors l'expression suivante, oÃ¹ $\sigma >0$ 
 \[p(v|u)=\frac{1}{\sqrt{2}\pi\sigma}\mathrm{e}^{-\frac{(v-u)^2}{2\sigma^2}}\]
@@ -60,13 +61,154 @@ Le bruit de grenaille est de type multiplicatif et suit une loi de Poisson. La P
 \[ p(v \mid u)=\mathrm{e}\frac{u^v}{v!}\]
 
 \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 poussÃ© les chercheurs vers 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, que nous n'avons pas la prÃ©tention d'Ã©galer.
+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}.
+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, que nous n'avons pas l'ambition d'Ã©galer.
+
+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 \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  
+\[ 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.  
+
+\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]{\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 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_{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}1&2&1\\2&4&2\\1&2&1\end{bmatrix}\]  
+
+\begin{figure}
+  \centering
+  \subfigure[Moyenneur 3$\times$3, PSNR=27.6dB MSSIM=0.34]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy3.png}}\quad  
+  \subfigure[Moyenneur 5$\times$5, PSNR=27.7dB MSSIM=0.38]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy5.png}}\quad
+  \subfigure[Filtre gaussien 3$\times$3, PSNR=27.4dB MSSIM=0.33]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_g3.png}}  
+\caption{Filtrage par convolution.}
+\label{fig-ny-convo}
+\end{figure}
+
+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 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 par Perreault et Hebert \cite{4287006}. 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, PSNR=26.4~dB MSSIM=0.90]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3.png}}  
+  \subfigure[MÃ©dian 3$\times$3 deux passes, PSNR=34.4~dB MSSIM=0.98]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3x2.png}}
+  \subfigure[MÃ©dian 5$\times$5 une passe, PSNR=35.1~dB MSSIM=0.98]{\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}
 
-Les techniques et implÃ©mentations que nous aborderons dans le chapitre suivant sont celles qui ont un lien direct avec les travaux que nous avons menÃ©s. Nous 
-prÃ©senterons donc les principales classes d'algorithmes  de rÃ©duction de bruit et les implÃ©mentations GPU qui leur ont Ã©tÃ© consacrÃ©es.
+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). 
+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 \cite{1521458}, 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 \cite{4587843}.
+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$, PSNR=25.6~dB MSSIM=0.25]{\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$, PSNR=28.0~dB MSSIM=0.36]{\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$, PSNR=27.9~dB MSSIM=0.36]{\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$, PSNR=26.7~dB MSSIM=0.29]{\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$, PSNR=27.9~dB MSSIM=0.39]{\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$, PSNR=27.5~dB MSSIM=0.38]{\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$, PSNR=26.8~dB MSSIM=0.29]{\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$, PSNR=26.8~dB MSSIM=0.37]{\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$, PSNR=25.9~dB MSSIM=0.36]{\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 \cite{BuadesCM06}.
+
+\subsubsection{Les algorithmes 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. 
+La figure \ref{fig-ny-dwt} illustre cela en montrant le rÃ©sultat du dÃ©bruitage obtenu par dÃ©composition en ondelettes et seuillage ``dur''.
+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.
+
+\begin{figure}
+  \centering
+  \subfigure[$T=20$, PSNR=26.9~dB MSSIM=0.30]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt20.png}}
+  \subfigure[$T=35$, PSNR=27.6~dB MSSIM=0.36]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt.png}}
+  \subfigure[$T=70$, PSNR=26.7~dB MSSIM=0.37]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt70.png}}
+\caption{Filtrage par dÃ©composition en ondelettes et seuillage dur des coefficients infÃ©rieurs au seuil $T$.}
+\label{fig-ny-dwt}
+\end{figure}
 
 
+\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 moyennes non locales (NL-means, \cite{1467423}) fut parmi les premiers de cette lignÃ©e Ã  Ãªtre proposÃ© et bien qu'ayant reprÃ©sentÃ© un progrÃ¨s notable dans la qualitÃ© de dÃ©bruitage, fut rapidement suivi, en particulier par le BM3D et ses variantes qui reprÃ©sentent actuellement l'Ã©tat de l'art en terme de qualitÃ© de dÃ©bruitage \cite{Dabov06imagedenoising,Dabov09bm3dimage}.  
+ 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 patch 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.
+La figure \ref{fig-ny-nlm} montre des rÃ©sultats de dÃ©bruitage obtenus par la mÃ©thode des NL-means avec plusieurs combinaisons des paramÃ¨tres de similaritÃ© des patchs et de non localitÃ© du voisinage, notÃ©s $f$ et $t$. La figure \ref{fig-ny-bm3d} montre quant-Ã  elle le rÃ©sultat du dÃ©bruitage par BM3D. Les points forts de ces deux techniques sont, comme on le voit, la qualitÃ© du dÃ©bruitage avec pour l'implÃ©mentation BM3D l'avantage de ne nÃ©cessiter aucun rÃ©glage de paramÃ¨tres.
+\begin{figure}
+  \centering
+  \subfigure[$f=2$ et $t=2$, PSNR=28.5~dB MSSIM=0.37]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_2_2_25.png}}\quad
+  \subfigure[$f=2$ et $t=5$, PSNR=28.6~dB MSSIM=0.38]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_2_5_25.png}}\quad
+\subfigure[$f=5$ et $t=2$, PSNR=29.0~dB MSSIM=0.39]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_5_2_25.png}}\quad
+\subfigure[$f=5$ et $t=5$, PSNR=29.0~dB MSSIM=0.40]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_5_5_25.png}}
+\caption{Filtrage par NL-means pour diffÃ©rentes combinaisons des paramÃ¨tres de similaritÃ© $f$ et de non localitÃ© $t$.}
+\label{fig-ny-nlm}
+\end{figure}
+\begin{figure}
+  \centering
+  \includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/bm3D/ny256_gauss25_bm3D.png}
+\caption{Filtrage par BM3D, PSNR=29.3~dB MSSIM=0.41}
+\label{fig-ny-bm3d}
+\end{figure}
+
+\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. 
+C'est le cas des tranformÃ©es de fourrier (FFT, DCT), qui sont par exemple utilisÃ©es dans l'implÃ©mentation d'un algorithme d'\textit{inpainting} \cite{cmla2009Kes}. 
+C'est aussi vrai pour l'opÃ©ration de 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 \cite{convolutionsoup}. 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.
+
+On connait 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}. 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. 
+Une prÃ©cÃ©dente implÃ©mentation avait Ã©tÃ© rÃ©alisÃ©e, basÃ©e sur l'algorithme BVM dÃ©crit dans \cite{5402362}. Elle prouve son efficacitÃ© dans l'Ã©limination des artefacts gÃ©nÃ©rÃ©s par les dispositifs d'imagerie mÃ©dicale magnÃ©tique en 3D \cite{chen09}, mais ne permet pas d'exploiter vÃ©ritablement le parallÃ©lisme des GPU en filtrage d'image en 2D.
+La figure \ref{fig-compare-jacket-pcmf}, tirÃ©e de \cite{5402362}, compare ces trois implÃ©mentations et 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. Ceci s'explique simplement par le fait que libJacket utilise un tri simple pour la sÃ©lection de la valeur mÃ©diane alors que le PCMF exploite les propriÃ©tÃ©s des histogrammes cumulÃ©s et n'est ainsi que trÃ¨s peu dÃ©pendant de la taille du masque. 
+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. 
+ParallÃ¨lement, on trouve aussi des implÃ©mentations de filtre mÃ©dian dans des traitements plus complexes comme dans \cite{aldinucci2012parallel} oÃ¹ les auteurs dÃ©crivent la plus rÃ©cente Ã©volution de leur technique itÃ©rative de rÃ©duction de bruit impulsionnel, sans qu'il soit possible d'Ã©valuer le dÃ©bit du mÃ©dian seul. 
+Il faut noter enfin que certains codes sont plus performants sur l'ancienne architecture GT200/Tesla 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 rapides. 
+Une implÃ©mentation Ã  temps constant en est proposÃ©e par Yang \textit{et al.} \cite{5206542} et s'exÃ©cute entre 3.7~ms et 15~ms pour une image de 1~MP. Cela ne constitue pas une rÃ©fÃ©rence de vitesse pour les masques de petite taille, mais devient compÃ©titif pour des masque de grande taille (plus de 400 pixels dans le voisinage).
+Une autre plus classique, employÃ©e dans la gÃ©nÃ©ration des images mÃ©dicales tomographiques, annonce 16~ms pour un masque de 11$\times$11 sur une image de 0.25~MP.
+Il demeure souvent  difficile de comparer les implÃ©mentations 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 premiÃ¨re rÃ©fÃ©rence 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, pour un dÃ©bit global de 133~MP/s.
+Dans \cite{zheng2011performance}, les auteurs prÃ©sentent un cadre gÃ©nÃ©ral pour optimiser l'accÃ¨s aux donnÃ©es par les diffÃ©rents kernels en utilisant la mÃ©moire partagÃ©e par les threads d'un mÃªme bloc. 
+Le principe est de prÃ©-charger les valeurs utiles au bloc de threads dans la mÃ©moire partagÃ©e, cela comprend les valeurs (niveaux de gris) des pixels associÃ©s aux threads ainsi que le halo correspondant aux voisinages des pixels de la bande pÃ©riphÃ©rique. On appelle communÃ©ment cet ensemble la \textit{region of interest} ou ROI. 
+Ils appliquent ensuite leur recette Ã  l'implÃ©mentation d'un filtre bilatÃ©ral et d'un filtre Ã  moyennes non locales (NL-means). Concernant le filtre bilatÃ©ral, ils prÃ©-calculent aussi les coefficients de la pondÃ©ration spatiale, alors que ceux de la pondÃ©ration d'intensitÃ© resent 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. Toutefois, le dÃ©bit global ne gagne que trÃ¨s peu (132~MP/s) en raison de la prÃ©pondÃ©rance des temps de tranfert annoncÃ©s Ã  7.5~ms pour l'image de 1~MP.
+Ce travail d'optimisation ne perd toutefois pas son intÃ©rÃªt, en ce sens 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.  
+Enfin, l'implÃ©mentation qui semble Ã  ce jour la plus performante s'attache Ã  rÃ©duire les redondances de calculs et parvient Ã  filtrer une image de 9~MP avec un masque de 21$\times$21 en seulement 200~ms, soir un dÃ©bit de 47~MP/s hors transfers.
+  
+Intuitivement, les algorithmes Ã  base de patches paraissent moins adaptÃ©s au parallÃ¨lisme des GPU, du fait de la nÃ©cessitÃ© d'accÃ©der Ã  un voisinage Ã©tendu autour de chaque pixel. On recense malgrÃ© tout quelques implÃ©mentations dont celle prÃ©sente dans le SDK CUDA qui fait cependant l'hypothÃ¨se que les coefficients de pondÃ©ration spatiale sont localement constants.   
+Dans \cite{PALHANOXAVIERDEFONTES}, le modÃ¨le de bruit employÃ© vise une adaptation aux images Ã©chographiques prÃ©sentant du bruit proche du speckle. Dans cette implÃ©mentation, aucune approximation des coefficients n'est faite, mais la taille maximale du patch est limitÃ©e par la quantitÃ© de mÃ©moire partagÃ©e disponible pour chaque bloc de threads. 
+Une version plus rÃ©cente implÃ©mente exactement l'algorithme original \cite{nlmeansgpubelge} en proposant des optimisations algorithmiques exploitant la symÃ©trie des coefficients spatiaux ainsi que l'interprÃ©tation du calcul de la similaritÃ© comme une convolution sÃ©parable, opÃ©ration aisÃ©ment parallÃ©lisable sur GPU, comme nous le dÃ©taillerons plus loin. Les auteurs parviennent ainsi Ã  filtrer des sÃ©quences vidÃ©o couleur de dimension 720$\times$480 Ã  plus de 30~fps en amÃ©liorant le PSNR de 16~dB (la sÃ©quence bruitÃ©e prÃ©sentant un PSNR de 20~dB). 
+
 \section{Les techniques de segmentation}
 La segmentation reprÃ©sente Ã©galement un enjeu important dans le domaine du traitement d'image et Ã  ce titre a fait l'objet d'abondants travaux et publications touchant les nombreux cas d'analyse dans lesquels une segmentation est utilisÃ©e. On peut citer la reconnaissance de formes, la dÃ©tections et/ou la poursuite de cibles, la cartographie, le diagnostique mÃ©dical, l'interaction Homme-machine, la discrimination d'arriÃ¨re plan, etc.
 
@@ -77,31 +219,31 @@ Dans cette dÃ©finition, le caractÃ¨re \textit{homogÃ¨ne} s'entend au sens d'un c
 Devant la diversitÃ© des cas Ã  traiter et des objectifs Ã  atteindre, on sait aujourd'hui qu'Ã  l'instar du filtre unique, la mÃ©thode universelle de segmentation n'existe pas et qu'une bonne segmentation est celle qui conduit effectivement Ã  l'extraction des structures pertinentes d'une image selon l'interprÃ©tation qui doit en Ãªtre faite.
 
 Les Ã©lÃ©ments constitutifs de la segmentation sont soit des rÃ©gions, soit des contours. Les deux notions sont complÃ©mentaires Ã©tant donnÃ© que les contours dÃ©limitent des rÃ©gions, mais les techniques de calcul basÃ©s sur l'un ou l'autre de ces Ã©lÃ©ments relÃ¨vent d'abords diffÃ©rents.
-Les algorithmes de segmentation orientÃ©s rÃ©gions s'appuient pour beaucoup sur des techniques de regroupement, ou \textit{clustering}, pour l'identification et le peuplement des rÃ©gions. Ce lien trouve son origine dans la psychologie du \textit{gestalt} \ref{biblio_web} oÃ¹ l'on considÃ¨re que la perception conceptuelle s'Ã©labore au travers de regroupements visuel d'Ã©lÃ©ments.
+Les algorithmes de segmentation orientÃ©s rÃ©gions s'appuient pour beaucoup sur des techniques de regroupement, ou \textit{clustering}, pour l'identification et le peuplement des rÃ©gions. Ce lien trouve son origine dans la psychologie du \textit{gestalt} \cite{humphrey1924psychology} oÃ¹ l'on considÃ¨re que la perception conceptuelle s'Ã©labore au travers de regroupements visuel d'Ã©lÃ©ments.
 La plupart des approches proposÃ©es jusqu'Ã  trÃ¨s rÃ©cemment consistent Ã  minimiser une fonction d'Ã©nergie qui n'a pas de solution formelle et que l'on rÃ©sout donc Ã  l'aide de techniques numÃ©riques, souvent itÃ©ratives.   
 
 \subsection{Analyse d'histogramme}
 Les techniques les plus simples Ã  mettre en \oe uvre en segmentation sont les techniques de seuillage, basÃ©es sur une analyse de l'histogramme des niveaux de gris (ou de couleurs) et cherchant Ã  en distinguer les diffÃ©rentes classes comme autant d'occurrences reprÃ©sentant des \textit{rÃ©gions} homogÃ¨nes.
-DiffÃ©rents critÃ¨res peuvent Ãªtre appliquÃ©s pour cette analyse, visant par exemple Ã  maximiser la variance \ref{otsu79} ou encore Ã  maximiser le contraste pour dÃ©terminer les valeurs pertinentes des seuils. 
+DiffÃ©rents critÃ¨res peuvent Ãªtre appliquÃ©s pour cette analyse, visant par exemple Ã  maximiser la variance \cite{otsu79} ou encore Ã  maximiser le contraste pour dÃ©terminer les valeurs pertinentes des seuils. 
 MalgrÃ© la multitude de variantes proposÃ©es, ces mÃ©thodes demeurent toutefois peu robustes et prÃ©sentent l'inconvÃ©nient majeur de ne pas garantir la connexitÃ© des rÃ©gions dÃ©terminÃ©es. On les rÃ©serve Ã  des applications trÃ¨s spÃ©cifiques oÃ¹, par exemple, on dispose d'une image de rÃ©fÃ©rence dont l'histogramme peut Ãªtre comparÃ© Ã  celui des images Ã  traiter. C'est le cas de certaines application de contrÃ´le industriel oÃ¹ la simplicitÃ© algorithmique permet de surcroÃ®t des implÃ©mentations trÃ¨s rapides, voire cÃ¢blÃ©es.
 Ces techniques sont aujourd'hui considÃ©rÃ©es comme rudimentaires mais les calculs d'histogrammes et les analyses associÃ©es interviennent dans beaucoup d'algorithmes rÃ©cents parmi les plus Ã©voluÃ©s et performants. 
 La figure \ref{fig-histo-cochon} illustre le traitement typique de l'histogramme de l'image d'entrÃ©e \ref{fig-histo-cochon-a} dans le but de distinguer les deux rÃ©gions du fond et du cochon (la cible). La premiÃ¨re Ã©tape consiste Ã  dresser l'histogramme des niveaux de gris sur tout le domaine de l'image \ref{fig-histo-cochon-b}. Il faut ensuite identifier le seuil de sÃ©paration des deux rÃ©gions supposÃ©es, ici, homogÃ¨nes au sens des valeurs de niveau de gris. Une estimation visuelle peut-Ãªtre faite, mais on voit immÃ©diatement que mÃªme dans une situation aussi claire, le choix du seuil n'est pas Ã©vident. Pour un traitement automatique, on peut par exemple proposer la technique itÃ©rative prÃ©sentÃ©e par l'Algorithme  \ref{algo-histo-cochon} qui conduit Ã  la segmentation de la figure \ref{fig-histo-cochon-c}. L'image \ref{fig-histo-cochon-d} est l'image initiale, corrompue par un bruit gaussien de moyenne nulle et d'Ã©cart type 25 . Les rÃ©sultats de la segmentation (\ref{fig-histo-cochon-c} et \ref{fig-histo-cochon-f}) de cette image sont clairement insuffisants le segment de la cible comporte des discontinuitÃ©s et dans le cas de l'image bruitÃ©e,  des pixels orphelins Ã©pars demeurent en quantitÃ©. Cette technique nÃ©cessiterait une Ã©tape supplÃ©mentaire pour disposer d'une segmentation pertinente.
 
 \begin{figure}
   \centering
-  \subfigure[Image initiale comportant deux zones : le fond et le cochon (la cible)]{\label{fig-histo-cochon-a} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/cochon256.png}}\quad
-  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-b} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/histo-cochon256.png}}\quad
-  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  101 aprÃ¨s 4 itÃ©rations.]{\label{fig-histo-cochon-c} \includegraphics[width=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/cochon256-seghisto-101-255.png}}\\
-\subfigure[Image initiale bruitÃ©e]{\label{fig-histo-cochon-d} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/cochon256-sig25.png}}\quad
-  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-e} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/histo-cochon256-sig25.png}}\quad
-  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  99 aprÃ¨s 5 itÃ©rations.]{\label{fig-histo-cochon-f} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/cochon256-sig25-seghisto-99-255.png}}
-  \caption{Segmentation par analyse simple d'histogramme. Colonne de gauche : image d'entrÃ©e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : rÃ©sultat de la segmentation.}
+  \subfigure[Image initiale comportant deux zones : le fond et le cochon (la cible)]{\label{fig-histo-cochon-a} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256.png}}\quad
+  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-b} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256.png}}\quad
+  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  101 aprÃ¨s 4 itÃ©rations.]{\label{fig-histo-cochon-c} \includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-seghisto-101-255.png}}\\
+\subfigure[Image initiale bruitÃ©e]{\label{fig-histo-cochon-d} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256-sig25.png}}\quad
+  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-e} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256-sig25.png}}\quad
+  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  99 aprÃ¨s 5 itÃ©rations.]{\label{fig-histo-cochon-f} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-sig25-seghisto-99-255.png}}
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entrÃ©e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : rÃ©sultat de la segmentation.}
 \label{fig-histo-cochon}
 \end{figure}
  
 \begin{algorithm}
-  \SetNlSty{textbf}{}{:}
-  \SetKwComment{Videcomment}{}{}
+  %\SetNlSty{textbf}{}{:}
+  %\SetKwComment{Videcomment}{}{}
 \caption{Calcul du seuil de sÃ©paration des segments de l'histogramme.}   
 \label{algo-histo-cochon}
 $\overline{h} \leftarrow $ histogramme sur l'image \;
@@ -119,14 +261,36 @@ $\epsilon \leftarrow 1$ \;
 Un autre formalisme qui a gÃ©nÃ©rÃ© une vaste classe d'algorithmes de segmentation est celui des graphes et repose sur l'idÃ©e que les rÃ©gions de l'image sont reprÃ©sentÃ©es par les n\oe uds du graphe, alors que les liens traduisent les relations de voisinage existant entre les rÃ©gions.
 L'idÃ©e de base est d'initialiser le graphe avec un n\oe ud pour chaque pixel. La segmentation est obtenue par simplification itÃ©rative du graphe, en Ã©valuant les liens et en dÃ©terminant ceux Ã  supprimer et ce, jusqu'Ã  convergence.
 L'essentiel de la problÃ©matique rÃ©side donc dans la mÃ©trique retenue pour Ã©valuer les liens ainsi que dans le critÃ¨re de sÃ©lection et lÃ  encore, la littÃ©rature regorge d'une grande variÃ©tÃ© de propositions.
-Nous pouvons retenir que les premiÃ¨res d'entre elles, qui n'Ã©taient pas spÃ©cifiquement dÃ©diÃ©es Ã  la segmentation d'images numÃ©riques mais au regroupement d'Ã©lÃ©ments rÃ©partis sur un domaine (1D ou 2D), ont Ã©tÃ© Ã©laborÃ©es autour d'une mesure locale des liens basÃ©e sur la distance entre les Ã©lÃ©ments. La rÃ©duction du graphe est ensuite effectuÃ©e en utilisant un algorithme spÃ©cifique, comme le \textit{minimum spanning tree}, dont l'application a Ã©tÃ© dÃ©crite dÃ¨s 1970 dans \ref{slac-pub-0672} et oÃ¹ il s'agit simplement de supprimer les liens \textit{inconsistants}, c'est Ã  dire ceux dont le poids est significativement plus Ã©levÃ© que la moyenne des voisins se trouvant de chaque cotÃ© du lien en question.
+Nous pouvons retenir que les premiÃ¨res d'entre elles, qui n'Ã©taient pas spÃ©cifiquement dÃ©diÃ©es Ã  la segmentation d'images numÃ©riques mais au regroupement d'Ã©lÃ©ments rÃ©partis sur un domaine (1D ou 2D), ont Ã©tÃ© Ã©laborÃ©es autour d'une mesure locale des liens basÃ©e sur la distance entre les Ã©lÃ©ments. La rÃ©duction du graphe est ensuite effectuÃ©e en utilisant un algorithme spÃ©cifique, comme le \textit{minimum spanning tree}, dont l'application a Ã©tÃ© dÃ©crite dÃ¨s 1970 dans \cite{slac-pub-0672} et oÃ¹ il s'agit simplement de supprimer les liens \textit{inconsistants}, c'est Ã  dire ceux dont le poids est significativement plus Ã©levÃ© que la moyenne des voisins se trouvant de chaque cotÃ© du lien en question.
 L'extension a rapidement Ã©tÃ© faite aux images numÃ©riques en ajoutant l'intensitÃ© des pixels au vecteur des paramÃ¨tres pris en compte dans l'Ã©valuation du poids des liens.
 D'autres critÃ¨res de simplification ont aussi Ã©tÃ© Ã©laborÃ©s, avec pour ambition de toujours mieux prendre en compte les caractÃ©ristiques structurelles globales des images pour prÃ©tendre Ã  une segmentation qui conduise Ã  une meilleure perception conceptuelle.
-Le principe gÃ©nÃ©ral des solutions actuelles est proche de l'analyse en composantes principales appliquÃ©e Ã  une matrice d'affinitÃ©s qui traduit les liens entre les segments.
-On peut citer, par ordre chronologique, les mÃ©thodes reposant sur le \textit{graphe optimal} de Wu et Leahy \ref{wulealy_1993} et plus rÃ©cemment \ref{cf_notes x5}. Le principal point faible de ces techniques rÃ©side essentiellement dans la difficultÃ©  Ã  trouver un compromis acceptable entre identification de structures globales et prÃ©servation des Ã©lÃ©ments de dÃ©tails. Cela se traduit dans la pratique par un ensemble de paramÃ¨tres Ã  rÃ©gler pour chaque type de segmentation Ã  effectuer.
+Le principe gÃ©nÃ©ral des solutions actuelles est proche de l'analyse en composantes principales appliquÃ©e Ã  une matrice de similaritÃ© qui traduit les liens entre les segments.
+Pour des images en niveaux de gris, l'expression gÃ©nÃ©rale des Ã©lÃ©ments $w_{ij}$ de la matrice de similaritÃ© $W$ est :
+\[w_{ij} = 
+\begin{cases}
+\mathrm{e}^{\|v_i-v_j\|^2/\sigma_v^2}\mathrm{e}^{\|x_i-x_j\|^2/\sigma_x^2} & \text{si $\|x_i-x_j\|<r$}\\
+0 & \text{sinon}
+\end{cases}
+\]
+On construit ensuite la matrice de connectivitÃ© $D$, diagonale et dont les Ã©lÃ©ments sont :
+\[d_{i} = \displaystyle\sum_jw_{ij}\]
+
+Le systÃ¨me dont on cherche les valeurs propres $\lambda_k$ et les vecteurs propres associÃ©s $Y_k$ est alors le suivant :
+\[\left(D-W)\right)Y=\lambda DY \]
+
+Parmi les mÃ©thodes reposant sur ce principe, on peut citer, par ordre chronologique, celles qui reposent sur le \textit{graphe optimal} de Wu et Leahy \cite{wulealy_1993} et plus rÃ©cemment \cite{cf-notes-x5}. Le principal point faible de ces techniques rÃ©side essentiellement dans la difficultÃ©  Ã  trouver un compromis acceptable entre identification de structures globales et prÃ©servation des Ã©lÃ©ments de dÃ©tails. Cela se traduit dans la pratique par un ensemble de paramÃ¨tres Ã  rÃ©gler pour chaque type de segmentation Ã  effectuer.
 Cependant, elles sont employÃ©es dans les algorithmes de haut niveau les plus rÃ©cents, comme nous le verrons plus loin.
-La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \ref{sm-ncuts}. Quatre paramÃ¨tres sont Ã  fixer pour rÃ©aliser la segmentation, ils correspondent respectivement aux facteurs de forme de la matrice d'affinitÃ©s en termes de distance et de niveau de gris (2 paramÃ¨tres), Ã  la surface minimale admise pour un segment ainsi qu'au seuil de sÃ©gmentation des graphes. Le choix des valeurs pour les paramÃ¨tres n'est pas immÃ©diat et la figure illustre bien la difficultÃ© de trouver un compromis acceptable. Enfin, les temps d'exÃ©cutions peuvent devenir trÃ¨s rapidement prohibitifs dÃ¨s lors que l'on utilise des facteurs de forme Ã©tendus.
-  
+La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \cite{sm-ncuts-pami2000} et implÃ©mentÃ© par Cour, Yu et Shi en 2004. Cette implÃ©mentation utilise des valeurs prÃ©-Ã©tablies des paramÃ¨tres de calcul de la matrice de similaritÃ© produisant de bonnes segmentations d'objets et/ou personnes dans les images naturelles, mais requiert de prÃ©dÃ©terminer le nombre de segments Ã  obtenir. Les images de la figure reprÃ©sentent les rÃ©sultats obtenus avec un nombre de segments variant de 2 Ã  5 et montrent qu'il difficile de trouver un compromis acceptable. Enfin, les temps d'exÃ©cutions peuvent devenir trÃ¨s rapidement prohibitifs, mÃªme avec des implÃ©mentations plus optimisÃ©es. Pour information, les rÃ©sultats de la figure \ref{fig-graph-cochon} ont Ã©tÃ© obtenus en 1.5~s environ (Matlab R2010 sur CPU intel core i5-2520M @ 2.50GHz - linux 3.2.0) 
+\begin{figure}
+  \centering
+  \subfigure[$s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_2seg.png}}
+  \subfigure[$s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_3seg.png}}
+  \subfigure[$s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_4seg.png}}
+  \subfigure[$s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_5seg.png}}
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par simplification de graphe de type \textit{Normalized cut} pour un nombre $s$ de segments variant de 2 Ã  5.}
+\label{fig-graph-cochon}
+\end{figure}
+
     
 \subsection{kernel-means, mean-shift et dÃ©rivÃ©s}
 ParallÃ¨lement Ã  la rÃ©duction de graphes, d'autres approches ont donnÃ© naissance Ã  une multitude de variantes tournÃ©es vers la recherche des moindres carrÃ©s. 
@@ -135,136 +299,93 @@ Il s'agit simplement de minimiser l'erreur quadratique totale, ce qui peut se r
 oÃ¹ $\mu_i$ reprÃ©sente la valeur affectÃ©e au segment $\Omega_i$, i.e la valeur moyenne des observations $v_k$ sur $\Omega_i$, et $\displaystyle{\bigcup_{i\in[1..C]}\Omega_i=\Omega}$ 
 
 Cette idÃ©e est trÃ¨s intuitive et simple, mais n'a pas souvent de solution explicite, d'autant que le nombre des segments est \textit{a priori} inconnu.
-DÃ¨s 1965, Mac Queen a proposÃ© l'appellation k-means pour cette procÃ©dure itÃ©rative de regroupement \ref{kmeans_1965} qui dÃ©bute avec $k$ groupes d'un seul pixel\footnote{Dans son article, MacQueen ne parle pas de pixel mais de point. En effet, la mÃ©thode dÃ©crite ne visait pas Ã  segmenter des images, mais des donnÃ©es de natures diverses.}
+DÃ¨s 1965, Mac Queen a proposÃ© l'appellation k-means pour cette procÃ©dure itÃ©rative de regroupement \cite{kmeans-1965} qui dÃ©bute avec $k$ groupes d'un seul pixel\footnote{Dans son article, MacQueen ne parle pas de pixel mais de point. En effet, la mÃ©thode dÃ©crite ne visait pas Ã  segmenter des images, mais des donnÃ©es de natures diverses.}
 pris au hasard, puis d'ajouter chaque point au groupe dont la moyenne est la plus proche de la valeur du point Ã  ajouter. La moyenne du groupe nouvellement agrandi doit alors Ãªtre recalculÃ©e avant le prochain ajout.
 Cette implÃ©mentation est extrÃªmement simple Ã  mettre en \oe uvre \footnote{MÃªme si en 1965, rien n'Ã©tait simple Ã  programmer} mais elle possÃ¨de de nombreux dÃ©faut dont le principal est qu'elle ne converge pas nÃ©cessairement vers le regroupement optimal, mÃªme si on connait la ``bonne'' valeur de $k$. 
 Un autre est d'Ãªtre trÃ¨s dÃ©pendant du choix des $k$ Ã©lÃ©ments initiaux, en nombre et en position.
 
 Toutefois, vraisemblablement du fait de sa simplicitÃ© d'implÃ©mentation et de temps d'exÃ©cution rapides, la communautÃ© scientifique s'est beaucoup penchÃ©e sur cette mÃ©thode pour en compenser les dÃ©fauts, jusqu'Ã  en faire une des plus employÃ©es, en particulier par les statisticiens.
-On compte aussi beaucoup de variantes telles les \textit{k-centers} \ref{k_centers} et les \textit{k-mÃ©dians} \ref{k_medians} qui n'employent pas la moyenne arithmÃ©tique comme expression du ``centre'' d'un segment. 
-Des solutions ont aussi Ã©tÃ© apportÃ©es pour l'estimation de $k$ en employant, par exemple, un critÃ¨re de vraisemblance pour choisir la meilleure valeur de $k$ dans un intervalle donnÃ© \ref{x-means}.
+On compte aussi beaucoup de variantes telles les \textit{k-centers} \cite{k-centers} et les \textit{k-mÃ©dians} \cite{k-medians} qui n'employent pas la moyenne arithmÃ©tique comme expression du ``centre'' d'un segment. 
+Des solutions ont aussi Ã©tÃ© apportÃ©es pour l'estimation de $k$ en employant, par exemple, un critÃ¨re de vraisemblance pour choisir la meilleure valeur de $k$ dans un intervalle donnÃ© \cite{x-means}.
+Ã titre d'illustration et de comparaison, l'image du cochon a Ã©tÃ© traitÃ©e par une implÃ©mentation naÃ¯ve de l'algorithme original des \textit{k-means} en donnant successivement au nombre de segments les valeurs $s=2$ Ã  $s=5$. Les rÃ©sultats sont reproduits Ã  la figure \ref{fig-kmeans-cochon} et montrent encore une fois l'influence de $s$ sur la segmentation.
+\begin{figure}
+  \centering
+  \subfigure[$s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_2seg.png}}
+  \subfigure[$s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_3seg.png}}
+  \subfigure[$s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_4seg.png}}
+  \subfigure[$s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_5seg.png}}
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme \textit{k-means} pour un nombre $s$ de segments variant de 2 Ã  5. Chaque couleur est associÃ©e Ã  un segment. Les couleurs sont choisies pour une meilleure visualisation des diffÃ©rents segments.}
+\label{fig-kmeans-cochon}
+\end{figure}
 
-Un algorithme initiallement proposÃ© en 1975 par Fukunaga et Hostetler \ref{Lestimation_html} permet de maniÃ¨re plus gÃ©nÃ©rique de dÃ©terminer le nombre de segments, ou modes, ainsi que les points, ou pixels, qui les composent. Il cherche pour ce faire Ã  localiser les $k$ positions ou le gradient de densitÃ© s'annule. 
+Un algorithme initiallement proposÃ© en 1975 par Fukunaga et Hostetler \cite{Lestimation-html} permet de maniÃ¨re plus gÃ©nÃ©rique de dÃ©terminer le nombre de segments, ou modes, ainsi que les points, ou pixels, qui les composent. Il cherche pour ce faire Ã  localiser les $k$ positions ou le gradient de densitÃ© s'annule. 
 Il utilisÃ© un voisinage pondÃ©re (ou \textit{kernel}) et dÃ©termine le centre de masse des segments en suivant itÃ©rativement le gradient de densitÃ© dans le voisinage autour de chaque Ã©lÃ©ment du domaine. Lorsque l'algorithme Ã  convergÃ©, les $k$ segments sont identifiÃ©s et continennent chacun l'ensemble des points qui ont conduit Ã  leur centre de masse respectif.
-Ãtonnement, malgrÃ© ses qualitÃ©s intrinsÃ¨ques, cet algorithme du \textit{mean-shift} est restÃ© longtemps sans susciter de grand intÃ©rÃªt, jusqu'Ã  l'Ã©tude de Cheng \ref{meanshift_1995} qui en a demontrÃ© les propriÃ©tÃ©s et Ã©tabli les lien avec d'autres techniques d'optimisation commme la descente/montÃ©e de gradient ou de filtrage commme le floutage.
-Comaniciu et Peer ont alors Ã©tendu l'Ã©tude et proposÃ© une application Ã  la segmentation en utilisant l'espace colorimÃ©trique CIELUV \ref{Computer Graphics by Foley, van Dam, Feiner, and Hughes, published by Addison-Wesley, 1990} et montrÃ© qu'elle permettait une meilleure identification des modes de l'image \ref{mean_shift 1999 2002}.
+Ãtonnement, malgrÃ© ses qualitÃ©s intrinsÃ¨ques, cet algorithme du \textit{mean-shift} est restÃ© longtemps sans susciter de grand intÃ©rÃªt, jusqu'Ã  l'Ã©tude de Cheng \cite{meanshift_1995} qui en a demontrÃ© les propriÃ©tÃ©s et Ã©tabli les lien avec d'autres techniques d'optimisation commme la descente/montÃ©e de gradient ou de filtrage commme le floutage.
+Comaniciu et Peer ont alors Ã©tendu l'Ã©tude et proposÃ© une application Ã  la segmentation en utilisant l'espace colorimÃ©trique CIELUV \cite{Computer-Graphics-by-Foley-van-Dam-Feiner-and-Hughes-published-by-Addison-Wesley-1990} et montrÃ© qu'elle permettait une meilleure identification des modes de l'image \cite{mean-shift-1999,2002}.
+Une implÃ©mentation de la variante proposÃ©e par Keselman et Micheli-Tzanakou dans \cite{yket1999} appliquÃ©e Ã  notre image de test fournit les rÃ©sultats reproduits Ã  la figure  \ref{fig-meanshift-cochon}. Pour se rapprocher des traitements prÃ©cÃ©dents, nous avons identifiÃ©, par essais successifs, les tailles de voisinage conduisant Ã  des nombre de segments identiques Ã  ceux des figures prÃ©cedentes (de 2 Ã  5). Le volume minimal admis pour un segment Ã  Ã©tÃ© arbitrairement fixÃ© Ã  100 pixels. 
+\begin{figure}
+  \centering
+  \subfigure[$r=100 \Rightarrow s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r100m100.png}}
+  \subfigure[$r=50 \Rightarrow s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r50m100.png}}
+\subfigure[$r=35 \Rightarrow s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r35m100.png}}
+  \subfigure[$r=25 \Rightarrow s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r25m100.png}}  
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme \textit{mean-shift} pour un rayon de voisinage $r$ de 100, 50, 35 et 25 pixels permettant d'obtenir un nombre $s$ de segments variant respectivement de 2 Ã  5. Le volume minimal admis pour un segment est fixÃ© Ã  100 pixels. Chaque couleur est associÃ©e Ã  un segment. Les couleurs sont choisies pour une meilleure visualisation des diffÃ©rents segments.}
+\label{fig-meanshift-cochon}
+\end{figure}
 
-Il est Ã  noter que les segmentations basÃ©es sur des algorithmes de \textit{clustering} nÃ©cessitent une phase supplÃ©mentaire de gÃ©nÃ©ration des frontiÃ¨res inter-segments et d'affectation de la valeur de chaque segment aux Ã©lÃ©ments qui le composent. 
+Il est Ã  noter que les segmentations basÃ©es sur des algorithmes de \textit{clustering} comme ceux que l'on vient de prÃ©senter nÃ©cessitent le plus souvent une phase supplÃ©mentaire de gÃ©nÃ©ration des frontiÃ¨res inter-segments et d'affectation de la valeur de chaque segment aux Ã©lÃ©ments qui le composent. 
 Par ailleurs, dans les deux cas du \textit{k-means} et du \textit{mean-shift}, chaque itÃ©ration gÃ©nÃ¨re une rÃ©duction de la variance (due au moyennage) et on peut donc rapprocher ces techniques de celles de rÃ©duction de bruit par minimisation de variance.
 
 \subsection{Les contours actifs, ou \textit{snakes}}
 Contrairement aux prÃ©cÃ©dentes techniques et comme leur nom le laisse deviner, les Ã©lÃ©ments constitutifs de ces mÃ©thodes sont cette fois des \textit{contours} et non plus des \textit{rÃ©gions}. De fait, ils dÃ©finissent nativement une segmentation de l'image.
-Le principe gÃ©nÃ©ral est de superposer une courbe paramÃ©trique Ã  l'image, le \textit{snake}, puis de lui appliquer des dÃ©formations successives destinÃ©es Ã  rapprocher le \textit{snake} des contours de l'objet. Les dÃ©formations Ã  appliquer sont guidÃ©es par l'Ã©valuation d'une fonction d'Ã©nergie prenant en compte :
+Le principe gÃ©nÃ©ral est de superposer une courbe paramÃ©trique $S$ Ã  l'image, le \textit{snake}, puis de lui appliquer des dÃ©formations successives destinÃ©es Ã  rapprocher le \textit{snake} des contours de l'objet. Les dÃ©formations Ã  appliquer sont guidÃ©es par l'Ã©valuation d'une fonction d'Ã©nergie $E_{snake}$ prenant en compte :
 \begin{itemize}
-\item l'Ã©nergie interne de la courbe, fonction de son allongement de sa courbure.
-\item l'Ã©nergie externe liÃ©e Ã  l'image, fonction de la proximitÃ© de la courbe avec les zones de fort gradient et Ã©ventuellement une contrainte fixÃ©e par l'utilisateur comme des points imposÃ©s par exemple.
+\item l'Ã©nergie interne $E_{int}$ de la courbe, fonction de son allongement de sa courbure.
+\item l'Ã©nergie externe $E_{ext}$ liÃ©e Ã  l'image, fonction de la proximitÃ© de la courbe avec les zones de fort gradient et Ã©ventuellement une contrainte fixÃ©e par l'utilisateur comme des points imposÃ©s par exemple.
 \end{itemize}
-Ici encore, la rÃ©solution du problÃ¨me revient Ã  minimiser une fonction d'Ã©nergie sous contrainte et les diverses techniques de rÃ©solution numÃ©rique peuvent s'appliquer comme pour les autres classes d'algorithmes itÃ©ratifs prÃ©sentÃ©s prÃ©cÃ©demment. 
-
-Dans sa version originale proposÃ©e par Kass \textit{et al.} en 1988 \ref{snake_kass_1988}, l'algorithme dit du \textit{snake} prÃ©sente l'intÃ©rÃªt de converger en un nombre d'itÃ©rations assez rÃ©duit et permet de suivre naturellement un \textit{cible} en mouvement aprÃ¨s une convergence initiale Ã  une position donnÃ©e, chaque position de convergence fournissant une position initiale pertinente pour la position suivante.
-Toutefois, il se montre sensible Ã  l'Ã©tat initial de la courbe et requiert souvent de celle-ci qu'elle soit assez proche de l'objet Ã  ``entourer'', sous peine de se verrouiller dans un minimum local. 
+L'expression gÃ©nÃ©rique peut alors s'Ã©crire 
+\[E_{snake} = E_{int}+E_{ext}\]
+oÃ¹ 
+\[E_{int} = \displaystyle\sum_{s\in S} \frac{1}{2}\left(\alpha\left|\frac{\partial x_s}{\partial s}\right|^2
++\beta \left|\frac{\partial^2x_s}{\partial s^2}\right|\right)ds\]
+et 
+\[E_{ext} = \displaystyle\sum_{s\in S} -\left|\nabla\left[G_{\sigma}(x_s)\ast v_s\right]\right|^2ds\]
+
+L'idÃ©e gÃ©nÃ©rale de l'algorithme du \textit{snake} est de trouver une courbe $S$ qui minimise l'Ã©nergie totale $E_{snake}$. 
+Ici encore, la rÃ©solution du problÃ¨me revient donc Ã  minimiser une fonction sous contrainte et les diverses techniques de rÃ©solution numÃ©rique peuvent s'appliquer comme pour les autres classes d'algorithmes itÃ©ratifs prÃ©sentÃ©s prÃ©cÃ©demment, avec ici encore, un nombre de paramÃ¨tres Ã  rÃ©gler assez important. Notons Ã©galement que dans le cas gÃ©nÃ©ral, les paramÃ¨tres notÃ©s $\alpha$ et $\beta$, que l'on qualifie aussi d'Ã©lasticitÃ© et de raideur, sont aussi des fonctions de l'abscisse curviligne $s$. La fonction $G_{\sigma}$ est la fonction d'attraction aux forts gradients de l'image. 
+
+Dans sa version originale proposÃ©e par Kass \textit{et al.} en 1988 \cite{snake-kass-1988}, l'algorithme dit du \textit{snake} prÃ©sente l'intÃ©rÃªt de converger en un nombre d'itÃ©rations assez rÃ©duit et permet de suivre naturellement un \textit{cible} en mouvement aprÃ¨s une convergence initiale Ã  une position donnÃ©e, chaque position de convergence fournissant une position initiale pertinente pour la position suivante.
+Toutefois, il se montre particuliÃ¨rement sensible Ã  l'Ã©tat initial de la courbe et requiert souvent de celle-ci qu'elle soit assez proche de l'objet Ã  ``entourer'', sous peine de se verrouiller dans un minimum local. 
 La sensibilitÃ© au bruit n'est pas non plus trÃ¨s bonne du fait de la formulation locale de l'Ã©nergie.  
 Les ``concavitÃ©s'' Ã©troites ou prÃ©sentant un goulot d'Ã©tranglement marquÃ© sont par ailleurs mal dÃ©limitÃ©es.
 Enfin, la fonction d'Ã©nergie Ã©tant calculÃ©e sur la longueur totale de la courbe, cela pÃ©nalise la bonne identification des structures de petite taille vis Ã  vis de la longueur totale de la courbe.
+La figure \ref{fig-snake-tradi-cochon} illustre ces dÃ©fauts en montrant quelques Ã©tats intÃ©rmÃ©diaires ainsi que le rÃ©sultat final d'une segmentation rÃ©alisÃ©e Ã  partir d'un contour  initial circulaire et des paramÃ¨tres Ã  valeurs constantes et rÃ©glÃ©s empiriquement, en employant la mÃ©thode du snake original.
+On voit que la convergence est assez rapide mais que le contour ainsi dÃ©tÃ©rminÃ© ne ``colle'' pas bien Ã  l'objet que l'on s'attend Ã  isoler.
+\begin{figure}
+  \centering
+\subfigure[Les Ã©tats initial et suivant chacune des trois premiÃ¨res itÃ©rations]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it3.png}}
+\subfigure[L'Ã©tat  du contour aprÃ¨s la septiÃ¨me itÃ©ration]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it7.png}}
+\subfigure[L'Ã©tat du contour aprÃ¨s la dixiÃ¨me itÃ©ration]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it10.png}}
+\subfigure[L'Ã©tat du contour aprÃ¨s la centiÃ¨me itÃ©ration. C'est le contour final.]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_result.png}}   
+\caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme dit du \textit{snake}, dans sa version originale. Les paramÃ¨tres d'Ã©lastictiÃ©, de raideur et d'attraction ont Ã©tÃ© fixÃ©s respectivement aux valeurs 5, 0.1 et 5. }
+\label{fig-snake-tradi-cochon}
+\end{figure} 
+
 Il est cependant possible de contrÃ´ler la finesse de la segmentation mais au prix de temps de calculs qui peuvent devenir trÃ¨s longs.
-Les variantes les plus intÃ©ressantes sont :
+Parmi les variantes Ã©laborÃ©es qui tentent de pallier ces dÃ©fauts, les plus intÃ©ressantes sont :
 \begin{itemize}
 \item le \textit{balloon snake}, conÃ§u pour remÃ©dier au mauvais suivi des concavitÃ©s en introduisant une force supplÃ©mentaire de pression tendant Ã  \textit{gonfler} le snake jusqu'Ã  ce qu'il rencontre un contour suffisamment marquÃ©. Cela suppose toutefois que l'Ã©tat initial de la courbe la situe entiÃ¨rement Ã  l'intÃ©rieur de la zone Ã  segmenter et est surtout employÃ© dans des applications semi-automatiques oÃ¹ l'utilisateur dÃ©finit au moins une position et une taille initiales pour la courbe. 
 \item le \textit{snake} GVF (pour Gradient Vector Flow), dont le but est de permettre qu'une initialisation lointaine de la courbe ne pÃ©nalise pas la segmentation. Une carte des lignes de gradient est Ã©tablie sur tout le domaine de l'image et sert Ã  intÃ©grer une force supplÃ©mentaire dans l'Ã©nergie totale, qui attire la courbe vers la zone de fort gradient.
 \item les \textit{level-sets}, dont la particularitÃ© est de ne pas employer directement une courbe paramÃ©trique plane mais de dÃ©finir l'Ã©volution des frontiÃ¨res comme l'Ã©volution temporelle de l'ensemble des points d'une surface 3D soumise Ã  un champ de force, tels que leur Ã©lÃ©vation soit constamment nulle. 
 Les propriÃ©tÃ©s des contours actifs par \textit{level-sets} se sont rÃ©vÃ©lÃ©es intÃ©ressantes, en particulier la facultÃ© de se disjoindre ou de fusionner, mais les temps de calcul trÃ¨s pÃ©nalisants.
-AprÃ¨s la formulation initiale de Osher et Sethian en 1988 \ref{level_sets_osher_sethian_1988}, plusieurs faÃ§on de rÃ©duire le coÃ»t du calcul ont Ã©tÃ© formulÃ©es, dont les plus importantes restent les techniques dites \textit{narrow band} \ref{narrow_band_level_set} (bande Ã©troite) qui ne calcule Ã  chaque itÃ©ration que les points dans une bande Ã©troite autour du plan $z=0$ de l'itÃ©ration courante et \textit{fast marching} \ref{fast_marching_sethian} qui s'applique dans le cas particulier d'une Ã©volution monotone des fronts.  
-\item les \textit{snake} orientÃ©s rÃ©gions, qui visent essentiellement Ã  mieux caractÃ©riser les zones Ã  segmenter et amÃ©liorer la robustesse vis Ã  vis du bruit en employant une formulation de l'Ã©nergie calculÃ©e sur le domaine complet de l'image \ref{cohenSMIE93, ronfard}. Les premiers rÃ©sultats confirment la qualitÃ© de cette mÃ©thode, mais la nÃ©cessitÃ© d'effectuer les calculs sur l'image entiÃ¨re gÃ©nÃ©rait des temps de traitement prohibitifs jusqu'Ã  ce que Bertaux \textitat{et al.} proposent une amÃ©lioration algorithmique exacte permettant Ã  nouveau un calcul en 1D, le long de la courbe, moyennant une simple Ã©tape initiale gÃ©nÃ©rant un certain nombre d'images intÃ©grales \ref{snake_bertaux}. La section \ref{sec_contrib_snake} qui introduit notre contribution Ã  cette technique en donnera une description dÃ©taillÃ©e. 
+AprÃ¨s la formulation initiale de Osher et Sethian en 1988 \cite{level-sets-osher-sethian-1988}, plusieurs faÃ§on de rÃ©duire le coÃ»t du calcul ont Ã©tÃ© formulÃ©es, dont les plus importantes restent les techniques dites \textit{narrow band} \cite{narrow-band-level-set} (bande Ã©troite) qui ne calcule Ã  chaque itÃ©ration que les points dans une bande Ã©troite autour du plan $z=0$ de l'itÃ©ration courante et \textit{fast marching} \cite{fast_marching_sethian} qui s'applique dans le cas particulier d'une Ã©volution monotone des fronts.  
+\item les \textit{snake} orientÃ©s rÃ©gions, qui visent essentiellement Ã  mieux caractÃ©riser les zones Ã  segmenter et amÃ©liorer la robustesse vis Ã  vis du bruit en employant une formulation de l'Ã©nergie calculÃ©e sur le domaine complet de l'image \cite{cohenSMIE93, ronfard}. Les premiers rÃ©sultats confirment la qualitÃ© de cette mÃ©thode, mais la nÃ©cessitÃ© d'effectuer les calculs sur l'image entiÃ¨re gÃ©nÃ©rait des temps de traitement prohibitifs jusqu'Ã  ce que Bertaux \textit{et al.} proposent une amÃ©lioration algorithmique exacte permettant Ã  nouveau un calcul en 1D, le long de la courbe, moyennant une simple Ã©tape initiale gÃ©nÃ©rant un certain nombre d'images intÃ©grales \cite{snake-bertaux}. La section \ref{sec-contrib-snake} qui introduit notre contribution Ã  cette technique en donnera une description dÃ©taillÃ©e. 
 \end{itemize}
  
-
+% ne faut-il pas mieux Ã©luder le paragraphe ci-dessous
 \subsection{MÃ©thodes hybrides}
-Aujourd'hui, les algorithmes de segmentation les plus performants en terme de qualitÃ© emploient des techniques qui tentent de tirer le meilleur parti de plusieurs  des mÃ©thodes ``historiques'' dÃ©crites prÃ©cÃ©demment.
-Le meilleur exemple, et le seul que nous citerons, est le dÃ©tecteur de contour et l'algorithme de segmentation associÃ© proposÃ© par Arbelaez \textit{et al.} en 2010 \ref{amfm_2010}. Il compose avec la constructions d'histogrammes locaux pour gÃ©nÃ©rer une matrice de similitude (affinity matrix) et appliquer les techniques liÃ©es Ã  la thÃ©orie des graphes pour rÃ©duire la dimension de l'espace de reprÃ©sentation (calcul des valeurs et vecteurs propres). Il utilise ensuite une technique adaptÃ©e de \textit{ligne de partage des eaux} (que l'on aurait rangÃ©e avec les mean-shift) pour regrouper les segments. 
+Aujourd'hui, les algorithmes de segmentation les plus performants en terme de qualitÃ© emploient des techniques qui tentent de tirer le meilleur parti de plusieurs des mÃ©thodes ``historiques'' dÃ©crites prÃ©cÃ©demment.
+Le meilleur exemple, et le seul que nous citerons, est le dÃ©tecteur de contour et l'algorithme de segmentation associÃ© proposÃ© par Arbelaez \textit{et al.} en 2010 \cite{amfm-2010}. Il compose avec la constructions d'histogrammes locaux pour gÃ©nÃ©rer une matrice de similitude (affinity matrix) et appliquer les techniques liÃ©es Ã  la thÃ©orie des graphes pour rÃ©duire la dimension de l'espace de reprÃ©sentation (calcul des valeurs et vecteurs propres). Il utilise ensuite une technique adaptÃ©e de \textit{ligne de partage des eaux} \cite{watershed} (que l'on aurait rangÃ©e avec les mean-shift) pour regrouper les segments. 
 Les rÃ©sultats sont trÃ¨s bons et des implÃ©mentations efficaces ont dores et dÃ©jÃ  Ã©tÃ© Ã©crites (voir section \ref{sec_ea_gpu}. 
-  
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+%TODO 
+%peut-Ãªtre dire deux mots sur le partage des eaux (avec kmeans et meanshift) puisqu'il est employÃ© dans gPb
