X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/5997a2db46b2dcd03451c2229f90a509b8db3759..d509beab7cc0737a1bdfbd609359733a30882a43:/THESE/Chapters/chapter2/chapter2.tex?ds=sidebyside

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index b02fcc4..43ceac1 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -1,643 +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.
-%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, 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}\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  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.
-\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}
-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}}\]
-
-\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 \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{Le filtre de convolution}
-L'opÃ©ration la plus employÃ©e dans les procÃ©dÃ©s de traitement d'image est sans doute la convolution. Selon les valeurs affectÃ©es aux coefficients du masque, le filtrage par convolution permet de rÃ©aliser bon nombre de traitements comme la rÃ©duction de bruit par moyennage ou noyau gaussien ou encore la dÃ©tection de contours. 
-Si la fonction dÃ©finissant le masque de convolution est notÃ©e $h$, l'expression gÃ©nÃ©rale de la valeur estimÃ©e de pixel de coordonnÃ©es $(i,j)$ est donnÃ©e par
-\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}
-
-\subsubsection{Le filtre mÃ©dian}
-Le filtrage mÃ©dian \cite{tukey77} est Ã©galement une opÃ©ration trÃ¨s employÃ©e en prÃ©traitement pour sa simplicitÃ© et ses propriÃ©tÃ©s de prÃ©servation des contours alliÃ©es Ã  une capacitÃ© de rÃ©duction 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}
-
-
-\subsubsection{Le filtre bilatÃ©ral}
-Le filtre bilatÃ©ral \cite{710815} est une composition d'opÃ©rations que l'on  peut voir comme un  filtre de convolution dont les coefficients ne dÃ©pendraient pas uniquement de la position du pixel courant par rapport au pixel central, mais Ã©galement de la diffÃ©rence de leurs intensitÃ©s (cas des images en niveaux de gris). 
-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}
-
-Il existe beaucoup de  variantes d'algorithmes basÃ©s sur des moyennes ou mÃ©dianes 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 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}.
-L'un de ces algorithmes tend Ã  utiliser une portion de la ligne de niveau de chaque pixel comme voisinage pour le moyennage. Cette technique a Ã©tÃ© prÃ©sentÃ©e dans \cite{bertaux2004speckle} et employÃ©e pour rÃ©duire le bruit de speckle. Nous y reviendrons en dÃ©tail dans le chapitre \ref{ch-lniv}.    
-  
-
-\subsubsection{Les algorithmes de filtrage par dictionnaire}
-Ces algorithmes font l'hypothÃ¨se qu'il est possible de dÃ©crire l'image Ã  dÃ©bruiter en utilisant une base de fonctions permettant de dÃ©composer l'image en une combinaison linÃ©aire des Ã©lÃ©ments de cette base. Les bases les plus employÃ©es sont les ondelettes \cite{Mallat:2008:WTS:1525499, Daubechies:1992:TLW:130655} ainsi que les fonctions sinusoÃ¯dales (DCT \cite{1093941,strang1999discrete}). Les Ã©lÃ©ments de la base peuvent Ãªtre prÃ©dÃ©terminÃ©s ou bien calculÃ©s Ã  partir des donnÃ©es de l'image, par exemple en s'appuyant sur une analyse en composantes principales ou aprÃ¨s apprentissage \cite{elad2006image}. Le principe du dÃ©bruitage est de considÃ©rer que le bruit est dÃ©corellÃ© des fonctions de la base et donc reprÃ©sentÃ© par les petits coefficients de la dÃ©composition, que l'on peut annuler. Diverses politiques de seuillage peuvent alors Ãªtre appliquÃ©es selon le type d'image et le modÃ¨le de bruit ayant chacune ses propres avantages et inconvÃ©nients. L'intÃ©rÃªt principal de ces mÃ©thodes est de bien restituer les transitions rapides (grande Ã©nergie), mais elles gÃ©nÃ¨rent en revanche des artefacts dus aux possibles grands coefficients de bruit. 
-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 algorithmes de filtrage par patches}
-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}. 
-
-\subsection{Le filtrage par convolution}
-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.
-
-\subsection{Le filtre mÃ©dian}
-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.
-
-\subsection{Le filtre bilatÃ©ral}  
-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 pour 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. La figure \ref{fig-prefetch-zheng} illustre la mise en \oe uvre de cette technique en montrant comment les threads d'un bloc se rÃ©partissent les prÃ©-chargements en mÃ©moire partagÃ©e des valeurs des pixels de la ROI. La gÃ©omÃ©trie des blocs de threads est ici choisie carrÃ©e, mais elle s'applique aisÃ©ment Ã  d'autres proportions comme nous le verrons plus loin. Les limites de cette mÃ©thode sont 
-\begin{itemize}
-\item la taille de la mÃ©moire partagÃ©e qui doit pouvoir stocker l'ensemble des valeurs des pixels de la ROI, ce qui peut imposer une limite sur la taille des blocs de threads.
-\item l'Ã©tendue du voisinage qui ne peut Ãªtre prÃ©-chargÃ© de cette faÃ§on (4 pixels par thread) que si la surface de la ROI demeure infÃ©rieure Ã  4 fois le nombre de thread par bloc. 
-\end{itemize}
-
-\begin{figure}
-  \centering
-  \includegraphics[width=10cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png}
-\caption{Illustration prÃ©-chargement en mÃ©moire partagÃ©e mise en \oe uvre dans \cite{zheng2011performance} pour l'implÃ©mentation, entre autres, du filtre bilatÃ©ral. a) en vert le bloc de threads associÃ© aux pixels centraux. b-e) les blocs de pixels successivement prÃ©-chargÃ©s en mÃ©moire partagÃ©e. f) la configuration finale de la ROI en mÃ©moire partagÃ©e.}
-\label{fig-prefetch-zheng}
-\end{figure}
-
-Cette recette est ensuite appliquÃ©e dans l'implÃ©mentation d'un filtre bilatÃ©ral et d'un filtre Ã  moyennes non locales (NL-means). Concernant le filtre bilatÃ©ral, 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.
-
-\subsection{Les filtres par patches}  
-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.
-
-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, le modÃ©le d'image 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} \cite{humphrey1924psychology} oÃ¹ l'on considÃ¨re que la perception conceptuelle s'Ã©labore au travers de regroupements visuel d'Ã©lÃ©ments.
-
-GÃ©nÃ©ralement, 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}\label{sec-histo}
-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 \cite{4310076} 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 peuvent  aujourd'hui Ãªtre 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{Partitionnement 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 partitionnement itÃ©ratif 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 \cite{Zahn:1971:GMD:1309266.1309359} 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 partitionnement ont Ã©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 repose sur la construction d'une matrice de similaritÃ© qui traduit les liens entre les segments et reprÃ©sente le graphe Ã  partitionner.
-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 Ã©galement la matrice de connectivitÃ© $D$, diagonale et dont les Ã©lÃ©ments sont :
-\[d_{i} = \displaystyle\sum_jw_{ij}\]
-
-Une famille de mÃ©thodes, inspirÃ©e par le \textit{graphe optimal} de Wu et Leahy \cite{wu1993optimal}, rÃ©alise le partitionnement sur la base des valeurs propres $\lambda_k$ et vecteurs propres $Y_k$ du systÃ¨me 
-\[\left(D-W)\right)Y=\lambda DY \]
-Certains algorithmes proposÃ©s plus rÃ©cemment s'inscrivent dans cette veine \cite{wang2001image,wang2003image,felzenszwalb2004efficient,shi2000normalized}. 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.
-
-La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \cite{shi2000normalized} 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}
-
-Un autre procÃ©dÃ© de partitionnement de graphe, reposant sur le thÃ©orÃ¨me dit du \textit{maximum flow-minimum cut} Ã©noncÃ© par Ford et Fulkerson \cite{ford1955simple} a fait l'objet de beaucoup de travaux. Des comparaison en sont rapportÃ©e dans \cite{boykov2004experimental,chandran2009computational}. 
-Plusieurs algorithmes mettent en \oe uvre ce procÃ©dÃ© avec de bons rÃ©sultats, comme la mÃ©thode du \textit{push-relabel} \cite{cherkassky1997implementing} ou le \textit{pseudoflow} \cite{hochbaum2013simplifications} qui semble aujourd'hui le plus peformant.
-
-\subsection{kernel-means, mean-shift et apparentÃ©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 \cite{macqueen1967some} 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} \cite{agarwal2002exact} et les \textit{k-mÃ©dians} \cite{arora1998approximation} 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{pelleg2000x}.
-Ã 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 \cite{fukunaga1975estimation} 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 \cite{cheng1995mean} 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{foley1994introduction} et montrÃ© qu'elle permettait une meilleure identification des modes de l'image \cite{comaniciu1999mean,comaniciu2002mean}.
-Une implÃ©mentation de la variante proposÃ©e par Keselman et Micheli-Tzanakou dans \cite{keselman1998extraction} 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 \cite{KassWT88}, 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 \cite{osher1988fronts}, 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{adalsteinsson1994fast} (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{sethian1996fast} 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{cohen1993surface, ronfard1994region}. 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{ChesnaudRB99,GallandBR03,GermainR01}. La section \ref{sec-contrib-snake} qui introduit notre contribution Ã  cette technique en donnera une description dÃ©taillÃ©e. 
-\end{itemize}
- 
-\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 \cite{arbelaez2011contour}. 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. 
-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
-
-\section{Les implÃ©mentations GPU des techniques de segmentation}
-
-La problÃ©matique tant Ã©tudiÃ©e de la segmentation n'a pas Ã©chappÃ© Ã  l'engouement des chercheurs pour les processeurs graphiques modernes. Un certain nombre de travaux proposent ainsi des implÃ©mentations GPU plus ou moins directes de mÃ©thodes de segmentation tirant parti de l'architecture massivememnt parallÃ¨le de ces matÃ©riels.
-La majoritÃ© d'entre elles cherche Ã  rÃ©pondre Ã  des besoins liÃ©s Ã  l'imagerie mÃ©dicale allant de la simple extraction des contours d'un organe, d'une tumeur, etc., Ã  la mesure de leur volume ; le traitement en 3D n'Ã©tant dans ce cas pas un choix mais une obligation, justifiant d'autant plus l'emploi des GPU.
- La natures des tissus et les formes Ã  identifier sont extrÃªmement variÃ©es. Les images sont souvent trÃ¨s bruitÃ©es et les modÃ¨les de bruit divers selon l'instrumentation employÃ©e. Enfin, le diagnostique mÃ©dical requerant la plus grande prÃ©cision possible, aucune solution gÃ©nÃ©rique satisfaisante de segmentation n'a encore pu Ã©merger dans ce cadre, laissant place Ã  autant d'implÃ©mentations adaptÃ©es que de besoin mÃ©dical spÃ©cifique.
-
-Beaucoup d'algorithmes rÃ©cents destinÃ©s Ã  la segmentation comportent plusieurs phases de calcul et mettent en \oe uvre diffÃ©rents algorithmes rÃ©alisant des fonctions Ã©lÃ©mentaires comme de la rÃ©duction de bruit ou du calcul d'histogramme.
- Selon le type de traitement Ã  effectuer sur le GPU, on peut-Ãªtre amenÃ© Ã  en concevoir des implÃ©mentations parallÃ¨les adaptÃ©es ou bien simplement exÃ©cuter indÃ©pendemment, pour chaque pixel par exemple, de multiples instances d'une version sÃ©quentielle classique du traitement.
-Dans les deux cas, on lira ``implÃ©mentation GPU'', mais cela recouvrira des rÃ©alitÃ©s et parfois aussi des niveaux de performance trÃ¨s diffÃ©rents.
-
-\subsection{Calcul d'histogramme}
-Comme il a Ã©tÃ© dit au paragraphe \ref{sec-histo}, les segmentations par analyse d'histogramme sont aujourd'hui cantonnÃ©es Ã  des applications trÃ¨s particuliÃ¨res et leurs implÃ©mentations GPU ne font pas l'objet de recherches, d'autant que dans la pratique, ces traitements sont souvent rÃ©alisÃ©s par des circuits spÃ©cialisÃ©s ou programmables de type FPGA et qu'il serait illusoire d'espÃ©rer les concurrencer par une solution de type gpu, plus coÃ»teuse, plus volumineuse et vraisemblablement moins robuste.
-
-Le calcul d'histogramme est cependant utilisÃ© de maniÃ¨re intensive dans certains algorithmes de haut-niveau, en particulier le \textit{level-set} et le \textit{gPb}. Ã ce titre, il faut citer les travaux de Fluck \textit{et al.} \cite{fluck2006gpu} qui apportent une rÃ©ponse efficace au calcul d'histogramme sur le GPU leur permetttant de conserver les donnÃ©es dans la mÃ©moire du processeur graphique tout au long de l'exÃ©cution de la segmentation par level-set qui leur a servi de motivation \cite{lefohn2003interactive}. 
-
-Les rÃ©sultats annoncÃ©s ont Ã©tÃ© obtenus sur un GPU GeForce 7900 et font Ã©tat du calcul des deux histogrammes nÃ©cessaires ( 64 classes chacun) sur une image de 256$\times$256 pixels en niveau de gris en 1.6~ms.
-
-\subsection{Partitionnement de graphe}
-Le domaine du traitement des graphes est trÃ¨s actif et peut fournir des Ã©lÃ©ments pour la segmentation comme l'implÃ©mentation du \textit{minimum spanning tree} dÃ©crite dans \cite{Vineet:2009:FMS:1572769.1572796} qui annonce la construction du minimum spanning tree d'un graphe de 5 millions de n\oe uds et 30 millions de liens en moins d'une seconde. 
-La parallÃ¨lisation GPU des opÃ©rations sur les graphes n'est pas simple en raison de l'indÃ©pendance des blocs de threads. Peu de travaux font encore Ã©tat d'implÃ©mentations efficaces mettant en \oe uvre ces techniques.
-On ne recense que quelques propositions GPU de l'algorithme \textit{push-relabel} pour le partitionnement selon l'approche \textit{min cut/max flow} dont on ne retient que les trois remarquables dÃ©taillÃ©e ci-dessous. 
-
-Dans \cite{dixit2005gpu}  une approche assez directe est mise en \oe uvre et parvient Ã  \textit{binariser} une image de 1~MP en 29~ms (GeForce 6800GT). 
-
-Les auteurs de \cite{4563095} remarquent qu'aprÃ¨s un nombre rÃ©duit d'itÃ©rations, trÃ¨s peu de n\oe ud se voient changer de segment. En consÃ©quence, certains blocs de traitement sont activÃ©s alors qu'ils n'ont effectivement pas de traitement Ã  effectuer et retardent ainsi les traitements Ã©ventuels des blocs en attente. Pour rÃ©duire les effet de ce comportement, un indicateur d'activitÃ© est calculÃ© Ã  chaque itÃ©ration et pour chaque bloc, en se basant le nombre de changements de segment qui vient d'y Ãªtre effectuÃ©. Ã l'itÃ©ration suivante, seuls les blocs considÃ©rÃ©s comme \textit{probablement} actifs seront activÃ©s, rÃ©duisant ainsi la latence globale. Un reparamÃ©trage dynamique du graphe aprÃ¨s chaque itÃ©ration est Ã©galement Ã©ffectuÃ© selon la mÃ©thode dÃ©crite par Kohli et Torr \cite{kohli2007dynamic}. Ces optimisations permettent d'atteindre un dÃ©bit d'environ 30 images de 0.3~MP par seconde sur GTX280, ce qui reprÃ©sente un bond en terme de performance. 
-
-Enfin, Stitch a proposÃ© dans \cite{graphcutscuda} des optimisations plus Ã©troitement liÃ©es Ã  l'architecture des GPUs Nvidia en faisant qu'un mÃªme thread mette Ã  jour plusieurs liens du graphe et aussi en compactant la reprÃ©sentation des indicateurs de changement de segment par 32 par l'emploi d'un seul bit par lien. Cela a permis d'accÃ©lÃ©rer la convergence de l'algorithme, comme la montre la courbe de la figure \ref{fig-graphcutscuda} (tirÃ©e de \cite{graphcutscuda}), et d'atteindre les 70 images par seconde dans les mÃªme conditions que prÃ©cÃ©demment (sur C1060).
-Il faut noter aussi que sur C1060, l'implÃ©mentation dÃ©crite dans \cite{4563095} est moins performante, avec 17~fps, que sur la carte GTX280.
-
-\begin{figure}
-  \centering
-  \includegraphics[width=12cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/graphcutscuda_stitch.png}
-\caption{Ãvolution du nombre de pixels actifs pour les itÃ©ration successives de l'implÃ©mentation  de l'algorithme push-relabel de \cite{graphcutscuda}. Les petites images montrent la localisation des pixels actifs aprÃ¨s chaque itÃ©ration, en blanc.}
-\label{fig-graphcutscuda}
-\end{figure}
-
-\subsection{K-means, mean-shift et apparentÃ©s}
-La popularitÃ© de l'algorithme des \textit{k-means} a induit des tentatives de portage sur GPU dont \cite{che2008performance} qui a implÃ©mentÃ© de maniÃ¨re directe l'etiquetage des Ã©lÃ©ments ainsi qu'une rÃ©duction partielle, par bloc,  pour la mise Ã  jour des centres ; la rÃ©duction finale Ã©tant rÃ©alisÃ©e par le CPU. Cette solution conduit Ã  un transfert des donnÃ©es Ã  chaque itÃ©ration et ne permet pas d'atteindre des performances Ã©levÃ©es. La mesure de performance a Ã©tÃ© faite avec la base de test KDD-Cup-99 \cite{kddcup99}, comportant 23 segments. Le temps annoncÃ© pour l'exÃ©cution d'une seule itÃ©ration sur un ensemble de 819200 Ã©lÃ©ments est de 200~ms. Toutefois, cette durÃ©e n'inclue pas la rÃ©duction ni les transferts et l'accÃ©lÃ©ration revendiquÃ©e semble alors trÃ¨s discutable.
-
-Dans \cite{5170921}, l'ensemble des tÃ¢ches d'Ã©tiquetage et de mise Ã  jour des centres est rÃ©alisÃ© sur le GPU. Une Ã©tape de rÃ©organisation des donnÃ©es est encore exÃ©cutÃ©e sur le CPU, mais elle s'avÃ¨re moins pÃ©nalisante que la solution prÃ©sentÃ©e prÃ©cÃ©demment, puisqu'elle permet de prÃ©senter au GPU des donnÃ©es permettant d'optimiser l'exÃ©cution parallÃ¨le de l'Ã©tape de rÃ©duction suivante (mise Ã  jour des centres). Les temps d'exÃ©cution par itÃ©ration sont sensiblement les mÃªmes que pour \cite{che2008performance} mais ils incluent cette fois l'ensemble des calculs (hors transferts). Les auteurs fournissent cette fois des mesures des temps d'exÃ©cution Ã  convergence, qui atteignent la vingtaine de secondes pour le mÃªme ensemble de test.
-
-La plus convaincante des implÃ©mentations de \textit{k-means} reste Ã  notre connaissance celle dÃ©crite dans \cite{kmeansgpuopengl} et oÃ¹ la totalitÃ© du traitement est effectuÃ©e sur le GPU, moyennant l'emploi d'une texture par segment de donnÃ©es. Les mesures ont montrÃ© que cette multiplication du nombre des textures ne constituait pas un facteur de perte de performance, tout du moins jusqu'aux limites des tests, conduits avec un maximum de 32 segments dans des ensembles de 1 million d'Ã©lÃ©ments. Sur GPU GeForce 8500GT, les temps d'exÃ©cution obtenus dans ces conditions sont de 13.8~ms par itÃ©ration, avec une dÃ©pendance trÃ¨s rÃ©duite vis Ã  vis du nombre de segments.
-
-Des travaux Ã  orientation non mÃ©dicale mettent en \oe uvre sur GPU un algorithme de \textit{mean-shift} pour la poursuite de cibles dans des sÃ©quences vidÃ©o \cite{li2009mean}. L'accÃ©lÃ©ration otenue par rapport aux implÃ©mentations sÃ©quentielles existantes n'est que d'un facteur 2. La solution prÃ©sentÃ©e effectue prÃ©alablement une rÃ©duction de l'espace colorimÃ©trique via un regroupement par la mÃ©thode \textit{k-means}, utilisÃ©e dans une version sÃ©quentielle. Un gain potentiel de performance pourrait Ãªtre apportÃ© en employant une implÃ©mentation GPU du \textit{k-means}, mais serait toutefois limitÃ© en raison des itÃ©rations nÃ©cessaires plus nombreuses pour le traitement \textit{mean-shift}. Par ailleurs, l'implÃ©mentation proposÃ©e fait un usage intensif de la mÃ©moire partagÃ©e et se heurte Ã  sa limite de 16~Ko par bloc, obligeant Ã  rÃ©duire la taille des blocs Ã  l'exÃ©cution et avec eux, le parallÃ©lisme et vraisemblement aussi la performance de l'application. On peut malgrÃ© tout raisonnablement espÃ©rer qu'une telle solution prÃ©senterait des performances meilleures sur une carte de type Fermi possÃ©dant jusqu'Ã  48~Ko de mÃ©moire partagÃ©e par bloc.
-
-\textit{Quick shift}, une approximation de l'algorithme mean-shift gaussien, c'est Ã  dire utilisant des masques de pondÃ©ration gaussiens, permettant d'obtenir un rÃ©sultat en une seule passe (sans itÃ©rer) et proposÃ©e initiallement dans \cite{vedaldi2008quick} a Ã©tÃ© parallÃ©lisÃ©e sur GPU par ses auteurs et dÃ©crite dans \cite{fulkerson2012really}. La recherche de performance se traduit par des approximations, en particulier on restreint les calculs de pondÃ©ration Ã  des voisinages de rayon $3\sigma$ (Ã©cart type de la gaussienne dÃ©finissant les coefficients du masque), considÃ©rant qu'au delÃ , les valeurs en sont nÃ©gligeable.
-Ensuite on construit un arbre des liens entre les pixels, mais on limite la recherche Ã  une distance maximale de $\sigma$. Par ailleurs, on diminue arbitrairement la dynamique de l'espace colomÃ©trique par 2. Enfin, la segmentation est obtenu par simple partionnnement de l'arbre selon un seuil $\tau$.
-Pour s'affranchir de la relative petite taille de la mÃ©moire partagÃ©e sans devoir pÃ¢tir de la grande latence des accÃ¨s Ã  la mÃ©moire globale de GPU, les auteurs ont ici choisi d'associer l'image et l'estimation de densitÃ© Ã  des textures et ainsi bÃ©nÃ©ficier du mÃ©canisme de cache.
-Les expÃ©rimentations ont Ã©tÃ© menÃ©es avec diffÃ©rentes valeurs de $\sigma$ et $tau$ choisies pour les rÃ©sultats visuels qu'elles induisent et permettent de segmenter une image couleur de 1~MP en environ 1~s avec $\tau=10$ et $\sigma=6$. Toutefois, des valeurs plus petites, requÃ©rant moins de calculs, permettent des temps d'exÃ©cution beaucoup plus courts. Les courbes prÃ©sentÃ©es permettent d'envisager, pour $\tau=4$ et $\sigma=2$, une rÃ©duction par 30, soit environ 33~ms. Une version amÃ©liorÃ©e rÃ©cemment, dans laquelle les positions des centres sont stockÃ©es en registres, permet selon les auteurs, de diviser encore par 2 les temps d'exÃ©cution pour atteindre une segmentation en environ 16.5~ms.
-La figure \ref{fig-quickshift-yo}, tirÃ©e de \cite{fulkerson2012really}, prÃ©sente quelques segmentations effectuÃ©es avec des valeurs diffÃ©rentes, permettant ainsi de juger des effets des variations des paramÃ¨tres $\tau$ et $\sigma$.
-
-\begin{figure}
-  \centering
-\subfigure[Image originale]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-orig.png}}\quad
-\subfigure[$\tau=10$ et $\sigma=2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s2t10.png}}\quad
-\subfigure[$\tau=10$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t10.png}}\quad
-\subfigure[$\tau=20$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t20.png}}\quad
-\caption{Segmentation d'une image couleur de 512$\times$512 pixels par l'implÃ©mentation GPU quick-shift de \cite{fulkerson2012really}.}
-\label{fig-quickshift-yo}
-\end{figure}
-
-RÃ©cemment, Xiao et Liu ont dÃ©crit dans \cite{xiao2010efficient} une implÃ©mentation de l'algorithme \textit{mean-shift} qui utilise cette fois une construction de \textit{KD-tree} (arbre binaire Ã  K dimensions) pour rÃ©duire l'espace colorimÃ©trique et effectuer rapidement les recherches des plus proches voisins. L'ensemble s'exÃ©cute sur le GPU et permet ainsi d'obtenir des rÃ©sultats beaucoup plus probants puisque les auteurs revendiquent une segmentation d'image couleur de 6.6 millions de pixels en 0.2 secondes. Malheureusement, il n'est pas dit combien de segments comprend l'image et il n'est fait rÃ©fÃ©rence qu'Ã  une seule image, dont on dÃ©duit qu'il s'agit de l'image reproduite Ã  la figure  \ref{fig-meanshift-castle} afin de montrer les diffÃ©rences avec une implÃ©mentation standard du \textit{mean-shift}.
-
-\begin{figure}
-  \centering
-\subfigure[Image originale]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift.png}}\quad
-\subfigure[Image segmentÃ©e par mean-shift standard]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-std.png}}\quad
-\subfigure[Image segmentÃ©e par mean-shift kd-tree]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-kdtree.png}}
-\caption{Segmentation d'une image couleur de 2256$\times$3008 pixels.}
-\label{fig-meanshift-castle}
-\end{figure}
-
-\subsection{Snakes et Level set}
-DÃ¨s 2003, on recense d'importants travaux liÃ©s Ã  l'imagerie mÃ©dicale mettant en \oe uvre des algorithmes \textit{level set} sur GPU. C'est le cas de \cite{lefohn2003inter,lefohn2003interactive} oÃ¹ les auteurs dÃ©crivent une solution de visualisation des coupes d'une mesure volumique rÃ©alisÃ©s par rÃ©sonnance magnÃ©tique (IRM) en exploitant pour la premiÃ¨re fois le caractÃ¨re creux du systÃ¨me d'Ã©quations Ã  rÃ©soudre, \textit{i.e.} variante narrow-band, contrairement Ã  la premiÃ¨re solution 2D prÃ©sentÃ©e dans \cite{rumpf2001level} qui implÃ©mente la version standard. En ne transfÃ©rant au GPU, pour chaque itÃ©ration, que les petits pavÃ©s de donnÃ©es actifs et en les  rangeant alors de maniÃ¨re contigue en texture pour optimiser les accÃ¨s en lecture, les auteurs sont ainsi parvenu Ã  effectuer, pour des donnÃ©es volumiques de 256$\times$256$\times$175, entre 3.5 et 70 itÃ©rations par seconde, Ã  comparer aux 50 itÃ©rations par seconde en 2D sur image de 128$^2$ pixels otenues dans \cite{rumpf2001level}. La limitation principale de cettesolution est celle des dimensions maximales admises pour une texture qui Ã©tait de 2048$^2$ pour le GPU ATI Radeon 9800 pro employÃ© (et programmÃ© en openGL, car ni openCL ni CUDA n'Ã©taient encore disponible Ã  l'Ã©poque).
-Les autres solutions GPU proposÃ©es depuis sont Ã©galement basÃ©es sur la variante \textit{narrow-band} (bande Ã©troite) des \textit{level-set} \cite{lefohn2005streaming,cates2004gist,jeong2009scalable}, mais seule \cite{jeong2009scalable} s'affranchit des transferts CPU/GPU Ã  chaque itÃ©ration pour dÃ©terminer et transfÃ©rer les pavÃ©s actifs. La solution retenue est d'employer les opÃ©rations atomiques pour assurer l'accÃ¨s exclusif Ã  la liste des pavÃ©s en mÃ©moire GPU. Cela permet de descendre Ã  3~ms par itÃ©ration pour une image de 512$^2$ pixels.
-
-La plus performante des implÃ©mentations Ã  ce jour est celle dÃ©crite dans \cite{Roberts:2010:WGA:1921479.1921499} qui parvient Ã  des itÃ©rations dont la durÃ©e varie, sur GTX280,  de 1.8 Ã  6.5~ms pour des donnÃ©es volumiques de 256$^3$ pixels issues d'examen IRM, pour une moyenne de 3.2~ms sur les 2200 itÃ©rations de l'exemple fourni (cerveau en 7~s, Figure \ref{fig-l7-brain}). Une optimisation poussÃ©e y a Ã©tÃ© effectuÃ©e pour rendre l'algorithme efficace, en particulier au travers de la refonte du code responsable de la dÃ©termination des pavÃ©s actifs. Il parvient cette fois Ã  dÃ©terminer l'ensemble minimal de pavÃ©s actifs et Ã  rendre cette dÃ©termination efficace sur le GPU en gÃ©rant parallÃ¨lement plusieurs tampons, chacun associÃ© Ã  une direction particuliÃ¨re en 6-connexitÃ©. Une Ã©tape de rÃ©solution des doublons est ensuite effectuÃ©e avant de les compacter de maniÃ¨re contigue comme cele Ã©tait dÃ©jÃ  fait dans \cite{lefohn2003inter}. Toutefois, tenir Ã  jour cette liste de pavÃ©s reprÃ©sente encore 77\% du temps de calcul aprÃ¨s cette optimisation.
-%TODO dire qu'il n'utilise pas de shmem !
-Ce faisant, le nombre cumulÃ© total de pavÃ©s ainsi traitÃ©s lors des 2200 itÃ©rations de la segmentation der l'image d'exemple s'Ã©lÃ¨ve Ã  294 millions Ã  comparer aux 4877 millions traitÃ©s par l'algorithme \textit{narrow-band} standard. Il est Ã  noter que la durÃ©e d'exÃ©cution d'une itÃ©ration dans cette variante dÃ©pend plus fortement de la proportion de pavÃ©s actifs que pour \textit{narrow-band} standard. Les deux courbes sont globalement affines et se croisent pour une proportion de pavÃ©s actifs proche de 10\%.
-Cela peut reprÃ©senter une piste pour une optimisation supplÃ©mentaire qui ne semble pas su justifier avec l'image et l'initialisation dont les performances sont dÃ©taillÃ©es, mais qui pourrait l'Ãªtre dans d'autres conditions, comme peut le suggÃ©rer le temps de segmentation de 16~s nÃ©cessaire pour l'image des reins (Figure \ref{fig-l7-reins}) et de l'aorte, malgrÃ© des dimensions comparables.
-
-\begin{figure}
-  \centering
-\subfigure[Cerveau 256$\times$256$\times$256 en 7~s]{\label{fig-l7-brain}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-brain7s.png}}\quad
-\subfigure[Reins et aorte, 256$\times$256$\times$272 en 16~s]{\label{fig-l7-reins}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-reins16s.png}}
-\caption{Segmentation d'images issues d'examens IRM par la mÃ©thode des level set Ã  bande Ã©troite.}
-\label{fig-meanshift-castle}
-\end{figure}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 
-
-
-
-   
-      
-
-
-
-
-
-
-
-
-
-
-
-
- 
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+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.    
+       
