X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/5d5e214d54eab1411ef86a32e11fccfaa53dbc45..72441aeeda78a2607a1fe941b9a3580e74b4951c:/THESE/Chapters/chapter3/chapter3.tex?ds=sidebyside

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index 89f5358..e616df8 100644
--- a/THESE/Chapters/chapter3/chapter3.tex
+++ b/THESE/Chapters/chapter3/chapter3.tex
@@ -1,10 +1,12 @@
-\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. 
 
+\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.
 On note $\Gamma$ le contour de la rÃ©gion cible ($\Gamma \in \Omega_t$), que l'on suppose continu en connexitÃ© Ã  8 voisins. 
@@ -50,7 +52,7 @@ En intÃ©grant \eqref{eq-teta} dans \eqref{eq-gl1}, il reste, Ã  une constante pr
   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}
@@ -139,14 +141,15 @@ L'intÃ©rÃªt de cette transformation est majeur :
 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.  
 
 \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}
+\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.
 
-\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\;
@@ -159,9 +162,10 @@ 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} 
    $n \leftarrow 0$ \tcc*[r]{indice de boucle niveau contour}
@@ -204,6 +208,7 @@ Un des inconvÃ©nients des algorithmes de type \textit{snake} est l'influence du
   }
 \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. 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$
@@ -229,7 +234,7 @@ Les temps d'exÃ©cution indiquÃ©s sont mesurÃ©s sur Intel Xeon E5530-2.4GHz with
  \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, 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 87~ms pour de 17 itÃ©rations et 273 n\oe uds. 
 
 \begin{figure}
   \centering
@@ -240,18 +245,26 @@ 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. 
+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. 
 
 \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$^2$ 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$^2$ pixels avec une cible de petite taille. Le contour initial est la transcription 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
@@ -267,26 +280,19 @@ 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. Seule l'image en 15~MP a pu Ãªtre traitÃ©e par une implÃ©mentation utilisant SSE2.}
       \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.
 
-\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 :
 \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 Le calcul de la contribution des segments (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 (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}).
 \end{itemize}
@@ -299,12 +305,12 @@ 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_x$ et $S_x^2$ dont le calcul est quant Ã  lui rÃ©alisÃ© en appliquant une variante de la mÃ©thode des \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 :
 \begin{itemize}
@@ -320,8 +326,8 @@ Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le dÃ©tail des opÃ©r
   \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}}}
-\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.}
+\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.
@@ -340,14 +346,14 @@ 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 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. 
 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.
@@ -362,26 +368,28 @@ 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Ã¹
 \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}
 
+
+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. 
+
+
 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}). 
   
 \begin{figure}
@@ -392,8 +400,8 @@ Aux deux derniÃ¨res lignes est dÃ©crite la concatÃ©nation des ensembles de 16 bl
 \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}
   \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. 
@@ -406,17 +414,18 @@ Les calculs liÃ©s Ã  l'Ã©valuation des contributions des pixels sont rÃ©alisÃ©s
 
 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.
 
-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, pour peu que ces nouvelles positions ne gÃ©nÃ¨rent pas de croisement de 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 tÃ¢chÃ© de faire en sorte que cette fonctionnalitÃ© ne grÃªve pas les performances globales.
+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 calculs des statistiques globales du nouveau contour et du critÃ¨re $GL$ sont effectuÃ©s aprÃ¨s l'obtention du nouveau contour. Les valeurs obtenues 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. 
+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}. 
+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 quant Ã  eux qu'un voisin sur la mÃªme ligne, ont un coefficient qui dÃ©pend du quadrant :
 \begin{itemize}
@@ -437,11 +446,11 @@ D'un point de vue opÃ©rationnel, on constate en se reportant Ã  la table \ref{ta
   \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}}
-\label{fig-segment-k<1}
   \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, dans les images cumulÃ©es, aux contributions des pixels de coefficient $C(i,j)=0$ 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()}.
+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}
@@ -451,14 +460,14 @@ Dans l'hypothÃ¨se la plus contraignante d'images en niveaux de gris codÃ©s sur 1
 \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)
 \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, milieus, 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 donnÃ©es diverses comme le contour lui-mÃªme (n\oe uds, milieux, Freemans, etc.).   
 
-Sur un GPU de type C1060 disposant de 3~Go de mÃ©moire, cela permet de traiter des image 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 qui est sans objet en employant les type 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 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.
+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 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 Ã  l'adoption de certains segments non Ã©valuÃ©s au prÃ©alable (voir fig. \ref{fig-cycle-contribs-segments}).
 
-Les comparaisons visuelle et de valeur du critÃ¨re $GL$ qui peuvent Ãªtre faites pour les images de taille infÃ©rieure Ã  4000$^2$ pixels nous renseignent toutefois sur la qualitÃ© de la segmentation obtenue. Pour les tailles au delÃ  et jusqu'au maximum de 12000$^2$ 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Ã©rant alors plus de variations significatives des contributions correspondantes.
+Les comparaisons visuelle et de valeur du critÃ¨re $GL$ qui peuvent Ãªtre faites pour les images de taille infÃ©rieure Ã  4000$^2$ pixels nous renseignent toutefois sur la qualitÃ© de la segmentation obtenue. Pour les tailles au delÃ  et jusqu'au maximum de 12000$^2$ 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Ã©rant alors plus de variations significatives des contributions correspondantes.
 
 La figure \ref{fig-snakegpu-result} prÃ©sente deux segmentations effectuÃ©es sur des images de respectivement 100 et 150 millions de pixels alors que la table \ref{tab-snake-results} rÃ©sume les performances obtenues sur l'image du \textit{cochon} en diffÃ©rentes tailles.
 \begin{table}[h]
