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

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index bae9ff9..52b00b7 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]{en parallÃ¨le via SSE2} 
    $n \leftarrow 0$ \tcc*[r]{indice de boucle niveau contour}
    $N_n \leftarrow 4$ \tcc*[r]{nombre de n\oe uds}
    $\Gamma \leftarrow \{\Gamma_0,\Gamma_1,\Gamma_2,\Gamma_3\} $\;
    $d \leftarrow d_{max}$ \tcc*[r]{pas de dÃ©placement des n\oe uds}
    $l_{min} = 32$ \tcc*[r]{longueur mini des segments sÃ©cables}
    $\Gamma_i \leftarrow \Gamma_0$ \tcc*[r]{sommet courant}
-   $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,7 +253,8 @@ 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.
 
@@ -294,7 +294,7 @@ Au delÃ  des 16 millions de pixels (4000$\times$4000 pixels), l'implÃ©mentation
 \end{table}
 
 
-Enfin, il faut aussi considÃ©rer les tailles relatives de la cible et de l'image. Ainsi, si on fait l'hypothÃ¨se d'une cible de petite taille \og noyÃ©e \fg{} dans une image de grandes dimensions, les rÃ©sultats de la segmentation seront impactÃ©s en raison, cette fois, d'une moindre adaptation Ã  la cible lors des toutes premiÃ¨res itÃ©rations, les plus grossiÃ¨res, oÃ¹ le nombre de n\oe uds est rÃ©duit et le pas de dÃ©placement potentiellement grand vis Ã  vis de la cible. Ce cas de figure est illustrÃ© par la segmentation reproduite Ã  la figure \ref{fig-snakecpu-cochon4kc3} et qui met en Ã©vidence une qualitÃ© moindre par la confusion des zones les plus sombres de la cible avec le fond.
+Enfin, il faut aussi considÃ©rer les tailles relatives de la cible et de l'image. Ainsi, si on fait l'hypothÃ¨se d'une cible de petite taille \og noyÃ©e \fg{} dans une image de grandes dimensions, les rÃ©sultats de la segmentation seront impactÃ©s en raison, cette fois, d'une moindre adaptation Ã  la cible lors des toutes premiÃ¨res itÃ©rations, les plus grossiÃ¨res, oÃ¹ le nombre de n\oe uds est rÃ©duit et le pas de dÃ©placement potentiellement grand vis Ã  vis de la cible. Ce cas de figure est illustrÃ© par la segmentation reproduite Ã  la figure \ref{fig-snakecpu-cochon4kc3} et qui met en Ã©vidence une qualitÃ© moindre par la confusion des zones les plus sombres de la cible avec le fond et confirme ainsi la nÃ©cessitÃ© d'adapter la stratÃ©gie d'optimisation au problÃ¨me posÃ©.
 
 
 
@@ -319,7 +319,7 @@ Si l'effort de parallÃ©lisation porte essentiellement sur ces fonctions coÃ»teus
 Les traitements Ã©tant totalement indÃ©pendants, nous traitons sÃ©parÃ©ment la parallÃ©lisation des prÃ©-calculs et celle de la segmentation.
 
 \subsection{PrÃ©-calculs des images cumulÃ©es}   
-Pour rÃ©duire la quantitÃ© de mÃ©moire requise, nous avons choisi de ne pas gÃ©nÃ©rer l'image $S_1$ mais plutÃ´t d'en calculer les valeurs Ã  la volÃ©e. L'expression en est simple et le temps pris par les opÃ©rations Ã©lÃ©mentaires qu'elle met en jeu est largement compensÃ© par le gain obtenu en Ã©conomisant les accÃ¨s mÃ©moire qui auraient Ã©tÃ© nÃ©cessaires, ce qui n'est pas le cas des deux autres images $S_x$ et $S_x^2$ dont le calcul est quant Ã  lui rÃ©alisÃ© en appliquant une variante de la mÃ©thode des sommes prÃ©fixÃ©es (\textit{prefixsums}) dÃ©crite dans \cite{BlellochTR90} et qui permet d'Ã©valuer les expressions de l'Ã©quation \eqref{eq-img-cumul}.
+Pour rÃ©duire la quantitÃ© de mÃ©moire requise, nous avons choisi de ne pas gÃ©nÃ©rer l'image $S_1$ mais plutÃ´t d'en calculer les valeurs Ã  la volÃ©e. L'expression en est simple et le temps pris par les opÃ©rations Ã©lÃ©mentaires qu'elle met en jeu est largement compensÃ© par le gain obtenu en Ã©conomisant les accÃ¨s mÃ©moire qui auraient Ã©tÃ© nÃ©cessaires, ce qui n'est pas le cas des deux autres images $S_I$ et $S_I^2$ dont le calcul est quant Ã  lui rÃ©alisÃ© en appliquant une variante de la mÃ©thode des sommes prÃ©fixÃ©es (\textit{prefixsums}) dÃ©crite dans \cite{BlellochTR90} et qui permet d'Ã©valuer les expressions de l'Ã©quation \eqref{eq-img-cumul}.
 
 Les sommations se font au niveau de chaque ligne de l'image, que l'on dÃ©compose en $n$ blocs de $bs$ pixels oÃ¹ $bs$ correspond aussi au nombre de threads exÃ©cutÃ©s par chaque bloc de la grille de calcul. La valeur $bs$ Ã©tant obligatoirement une puissance de 2 supÃ©rieure Ã  32, le bloc de pixels d'indice $n-1$ doit Ã©ventuellement Ãªtre complÃ©tÃ© par des valeurs nulles. Chaque bloc de thread rÃ©alise son traitement indÃ©pendemment des autres, mais l'ensemble des sommes de bloc Ã©tant requise pour le calcul des sommes globales, une synchronisation est nÃ©cessaire Ã  deux endroits du calcul. Nous avons choisi d'assurer ces synchronisations en dÃ©coupant le traitement en trois \textit{kernels} distincts, rendant par la mÃªme occasion le code plus concis :
 \begin{itemize}
