X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/337bc2017ae0e8ef623077988ea7998f48b3c442..5468e1e9820093c08ad166ddd847123338479b2c:/THESE/Chapters/chapter2/chapter2.tex?ds=inline

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index 53201d6..2e2e701 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -89,13 +89,13 @@ La figure \ref{fig-histo-cochon} illustre le traitement typique de l'histogramme
 
 \begin{figure}
   \centering
-  \subfigure[Image initiale comportant deux zones : le fond et le cochon (la cible)]{\label{fig-histo-cochon-a} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/cochon256.png}}\quad
-  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-b} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/histo-cochon256.png}}\quad
-  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  101 aprÃ¨s 4 itÃ©rations.]{\label{fig-histo-cochon-c} \includegraphics[width=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/cochon256-seghisto-101-255.png}}\\
-\subfigure[Image initiale bruitÃ©e]{\label{fig-histo-cochon-d} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/cochon256-sig25.png}}\quad
-  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-e} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/histo-cochon256-sig25.png}}\quad
-  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  99 aprÃ¨s 5 itÃ©rations.]{\label{fig-histo-cochon-f} \includegraphics[height=3cm]{/home/zulu/Documents/THESE/codes/seg_histogramme/cochon256-sig25-seghisto-99-255.png}}
-  \caption{Segmentation par analyse simple d'histogramme. Colonne de gauche : image d'entrÃ©e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : rÃ©sultat de la segmentation.}
+  \subfigure[Image initiale comportant deux zones : le fond et le cochon (la cible)]{\label{fig-histo-cochon-a} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256.png}}\quad
+  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-b} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256.png}}\quad
+  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  101 aprÃ¨s 4 itÃ©rations.]{\label{fig-histo-cochon-c} \includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-seghisto-101-255.png}}\\
+\subfigure[Image initiale bruitÃ©e]{\label{fig-histo-cochon-d} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256-sig25.png}}\quad
+  \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-e} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256-sig25.png}}\quad
+  \subfigure[Image binaire reprÃ©sentant la segmentation. Seuil estimÃ© Ã  99 aprÃ¨s 5 itÃ©rations.]{\label{fig-histo-cochon-f} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-sig25-seghisto-99-255.png}}
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entrÃ©e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : rÃ©sultat de la segmentation.}
 \label{fig-histo-cochon}
 \end{figure}
  
@@ -122,11 +122,21 @@ L'essentiel de la problÃ©matique rÃ©side donc dans la mÃ©trique retenue pour Ã©v
 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 d'affinitÃ©s qui traduit les liens entre les segments.
+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.
 On peut citer, par ordre chronologique, les mÃ©thodes reposant sur le \textit{graphe optimal} de Wu et Leahy \ref{wulealy_1993} et plus rÃ©cemment \ref{cf_notes x5}. Le principal point faible de ces techniques rÃ©side essentiellement dans la difficultÃ©  Ã  trouver un compromis acceptable entre identification de structures globales et prÃ©servation des Ã©lÃ©ments de dÃ©tails. Cela se traduit dans la pratique par un ensemble de paramÃ¨tres Ã  rÃ©gler pour chaque type de segmentation Ã  effectuer.
 Cependant, elles sont employÃ©es dans les algorithmes de haut niveau les plus rÃ©cents, comme nous le verrons plus loin.