@@ -483,7 +492,7 @@ La figure \ref{fig-snakegpu-result} prÃ©sente deux segmentations effectuÃ©es sur
 
       \bottomrule
 \end{tabular}
-   \caption{Comparaison des temps d'exÃ©cution de l'implÃ©mentation GPU par rapport Ã  l'implÃ©mentation CPU de rÃ©fÃ©rence, appliquÃ©s Ã  une mÃªme image dilatÃ©e pour en adapter la taille.}
+   \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 pour en adapter la taille.}
       \label{tab-snake-results}
 \end{table} 
 
@@ -491,11 +500,11 @@ La figure \ref{fig-snakegpu-result} prÃ©sente deux segmentations effectuÃ©es sur
   \centering
   \subfigure[5 itÃ©rations en 0,59~s]{\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 de grandes images, avec le contour intial transposÃ© de celui de la figure \ref{fig-snakecpu-cochon512}. a) image du cochon en 100~MP. b) image satellite de l'Ã®le de Montserrat en 150~MP.}
 \label{fig-snakegpu-result}
-  \caption{Segmentations de grandes images, avec le contour intial transposÃ© de celui de la figure \ref{fig-snakecpu-cochon512}. a) image de 100~MP. b) image de 150~MP.}
 \end{figure}
 
-\subsection{Discussion sur l'initialisation}
+\subsection{DÃ©termination intelligente du contour initial}
 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 le choix du contour initial, 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$^2$ pixels, si la cible est un carrÃ© de 1000$^2$ 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Ã©.
@@ -518,21 +527,20 @@ Pour optimiser l'initialisation, nous avons donc proposÃ© de tirer parti du GPU
 \end{figure} 
  
 \subsection{Conclusion}
-Nous avons conÃ§u une implÃ©mentation parallÃ¨le de \textit{snake} polygonal orientÃ© rÃ©gions, ce qui Ã  notre connaissance n'avait encore pas Ã©tÃ© rÃ©alisÃ©, aucune publication n'Ã©tant parue Ã  ce sujet.
-
+Nous avons conÃ§u une implÃ©mentation parallÃ¨le de \textit{snake} polygonal orientÃ© rÃ©gions, ce qui n'avait encore pas Ã©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 obtenu en un temps plus court, mais il n'est pas impensable que certaines situations particuliÃ¨res puissent conduire Ã  dÃ©passer cette barre symoblique.
+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 coalescent Ã  la mÃ©moire. 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 pour que le GPU surclasse le CPU.  
+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 reprÃ©sentant l'\textit{l'Ã©tat de l'art} du domaine ; il n'Ã©tait pas trivial d'en surpasser les performances, mÃªme avec un GPU.     
+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 reprÃ©sentant l'\textit{Ã©tat de l'art} du 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 l'ensemble des sommets du polygone. Ce faisant, la dÃ©croissance du critÃ¨re n'est pas certaine Ã  toutes les Ã©tapes de la segmantation et l'on observe cette consÃ©quence en particulier lors des derniÃ¨re itÃ©rations lorsque le pas de dÃ©placement et aussi les variations du critÃ¨re sont faibles. Ce comportement, lorsqu'il est observÃ©, provoque parfois la convergence prÃ©maturÃ©e de la segmentation, mais n'influe toutefois que sur quelques n\oe uds et dans la mesure d'un pixel.
+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 et aussi les variations du critÃ¨re sont faibles. Ce comportement, lorsqu'il est observÃ©, 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 de rÃ©fÃ©rence.
 
-La technique que nous avons proposÃ©e pour la dÃ©termination 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. Nous ne sommes pas parvenu Ã  concevoir une technique permettant de prÃ©voir si la recherche intelligente du contour intial 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 intelligente 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Ã¨re Ã©tapes, en revanche, traitent d'une plus grand nombre de petits segments, gÃ©nÃ©rant beaucoup de trous dans la grille de calcul et induisant des performances moindres. L'accÃ©leration globale obtenue est ainsi gÃ©nÃ©ralement le fruit du calcul des images cumulÃ©es et des toutes premiÃ¨res Ã©tapes de dÃ©placements. Une possiblitÃ© qui reste Ã  explorer serait de construire une version hybride rÃ©alisant le dÃ©but de la segmentation sur GPU, puis 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).
+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 d'un plus grand nombre de petits segments, gÃ©nÃ©rant beaucoup de trous dans la grille de calcul, induisant des performances moindres. L'accÃ©lÃ©ration globale obtenue est ainsi gÃ©nÃ©ralement le fruit du calcul des images cumulÃ©es et des toutes premiÃ¨res Ã©tapes de dÃ©placements. Une possibilitÃ© qui reste Ã  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).
 
 
  
