X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/2145c00e2163c4976cfc5dd2937ac2b5e7515892..5997a2db46b2dcd03451c2229f90a509b8db3759:/THESE/Chapters/chapter2/chapter2.tex?ds=inline

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index b4368c0..b02fcc4 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -260,7 +260,7 @@ Les algorithmes de segmentation orientÃ©s rÃ©gions s'appuient pour beaucoup sur
 
 GÃ©nÃ©ralement, la plupart des approches proposÃ©es jusqu'Ã  trÃ¨s rÃ©cemment consistent Ã  minimiser une fonction d'Ã©nergie qui n'a pas de solution formelle et que l'on rÃ©sout donc Ã  l'aide de techniques numÃ©riques, souvent itÃ©ratives.   
 
-\subsection{Analyse d'histogramme}
+\subsection{Analyse d'histogramme}\label{sec-histo}
 Les techniques les plus simples Ã  mettre en \oe uvre en segmentation sont les techniques de seuillage, basÃ©es sur une analyse de l'histogramme des niveaux de gris (ou de couleurs) et cherchant Ã  en distinguer les diffÃ©rentes classes comme autant d'occurrences reprÃ©sentant des \textit{rÃ©gions} homogÃ¨nes.
 DiffÃ©rents critÃ¨res peuvent Ãªtre appliquÃ©s pour cette analyse, visant par exemple Ã  maximiser la variance \cite{4310076} ou encore Ã  maximiser le contraste pour dÃ©terminer les valeurs pertinentes des seuils. 
 
@@ -297,16 +297,16 @@ $\epsilon \leftarrow 1$ \;
 } 
 \end{algorithm}
 
-\subsection{Analyse de graphe}
+\subsection{Partitionnement de graphe}
 Un autre formalisme qui a gÃ©nÃ©rÃ© une vaste classe d'algorithmes de segmentation est celui des graphes et repose sur l'idÃ©e que les rÃ©gions de l'image sont reprÃ©sentÃ©es par les n\oe uds du graphe, alors que les liens traduisent les relations de voisinage existant entre les rÃ©gions.
-L'idÃ©e de base est d'initialiser le graphe avec un n\oe ud pour chaque pixel. La segmentation est obtenue par simplification itÃ©rative du graphe, en Ã©valuant les liens et en dÃ©terminant ceux Ã  supprimer et ce, jusqu'Ã  convergence.
+L'idÃ©e de base est d'initialiser le graphe avec un n\oe ud pour chaque pixel. La segmentation est obtenue par partitionnement itÃ©ratif du graphe, en Ã©valuant les liens et en dÃ©terminant ceux Ã  supprimer et ce, jusqu'Ã  convergence.
 
 L'essentiel de la problÃ©matique rÃ©side donc dans la mÃ©trique retenue pour Ã©valuer les liens ainsi que dans le critÃ¨re de sÃ©lection et lÃ  encore, la littÃ©rature regorge d'une grande variÃ©tÃ© de propositions.
 Nous pouvons retenir que les premiÃ¨res d'entre elles, qui n'Ã©taient pas spÃ©cifiquement dÃ©diÃ©es Ã  la segmentation d'images numÃ©riques mais au regroupement d'Ã©lÃ©ments rÃ©partis sur un domaine (1D ou 2D), ont Ã©tÃ© Ã©laborÃ©es autour d'une mesure locale des liens basÃ©e sur la distance entre les Ã©lÃ©ments. La rÃ©duction du graphe est ensuite effectuÃ©e en utilisant un algorithme spÃ©cifique, comme le \textit{minimum spanning tree}, dont l'application a Ã©tÃ© dÃ©crite dÃ¨s 1970 dans \cite{Zahn:1971:GMD:1309266.1309359} et oÃ¹ il s'agit simplement de supprimer les liens \textit{inconsistants}, c'est Ã  dire ceux dont le poids est significativement plus Ã©levÃ© que la moyenne des voisins se trouvant de chaque cotÃ© du lien en question.
 
 L'extension a rapidement Ã©tÃ© faite aux images numÃ©riques en ajoutant l'intensitÃ© des pixels au vecteur des paramÃ¨tres pris en compte dans l'Ã©valuation du poids des liens.
-D'autres critÃ¨res de simplification ont aussi Ã©tÃ© Ã©laborÃ©s, avec pour ambition de toujours mieux prendre en compte les caractÃ©ristiques structurelles globales des images pour prÃ©tendre Ã  une segmentation qui conduise Ã  une meilleure perception conceptuelle.
-Le principe gÃ©nÃ©ral des solutions actuelles est proche de l'analyse en composantes principales appliquÃ©e Ã  une matrice de similaritÃ© qui traduit les liens entre les segments.
+D'autres critÃ¨res de partitionnement ont Ã©tÃ© Ã©laborÃ©s, avec pour ambition de toujours mieux prendre en compte les caractÃ©ristiques structurelles globales des images pour prÃ©tendre Ã  une segmentation qui conduise Ã  une meilleure perception conceptuelle.
+Le principe gÃ©nÃ©ral des solutions actuelles repose sur la construction d'une matrice de similaritÃ© qui traduit les liens entre les segments et reprÃ©sente le graphe Ã  partitionner.
 Pour des images en niveaux de gris, l'expression gÃ©nÃ©rale des Ã©lÃ©ments $w_{ij}$ de la matrice de similaritÃ© $W$ est :
 \[w_{ij} = 
 \begin{cases}
@@ -314,14 +314,12 @@ Pour des images en niveaux de gris, l'expression gÃ©nÃ©rale des Ã©lÃ©ments $w_{i
 0 & \text{sinon}
 \end{cases}
 \]
-On construit ensuite la matrice de connectivitÃ© $D$, diagonale et dont les Ã©lÃ©ments sont :
+On construit Ã©galement la matrice de connectivitÃ© $D$, diagonale et dont les Ã©lÃ©ments sont :
 \[d_{i} = \displaystyle\sum_jw_{ij}\]
 
-Le systÃ¨me dont on cherche les valeurs propres $\lambda_k$ et les vecteurs propres associÃ©s $Y_k$ est alors le suivant :
+Une famille de mÃ©thodes, inspirÃ©e par le \textit{graphe optimal} de Wu et Leahy \cite{wu1993optimal}, rÃ©alise le partitionnement sur la base des valeurs propres $\lambda_k$ et vecteurs propres $Y_k$ du systÃ¨me 
 \[\left(D-W)\right)Y=\lambda DY \]