-La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \ref{sm-ncuts}. Quatre paramÃ¨tres sont Ã  fixer pour rÃ©aliser la segmentation, ils correspondent respectivement aux facteurs de forme de la matrice d'affinitÃ©s en termes de distance et de niveau de gris (2 paramÃ¨tres), Ã  la surface minimale admise pour un segment ainsi qu'au seuil de sÃ©gmentation des graphes. Le choix des valeurs pour les paramÃ¨tres n'est pas immÃ©diat et la figure illustre bien la difficultÃ© de trouver un compromis acceptable. Enfin, les temps d'exÃ©cutions peuvent devenir trÃ¨s rapidement prohibitifs dÃ¨s lors que l'on utilise des facteurs de forme Ã©tendus.
-  
+La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \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[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_2seg.png}}\quad
+  \subfigure[$s = 3$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_3seg.png}}\\
+  \subfigure[$s = 4$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_4seg.png}}\quad
+  \subfigure[$s = 5$]{\includegraphics[height=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}
+%TODO 
+%donner l'expression gÃ©nÃ©rale de la matrice de similaritÃ© ?
     
 \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. 
@@ -143,13 +153,33 @@ Un autre est d'Ãªtre trÃ¨s dÃ©pendant du choix des $k$ Ã©lÃ©ments initiaux, en n
 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[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_2seg.png}}\quad
+  \subfigure[$s = 3$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_3seg.png}}\\
+  \subfigure[$s = 4$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_4seg.png}}\quad
+  \subfigure[$s = 5$]{\includegraphics[height=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[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r100m100.png}}\quad
+  \subfigure[$r=50 \Rightarrow s = 3$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r50m100.png}}\\
+\subfigure[$r=35 \Rightarrow s = 4$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r35m100.png}}\quad
+  \subfigure[$r=25 \Rightarrow s = 5$]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r25m100.png}}  
+  \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme \textit{mean-shift} pour un rayon de voisinage $r$ de 100, 50, 35 et 25 pixels permettant d'obtenir un nombre $s$ de segments variant respectivement de 2 Ã  5. Le volume minimal admis pour un segment est fixÃ© Ã  100 pixels. Chaque couleur est associÃ©e Ã  un segment. Les couleurs sont choisies pour une meilleure visualisation des diffÃ©rents segments.}
+\label{fig-meanshift-cochon}
+\end{figure}
 
-Il est Ã  noter que les segmentations basÃ©es sur des algorithmes de \textit{clustering} nÃ©cessitent une phase supplÃ©mentaire de gÃ©nÃ©ration des frontiÃ¨res inter-segments et d'affectation de la valeur de chaque segment aux Ã©lÃ©ments qui le composent. 
+Il est Ã  noter que les segmentations basÃ©es sur des algorithmes de \textit{clustering} comme ceux que l'on vient de prÃ©senter nÃ©cessitent le plus souvent une phase supplÃ©mentaire de gÃ©nÃ©ration des frontiÃ¨res inter-segments et d'affectation de la valeur de chaque segment aux Ã©lÃ©ments qui le composent. 
 Par ailleurs, dans les deux cas du \textit{k-means} et du \textit{mean-shift}, chaque itÃ©ration gÃ©nÃ¨re une rÃ©duction de la variance (due au moyennage) et on peut donc rapprocher ces techniques de celles de rÃ©duction de bruit par minimisation de variance.
 
 \subsection{Les contours actifs, ou \textit{snakes}}
@@ -159,15 +189,29 @@ Le principe gÃ©nÃ©ral est de superposer une courbe paramÃ©trique Ã  l'image, le
 \item l'Ã©nergie interne de la courbe, fonction de son allongement de sa courbure.
 \item l'Ã©nergie externe liÃ©e Ã  l'image, fonction de la proximitÃ© de la courbe avec les zones de fort gradient et Ã©ventuellement une contrainte fixÃ©e par l'utilisateur comme des points imposÃ©s par exemple.
 \end{itemize}
