final rapporteurs ?

[these_gilles.git] / THESE / Chapters / chapter3 / chapter3.tex

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index bae9ff9f98f5bf5048bd8e498caa75e30c63a344..52b00b7b5b0ce1ae0389c002a9c19c2d82eb25dc 100644 (file)
--- a/THESE/Chapters/chapter3/chapter3.tex
+++ b/THESE/Chapters/chapter3/chapter3.tex
@@ -1,10 +1,10 @@
 \section{Introduction}
 La principale difficulté soulevée par l'emploi d'algorithmes de type \textit{snake} orientés contour est le choix de la fonction d'énergie externe et la détermination de la nature des images auxquelles elle convient. 
 Dans l'approche orientée régions, les deux régions que sont l'extérieur et l'intérieur du contour (cas mono cible) sont prises en compte dans l'estimation de la forme du contour ;  cela permet d'extraire des formes dans des images où les contours de la cible sont mal définis, en raison d'un fort niveau de bruit par exemple.
 \section{Introduction}
 La principale difficulté soulevée par l'emploi d'algorithmes de type \textit{snake} orientés contour est le choix de la fonction d'énergie externe et la détermination de la nature des images auxquelles elle convient. 
 Dans l'approche orientée régions, les deux régions que sont l'extérieur et l'intérieur du contour (cas mono cible) sont prises en compte dans l'estimation de la forme du contour ;  cela permet d'extraire des formes dans des images où les contours de la cible sont mal définis, en raison d'un fort niveau de bruit par exemple.

-Les algorithmes découlant de cette approche n'ont fait l'objet, à notre connaissance, d'aucune parallèlisation sur GPU, malgré le grand intérêt qu'elles revêtent dans l'interprétation d'images fortement bruitées ( RADAR, médicales,\dots ) et le besoin de réduire suffisamment les temps de traiement pour permettre l'interactivité. 
+Les algorithmes découlant de cette approche n'ont fait l'objet, à notre connaissance, d'aucune parallèlisation sur GPU, malgré le grand intérêt qu'elles revêtent dans l'interprétation d'images fortement bruitées ( imagerie ultrasonore, RADAR ) et le besoin de réduire suffisamment les temps de traitement pour permettre l'interactivité. 

 
 Nous proposons dans la suite de ce chapitre de commencer par détailler l'algorithme séquentiel que nous avons pris comme référence, puis d'en présenter la version parallèle pour GPU que nous avons conçue.
 
 Nous proposons dans la suite de ce chapitre de commencer par détailler l'algorithme séquentiel que nous avons pris comme référence, puis d'en présenter la version parallèle pour GPU que nous avons conçue.

-L'algorithme a été décrit et proposé initialement en 1999 par Chesnaud \textit{et al.} dans \cite{ChesnaudRB99}. L'implémentation que les auteurs ont développée a continué d'être améliorée jusqu'à aujourd'hui et est employée comme brique élémentaire dans des algorithmes plus complexes. La version qui sert de référence ici est une implémentation séquentielle optimisée qui met à profit les capacités de parallélisme des CPU actuels en employant le jeu d'instruction SSE2 des microprocesseurs. La description que nous en faisons dans les lignes qui suivent est très largement inspirée de \cite{ChesnaudRB99} à la différence que nous n'implémentons pas les critères de régularisation du contour ni de minimisation de la longueur de description pour nous focaliser sur la déformation du contour et sa convergence. 
+L'algorithme a été décrit et proposé initialement en 1999 par Chesnaud \textit{et al.} dans \cite{ChesnaudRB99}. L'implémentation que les auteurs ont développée a continué d'être améliorée jusqu'à aujourd'hui et est employée comme brique élémentaire dans des algorithmes plus complexes. La version qui sert de référence ici est une implémentation séquentielle optimisée et dont nous faisons ici une description très largement inspirée de \cite{ChesnaudRB99} à la différence que nous n'implémentons pas les critères de régularisation du contour ni de minimisation de la longueur de description pour nous focaliser sur la déformation du contour et sa convergence. 

 
 \section{Présentation de l'algorithme}
 \subsection{Formulation}
 
 \section{Présentation de l'algorithme}
 \subsection{Formulation}


@@ -96,7 +96,7 @@ où $C(i,j)$ est un coefficient lié à la direction du contour au point $(i,j)$
 \end{equation}
 
 La valeur de $C(i,j)$ est déterminée pour chaque pixel d'indice $l$ du contour en considérant les pixels d'indices $l-1$ et $l+1$ qui définissent les deux vecteurs $f_{in}$ et $f_{out}$ et leur code selon le codage de Freeman, comme l'illustre la figure \ref{fig-freeman}. La table \ref{tab-freeman} donne les valeurs de $C(i,j)$ selon les valeurs des codes de Freeman des vecteurs $f_{in}$ et $f_{out}$.
 \end{equation}
 
 La valeur de $C(i,j)$ est déterminée pour chaque pixel d'indice $l$ du contour en considérant les pixels d'indices $l-1$ et $l+1$ qui définissent les deux vecteurs $f_{in}$ et $f_{out}$ et leur code selon le codage de Freeman, comme l'illustre la figure \ref{fig-freeman}. La table \ref{tab-freeman} donne les valeurs de $C(i,j)$ selon les valeurs des codes de Freeman des vecteurs $f_{in}$ et $f_{out}$.

-Il faut noter que les valeurs dans la table \ref{tab-freeman} diffèrent de celles proposées initialement dans \cite{ChesnaudRB99}. Cette modification a été proposée pour permettre de s'adapter à la  segmentation multi-cibles. 
+Il faut noter que les valeurs dans la table \ref{tab-freeman} diffèrent de celles proposées initialement dans \cite{ChesnaudRB99}. Cette modification a été proposée pour permettre de s'adapter à la  segmentation multi-cibles \cite{GallandBR03}. 

 \begin{figure}[htb]
   \centering
   \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/codage-freeman.png}
 \begin{figure}[htb]
   \centering
   \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/codage-freeman.png}