-
-Parmi les mÃ©thodes reposant sur ce principe, on peut citer, par ordre chronologique, celles qui reposent sur le \textit{graphe optimal} de Wu et Leahy \cite{wu1993optimal} et plus rÃ©cemment \cite{wang2001image,wang2003image,felzenszwalb2004efficient,shi2000normalized}. Le principal point faible de ces techniques rÃ©side essentiellement dans la difficultÃ©  Ã  trouver un compromis acceptable entre identification de structures globales et prÃ©servation des Ã©lÃ©ments de dÃ©tails. Cela se traduit dans la pratique par un ensemble de paramÃ¨tres Ã  rÃ©gler pour chaque type de segmentation Ã  effectuer.
-Elles sont cependant employÃ©es dans les algorithmes de haut niveau les plus rÃ©cents, comme nous le verrons plus loin.
+Certains algorithmes proposÃ©s plus rÃ©cemment s'inscrivent dans cette veine \cite{wang2001image,wang2003image,felzenszwalb2004efficient,shi2000normalized}. Le principal point faible de ces techniques rÃ©side essentiellement dans la difficultÃ©  Ã  trouver un compromis acceptable entre identification de structures globales et prÃ©servation des Ã©lÃ©ments de dÃ©tails. Cela se traduit dans la pratique par un ensemble de paramÃ¨tres Ã  rÃ©gler pour chaque type de segmentation Ã  effectuer.
 
 La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} dÃ©crit dans \cite{shi2000normalized} et implÃ©mentÃ© par Cour, Yu et Shi en 2004. Cette implÃ©mentation utilise des valeurs prÃ©-Ã©tablies des paramÃ¨tres de calcul de la matrice de similaritÃ© produisant de bonnes segmentations d'objets et/ou personnes dans les images naturelles, mais requiert de prÃ©dÃ©terminer le nombre de segments Ã  obtenir. Les images de la figure reprÃ©sentent les rÃ©sultats obtenus avec un nombre de segments variant de 2 Ã  5 et montrent qu'il difficile de trouver un compromis acceptable. Enfin, les temps d'exÃ©cutions peuvent devenir trÃ¨s rapidement prohibitifs, mÃªme avec des implÃ©mentations plus optimisÃ©es. Pour information, les rÃ©sultats de la figure \ref{fig-graph-cochon} ont Ã©tÃ© obtenus en 1.5~s environ (Matlab R2010 sur CPU intel core i5-2520M @ 2.50GHz - linux 3.2.0) 
 \begin{figure}
