diapo v2

[these_gilles.git] / PRESENTATION / diapos.rst

diff --git a/PRESENTATION/diapos.rst b/PRESENTATION/diapos.rst
index adad7b43e117721554a2a9769ed1c31ea49e66c1..8a0274d9f42c8805790ec20474b31422b22ebfe1 100644 (file)
--- a/PRESENTATION/diapos.rst
+++ b/PRESENTATION/diapos.rst
@@ -32,236 +32,212 @@
 TRAITEMENT D'IMAGES SUR GPU 
 ===========================
 
 TRAITEMENT D'IMAGES SUR GPU 
 ===========================
 

-Algorithmes parrallèles rapides pour le filtrage et la segmentation des images bruitées sur GPU.
+Algorithmes rapides pour le filtrage et la segmentation des images bruitées sur GPU.

 ------------------------------------------------------------------------------------------------
 
 Gilles Perrot
 +++++++++++++
 ------------------------------------------------------------------------------------------------
 
 Gilles Perrot
 +++++++++++++

-
+17 avril 2014
++++++++++++++

 Université de Franche-Comté, Institut FEMTO-ST 
 +++++++++++++++++++++++++++++++++++++++++++++++
 Département DISC - équipe AND
 Université de Franche-Comté, Institut FEMTO-ST 
 +++++++++++++++++++++++++++++++++++++++++++++++
 Département DISC - équipe AND

-+++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++
+Direction  : R. Couturier & S. Domas
+++++++++++++++++++++++++++++++++++++

 
 ----
 
 
 ----
 

-PLAN DE LA PRÉSENTATION
-=======================
+FILTRAGE
+========

 
 

-#. Introduction - cadre des travaux
+Réduire le bruit.

 
 

-   - Les GPUs (Graphical Processing Units)
-   - Généralités sur le traitement d'image. Nos axes de recherche.
+.. image:: img/ex-filtrage.png
+   :width: 800px

 
 

-#. La segmentation des images
+.. note::
+ 
+ * les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.
+ *  Les capteurs numériques et les conditions d'acquisition sont à l'origine de perturbations (bruits).
+ * Les hautes résolutions sont souvent obtenues à faible flux de photons, dont les variations engendrent du bruit. 

 
 

-   - Généralités. Travaux de référence.
-   - Parallélisation GPU d'un algorithme de segmentation de type *snake*.
+----

 
 

-#. Le filtrage des images
+SEGMENTATION
+============

 
 

-   - Généralités. Travaux de référence. 
-   - Optimisation pour GPU des filtres médian et de convolution.
-   - Conception d'un algorithme parallèle de réduction de bruit par recherche des lignes de niveaux.
+Distinguer les zones homogènes d'une image.

 
 

-#. Synthèse et conclusion. 
+.. image:: img/seg1.png
+   :width: 700px

 
 

-----
+.. note::
+
+ * on recense plus de 4000 algorithmes de segmentation
+ * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
+ * Mais aujourd'hui encore, une bonne segmentation est celle qui permet d'extraire ce que l'on attend => l'algorithme dépend du problème. 

 
 

-INTRODUCTION
-============

 
 ----
 
 
 ----
 

-INTRODUCTION
+SEGMENTATION

 ============
 ============

-Les GPUs ou *Processeurs graphiques*.
--------------------------------------
+Deux approches

 
 

-.. image:: img/gpucpu1.png
-   :height: 400px
+.. image:: img/approches.png
+   :width: 800px

 
 

+.. note::

 
 

-* Processeurs *classiques* **CPU** : exécution **séquentielle** 
+ *  **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*. 

 
 

-  - Quelques unités de calcul ( les c |oe| urs).
+   * réduction, *a priori*, du coût des traitements de haut niveau.
+   * les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.
+ 
+ * **Ne pas pré-traiter** et effectuer les traitements de haut niveau sur les images bruitées.

 
 

-* Processeurs *graphiques* **GPU** : exécution **massivement parallèle**
+   * pas de perte d'information due au pré-traitement. 

 
 

-  - Des centaines, voire millier, d'unités de calcul, regroupées en quelques SMs (*Streaming Multiprocessors*).
+----

 
 

-----  
+PLAN DE LA PRÉSENTATION
+=======================

 
 

-INTRODUCTION
-============
-Les GPUs ou *Processeurs graphiques*.
--------------------------------------
+#. Introduction 

 
 

-* La multiplication des c |oe| urs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
-* Seule la mémoire *globale* est accessible par l'ensemble des fils d'exécution (les *threads*) et ses performances sont faibles.
-* L'accès efficace aux différents types de mémoires est contraignant.
-* Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
-* Il est important de concevoir un partage équilibré des ressources au sein de chaque SM, pour permettre un niveau de parallélisme élevé, et donc d'envisager de bonnes performances.
-* La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.
+   - Les GPUs ou *Graphical Processing Units*.
+   - Le filtrage et la segmentation d'images.

 
 

-----   
+#. La segmentation des images

 
 

-INTRODUCTION
-============
-Le traitement des images
-------------------------
+   - Travaux de référence.
+   - Parallélisation GPU d'un algorithme de segmentation de type *snake*.

 
 

