X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/de66b573538c6949bbc090e4e7ac4af93a868bbd..10d54068846e7aee58e98dc76fa92f6f3a5c957a:/THESE/Chapters/chapter3/chapter3.tex?ds=inline

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index e802a48..8082daa 100644
--- a/THESE/Chapters/chapter3/chapter3.tex
+++ b/THESE/Chapters/chapter3/chapter3.tex
@@ -1,16 +1,18 @@
-\section{PrÃ©sentation de l'algorithme}
+\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 d'en rÃ©duire les temps d'exÃ©cution suffisamment  pour permettre l'interactivitÃ©. 
-Nous proposons dans la suite de ce chapitre de dÃ©tailler tout d'abord 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 en avons conÃ§u.
-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Ã© 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 aussi Ã  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. 
+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.
+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}
-Ã l'intÃ©rieur de l'image observÃ©e $\bar{v}$, soient $\bar{t}$ le vecteur composÃ© par les niveaux de gris des $N_t$ pixels de la rÃ©gion cible $\Omega_t$ et $\bar{b}$ celui des $N_b$ pixels du fond $\Omega_b$. Les vecteurs $\bar{t}$ et $\bar{b}$ sont supposÃ©s non corrÃ©lÃ©s et sont caractÃ©risÃ©s par leurs densitÃ©s de probabilitÃ© (PDF) respectives $p^{\Theta_t}$ et $p^{\Theta_b}$ ; $\Theta_t$ et $\Theta_b$ Ã©tant les vecteurs des paramÃ¨tres de leurs PDF. Dans le cas gaussien que nous supposerons ici, $\Theta = (\mu, \sigma)$ oÃ¹ $\mu$ est la moyenne et $\sigma^2$ est la variance.
+Ã l'intÃ©rieur de l'image observÃ©e $\bar{v}$, soient $\bar{t}$ le vecteur composÃ© par les niveaux de gris des $N_t$ pixels de la rÃ©gion cible $\Omega_t$ et $\bar{b}$ celui des $N_b$ pixels du fond $\Omega_b$. Les vecteurs $\bar{t}$ et $\bar{b}$ sont supposÃ©s non corrÃ©lÃ©s et sont caractÃ©risÃ©s par leurs densitÃ©s de probabilitÃ© (PDF) respectives $p^{\Theta_t}$ et $p^{\Theta_b}$ ; $\Theta_t$ et $\Theta_b$ Ã©tant les vecteurs des paramÃ¨tres de leurs PDF. Dans le cas gaussien que nous supposerons ici parcequ'il est considÃ©rÃ© comme prÃ©pondÃ©rant dans les images naturelles, $\Theta = (\mu, \sigma)$ oÃ¹ $\mu$ est la moyenne et $\sigma^2$ est la variance.
 On note $\Gamma$ le contour de la rÃ©gion cible ($\Gamma \in \Omega_t$), que l'on suppose continu en connexitÃ© Ã  8 voisins. 
 
 Le but de la segmentation est alors de dÃ©terminer la gÃ©omÃ©trie de $\Gamma$ qui maximise un critÃ¨re de vraisemblance gÃ©nÃ©ralisÃ©e (GL).
-La vraisemblance sur l'ensemble de l'image, \textit{ie.} la rÃ©gion $\Omega$ est donnÃ©e par
+La vraisemblance sur l'ensemble de l'image, \textit{i.e} la rÃ©gion $\Omega$, est donnÃ©e par
 
 \begin{equation}
 P\left(\bar{v} | \Omega_t, \Omega_b, \Theta_t, \Theta_b\right) = P\left(\bar{v} | \Omega_t, \Theta_t\right)P\left(\bar{v}|\Omega_b, \Theta_b\right)   
@@ -44,13 +46,13 @@ dans laquelle les vecteurs $\Theta_t$ et $\Theta_b$ sont estimÃ©s suivant la mÃ©
 \right.
 \end{equation}
 
-En intÃ©grant \eqref{eq-teta} dans \eqref{eq-gl1}, il reste, Ã  une constante prÃ¨s, le critÃ¨re de vraisemblance gÃ©nÃ©ralisÃ©e suivant, notÃ© GL, que l'on cherche Ã   optimiser en dÃ©terminant la gÃ©omÃ©trie de $\Gamma$ qui en maximise la valeur et Ã©pousera alors au mieux la forme du contour de la cible.
+En insÃ©rant les expressions de \eqref{eq-teta} dans \eqref{eq-gl1}, il reste, Ã  une constante prÃ¨s, le critÃ¨re de vraisemblance gÃ©nÃ©ralisÃ©e suivant, notÃ© GL, que l'on cherche Ã   optimiser en dÃ©terminant la gÃ©omÃ©trie de $\Gamma$ qui en maximise la valeur et Ã©pousera alors au mieux la forme du contour de la cible.
 \begin{equation}
   \label{eq-gl}
   GL=\frac{1}{2}\left(N_tln\left(\widehat{\sigma_t^2}\right)+N_bln\left(\widehat{\sigma_b^2}\right)\right)
 \end{equation}
 
-\subsection{Optimisation des calculs}\label{snake-formulation}
+\subsection{Optimisation des calculs\label{snake-formulation}}
 La maximisation de GL est effectuÃ©e en employant une technique itÃ©rative oÃ¹ sa valeur doit Ãªtre calculÃ©e Ã  chaque dÃ©formation du contour $\Gamma$.
 Si l'on se reporte Ã  l'Ã©quation \eqref{eq-teta}, on voit que l'obtention de la valeur de GL nÃ©cessite, Ã  chaque Ã©valuation d'une gÃ©omÃ©trie donnÃ©e de $\Gamma$, le calcul des sommes  
 \begin{align}
@@ -59,12 +61,12 @@ Si l'on se reporte Ã  l'Ã©quation \eqref{eq-teta}, on voit que l'obtention de la
   S_v(\Omega_b) &= \sum_{x_k\in \Omega_b} v_k & S_{v^2}(\Omega_b) &= \displaystyle\sum_{x_k\in \Omega_b} v_k^2 \nonumber\\
 \end{align}
 
-ConsidÃ¨rons la rÃ©gion cible $\Omega_t$, les pixels de coordonÃ©es $(i,j)$ qui la composent, et gÃ©nÃ©ralisons l'Ã©criture des sommes de \eqref{eq-sommes1} en 
+ConsidÃ©rons la rÃ©gion cible $\Omega_t$, les pixels de coordonÃ©es $(i,j)$ qui la composent, et gÃ©nÃ©ralisons l'Ã©criture des sommes de \eqref{eq-sommes1} en 
 \begin{equation}
   \label{eq-sommes-gene}
-  S_f(\Omega_t) = \sum_{i=i_{min}}^{i=i_{max}}\sum_{j=j_{min}(i)}^{j=j_{max}(i)}g\left(v(i,j)\right)
+  S_g(\Omega_t) = \sum_{i=i_{min}}^{i=i_{max}}\sum_{j=j_{min}(i)}^{j=j_{max}(i)}g\left(v(i,j)\right)
 \end{equation}
-oÃ¹ $f$ reprÃ©sente la fonction de valeurs de niveaux de gris Ã  sommer.
+oÃ¹ $g$ reprÃ©sente la fonction de valeurs de niveaux de gris Ã  sommer.
 
 En posant 
 \begin{equation}
@@ -74,7 +76,7 @@ En posant
 L'Ã©quation \eqref{eq-sommes-gene} devient 
 \begin{equation}
   \label{eq-somme-cumuls2}
-  S_f(\Omega_t) = \sum_{i=i_{min}}^{i=i_{max}}\left[T_g(i,j_{max}(i))-T_g(i,j_{min}(i)-1)\right]
+  S_g(\Omega_t) = \sum_{i=i_{min}}^{i=i_{max}}\left[T_g(i,j_{max}(i))-T_g(i,j_{min}(i)-1)\right]
 \end{equation}
 qui reprÃ©sente  une sommation sur le contour $\Gamma$ que l'on peut Ã©crire 
 \begin{equation}
