7 dec

[these_gilles.git] / THESE / Chapters / chapter2 / chapter2.tex

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index ebdbd556c23b149dc6dfc6131392522aa9c5a7b2..c333d0ff29132d91d8497cc2dba7d5bbbb79279a 100644 (file)
--- 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}
 
 \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. 
 
 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{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. 
 \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
 
 %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
 
 \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}
 
 \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.   
 
 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.
 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.