-* Beaucoup d'applications sont basées sur l'analyse ou la visualisation d'images numériques.    
-* Les capteurs numériques et les conditions d'acquisition sont à l'origine de perturbations (bruits) qui dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.
-* La réduction de bruit demeure un thème important, car les hautes résolutions sont souvent obtenues à faible flux de photons, dont les variations engendrent du bruit. 
-* La segmentation représente aussi un enjeu crucial, mais aucun algorithme universel n'a encore été élaboré.
+#. Le filtrage des images

 
 

-.. note:: 
+   - Travaux de référence. 
+   - Optimisation GPU des filtres médian et de convolution.
+   - Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.

 
 

- * on recense plus de 4000 algorithmes de segmentation
- * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
- * Mais aujourd'hui encore, une bonne segmentation est celle qui permet d'extraire ce que l'on attend => l'algorithme dépend du problème. 
+#. Conclusion et perspectives 

 
 ----
 
 INTRODUCTION
 ============
 
 ----
 
 INTRODUCTION
 ============

-Le traitement des images
-------------------------
+Les GPUs ou *Processeurs graphiques*.
+-------------------------------------

 
 

-* L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
-* Les traitements envisagés sur les images sont de plus en plus évolués ( traitements de haut niveau ) et requièrent souvent un temps de calcul accru.
-* L'architecture parallèle particulière des GPUs a permis d'améliorer considérablement les performances de certaines classes d'algorithme et fait espérer des accélérations importantes pour d'autres.
- 
-**Nos travaux sont une contribution à cette recherche de performance.**
+.. image:: img/gpucpu1.png
+   :width: 800px

 
 

-.. note:: 

 
 

- * La croissance des capacités de calcul des GPUs à été beaucoup plus forte que celle des CPUs.
- 
+* Processeurs *classiques* **CPU** : exécution **séquentielle** 

 
 

-----
+  - Quelques unités de calcul ( les c |oe| urs).

 
 

-INTRODUCTION
-============
-Traitements d'images de haut niveau
------------------------------------
+* Processeurs *graphiques* **GPU** : exécution **massivement parallèle**

 
 

-#. **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*. 
+  - Des centaines, voire milliers, d'unités de calcul, regroupées en SMs (*Streaming Multiprocessors*).

 
 

-   * permet, *a priori*, de réduire le coût des traitements de haut niveau.
-   * les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.
- 
-#. **Ne pas pré-traiter** et effectuer les traitements de haut niveau sur les images bruitées.
+.. note::

 
 

-   * permet de ne pas subir la perte d'information occasionnée par le pré-traitement.
-   * les traitements de haut niveau sont, *a priori*, plus coûteux.  
+ * La multiplication des c |oe| urs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
+ * Seule la mémoire *globale* est accessible par l'ensemble des fils d'exécution (les *threads*) et ses performances sont faibles.
+ * AU sein de la RAM il y a différents canaux vers différents types de mémoires.
+ * L'accès efficace aux mémoires  est contraignant.
+ * Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
+ * Il est important de concevoir un partage équilibré des ressources au sein de chaque SM, pour permettre un niveau de parallélisme  élevé, et donc d'envisager de bonnes performances.
+ * La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.

 
 

+ * L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
+ * Les traitements envisagés sur les images sont de plus en plus évolués ( traitements de haut niveau ) et requièrent souvent un temps de calcul accru.
+ * L'architecture parallèle particulière des GPUs a permis d'améliorer considérablement les performances de certaines classes d'algorithme et fait espérer par ailleurs des accélérations importantes.

 
 

-.. note:: 

 
 

- Certains algo (LNIV) peuvent être considérés comme pré-traitement ou comme haut-niveau selon le point de vue et la classe d'algorithme.

 
 

-----
+----   

 
 INTRODUCTION
 ============
 
 INTRODUCTION
 ============

+Le traitement des images
+------------------------

 
 

-Axes des travaux présentés
---------------------------
-
+**Le filtrage (du bruit)**

 
 

-**Segmentation : accélérer le traitement de haut niveau**
- 
- * La segmentation consiste à identifier des zones homogènes dans une image.   
- * Algorithme de segmentation d'images bruitées (fortement) par contours actifs, appartenant à la classe communément appelée  *snakes*.
+ * Les capteurs et les conditions d'acquisition induisent du bruit.
+ * *Résolution élevée* n'implique pas *bruit réduit*. 

 
 

-**Filtrage : accélérer les pré-traitements**
+**La segmentation**

 
 

- Réduction de bruit additif gaussien, suivant deux méthodes de conception  :
+ * Enjeu important.
+ * Aucun algorithme universel.

 
 

-     * algorithme original, conçu spécifiquement pour GPU, conjointement à son implémentation.
-     * algorithmes existants, où l'effort de conception ne peut porter que sur l'implémentation : filtres médian et de convolution.
+.. note:: 

 
 

+ * les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.
+ * on recense plus de 4000 algorithmes de segmentation
+ * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
+ * Mais aujourd'hui encore, une bonne segmentation est celle qui permet d'extraire ce que l'on attend => l'algorithme dépend du problème. 

 
 ----
 
 INTRODUCTION
 ============
 
 
 ----
 
 INTRODUCTION
 ============
 

-Images traitées
----------------
+Ojectif : accélérer
+-------------------

 
 

-* Nous nous sommes focalisés sur les *images naturelles* :

 
 