@@ -328,14 +328,14 @@ Les sommations se font au niveau de chaque ligne de l'image, que l'on dÃ©compose
 \item \texttt{add\_sums2prefixes()} est le \textit{kernel} effectuant les additions de chaque Ã©lÃ©ment d'indice $i$ des vecteurs $V_x$ (respectivement $V_x^2$) avec tous les Ã©lÃ©ments du prefixsum du bloc de mÃªme indice $i$. 
 \end{itemize}
 
-Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le dÃ©tail des opÃ©rations effectuÃ©es par ces trois \textit{kernels} pour l'image cumulÃ©e $S_x$. La seconde image cumulÃ©e $S_x^2$ est obtenues exactement de la mÃªme maniÃ¨re en sommant non plus les valeurs $v_k$ mais $v^2_k$.
+Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le dÃ©tail des opÃ©rations effectuÃ©es par ces trois \textit{kernels} pour l'image cumulÃ©e $S_I$. La seconde image cumulÃ©e $S_{I^2}$ est obtenues exactement de la mÃªme maniÃ¨re en sommant non plus les valeurs $v_k$ mais $v^2_k$.
 
 \begin{figure}
   \centering
   \subfigure[DÃ©tail des opÃ©rations effectuÃ©es par le \textit{kernel} \texttt{compute\_block\_prefixes()}. La valeur $bs$ correspond au nombre de pixels de chaque bloc, qui est aussi le nombre de threads exÃ©cutÃ© par chaque bloc de la grille de calcul.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUcumuls.pdf_t}}}\vspace{1cm}
 \subfigure[DÃ©tail des opÃ©rations effectuÃ©es par le \textit{kernel} \texttt{scan\_blocksums()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUscansomblocs.pdf_t}}}\vspace{1cm}
 \subfigure[DÃ©tail des opÃ©rations effectuÃ©es par le \textit{kernel} \texttt{add\_sums2prefixes()}.]{\resizebox{0.9\linewidth}{!}{ \input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/GPUaddsoms2cumuls.pdf_t}}}
-  \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}
 
@@ -470,8 +470,8 @@ Les accÃ¨s en mÃ©moire aux contributions des pixels de coefficient $C(i,j)=0$, d
 Dans l'hypothÃ¨se la plus contraignante d'images en niveaux de gris codÃ©s sur 16 bits, l'implÃ©mentation parallÃ¨le que nous venons de dÃ©crire utilise de maniÃ¨re permanente 20 octets par pixel de l'image d'entrÃ©e, qui se dÃ©taillent en
 \begin{itemize}
 \item l'image d'entrÃ©e pour 4 octets par pixel (1 entier).
-\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.).   
 
@@ -539,7 +539,7 @@ Le gain de  performance apportÃ© par cette initialisation \og intelligente \fg{}
   \subfigure[DÃ©termination de $j_L$ et $j_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init1.pdf_t}}}\quad
  \subfigure[DÃ©termination de $i_L$ et $i_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init2.pdf_t}}}
 \label{fig-smart-init}
-  \caption{DÃ©termination intelligente du contour initial en deux phases successives. a) La premiÃ¨re Ã©tape repose sur un Ã©chantillonnage horizontal. b) La seconde Ã©tape repose sur un Ã©chantillonnage vertical.}
+  \caption{DÃ©termination intelligente du contour initial en deux phases successives. (a) La premiÃ¨re Ã©tape repose sur un Ã©chantillonnage horizontal. (b) La seconde Ã©tape repose sur un Ã©chantillonnage vertical.}
 \end{figure}
  
 \subsection{Conclusion}