@@ -94,6 +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}$.
+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}
@@ -101,7 +104,7 @@ La valeur de $C(i,j)$ est dÃ©terminÃ©e pour chaque pixel d'indice $l$ du contour
   \label{fig-freeman}
 \end{figure}
 
-\begin{table}[htb]
+\begin{table}[h]
   \centering
 \begin{tabular}[htb]{ccccccccc}
       \toprule
@@ -119,33 +122,34 @@ La valeur de $C(i,j)$ est dÃ©terminÃ©e pour chaque pixel d'indice $l$ du contour
       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$.
-\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}
-    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}
 
 
-Par ailleurs, le choix d'un contour polygonal permet Ã©galement d'amÃ©liorer l'efficacitÃ© de l'algorithme car lors de la phase de segmentation, le dÃ©placement d'un sommet du polygone n'influe que sur les pixels des deux segments qui s'y rapportent, rÃ©duisant ainsi la quantitÃ© de calculs Ã  effectuer Ã  chaque nouvelle dÃ©formation du contour.  
+Par ailleurs, le choix d'un contour polygonal permet d'amÃ©liorer l'efficacitÃ© de l'algorithme. Lors de la phase de segmentation, le dÃ©placement d'un sommet du polygone n'influe ainsi que sur les pixels des deux segments qui s'y rapportent, rÃ©duisant ainsi la quantitÃ© de calculs Ã  effectuer Ã  chaque nouvelle dÃ©formation du contour.  
 
 \begin{upminfo}
-  L'approche dÃ©crite dans ce chapitre n'est valide que si les segments formant le polygone du contour ne se croisent pas. Il est donc nÃ©cessaire, lors de la convergence de la segmentation, d'empÃªcher les croisements de segments. Une solution simple a Ã©tÃ© proposÃ©e dans \cite{ChesnaudRB99} et nous l'avons parallÃ©lisÃ©e dans le cadre des travaux prÃ©sentÃ©s ici. 
+L'approche dÃ©crite dans ce chapitre n'est valide que si les segments formant le polygone du contour ne se croisent pas. Il est donc nÃ©cessaire, lors de la convergence de la segmentation, d'empÃªcher ces croisements. Une solution simple a Ã©tÃ© proposÃ©e dans \cite{ChesnaudRB99}, que nous avons parallÃ©lisÃ©e et intÃ©grÃ©e. 
 \end{upminfo}
 
-\subsection{ImplÃ©mentation sÃ©quentielle}\label{snake-cpu-impl}
-Un des inconvÃ©nients des algorithmes de type \textit{snake} est l'influence du contour initial sur la convergence de la segmentation. Pour pallier simplement ce dÃ©faut, une technique progressive est adoptÃ©e, en initialisant le contour avec peu de sommets (4) puis en augmentant le nombre au fur et Ã  mesure de la convergence. L'algorithme \ref{algo-snake-cpu1} dÃ©crit macroscopiquement la solution mise \oe uvre tandis que l'algorithme \ref{algo-snake-cpu2} en prÃ©sente les dÃ©tails.
+\subsection{ImplÃ©mentation sÃ©quentielle\label{snake-cpu-impl}}
+Un des inconvÃ©nients des algorithmes de type \textit{snake} est l'influence du contour initial sur la convergence de la segmentation. Pour pallier simplement ce dÃ©faut, une technique progressive est adoptÃ©e, en initialisant le contour avec peu de sommets (par exemple 4) puis en augmentant le nombre au fur et Ã  mesure de la convergence. L'algorithme \ref{algo-snake-cpu1} dÃ©crit macroscopiquement la solution mise \oe uvre tandis que l'algorithme \ref{algo-snake-cpu2} en prÃ©sente les dÃ©tails.
 
-\begin{algorithm}
-\label{algo-snake-cpu}
+\begin{algorithm}[h]
+\label{algo-snake-cpu1}
+\small
 \caption{Principe mis en \oe uvre pour la convergence du snake polygonal}
   Calculer les images cumulÃ©es\;
   Initialiser le contour avec 4 sommets\;
@@ -158,31 +162,32 @@ Un des inconvÃ©nients des algorithmes de type \textit{snake} est l'influence du
   }
 \end{algorithm}
 
-\begin{algorithm}[h]
+\begin{algorithm}[H]
 \caption{DÃ©tail de l'implÃ©mentation du snake polygonal} 
-\label{cpualgo}
+\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]{} 
    $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$}{
-	Calculer les positions $\{\Gamma_i^0, \dots, \Gamma_i^7\}$ \tcc*[r]{les 8 voisins de $\Gamma_i$ }
-	\Pour{$w=0$ Ã  $w=7$}{
-          Soustraire Ã  $GL_{ref}$ la contribution des segments $\Gamma_{i-1}\Gamma_i$ et $\Gamma_{i}\Gamma_{i+1}$\;
+	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}\;
-          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}\;
-	  \lSi{$GL_w > GL_{ref}$}{
+	  \Si{$GL_w > GL_{ref}$}{
 	    $GL_{ref} \leftarrow GL_w$\;
 	    $\Gamma_i \leftarrow \Gamma_i^w$\;
             $N_{move} \leftarrow N_{move}+1$\;
@@ -199,21 +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$ }\;
-   $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}
 
-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. La taille des registres utilisables est de 128 bits et permet ainsi de traiter des images de 4096$\times$4096 pixels dont les niveaux de gris sont codÃ©s sur 16 bits. Cela ne laisse toutefois que 12 bits pour le codage des segments du contour et limite ainsi leur longueur Ã  4096 pixels. L'organisation d'un registre SSE 128 bits est donc la suivante :
-\begin{itemize}
-\item 24 bits pour les sommes Ã  opÃ©randes dans $S_1$
-\item 24+16 = 40 bits pour les sommes Ã  opÃ©randes dans $S_x$
-\item 24+32 = 60 bits pour les sommes Ã  opÃ©randes dans $S_x^2$
-\end{itemize}
-Soit un total de 124 bits, qui peuvent donc Ãªtre reprÃ©sentÃ©s par un registre SSE2.
+% 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$^2$ 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 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 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}}
@@ -224,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}}
-  \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}
 
-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 obtenu est trÃ¨s proche de celui obtenu Ã  partir d'un Ã©tat initial englobant la cible, malgrÃ© un n\oe ud qui s'est ``accrochÃ©'' au bord de l'image. La convergence est Ã©galement plus longue Ã  obtenir dans ce cas avec Un total de 17 itÃ©rations en 87~ms 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
@@ -239,18 +253,27 @@ La dÃ©pendance vis Ã  vis du contour initial qui est un des principaux soucis li
   \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$^2$ 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$ 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$^2$ pixels. 
-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$^2$ pixels), l'implÃ©mentation sÃ©quentielle est toujours possible mais doit se priver des instructions SSE. Nous avons, avec leur accord, adaptÃ© le code des auteurs 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. 
+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 de rÃ©fÃ©rence ne permettait plus le traitement. 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.
 
 \begin{figure}
   \centering
