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

diff --git a/THESE/Chapters/chapter2/chapter2d.tex b/THESE/Chapters/chapter2/chapter2d.tex
index 96a530b..3394929 100644
--- a/THESE/Chapters/chapter2/chapter2d.tex
+++ b/THESE/Chapters/chapter2/chapter2d.tex
@@ -1,4 +1,4 @@
-\section{Les techniques de segmentation}
+\section{Introduction}
 La segmentation reprÃ©sente un enjeu particuliÃ¨rement important dans le domaine du traitement d'image et a ainsi 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 diagnostic 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, nous proposons la formulation gÃ©nÃ©rique suivante :\\
@@ -7,9 +7,10 @@ Le caractÃ¨re \textit{homogÃ¨ne} s'entend au sens d'un critÃ¨re prÃ©-Ã©tabli, ad
 
 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 (les segments), 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Ã©es sur l'un ou l'autre de ces Ã©lÃ©ments relÃ¨vent d'analyses diffÃ©rentes.
+Les Ã©lÃ©ments constitutifs de la segmentation sont soit des rÃ©gions (les segments), soit des contours. Les deux notions sont complÃ©mentaires Ã©tant donnÃ© que les contours dÃ©limitent des rÃ©gions\footnote{Nous excluons ici les contours non-fermÃ©s qui peuvent Ãªtre obtenus Ã  l'aide d'un simple dÃ©tecteur de bords.}, mais les techniques de calcul basÃ©es sur l'un ou l'autre de ces Ã©lÃ©ments relÃ¨vent d'analyses diffÃ©rentes.
 
-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 thÃ©orie du \textit{gestalt} \cite{humphrey1924psychology} oÃ¹ l'on considÃ¨re que la perception conceptuelle s'Ã©labore au travers de regroupements visuels d'Ã©lÃ©ments.
+\section{Les techniques de segmentation orientÃ©es rÃ©gions}
+Les algorithmes de cette classe 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 thÃ©orie du \textit{gestalt} \cite{humphrey1924psychology} oÃ¹ l'on considÃ¨re que la perception conceptuelle s'Ã©labore au travers de regroupements visuels d'Ã©lÃ©ments.
 
 La plupart des approches proposÃ©es jusqu'Ã  trÃ¨s rÃ©cemment consistent Ã  minimiser une fonction d'Ã©nergie qui n'a pas de solution formelle et que l'on rÃ©sout donc Ã  l'aide de techniques numÃ©riques souvent itÃ©ratives.   
 
@@ -20,14 +21,14 @@ DiffÃ©rents critÃ¨res peuvent Ãªtre appliquÃ©s pour cette analyse, visant par ex
 MalgrÃ© la multitude de variantes proposÃ©es, ces mÃ©thodes demeurent  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 applications 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}. 
+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 de la peluche (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}. 
 Le principe mis en \oe uvre est de fixer arbitrairement une valeur initiale au seuil (ici 128), puis de calculer les \og poids \fg{} respectifs des valeurs situÃ©es au-dessus et en-dessous de ce seuil (ligne 6). Cette Ã©valuation de la rÃ©partition Ã©nergÃ©tique permet d'ajuster la valeur du seuil (ligne 8), puis de recommencer jusqu'Ã  convergence, lorsque l'Ã©cart entre deux valeurs successives du seuil devient infÃ©rieur Ã  une limite fixÃ©e Ã  l'avance ($\epsilon$, ligne 9).       
 
 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 : les rÃ©gions identifiÃ©es prÃ©sentent des discontinuitÃ©s et dans le cas de l'image bruitÃ©e, quantitÃ© de pixels orphelins subsistent en quantitÃ©. Cette technique nÃ©cessiterait une Ã©tape supplÃ©mentaire pour obtenir 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[Image initiale comportant deux zones : le fond et la peluche (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
@@ -53,8 +54,8 @@ $\epsilon \leftarrow 1$ \;
 } 
 \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. Il 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 Ã©tant 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.
+\subsection{Partitionnement de graphe\label{seggraph}}
+Un autre formalisme qui a gÃ©nÃ©rÃ© une vaste classe d'algorithmes de segmentation est celui des graphes. Il repose sur l'idÃ©e que les rÃ©gions de l'image sont reprÃ©sentÃ©es par les n\oe uds d'un graphe, alors que les liens traduisent les relations de voisinage existant entre les rÃ©gions, l'idÃ©e de base Ã©tant 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.
 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.
@@ -74,7 +75,7 @@ On construit Ã©galement la matrice de connectivitÃ© $D$, diagonale et dont les 
 \[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 \]