@@ -122,17 +122,17 @@ Il faut noter que les valeurs dans la table \ref{tab-freeman} diffèrent de cell
       7     &0&0&0&0&0&-1&-1&-1\\
       \bottomrule
 \end{tabular}
       7     &0&0&0&0&0&-1&-1&-1\\
       \bottomrule
 \end{tabular}

-   \caption{Valeur du coefficient $C(i,j)$ en fonction des valeurs des codes de Freeman des vecteurs $f_{in}$ et $f_{out}$.}
+   \caption{Valeur du coefficient $C(i,j)$ en fonction des valeurs des codes de Freeman des vecteurs $f_{in}$ et $f_{out}$ \cite{GallandBR03}.}

       \label{tab-freeman}
 \end{table}
 
 L'intérêt de cette transformation est majeur :
 \begin{itemize}
 \item La sommation en deux dimensions sur la région $\Omega_t$ est ainsi réduite à une sommation à une dimension sur le contour $\Gamma$.
       \label{tab-freeman}
 \end{table}
 
 L'intérêt de cette transformation est majeur :
 \begin{itemize}
 \item La sommation en deux dimensions sur la région $\Omega_t$ est ainsi réduite à une sommation à une dimension sur le contour $\Gamma$.

-\item Les valeurs $T_g(i,j)$ peuvent être calculées préalablement à la phase de segmentation proprement dite. Pour le cas gaussien qui nous intéresse, cela revient à pré-calculer les trois images \textit{cumulées} $S_1$, $S_x$ et $S_{x^2}$ définies par
+\item Les valeurs $T_g(i,j)$ peuvent être calculées préalablement à la phase de segmentation proprement dite. Pour le cas gaussien qui nous intéresse, cela revient à pré-calculer les trois images \textit{cumulées} $S_1$, $S_I$ et $S_{I^2}$ définies par

   \begin{alignat}{4}
     \label{eq-img-cumul}
   \begin{alignat}{4}
     \label{eq-img-cumul}

-    S_1(i,j) &= \sum_{x=0}^jx & \quad \text{,}\quad S_x(i,j) &= \sum_{x=0}^jv(i,x) & \quad \text{et}&\quad & S_{x^2}(i,j) &= \sum_{x=0}^jv(i,x)^2 
+    S_1(i,j) &= \sum_{x=0}^jx & \quad \text{,}\quad S_I(i,j) &= \sum_{x=0}^jv(i,x) & \quad \text{et}&\quad & S_{I^2}(i,j) &= \sum_{x=0}^jv(i,x)^2 

   \end{alignat}
 \item Les valeurs du coefficient $C(i,j)$ se calculent très facilement durant la génération du contour $\Gamma$.
 \end{itemize}
   \end{alignat}
 \item Les valeurs du coefficient $C(i,j)$ se calculent très facilement durant la génération du contour $\Gamma$.
 \end{itemize}


@@ -167,24 +167,24 @@ Un des inconvénients des algorithmes de type \textit{snake} est l'influence du
 \small
 \label{algo-snake-cpu2}
    Lire l'image $\bar{v}$\;
 \small
 \label{algo-snake-cpu2}
    Lire l'image $\bar{v}$\;

