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

diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex
index 9d12c73..7cf0689 100644
--- a/THESE/Chapters/chapter2/chapter2.tex
+++ b/THESE/Chapters/chapter2/chapter2.tex
@@ -1,11 +1,12 @@
-L'Ã©tendue des techniques applicables aux images numÃ©riques est aujourd'hui si vaste qu'il serait illusoire de chercher Ã  les dÃ©crire ici. Ce chapitre prÃ©sente plus spÃ©cifiquement les algorithmes utilisÃ©s en prÃ©sence d'images (fortement) bruitÃ©es. Le bruit rend potentiellement dÃ©licate l'extraction des informations utiles contenues dans les images pertubÃ©es ou en complique l'interpretation, qu'elle soit automatique ou confiÃ©e Ã  la vision humaine. 
-L'intuition nous incite donc Ã  chercher des mÃ©thodes efficaces de prÃ©traitement pour rÃ©duire la puissance du bruit afin de permettre aux traitements de plus haut niveau comme la segmentation, d'opÃ©rer ensuite dans de meilleures conditions.           
+L'Ã©tendue des techniques applicables aux images numÃ©riques est aujourd'hui si vaste qu'il serait illusoire de chercher Ã  les dÃ©crire ici. Ce chapitre prÃ©sente plus spÃ©cifiquement les algorithmes utilisÃ©s en prÃ©sence d'images (fortement) bruitÃ©es. Le bruit rend potentiellement dÃ©licate l'extraction des informations utiles contenues dans les images perturbÃ©es ou en complique l'interprÃ©tation, qu'elle soit automatique ou confiÃ©e Ã  la vision humaine. 
+L'intuition nous incite donc Ã  chercher des mÃ©thodes efficaces de prÃ©-traitement pour rÃ©duire la puissance du bruit afin de permettre aux traitements de plus haut niveau comme la segmentation, d'opÃ©rer ensuite dans de meilleures conditions.           
 
 Toutefois, il faut Ã©galement considÃ©rer que les opÃ©rations prÃ©alables de rÃ©duction de bruit apportent des modifications statistiques aux images et influent donc potentiellement sur les caractÃ©ristiques que l'on cherche Ã  mettre en Ã©vidence grÃ¢ce au traitement principal. En ce sens, il peut-Ãªtre prÃ©fÃ©rable de chercher Ã  employer des algorithmes de haut niveau travaillant directement sur les images bruitÃ©es pour minimiser les effets des altÃ©rations apportÃ©es par les filtres dÃ©bruiteurs et conserver toute l'information contenue dans les images perturbÃ©es.