-Ici encore, la rÃ©solution du problÃ¨me revient Ã  minimiser une fonction d'Ã©nergie sous contrainte et les diverses techniques de rÃ©solution numÃ©rique peuvent s'appliquer comme pour les autres classes d'algorithmes itÃ©ratifs prÃ©sentÃ©s prÃ©cÃ©demment. 
+%TODO
+% formule gÃ©nÃ©rale
+Ici encore, la rÃ©solution du problÃ¨me revient Ã  minimiser une fonction d'Ã©nergie sous contrainte et les diverses techniques de rÃ©solution numÃ©rique peuvent s'appliquer comme pour les autres classes d'algorithmes itÃ©ratifs prÃ©sentÃ©s prÃ©cÃ©demment, avec ici encore, un nombre de paramÃ¨tres Ã  rÃ©gler assez important.
 
 Dans sa version originale proposÃ©e par Kass \textit{et al.} en 1988 \ref{snake_kass_1988}, l'algorithme dit du \textit{snake} prÃ©sente l'intÃ©rÃªt de converger en un nombre d'itÃ©rations assez rÃ©duit et permet de suivre naturellement un \textit{cible} en mouvement aprÃ¨s une convergence initiale Ã  une position donnÃ©e, chaque position de convergence fournissant une position initiale pertinente pour la position suivante.
-Toutefois, il se montre sensible Ã  l'Ã©tat initial de la courbe et requiert souvent de celle-ci qu'elle soit assez proche de l'objet Ã  ``entourer'', sous peine de se verrouiller dans un minimum local. 
+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 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 aprÃ¨s chacune des trois premiÃ¨res itÃ©rations]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it3.png}}\quad
+\subfigure[L'Ã©tat  du contour aprÃ¨s la septiÃ¨me itÃ©ration]{\includegraphics[height=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[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it10.png}}\quad
+\subfigure[L'Ã©tat du contour aprÃ¨s la centiÃ¨me itÃ©ration. C'est le contour final.]{\includegraphics[height=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 viscositÃ©, de raideur et d'attraction ont Ã©tÃ© fixÃ©s respectivement aux valeurs 5, 0, 0.1 et 5. }
+\label{fig-snake-tradi-cochon}
+\end{figure} 
+
 Il est cependant possible de contrÃ´ler la finesse de la segmentation mais au prix de temps de calculs qui peuvent devenir trÃ¨s longs.
-Les variantes les plus intÃ©ressantes sont :
+Parmi les variantes Ã©laborÃ©es qui tentent de pallier ces dÃ©fauts, les plus intÃ©ressantes sont :
 \begin{itemize}
 \item le \textit{balloon snake}, conÃ§u pour remÃ©dier au mauvais suivi des concavitÃ©s en introduisant une force supplÃ©mentaire de pression tendant Ã  \textit{gonfler} le snake jusqu'Ã  ce qu'il rencontre un contour suffisamment marquÃ©. Cela suppose toutefois que l'Ã©tat initial de la courbe la situe entiÃ¨rement Ã  l'intÃ©rieur de la zone Ã  segmenter et est surtout employÃ© dans des applications semi-automatiques oÃ¹ l'utilisateur dÃ©finit au moins une position et une taille initiales pour la courbe. 
 \item le \textit{snake} GVF (pour Gradient Vector Flow), dont le but est de permettre qu'une initialisation lointaine de la courbe ne pÃ©nalise pas la segmentation. Une carte des lignes de gradient est Ã©tablie sur tout le domaine de l'image et sert Ã  intÃ©grer une force supplÃ©mentaire dans l'Ã©nergie totale, qui attire la courbe vers la zone de fort gradient.
@@ -177,12 +221,13 @@ AprÃ¨s la formulation initiale de Osher et Sethian en 1988 \ref{level_sets_osher
 \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} (que l'on aurait rangÃ©e avec les mean-shift) pour regrouper les segments. 
+Aujourd'hui, les algorithmes de segmentation les plus performants en terme de qualitÃ© emploient des techniques qui tentent de tirer le meilleur parti de plusieurs des mÃ©thodes ``historiques'' dÃ©crites prÃ©cÃ©demment.
+Le meilleur exemple, et le seul que nous citerons, est le dÃ©tecteur de contour et l'algorithme de segmentation associÃ© proposÃ© par Arbelaez \textit{et al.} en 2010 \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
 
 
 
