X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/e81bd9912542bc52e4b0fd1206e0b6f9b93a5fda..1171799649e99aa6b7222c9f180de7523e5e7da4:/THESE/Chapters/chapter3/chapter3.tex?ds=sidebyside

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index bae9ff9..8082daa 100644
--- 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.
-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.
-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}
@@ -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}$.
-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}
@@ -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}
-   \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}
@@ -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}$\;
-   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$ }
+	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}\;
 	  \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$ }\;
-   $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}
 
-\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$.
-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}}
@@ -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}}
-  \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 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
@@ -254,9 +253,10 @@ La dÃ©pendance vis Ã  vis du contour initial, qui est un des principaux soucis l
   \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.
+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
@@ -289,12 +289,12 @@ Au delÃ  des 16 millions de pixels (4000$\times$4000 pixels), l'implÃ©mentation
       {\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. 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. 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 \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,27 +319,27 @@ 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}   
-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 :
+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, la \textit{prefixsum} inclusive de chaque bloc, puis qui en mÃ©morise la 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{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$. 
 \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_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}
 
-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}[h]
@@ -363,7 +363,7 @@ On obtient des accÃ©lÃ©rations supÃ©rieures en rendant le calcul moins gÃ©nÃ©riq
 
 \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 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. 
@@ -402,7 +402,7 @@ La seconde ligne prÃ©sente l'ordre dans lequel sont concatÃ©nÃ©s les 16 groupes
 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.   
+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}
@@ -421,7 +421,7 @@ La reprÃ©sentation en mÃ©moire des segments conduit Ã  avoir un certain nombre n
 
 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 de n\oe ud quand c'est possible.
+\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}
 
@@ -470,19 +470,20 @@ 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).
-\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.).   
+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.
 
-La convergence de notre implÃ©mentation intervient en un nombre gÃ©nÃ©ralement plus rÃ©duit d'itÃ©rations vers un contour final qui diffÃ¨re par essence de celui obtenu avec la solution de rÃ©fÃ©rence. Ces effets sont la consÃ©quence dÃ©jÃ  abordÃ©e de l'heuristique d'optimisation appliquÃ©e Ã  l'implÃ©mentation parallÃ¨le qui conduit Ã  la crÃ©ation de certains segments non validÃ©s au prÃ©alable (voir fig. \ref{fig-cycle-contribs-segments}).
+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 $GL$ qui peuvent Ãªtre faites pour les images de taille infÃ©rieure Ã  4096$\times$4096 pixels nous renseignent toutefois sur la qualitÃ© de la segmentation obtenue. Pour les tailles au delÃ  et jusqu'au maximum de 12000$\times$12000 pixels, le comportement est globalement conservÃ©, mais on note qu'il n'est pas pertinent de permettre des tailles de segments trop petites vis-Ã -vis de la taille d'image. Les dÃ©placements des n\oe uds ne gÃ©nÃ©rent alors plus de variations significatives des contributions correspondantes.
+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.
+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}
@@ -505,7 +506,7 @@ La figure \ref{fig-snakegpu-result} prÃ©sente une segmentation effectuÃ©e sur un
 
       \bottomrule
 \end{tabular}
-   \caption{Comparaison des temps d'exÃ©cution de l'implÃ©mentation GPU (C2070) par rapport Ã  l'implÃ©mentation CPU de rÃ©fÃ©rence, appliquÃ©s Ã  une mÃªme image dilatÃ©e (fig. \ref{fig-snakecpu-cochon512}) pour en adapter la taille.}
+   \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} 
 
@@ -518,10 +519,10 @@ La figure \ref{fig-snakegpu-result} prÃ©sente une segmentation effectuÃ©e sur un
 \label{fig-snakegpu-result}
 \end{figure}
 
-\subsection{DÃ©termination intelligente du contour initial}
+\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 polygone Ã  quatre cotÃ©s. 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Ã©.
+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 :
@@ -532,14 +533,14 @@ Pour optimiser l'initialisation, nous avons donc proposÃ© de tirer parti du GPU
 \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 initialisation \og intelligente \fg{} est naturellement trÃ¨s 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.  
+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 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 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}
@@ -552,13 +553,14 @@ L'emploi du GPU dans notre implÃ©mentation ne parvient pas Ã  Ãªtre optimal car,
 
 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 de l'ensemble des sommets du polygone. Ce faisant, la dÃ©croissance du critÃ¨re n'est pas certaine Ã  toutes les Ã©tapes de la segmentation et l'on observe cette consÃ©quence, en particulier lors des derniÃ¨re itÃ©rations lorsque le pas de dÃ©placement ainsi que les variations du critÃ¨re sont faibles. Ce comportement  provoque parfois la convergence prÃ©maturÃ©e de la segmentation, mais n'influe toutefois que sur quelques n\oe uds et le contour ainsi obtenu ne s'Ã©loigne que trÃ¨s peu du contour obtenu par l'algorithme de rÃ©fÃ©rence.
+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 intelligente serait gÃ©nÃ©ratrice de gain de performance. 
+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).
+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. 
+
 
 
  