- - réalisées en lumière naturelle, en intérieur aussi bien qu'en extérieur,
- - prises avec un dispositif standard (CMOS, CCD).
+**Segmentation**
+ 
+ * Algorithme par contours actifs, classe des  *snakes*.
+ * Implémentation CPU optimisée existante. 
+ * Conception de l'implémentation GPU.
+ * Adaptations mineures de l'algorithme. 

 
 

-* Les traitements que nous présentons ici opèrent sur des images en 
-  niveau de gris (8 ou 16 bits). 
+**Filtrage**

 
 

-.. note:: 
+     * Filtre par lignes de niveaux 
+        
+         - Algorithme original,
+         - Conceptions conjointes algorithme et implémentation.

 
 

- Toutefois, la plupart des algorithmes que nous proposons s'étend simplement à d'autres types d'images, comme les images en couleur ou celles issues des imageries ultrasonore ou RADAR à ouverture synthétique.  
+     * Filtres médians, filtres de convolution

 
 

-----
-
-LA SEGMENTATION DES IMAGES
-==========================
-Segmentation par contour actif
+          - Opérateurs mathématiques,
+          - Conception d'une implémentation optimisée.
+  

 
 ----
 
 SEGMENTATION PAR CONTOUR ACTIF 
 ==============================
 
 ----
 
 SEGMENTATION PAR CONTOUR ACTIF 
 ==============================

-Introduction
-------------
-
-* Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
-* Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
-* La segmentation par contour actif regroupe des méthodes itératives tendant à faire converger, par déformation successive, une courbe paramétrique (contour) selon un critère d'homogénéité pré-établi :
+Travaux de référence
+--------------------

 
 

- - La classe d'algorithmes la plus implémentée est celle des **level-set**, essentiellement dans sa variante *bande étroite*.
- - La classe des **snakes** n'est implémentée qu'au travers la variante GVF (Gradient Vector Flow).
+**Level-set** ( Roberts *et al.*, 2010) 

 
 

-.. figure:: img/l7-gvf.png
-   :width: 600px
+ * Images d'IRM de 256x256x256 pixels (16 millions),
+ * Temps sur GTX280 : **11 s**.

    
    

-   À  gauche : Level-set, évolution du contour, en rouge. À droite : visualisation du champ de force d'un *snake* GVF. 
+**Snake GVF** (Smistad *et al.*, 2012)

 
 

-----
+ * Images d'IRM de 256x256x256 pixels (16 millions),
+ * Temps sur C2070 : **7 s**.

 
 

-SEGMENTATION PAR CONTOUR ACTIF 
-==============================
-Travaux de référence (level-set)
---------------------------------
-
-L'implémentation de Roberts *et al.*  du *level-set* à *bande étroite* est actuellement la plus performante et parvient à segmenter des images d'IRM 
-
- - 3D, de 256x256x256 pixels, sur GTX280, en **11 000 ms**
+.. figure:: img/brain3D-gvf.png
+   :width: 600px

 
 

-.. figure:: img/brain3D.png
-   :width: 800px
-   
-   À  gauche : évolution du contour pour une *tranche* avec, en bleu, les zones actives. À droite : visualisation  en 3D de la segmentation complète. 

 
 

-----

 
 

-SEGMENTATION PAR CONTOUR ACTIF 
-==============================
-Travaux de référence (snake)
-----------------------------
-
-* À notre connaissance, aucune publication ne décrit d'implémentation de *snake* polygonal ou de *snake* orienté région.
-* La référence est l'implémentation *snake GVF*  de Smistad *et al.* qui parvient à segmenter des images d'IRM
+.. note::

 
 

- - 2D, de 512x512 pixels, sur C2070, en **41 ms**.
- - 3D, de 256x256x256 pixels, sur C2070, en **7151 ms**
-
-.. figure:: img/brain3D-gvf.png
-   :width: 600px
-   
-   À  gauche : une image 2D d'IRM. À droite : visualisation  en 3D de la segmentation complète. 
+ * Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
+ * Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
+ * Les algorithmes **level-set** sont les plus implémentés sur GPU :
+ * Les algorithmes **snakes** sont très peu implémentée sur GPU :

 
 ----
 
 
 ----
 


@@ -278,31 +254,21 @@ SEGMENTATION PAR CONTOUR ACTIF
 
     * - .. image:: img/snake-modele.png 
                 :width: 350px 
 
     * - .. image:: img/snake-modele.png 
                 :width: 350px 

-      - * L'objectif est de déterminer le contour le plus *vraisemblable* (nombre et positions des n |oe| uds).
+      - * Objectif : déterminer le contour le plus *vraisemblable*.

         *  Le critère de vraisemblance généralisée est, dans le cas gaussien :
            
            .. math::
             
               $$GL = \frac{1}{2}\left[ n_B.log\left(\sigma_B^2\right) + n_T.log\left(\sigma_T^2\right)\right]$$        
        
         *  Le critère de vraisemblance généralisée est, dans le cas gaussien :
            
            .. math::
             
               $$GL = \frac{1}{2}\left[ n_B.log\left(\sigma_B^2\right) + n_T.log\left(\sigma_T^2\right)\right]$$        
        

-* Les deux régions, intérieure et extérieure (T et B), sont prises en compte dans l'évaluation du contour. Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple. 
-* Les variances :math:`\(\sigma^2\)` doivent être calculées pour chaque état du contour, ce qui est **très coûteux**. 
-
-----
-
-SEGMENTATION PAR CONTOUR ACTIF 
-===============================
-*Snake* polygonal orienté région (principe)
---------------------------------------------
+* Calcul des variances :math:`\(\sigma^2\)` pour chaque contour :

 
 

