X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/5d5e214d54eab1411ef86a32e11fccfaa53dbc45..72441aeeda78a2607a1fe941b9a3580e74b4951c:/THESE/Chapters/chapter2/chapter2.tex?ds=inline

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index ebdbd55..c333d0f 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -189,7 +189,7 @@ La figure \ref{fig-ny-nlm} montre des rÃ©sultats de dÃ©bruitage obtenus par la m
 \label{fig-ny-bm3d}
 \end{figure}
 
-\section{Les implÃ©mentations sur GPU des algorithmes de filtrage}
+\section{Les implÃ©mentations sur GPU des algorithmes de filtrage\label{sec-filtresgpu}}
 Le fabricant de processeurs graphiques Nvidia, seul type d'Ã©quipements dont nous disposons, fournit des implÃ©mentations performantes de certains prÃ©-traitements et algorithmes de filtrage. 
 C'est le cas des transformÃ©es de fourrier (FFT, DCT), qui sont par exemple utilisÃ©es dans l'implÃ©mentation d'un algorithme d'\textit{inpainting} \cite{cmla2009Kes} et de l'opÃ©ration de convolution dont l'Ã©tude est prÃ©sentÃ©e ci-dessous. 
 
@@ -437,13 +437,13 @@ Parmi les variantes Ã©laborÃ©es qui tentent de pallier ces dÃ©fauts, les plus in
 \item les \textit{level-sets}, dont la particularitÃ© est de ne pas employer directement une courbe paramÃ©trique plane mais de dÃ©finir l'Ã©volution des frontiÃ¨res comme l'Ã©volution temporelle de l'ensemble des points d'Ã©lÃ©vation nulle d'une surface 3D soumise Ã  un champ de force. 
 Les propriÃ©tÃ©s des contours actifs par \textit{level-sets} se sont rÃ©vÃ©lÃ©es intÃ©ressantes, en particulier la facultÃ© de se disjoindre ou de fusionner, mais les temps de calcul se sont avÃ©rÃ©s trÃ¨s pÃ©nalisants.
 AprÃ¨s la formulation initiale de Osher et Sethian en 1988 \cite{osher1988fronts}, plusieurs faÃ§ons de rÃ©duire le coÃ»t du calcul ont Ã©tÃ© formulÃ©es, dont les plus importantes restent la technique dite \textit{narrow band} \cite{adalsteinsson1994fast} (bande Ã©troite) qui ne calcule Ã  chaque itÃ©ration que les points dans une bande Ã©troite autour du plan $z=0$ de l'itÃ©ration courante et celle du \textit{fast marching} \cite{sethian1996fast} qui s'applique dans le cas particulier d'une Ã©volution monotone des fronts.  
-\item les \textit{snake} orientÃ©s rÃ©gions, qui visent essentiellement Ã  mieux caractÃ©riser les zones Ã  segmenter et amÃ©liorer la robustesse vis-Ã -vis du bruit en employant une formulation de l'Ã©nergie calculÃ©e sur le domaine complet de l'image \cite{cohen1993surface, ronfard1994region}. Les premiers rÃ©sultats confirment la qualitÃ© de cette mÃ©thode, mais la nÃ©cessitÃ© d'effectuer les calculs sur l'image entiÃ¨re gÃ©nÃ©rait des temps de traitement prohibitifs jusqu'Ã  ce que Bertaux \textit{et al.} proposent une amÃ©lioration algorithmique exacte permettant Ã  nouveau un calcul en 1D, le long de la courbe, moyennant une simple Ã©tape initiale gÃ©nÃ©rant un certain nombre d'images intÃ©grales \cite{ChesnaudRB99,GallandBR03,GermainR01}. La section \ref{sec-contrib-snake} qui introduit notre contribution Ã  cette technique en donnera une description dÃ©taillÃ©e. 
+\item les \textit{snake} orientÃ©s rÃ©gions, qui visent essentiellement Ã  mieux caractÃ©riser les zones Ã  segmenter et amÃ©liorer la robustesse vis-Ã -vis du bruit en employant une formulation de l'Ã©nergie calculÃ©e sur le domaine complet de l'image \cite{cohen1993surface, ronfard1994region}. Les premiers rÃ©sultats confirment la qualitÃ© de cette mÃ©thode, mais la nÃ©cessitÃ© d'effectuer les calculs sur l'image entiÃ¨re gÃ©nÃ©rait des temps de traitement prohibitifs jusqu'Ã  ce que Bertaux \textit{et al.} proposent une amÃ©lioration algorithmique exacte permettant Ã  nouveau un calcul en 1D, le long de la courbe, moyennant une simple Ã©tape initiale gÃ©nÃ©rant un certain nombre d'images intÃ©grales \cite{ChesnaudRB99,GallandBR03,GermainR01}. La section \ref{snake-formulation} en donnera une description dÃ©taillÃ©e. 
 \end{itemize}
  
 \subsection{MÃ©thodes hybrides}
 Aujourd'hui, les algorithmes de segmentation les plus performants en termes de qualitÃ© emploient des techniques qui tentent de tirer le meilleur parti de plusieurs des mÃ©thodes ``historiques'' dÃ©crites prÃ©cÃ©demment.
 Le meilleur exemple, et le seul que nous citerons, est le dÃ©tecteur de contour et l'algorithme de segmentation associÃ© proposÃ© par Arbelaez \textit{et al.} en 2010 \cite{arbelaez2011contour}. Ils  construisent des  histogrammes locaux pour gÃ©nÃ©rer une matrice de similitude (affinity matrix) et appliquent les techniques liÃ©es Ã  la thÃ©orie des graphes pour rÃ©duire la dimension de l'espace de reprÃ©sentation (calcul des valeurs et vecteurs propres). Ils utilisent ensuite une technique adaptÃ©e de l'algorithme intitulÃ© \textit{ligne de partage des eaux} pour en regrouper les segments. 
