diapo v2

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

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index 52b00b7b5b0ce1ae0389c002a9c19c2d82eb25dc..8082daa4b8af365b76a1b0d6bb50312fc7bb8ee9 100644 (file)
--- a/THESE/Chapters/chapter3/chapter3.tex
+++ b/THESE/Chapters/chapter3/chapter3.tex
@@ -167,7 +167,7 @@ Un des inconvénients des algorithmes de type \textit{snake} est l'influence du
 \small
 \label{algo-snake-cpu2}
    Lire l'image $\bar{v}$\;
 \small
 \label{algo-snake-cpu2}
    Lire l'image $\bar{v}$\;

-   Calculer les images cumulées $S_1$, $S_I$ $S_{I^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\} $\;
    $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\} $\;


@@ -256,7 +256,7 @@ La dépendance vis à vis du contour initial, qui est un des principaux soucis l
 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.
 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
 
 \begin{figure}
   \centering


@@ -289,7 +289,7 @@ 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}
       {\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}
 
       \label{tab-snakecpu-speed-size}
 \end{table}
 


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

-Les sommations se font au niveau de chaque ligne de l'image, que l'on décompose en $n$ blocs de $bs$ pixels où $bs$ correspond aussi au nombre de threads exécutés par chaque bloc de la grille de calcul. La valeur $bs$ étant obligatoirement une puissance de 2 supérieure à 32, le bloc de pixels d'indice $n-1$ doit é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}
 \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}
 
 \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_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$.
+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
 
 \begin{figure}
   \centering


@@ -339,7 +339,7 @@ Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le détail des opér
 \label{fig-calcul-cumuls}
 \end{figure}
 
 \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]
 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}
 
 
 \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. 
 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.
 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}
 
   
 \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}
 
 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}
 
 \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}
 


@@ -473,16 +473,17 @@ Dans l'hypothèse la plus contraignante d'images en niveaux de gris codés sur 1
 \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}
 \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.
 
 
 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}
 \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}
 
       \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} 
 
       \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}
 
 \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.
 
 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 :
 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}
 
 \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}
 
 \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}
 \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.     
 
 
 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. 
 
 
 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. 
+