-* Chesnaud *et al.* ont montré comment réaliser le calcul des variances par une **sommation 2D** le long du contour, au lieu d'une classique sommation 3D sur la surface des régions concernées.
-* Cette optimisation algorithmique implique de **pré-calculer** les trois images cumulées
+ * Méthode de Chesnaud *et el.* (1999) en :math:`\(\mathcal{O}(n^2)\)`. 
+ * Implique le **pré-calcul** de 3 images cumulées.

 
 

-  .. math::
-    
-     $$S_1(i,j)=\sum_{x=0}^jx \text{ , }  S_x(i,j)=\sum_{x=0}^jI(i,x) \text{ et  } S_x^2(i,j)=\sum_{x=0}^jI(i,x)^2$$
+.. note::

 
 

-* Les valeurs des éléments de ces images cumulées permettent de calculer la **contribution** de chaque pixel du contour, puis de chaque segment, aux calculs des variances.
+ * Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple. 

 
 ----
 
 
 ----
 


@@ -330,22 +296,12 @@ SEGMENTATION PAR CONTOUR ACTIF
 .. image:: img/cochons-it21-it22.png
    :height: 300px
 
 .. image:: img/cochons-it21-it22.png
    :height: 300px
 

-**Itération 2**
-
- 3. Ajout de n |oe| uds au milieu des segments suffisamment grands.
- #. On recommence à évaluer les déplacements successifs des n |oe| uds.
-
-----
-
-SEGMENTATION PAR CONTOUR ACTIF 
-===============================
-*Snake* polygonal orienté région (algo CPU)
---------------------------------------------
-

 .. image:: img/cochons-it4-it5.png
    :height: 300px
 
 .. image:: img/cochons-it4-it5.png
    :height: 300px
 

-**Itérations 4 et 5**
+.. note:: 
+
+ * CONVERGENCE RAPIDE

 
 ----
 
 
 ----
 


@@ -354,24 +310,14 @@ SEGMENTATION PAR CONTOUR ACTIF
 *Snake* polygonal orienté région (algo CPU)
 --------------------------------------------
 
 *Snake* polygonal orienté région (algo CPU)
 --------------------------------------------
 

-.. figure:: img/im014.png
-   :height: 400px
-
-   Image de 512x512 : contour final de 256 n |oe| uds en 14ms.
+Exemples de résultats 

 
 

-* Les résultats de segmentation dépendent des paramètres de la séquence d'optimisation (pas des déplacements, contour initial, seuil d'ajout des n |oe| uds)
-
-----
-
-SEGMENTATION PAR CONTOUR ACTIF 
-===============================
-*Snake* polygonal orienté région (algo CPU)
---------------------------------------------
+.. figure:: img/snake-exs.png
+   :width: 700px

 
 

-.. figure:: img/snakegpu1.png
-   :height: 400px
+.. note ::

 
 

-   Image de 4000x4000 : contour final de 447 n |oe| uds en 700ms.
+ * Les résultats de segmentation dépendent des paramètres de la séquence d'optimisation (pas des déplacements, contour initial, seuil d'ajout des n |oe| uds)

 
 ----
 
 
 ----
 


@@ -390,10 +336,10 @@ SEGMENTATION PAR CONTOUR ACTIF
 ===============================
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------
 ===============================
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------

-Détail de la fonction de calcul du critère GL
+Calcul du critère GL

 
 

-.. image:: img/algosnake2b.png
-   :height: 500px
+.. image:: img/algosnake-3etages.png
+   :width: 800px

 
 
 ----
 
 
 ----


@@ -412,21 +358,7 @@ Parallélisation du *Snake* polygonal sur GPU
  * Pour éviter les oscillations et *coller* à l'algorithme séquentiel, on distingue les n |oe| uds d'indices pairs et impairs.
  * On évalue **en parallèle** l'ensemble des déplacements éventuels de tous les n |oe| uds de même parité. 
 
  * Pour éviter les oscillations et *coller* à l'algorithme séquentiel, on distingue les n |oe| uds d'indices pairs et impairs.
  * On évalue **en parallèle** l'ensemble des déplacements éventuels de tous les n |oe| uds de même parité. 
 

-----
-
-SEGMENTATION PAR CONTOUR ACTIF 
-===============================
-Parallélisation du *Snake* polygonal sur GPU
---------------------------------------------

 
 

-**Structure des données** (n |oe| uds pairs)
-
-.. image:: img/snake-segments-pairs.png
-   :width: 800px
-
-.. note:: 
-
-  * règle 1 thread par pixel

 
 ----
 
 
 ----
 


@@ -435,17 +367,14 @@ SEGMENTATION PAR CONTOUR ACTIF
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------
 
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------
 

-**Obtention du critère**
-
-* Parallélisation :  1 thread par pixel. 
+* 1 thread par pixel.
+* Concaténation de tous les pixels composant l'ensemble des contours évalués. 
+* Réductions en mémoire partagée. 

 * Une seule taille de segment : la taille du plus long. 
 * Une seule taille de segment : la taille du plus long. 

-* Bourrage avec des threads inactifs pour les segments plus courts.
-* Calcul réalisé en 3 étapes par 3 fonctions parallèles GPU (*kernels*)

 
 

