X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/5997a2db46b2dcd03451c2229f90a509b8db3759..d77325cc1ec33fa6968b1ae96b0c66df6120a06a:/THESE/Chapters/chapter2/chapter2.tex

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index b02fcc4..9d12c73 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -508,19 +508,46 @@ RÃ©cemment, Xiao et Liu ont dÃ©crit dans \cite{xiao2010efficient} une implÃ©ment
 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 !
+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 cela Ã©tait dÃ©jÃ  fait dans \cite{lefohn2003inter}.Tout cela est rÃ©alisÃ© sans recourir Ã  la mÃ©moire partagÃ©e qui s'avÃ¨re complexe voire impossile Ã  utiliser efficacement lorsque les Ã©lÃ©ments Ã  accÃ©der sont trÃ¨s irrÃ©guliÃ¨rement rÃ©partis en mÃ©moire. 
+
 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.
+Si l'on considÃ¨re que malgrÃ© les stratÃ©gies adoptÃ©es, tenir Ã  jour cette liste de pavÃ©s reprÃ©sente encore 77\% du temps de calcul, 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, aux 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}
+\label{fig-l7-narrow}
 \end{figure}
 
+Les algorithmes de type \textit{snake}, trÃ¨s coÃ»teux en temps de calcul, pouvaient prÃ©tendre Ã  bÃ©nÃ©ficier largement de la technologie des GPU pour amÃ©liorer leurs performances, mais seule la variante paramÃ©trique GVF Ã  vÃ©ritablement Ã©tÃ© implÃ©mentÃ©e de maniÃ¨re spÃ©cifique et efficace \cite{snakegvf06, bauer2009segmentation, li2011robust, snakegvfopencl12}. Les variantes de type gÃ©omÃ©trique, principalement en raison de l'irrÃ©gularitÃ© des motifs d'accÃ¨s Ã  la mÃ©moire, restent Ã  ce jour sans implÃ©mentation GPU.
+Parmi les premiÃ¨res solutions dÃ©crites, \cite{snakegvf06} propose une implÃ©mentation rÃ©alisÃ©e en openGL, oÃ¹ les donnÃ©es de gradient sont compactÃ©es en texture RVBA de maniÃ¨re Ã  s'affranchir du format 16 bits de la reprÃ©sentation : les deux premiers canaux R et V contiennent les valeursreprÃ©sentant respectivement le gradients selon $dx$ et $dy$ sous une forme codÃ©e par la valeurs des 2 autres canaux. 
+Par ailleurs, une approximation du systÃ¨me linÃ©aire Ã  rÃ©soudre est proposÃ©e afin de donner une structure bande symÃ©trique Ã  la matrice Ã  inverser, ce qui amÃ©liore considÃ©rablement l'efficacitÃ© des accÃ¨s aux donnÃ©es au travers du cache.
+
+Les performances annoncÃ©es montrent tout d'abord que l'approximation adoptÃ©e n'a qu'un impact extrÃªmement limitÃ© sur le rÃ©sulat de la segmentation avec un Ã©cart radial maximal infÃ©rieur Ã  1.3 pixel par rapport au calcul exact effectuÃ© sur CPU. Enfin, la segmentation de l'image d'exemple en 1024$^2$ pixels s'effectue en un total de 11~s aprÃ¨s l'initialisation manuelle reproduite Ã  la figure \ref{fig-snakegvf}. Cela est annoncÃ© comme presque 30 fois plus rapide que l'implÃ©mentation CPU de rÃ©fÃ©rence, mais demeure beaucoup trop lent pour un usage interactif.
+
+Une solution directe employant la transformÃ©e de fourier pour inverser le systÃ¨me Ã  rÃ©soudre a Ã©tÃ© dÃ©crite rÃ©cemment dans  \cite{zheng2012fast}et programmÃ©e en employant la bibliothÃ¨que openGL. Les exemples fournis montrent des objets segmentÃ©s dans des images d'environ 10000 pixels en une durÃ©e de l'ordre de la demi seconde.   
+
+En adaptant sur GPU une variante dite FD-snake \cite{li2011robust} du snake GVF (pour Fourier Descriptors) permettant une convergence plus rapide et un calcul parallÃ¨le beaucoup plus adaptÃ© au GPU, Li \textit{et al.} parviennent quant Ã  eux Ã  suivre les dÃ©formations d'un contour en temps rÃ©el dans des images issues d'examens Ã©chographique ; Un contour de 100 points pouvant converger convenablement en Ã  peine 30~ms. Une contribution supplÃ©mentaire de cette implÃ©mentation est de permettre une initialisation simplifiÃ©e et semi-automatique du contour. 
+
+La plus aboutie des implÃ©mentations actuelles du snake GVF est enfin celle prÃ©sentÃ©e par Smistad \textit{et al.} dans \cite{snakegvfopencl12} et 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 openGL permet d'exÃ©cuter le code sur les GPU des deux principaux fabricants.   
+
+\subsection{Algorithmes hybrides}
+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 semgentation d'objets et personnages dans des image naturelles, Ã  Ã©tÃ© implÃ©mentÃ© en CUDA par Catanzaro \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 Ã  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.
+\begin{figure}
+  \centering
+\includegraphics[height=4cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/gPb_examples.png}
+\caption{Extraction de contour par la version GPU de l'algorithme gPb. Les images sont issues de la base BSDS  \cite{martin2001database}}
+\label{fig-gPb}
+\end{figure}
+
+     
+
+
 
 
 