-   Calculer les images cumulées $S_1$, $S_x$ $S_{x^2}$ \nllabel{li-img-cumul}\tcc*[r]{en parallèle via SSE2} 
+   Calculer les images cumulées $S_1$, $S_I$ $S_{I^2}$ \nllabel{li-img-cumul}\tcc*[r]{en parallèle via SSE2} 

    $n \leftarrow 0$ \tcc*[r]{indice de boucle niveau contour}
    $N_n \leftarrow 4$ \tcc*[r]{nombre de n\oe uds}
    $\Gamma \leftarrow \{\Gamma_0,\Gamma_1,\Gamma_2,\Gamma_3\} $\;
    $d \leftarrow d_{max}$ \tcc*[r]{pas de déplacement des n\oe uds}
    $l_{min} = 32$ \tcc*[r]{longueur mini des segments sécables}
    $\Gamma_i \leftarrow \Gamma_0$ \tcc*[r]{sommet courant}
    $n \leftarrow 0$ \tcc*[r]{indice de boucle niveau contour}
    $N_n \leftarrow 4$ \tcc*[r]{nombre de n\oe uds}
    $\Gamma \leftarrow \{\Gamma_0,\Gamma_1,\Gamma_2,\Gamma_3\} $\;
    $d \leftarrow d_{max}$ \tcc*[r]{pas de déplacement des n\oe uds}
    $l_{min} = 32$ \tcc*[r]{longueur mini des segments sécables}
    $\Gamma_i \leftarrow \Gamma_0$ \tcc*[r]{sommet courant}