- #. Calcul des coordonnées des pixels. Lecture des paramètres de chaque pixel dans les images cumulées. Sommes partielles, par bloc, des contributions des segments.  
- #. Calcul final des contributions des segments par sommation des résultats du *kernel* précedent.
- #. Calcul des valeurs du critère pour chaque contour évalué. Sélection du meilleur contour.
+.. note::

 
 

+ * les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1

 
 ----
 
 
 ----
 


@@ -454,13 +383,17 @@ SEGMENTATION PAR CONTOUR ACTIF
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------
 
 Parallélisation du *Snake* polygonal sur GPU
 --------------------------------------------
 

-**Propriétés de l'implémentation**
+Points positifs :

 
  * Conservation des données en mémoire GPU. 
 
  * Conservation des données en mémoire GPU. 

- * Les images cumulées sont calculées en parallèle. 
- * Abandon de l'algorithme de Bresenham pour la discretisation des segments. 
- * Trop peu de calculs à effectuer. 
- * Pas de coalescence possible dans les accès à la mémoire globale.
+ * Images cumulées calculées en parallèle. 
+ * Discretisation des segments en parallèle (1 thread/pixel). 
+ * Respect de l'algorithme original.
+
+Points négatifs :
+
+ * Trop peu de calculs à effectuer.
+ * Motifs d'accès à la mémoire globale trop irréguliers.

  * Emploi de la mémoire partagée.    
  
 .. note::
  * Emploi de la mémoire partagée.    
  
 .. note::


@@ -487,7 +420,7 @@ Parallélisation du *Snake* polygonal sur GPU
 ..
  
 .. image:: img/perfs-snake-img.png
 ..
  
 .. image:: img/perfs-snake-img.png

-   :width: 600px
+   :width: 400px

 
 ----
 
 
 ----
 


@@ -499,24 +432,24 @@ Parallélisation du *Snake* polygonal sur GPU
 **Conclusion**
 
 * Première et seule implémentation à ce jour.
 **Conclusion**
 
 * Première et seule implémentation à ce jour.

-* Performances intéressantes pour les grandes images. 1OO MP en moins de 0,6 seconde.  
-* Temps de calcul très dépendant du contenu de l'image.
-* Le GPU n'est pas employé de manière optimale : réductions, threads inactifs, non coalescence.
-* Le GPU apporte un gain important sur les premières itérations, quand les segments sont grands.
-* Initialisation optionnelle par maximum de vraisemblance. Accélération jusqu'à x15 avec de petites cibles.
+* Performances intéressantes pour les grandes images.
+* Image 10000x10000 en moins de 0,6 seconde.  
+* Emploi non optimal du GPU : réductions, irrégularités.
+* Premières itérations GPU rapides : grands segments.
+* Temps de calcul très dépendant du contenu de l'image :
+
+  - Proposition d'une méthode d'initialisation alternative.
+  - Recherche du contour rectangle le plus vraisemblable.  
+  - Accélération jusqu'à x15 avec de petites cibles.

   
 ----
 
 LE FILTRAGE DES IMAGES
 ======================
   
 ----
 
 LE FILTRAGE DES IMAGES
 ======================

-Filtre médian - Filtres de convolution - Filtre par lignes de niveaux

 
 

-----
-
-LE FILTRAGE DES IMAGES
-======================
-Filtre médian
--------------
+  * Filtre médian, 
+  * Filtres de convolution, 
+  * Filtre par recherche des lignes de niveaux (PIPD).

 
 ----
 
 
 ----
 


@@ -534,7 +467,7 @@ La valeur de sortie d'un pixel est la **médiane** des valeurs de son voisinage.
 * Valeurs de sortie appartenant au voisinage.
 * Opération de sélection coûteuse (tri).
 * Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).
 * Valeurs de sortie appartenant au voisinage.
 * Opération de sélection coûteuse (tri).
 * Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).

-* Quelques applications avec de grandes fenêtres (au delà de 21x21).
+* Quelques applications avec de grandes fenêtres.

 
 ----
 
 
 ----
 


@@ -558,10 +491,11 @@ LE FILTRAGE DES IMAGES
 Filtre médian GPU : Travaux de référence
 ----------------------------------------
 
 Filtre médian GPU : Travaux de référence
 ----------------------------------------
 

-* Sanchez *et al.* ont proposé le **PCMF** et l'ont comparé, sur C2075, avec les implémentations GPU de référence pour une image 8 bits de 512x512 (débit max. **80 MP/s**) :
+Comparaison des implémentations GPU de référence :

 
 

- - **ArrayFire**, bibliothèque commerciale, débit max. **185 MP/s**
- - **BVM** parallélisé par Kachelrie |B|, débit max. **110 MP/s** 
+ - **PCMF**, Sanchez *et al.* (2013), débit max. **80 MP/s**,
+ - **ArrayFire**, bibliothèque commerciale, débit max. **185 MP/s**,
+ - **BVM** parallélisé par Chen *et al.* (2009), débit max. **110 MP/s**. 

 
 .. image:: img/compar-median2.png
    :width: 500px 
 
 .. image:: img/compar-median2.png
    :width: 500px 


@@ -578,11 +512,15 @@ LE FILTRAGE DES IMAGES
 Filtre médian GPU : Travaux de référence  
 ----------------------------------------
 
 Filtre médian GPU : Travaux de référence  
 ----------------------------------------
 