-  \subfigure[$d_{max}=16$ et $l_{min}=8$, 1246 n\oe uds en 1.3~s]{\label{fig-snakecpu-cochon4ka}\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/snakecpu-cochon4k.png}}
-  \subfigure[$d_{max}=128$ et $l_{min}=32$, 447 n\oe uds en 0.7~s]{\label{fig-snakecpu-cochon4kb}\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/snakecpu-cochon4k-128-32.png}}
-  \caption{Segmentation de l'image de test en 4000$^2$ pixels.}
+  \subfigure[$d_{max}=16$ et $l_{min}=8$, 1246 n\oe uds en 1.3~s]{\label{fig-snakecpu-cochon4ka}\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/snakecpu-cochon4k-t.png}}
+  \subfigure[$d_{max}=128$ et $l_{min}=32$, 447 n\oe uds en 0.7~s]{\label{fig-snakecpu-cochon4kb}\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/snakecpu-cochon4k-128-32-t.png}}
+  \caption{Segmentation de l'image de test en 4000$\times$4000 pixels. Le tracÃ© du contour a Ã©tÃ© artificiellement Ã©paissi pour le rendre visible Ã  l'Ã©chelle de l'impression.}
   \label{fig-snakecpu-cochon4k}
 \end{figure}
 
+\begin{figure}[h]
+  \centering
+  \includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cochon4kc-128-8-t.png}
+  \caption{Segmentation de l'image de test en 4000$\times$4000 pixels avec une cible de petite taille. Le contour initial est la transcription de celui utilisÃ© Ã  la figure \ref{fig-snakecpu-cochon512}. Le tracÃ© du contour a Ã©tÃ© artificiellement Ã©paissi pour le rendre visible Ã  l'Ã©chelle de l'impression.}
+  \label{fig-snakecpu-cochon4kc3}
+\end{figure}
+ 
+
 
 \begin{table}[h]
   \centering
@@ -266,28 +289,21 @@ Au delÃ  des 16 millions de pixels (4000$^2$ pixels), l'implÃ©mentation sÃ©quent
       {\bf Total} &0,51&4,08&5,7\\
       \bottomrule
 \end{tabular}
-   \caption{Performances (en secondes) de la segmentation par snake polygonal sur CPU en fonction de la taille de l'image Ã  traiter. Le temps sont obtenus avec la mÃªme image de test dilatÃ©e et bruitÃ©e et un contour initial carrÃ© dont la distance aux bords est proportionnelle Ã  la taille de l'image. Seule l'image en 15~MP a pu Ãªtre traitÃ©e par une implÃ©mentation utilisant SSE2.}
+   \caption{Performances (en secondes) de la segmentation par snake polygonal sur CPU en fonction de la taille de l'image Ã  traiter. Les temps sont obtenus avec la mÃªme image de test dilatÃ©e et bruitÃ©e et un contour initial carrÃ© dont la distance aux bords est proportionnelle Ã  la taille de l'image.}
       \label{tab-snakecpu-speed-size}
 \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 ``noyÃ©e'' 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 et 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Ã©.
 
-\begin{figure}[h]
-  \centering
-  \includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cochon4kc-128-8.png}
-  \caption{Segmentation de l'image de test en 4000$^2$ pixels avec une cible de petite taille. Le contour initial est celui utilisÃ© Ã  la figure \ref{fig-snakecpu-cochon4k}.}
-  \label{fig-snakecpu-cochon4kc3}
-\end{figure}
- 
 
 
 \section{ImplÃ©mentation parallÃ¨le GPU du snake polygonal}
-L'analyse de l'exÃ©cution du programme sÃ©quentiel rÃ©vÃ¨le la prÃ©pondÃ©rance des blocs fonctionnels suivants, dans l'ordre d'importance, qui occupent Ã  eux seuls plus de 80\% du temps total d'exÃ©cution :
+L'analyse de l'exÃ©cution du programme sÃ©quentiel rÃ©vÃ¨le la prÃ©pondÃ©rance des blocs fonctionnels suivants, qui occupent Ã  eux seuls 80\% du temps total d'exÃ©cution :
 \begin{itemize}
- \item Le calcul de la contribution des segments (lignes \ref{li-contrib-seg-deb} Ã  \ref{li-contrib-seg-fin} dans l'algorithme \ref{cpualgo}) 
-  \item La gÃ©nÃ©ration des trois images cumulÃ©es, avant le dÃ©but des itÃ©rations (ligne \ref{li-img-cumul}).
-  \item La discrÃ©tisation des segments dÃ©finis par les coordonnÃ©es de leurs extrÃ©mitÃ©s (ligne \ref{li-bresen}).
+ \item Le calcul de la contribution des segments, pour environ 50\% (lignes \ref{li-contrib-seg-deb} Ã  \ref{li-contrib-seg-fin} dans l'algorithme \ref{algo-snake-cpu2}) 
+  \item La gÃ©nÃ©ration des trois images cumulÃ©es, avant le dÃ©but des itÃ©rations, pour environ 20\% (ligne \ref{li-img-cumul}).
+  \item La discrÃ©tisation des segments dÃ©finis par les coordonnÃ©es de leurs extrÃ©mitÃ©s, pour environ 7\% (ligne \ref{li-bresen}).
 \end{itemize}
 Cette proportion est globalement conservÃ©e lorsque la taille de l'image Ã  traiter varie, comme le montre le graphique de la figure \ref{fig-snakecpu-chronos1} 
 
@@ -298,34 +314,35 @@ Cette proportion est globalement conservÃ©e lorsque la taille de l'image Ã  trai
   \caption{Ãvolution du coÃ»t relatif des trois fonctions les plus consommatrices en temps de calcul en fonction de la taille de l'image Ã  traiter.}
 \end{figure} 
 
-Si l'effort de parallÃ©lisation porte essentiellement sur ces fonctions coÃ»teuses, l'ensemble du traitement est rÃ©alisÃ© sur le GPU afin de rÃ©duire autant que possible les transferts entre le GPU et le systÃ¨me hÃ´te qui, selon le volume concernÃ©, sont susceptibles de grever considÃ©rablement la performance globale. L'hÃ´te ne conserve que l'initiative du transfert initial et le contrÃ´le de la boucle principale, ne nÃ©cessitant l'Ã©change que d'un seul octet Ã  chaque itÃ©ration (le nombre de nouveau n\oe uds $N_{add}$).
+Si l'effort de parallÃ©lisation porte essentiellement sur ces fonctions coÃ»teuses, l'ensemble du traitement est rÃ©alisÃ© sur le GPU afin de rÃ©duire autant que possible les transferts entre le GPU et le systÃ¨me hÃ´te qui, selon le volume concernÃ©, sont susceptibles de grever considÃ©rablement la performance globale. L'hÃ´te ne conserve que l'initiative du transfert initial et le contrÃ´le de la boucle principale, ne nÃ©cessitant l'Ã©change que d'un seul octet Ã  chaque itÃ©ration (reprÃ©sentant le nombre de nouveaux n\oe uds $N_{add}$).
 
-Les traitements Ã©tant totalement indÃ©pendants, nos traitons sÃ©parÃ©ment la parallÃ©lisation des prÃ©-calculs et celle de la segmentation.
+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Ã©ration Ã©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 la mÃ©thode des \textit{prefixsums} dÃ©crite dans \cite{BlellochTR90}.
+\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_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 Ã©ventuellment Ãª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 :
+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. 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$ :
 \begin{itemize}
-\item \texttt{compute\_block\_prefixes()} est le \textit{kernel} effectuant, en mÃ©moire partagÃ©e, les prefixsums inclusif de chaque bloc, puis mÃ©morisant les sommes des blocs, \textit{i.e} le dernier Ã©lÃ©ment du prefixsum associÃ©, dans deux vecteurs $V_x$ et $V_x^2$ en mÃ©moire globale. L'ensemble des prefixsums est Ã©galement mÃ©morisÃ© en mÃ©moire globale. La largeur de l'image n'Ã©tant pas nÃ©cessairement une puissance de 2, il est nÃ©cessaire de faire du remplissage avec des valeurs nulles dans le dernier bloc (indice $n-1$). 
+\item \texttt{compute\_block\_prefixes()} est le \textit{kernel} effectuant, en mÃ©moire partagÃ©e, la \textit{prefixsum} inclusive de chaque bloc, puis qui en mÃ©morise les sommes, \textit{i.e} le dernier Ã©lÃ©ment, dans deux vecteurs $V_x$ et $V_x^2$ en mÃ©moire globale. L'ensemble des prefixsums est Ã©galement mÃ©morisÃ© en mÃ©moire globale. La largeur de l'image n'Ã©tant pas nÃ©cessairement une puissance de 2, il est nÃ©cessaire de faire du remplissage avec des valeurs nulles dans le dernier bloc (indice $n-1$). 
 \item \texttt{scan\_blocksums()} est le \textit{kernel} effectuant les prefixsum exclusifs des vecteurs $V_x$ et $V_x^2$. Les rÃ©sultat demeurent respectivement dans $V_x$ et $V_x^2$.
-\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$ associÃ©. 
+\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$.
+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}}}
+  \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}
-  \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.}
 \end{figure}
 
