+\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}}
+ \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 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}
+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_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 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.
+
+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 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. 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}
+ \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 (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}
+
+\begin{figure}
+ \centering
+ {\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 d'une image de 100~MP en 0,59~s pour 5 itérations. Le contour initial conserve les proportions de celui de la figure \ref{fig-snakecpu-cochon512}. }
+\label{fig-snakegpu-result}
+\end{figure}
+
+\subsection{Détermination du contour initial au sens du maximum de vraisemblance}
+Nous avons déjà discuté de l'influence du contour initial sur le résultat de la segmentation, mais il faut ajouter que la durée d'exécution est aussi impactée par ce choix, dans des proportions qui peuvent être importantes selon la distance, la taille et dans une moindre mesure la forme de la cible.
+
+Ces effets se mesurent lors de la première itération, celle qui va cerner grossièrement la cible avec un 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 :
+\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}
+
+Le gain de performance apporté par cette stratégie d'initialisation est variable selon la cible, mais dans des situations favorables comme celle de l'image de la figure \ref{fig-snakecpu-cochon4kc3}, on parvient à une accélération proche de 15 alors qu'elle n'est que d'environ 7 avec l'initialisation basique. Cette proportion est conservée pour les tailles supérieures et signifie que la phase de segmentation est tout de même effectuée 30 fois plus rapidement qu'avec l'implémentation CPU, grâce à une première itération optimisée.
+
+\begin{figure}
+ \centering
+ \subfigure[Détermination de $j_L$ et $j_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init1.pdf_t}}}\quad
+ \subfigure[Détermination de $i_L$ et $i_H$.]{\resizebox{6cm}{!}{\input{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter3/img/smart_init2.pdf_t}}}
+\label{fig-smart-init}
+ \caption{Détermination 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}
+Nous avons conçu une implémentation parallèle de \textit{snake} polygonal orienté régions, ce qui n'avait pas encore é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 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 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 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 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 de contour initial serait génératrice de gain de performance.
+
+L'analyse fine des séquences de segmentation montre enfin que les première étapes, qui mettent en \oe uvre les segments les plus longs, génèrent des grilles de calcul suffisamment chargées et homogènes pour présenter de bonnes performances. Les dernières étapes, en revanche, traitent un grand nombre de petits segments, générant beaucoup de trous dans la grille de calcul et induisant des performances moindres.
+
+Pour résumer, l'accélération globale obtenue est principalement déterminée par le calcul des images cumulées et des toutes premières étapes de déplacements. Une possibilité à explorer serait de construire une version hybride réalisant le début de la segmentation sur GPU, puis la terminant sur le CPU hôte. Ceci est envisageable en raison du très petit volume de données à transférer que constituent les paramètres du contour (2~ko pour 100 n\oe uds). 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.
+
+
+
+