@@ -334,8 +332,10 @@ La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorit
 \label{fig-graph-cochon}
 \end{figure}
 
-    
-\subsection{kernel-means, mean-shift et dÃ©rivÃ©s}
+Un autre procÃ©dÃ© de partitionnement de graphe, reposant sur le thÃ©orÃ¨me dit du \textit{maximum flow-minimum cut} Ã©noncÃ© par Ford et Fulkerson \cite{ford1955simple} a fait l'objet de beaucoup de travaux. Des comparaison en sont rapportÃ©e dans \cite{boykov2004experimental,chandran2009computational}. 
+Plusieurs algorithmes mettent en \oe uvre ce procÃ©dÃ© avec de bons rÃ©sultats, comme la mÃ©thode du \textit{push-relabel} \cite{cherkassky1997implementing} ou le \textit{pseudoflow} \cite{hochbaum2013simplifications} qui semble aujourd'hui le plus peformant.
+
+\subsection{kernel-means, mean-shift et apparentÃ©s}
 ParallÃ¨lement Ã  la rÃ©duction de graphes, d'autres approches ont donnÃ© naissance Ã  une multitude de variantes tournÃ©es vers la recherche des moindres carrÃ©s. 
 Il s'agit simplement de minimiser l'erreur quadratique totale, ce qui peut se rÃ©sumer, pour une image de $N$ pixels, en la dÃ©termination du nombre $C$ de segments $\Omega_i$ et leur contenu, de sorte Ã  minimiser l'expression 
 \[\sum_{i\in[1..C]}\sum_{x_k\in\Omega_i} \left(v_k-\mu_i\right)^2\]  
@@ -435,12 +435,209 @@ Les rÃ©sultats sont trÃ¨s bons et des implÃ©mentations efficaces ont dores et d
 \section{Les implÃ©mentations GPU des techniques de segmentation}
 
 La problÃ©matique tant Ã©tudiÃ©e de la segmentation n'a pas Ã©chappÃ© Ã  l'engouement des chercheurs pour les processeurs graphiques modernes. Un certain nombre de travaux proposent ainsi des implÃ©mentations GPU plus ou moins directes de mÃ©thodes de segmentation tirant parti de l'architecture massivememnt parallÃ¨le de ces matÃ©riels.
-La majoritÃ© d'entre elles cherche Ã  rÃ©pondre Ã  des besoins liÃ©s Ã  l'imagerie mÃ©dicale allant de la simple extraction des contours d'un organe, d'une tumeur, etc., Ã  la mesure de leur volume. La natures des tissus et les formes Ã  identifier sont extrÃªmement variÃ©es. Les images sont souvent trÃ¨s bruitÃ©es et les modÃ¨les de bruit divers selon l'instrumentation employÃ©e. Enfin, le diagnostique mÃ©dical requerant la plus grande prÃ©cision possible, aucune solution gÃ©nÃ©rique satisfaisante de segmentation n'a encore pu Ã©merger dans ce cadre, laissant place Ã  autant d'implÃ©mentations adaptÃ©es que de besoin mÃ©dical spÃ©cifique.
+La majoritÃ© d'entre elles cherche Ã  rÃ©pondre Ã  des besoins liÃ©s Ã  l'imagerie mÃ©dicale allant de la simple extraction des contours d'un organe, d'une tumeur, etc., Ã  la mesure de leur volume ; le traitement en 3D n'Ã©tant dans ce cas pas un choix mais une obligation, justifiant d'autant plus l'emploi des GPU.
+ La natures des tissus et les formes Ã  identifier sont extrÃªmement variÃ©es. Les images sont souvent trÃ¨s bruitÃ©es et les modÃ¨les de bruit divers selon l'instrumentation employÃ©e. Enfin, le diagnostique mÃ©dical requerant la plus grande prÃ©cision possible, aucune solution gÃ©nÃ©rique satisfaisante de segmentation n'a encore pu Ã©merger dans ce cadre, laissant place Ã  autant d'implÃ©mentations adaptÃ©es que de besoin mÃ©dical spÃ©cifique.
 
 Beaucoup d'algorithmes rÃ©cents destinÃ©s Ã  la segmentation comportent plusieurs phases de calcul et mettent en \oe uvre diffÃ©rents algorithmes rÃ©alisant des fonctions Ã©lÃ©mentaires comme de la rÃ©duction de bruit ou du calcul d'histogramme.