-   $GL_{ref} \leftarrow GL(\Gamma, N_n, \bar{v}, S_y, S_{y^2})$ \tcc*[r]{voir à partir de ligne 18 pour le détail}
+   $GL_{ref} \leftarrow GL(\Gamma, N_n, \bar{v}, S_I, S_{I^2})$ \tcc*[r]{voir à partir de ligne 18 pour le détail}

   \Repeter(\tcc*[f]{niveau contour}){$N_{add}=0$}{
     $N_{add}\leftarrow 0$\;
     \Repeter(\tcc*[f]{niveau n\oe ud}){$N_{move}=0$}{
       $N_{move}\leftarrow 0$\;
       \Pour{$i=0$ à $i=N_n-1$}{
   \Repeter(\tcc*[f]{niveau contour}){$N_{add}=0$}{
     $N_{add}\leftarrow 0$\;
     \Repeter(\tcc*[f]{niveau n\oe ud}){$N_{move}=0$}{
       $N_{move}\leftarrow 0$\;
       \Pour{$i=0$ à $i=N_n-1$}{

-       Calculer les positions $\{\Gamma_i^0, \dots, \Gamma_i^7\}$ \tcc*[r]{les 8 voisins de $\Gamma_i$ }
+       Calculer les positions $\{\Gamma_i^0, \dots, \Gamma_i^7\}$ \tcc*[r]{les 8 voisins de $\Gamma_i$ à distance $d$ }

         $GL_w \leftarrow GL_{ref} - $ la contribution des segments $\Gamma_{i-1}\Gamma_i$ et $\Gamma_{i}\Gamma_{i+1}$\;        
         \Pour{$w=0$ à $w=7$}{
          Discrétiser les segments $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$\nllabel{li-bresen}\;
         $GL_w \leftarrow GL_{ref} - $ la contribution des segments $\Gamma_{i-1}\Gamma_i$ et $\Gamma_{i}\Gamma_{i+1}$\;        
         \Pour{$w=0$ à $w=7$}{
          Discrétiser les segments $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$\nllabel{li-bresen}\;

-          Lire dans $S_1$, $S_x$ et $S_{x^2}$ les contributions des pixels de $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$\nllabel{li-contrib-seg-deb}\;
+          Lire dans $S_1$, $S_I$ et $S_{I^2}$ les contributions des pixels de $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$\nllabel{li-contrib-seg-deb}\;

           Calculer les directions et lire les codes de Freeman \;
           Calculer $GL_w$ incluant les contributions de $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$ \nllabel{li-contrib-seg-fin}\;
          \Si{$GL_w > GL_{ref}$}{
           Calculer les directions et lire les codes de Freeman \;
           Calculer $GL_w$ incluant les contributions de $\Gamma_{i-1}\Gamma_i^w$ et $\Gamma_{i}^w\Gamma_{i+1}$ \nllabel{li-contrib-seg-fin}\;
          \Si{$GL_w > GL_{ref}$}{


@@ -204,31 +204,30 @@ Un des inconvénients des algorithmes de type \textit{snake} est l'influence du
    }
    $N_n \leftarrow N_n + N_{add}$\;
    \lSi{$d > 1$}{ $d \leftarrow d/2$ } \lSinon{ $d \leftarrow 1$ }\;
    }
    $N_n \leftarrow N_n + N_{add}$\;
    \lSi{$d > 1$}{ $d \leftarrow d/2$ } \lSinon{ $d \leftarrow 1$ }\;

-   $GL_{ref} \leftarrow GL(\Gamma, N_n, \bar{v}, S_y, S_{y^2})$ \;
+   $GL_{ref} \leftarrow GL(\Gamma, N_n, \bar{v}, S_I, S_{I^2})$ \;

   }
 \end{algorithm}
 
   }
 \end{algorithm}
 

-\pagebreak
-Les différentes sommations nécessaires au calcul de la valeur du critère $GL$ sont effectuées en parallèle à l'aide du jeu d'instructions SSE2, qui permet de travailler avec des registres de grande capacité (128 bits) et d'envisager d'y ranger côte à côte les opérandes des trois sommes pour les effectuer simultanément. 
-Si l'on cherche à traiter des images en niveaux de gris sont codés sur 16 bits, les sommes $S_1$, $S_X$ et $S_{X^2}$ vont utiliser :
-\begin{itemize}
-\item $N_c$ bits par opérande de chaque somme pour représenter les coordonnées des pixels.
-\item $N_p$ bits pour traduire le nombre d'opérandes dans chaque somme. 
-\item 16 bits par valeur de niveau de gris dans $S_X$.
-\item 32 bits par valeur de niveau de gris au carré dans $S_{X^2}$.
-\end{itemize}
-Les trois sommes utilisent donc, par opérande, un total de $\left(3\left(N_c+N_p\right)+16+32\right)$ bits devant être contenu dans un registre de 128 bits, ce qui nous donne un maximum de 26 bits pour $N_c+N_p$. 
-La longueur des segments pouvant être au maximum $\sqrt{2}$ fois supérieure au coté de l'image, on peut donc considérer qu'il est nécessaire d'avoir  $N_p = N_c+1$ pour ne pas générer de restriction sur la longueur des segments. Cela nous conduit donc à $N_c = 12$ et $N_p=13$ ($12+13 = 25 < 26$).  
-La répartition retenue pour les données dans les registres SSE2 de 128 bits est alors la suivante :
-\begin{itemize}
-\item $N_c+N_p=25$ bits pour les opérandes des sommes de $S_1$.
-\item $N_c+N_p+16=41$ bits pour les opérandes des sommes de $S_X$.
-\item $N_c+N_p+32=57$ bits pour les opérandes des sommes de $S_{X^2}$.
-\end{itemize}
+% Les différentes sommations nécessaires au calcul de la valeur du critère $GL$ sont effectuées en parallèle à l'aide du jeu d'instructions SSE2, qui permet de travailler avec des registres de grande capacité (128 bits) et d'envisager d'y ranger côte à côte les opérandes des trois sommes pour les effectuer simultanément. 
+% Si l'on cherche à traiter des images en niveaux de gris sont codés sur 16 bits, les sommes $S_1$, $S_X$ et $S_{X^2}$ vont utiliser :
+% \begin{itemize}
+% \item $N_c$ bits par opérande de chaque somme pour représenter les coordonnées des pixels.
+% \item $N_p$ bits pour traduire le nombre d'opérandes dans chaque somme. 
+% \item 16 bits par valeur de niveau de gris dans $S_X$.
+% \item 32 bits par valeur de niveau de gris au carré dans $S_{X^2}$.
+% \end{itemize}
+% Les trois sommes utilisent donc, par opérande, un total de $\left(3\left(N_c+N_p\right)+16+32\right)$ bits devant être contenu dans un registre de 128 bits, ce qui nous donne un maximum de 26 bits pour $N_c+N_p$. 
+% La longueur des segments pouvant être au maximum $\sqrt{2}$ fois supérieure au coté de l'image, on peut donc considérer qu'il est nécessaire d'avoir  $N_p = N_c+1$ pour ne pas générer de restriction sur la longueur des segments. Cela nous conduit donc à $N_c = 12$ et $N_p=13$ ($12+13 = 25 < 26$).  
+% La répartition retenue pour les données dans les registres SSE2 de 128 bits est alors la suivante :
+% \begin{itemize}
+% \item $N_c+N_p=25$ bits pour les opérandes des sommes de $S_1$.
+% \item $N_c+N_p+16=41$ bits pour les opérandes des sommes de $S_X$.
+% \item $N_c+N_p+32=57$ bits pour les opérandes des sommes de $S_{X^2}$.
+% \end{itemize}

 
 \subsection{Performances}
 Les images de 1024$\times$1024 pixels de la figure \ref{fig-snakecpu-cochon512} montrent l'évolution du contour lors de la segmentation d'une image photographique prise en faible éclairement et bruitée artificiellement par un bruit gaussien d'écart type 25. Les paramètres de la séquence sont fixés empiriquement aux valeurs $d_{max}=16, l_{min}=8$.
 
 \subsection{Performances}
 Les images de 1024$\times$1024 pixels de la figure \ref{fig-snakecpu-cochon512} montrent l'évolution du contour lors de la segmentation d'une image photographique prise en faible éclairement et bruitée artificiellement par un bruit gaussien d'écart type 25. Les paramètres de la séquence sont fixés empiriquement aux valeurs $d_{max}=16, l_{min}=8$.

-Les temps d'exécution indiqués sont mesurés sur Intel Xeon E5530-2.4GHz with 12Go RAM et sont les valeurs moyennes obtenues pour 10 exécutions.
+Les temps d'exécution indiqués sont mesurés sur Intel Xeon E5530-2.4GHz avec 12Go RAM.

 \begin{figure}
   \centering
   \subfigure[Initialisation : 4 n\oe uds]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im000.png}}
 \begin{figure}
   \centering
   \subfigure[Initialisation : 4 n\oe uds]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im000.png}}


@@ -239,11 +238,11 @@ Les temps d'exécution indiqués sont mesurés sur Intel Xeon E5530-2.4GHz with
   \subfigure[Itération 10 : 244 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im010.png}}
   \subfigure[Itération 13 : 256 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im013.png}}
   \subfigure[Itération 14 : 256 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im014.png}}
   \subfigure[Itération 10 : 244 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im010.png}}
   \subfigure[Itération 13 : 256 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im013.png}}
   \subfigure[Itération 14 : 256 n\oe uds 3~ms]{\includegraphics[height=3.5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/im014.png}}

