modif finale lnivs + keywords

[these_gilles.git] / THESE / Chapters / chapter2 / chapter2d.tex

diff --git a/THESE/Chapters/chapter2/chapter2d.tex b/THESE/Chapters/chapter2/chapter2d.tex
index 96a530b88fc5abbfa836aebbd13adcd940b6ffc3..339492938a9cc8d67d02cf58d2d0e3110b81c5b5 100644 (file)
--- 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 :\\
 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.
 
 
 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.   
 
 
 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. 
 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
 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
   \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}
 
 } 
 \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.
 
 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 
 \[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) 
 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. 
 
 \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.}
 
 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. 
 
 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
 \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}
 
 \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
 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.
 
 \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}
 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 
 \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{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.
 \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}
 
 \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}}
 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}
 
 \label{fig-snakegvf}
 \end{figure}