+ Selon le type de traitement Ã  effectuer sur le GPU, on peut-Ãªtre amenÃ© Ã  en concevoir des implÃ©mentations parallÃ¨les adaptÃ©es ou bien simplement exÃ©cuter indÃ©pendemment, pour chaque pixel par exemple, de multiples instances d'une version sÃ©quentielle classique du traitement.
+Dans les deux cas, on lira ``implÃ©mentation GPU'', mais cela recouvrira des rÃ©alitÃ©s et parfois aussi des niveaux de performance trÃ¨s diffÃ©rents.
+
+\subsection{Calcul d'histogramme}
+Comme il a Ã©tÃ© dit au paragraphe \ref{sec-histo}, les segmentations par analyse d'histogramme sont aujourd'hui cantonnÃ©es Ã  des applications trÃ¨s particuliÃ¨res et leurs implÃ©mentations GPU ne font pas l'objet de recherches, d'autant que dans la pratique, ces traitements sont souvent rÃ©alisÃ©s par des circuits spÃ©cialisÃ©s ou programmables de type FPGA et qu'il serait illusoire d'espÃ©rer les concurrencer par une solution de type gpu, plus coÃ»teuse, plus volumineuse et vraisemblablement moins robuste.
+
+Le calcul d'histogramme est cependant utilisÃ© de maniÃ¨re intensive dans certains algorithmes de haut-niveau, en particulier le \textit{level-set} et le \textit{gPb}. Ã ce titre, il faut citer les travaux de Fluck \textit{et al.} \cite{fluck2006gpu} qui apportent une rÃ©ponse efficace au calcul d'histogramme sur le GPU leur permetttant de conserver les donnÃ©es dans la mÃ©moire du processeur graphique tout au long de l'exÃ©cution de la segmentation par level-set qui leur a servi de motivation \cite{lefohn2003interactive}. 
+
+Les rÃ©sultats annoncÃ©s ont Ã©tÃ© obtenus sur un GPU GeForce 7900 et font Ã©tat du calcul des deux histogrammes nÃ©cessaires ( 64 classes chacun) sur une image de 256$\times$256 pixels en niveau de gris en 1.6~ms.
+
+\subsection{Partitionnement de graphe}
+Le domaine du traitement des graphes est trÃ¨s actif et peut fournir des Ã©lÃ©ments pour la segmentation comme l'implÃ©mentation du \textit{minimum spanning tree} dÃ©crite dans \cite{Vineet:2009:FMS:1572769.1572796} qui annonce la construction du minimum spanning tree d'un graphe de 5 millions de n\oe uds et 30 millions de liens en moins d'une seconde. 
+La parallÃ¨lisation GPU des opÃ©rations sur les graphes n'est pas simple en raison de l'indÃ©pendance des blocs de threads. Peu de travaux font encore Ã©tat d'implÃ©mentations efficaces mettant en \oe uvre ces techniques.
+On ne recense que quelques propositions GPU de l'algorithme \textit{push-relabel} pour le partitionnement selon l'approche \textit{min cut/max flow} dont on ne retient que les trois remarquables dÃ©taillÃ©e ci-dessous. 
+
+Dans \cite{dixit2005gpu}  une approche assez directe est mise en \oe uvre et parvient Ã  \textit{binariser} une image de 1~MP en 29~ms (GeForce 6800GT). 
+
+Les auteurs de \cite{4563095} remarquent qu'aprÃ¨s un nombre rÃ©duit d'itÃ©rations, trÃ¨s peu de n\oe ud se voient changer de segment. En consÃ©quence, certains blocs de traitement sont activÃ©s alors qu'ils n'ont effectivement pas de traitement Ã  effectuer et retardent ainsi les traitements Ã©ventuels des blocs en attente. Pour rÃ©duire les effet de ce comportement, un indicateur d'activitÃ© est calculÃ© Ã  chaque itÃ©ration et pour chaque bloc, en se basant le nombre de changements de segment qui vient d'y Ãªtre effectuÃ©. Ã l'itÃ©ration suivante, seuls les blocs considÃ©rÃ©s comme \textit{probablement} actifs seront activÃ©s, rÃ©duisant ainsi la latence globale. Un reparamÃ©trage dynamique du graphe aprÃ¨s chaque itÃ©ration est Ã©galement Ã©ffectuÃ© selon la mÃ©thode dÃ©crite par Kohli et Torr \cite{kohli2007dynamic}. Ces optimisations permettent d'atteindre un dÃ©bit d'environ 30 images de 0.3~MP par seconde sur GTX280, ce qui reprÃ©sente un bond en terme de performance. 
+
+Enfin, Stitch a proposÃ© dans \cite{graphcutscuda} des optimisations plus Ã©troitement liÃ©es Ã  l'architecture des GPUs Nvidia en faisant qu'un mÃªme thread mette Ã  jour plusieurs liens du graphe et aussi en compactant la reprÃ©sentation des indicateurs de changement de segment par 32 par l'emploi d'un seul bit par lien. Cela a permis d'accÃ©lÃ©rer la convergence de l'algorithme, comme la montre la courbe de la figure \ref{fig-graphcutscuda} (tirÃ©e de \cite{graphcutscuda}), et d'atteindre les 70 images par seconde dans les mÃªme conditions que prÃ©cÃ©demment (sur C1060).
+Il faut noter aussi que sur C1060, l'implÃ©mentation dÃ©crite dans \cite{4563095} est moins performante, avec 17~fps, que sur la carte GTX280.
+
+\begin{figure}
+  \centering
+  \includegraphics[width=12cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/graphcutscuda_stitch.png}
+\caption{Ãvolution du nombre de pixels actifs pour les itÃ©ration successives de l'implÃ©mentation  de l'algorithme push-relabel de \cite{graphcutscuda}. Les petites images montrent la localisation des pixels actifs aprÃ¨s chaque itÃ©ration, en blanc.}
+\label{fig-graphcutscuda}
+\end{figure}
+
+\subsection{K-means, mean-shift et apparentÃ©s}
+La popularitÃ© de l'algorithme des \textit{k-means} a induit des tentatives de portage sur GPU dont \cite{che2008performance} qui a implÃ©mentÃ© de maniÃ¨re directe l'etiquetage des Ã©lÃ©ments ainsi qu'une rÃ©duction partielle, par bloc,  pour la mise Ã  jour des centres ; la rÃ©duction finale Ã©tant rÃ©alisÃ©e par le CPU. Cette solution conduit Ã  un transfert des donnÃ©es Ã  chaque itÃ©ration et ne permet pas d'atteindre des performances Ã©levÃ©es. La mesure de performance a Ã©tÃ© faite avec la base de test KDD-Cup-99 \cite{kddcup99}, comportant 23 segments. Le temps annoncÃ© pour l'exÃ©cution d'une seule itÃ©ration sur un ensemble de 819200 Ã©lÃ©ments est de 200~ms. Toutefois, cette durÃ©e n'inclue pas la rÃ©duction ni les transferts et l'accÃ©lÃ©ration revendiquÃ©e semble alors trÃ¨s discutable.
+
+Dans \cite{5170921}, l'ensemble des tÃ¢ches d'Ã©tiquetage et de mise Ã  jour des centres est rÃ©alisÃ© sur le GPU. Une Ã©tape de rÃ©organisation des donnÃ©es est encore exÃ©cutÃ©e sur le CPU, mais elle s'avÃ¨re moins pÃ©nalisante que la solution prÃ©sentÃ©e prÃ©cÃ©demment, puisqu'elle permet de prÃ©senter au GPU des donnÃ©es permettant d'optimiser l'exÃ©cution parallÃ¨le de l'Ã©tape de rÃ©duction suivante (mise Ã  jour des centres). Les temps d'exÃ©cution par itÃ©ration sont sensiblement les mÃªmes que pour \cite{che2008performance} mais ils incluent cette fois l'ensemble des calculs (hors transferts). Les auteurs fournissent cette fois des mesures des temps d'exÃ©cution Ã  convergence, qui atteignent la vingtaine de secondes pour le mÃªme ensemble de test.
+
+La plus convaincante des implÃ©mentations de \textit{k-means} reste Ã  notre connaissance celle dÃ©crite dans \cite{kmeansgpuopengl} et oÃ¹ la totalitÃ© du traitement est effectuÃ©e sur le GPU, moyennant l'emploi d'une texture par segment de donnÃ©es. Les mesures ont montrÃ© que cette multiplication du nombre des textures ne constituait pas un facteur de perte de performance, tout du moins jusqu'aux limites des tests, conduits avec un maximum de 32 segments dans des ensembles de 1 million d'Ã©lÃ©ments. Sur GPU GeForce 8500GT, les temps d'exÃ©cution obtenus dans ces conditions sont de 13.8~ms par itÃ©ration, avec une dÃ©pendance trÃ¨s rÃ©duite vis Ã  vis du nombre de segments.
+
+Des travaux Ã  orientation non mÃ©dicale mettent en \oe uvre sur GPU un algorithme de \textit{mean-shift} pour la poursuite de cibles dans des sÃ©quences vidÃ©o \cite{li2009mean}. L'accÃ©lÃ©ration otenue par rapport aux implÃ©mentations sÃ©quentielles existantes n'est que d'un facteur 2. La solution prÃ©sentÃ©e effectue prÃ©alablement une rÃ©duction de l'espace colorimÃ©trique via un regroupement par la mÃ©thode \textit{k-means}, utilisÃ©e dans une version sÃ©quentielle. Un gain potentiel de performance pourrait Ãªtre apportÃ© en employant une implÃ©mentation GPU du \textit{k-means}, mais serait toutefois limitÃ© en raison des itÃ©rations nÃ©cessaires plus nombreuses pour le traitement \textit{mean-shift}. Par ailleurs, l'implÃ©mentation proposÃ©e fait un usage intensif de la mÃ©moire partagÃ©e et se heurte Ã  sa limite de 16~Ko par bloc, obligeant Ã  rÃ©duire la taille des blocs Ã  l'exÃ©cution et avec eux, le parallÃ©lisme et vraisemblement aussi la performance de l'application. On peut malgrÃ© tout raisonnablement espÃ©rer qu'une telle solution prÃ©senterait des performances meilleures sur une carte de type Fermi possÃ©dant jusqu'Ã  48~Ko de mÃ©moire partagÃ©e par bloc.
+
+\textit{Quick shift}, une approximation de l'algorithme mean-shift gaussien, c'est Ã  dire utilisant des masques de pondÃ©ration gaussiens, permettant d'obtenir un rÃ©sultat en une seule passe (sans itÃ©rer) et proposÃ©e initiallement dans \cite{vedaldi2008quick} a Ã©tÃ© parallÃ©lisÃ©e sur GPU par ses auteurs et dÃ©crite dans \cite{fulkerson2012really}. La recherche de performance se traduit par des approximations, en particulier on restreint les calculs de pondÃ©ration Ã  des voisinages de rayon $3\sigma$ (Ã©cart type de la gaussienne dÃ©finissant les coefficients du masque), considÃ©rant qu'au delÃ , les valeurs en sont nÃ©gligeable.
+Ensuite on construit un arbre des liens entre les pixels, mais on limite la recherche Ã  une distance maximale de $\sigma$. Par ailleurs, on diminue arbitrairement la dynamique de l'espace colomÃ©trique par 2. Enfin, la segmentation est obtenu par simple partionnnement de l'arbre selon un seuil $\tau$.
+Pour s'affranchir de la relative petite taille de la mÃ©moire partagÃ©e sans devoir pÃ¢tir de la grande latence des accÃ¨s Ã  la mÃ©moire globale de GPU, les auteurs ont ici choisi d'associer l'image et l'estimation de densitÃ© Ã  des textures et ainsi bÃ©nÃ©ficier du mÃ©canisme de cache.
+Les expÃ©rimentations ont Ã©tÃ© menÃ©es avec diffÃ©rentes valeurs de $\sigma$ et $tau$ choisies pour les rÃ©sultats visuels qu'elles induisent et permettent de segmenter une image couleur de 1~MP en environ 1~s avec $\tau=10$ et $\sigma=6$. Toutefois, des valeurs plus petites, requÃ©rant moins de calculs, permettent des temps d'exÃ©cution beaucoup plus courts. Les courbes prÃ©sentÃ©es permettent d'envisager, pour $\tau=4$ et $\sigma=2$, une rÃ©duction par 30, soit environ 33~ms. Une version amÃ©liorÃ©e rÃ©cemment, dans laquelle les positions des centres sont stockÃ©es en registres, permet selon les auteurs, de diviser encore par 2 les temps d'exÃ©cution pour atteindre une segmentation en environ 16.5~ms.
+La figure \ref{fig-quickshift-yo}, tirÃ©e de \cite{fulkerson2012really}, prÃ©sente quelques segmentations effectuÃ©es avec des valeurs diffÃ©rentes, permettant ainsi de juger des effets des variations des paramÃ¨tres $\tau$ et $\sigma$.
+
+\begin{figure}
+  \centering
+\subfigure[Image originale]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-orig.png}}\quad
+\subfigure[$\tau=10$ et $\sigma=2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s2t10.png}}\quad
+\subfigure[$\tau=10$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t10.png}}\quad
+\subfigure[$\tau=20$ et $\sigma=10$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/quick-shift-yo-s10t20.png}}\quad
+\caption{Segmentation d'une image couleur de 512$\times$512 pixels par l'implÃ©mentation GPU quick-shift de \cite{fulkerson2012really}.}
+\label{fig-quickshift-yo}
+\end{figure}
+
+RÃ©cemment, Xiao et Liu ont dÃ©crit dans \cite{xiao2010efficient} une implÃ©mentation de l'algorithme \textit{mean-shift} qui utilise cette fois une construction de \textit{KD-tree} (arbre binaire Ã  K dimensions) pour rÃ©duire l'espace colorimÃ©trique et effectuer rapidement les recherches des plus proches voisins. L'ensemble s'exÃ©cute sur le GPU et permet ainsi d'obtenir des rÃ©sultats beaucoup plus probants puisque les auteurs revendiquent une segmentation d'image couleur de 6.6 millions de pixels en 0.2 secondes. Malheureusement, il n'est pas dit combien de segments comprend l'image et il n'est fait rÃ©fÃ©rence qu'Ã  une seule image, dont on dÃ©duit qu'il s'agit de l'image reproduite Ã  la figure  \ref{fig-meanshift-castle} afin de montrer les diffÃ©rences avec une implÃ©mentation standard du \textit{mean-shift}.
+
+\begin{figure}
+  \centering
+\subfigure[Image originale]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift.png}}\quad
+\subfigure[Image segmentÃ©e par mean-shift standard]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-std.png}}\quad
+\subfigure[Image segmentÃ©e par mean-shift kd-tree]{\includegraphics[width=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/castle-meanshift-kdtree.png}}
+\caption{Segmentation d'une image couleur de 2256$\times$3008 pixels.}
+\label{fig-meanshift-castle}
+\end{figure}
+
+\subsection{Snakes et Level set}
+DÃ¨s 2003, on recense d'importants travaux liÃ©s Ã  l'imagerie mÃ©dicale mettant en \oe uvre des algorithmes \textit{level set} sur GPU. C'est le cas de \cite{lefohn2003inter,lefohn2003interactive} oÃ¹ les auteurs dÃ©crivent une solution de visualisation des coupes d'une mesure volumique rÃ©alisÃ©s par rÃ©sonnance magnÃ©tique (IRM) en exploitant pour la premiÃ¨re fois le caractÃ¨re creux du systÃ¨me d'Ã©quations Ã  rÃ©soudre, \textit{i.e.} variante narrow-band, contrairement Ã  la premiÃ¨re solution 2D prÃ©sentÃ©e dans \cite{rumpf2001level} qui implÃ©mente la version standard. En ne transfÃ©rant au GPU, pour chaque itÃ©ration, que les petits pavÃ©s de donnÃ©es actifs et en les  rangeant alors de maniÃ¨re contigue en texture pour optimiser les accÃ¨s en lecture, les auteurs sont ainsi parvenu Ã  effectuer, pour des donnÃ©es volumiques de 256$\times$256$\times$175, entre 3.5 et 70 itÃ©rations par seconde, Ã  comparer aux 50 itÃ©rations par seconde en 2D sur image de 128$^2$ pixels otenues dans \cite{rumpf2001level}. La limitation principale de cettesolution est celle des dimensions maximales admises pour une texture qui Ã©tait de 2048$^2$ pour le GPU ATI Radeon 9800 pro employÃ© (et programmÃ© en openGL, car ni openCL ni CUDA n'Ã©taient encore disponible Ã  l'Ã©poque).
+Les autres solutions GPU proposÃ©es depuis sont Ã©galement basÃ©es sur la variante \textit{narrow-band} (bande Ã©troite) des \textit{level-set} \cite{lefohn2005streaming,cates2004gist,jeong2009scalable}, mais seule \cite{jeong2009scalable} s'affranchit des transferts CPU/GPU Ã  chaque itÃ©ration pour dÃ©terminer et transfÃ©rer les pavÃ©s actifs. La solution retenue est d'employer les opÃ©rations atomiques pour assurer l'accÃ¨s exclusif Ã  la liste des pavÃ©s en mÃ©moire GPU. Cela permet de descendre Ã  3~ms par itÃ©ration pour une image de 512$^2$ pixels.
+
+La plus performante des implÃ©mentations Ã  ce jour est celle dÃ©crite dans \cite{Roberts:2010:WGA:1921479.1921499} qui parvient Ã  des itÃ©rations dont la durÃ©e varie, sur GTX280,  de 1.8 Ã  6.5~ms pour des donnÃ©es volumiques de 256$^3$ pixels issues d'examen IRM, pour une moyenne de 3.2~ms sur les 2200 itÃ©rations de l'exemple fourni (cerveau en 7~s, Figure \ref{fig-l7-brain}). Une optimisation poussÃ©e y a Ã©tÃ© effectuÃ©e pour rendre l'algorithme efficace, en particulier au travers de la refonte du code responsable de la dÃ©termination des pavÃ©s actifs. Il parvient cette fois Ã  dÃ©terminer l'ensemble minimal de pavÃ©s actifs et Ã  rendre cette dÃ©termination efficace sur le GPU en gÃ©rant parallÃ¨lement plusieurs tampons, chacun associÃ© Ã  une direction particuliÃ¨re en 6-connexitÃ©. Une Ã©tape de rÃ©solution des doublons est ensuite effectuÃ©e avant de les compacter de maniÃ¨re contigue comme cele Ã©tait dÃ©jÃ  fait dans \cite{lefohn2003inter}. Toutefois, tenir Ã  jour cette liste de pavÃ©s reprÃ©sente encore 77\% du temps de calcul aprÃ¨s cette optimisation.
+%TODO dire qu'il n'utilise pas de shmem !
+Ce faisant, le nombre cumulÃ© total de pavÃ©s ainsi traitÃ©s lors des 2200 itÃ©rations de la segmentation der l'image d'exemple s'Ã©lÃ¨ve Ã  294 millions Ã  comparer aux 4877 millions traitÃ©s par l'algorithme \textit{narrow-band} standard. Il est Ã  noter que la durÃ©e d'exÃ©cution d'une itÃ©ration dans cette variante dÃ©pend plus fortement de la proportion de pavÃ©s actifs que pour \textit{narrow-band} standard. Les deux courbes sont globalement affines et se croisent pour une proportion de pavÃ©s actifs proche de 10\%.
+Cela peut reprÃ©senter une piste pour une optimisation supplÃ©mentaire qui ne semble pas su justifier avec l'image et l'initialisation dont les performances sont dÃ©taillÃ©es, mais qui pourrait l'Ãªtre dans d'autres conditions, comme peut le suggÃ©rer le temps de segmentation de 16~s nÃ©cessaire pour l'image des reins (Figure \ref{fig-l7-reins}) et de l'aorte, malgrÃ© des dimensions comparables.
+
+\begin{figure}
+  \centering
+\subfigure[Cerveau 256$\times$256$\times$256 en 7~s]{\label{fig-l7-brain}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-brain7s.png}}\quad
+\subfigure[Reins et aorte, 256$\times$256$\times$272 en 16~s]{\label{fig-l7-reins}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/l7-reins16s.png}}
+\caption{Segmentation d'images issues d'examens IRM par la mÃ©thode des level set Ã  bande Ã©troite.}
+\label{fig-meanshift-castle}
+\end{figure}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
  
-%dire que les combianisons possibles sont nombreuses pour la conception, en fonction du niveau de prarllelisme. Par exmple, on peut calculer un histogramme par pixel mais le faire en sequentiel, ou bien chercher Ã  paralleliser aussi le calcul d'histo. Das les deux cas, on dira histograme GPU, mais cela recouvrira des rÃ©alitÃ©s et des niveaux de difficultÃ© et de perf tres differents.
 
 
 
-      
\ No newline at end of file
+   
+      
+
+
+
+
+
+
+
+
+
+
+
+
+ 
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
