X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/5efa829cb4570828a242e2baced8b215ea6029d5..e42b2289f57cc234c130e3cfdec43a7328d24958:/THESE/Chapters/chapter2/chapter2.tex?ds=inline

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index 9788856..43ceac1 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -1,427 +1,13 @@
-L'Ã©tendue des techniques applicables aux images numÃ©riques est aujourd'hui si vaste qu'il serait illusoire de chercher Ã  les dÃ©crire ici. Ce chapitre prÃ©sente plus spÃ©cifiquement les algorithmes utilisÃ©s en prÃ©sence d'images (fortement) bruitÃ©es. Le bruit rend potentiellement dÃ©licate l'extraction des informations utiles contenues dans les images pertubÃ©es ou en complique l'interpretation, qu'elle soit automatique ou confiÃ©e Ã  la vision humaine. 
-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. 
-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, 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}$. 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}
-\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}.
-On distingue en particulier les bruits suivants selon leur origine physique :
-\begin{itemize}
-\item la non uniformitÃ© de rÃ©ponse des photosites.
-\item le bruit de photon
-\item le bruit de courant d'obscuritÃ©
-\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}  
-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}}\]
-
-\subsection{Le speckle}
-En imagerie radar, sonar ou mÃ©dicale, les surfaces que l'on veut observer sont ``Ã©clairÃ©es'' par des sources cohÃ©rentes. Les propriÃ©tÃ©s locales de ces surfaces sont  le siÃ¨ge de rÃ©flexions multiples qui interfÃ¨rent entre elles pour gÃ©nÃ©rer un bruit de tavelures, ou speckle, dont l'intensitÃ© dÃ©pend de l'information contenue dans le signal observÃ©.
-
-Le speckle est ainsi un bruit de type \textit{multiplicatif} qui confÃ¨re aux observations une trÃ¨s grande variance qui peut-Ãªtre rÃ©duite en moyennant plusieurs  observations, ou vues,  de la mÃªme scÃ¨ne. Si $L$ est le nombre de vues, le speckle est traditionnellement modÃ©lisÃ© par la PDF suivante :
-\[p(v \mid u)=\frac{L^2v^{(L-1)}\mathrm{e}^{-L\frac{v}{u}}}{\Gamma (L)u^L} \]
-L'espÃ©rance vaut $\mathrm{E}\left[v\right]=u$ et la variance $\sigma^2=\frac{u^2}{L}$ est effectivement inversement proportionnelle Ã  $L$, mais pour le cas mono vue oÃ¹ $L=1$, la variance vaut $u^2$, soit un Ã©cart type du signal $v$ Ã©gal Ã  sa moyenne.
-
-\subsection{Le bruit ``sel et poivre''}
-Le bruit \textit{sel et poivre}, ou bruit \textit{impulsionnel} trouve son origine dans les pixels dÃ©fectueux des capteurs ou dans les erreurs de transmission. Il tire son nom de l'aspect visuel de la dÃ©gradation qu'il produit : des pixels noirs et blancs rÃ©partis dans l'image.
-Le bruit impulsionnel se caractÃ©rise par la probabilitÃ© $P$ d'un pixel d'Ãªtre corrompu. La PDF peut alors Ãªtre exprimÃ©e par parties comme suit, pour le cas d'images en 256 niveaux de gris (8 bits) :
-
-\[p(v \mid u)=
-\begin{cases}
-\frac{P}{2}+(1-P) & \text{si $v=0$ et $u=0$}\\
-\frac{P}{2}+(1-P) & \text{si $v=255$ et $u=255$}\\
-\frac{P}{2}       & \text{si $v=0$ et $u \neq 0$}\\
-\frac{P}{2}       & \text{si $v=255$ et $u \neq 255$}\\
-(1-P)             & \text{si $v=u$ et $u \notin \{0, 255\}$}\\
-0                 & sinon
-\end{cases}
- \]  
-
-\subsection{Le bruit de Poisson}
-Aussi appelÃ© \textit{bruit de grenaille} (shot noise), ce type de bruit est inhÃ©rent aux dispositifs de dÃ©tection des photons. Il devient prÃ©pondÃ©rant dans des conditions de faible Ã©clairement, lorsque la variabilitÃ© naturelle du nombre de photons reÃ§us par un photosite par intervalle d'intÃ©gration influe sur les propriÃ©tÃ©s statistiques du signal.
-Le bruit de grenaille est de type multiplicatif et suit une loi de Poisson. La PDF peut s'Ã©crire comme suit :
-\[ 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 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 \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.  
-
-
-\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.
-
-On pourrait donner de la segmentation une dÃ©finition spÃ©cifique par type d'usage, mais dans un souci d'unification, on propose la formulation gÃ©nÃ©rique suivante :
-``La segmentation consiste Ã  distinguer les zones homogÃ¨nes au sein d'une image''.
-Dans cette dÃ©finition, le caractÃ¨re \textit{homogÃ¨ne} s'entend au sens d'un critÃ¨re prÃ© Ã©tabli, adaptÃ© aux contraintes particuliÃ¨res de traitement comme le type de bruit corrompant les images, ou bien la dimension du signal observÃ© $\bar{v}$ selon que l'image est en couleur ou non. Un tel critÃ¨re peut ainsi Ãªtre un simple seuil de niveau de gris ou bien nÃ©cessiter de coÃ»teux calculs statistiques dont certains seront dÃ©taillÃ©s dans les chapitres suivants.
-
-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.
-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. 
-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_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}{}{}
-\caption{Calcul du seuil de sÃ©paration des segments de l'histogramme.}   
-\label{algo-histo-cochon}
-$\overline{h} \leftarrow $ histogramme sur l'image \;
-$S_{init} \leftarrow 128$ \;
-$S_k \leftarrow S_{init}$ \;
-$\epsilon \leftarrow 1$ \;
-\Repeat{$\|S_k - \frac{1}{2}(\mu_{inf} + \mu_{sup})\| < \epsilon $}{
-  $\mu_{inf}=\displaystyle \frac{\displaystyle\sum_{i<S_k}h_ii}{\displaystyle\sum_{i<S_k}h_i}$ \;
-  $\mu_{sup}=\displaystyle \frac{\displaystyle\sum_{i\geq S_k}h_ii}{\displaystyle\sum_{i\geq S_k}h_i}$ \;
-  $S_k = \frac{1}{2}(\mu_{inf} + \mu_{sup})$ \ ;
-} 
-\end{algorithm}
-
-\subsection{Analyse de graphe}
-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.
-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 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)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 \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.
-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 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. 
-Il s'agit simplement de minimiser l'erreur quadratique totale, ce qui peut se rÃ©sumer, pour une image de $N$ pixels, en la dÃ©termination du nombre $C$ de segments $\Omega_i$ et leur contenu, de sorte Ã  minimiser l'expression 
-\[\sum_{i\in[1..C]}\sum_{x_k\in\Omega_i} \left(v_k-\mu_i\right)^2\]  
-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.}
-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}.
-Ã 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. 
-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}.
-Une implÃ©mentation de la variante proposÃ©e par Keselman et Micheli-Tzanakou dans \ref{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} 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 $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 $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}
-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 \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 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.
-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. 
-\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} \ref{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
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+L'Ã©tendue des techniques applicables aux images numÃ©riques est aujourd'hui si vaste qu'il serait illusoire de chercher Ã  les dÃ©crire ici de maniÃ¨re exhaustive. Ce chapitre prÃ©sente plus spÃ©cifiquement les algorithmes utilisÃ©s en prÃ©sence d'images (fortement) bruitÃ©es, c'est-Ã -dire prÃ©sentant une altÃ©ration de la rÃ©alitÃ© \og absolue \fg{} qu'elles reprÃ©sentent. 
 
+Le bruit rend potentiellement dÃ©licate l'extraction des informations utiles contenues dans les images perturbÃ©es ou en complique l'interprÃ©tation, automatisÃ©e ou humaine. 
+L'intuition incite donc Ã  chercher des mÃ©thodes efficaces de prÃ©-traitement rÃ©duisant la puissance du bruit et permettant ainsi  aux traitements de plus haut niveau (comme la segmentation), d'opÃ©rer dans de meilleures conditions.           
 
+Toutefois, il faut Ã©galement considÃ©rer que les opÃ©rations prÃ©alables de rÃ©duction de bruit gÃ©nÃ¨rent des modifications statistiques et peuvent altÃ©rer  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 en prÃ©server toute l'information, ce qui est le cadre de notre contribution portant sur un algorithme de segmentation par contour actif polygonal (dit \textit{snake}, voir chapitre \ref{ch-snake}).
 
+De plus, toute opÃ©ration supplÃ©mentaire si basique soit elle, rÃ©duit le temps de traitement disponible pour l'opÃ©ration de haut niveau. En effet, lorsque les images Ã  analyser sont de grande taille,  procÃ©der Ã  un dÃ©bruitage prÃ©alable peut s'avÃ©rer incompatible avec les contraintes de dÃ©bit.
 
+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 issues de l'imagerie radar Ã  ouverture synthÃ©tique (ROS ou en anglais SAR) \cite{cutrona1990synthetic}, ou de l'imagerie mÃ©dicale Ã  ultrasons (Ã©chographie). 
+Ces dispositifs d'acquisition sont, par essence, gÃ©nÃ©rateurs de bruits divers, inhÃ©rents aux technologies mises en \oe uvre 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 d'ores 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. Quant Ã  la recherche d'un filtre universel, bien qu'encore illusoire, elle n'est pas abandonnÃ©e, tant les besoins sont nombreux, divers et souvent complexes.    
+       