-Les gains de performance de cette implÃ©mentation GPU comparÃ©e Ã  l'implÃ©mentation CPU/SSE2 sont ceux de la table \ref{tab-speedup-cumuls}, soit un GPU environ 7 fois plus rapide pour des images de taille 15 Ã  150 millions de pixels. L'influence de la taille d'image sur le gain est faible, mais on peut toutefois noter que plus l'image est grande plus le gain est important.
+Les gains de performance de cette implÃ©mentation GPU comparÃ©e Ã  l'implÃ©mentation CPU (mono thread) sont ceux de la table \ref{tab-speedup-cumuls}, soit un GPU environ 7 fois plus rapide pour des images de taille 15 Ã  150 millions de pixels. L'influence de la taille d'image sur le gain est faible, mais on peut toutefois noter que plus l'image est grande plus le gain est important. 
+Les accÃ©lÃ©rations constatÃ©es peuvent sembler faibles en regard de ce que l'on attend d'un GPU, mais il faut rappeler que ce type d'opÃ©ration (les rÃ©ductions) n'est pas vÃ©ritablement adaptÃ© Ã  leur architecture en raison d'une grande inter-dÃ©pendance des donnÃ©es d'une Ã©tape de calcul Ã  l'autre. Sans une implÃ©mentation optimisÃ©e, cette opÃ©ration s'exÃ©cuterait mÃªme plus lentement sur GPU que sur un CPU.     
 On obtient des accÃ©lÃ©rations supÃ©rieures en rendant le calcul moins gÃ©nÃ©rique et en dÃ©veloppant des versions spÃ©cifiques des trois \textit{kernels}, dÃ©diÃ©es par exemple au traitement des images dont largeur est multiple de 256 pixels.
-\begin{table}
+\begin{table}[h]
   \centering
   \begin{tabular}{rrrr}
       \toprule
@@ -339,17 +356,17 @@ On obtient des accÃ©lÃ©rations supÃ©rieures en rendant le calcul moins gÃ©nÃ©riq
       {\bf AccÃ©lÃ©ration} &{\bf 6,5} &{\bf 6,9} &{\bf 7,0}\\
       \bottomrule
 \end{tabular}
-   \caption{AccÃ©lÃ©ration constatÃ©e, pour le calcul des images cumulÃ©es, de l'implÃ©mentation GPU par rapport Ã  l'implÃ©mentation CPU de rÃ©fÃ©rence.}
+   \caption{AccÃ©lÃ©ration constatÃ©e, pour le calcul des images cumulÃ©es, de l'implÃ©mentation GPU (C2070) par rapport Ã  l'implÃ©mentation CPU de rÃ©fÃ©rence.}
       \label{tab-speedup-cumuls}
 \end{table}
 
 
-\subsection{Calcul des contribution des segments}
+\subsection{Calcul des contributions des segments}
 
-Le dÃ©placement d'un des $N_n$ n\oe uds du contour $\Gamma$ vers l'une des 8 positions voisines permises, impose d'Ã©valuer les contributions des 8 paires de segments associÃ©es, soit $16N_n$ segments pour la totalitÃ© du contour, que nous Ã©valuons en parallÃ¨le au sein du \textit{kernel} \texttt{GPU\_compute\_segments\_contribs()}. Pour ce faire, chaque segment doit tout d'abord Ãªtre discrÃªtisÃ© en une suite de pixels puis, en conservant la rÃ¨gle \textit{1 pixel par thread} la contribution de chaque pixel est dÃ©terminÃ©e avant de toutes les additionner pour obtenir la contribution du segment. 
+Le dÃ©placement d'un des $N_n$ n\oe uds du contour $\Gamma$ vers l'une des 8 positions voisines Ã  distance $d$\footnote{Sous rÃ©serve que la position considÃ©rÃ©e ne dÃ©passe pas les limites de l'image.}, impose d'Ã©valuer les contributions des 8 paires de segments associÃ©es, soit $16N_n$ segments pour la totalitÃ© du contour, que nous Ã©valuons en parallÃ¨le au sein du \textit{kernel} \texttt{GPU\_compute\_segments\_contribs()}. Pour ce faire, chaque segment doit tout d'abord Ãªtre discrÃ©tisÃ© en une suite de pixels puis, en conservant la rÃ¨gle \textit{1 pixel par thread} la contribution de chaque pixel est dÃ©terminÃ©e avant de toutes les additionner pour obtenir la contribution du segment. 
 Les pixels reprÃ©sentant les n\oe uds font l'objet d'un traitement spÃ©cifique impliquant les codes de Freeman, pour ne pas fausser les contributions globales (voir paragraphe \ref{snake-cpu-impl}).  
 
-Pour optimiser l'exÃ©cution de ce kernel et rÃ©duire l'effet de la disparitÃ© des longueurs des segments, nous crÃ©ons un motif rÃ©gulier en mÃ©moire, basÃ© sur la longueur $npix_{max}$ du plus grand segment et moyennant le recours au remplissage par des valeurs neutres lÃ  oÃ¹ c'est nÃ©cessaire pour les autres segments.
+Pour optimiser l'exÃ©cution de ce kernel et rÃ©duire l'effet de la disparitÃ© des longueurs des segments, nous avons crÃ©e un motif rÃ©gulier en mÃ©moire, basÃ© sur la longueur $npix_{max}$ du plus grand segment et avons complÃ©tÃ© les blocs associÃ©s aux segments de longueur infÃ©rieure Ã  $npix_{max}$ avec des valeurs neutres pour l'opÃ©ration rÃ©alisÃ©e, c'est-Ã -dire des valeurs nulles. 
 
 Si $bs_{max}$ est la taille de bloc maximale admissible par le GPU, la taille $bs$ des blocs de threads/pixels employÃ©e pour le calcul des contributions des segments est alors dÃ©terminÃ©e de la faÃ§on suivante :
 \[
@@ -361,58 +378,69 @@ bs_{max} & \text{ si $npix_{max} > bs_{max}$}
 \end{cases} 
 \]
  
-Dans notre implÃ©mentation, les calculs sont faits en mÃ©moire partagÃ©e et la quantitÃ© nÃ©cessaire limite la taille de bloc admissible. Nous limitons celle-ci Ã  256 sur C1060 et 512 sur C2050. Toutefois, les tests ont montrÃ© que sur ces deux versions de l'architecture, La taille maximale conduisant aux meilleures performances est de 256 threads par bloc. 
+Dans notre implÃ©mentation, les calculs sont faits en mÃ©moire partagÃ©e et la quantitÃ© nÃ©cessaire limite la taille de bloc admissible. Nous limitons celle-ci Ã  256 sur C1060 et 512 sur C2050. Toutefois, les tests ont montrÃ© que sur ces deux versions de l'architecture, la taille maximale conduisant aux meilleures performances est de 256 threads par bloc. 
 
-Le \textit{kernel} \texttt{GPU\_compute\_segments\_contribs()} calcule alors en paralÃ¨le pour tous les segments les coordonnÃ©es de tous les pixels qui les composent. Nous mettons pour cela en \oe uvre l'algorithme de Bresenham, \textit{i.e} la mÃ©thode du segment semi-ouvert, en distinguant les cas oÃ¹
+Le \textit{kernel} \texttt{GPU\_compute\_segments\_contribs()} calcule alors en parallÃ¨le pour tous les segments les coordonnÃ©es de tous les pixels qui les composent. Nous mettons pour cela en \oe uvre l'algorithme de Bresenham, \textit{i.e} la mÃ©thode du segment semi-ouvert, en distinguant les cas oÃ¹
 \begin{itemize}
-\item la valeur absolue de la pente $k$ du segment Ã  discrÃªtiser est supÃ©rieure Ã  $1$; on applique alors la mÃ©thode au segment \textit{horizontal} semi-ouvert et on obtient un pixel par ligne.
-\item la valeur absolue de la pente $k$ du segment Ã  discrÃªtiser est infÃ©rieure ou Ã©gale Ã   $1$; on applique alors la mÃ©thode au segment \textit{vertical} semi-ouvert et on obtient un pixel par colonne.
+\item la valeur absolue de la pente $k$ du segment Ã  discrÃ©tiser est supÃ©rieure Ã  $1$; on applique alors la mÃ©thode au segment \textit{horizontal} semi-ouvert et on obtient un pixel par ligne.
+\item la valeur absolue de la pente $k$ du segment Ã  discrÃ©tiser est infÃ©rieure ou Ã©gale Ã   $1$; on applique alors la mÃ©thode au segment \textit{vertical} semi-ouvert et on obtient un pixel par colonne.
 \end{itemize}
 Cette distinction nous permet de conserver la rÃ¨gle \textit{1 pixel par thread} importante pour la rÃ©gularitÃ© des motifs d'accÃ¨s en mÃ©moire et aussi pour \textit{charger} au maximum le GPU.
 
-La figure \ref{fig-structure-segment} reprÃ©sente la structure dÃ©crite ci-dessus pour la reprÃ©sentation en mÃ©moire des segments Ã  Ã©valuer. La premiÃ¨re ligne montre le dÃ©tail du premier segment, avec la correspondance \textit{1 pixel par thread} et le dÃ©coupage en un nombre de blocs suffisant pour permettre de dÃ©crire le plus long des segments. 
-
-La seconde ligne prÃ©sente l'ordre dans lequel sont concatÃ©nÃ©s les 16 groupes de blocs-segment associÃ©s au dÃ©placement d'un n\oe ud particulier. 
-
 \begin{figure}
   \centering
   \resizebox{0.8\linewidth}{8cm}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/contribs_segments.pdf_t}}
