PRESENTATION/diapos.rst~

   1 :title: Algorithmes rapides sur GPU
   2 :author: Gilles Perrot
   3
   4
   5 # boite arrondie fond gris
   6
   7 .. class:: example
   8
   9  lkj lkj lkj lj
  10  olkj lkj
  11  lkjdlkdj
  12  ml kdmlk
  13
  14 # 2 colonnes
  15
  16 .. class:: columns
  17
  18  .. list-table::
  19     :widths: 50 80
  20     :header-rows: 0
  21
  22     * - * kjh kj hkjh kqj hdkq jdhq lkj lj lkj lkj lj lqks,jxdxqdiqoioqiij
  23         *  jkkjskdjf lskfj lskfjlksdjfls
  24       - .. image:: css/logo-femto.png
  25                 :width: 300px
  26
  27
  28 ----
  29
  30 :id: titre
  31
  32 TRAITEMENT D'IMAGES SUR GPU
  33 ===========================
  34
  35 Algorithmes parrallèles rapides pour le filtrage et la segmentation des images bruitées sur GPU.
  36 ------------------------------------------------------------------------------------------------
  37
  38 Gilles Perrot
  39 +++++++++++++
  40
  41 Université de Franche-Comté, Institut FEMTO-ST
  42 +++++++++++++++++++++++++++++++++++++++++++++++
  43 Département DISC - équipe AND
  44 +++++++++++++++++++++++++++++++++++++
  45
  46 ----
  47
  48 PLAN DE LA PRÉSENTATION
  49 =======================
  50
  51 #. Introduction et présentation du cadre des travaux
  52 #. Parallélisation GPU d'un algorithme de segmentation de type *snake*.
  53 #. Optimisation pour GPU des filtres médian et de convolution.
  54 #. Conception et implémentation d'un algorithme parallèle de réduction de bruit par recherche des lignes de niveaux.
  55 #. Synthèse et conclusion.
  56
  57 ----
  58
  59 INTRODUCTION
  60 ============
  61 Contexte Général (Point de vue applicatif)
  62 ------------------------------------------
  63
  64 * Un très grand nombre d'applications sont basées sur l'analyse ou la visualisation d'images numériques.
  65 * 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.
  66 * 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.
  67 * La segmentation représente aussi un enjeu crucial, mais aucun algorithme universel n'a encore été élaboré.
  68
  69 ----
  70
  71 INTRODUCTION
  72 ============
  73 Contexte Général (Point de vue technologique)
  74 ---------------------------------------------
  75
  76 * L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
  77 * Les traitements envisagés sur les images sont de plus en plus évolués et requièrent souvent un temps de calcul accru.
  78 * 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.
  79
  80 **Nos travaux sont une contribution à cette recherche de performance.**
  81
  82 .. note::
  83
  84  * on recense plus de 4000 algorithmes de segmentation
  85  * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
  86  * 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.
  87  * La croissance des capacités de calcul des GPUs à été beaucoup plus forte que celle des CPUs.
  88
  89
  90
  91 ----
  92
  93 INTRODUCTION
  94 ============
  95 Traitements de haut niveau : deux approches
  96 -------------------------------------------
  97
  98 #. **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*.
  99
 100    * permet, *a priori*, de réduire le coût des traitements de haut niveau.
 101    * les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.
 102
 103 #. **Ne pas pré-traiter** et effectuer les traitements de haut niveau sur les images bruitées.
 104
 105    * permet de ne pas subir la perte d'information occasionnée par le pré-traitement.
 106    * les traitements de haut niveau sont, *a priori*, plus coûteux.
 107
 108
 109 .. note::
 110
 111  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.
 112
 113 ----
 114
 115 INTRODUCTION
 116 ============
 117
 118 Axes des travaux
 119 ----------------
 120
 121 **Filtrage : accélérer les pré-traitements**
 122
 123  Réduction de bruit additif gaussien, suivant deux méthodes de conception  :
 124
 125      * algorithme original, conçu spécifiquement pour GPU, conjointement à son implémentation.
 126      * algorithmes existants, où l'effort de conception ne peut porter que sur l'implémentation : filtres médian et de convolution.
 127
 128 **Segmentation : accélérer le traitement de haut niveau**
 129
 130  Algorithme de segmentation d'images bruitées (fortement) par contours actifs, appartenant à la classe communément appelée  *snakes*.
 131
 132 ----
 133
 134 INTRODUCTION
 135 ============
 136
 137 Images traitées
 138 ---------------
 139
 140 * Nous nous sommes focalisés sur les *images naturelles* :
 141
 142  - réalisées en lumière naturelle, en intérieur aussi bien qu'en extérieur,
 143  - prises avec un dispositif standard (CMOS, CCD).
 144
 145 * Les traitements que nous présentons ici opèrent sur des images en
 146   niveau de gris (8 ou 16 bits).
 147
 148 .. note::
 149
 150  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.
 151
 152 ----
 153
 154 SEGMENTATION PAR CONTOUR ACTIF
 155 ==============================
 156 Introduction
 157 ------------
 158
 159 * Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
 160 * Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
 161 * La classe d'algorithmes la plus implémentée est celle des **level-set**.
 162 * La classe des **snakes** n'est implémentée qu'au travers la variante GVF (Gradient Vector Flow).
 163 * Nos travaux ont porté sur une version orientée région de *snake*, où le contour est décrit par un polygone.
 164
 165 ----
 166
 167 SEGMENTATION PAR CONTOUR ACTIF
 168 ==============================
 169 TRAVAUX de RÉFÉRENCE
 170 --------------------
 171
 172 Bien qu'à notre connaissance, aucune publication ne propose d'implémentation de *snake* polygonal ou de *snake* orienté région, on peut
 173
 174 ----
 175
 176 Filtrage médian
 177 ---------------
 178
 179 * Le filtre médian est très utilisé dans beaucoup d'applications. Il permet de débruiter fortement le bruit poivre et sel, mais est aussi employé pour réduire le bruit gaussien.
 180 * En chaque pixel de l'image, la valeur filtrée est la médiane des valeurs du voisinage (pixel central inclus).
 181 * Le procédé est simple, mais l'opération de tri qu'il implique est assez coûteuse et son temps de calcul dépend des valeurs du voisinage.
 182 * Des implémentations séquentielles performantes existent. On recense même une variante à temps *constant*.
 183 * Des implémentations GPU existent, basées sur la variante BVM (Branchless Vectorized Median) ou sur le calcul d'histogrammes cumulatifs.
 184
 185 Exemples / citations / résultats
 186
 187 Filtrage de convolution
 188 -----------------------
 189
 190 * Classe de filtres permettant de réaliser une grande variété de traitements, depuis la réduction de bruit jusqu'à la détection de bords.
 191 * En chaque pixel de l'image, la valeur filtrée est une moyenne pondérée des valeurs du voisinage (pixel central inclus). Les coefficients de pondération, et donc les dimensions du voisinage sont donnés par le **masque de convolution**.
 192 * On ne recense comme implémentation performante, que celle proposée par le constructeur Nvidia et issue d'une étude extensive de 16 variantes d'optimisation.
 193
 194 Exemples / citations / résultats
 195
 196 La présentation des travaux de référence sera faite en début de chaque partie : snake, median, convo.
 197
 198 -----
 199
 200 LA SEGMENTATION PAR CONTOUR ACTIF ORIENTÉE RÉGION (Snake)
 201 =========================================================
 202
 203 Inserer image
 204
 205