+\[\left(D-W\right)Y=\lambda DY \]
 Certains algorithmes proposÃ©s plus rÃ©cemment s'inscrivent dans cette veine \cite{wang2001image,wang2003image,felzenszwalb2004efficient,shi2000normalized}, avec comme principal point faible, une 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 de sujets dans les images naturelles, mais requiert de prÃ©dÃ©terminer le nombre de segments. Les images de la figure reprÃ©sentent les rÃ©sultats obtenus avec un nombre de segments variant de 2 Ã  5 et montrent qu'il est difficile de trouver un compromis acceptable. De plus, les temps d'exÃ©cution peuvent devenir trÃ¨s rapidement prohibitifs, mÃªme avec des implÃ©mentations plus optimisÃ©es. 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) 
@@ -93,9 +94,9 @@ Ce procÃ©dÃ© est mis en \oe uvre avec de bons rÃ©sultats dans plusieurs algorith
 
 \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}$ 
+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 $K$ de segments $\Omega_i$ et leur contenu, de sorte Ã  minimiser l'expression 
+\[\sum_{i\in[1..K]}\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..K]}\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.}
@@ -105,15 +106,15 @@ 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 son temps d'exÃ©cution rapide, 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 \og centre \fg{} 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.
+Des solutions ont aussi Ã©tÃ© apportÃ©es pour l'estimation de $K$ en employant, par exemple, un critÃ¨re BIC (Bayesian Information Criterion) pour choisir la meilleure valeur de $K$ dans un intervalle donnÃ© \cite{pelleg2000x}.
+Ã titre d'illustration et de comparaison, l'image de la peluche 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 $K=2$ Ã  $K=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.}
+  \subfigure[$K = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_2seg.png}}
+  \subfigure[$K = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_3seg.png}}
+  \subfigure[$K = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_4seg.png}}
+  \subfigure[$K = 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 $K$ 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}
 
@@ -125,22 +126,22 @@ Comaniciu et Peer en ont alors Ã©tendu l'Ã©tude et proposÃ© une application Ã  l
 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 nombres de segments identiques Ã  ceux des figures prÃ©cÃ©dentes (de 2 Ã  5), le volume minimal admis pour un segment Ã©tant 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.}