-\label{fig-structure-segment}
   \caption{Structuration des donnÃ©es en mÃ©moire du GPU pour l'Ã©valuation en parallÃ¨le de l'ensemble des Ã©volutions possibles du contour.}
+\label{fig-structure-segment}
 \end{figure}
 
-Aux deux derniÃ¨res lignes est dÃ©crite la concatÃ©nation des ensembles de 16 blocs-segment, avec la particularitÃ© de sÃ©parer la description des n\oe uds d'indices pairs et ceux d'indices impairs. Cela permet de moins s'Ã©carter de l'heuristique d'optimisation en vigueur dans la version sÃ©quentielle : les statistiques globales comme la valeur de critÃ¨re $GL$ y sont recalculÃ©es aprÃ¨s chaque dÃ©placement, alors que dans le cas d'un traitement parallÃ¨le, les statistiques de rÃ©fÃ©rence ne sont calculÃ©es qu'aprÃ¨s le dÃ©placement simultanÃ© des $N_n$ n\oe uds; les rÃ©sultats et la convergence en sont potentiellement affectÃ©s, comme l'illustrent les situations prÃ©sentÃ©es Ã  la figure \ref{fig-cycle-contribs-segments}, car les segments composant vÃ©ritablement le contour aprÃ¨s dÃ©placement des n\oe uds n'ont pas nÃ©cessairement Ã©tÃ© Ã©valuÃ©s (segments en rouge dans la figure \ref{fig-cycle-contribs-segments}). 
+
+La figure \ref{fig-structure-segment} reprÃ©sente la structure dÃ©crite ci-dessus pour la reprÃ©sentation en mÃ©moire des segments Ã  Ã©valuer. La premiÃ¨re ligne montre le dÃ©tail du premier segment, avec la correspondance \textit{1 pixel par thread} et le dÃ©coupage en un nombre de blocs suffisant pour permettre de dÃ©crire le plus long des segments. 
+
+La seconde ligne prÃ©sente l'ordre dans lequel sont concatÃ©nÃ©s les 16 groupes de blocs-segment associÃ©s au dÃ©placement d'un n\oe ud particulier. 
+
+Les deux derniÃ¨res lignes dÃ©crivent la concatÃ©nation des ensembles de 16 blocs-segment, avec la particularitÃ© de sÃ©parer la description des positions des n\oe uds d'indices pairs et ceux d'indices impairs. Cela permet de moins s'Ã©carter de l'heuristique d'optimisation en vigueur dans la version sÃ©quentielle oÃ¹ les statistiques globales comme la valeur de critÃ¨re $GL$ sont recalculÃ©es aprÃ¨s chaque dÃ©placement (figures \ref{fig-cycle-contribs-segments-a}, \ref{fig-cycle-contribs-segments-b} et \ref{fig-cycle-contribs-segments-c}) .
+
+En version parallÃ¨le, si les \og meilleures \fg{}  positions de tous les n\oe uds sont calculÃ©es simultanÃ©ment, le contour gÃ©nÃ©rÃ© est constituÃ© de segments qui n'ont pas Ã©tÃ© validÃ©s pendant la phase de dÃ©placement des n\oe uds, comme l'illustre la figure \ref{fig-cycle-contribs-segments-e}. La valeur du critÃ¨re $GL$ doit donc Ãªtre calculÃ©e aprÃ¨s coup sur les segments rÃ©els du nouveau contour. Dans l'absolu, nous ne sommes donc pas assurÃ©s d'amÃ©liorer rÃ©ellement la valeur du critÃ¨re par rapport au contour de l'itÃ©ration prÃ©cÃ©dente.
+Pour limiter ce phÃ©nomÃ¨ne, qui pourrait provoquer des oscillations et empÃªcher la convergence, nous avons effectuÃ© les dÃ©placements en alternant ceux des n\oe uds d'indices pairs et ceux d'indices impairs. Cela permet de rÃ©gler le problÃ¨me lorsque le nombre de n\oe uds du contour est pair. Comme le montrent les figures \ref{fig-cycle-contribs-segments-e} et \ref{fig-cycle-contribs-segments-e}, un segment du contour demeure non validÃ© lorsque le nombre de n\oe uds est impair et nous impose toujours de recalculer, \textit{a posteriori}, la valeur du critÃ¨re $GL$ pour s'assurer de l'amÃ©lioration apportÃ© par les dÃ©placements des n\oe uds. La version parallÃ¨le reproduit, malgrÃ© cela, assez fidÃ¨lement la version sÃ©quentielle en effectuant une optimisation n\oe ud par n\oe ud et non une optimisation au niveau du contour complet.    
+
   
 \begin{figure}
   \centering