-%TODO
-% dire aussi que le prÃ©traitement, Ã§a prend du temps. C'est Ã©vident mais c'est mieux en le disant
- Les images auxquelles nous nous intÃ©ressons sont gÃ©nÃ©ralement les images numÃ©riques allant des images naturelles telles que dÃ©finies par Caselles \cite{Caselles99topographicmaps} aux images d'amplitude isues de l'imagerie radar Ã  ouverture synthÃ©tique (ROS ou en anglais SAR) \cite{cutrona1990synthetic}, de l'imagerie mÃ©dicale Ã  ultrasons (echographie) ou encore biologique dans le cas de la microscopie Ã©lectronique. 
-Ces dispositifs d'acquisition sont naturellement, et par essence, gÃ©nÃ©rateurs de bruits divers, inhÃ©rents aux thechnologies mises en \oe uvre au sein de ces systÃ¨mes et qui viennent dÃ©grader l'image idÃ©ale de la scÃ¨ne que l'on cherche Ã  reprÃ©senter ou analyser. On sait aujourd'hui caractÃ©riser de maniÃ¨re assez prÃ©cise ces bruits et la section \ref{sec_bruits} en dÃ©taille les  origines physiques ainsi que  les propriÃ©tÃ©s statistiques qui en dÃ©coulent.
+
+Enfin, toute opÃ©ration aussi basique soit elle, prend un certain temps qui rÃ©duit potentiellement celui disponible pour le traitement de haut niveau. Lorsque les images Ã  analyser sont de grande taille,  procÃ©der Ã  un dÃ©bruitage prÃ©alable peut s'avÃ©rer incompatible avec les contraintes de dÃ©bit et les temps requis par le traitement de haut niveau.
+
+ Les images auxquelles nous nous intÃ©ressons sont gÃ©nÃ©ralement les images numÃ©riques allant des images naturelles telles que dÃ©finies par Caselles \cite{Caselles99topographicmaps} aux images d'amplitude issues de l'imagerie radar Ã  ouverture synthÃ©tique (ROS ou en anglais SAR) \cite{cutrona1990synthetic}, de l'imagerie mÃ©dicale Ã  ultrasons (Ã©chographie) ou encore biologique dans le cas de la microscopie Ã©lectronique. 
+Ces dispositifs d'acquisition sont naturellement, et par essence, gÃ©nÃ©rateurs de bruits divers, inhÃ©rents aux technologies mises en \oe uvre au sein de ces systÃ¨mes et qui viennent dÃ©grader l'image idÃ©ale de la scÃ¨ne que l'on cherche Ã  reprÃ©senter ou analyser. On sait aujourd'hui caractÃ©riser de maniÃ¨re assez prÃ©cise ces bruits et la section \ref{sec_bruits} en dÃ©taille les  origines physiques ainsi que  les propriÃ©tÃ©s statistiques qui en dÃ©coulent.
 On peut dores et dÃ©jÃ  avancer que la connaissance de l'origine d'une image et donc des propriÃ©tÃ©s des bruits associÃ©s qui en corrompent les informations, est un atout permettant de concevoir des techniques de filtrage adaptÃ©es Ã  chaque situation. Toutefois, la recherche d'un filtre universel, bien qu'encore illusoire, n'est pas abandonnÃ©e, tant les besoins sont nombreux, divers et souvent complexes.    
        
 \section{ModÃ¨le d'image bruitÃ©e}
@@ -64,7 +65,7 @@ Le bruit de grenaille est de type multiplicatif et suit une loi de Poisson. La P
 La trÃ¨s grande majoritÃ© des algorithmes de rÃ©duction de bruit fait l'hypothÃ¨se que la perturbation est de type gaussien, mÃªme si le dÃ©veloppement des systÃ¨mes d'imagerie radar et mÃ©dicale a favorisÃ© l'Ã©tude des bruits multiplicatifs du type \textit{speckle} ou \textit{Poisson}.
 Un trÃ¨s grand nombre de travaux proposant des mÃ©thodes de rÃ©duction de ces bruits ont Ã©tÃ© menÃ©s, ainsi que beaucoup d'Ã©tats de l'art et d'Ã©tudes comparatives de ces diverses techniques, que nous n'avons pas l'ambition d'Ã©galer.
 
-Nous nous focaliserons sur les techniques en lien avec les travaux que nous avons menÃ©s et qui ont donnÃ© lieu Ã  des implÃ©mentations efficaces  susceptibles de fournir des Ã©lÃ©ments opÃ©rationnels rapides pour le prÃ©traitement des images. 
+Nous nous focaliserons sur les techniques en lien avec les travaux que nous avons menÃ©s et qui ont donnÃ© lieu Ã  des implÃ©mentations efficaces  susceptibles de fournir des Ã©lÃ©ments opÃ©rationnels rapides pour le prÃ©-traitement des images. 
 
 La figure \ref{fig-ny-noises} montre une image de synthÃ¨se issue de la base de test COIL \cite{coil}, supposÃ©e sans bruit et qui sera considÃ©rÃ©e comme rÃ©fÃ©rence, ainsi que deux versions bruitÃ©es, respectivement avec un bruit gaussien d'Ã©cart type 25 et un bruit impulsionnel affectant 25\% des pixels. 
 L'indice de qualitÃ© le plus employÃ© pour mesurer la similaritÃ© entre deux images est le PSNR (pour Peak Signal to Noise Ratio). Il est exprimÃ© en dÃ©cibels (dB) et se calcule en appliquant la formule  
@@ -202,9 +203,17 @@ On connait peu de versions GPU du filtre mÃ©dian, peut-Ãªtre en raison des impl
 Sur architecture GT200 (GTX260), les performances maximales de ces deux versions sont obtenues pour un masque de 3$\times$3 pixels avec respectivement 175~MP/s pour libJacket et 60~MP/s pour PCMF. 
 Une prÃ©cÃ©dente implÃ©mentation avait Ã©tÃ© rÃ©alisÃ©e, basÃ©e sur l'algorithme BVM dÃ©crit dans \cite{5402362}. Elle prouve son efficacitÃ© dans l'Ã©limination des artefacts gÃ©nÃ©rÃ©s par les dispositifs d'imagerie mÃ©dicale magnÃ©tique en 3D \cite{chen09}, mais ne permet pas d'exploiter vÃ©ritablement le parallÃ©lisme des GPU en filtrage d'image en 2D.
 
-La figure \ref{fig-compare-jacket-pcmf}, tirÃ©e de \cite{5402362}, compare ces trois implÃ©mentations et montre que le dÃ©bit permis par la libJacket dÃ©croit trÃ¨s vite avec la taille du masque pour passer Ã  30~MP/s dÃ¨s la taille 5$\times$5, alors que le PCMF dÃ©croit linÃ©airement jusqu'Ã  la taille 11$\times$11 oÃ¹ il permet encore de traiter quelque 40~MP/s. Ceci s'explique simplement par le fait que libJacket utilise un tri simple pour la sÃ©lection de la valeur mÃ©diane alors que le PCMF exploite les propriÃ©tÃ©s des histogrammes cumulÃ©s et n'est ainsi que trÃ¨s peu dÃ©pendant de la taille du masque.
+\begin{figure}
+  \centering
+  \subfigure[Sur GPU GTX260. Courbe tirÃ©e de \cite{5402362}]{\label{fig-compare-jacket-pcmf1}\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/compar-median1.png}}\quad
+  \subfigure[Sur GPU C2075. Courbe tirÃ©e de \cite{sanchez2013highly}]{\label{fig-compare-jacket-pcmf2}\includegraphics[width=7cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/compar-median2.png}}
+\caption{Performances relatives des filtres mÃ©dians implÃ©mentÃ©s sur GPU dans libJacket/ArrayFire, PCMF et BVM et exÃ©cutÃ©s sur deux modÃ¨le de gÃ©nÃ©rations diffÃ©rentes.}
+\label{fig-compare-jacket-pcmf}
+\end{figure}
+
+La figure \ref{fig-compare-jacket-pcmf1}, tirÃ©e de \cite{5402362}, compare ces trois implÃ©mentations et montre que le dÃ©bit permis par la libJacket dÃ©croit trÃ¨s vite avec la taille du masque pour passer Ã  30~MP/s dÃ¨s la taille 5$\times$5, alors que le PCMF dÃ©croit linÃ©airement jusqu'Ã  la taille 11$\times$11 oÃ¹ il permet encore de traiter quelque 40~MP/s. Ceci s'explique simplement par le fait que libJacket utilise un tri simple pour la sÃ©lection de la valeur mÃ©diane alors que le PCMF exploite les propriÃ©tÃ©s des histogrammes cumulÃ©s et n'est ainsi que trÃ¨s peu dÃ©pendant de la taille du masque.
  
