X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/de66b573538c6949bbc090e4e7ac4af93a868bbd..12d11169397a4c178be057928f1ac5bd0b956579:/THESE/Chapters/chapter3/chapter3.tex?ds=sidebyside

diff --git a/THESE/Chapters/chapter3/chapter3.tex b/THESE/Chapters/chapter3/chapter3.tex
index e802a48..89f5358 100644
--- a/THESE/Chapters/chapter3/chapter3.tex
+++ b/THESE/Chapters/chapter3/chapter3.tex
@@ -94,6 +94,7 @@ oÃ¹ $C(i,j)$ est un coefficient liÃ© Ã  la direction du contour au point $(i,j)$
 \end{equation}
 
 La valeur de $C(i,j)$ est dÃ©terminÃ©e pour chaque pixel d'indice $l$ du contour en considÃ©rant les pixels d'indices $l-1$ et $l+1$ qui dÃ©finissent les deux vecteurs $f_{in}$ et $f_{out}$ et leur code selon le codage de Freeman, comme l'illustre la figure \ref{fig-freeman}. La table \ref{tab-freeman} donne les valeurs de $C(i,j)$ selon les valeurs des codes de Freeman des vecteurs $f_{in}$ et $f_{out}$.
+Il faut noter que les valeurs dans la table \ref{tab-freeman} diffÃ¨rent de celles proposÃ©es initialement dans \cite{ChesnaudRB99}. Cette modification a Ã©tÃ© proposÃ©e 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}
@@ -101,7 +102,7 @@ La valeur de $C(i,j)$ est dÃ©terminÃ©e pour chaque pixel d'indice $l$ du contour
   \label{fig-freeman}
 \end{figure}
 
-\begin{table}[htb]
+\begin{table}[h]
   \centering
 \begin{tabular}[htb]{ccccccccc}
       \toprule
@@ -325,7 +326,7 @@ Les diagrammes de la figure \ref{fig-calcul-cumuls} donnent le dÃ©tail des opÃ©r
 
 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
@@ -405,14 +406,19 @@ 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.
-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}
@@ -426,7 +432,110 @@ D'aprÃ¨s la formulation gÃ©nÃ©rale du snake faite au paragraphe \ref{snake-formu
    \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).
+
+
+ 
 
 
 