-  \subfigure[Contour de rÃ©fÃ©rence.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu1.png}}\quad
-\subfigure[DÃ©placement du n\oe ud $N_1$. Le critÃ¨re est amÃ©liorÃ©.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu2.png}}\quad
-\subfigure[DÃ©placement du n\oe ud $N_2$. Le critÃ¨re est amÃ©liorÃ©.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu3.png}}\\
-\subfigure[DÃ©placement en parallÃ¨le de tous les n\oe uds. Les segments du contour n'ont pas Ã©tÃ© Ã©valuÃ©s. On ne peut pas dire, a priori si le critÃ¨re est amÃ©liorÃ©.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu1.png}}\quad
-\subfigure[DÃ©placement en parallÃ¨le des n\oe uds impairs. Le critÃ¨re est amÃ©liorÃ©.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu2.png}}\quad
-\subfigure[DÃ©placement en parallÃ¨le des n\oe uds pairs. Un seul segment n'a pas Ã©tÃ© Ã©valuÃ©.]{\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu3.png}}
-\label{fig-cycle-contribs-segments}
+  \subfigure[Contour de rÃ©fÃ©rence.]{\label{fig-cycle-contribs-segments-a}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu1.png}}\quad
+\subfigure[DÃ©placement du n\oe ud $N_1$. Le critÃ¨re est amÃ©liorÃ©.]{\label{fig-cycle-contribs-segments-b}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu2.png}}\quad
+\subfigure[DÃ©placement du n\oe ud $N_2$. Le critÃ¨re est amÃ©liorÃ©.]{\label{fig-cycle-contribs-segments-c}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-cpu3.png}}\\
+\subfigure[DÃ©placement en parallÃ¨le de tous les n\oe uds. Les segments du contour n'ont pas Ã©tÃ© validÃ©s. On doit recalculer le critÃ¨re aprÃ¨s les dÃ©placements pour savoir s'il a Ã©tÃ© amÃ©liorÃ©.]{\label{fig-cycle-contribs-segments-d}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu1.png}}\quad
+\subfigure[DÃ©placement en parallÃ¨le des n\oe uds impairs. Le critÃ¨re est amÃ©liorÃ©.]{\label{fig-cycle-contribs-segments-e}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu2.png}}\quad
+\subfigure[DÃ©placement en parallÃ¨le des n\oe uds pairs. Un seul segment n'a pas Ã©tÃ© Ã©valuÃ©.]{\label{fig-cycle-contribs-segments-f}\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cycle-contribs-segments-gpu3.png}}
   \caption{Comparaison des cycles de dÃ©placement des n\oe uds. Ligne du haut : version sÃ©quentielle. Ligne du bas : version parallÃ¨le. Les segments en rouge sont des segments du contour non Ã©valuÃ©s, alors que ceux en pointillÃ©s sont les paires ayant reÃ§u les meilleures Ã©valuations parmi les 8 dÃ©placements possibles des n\oe uds correspondant.}
+\label{fig-cycle-contribs-segments}
 \end{figure}
 
-La reprÃ©sentation en mÃ©moire des segments conduit Ã  avoir un certain nombre non prÃ©visible de threads inactifs dans la grille, sans que cela soit prÃ©judiciable aux performances car cela n'engendre pas de branches divergentes. 
+La reprÃ©sentation en mÃ©moire des segments conduit Ã  avoir un certain nombre non prÃ©visible de threads inactifs dans la grille, sans que cela soit prÃ©judiciable aux performances car cela n'engendre pas de branches d'exÃ©cution divergentes, qui sont Ã  proscrire sur GPU. 
 
-Les calculs liÃ©s Ã  l'Ã©valuation des contributions des pixels sont rÃ©alisÃ©s en mÃ©moire partagÃ©e. Seule une trÃ¨s petite quantitÃ© de donnÃ©es doit Ãªtre stockÃ©e en mÃ©moire globale. Il s'agit, pour chaque segment (pas pixel) :
+Les calculs liÃ©s Ã  l'Ã©valuation des contributions des pixels sont rÃ©alisÃ©s en mÃ©moire partagÃ©e. Seule une trÃ¨s petite quantitÃ© de donnÃ©es doit Ãªtre stockÃ©e en mÃ©moire globale. Il s'agit, pour chaque {\bf segment} :
 \begin{itemize}
-\item des coordonnÃ©es de son milieu. Cela permet l'ajout efficace quand c'est nÃ©cessaire.
+\item des coordonnÃ©es de son milieu. Cela permet l'ajout de n\oe ud quand c'est possible, sans calcul supplÃ©mentaire.
 \item les coordonnÃ©es des deux derniers pixels de chaque extrÃ©mitÃ©. Ils sont nÃ©cessaires pour calculer la dÃ©rivÃ©e aux extrÃ©mitÃ©s et ainsi dÃ©terminer le code de Freeman des n\oe uds.      
 \end{itemize}
 
-Pour obtenir les contributions des segments, \textit{i.e} les sommes des contributions des leurs pixels, une premiÃ¨re phase de rÃ©duction partielle est effectuÃ©e au niveau de chaque bloc.
+Pour obtenir les contributions des segments, c'est-Ã -dire les sommes des contributions des leurs pixels, une premiÃ¨re phase de rÃ©duction partielle est effectuÃ©e au niveau de chaque bloc.
+
+Une synchronisation est alors nÃ©cessaire avant d'effectuer les sommes de l'ensemble des contributions partielles qui fournissent les contributions globales des segments. Le contour modifiÃ© est alors construit comme la suite des meilleures positions dÃ©terminÃ©es pour chaque n\oe ud, pour peu que ces nouvelles positions ne gÃ©nÃ¨rent pas de croisement de segments. 
 
-Une synchronisation est alors nÃ©cessaire avant d'effectuer les sommes de l'ensemble des contributions partielles qui fournissent les contributions globales des segments. Le contour modifiÃ© est alors construit comme la suite des meilleures positions dÃ©terminÃ©es pour chaque n\oe ud.
-Un calcul des statistiques globales du nouveau contour ainsi que du critÃ¨re $GL$ est alors nÃ©cessaire et applique Ã  nouveau les techniques dÃ©crites dans ce paragraphe.  
-Enfin l'ajout des nouveaux n\oe uds se fait simplement pour les segments suffisamment grands, en utilisant les coordonnÃ©es des pixels milieux mÃ©morisÃ©es lors de la discrÃªtisation des segments. 
+La solution retenue pour vÃ©rifier l'absence de croisement est celle de l'implÃ©mentation sÃ©quentielle, parallÃ©lisÃ©e simplement par paire de segments. Cela n'apporte pas de vÃ©ritable gain de performance par rapport Ã  la version CPU, mais, contraints de conserver les donnÃ©es en mÃ©moire GPU pour limiter les transferts entre l'hÃ´te et son pÃ©riphÃ©rique, nous avons fait en sorte que cette fonctionnalitÃ© ne grÃ¨ve pas les performances globales.
+
+Les valeurs obtenues aprÃ¨s dÃ©termination du nouveau contour, calcul des statistiques globales et Ã©valuation du critÃ¨re $GL$, servent de rÃ©fÃ©rence pour les prochaines dÃ©formations du contour. Les techniques appliquÃ©es pour ces calculs sont de nouveau celles dÃ©crites au dÃ©but ce paragraphe.  
+Enfin, l'ajout des nouveaux n\oe uds se fait simplement,  pour les segments suffisamment grands, en utilisant les coordonnÃ©es des pixels milieux mÃ©morisÃ©es lors de la discrÃ©tisation des segments. 
 
 
 \subsubsection{Cas particulier des segments dont la pente $k$ vÃ©rifie $|k|\leq 1$}
-Comme nous venons de le voir, les segments dont la pente $k$ vÃ©rifie $|k|\leq 1$ sont discrÃªtisÃ©s Ã  raison de \textit{1 pixel par colonne} et comportent donc le plus souvent plusieurs pixels sur une ligne donnÃ©e, comme le montrent les schÃ©mas de la figure \ref{fig-segment-k<1}. 
-D'aprÃ¨s la formulation gÃ©nÃ©rale du snake faite au paragraphe \ref{snake-formulation}, le coefficient $C(i,j)$ est Ã  appliquer en chaque point du contour. La technique de discrÃªtisation employÃ©e conduit Ã  des coefficients $C(i,j)$ constants sur l'ensemble des pixels des segments dont la pente $k$ vÃ©rifie  $|k|> 1$, mais ce n'est pas le cas pour ceux dont la pente $k$ est infÃ©rieure ou Ã©gale Ã  $1$. Les quatre cas, un par quadrant, qui peuvent se prÃ©senter sont reprÃ©sentÃ©s Ã  la figure \ref{fig-segment-k<1}. On y constate en se reportant Ã  la table \ref{tab-freeman} que tout pixel dont les voisins immÃ©diats sont sur la mÃªme ligne Ã  un coefficient $C(i,j)=0$ ($F_{in}=f_{out}=0$). Les deux pixels des extrÃ©mitÃ©s, n'ayant quant Ã  eux qu'un voisin, ont un coefficient qui dÃ©pend du quadrant :
+Comme nous venons de le voir, les segments dont la pente $k$ vÃ©rifie $|k|\leq 1$ sont discrÃ©tisÃ©s Ã  raison de \textit{1 pixel par colonne} et comportent donc le plus souvent plusieurs pixels sur une ligne donnÃ©e, comme le montrent les schÃ©mas de la figure \ref{fig-segment-k<1}. 
+
+D'aprÃ¨s la formulation gÃ©nÃ©rale du snake faite au paragraphe \ref{snake-formulation}, le coefficient $C(i,j)$ est Ã  appliquer en chaque point du contour. La technique de discrÃ©tisation employÃ©e conduit Ã  des coefficients $C(i,j)$ constants sur l'ensemble des pixels des segments dont la pente $k$ vÃ©rifie  $|k|> 1$, mais ce n'est pas le cas pour ceux dont la pente $k$ est infÃ©rieure ou Ã©gale Ã  $1$. Les quatre cas, un par quadrant, qui peuvent se prÃ©senter sont reprÃ©sentÃ©s Ã  la figure \ref{fig-segment-k<1}. 
+
+D'un point de vue opÃ©rationnel, on constate en se reportant Ã  la table \ref{tab-freeman}, que tout pixel dont les voisins immÃ©diats sont sur la mÃªme ligne, Ã  un coefficient $C(i,j)=0$ ($F_{in}=f_{out}=0$). Les deux pixels des extrÃ©mitÃ©s, n'ayant qu'un voisin sur la mÃªme ligne, ont un coefficient qui dÃ©pend du quadrant :
 \begin{itemize}
 \item dans les quandrant  1 et 2
   \begin{itemize}
@@ -426,7 +454,116 @@ D'aprÃ¨s la formulation gÃ©nÃ©rale du snake faite au paragraphe \ref{snake-formu
    \end{itemize}
 \end{itemize}
 
-Les accÃ¨s en mÃ©moire aux contributions de ces pixels dans les images cumulÃ©es sont Ã©vitÃ©s et une contribution nulle leur est automatiquement attribuÃ©e dÃ¨s l'Ã©tape de discrÃªtisation au sein du kernel \texttt{GPU\_compute\_segments\_contribs()}.
+\begin{figure}
+  \centering
+  \subfigure[Quadrants 1 et 4]{\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels2.png}}\quad
+  \subfigure[Quadrants 2 et 3]{\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels1.png}}\\
+  \subfigure{\includegraphics[width=8cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels3.png}}
+  \caption{DÃ©termination des coefficients $C(i,j)$ des pixels du contour.}
+\label{fig-segment-k<1}
+\end{figure}
+
+Les accÃ¨s en mÃ©moire aux contributions des pixels de coefficient $C(i,j)=0$, dans les images cumulÃ©es, sont Ã©vitÃ©s et une contribution nulle leur est automatiquement attribuÃ©e dÃ¨s l'Ã©tape de discrÃ©tisation au sein du kernel \texttt{GPU\_compute\_segments\_contribs()}.
+
+
+\subsection{Performances}
+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_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 des donnÃ©es du contour lui-mÃªme : coordonnÃ©es des n\oe uds, des milieux des segments, codes de Freeman.   
+
+Sur un GPU de type C1060 disposant de 3~Go de mÃ©moire, cela permet de traiter des images jusqu'Ã  presque 150 millions de pixels.
+Il est possible de rÃ©duire cette empreinte jusqu'Ã  13 octets par pixel, mais cela soulÃ¨ve la question de l'alignement des donnÃ©es en mÃ©moire, sans objet si on emploie les types entier et entier long (32 et 64 bits) pour la reprÃ©sentation des donnÃ©es et qui permet de prÃ©server les performances maximales des opÃ©rations et des accÃ¨s aux donnÃ©es du GPU. On pourrait tout de mÃªme porter ainsi la limite de taille de l'image d'entrÃ©e Ã  230 millions de pixels.
+
+Comme l'heuristique d'optimisation appliquÃ©e Ã  l'implÃ©mentation parallÃ¨le conduit Ã  la crÃ©ation de certains segments non validÃ©s au prÃ©alable (voir fig. \ref{fig-cycle-contribs-segments}), notre implÃ©mentation peut converger plus tÃ´t que la version de rÃ©fÃ©rence CPU, gÃ©nÃ©ralement une itÃ©ration avant.
+
+Les comparaisons visuelles et de valeur du critÃ¨re final $GL$ aprÃ¨s convergence nous renseignent toutefois sur la qualitÃ© de la segmentation obtenue avec des solutions trÃ¨s voisines de celles de la version de rÃ©fÃ©rence.
+
+La figure \ref{fig-snakegpu-result} prÃ©sente une segmentation effectuÃ©e sur une image de 100 millions de pixels. La table \ref{tab-snake-results} rÃ©sume les performances obtenues pour diffÃ©rentes tailles de la mÃªme image. Une implÃ©mentation CPU multi threads permettrait d'accÃ©lÃ©rer significativement le calcul des images cumulÃ©es. Nous n'avons pas toutefois Ã©valuÃ© l'accÃ©lÃ©ration rÃ©elle qu'une telle solution apporterait. En revanche, on peut affirmer que l'emploi du GPU reste pertinent car aucune solution multi threads classique n'est envisageable pour implÃ©menter la partie segmentation de l'algorithme, la plus coÃ»teuse en temps de calcul et donc celle qu'il est le plus judicieux de parallÃ©liser.
+   
+\begin{table}[h]
+  \centering
+  \begin{tabular}{rrrrr}
+      \toprule
+      &&\multicolumn{3}{c}{Performances}\\
+      \cmidrule(r){3-5}
+      && CPU & GPU & CPU/GPU \\
+      \midrule
+                     & {\bf total}      &{\bf 0,51 s}&{\bf 0,06 s}&{\bf x8,5}\\
+      Image 15~MP    & images cumulÃ©es  &0,13 s&0,02 s&x6,5\\
+                     & segmentation     &0,46 s&0,04 s&x11,5\\
+      \midrule
+                     & {\bf total}      &{\bf 4,08 s}&{\bf 0,59 s}&{\bf x6,9}\\
+      Image 100~MP   & images cumulÃ©es  &0,91 s&0,13 s&x6,9\\
+                     & segmentation     &3,17 s&0,46 s&x6,9\\
+      \midrule
+                     & {\bf total}      &{\bf 5,70 s}&{\bf 0,79 s}&{\bf x7,2}\\
+      Image 150~MP   & images cumulÃ©es  &1,40 s&0,20 s&x7,0\\
+                     & segmentation     &4,30 s&0,59 s&x7,3\\
+
+      \bottomrule
+\end{tabular}
+   \caption{Comparaison des temps d'exÃ©cution de l'implÃ©mentation GPU (C2070) par rapport Ã  l'implÃ©mentation CPU (mono thread) de rÃ©fÃ©rence, pour une mÃªme image dilatÃ©e (fig. \ref{fig-snakecpu-cochon512}) pour en adapter la taille.}
+      \label{tab-snake-results}
+\end{table} 
+
+\begin{figure}
+  \centering
+  {\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/cochon_it5_points.png}}
+%\quad
+%\subfigure[3 itÃ©rations en 0,35~s]{\includegraphics[height=5cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/Montserrat_3it.png}}
+  \caption{Segmentations d'une image de 100~MP en 0,59~s pour 5 itÃ©rations. Le contour initial conserve les proportions de celui de la figure \ref{fig-snakecpu-cochon512}. }
+\label{fig-snakegpu-result}
+\end{figure}
+
+\subsection{DÃ©termination du contour initial au sens du maximum de vraisemblance}
+Nous avons dÃ©jÃ  discutÃ© de l'influence du contour initial sur le rÃ©sultat de la segmentation, mais il faut ajouter que la durÃ©e d'exÃ©cution est aussi impactÃ©e par ce choix, dans des proportions qui peuvent Ãªtre importantes selon la distance, la taille et dans une moindre mesure la forme de la cible.
+
+Ces effets se mesurent lors de la premiÃ¨re itÃ©ration, celle qui va cerner grossiÃ¨rement la cible avec un contour Ã  quatre n\oe uds. Si le contour initial se trouve trÃ¨s Ã©loignÃ©, comme dans la situation de la figure \ref{fig-snakecpu-cochon4kc3}, notre choix maintenant habituel d'un rectangle prÃ¨s des bords de l'image s'avÃ¨re peu adaptÃ© et conduit Ã  une premiÃ¨re itÃ©ration trÃ¨s longue. Dans un tel cas, pour une image de 10000$\times$10000 pixels, si la cible est un carrÃ© de 1000$\times$1000 pixels dont le sommet du bas Ã  droite se confond avec celui du contour et que l'on approche par pas de 64 pixels, on devra dans le meilleur des cas dÃ©placer les 4 n\oe uds du contour 110 fois de suite avant de pouvoir passer Ã  la deuxiÃ¨me itÃ©ration. Un pas de 128 permet de rÃ©duire ces valeurs, mais l'expÃ©rience montre qu'au delÃ , l'approche initiale de la cible est trop grossiÃ¨re et les itÃ©rations suivantes en pÃ¢tissent pour un rÃ©sultat souvent dÃ©gradÃ©.
+En revanche, si les proportions sont celles de la figure \ref{fig-snakecpu-cochon512}, seules 31 passes de dÃ©placement des 4 n\oe uds initiaux sont nÃ©cessaires.
+
+Pour optimiser l'initialisation, nous avons donc proposÃ© de tirer parti du GPU pour Ã©valuer une grande quantitÃ© de contours initiaux rectangulaires et rÃ©duire ainsi le coÃ»t de la premiÃ¨re itÃ©ration. Pour pouvoir employer la mÃ©moire partagÃ©e comme tampon de donnÃ©es, il faut limiter le nombre de contours Ã  Ã©valuer. Nous avons donc effectuÃ© un Ã©chantillonnage spatial des images et dÃ©terminÃ© le contour initial en deux temps, en mettant Ã  profit la propriÃ©tÃ© qu'ont les segments horizontaux d'avoir une contribution nulle, comme on peut le vÃ©rifier en se reportant Ã  la figure \ref{fig-freeman} et Ã  la table \ref{tab-freeman}. Le principe mis en \oe uvre, illustrÃ© par la figure \ref{fig-smart-init} est le suivant :
+\begin{enumerate}
+\item on rÃ©alise un Ã©chantillonnage horizontal pour ne considÃ©rer que les colonnes d'indice $j=8k$.
+\item on Ã©value alors tous les contours rectangulaires de diagonale $(0, j_L)-(J_H, H)$
+\item on identifie le contour prÃ©sentant le meilleur critÃ¨re $GL$, ce qui dÃ©termine $j_L$ et $j_H$.
+\item on fait de mÃªme en Ã©chantillonnant verticalement : les lignes d'indice $i=8t$ permettent de dÃ©crire tous les contours de diagonale $(i_L, j_L)-(i_H, j_H)$. Le meilleur contour est celui retenu pour l'initialisation de la segmentatation.  
+\end{enumerate}
+
+Le gain de  performance apportÃ© par cette stratÃ©gie d'initialisation est variable selon la cible, mais dans des situations favorables comme celle de l'image de la figure \ref{fig-snakecpu-cochon4kc3}, on parvient Ã  une accÃ©lÃ©ration proche de 15 alors qu'elle n'est que d'environ 7 avec l'initialisation basique. Cette proportion est conservÃ©e pour les tailles supÃ©rieures et signifie que la phase de segmentation est tout de mÃªme effectuÃ©e 30 fois plus rapidement qu'avec l'implÃ©mentation CPU, grÃ¢ce Ã  une premiÃ¨re itÃ©ration optimisÃ©e.  
+
+\begin{figure}
+  \centering
+  \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 du contour initial au sens du maximum de vraisemblance, par 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}
+Nous avons conÃ§u une implÃ©mentation parallÃ¨le de \textit{snake} polygonal orientÃ© rÃ©gions, ce qui n'avait pas encore Ã©tÃ© rÃ©alisÃ©, n'ayant recensÃ© Ã  ce jour aucune publication y faisant rÃ©fÃ©rence. Elle a fait l'objet d'une publication et d'une communication Ã  la confÃ©rence \textit{Computer and Information Technology} (voir \cite{6036776}).
+Les objectifs Ã©taient d'Ã©tendre les capacitÃ©s de traitement de l'implÃ©mentation CPU de rÃ©fÃ©rence en terme de taille d'image en conservant des temps d'exÃ©cution acceptables ce qui, de l'avis des auteurs de la version CPU, impose de se situer \textit{a minima} sous la seconde pour pouvoir envisager l'intÃ©gration dans une application interactive.
+
+Sur ce point, les performances de notre version sont satisfaisantes, puisque nous avons repoussÃ© la limite de taille de 16 Ã  150 millions de pixels et parvenons Ã  segmenter ces grandes images en moins d'une seconde. Le temps de calcul dÃ©pend trÃ¨s fortement du contenu de l'image et la segmentation est le plus souvent obtenue en un temps plus court.
+
+L'emploi du GPU dans notre implÃ©mentation ne parvient pas Ã  Ãªtre optimal car, par essence, la rÃ©partition des pixels d'intÃ©rÃªt est mouvante et ne permet pas de construire des accÃ¨s mÃ©moire coalescents. Les opÃ©rations de type rÃ©duction sont Ã©galement  nombreuses et ne sont pas les plus efficaces sur GPU. Dans notre situation, elles peuvent mÃªme reprÃ©senter une perte de performances, car effectuÃ©es sur des vecteurs de tailles insuffisantes.  
+
+S'il s'agit de parler d'accÃ©lÃ©ration, notre implÃ©mentation divise les temps de traitement prÃ©cÃ©dents par un facteur allant de 6 Ã  15 selon l'image et le contour initial adoptÃ©. Rappelons encore que l'implÃ©mentation CPU de rÃ©fÃ©rence n'est pas une implÃ©mentation naÃ¯ve, mais une solution optimisÃ©e employant dÃ©jÃ  les capacitÃ©s de parallÃ©lisme des microprocesseurs modernes et affichant les performances les plus Ã©levÃ©es dans ce domaine ; il n'Ã©tait pas trivial d'en surpasser les performances, mÃªme avec un GPU.     
+
+Par nÃ©cessitÃ©, notre solution s'Ã©carte cependant quelque peu de l'algorithme original pour permettre les dÃ©placements simultanÃ©s des sommets d'indices pairs, puis impairs, du polygone. Ce faisant, on observe parfois la convergence de notre solution Ã  l'avant derniÃ¨re Ã©tape de la segmentation rÃ©alisÃ©e par la version sÃ©quentielle de rÃ©fÃ©rence itÃ©ration, sans que cela n'influe significativement sur la qualitÃ©. En effet, seuls quelques n\oe uds voient leur position potentiellement modifiÃ©e d'un seul pixel (le pas de dÃ©placement des derniÃ¨res Ã©tapes) et le contour obtenu ne s'Ã©loigne donc que trÃ¨s peu du contour obtenu par l'algorithme de rÃ©fÃ©rence.
+
+La technique que nous avons proposÃ©e pour la dÃ©termination intelligente du contour initial permet d'augmenter encore les performances, surtout dans les grandes images lorsque la cible est petite vis-Ã -vis des dimensions de l'image. Il reste toutefois Ã  concevoir une technique permettant de prÃ©voir si cette recherche de contour initial serait gÃ©nÃ©ratrice de gain de performance. 
+
+L'analyse fine des sÃ©quences de segmentation montre enfin que les premiÃ¨re Ã©tapes, qui mettent en \oe uvre les segments les plus longs, gÃ©nÃ¨rent des grilles de calcul suffisamment chargÃ©es et homogÃ¨nes pour prÃ©senter de bonnes performances. Les derniÃ¨res Ã©tapes, en revanche, traitent un grand nombre de petits segments, gÃ©nÃ©rant beaucoup de trous dans la grille de calcul et induisant des performances moindres. 
+
+Pour rÃ©sumer, l'accÃ©lÃ©ration globale obtenue est principalement dÃ©terminÃ©e par le calcul des images cumulÃ©es et des toutes premiÃ¨res Ã©tapes de dÃ©placements. Une possibilitÃ© Ã  explorer serait de construire une version hybride rÃ©alisant le dÃ©but de la segmentation sur GPU, puis la terminant sur le CPU hÃ´te. Ceci est envisageable en raison du trÃ¨s petit volume de donnÃ©es Ã  transfÃ©rer que constituent les paramÃ¨tres du contour (2~ko pour 100 n\oe uds). Cette Ã©tude nous conforte Ã©galement dans l'idÃ©e que la transposition pour GPU d'algorithmes sÃ©quentiels optimisÃ©s pour CPU, malgrÃ© des adaptations Ã  l'architecture, ne semble pas Ãªtre la dÃ©marche permettant d'atteindre les niveaux de performances attendus lorsqu'on met en \oe uvre ces processeurs graphiques. 
+
+
+
+ 
 
 
 