-Emploi de la **mémoire partagée** pour pré-charger les valeurs utiles à chaque bloc de threads.
+Emploi de la **mémoire partagée** (exemple médian 5x5)

 
 .. image:: img/shmemhalo.png   
    :width: 800px
  
 
 .. image:: img/shmemhalo.png   
    :width: 800px
  

+.. note:: 
+
+ - recouvrement pose problème à cause accès concurrents à la mémoire partagée.
+

 ----
 
 LE FILTRAGE DES IMAGES
 ----
 
 LE FILTRAGE DES IMAGES


@@ -590,12 +528,11 @@ LE FILTRAGE DES IMAGES
 Optimisation du filtre médian GPU  
 ---------------------------------
 
 Optimisation du filtre médian GPU  
 ---------------------------------
 

-Transferts des données optimisés
-
- CPU :math:`\(\rightarrow\)` GPU texture :KERNEL:  GPU globale :math:`\(\rightarrow\)` CPU non paginée
+.. image:: img/CPU-GPU-memcpy.png
+   :width: 650px

 
 

- .. image:: img/transferts-mem.png
-   :width: 650px 
+.. image:: img/transferts-mem.png
+   :height: 300px 

 
 .. note::
 
 
 .. note::
 


@@ -608,7 +545,12 @@ LE FILTRAGE DES IMAGES
 Optimisation du filtre médian GPU  
 ---------------------------------
 
 Optimisation du filtre médian GPU  
 ---------------------------------
 

-Débits maximums effectifs, en MP/s, pour des images en 8 et 16 bits, incluant les transferts optimisés (C2070).
+
+.. image:: img/CPU-GPU-memcpy-dummykernel.png
+   :width: 750px
+
+
+Débits maximums effectifs, en MP/s, sur C2070.

 
  .. image:: img/debit-max-2070.png
    :width: 300px
 
  .. image:: img/debit-max-2070.png
    :width: 300px


@@ -628,10 +570,14 @@ Optimisation du filtre médian GPU
 
 **Sélection de la médiane**
 
 
 **Sélection de la médiane**
 

