:title: Algorithmes rapides sur GPU :author: Gilles Perrot # boite arrondie fond gris .. class:: example lkj lkj lkj lj olkj lkj lkjdlkdj ml kdmlk # 2 colonnes .. class:: columns .. list-table:: :widths: 50 80 :header-rows: 0 * - * kjh kj hkjh kqj hdkq jdhq lkj lj lkj lkj lj lqks,jxdxqdiqoioqiij * jkkjskdjf lskfj lskfjlksdjfls - .. image:: css/logo-femto.png :width: 300px ---- :id: titre TRAITEMENT D'IMAGES SUR GPU =========================== Algorithmes parrallèles rapides pour le filtrage et la segmentation des images bruitées sur GPU. ------------------------------------------------------------------------------------------------ Gilles Perrot +++++++++++++ Université de Franche-Comté, Institut FEMTO-ST +++++++++++++++++++++++++++++++++++++++++++++++ Département DISC - équipe AND +++++++++++++++++++++++++++++++++++++ ---- PLAN DE LA PRÉSENTATION ======================= #. Introduction et présentation du cadre des travaux #. Parallélisation GPU d'un algorithme de segmentation de type *snake*. #. Optimisation pour GPU des filtres médian et de convolution. #. Conception et implémentation d'un algorithme parallèle de réduction de bruit par recherche des lignes de niveaux. #. Synthèse et conclusion. ---- INTRODUCTION ============ Contexte Général (Point de vue applicatif) ------------------------------------------ * Un très grand nombre 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é. ---- INTRODUCTION ============ Contexte Général (Point de vue technologique) --------------------------------------------- * 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 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.** .. 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. * La croissance des capacités de calcul des GPUs à été beaucoup plus forte que celle des CPUs. ---- INTRODUCTION ============ Traitements de haut niveau : deux approches ------------------------------------------- #. **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*. * 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. * 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. .. 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 ============ Axes des travaux ---------------- **Filtrage : accélérer les pré-traitements** Réduction de bruit additif gaussien, suivant deux méthodes de conception : * 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. **Segmentation : accélérer le traitement de haut niveau** Algorithme de segmentation d'images bruitées (fortement) par contours actifs, appartenant à la classe communément appelée *snakes*. ---- INTRODUCTION ============ Images traitées --------------- * 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). * Les traitements que nous présentons ici opèrent sur des images en niveau de gris (8 ou 16 bits). .. note:: 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. ---- 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 classe d'algorithmes la plus implémentée est celle des **level-set**. * La classe des **snakes** n'est implémentée qu'au travers la variante GVF (Gradient Vector Flow). * Nos travaux ont porté sur une version orientée région de *snake*, où le contour est décrit par un polygone. ---- SEGMENTATION PAR CONTOUR ACTIF ============================== TRAVAUX de RÉFÉRENCE -------------------- Bien qu'à notre connaissance, aucune publication ne propose d'implémentation de *snake* polygonal ou de *snake* orienté région, on peut ---- Filtrage médian --------------- * 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. * En chaque pixel de l'image, la valeur filtrée est la médiane des valeurs du voisinage (pixel central inclus). * 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. * Des implémentations séquentielles performantes existent. On recense même une variante à temps *constant*. * Des implémentations GPU existent, basées sur la variante BVM (Branchless Vectorized Median) ou sur le calcul d'histogrammes cumulatifs. Exemples / citations / résultats Filtrage de convolution ----------------------- * 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. * 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**. * 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. Exemples / citations / résultats La présentation des travaux de référence sera faite en début de chaque partie : snake, median, convo. ----- LA SEGMENTATION PAR CONTOUR ACTIF ORIENTÉE RÉGION (Snake) ========================================================= Inserer image