-Plus rÃ©cemment, Sanchez \textit{et al.} ont actualisÃ© leurs mesures sur architecture Fermi (GPU C2075) en comparant leur PCMF Ã  la version rÃ©-Ã©crite en C de libJacket, nommÃ©e ArrayFire. Les courbes sont celles de la figure \ref{fig-compare-arrayfire-pcmf}, oÃ¹ l'on constate que les variations selon la taille du masque demeurent comparables, avec toutefois des valeurs de dÃ©bit augmentÃ©es, avec prÃ¨s de 185~MP/s pour ArrayFire et 82~MP/s pour PCMF. 
+Plus rÃ©cemment, Sanchez \textit{et al.} ont actualisÃ© dans \cite{sanchez2013highly} leurs mesures sur architecture Fermi (GPU C2075) en comparant leur PCMF Ã  la version rÃ©-Ã©crite en C de libJacket, nommÃ©e ArrayFire. Les courbes sont celles de la figure \ref{fig-compare-jacket-pcmf2}, oÃ¹ l'on constate que les variations selon la taille du masque demeurent comparables, avec toutefois des valeurs de dÃ©bit augmentÃ©es, avec prÃ¨s de 185~MP/s pour ArrayFire et 82~MP/s pour PCMF. 
 
 ParallÃ¨lement, on trouve aussi des implÃ©mentations de filtre mÃ©dian dans des traitements plus complexes comme dans \cite{aldinucci2012parallel} oÃ¹ les auteurs dÃ©crivent la plus rÃ©cente Ã©volution de leur technique itÃ©rative de rÃ©duction de bruit impulsionnel, sans qu'il soit possible d'Ã©valuer le dÃ©bit du mÃ©dian seul. 
 
@@ -410,7 +419,7 @@ On voit que la convergence est assez rapide mais que le contour ainsi dÃ©tÃ©rmin
 \subfigure[L'Ã©tat  du contour aprÃ¨s la septiÃ¨me itÃ©ration]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it7.png}}
 \subfigure[L'Ã©tat du contour aprÃ¨s la dixiÃ¨me itÃ©ration]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it10.png}}
 \subfigure[L'Ã©tat du contour aprÃ¨s la centiÃ¨me itÃ©ration. C'est le contour final.]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_result.png}}   
-\caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme dit du \textit{snake}, dans sa version originale. Les paramÃ¨tres d'Ã©lastictiÃ©, de raideur et d'attraction ont Ã©tÃ© fixÃ©s respectivement aux valeurs 5, 0.1 et 5. }
+\caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme dit du \textit{snake}, dans sa version originale. Les paramÃ¨tres d'Ã©lasticitÃ©, de raideur et d'attraction ont Ã©tÃ© fixÃ©s respectivement aux valeurs 5, 0.1 et 5. }
 \label{fig-snake-tradi-cochon}
 \end{figure} 
 
@@ -525,6 +534,14 @@ Les algorithmes de type \textit{snake}, trÃ¨s coÃ»teux en temps de calcul, pouva
 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.
 