-  \caption{Évolution du contour lors de la segmentation d'une image de 512$^2$ pixels. La convergence est obtenue à l'itération 14 après 44~ms pour un total de  256 n\oe uds.}
+  \caption{Évolution du contour lors de la segmentation d'une image de 512$\times$512 pixels. La convergence est obtenue à l'itération 14 après 44~ms pour un total de  256 n\oe uds.}

  \label{fig-snakecpu-cochon512}
 \end{figure}
 
  \label{fig-snakecpu-cochon512}
 \end{figure}
 

-La dépendance vis à vis du contour initial, qui est un des principaux soucis liés au snake est ici fortement relativisée. La figure \ref{fig-snakecpu-compinit} montre le contour final segmentant l'image de test de la figure \ref{fig-snakecpu-cochon512} à partir d'un état initial très éloigné du précédent et, \textit{a priori}, très défavorable compte tenu du fait qu'il est loin de la cible et sans intersection avec elle. Toutefois, le contour final est très proche de celui obtenu à partir d'un état initial englobant la cible, malgré un n\oe ud qui s'est \og accroché \fg{} au bord de l'image. La convergence est également plus longue à obtenir dans ce cas avec 87~ms pour de 17 itérations et 273 n\oe uds. 
+La dépendance vis à vis du contour initial, qui est un des principaux soucis liés au snake est ici fortement relativisée. La figure \ref{fig-snakecpu-compinit} montre le contour final segmentant l'image de test de la figure \ref{fig-snakecpu-cochon512} à partir d'un état initial très éloigné du précédent et, \textit{a priori}, très défavorable compte tenu du fait qu'il est loin de la cible et sans intersection avec elle. Toutefois, le contour final est très proche de celui obtenu à partir d'un état initial englobant la cible, avec la particularité d'avoir identifié la peluche au fond et la zone sombre à la cible avec un n\oe ud à chaque coin de l'image. Cela est du à l'initialisation des zones avec comme cible une portion de la zone sombre, relativement homogène. La convergence est également plus longue à obtenir dans ce cas avec 87~ms pour 17 itérations et 273 n\oe uds. 

 
 \begin{figure}
   \centering
 
 \begin{figure}
   \centering


@@ -254,7 +253,8 @@ La dépendance vis à vis du contour initial, qui est un des principaux soucis l
   \label{fig-snakecpu-compinit}
 \end{figure}
 
   \label{fig-snakecpu-compinit}
 \end{figure}
 

