\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 plus tard pour permettre de s'adapter à la segmentation multi-cibles. Nous avons conservé la version la plus récente.
\begin{figure}[htb]
\centering
\includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/codage-freeman.png}
\label{fig-freeman}
\end{figure}
-\begin{table}[htb]
+\begin{table}[h]
\centering
\begin{tabular}[htb]{ccccccccc}
\toprule
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.
On obtient des accélérations supérieures en rendant le calcul moins générique et en développant des versions spécifiques des trois \textit{kernels}, dédiées par exemple au traitement des images dont largeur est multiple de 256 pixels.
-\begin{table}
+\begin{table}[h]
\centering
\begin{tabular}{rrrr}
\toprule
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.
-Un calcul des statistiques globales du nouveau contour ainsi que du critère $GL$ est alors nécessaire et applique à nouveau les techniques décrites dans ce paragraphe.
-Enfin l'ajout des nouveaux n\oe uds se fait simplement pour les segments suffisamment grands, en utilisant les coordonnées des pixels milieux mémorisées lors de la discrêtisation des segments.
+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.
+
+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.
\subsubsection{Cas particulier des segments dont la pente $k$ vérifie $|k|\leq 1$}
Comme nous venons de le voir, les segments dont la pente $k$ vérifie $|k|\leq 1$ sont discrêtisés à raison de \textit{1 pixel par colonne} et comportent donc le plus souvent plusieurs pixels sur une ligne donnée, comme le montrent les schémas de la figure \ref{fig-segment-k<1}.
-D'après la formulation générale du snake faite au paragraphe \ref{snake-formulation}, le coefficient $C(i,j)$ est à appliquer en chaque point du contour. La technique de discrêtisation employée conduit à des coefficients $C(i,j)$ constants sur l'ensemble des pixels des segments dont la pente $k$ vérifie $|k|> 1$, mais ce n'est pas le cas pour ceux dont la pente $k$ est inférieure ou égale à $1$. Les quatre cas, un par quadrant, qui peuvent se présenter sont représentés à la figure \ref{fig-segment-k<1}. On y constate en se reportant à la table \ref{tab-freeman} que tout pixel dont les voisins immédiats sont sur la même ligne à un coefficient $C(i,j)=0$ ($F_{in}=f_{out}=0$). Les deux pixels des extrémités, n'ayant quant à eux qu'un voisin, ont un coefficient qui dépend du quadrant :
+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}
\item dans les quandrant 1 et 2
\begin{itemize}
\end{itemize}
\end{itemize}
-Les accès en mémoire aux contributions de ces pixels dans les images cumulées sont évités et une contribution nulle leur est automatiquement attribuée dès l'étape de discrêtisation au sein du kernel \texttt{GPU\_compute\_segments\_contribs()}.
+\begin{figure}
+ \centering
+ \subfigure[Quadrants 1 et 4]{\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels2.png}}\quad
+ \subfigure[Quadrants 2 et 3]{\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels1.png}}\\
+ \subfigure{\includegraphics[width=8cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/coeffs-pixels3.png}}
+\label{fig-segment-k<1}
+ \caption{Détermination des coefficients $C(i,j)$ des pixels du contour.}
+\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()}.
+
+
+\subsection{Performances}
+Dans l'hypothèse la plus contraignante d'images en niveaux de gris codés sur 16 bits, l'implémentation parallèle que nous venons de décrire utilise de manière permanente 20 octets par pixel de l'image d'entrée, qui se détaillent en
+\begin{itemize}
+\item l'image d'entrée pour 4 octets par pixel (1 entier).
+\item l'image cumulée $S_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.).
+
+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.
+
+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.
+
+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]
+ \centering
+ \begin{tabular}{rrrrr}
+ \toprule
+ &&\multicolumn{3}{c}{Performances}\\
+ \cmidrule(r){3-5}
+ && CPU & GPU & CPU/GPU \\
+ \midrule
+ & {\bf total} &{\bf 0,51 s}&{\bf 0,06 s}&{\bf x8,5}\\
+ Image 15~MP & images cumulées &0,13 s&0,02 s&x6,5\\
+ & segmentation &0,46 s&0,04 s&x11,5\\
+ \midrule
+ & {\bf total} &{\bf 4,08 s}&{\bf 0,59 s}&{\bf x6,9}\\
+ Image 100~MP & images cumulées &0,91 s&0,13 s&x6,9\\
+ & segmentation &3,17 s&0,46 s&x6,9\\
+ \midrule
+ & {\bf total} &{\bf 5,70 s}&{\bf 0,79 s}&{\bf x7,2}\\
+ Image 150~MP & images cumulées &1,40 s&0,20 s&x7,0\\
+ & segmentation &4,30 s&0,59 s&x7,3\\
+
+ \bottomrule
+\end{tabular}
+ \caption{Comparaison des temps d'exécution de l'implémentation GPU 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}
+
+\begin{figure}
+ \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}}
+\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}
+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é.
+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. Le principe mis en \oe uvre, illustré par la figure \ref{fig-smart-init} est le suivant :
+\begin{enumerate}
+\item on réalise un échantillonnage horizontal pour ne considérer que les colonnes d'indice $j=8k$.
+\item on évalue alors tous les contours rectangulaires de diagonale $(0, j_L)-(J_H, H)$
+\item on identifie le contour présentant le meilleur critère $GL$, ce qui détermine $j_L$ et $j_H$.
+\item on fait de même en échantillonnant verticalement : les lignes d'indice $i=8t$ permettent de décrire tous les contours de diagonale $(i_L, j_L)-(i_H, j_H)$. Le meilleur contour est celui retenu pour l'initialisation de la segmentatation.
+\end{enumerate}
+
+\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. }
+\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.
+
+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.
+
+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.
+
+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.
+
+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.
+
+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.
+
+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).
+
+
+