+  \subfigure[$r=100 \Rightarrow K = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r100m100.png}}
+  \subfigure[$r=50 \Rightarrow K = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r50m100.png}}
+\subfigure[$r=35 \Rightarrow K = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r35m100.png}}
+  \subfigure[$r=25 \Rightarrow K = 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 $K$ 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 snakes}
+\section{Les techniques de segmentation par contours actifs, ou 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 interne $E_{int}$ de la courbe, fonction de son allongement de sa courbure et qui vise Ã  rÃ©gulariser les courbes obtenues.
 \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 
@@ -179,7 +180,7 @@ Parmi les variantes Ã©laborÃ©es qui tentent de pallier ces dÃ©fauts, les plus in
 \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'Ã©lÃ©vation nulle d'une surface 3D soumise Ã  un champ de force. 
 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 se sont avÃ©rÃ©s trÃ¨s pÃ©nalisants.
 AprÃ¨s la formulation initiale de Osher et Sethian en 1988 \cite{osher1988fronts}, plusieurs faÃ§ons de rÃ©duire le coÃ»t du calcul ont Ã©tÃ© formulÃ©es, dont les plus importantes restent la technique dite \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 celle du \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{snake-formulation} en donnera une description dÃ©taillÃ©e. 
+\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 les auteurs de \cite{ChesnaudRB99} 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. Des travaux ultÃ©rieurs leur ont permis d'Ã©tendre la portÃ©e de leur algorithme Ã  la segmentation multirÃ©gions \cite{GallandBR03,GermainR01}, puis de proposer des variantes non paramÃ©triques ne nÃ©cessitant aucune connaissance \textit{a priori} sur le bruit. La plus rÃ©cente de ces versions prÃ©sente des temps de traitement trÃ¨s courts, infÃ©rieurs Ã  10~ms pour l'image de la peluche en 256$\times$256 pixels \cite{galland2005minimal,5767240}. La section \ref{snake-formulation} donnera une description dÃ©taillÃ©e de la variante de \cite{ChesnaudRB99} qui a servi de base Ã  nos travaux. 
 \end{itemize} 
 \subsection{MÃ©thodes hybrides}
 Aujourd'hui, les algorithmes de segmentation les plus performants en termes de qualitÃ© emploient des techniques qui tentent de tirer le meilleur parti de plusieurs des mÃ©thodes \og historiques \fg{} dÃ©crites prÃ©cÃ©demment.
@@ -275,16 +276,16 @@ Si l'on considÃ¨re que malgrÃ© les stratÃ©gies adoptÃ©es, tenir Ã  jour cette li
 \label{fig-l7-narrow}
 \end{figure}
 
-Les algorithmes de type \textit{snake}, trÃ¨s coÃ»teux en temps de calcul, pouvaient prÃ©tendre Ã  bÃ©nÃ©ficier largement de la technologie des GPU pour amÃ©liorer leurs performances, mais seule la variante paramÃ©trique GVF Ã  Ã©tÃ© vÃ©ritablement implÃ©mentÃ©e de maniÃ¨re spÃ©cifique et efficace \cite{snakegvf06, bauer2009segmentation, li2011robust, snakegvfopencl12}. Les variantes de type gÃ©omÃ©trique restent Ã  ce jour sans implÃ©mentation GPU, principalement en raison de l'irrÃ©gularitÃ© des motifs d'accÃ¨s Ã  la mÃ©moire.
+Les algorithmes de type \textit{snake}, trÃ¨s coÃ»teux en temps de calcul, pouvaient prÃ©tendre Ã  bÃ©nÃ©ficier largement de la technologie des GPU pour amÃ©liorer leurs performances, mais seule la variante paramÃ©trique GVF Ã  Ã©tÃ© vÃ©ritablement implÃ©mentÃ©e de maniÃ¨re spÃ©cifique et efficace \cite{snakegvf06, bauer2009segmentation, li2011robust, snakegvfopencl12}. Les variantes de type polygonal restent Ã  ce jour sans implÃ©mentation GPU, principalement en raison de l'irrÃ©gularitÃ© des motifs d'accÃ¨s Ã  la mÃ©moire.
 
-Parmi les premiÃ¨res solutions dÃ©crites, \cite{snakegvf06} propose une implÃ©mentation rÃ©alisÃ©e en openGL, oÃ¹ les donnÃ©es de gradient sont compactÃ©es en texture RVBA de maniÃ¨re Ã  s'affranchir du format 16 bits de la reprÃ©sentation : les deux premiers canaux R et V contiennent les valeurs reprÃ©sentant respectivement les gradients selon $dx$ et $dy$ sous une forme codÃ©e par la valeur des 2 autres canaux. 
+Parmi les premiÃ¨res solutions dÃ©crites, \cite{snakegvf06} propose une implÃ©mentation rÃ©alisÃ©e en openGL, oÃ¹ les donnÃ©es de gradient sont compactÃ©es en texture Ã  quatre canaux (R,V,B,A) de maniÃ¨re Ã  s'affranchir du format 16 bits de la reprÃ©sentation : les deux premiers canaux R et V contiennent les valeurs reprÃ©sentant respectivement les gradients selon $dx$ et $dy$ sous une forme codÃ©e selon les valeur des 2 autres canaux B et A.
 Par ailleurs, une approximation du systÃ¨me linÃ©aire Ã  rÃ©soudre est proposÃ©e afin de donner une structure bande symÃ©trique Ã  la matrice Ã  inverser, ce qui amÃ©liore considÃ©rablement l'efficacitÃ© des accÃ¨s aux donnÃ©es au travers du cache.
 
 \begin{figure}
   \centering
   \subfigure[Contour initial]{\label{fig-epaule-init}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-init-t.png}}\quad
   \subfigure[Contour final]{\label{fig-epaule-fin}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-fin-t.png}}
-\caption{Segmentation d'une image d'Ã©paule en 1024$^2$ pixels issue d'un examen IRM par l'implÃ©mentation du snake GVF de \cite{snakegvf06}. Le contour est reprÃ©sentÃ© en rouge et le contour final est obtenu en 11~s. Le tracÃ© initial du contour a Ã©tÃ© artificiellement Ã©paissi pour le rendre visible Ã  l'Ã©chelle de l'impression.}
+\caption{Segmentation d'une image d'Ã©paule en 1024$\times$1024 pixels issue d'un examen IRM par l'implÃ©mentation du snake GVF de \cite{snakegvf06}. Le contour est reprÃ©sentÃ© en rouge et son Ã©tat final est obtenu en 11~s. Le tracÃ© initial du contour a Ã©tÃ© artificiellement Ã©paissi pour le rendre visible Ã  l'Ã©chelle de l'impression.}
 \label{fig-snakegvf}
 \end{figure}
 