-La dimension de l'image à traiter a également un effet sur le résultat et naturellement sur le temps de calcul. Si l'on conserve les mêmes paramètres d'optimisation que pour la segmentation de l'image 512$\times$512 pixels et un contour initial dont les cotés sont à une distance des bords équivalente à 10\% des cotés de l'image, le résultat sur une image identique de 4000$^2$4000 pixels est  obtenu en 1,3~s avec 1246 n\oe uds ; il est reproduit  à la figure \ref{fig-snakecpu-cochon4ka}. Le nombre de pixels appartenant à la région cible est tel que l'amplitude des déplacements autorisés pour chaque n\oe ud ($d$) peut se révéler trop faible vis-à-vis du seuil d'acceptation des mouvements. On observe que les zones à gradient élevé ne posent pas de problème et sont détourées de la même manière, alors que dans le bas de l'image où figure une zone de gradient faible (ombre), la cible se trouve maintenant quelque peu surévaluée en surface là ou elle était plutôt sous évaluée dans l'image en 512$\times$512 pixels. 
+La dimension de l'image à traiter a également un effet sur le résultat et naturellement sur le temps de calcul. Si l'on conserve la même stratégie d'optimisation que pour la segmentation de l'image 512$\times$512 pixels et un contour initial dont les cotés sont à une distance des bords équivalente à 10\% des cotés de l'image, le résultat sur une image identique de 4000$^2$4000 pixels est  obtenu en 1,3~s avec 1246 n\oe uds ; il est reproduit  à la figure \ref{fig-snakecpu-cochon4ka}. Le nombre de pixels appartenant à la région cible est tel que l'amplitude des déplacements autorisés pour chaque n\oe ud ($d$) peut se révéler trop faible vis-à-vis du seuil d'acceptation des mouvements. On observe que les zones à fort contraste ne posent pas de problème et sont détourées de la même manière, alors que dans le bas de l'image où figure une zone de faible contraste (ombre), la cible se trouve maintenant quelque peu surévaluée en surface là ou elle était plutôt sous évaluée dans l'image en 512$\times$512 pixels. 
+Ces deux contours correspondent chacun à un minimum local vers lequel l'algorithme du snake a convergé, mais les variances associées demeurent extrêmement proches.

 On parvient à un résultat très proche beaucoup plus rapidement en adaptant les paramètres à la taille de l'image, comme le montre par exemple la segmentation de la figure \ref{fig-snakecpu-cochon4kb}, effectuée avec $d_{max}=128$ et $l_{min}=32$ et qui converge vers un contour de 447 n\oe uds en moins de 0,7~s.
 Au delà des 16 millions de pixels (4000$\times$4000 pixels), l'implémentation séquentielle est toujours possible mais doit se priver des instructions SSE. Nous avons, avec l'accord des auteurs, adapté leur code en ce sens et réalisé les mesures pour des tailles allant jusqu'à 150~MP. La table \ref{tab-snakecpu-speed-size} en synthétise les résultats en distinguant chaque fois le temps pris par les pré-calculs et celui nécessaire à la convergence de la segmentation. On constate que les deux étapes et donc le temps total varient linéairement avec la taille de l'image.
 
 On parvient à un résultat très proche beaucoup plus rapidement en adaptant les paramètres à la taille de l'image, comme le montre par exemple la segmentation de la figure \ref{fig-snakecpu-cochon4kb}, effectuée avec $d_{max}=128$ et $l_{min}=32$ et qui converge vers un contour de 447 n\oe uds en moins de 0,7~s.
 Au delà des 16 millions de pixels (4000$\times$4000 pixels), l'implémentation séquentielle est toujours possible mais doit se priver des instructions SSE. Nous avons, avec l'accord des auteurs, adapté leur code en ce sens et réalisé les mesures pour des tailles allant jusqu'à 150~MP. La table \ref{tab-snakecpu-speed-size} en synthétise les résultats en distinguant chaque fois le temps pris par les pré-calculs et celui nécessaire à la convergence de la segmentation. On constate que les deux étapes et donc le temps total varient linéairement avec la taille de l'image.
 


@@ -294,7 +294,7 @@ Au delà des 16 millions de pixels (4000$\times$4000 pixels), l'implémentation
 \end{table}
 
 
 \end{table}
 
 

-Enfin, il faut aussi considérer les tailles relatives de la cible et de l'image. Ainsi, si on fait l'hypothèse d'une cible de petite taille \og noyée \fg{} dans une image de grandes dimensions, les résultats de la segmentation seront impactés en raison, cette fois, d'une moindre adaptation à la cible lors des toutes premières itérations, les plus grossières, où le nombre de n\oe uds est réduit et le pas de déplacement potentiellement grand vis à vis de la cible. Ce cas de figure est illustré par la segmentation reproduite à la figure \ref{fig-snakecpu-cochon4kc3} et qui met en évidence une qualité moindre par la confusion des zones les plus sombres de la cible avec le fond.
+Enfin, il faut aussi considérer les tailles relatives de la cible et de l'image. Ainsi, si on fait l'hypothèse d'une cible de petite taille \og noyée \fg{} dans une image de grandes dimensions, les résultats de la segmentation seront impactés en raison, cette fois, d'une moindre adaptation à la cible lors des toutes premières itérations, les plus grossières, où le nombre de n\oe uds est réduit et le pas de déplacement potentiellement grand vis à vis de la cible. Ce cas de figure est illustré par la segmentation reproduite à la figure \ref{fig-snakecpu-cochon4kc3} et qui met en évidence une qualité moindre par la confusion des zones les plus sombres de la cible avec le fond et confirme ainsi la nécessité d'adapter la stratégie d'optimisation au problème posé.

 
 
 
 
 
 