-Les rÃ©sultats sont trÃ¨s bons et des implÃ©mentations efficaces ont d'ores et dÃ©jÃ  Ã©tÃ© Ã©crites (voir section \ref{sec_ea_gpu}). 
+Les rÃ©sultats sont trÃ¨s bons et des implÃ©mentations efficaces ont d'ores et dÃ©jÃ  Ã©tÃ© Ã©crites (voir section \ref{sec-seg-hybride}). 
 %TODO 
 %peut-Ãªtre dire deux mots sur le partage des eaux (avec kmeans et meanshift) puisqu'il est employÃ© dans gPb
 
@@ -542,9 +542,9 @@ Par ailleurs, une approximation du systÃ¨me linÃ©aire Ã  rÃ©soudre est proposÃ©e
 
 \begin{figure}
   \centering
-  \subfigure[Contour initial]{\label{fig-epaule-init}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-init.png}}\quad
-  \subfigure[Contour final]{\label{fig-epaule-fin}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-fin.png}}
-\caption{Segmentation d'une image d'Ã©paule en 1024$^2$ pixels issue d'un examen IRM par l'implÃ©mentation du snake GVF de \cite{snakegvf06}. Le contour est reprÃ©sentÃ© en rougeet le contour final est obtenu en 11~s. }
+  \subfigure[Contour initial]{\label{fig-epaule-init}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-init-t.png}}\quad
+  \subfigure[Contour final]{\label{fig-epaule-fin}\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/snake-epaule-fin-t.png}}
+\caption{Segmentation d'une image d'Ã©paule en 1024$^2$ pixels issue d'un examen IRM par l'implÃ©mentation du snake GVF de \cite{snakegvf06}. Le contour est reprÃ©sentÃ© en rougeet le contour final est obtenu en 11~s. Le tracÃ© initial du contour a Ã©tÃ© artificiellement Ã©paissi pour le rendre visible Ã  l'Ã©chelle de l'imppression}
 \label{fig-snakegvf}
 \end{figure}
 
@@ -557,7 +557,7 @@ En adaptant sur GPU une variante du snake GVF dite FD-snake  (pour Fourier Descr
 La plus aboutie des implÃ©mentations actuelles du snake GVF est enfin celle prÃ©sentÃ©e par Smistad \textit{et al.} dans \cite{snakegvfopencl12} oÃ¹ les auteurs ont concentrÃ© leur effort sur l'optimisation des accÃ¨s mÃ©moire lors du calcul du GVF. Ils ont comparÃ© 8 combinaisons possibles impliquant l'emploi des mÃ©moires partagÃ©e et de texture ainsi que la reprÃ©sentation des nombres selon le format classique 32 bits ou selon un format compressÃ© sur 16 bits. Il en ressort que l'association la plus performante est celle des textures et du format de donnÃ©es sur 16 bits.
 Les performances sont alors nettement en hausse avec des segmentations d'images mÃ©dicales d'IRM de 512$^2$ pixels effectuÃ©es en 41~ms sur Nvidia C2070 et 28~ms sur ATI 5870 (512 itÃ©rations). L'implÃ©mentation rÃ©alisÃ©e en openCL permet d'exÃ©cuter le code sur les GPU des deux principaux fabricants.   
 
-\subsection{Algorithmes hybrides}
+\subsection{Algorithmes hybrides\label{sec-seg-hybride}}
 Le dÃ©tecteur de contour \textit{gPb} dÃ©crit dans \cite{arbelaez2011contour} et que l'on considÃ¨re comme la rÃ©fÃ©rence actuelle pour la segmentation d'objets et personnages dans des image naturelles, Ã  Ã©tÃ© implÃ©mentÃ© en CUDA par Cantazaro \textit{et al.} et est dÃ©crit dans \cite{5459410}. La qualitÃ© des contours extraits y est prÃ©servÃ©e et le temps de traitement y est rÃ©duit d'un facteur supÃ©rieur Ã  100 : les contours des images de 0.15~MP de la base de test BSDS \cite{martin2001database} sont ainsi traitÃ©es en 2 secondes environ sur GPU C1060.
 L'apport principal de ces travaux rÃ©side dans la solution conÃ§ue pour le calcul des histogrammes locaux, qui dans l'algorithme original s'Ã©tendaient sur des demi-disques centrÃ©s sur chaque pixel. La parallÃ©lisation rÃ©alisÃ©e fait l'approximation de chaque demi-disque en un rectangle de mÃªme surface dont un des grands cotÃ©s a le centre du disque pour milieu. Les rectangles sont ensuite pivotÃ©s par une rotation basÃ©e sur la discrÃ©tisation de Bresenham \cite{bresenham1965algorithm} pour en aligner les cotÃ©s avec les cotÃ©s de l'image et pouvoir employer la technique des images cumulÃ©es pour calculer rapidement l'histogramme.   
 La figure \ref{fig-gPb} prÃ©sente quelques rÃ©sultats d'extraction de contours.