+\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. }
+\label{fig-snakegvf}
+\end{figure}
+
 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.   
@@ -545,39 +562,18 @@ La figure \ref{fig-gPb} prÃ©sente quelques rÃ©sultats d'extraction de contours.
 \label{fig-gPb}
 \end{figure}
 
-     
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+\section{Conclusion}
+La prÃ©sentation que nous venons de faire des principales techniques de filtrage et de sÃ©gmentation ainsi que des implÃ©mentations sur GPU qui leur ont Ã©tÃ© consacrÃ©es nous ont permis de mettre une Ã©vidence en lumiÃ¨re : malgrÃ© leur orientation grand public et les langages de huat niveau permettant d'accÃ©der rapidement Ã  la programmation GPU, la parallÃ©lisation efficace d'un algorithme sÃ©quentiel destinÃ© Ã  s'exÃ©cuter sur ces processeurs n'est pas triviale. Le modÃ¨le et les contraintes de programmation leur sont spÃ©cifiques et obtenir un code rapide dÃ©coule nÃ©cessairement d'un compromis qui peut parfois Ãªtre complexe Ã  affiner. 
 
+Ajoutons que les gÃ©nÃ©rations de GPU qui se succÃ¨dent conservent certes des caractÃ©ristiques communes mais diffÃ¨rent suffisemment quant-Ã  la distribution des ressources, rendant toute gÃ©nÃ©ralitÃ© vaine et faisant qu'un code optimisÃ© pour un modÃ¨le donnÃ© peut devenir moins rapide avec un modÃ¨le plus rÃ©cent. Prenons l'exemple du nombre maximal de registres utilisables par thread ; il est de 128 sur GPU C1060 contre seulement de 63 pour un C2070. Un code faisant un usage optimisÃ© des registres sur C1060 pourra s'exÃ©cuter plus lentement sur C2070. C'est un cas de figure sur lequel nous reviendrons plus en dÃ©tail dans le chapitre consacrÃ© au filtre mÃ©dian.
 
+Cet Ã©tat de fait rend les rÃ©sultats publiÃ©s par les chercheurs souvent dÃ©licats Ã  intÃ©rprÃ©ter et plus encore Ã  reproduire lorsque l'on souhaite comparer les performances de nos propres codes avec les rÃ©fÃ©rences du moment, sauf Ã  disposer d'un panel de cartes GPU reprÃ©sentant toutes les Ã©volutions de l'architecture et ce pour au moins les deux grands fabricants de GPUs que sont ATI et Nvidia.   
 
+Pour aider les dÃ©veloppeurs Ã  allouer les ressources de maniÃ¨re optimale, ou tout du moins estimer le dÃ©grÃ© d'optimisation de leur code Ã  l'aune de la vitesse d'exÃ©cution, Nvidia fournit une feuille de calcul appelÃ©e \textit{occupancy calculator} dans laquelle ont peut entrer les paramÃ¨tres d'exÃ©cution d'un \textit{kernel} parallÃ¨le : nmobre de registres utilisÃ©s par chaque thread, quantitÃ© de mÃ©moire partagÃ©e, modÃ¨le de GPU, dimensions de la grille. Le tableur retourne alors l'indice de charge (l'occupancy) qui traduit le rapport, Ã  chaque instant, entre le nombre de warps actifs et le nombre maximal de warps par processeur (SM = Streaming Multiprocessor). L'occupancy se traduit donc par un indice compris entre 0 et 100\% et la recherche de performance semble devoir Ãªtre la recherche de l'occupancy maximale.
 
+Toutefois, comme l'a clairement demontrÃ© Volkov dans \cite{volkov2010better}, ce paradigme peut aisÃ©ment Ãªtre remis en cause et Volkov parvient effectivement Ã  amÃ©liorer les peformances d'un certain nombre d'exemples gÃ©nÃ©riques dans des conditions de faible valeur d'occupancy. 
+Enfin, nous avons pu constater deux grands modÃ¨les d'accÃ¨s aux donnÃ©es : les algorithmes de filtrage usent quasiment tous de la mÃ©moire partagÃ©e comme tampon d'accÃ¨s aux donnÃ©es de l'image en mÃ©moire globale (ou texture) alors que les algorithmes de segmentation performants s'en affranchissent. La raison en est clairement des motifs d'accÃ¨s trÃ¨s irrÃ©guliers et non contigus pour ces derniers, rendant la gestion efficace de la mÃ©moire partagÃ©e dÃ©licate et potentiellement si coÃ»teuse qu'elle en devienne sans intÃ©rÃªt.
+Les chapitres suivants prÃ©sentant nos contributions reviendront sur ces aspects en proposant des solutions pour accroÃ®tre la performance des algorithmes parallÃ©lisÃ©s.
 
 
 