@@ -319,7 +319,7 @@ Si l'effort de parallélisation porte essentiellement sur ces fonctions coûteus
 Les traitements étant totalement indépendants, nous traitons séparément la parallélisation des pré-calculs et celle de la segmentation.
 
 \subsection{Pré-calculs des images cumulées}   
 Les traitements étant totalement indépendants, nous traitons séparément la parallélisation des pré-calculs et celle de la segmentation.
 
 \subsection{Pré-calculs des images cumulées}   

-Pour réduire la quantité de mémoire requise, nous avons choisi de ne pas générer l'image $S_1$ mais plutôt d'en calculer les valeurs à la volée. L'expression en est simple et le temps pris par les opérations élémentaires qu'elle met en jeu est largement compensé par le gain obtenu en économisant les accès mémoire qui auraient été nécessaires, ce qui n'est pas le cas des deux autres images $S_x$ et $S_x^2$ dont le calcul est quant à lui réalisé en appliquant une variante de la méthode des sommes préfixées (\textit{prefixsums}) décrite dans \cite{BlellochTR90} et qui permet d'évaluer les expressions de l'équation \eqref{eq-img-cumul}.
+Pour réduire la quantité de mémoire requise, nous avons choisi de ne pas générer l'image $S_1$ mais plutôt d'en calculer les valeurs à la volée. L'expression en est simple et le temps pris par les opérations élémentaires qu'elle met en jeu est largement compensé par le gain obtenu en économisant les accès mémoire qui auraient été nécessaires, ce qui n'est pas le cas des deux autres images $S_I$ et $S_I^2$ dont le calcul est quant à lui réalisé en appliquant une variante de la méthode des sommes préfixées (\textit{prefixsums}) décrite dans \cite{BlellochTR90} et qui permet d'évaluer les expressions de l'équation \eqref{eq-img-cumul}.

 
 Les sommations se font au niveau de chaque ligne de l'image, que l'on décompose en $n$ blocs de $bs$ pixels où $bs$ correspond aussi au nombre de threads exécutés par chaque bloc de la grille de calcul. La valeur $bs$ étant obligatoirement une puissance de 2 supérieure à 32, le bloc de pixels d'indice $n-1$ doit éventuellement être complété par des valeurs nulles. Chaque bloc de thread réalise son traitement indépendemment des autres, mais l'ensemble des sommes de bloc étant requise pour le calcul des sommes globales, une synchronisation est nécessaire à deux endroits du calcul. Nous avons choisi d'assurer ces synchronisations en découpant le traitement en trois \textit{kernels} distincts, rendant par la même occasion le code plus concis :
 \begin{itemize}
 
 Les sommations se font au niveau de chaque ligne de l'image, que l'on décompose en $n$ blocs de $bs$ pixels où $bs$ correspond aussi au nombre de threads exécutés par chaque bloc de la grille de calcul. La valeur $bs$ étant obligatoirement une puissance de 2 supérieure à 32, le bloc de pixels d'indice $n-1$ doit éventuellement être complété par des valeurs nulles. Chaque bloc de thread réalise son traitement indépendemment des autres, mais l'ensemble des sommes de bloc étant requise pour le calcul des sommes globales, une synchronisation est nécessaire à deux endroits du calcul. Nous avons choisi d'assurer ces synchronisations en découpant le traitement en trois \textit{kernels} distincts, rendant par la même occasion le code plus concis :
 \begin{itemize}


@@ -328,14 +328,14 @@ Les sommations se font au niveau de chaque ligne de l'image, que l'on décompose
 \item \texttt{add\_sums2prefixes()} est le \textit{kernel} effectuant les additions de chaque élément d'indice $i$ des vecteurs $V_x$ (respectivement $V_x^2$) avec tous les éléments du prefixsum du bloc de même indice $i$. 
 \end{itemize}
 
 \item \texttt{add\_sums2prefixes()} est le \textit{kernel} effectuant les additions de chaque élément d'indice $i$ des vecteurs $V_x$ (respectivement $V_x^2$) avec tous les éléments du prefixsum du bloc de même indice $i$. 
 \end{itemize}
 

-Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le détail des opérations effectuées par ces trois \textit{kernels} pour l'image cumulée $S_x$. La seconde image cumulée $S_x^2$ est obtenues exactement de la même manière en sommant non plus les valeurs $v_k$ mais $v^2_k$.
+Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le détail des opérations effectuées par ces trois \textit{kernels} pour l'image cumulée $S_I$. La seconde image cumulée $S_{I^2}$ est obtenues exactement de la même manière en sommant non plus les valeurs $v_k$ mais $v^2_k$.

 
 \begin{figure}
   \centering
   \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{compute\_block\_prefixes()}. La valeur $bs$ correspond au nombre de pixels de chaque bloc, qui est aussi le nombre de threads exécuté par chaque bloc de la grille de calcul.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUcumuls.pdf_t}}}\vspace{1cm}
 \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{scan\_blocksums()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUscansomblocs.pdf_t}}}\vspace{1cm}
 \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{add\_sums2prefixes()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUaddsoms2cumuls.pdf_t}}}
 
 \begin{figure}
   \centering
   \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{compute\_block\_prefixes()}. La valeur $bs$ correspond au nombre de pixels de chaque bloc, qui est aussi le nombre de threads exécuté par chaque bloc de la grille de calcul.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUcumuls.pdf_t}}}\vspace{1cm}
 \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{scan\_blocksums()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUscansomblocs.pdf_t}}}\vspace{1cm}
 \subfigure[Détail des opérations effectuées par le \textit{kernel} \texttt{add\_sums2prefixes()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUaddsoms2cumuls.pdf_t}}}

-  \caption{Calcul des images cumulées $S_x$ et $S_x^2$ en trois étapes successives. a) cumul partiel bloc par bloc et mémorisation de la somme de chaque bloc. b) cumul sur le  vecteur des sommes partielles. c) ajout des sommes partielles à chaque élément des blocs cumulés.}
+  \caption{Calcul des images cumulées $S_I$ et $S_{I^2}$ en trois étapes successives. a) cumul partiel bloc par bloc et mémorisation de la somme de chaque bloc. b) cumul sur le  vecteur des sommes partielles. c) ajout des sommes partielles à chaque élément des blocs cumulés.}

 \label{fig-calcul-cumuls}
 \end{figure}
 
 \label{fig-calcul-cumuls}
 \end{figure}
 


@@ -470,8 +470,8 @@ Les accès en mémoire aux contributions des pixels de coefficient $C(i,j)=0$, d
 Dans l'hypothèse la plus contraignante d'images en niveaux de gris codés sur 16 bits, l'implémentation parallèle que nous venons de décrire utilise de manière permanente 20 octets par pixel de l'image d'entrée, qui se détaillent en
 \begin{itemize}
 \item l'image d'entrée pour 4 octets par pixel (1 entier).
 Dans l'hypothèse la plus contraignante d'images en niveaux de gris codés sur 16 bits, l'implémentation parallèle que nous venons de décrire utilise de manière permanente 20 octets par pixel de l'image d'entrée, qui se détaillent en
 \begin{itemize}
 \item l'image d'entrée pour 4 octets par pixel (1 entier).

-\item l'image cumulée $S_x$ pour 8 octets par pixel (1 entier long)
-\item l'image cumulée $S_x^2$ pour 8 octets par pixel (1 entier long)
+\item l'image cumulée $S_I$ pour 8 octets par pixel (1 entier long)
+\item l'image cumulée $S_{I^2}$ pour 8 octets par pixel (1 entier long)

 \end{itemize}
 auxquels il faut ajouter un maximum d'environ 50~Mo d'espace nécessaire à la mémorisation des variables temporaires des calculs et données diverses comme le contour lui-même (n\oe uds, milieux, Freemans, etc.).   
 
 \end{itemize}
 auxquels il faut ajouter un maximum d'environ 50~Mo d'espace nécessaire à la mémorisation des variables temporaires des calculs et données diverses comme le contour lui-même (n\oe uds, milieux, Freemans, etc.).   
 


@@ -539,7 +539,7 @@ Le gain de  performance apporté par cette initialisation \og intelligente \fg{}
   \subfigure[Détermination de $j_L$ et $j_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init1.pdf_t}}}\quad
  \subfigure[Détermination de $i_L$ et $i_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init2.pdf_t}}}
 \label{fig-smart-init}
   \subfigure[Détermination de $j_L$ et $j_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init1.pdf_t}}}\quad
  \subfigure[Détermination de $i_L$ et $i_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init2.pdf_t}}}
 \label{fig-smart-init}

-  \caption{Détermination intelligente du contour initial en deux phases successives. a) La première étape repose sur un échantillonnage horizontal. b) La seconde étape repose sur un échantillonnage vertical.}
+  \caption{Détermination intelligente du contour initial en deux phases successives. (a) La première étape repose sur un échantillonnage horizontal. (b) La seconde étape repose sur un échantillonnage vertical.}

 \end{figure}
  
 \subsection{Conclusion}
 \end{figure}
  
 \subsection{Conclusion}