- * Emploi exclusif des **registres** pour charger les valeurs utiles.
- * Limitations à 63 registres par thread et 32 K par bloc de threads.
- * Envisageable pour les médians de petite taille (jusqu'à 7x7 avec 1 thread/pixel).
- * Exploitation des recouvrements entre fenêtres de pixels voisins.
+ * Emploi exclusif des **registres** pour charger les valeurs utiles
+
+     - mémoires individuelles au c |oe| ur du GPU,
+     - non indexables dans un tableau.
+     - maximum de 63 registres par thread et 32 K par bloc de threads.
+
+ * Pour les petites tailles : max. 7x7 avec 1 pixel/thread.
+ * Exploitation des recouvrements entre fenêtres voisines.

    
   
 ----
    
   
 ----


@@ -649,10 +595,12 @@ Optimisation du filtre médian GPU
     :widths: 50 80 
     :header-rows: 0 
 
     :widths: 50 80 
     :header-rows: 0 
 

-    * - Bonnes performances envisagées :
-
-         * Économie de registres.
-         * Évite le tri complet. 
+    * - Avantages :
+ 
+        * Évite le tri complet : performances en hausse,
+        * Économie de registres : :math:`\(\lceil \frac{n}{2}\rceil +1\)` au lieu de :math:`\(n\)`,
+        * Permet de plus grandes tailles : max 11x11.
+          

       - .. image:: img/forgetful_selection.png
            :height: 500px
 
       - .. image:: img/forgetful_selection.png
            :height: 500px
 


@@ -663,12 +611,12 @@ LE FILTRAGE DES IMAGES
 Optimisation du filtre médian GPU  
 ---------------------------------
 
 Optimisation du filtre médian GPU  
 ---------------------------------
 

-**Exploitation des recouvrements**
+**Exploitation des recouvrements** : 2 pixels par thread (médian 5x5).

 
 .. image:: img/recouvrement5.png
      :width: 800px
 
 
 .. image:: img/recouvrement5.png
      :width: 800px
 

-**Intérêt :**  Économie de registres - chaque thread traite 2 pixels. 
+À 4 pixels/thread, zone commune = 10 pixels < 14 : **pas performant**.

 
 .. note:: 
 
 
 .. note:: 
 


@@ -679,29 +627,7 @@ Optimisation du filtre médian GPU
 
 LE FILTRAGE DES IMAGES
 ======================
 
 LE FILTRAGE DES IMAGES
 ======================

-Optimisation du filtre médian GPU  
----------------------------------
-
-**Masquage des latences**
-
-* Accès à la mémoire globale : 2 pixels par thread.
-* Instruction Level Parallelism (ILP) : Ordre des instructions minimisant l'interdépendance.
-
-  .. figure:: img/bitonic.png
-     :height: 300px 
-
-     Identification des extrema dans le vecteur initial d'un médian 5x5
-
-.. note:: 
-
-   * au delà de 2 pixels par thread, le gain sur les latences est compensé par la perte sur le calcul / niveau de parallèlisme.
-   * ILP maximisée en appliquant une méthode simple; utilisée par ex. dans la technique des réseaux de tri bitoniques. 
-
-----
-
-LE FILTRAGE DES IMAGES
-======================
-Performances du filtre médian GPU proposé (PRMF)  
+Performances du médian GPU proposé (PRMF)  

 ------------------------------------------------
 
 .. image:: img/perf-median.png
 ------------------------------------------------
 
 .. image:: img/perf-median.png


@@ -724,6 +650,10 @@ Image 4096x4096
  .. image:: img/comp4k.png  
     :height: 200px
 
  .. image:: img/comp4k.png  
     :height: 200px
 

+.. note::
+
+ * débit décroit linéairement en fonction de **n**
+

 ----
 
 LE FILTRAGE DES IMAGES
 ----
 
 LE FILTRAGE DES IMAGES


@@ -734,24 +664,18 @@ Le filtre médian GPU
 **Conclusion**
 
  * Pas d'utilisation de la mémoire partagée.
 **Conclusion**
 
  * Pas d'utilisation de la mémoire partagée.

- * Débit global amélioré de x7 à x10, proche du maximum.
- * Débit de calcul atteignant **5,3 GP/s**. 
- * Médian jusqu'au 9x9 sur C2070, 21x21 sur K40. 
+ * Accès optimaux : 1 lecture par pixel.
+ * Débit global amélioré de **x7** à **x10**, proche du maximum.
+ * Débit de calcul max. **5,3 GP/s**. 
+ * Médian jusqu'au 11x11 sur C2070, 21x21 sur K40. 

  * Création d'une application web générant les codes sources.
  * Création d'une application web générant les codes sources.

- * Utilisé pour le pré-traitement d'images de cristallographie  au synchrotron **SPring-8** (Japon).
+ * Utilisé sur images de cristallographie au synchrotron **SPring-8**.

  
  

-.. image:: img/SPring8.png
+.. image:: img/spring82.png

     :height: 200px 
 
 ----
 
     :height: 200px 
 
 ----
 

-LE FILTRAGE DES IMAGES
-======================
-Les filtres de convolution 
---------------------------
-
-----
-

 LE FILTRAGE DES IMAGES
 ======================
 Les filtres de convolution : généralités  
 LE FILTRAGE DES IMAGES
 ======================
 Les filtres de convolution : généralités  


@@ -763,51 +687,35 @@ Les filtres de convolution : généralités
  
   $$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$
 
  
   $$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$
 

-**Usage, selon les valeurs du masque h**
-
- * réduction de bruit,
- * détection de bords,...
-
-.. note::
+**Selon les valeurs du masque h**

 
 

- * selon h --> convo séparable ou non séparable
+ * Réduction de bruit, détection de bords,...
+ * Opération **séparable** en deux convolutions 1D.
+ 

 
 ----
 
 
 ----
 

-LE FILTRAGE DES IMAGES
-======================
-Les filtres de convolution GPU
-------------------------------
-
-Le fabricant Nvidia propose la plus rapide des implémentations connue :
-
-Convolution **non séparable** sur image de 2048x2048, masque h de 5x5, sur **GTX280**.
-
-* Débit global : **945 MP/s**.
-* Débit de calcul : **3,00 GP/s** 
-
-----

 
 LE FILTRAGE DES IMAGES
 ======================
 Les filtres de convolution GPU
 ------------------------------
 
 
 LE FILTRAGE DES IMAGES
 ======================
 Les filtres de convolution GPU
 ------------------------------
 

-Exploitation des recouvrements
+Exploitation des recouvrements :

 
  * un seul accès mémoire par pixel, mémorisation en registre.
 
  * un seul accès mémoire par pixel, mémorisation en registre.

- * mise à jour de tous les calculs concernés
+ * Optimum à 8 pixels/thread :
+ * Exemple médian 5x5, pour un thread :

 
 

-.. image:: img/convoOverlap2.png
-   :width: 400px
+    - 60 pixels dans le halo : 60 lectures.
+    - 200 lectures + préchargement si utilisation mémoire partagée.

 
 

-Application des techniques présentées pour le filtre médian :
+Nvidia propose les implémentations les plus rapides (séparable ou non) :

 
 

-* Optimum à 8 pixels par thread.
-* Débit global : **966 MP/s**.
-* Débit de calcul : **3,47 GP/s** 
+     * Traitement de référence : 2048x2048 pixels, 5x5, 8bits.

 
 

-Sur **C2070**, nos débits sont de **1666 MP/S** et **5280 MP/s**. Les débits maximum atteignent **2140 MP/s** et **8540 MP/s** (4090x4096, masque 3x3) 
+.. image:: img/debit-calcul-convoNS.png
+   :width: 600px

 
 ----
 
 
 ----
 


@@ -816,20 +724,16 @@ LE FILTRAGE DES IMAGES
 Les filtres de convolution GPU 
 ------------------------------
 
 Les filtres de convolution GPU 
 ------------------------------
 

-Convolution **séparable** sur C2070.
-
-Implémentation Nvidia (mémoire partagée)
+**Résultats (suite)**

 
 

- * Débit global max : **1933 MP/s**.
- * Débit de calcul max : **6000 MP/s** 
+.. image:: img/debit-calcul-convoS.png
+   :width: 600px

 
 

-Notre implémentation
+Convolution séparable :

 
 

- * Optimum à 8 pixels par thread.
- * Une convolution 1D en mémoire partagée, l'autre en registres. Copie intermédiaire en mémoire globale (cache 1D rapide).
- * Débit global : **2028 MP/s**.
- * Débit de calcul : **7626 MP/s** 
- * Le gain est obtenu sur la convolution 1D en registres.
+* Une convolution verticale en mémoire partagée, suivie d'une convolution horizontale en registres.
+* Copie intermédiaire en mémoire globale (cache 1D rapide).
+* L'accélération est due à la seule convolution en registres (54%).

 
 ----
 
 
 ----
 


@@ -840,16 +744,9 @@ Les filtres de convolution GPU
 
 **Conclusion**
 
 
 **Conclusion**
 

- * Amélioration limitée des débits globaux en raison de la prépondérance des temps de transfert.

  * Amélioration sensible sur les débits de calcul (de 17 à 33 %).
  * Amélioration sensible sur les débits de calcul (de 17 à 33 %).

- * Le traitement 1D est jusqu'à 66% plus rapide. Applicable à d'autres signaux 1D.
-
-----
-
-LE FILTRAGE DES IMAGES
-======================
-Filtre par recherche des lignes de niveaux 
-------------------------------------------
+ * Le traitement 1D est jusqu'à 54% plus rapide. 
+ * Application à d'autres familles de signaux 1D (audio,...).

 
 ----
 
 
 ----
 


@@ -871,7 +768,7 @@ LE FILTRAGE DES IMAGES
 Filtre par recherche des lignes de niveaux 
 ------------------------------------------
 
 Filtre par recherche des lignes de niveaux 
 ------------------------------------------
 

-**Principe**
+**Principe - modèle**

 
  * Estimation locale, par maximum de vraisemblance, des lignes de niveaux.
  * Réduction de bruit par moyennage le long de la ligne estimée.
 
  * Estimation locale, par maximum de vraisemblance, des lignes de niveaux.
  * Réduction de bruit par moyennage le long de la ligne estimée.


@@ -952,7 +849,7 @@ Filtre par recherche des lignes de niveaux
 
 **Résultats**
 
 
 **Résultats**
 

- Sur l'ensemble d'images de S. Lansel (DenoiseLab, Université Stanford)
+ Sur l'ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD)

 
  * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB**
  * Indice de similarité structurelle : **+30%**
 
  * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB**
  * Indice de similarité structurelle : **+30%**


@@ -976,12 +873,11 @@ Filtre par recherche des lignes de niveaux
    ============================================ === ======================================== 
    .. image:: img/zoom_noisy.png                    .. image:: img/zoom_mean5.png        
     
    ============================================ === ======================================== 
    .. image:: img/zoom_noisy.png                    .. image:: img/zoom_mean5.png        
     

-
-   Bruit gaussien :math:`\(\sigma=25\)`             Moyennage 5x5                                                           
+    Bruit gaussien :math:`\(\sigma=25\)`             Moyennage 5x5                                                           

    
    .. image:: img/zoom_pipdh.png                    .. image:: img/zoom_bm3d.png
    
    
    .. image:: img/zoom_pipdh.png                    .. image:: img/zoom_bm3d.png
    

-   PI-PD                                            BM3D
+    PI-PD                                            BM3D

    ============================================ === ======================================== 
 
 --------
    ============================================ === ======================================== 
 
 --------


@@ -997,30 +893,48 @@ Filtre par recherche des lignes de niveaux
  * Traitement d'images HD à 20 fps.
  * Artefacts en marche d'escalier. Réduits par la méthode de Buades *et al.* (+1 dB, +0,2 ms pour 512x512).
  * Extension aux images couleurs et autres types de bruits (multiplicatif). 
  * Traitement d'images HD à 20 fps.
  * Artefacts en marche d'escalier. Réduits par la méthode de Buades *et al.* (+1 dB, +0,2 ms pour 512x512).
  * Extension aux images couleurs et autres types de bruits (multiplicatif). 

- * Algorithme original sans implémentation de référence séquentielle. Conception GPU dès l'origine. 
+ * Algorithme original sans implémentation séquentielle de référence. 

 
 ----
 
 CONCLUSION GÉNÉRALE - PERSPECTIVES
 ==================================
 
 
 ----
 
 CONCLUSION GÉNÉRALE - PERSPECTIVES
 ==================================
 

-* Trois types de conception mis en  |oe| uvre.  
+* Trois types de conception mis en |~oe| uvre.  

 * Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt.
 * L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.
 * Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt.
 * L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.

-* L'écriture de code performant est fastidieuse et les codes non paramétriques.
-* Création d'un programme générateur.
-
-* Beaucoup de traitements peuvent bénéficier des techniques proposées.
+* Filtres utilisables par tout programmeur grâce à un générateur de code.
+* Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées.

 * Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités.
 * Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités.

-* Extension à d'autres domaines. 

 
 
 .. note::
 
  * certaines ardeurs ont été refroidies 
 
 
 
 .. note::
 
  * certaines ardeurs ont été refroidies 
 

+----
+
+ANNEXE 
+======
+Parallélisation du *Snake* polygonal sur GPU
+--------------------------------------------
+
+**Structure des données** (n |oe| uds pairs)
+
+.. image:: img/16segments.png
+   :width: 800px
+
+.. note:: 
+
+  * règle 1 thread par pixel
+
+

 .. |oe| unicode:: U+0153
    :trim:
 
 .. |oe| unicode:: U+0153
    :trim:
 

+.. |~oe| unicode:: U+0153
+   :rtrim:
+
+

 .. |B| unicode:: U+00DF
    :trim:
 .. |B| unicode:: U+00DF
    :trim: