1 <!DOCTYPE html><html xmlns="http://www.w3.org/1999/xhtml"><head><title>Algorithmes rapides sur GPU</title><meta name="generator" content="Hovercraft! 1.0 http://regebro.github.com/hovercraft"></meta><meta name="author" content="Gilles Perrot"></meta><link rel="stylesheet" href="css/hovercraft.css" media="all"></link><link rel="stylesheet" href="css/impressConsole.css" media="all"></link><link rel="stylesheet" href="css/highlight.css" media="all"></link><link rel="stylesheet" href="css/zulug5.css" media="all"></link><script type="text/javascript" src="https://c328740.ssl.cf1.rackcdn.com/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></head><body class="impress-not-supported"><div id="impress"><div class="step" step="0" id="titre" data-x="0" data-y="0"><h1 id="traitement-d-images-sur-gpu">TRAITEMENT D'IMAGES SUR GPU</h1><h2 id="algorithmes-rapides-pour-le-filtrage-et-la-segmentation-des-images-bruitees-sur-gpu">Algorithmes rapides pour le filtrage et la segmentation des images bruitées sur GPU.</h2><h3 id="gilles-perrot">Gilles Perrot</h3><h3 id="universite-de-franche-comte-institut-femto-st">Université de Franche-Comté, Institut FEMTO-ST</h3><h3 id="departement-disc-equipe-and">Département DISC - équipe AND</h3><h3 id="direction-r-couturier-s-domas">Direction : R. Couturier & S. Domas</h3></div><div class="step" step="1" data-x="1600" data-y="0"><h1 id="plan-de-la-presentation">PLAN DE LA PRÉSENTATION</h1><ol><li>Introduction - cadre des travaux<ul><li>Les GPUs (Graphical Processing Units)</li><li>Généralités sur le traitement d'image. Nos axes de recherche.</li></ul></li><li>La segmentation des images<ul><li>Généralités. Travaux de référence.</li><li>Parallélisation GPU d'un algorithme de segmentation de type <em>snake</em>.</li></ul></li><li>Le filtrage des images<ul><li>Généralités. Travaux de référence.</li><li>Optimisation pour GPU des filtres médian et de convolution.</li><li>Conception d'un algorithme parallèle de réduction de bruit par recherche des lignes de niveaux.</li></ul></li><li>Synthèse et conclusion.</li></ol></div><div class="step" step="2" data-x="3200" data-y="0"><h1 id="introduction">INTRODUCTION</h1><p>Les GPUs - Les traitements d'image</p></div><div class="step" step="3" data-x="4800" data-y="0"><h1 id="id1">INTRODUCTION</h1><h2 id="les-gpus-ou-processeurs-graphiques">Les GPUs ou <em>Processeurs graphiques</em>.</h2><img src="img/gpucpu1.png" alt="" width="800px" height=""></img><ul><li>Processeurs <em>classiques</em> <strong>CPU</strong> : exécution <strong>séquentielle</strong><ul><li>Quelques unités de calcul ( les cœurs).</li></ul></li><li>Processeurs <em>graphiques</em> <strong>GPU</strong> : exécution <strong>massivement parallèle</strong><ul><li>Des centaines, voire millier, d'unités de calcul, regroupées en quelques SMs (<em>Streaming Multiprocessors</em>).</li></ul></li></ul><div class="notes"><ul><li>La multiplication des cœurs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.</li><li>Seule la mémoire <em>globale</em> est accessible par l'ensemble des fils d'exécution (les <em>threads</em>) et ses performances sont faibles.</li><li>AU sein de la RAM il y a différents canaux vers différents types de mémoires.</li><li>L'accès efficace aux mémoires est contraignant.</li><li>Les échanges de données entre le GPU et son hôte CPU sont pénalisants.</li><li>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.</li><li>La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.</li></ul></div></div><div class="step" step="4" data-x="6400" data-y="0"><h1 id="id2">INTRODUCTION</h1><h2 id="le-traitement-des-images">Le traitement des images</h2><ul><li>L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.</li><li>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.</li><li>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.</li></ul><div class="notes"><ul><li>La croissance des capacités de calcul des GPUs à été beaucoup plus forte que celle des CPUs.</li><li><strong>Les travaux présentés ici sont une contribution à cette recherche de performance.</strong></li></ul></div></div><div class="step" step="5" data-x="8000" data-y="0"><h1 id="id3">INTRODUCTION</h1><h2 id="id4">Le traitement des images</h2><ul><li>Beaucoup d'applications intègrent des traitements d'images numériques.</li><li>Les capteurs numériques et les conditions d'acquisition sont à l'origine de perturbations (bruits).</li><li>Les hautes résolutions sont souvent obtenues à faible flux de photons, dont les variations engendrent du bruit.</li><li>La segmentation représente aussi un enjeu crucial, mais aucun algorithme universel n'a encore été élaboré.</li></ul><div class="notes"><ul><li>les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.</li><li>on recense plus de 4000 algorithmes de segmentation</li><li>La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.</li><li>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.</li></ul></div></div><div class="step" step="6" data-x="9600" data-y="0"><h1 id="id5">INTRODUCTION</h1><h2 id="traitements-d-images-de-haut-niveau">Traitements d'images de haut niveau</h2><ol><li><strong>Pré-traiter</strong> et effectuer les traitements de haut niveau sur des images <em>améliorées</em>.<ul><li>réduction, <em>a priori</em>, du coût des traitements de haut niveau.</li><li>les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.</li></ul></li><li><strong>Ne pas pré-traiter</strong> et effectuer les traitements de haut niveau sur les images bruitées.<ul><li>pas de perte d'information due au pré-traitement.</li><li>les traitements de haut niveau sont, <em>a priori</em>, plus coûteux.</li></ul></li></ol><div class="notes"><ul><li>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.</li></ul></div></div><div class="step" step="7" data-x="11200" data-y="0"><h1 id="id6">INTRODUCTION</h1><h2 id="axes-des-travaux-presentes">Axes des travaux présentés</h2><p><strong>Segmentation : accélérer le traitement de haut niveau</strong></p><blockquote><ul><li>La segmentation consiste à identifier des zones homogènes dans une image.</li><li>Algorithme de segmentation d'images bruitées par contours actifs, de la classe des <em>snakes</em>.</li><li>Conception d'une implémentation avec adaptation de la technique d'optimisation.</li></ul></blockquote><p><strong>Filtrage : accélérer les pré-traitements</strong></p><blockquote><p>Réduction de bruit additif gaussien, suivant deux méthodes de conception :</p><blockquote><ul><li>algorithme original, conçu spécifiquement pour GPU, conjointement à son implémentation.</li><li>algorithmes existants, où l'effort de conception ne peut porter que sur l'implémentation : filtres médian et de convolution.</li></ul></blockquote></blockquote></div><div class="step" step="8" data-x="12800" data-y="0"><h1 id="id7">INTRODUCTION</h1><h2 id="images-traitees">Images traitées</h2><ul><li>Nous nous sommes focalisés sur les <em>images naturelles</em> :</li></ul><blockquote><ul><li>réalisées en lumière naturelle, en intérieur ou en extérieur,</li><li>prises avec un dispositif standard (CMOS, CCD).</li></ul></blockquote><ul><li>Les traitements que nous présentons ici opèrent sur des images en
2 niveau de gris (8 ou 16 bits).</li></ul><div class="notes"><ul><li>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.</li></ul></div></div><div class="step" step="9" data-x="14400" data-y="0"><h1 id="la-segmentation-des-images">LA SEGMENTATION DES IMAGES</h1><p>Segmentation par contour actif</p></div><div class="step" step="10" data-x="16000" data-y="0"><h1 id="segmentation-par-contour-actif">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id8">Introduction</h2><p>La segmentation par contour actif regroupe des méthodes itératives tendant à faire converger, par déformations successives, une courbe paramétrique (contour) selon un critère d'homogénéité pré-établi :</p><blockquote><ul><li>La classe d'algorithmes la plus implémentée sur GPU est celle des <strong>level-set</strong>, essentiellement dans sa variante <em>bande étroite</em>.</li><li>La classe des <strong>snakes</strong> n'est implémentée sur GPU qu'au travers la variante GVF (Gradient Vector Flow).</li></ul></blockquote><img src="img/l7-gvf.png" alt="" width="600px" height=""></img>À gauche : Level-set, évolution du contour, en rouge (d'après J. Sethian). À droite : visualisation du champ de force d'un <em>snake</em> GVF (d'après C. Xu).<div class="notes"><ul><li>Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.</li><li>Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.</li></ul></div></div><div class="step" step="11" data-x="17600" data-y="0"><h1 id="id9">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="travaux-de-reference-level-set">Travaux de référence (level-set)</h2><p>L'implémentation de Roberts <em>et al.</em> du <em>level-set</em> à <em>bande étroite</em> est actuellement la plus performante et parvient à segmenter des images d'IRM</p><blockquote><ul><li>3D, de 256x256x256 pixels, sur GTX280, en <strong>11 000 ms</strong></li></ul></blockquote><img src="img/brain3D.png" alt="" width="800px" height=""></img>À gauche : évolution du contour pour une <em>tranche</em> avec, en bleu, les zones actives. À droite : visualisation en 3D de la segmentation complète.</div><div class="step" step="12" data-x="19200" data-y="0"><h1 id="id10">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="travaux-de-reference-snake">Travaux de référence (snake)</h2><ul><li>La référence est l'implémentation <em>snake GVF</em> de Smistad <em>et al.</em> qui parvient à segmenter des images d'IRM</li></ul><blockquote><ul><li>2D, de 512x512 pixels, sur C2070, en <strong>41 ms</strong>.</li><li>3D, de 256x256x256 pixels, sur C2070, en <strong>7151 ms</strong></li></ul></blockquote><img src="img/brain3D-gvf.png" alt="" width="600px" height=""></img>À gauche : une image 2D d'IRM. À droite : visualisation en 3D de la segmentation complète.<div class="notes"><ul><li>À notre connaissance, aucune publication ne décrit d'implémentation de <em>snake</em> polygonal ou de <em>snake</em> orienté région.</li></ul></div></div><div class="step" step="13" data-x="20800" data-y="0"><h1 id="id11">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="snake-polygonal-oriente-region-principe"><em>Snake</em> polygonal orienté région (principe)</h2><table cellpadding="0" cellspacing="0" class="columns"><tbody><tr><td><img src="img/snake-modele.png" alt="" width="350px" height=""></img></td><td><ul><li>L'objectif est de déterminer le contour le plus <em>vraisemblable</em> (nombre et positions des nœuds).</li><li>Le critère de vraisemblance généralisée est, dans le cas gaussien :$$GL = \frac{1}{2}\left[ n_B.log\left(\sigma_B^2\right) + n_T.log\left(\sigma_T^2\right)\right]$$</li></ul></td></tr></tbody></table><ul><li>Les deux régions, intérieure et extérieure (T et B), sont prises en compte dans l'évaluation du contour.</li><li>Les variances \(\sigma^2\) doivent être calculées pour chaque état du contour, ce qui est <strong>très coûteux</strong>.</li></ul><div class="notes"><ul><li>Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple.</li></ul></div></div><div class="step" step="14" data-x="22400" data-y="0"><h1 id="id12">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id13"><em>Snake</em> polygonal orienté région (principe)</h2><img src="img/snake-modele.png" alt="" width="350px" height=""></img><ul><li>Chesnaud <em>et al.</em> ont montré comment remplacer la sommation 3D par une <strong>sommation 2D</strong> le long du contour.</li><li>Implique le <strong>pré-calcul</strong> des trois images cumulées$$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$$</li></ul><div class="notes"><ul><li>Les valeurs des éléments de ces images cumulées permettent de calculer la <strong>contribution</strong> de chaque pixel du contour, puis de chaque segment, aux calculs des variances.</li></ul></div></div><div class="step" step="15" data-x="24000" data-y="0"><h1 id="id14">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="snake-polygonal-oriente-region-algo-cpu"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/cochons-it0-it1.png" alt="" width="" height="300px"></img><p><strong>Itération 1</strong></p><blockquote><ol><li>Le contour initial est rectangulaire ( 4 nœuds )</li><li>On déplace successivement les 4 nœuds jusqu'à ce que plus aucun nouveau déplacement ne provoque l'amélioration du critère.</li></ol></blockquote></div><div class="step" step="16" data-x="25600" data-y="0"><h1 id="id15">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id16"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/cochons-it21-it22.png" alt="" width="" height="300px"></img><p><strong>Itération 2</strong></p><blockquote><ol><li>Ajout de nœuds au milieu des segments suffisamment grands.</li><li>On recommence à évaluer les déplacements successifs des nœuds.</li></ol></blockquote></div><div class="step" step="17" data-x="27200" data-y="0"><h1 id="id17">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id18"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/cochons-it4-it5.png" alt="" width="" height="300px"></img><p><strong>Itérations 4 et 5</strong></p></div><div class="step" step="18" data-x="28800" data-y="0"><h1 id="id19">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id20"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/im014.png" alt="" width="" height="400px"></img>Image de 512x512 : contour final de 256 nœuds en 14ms.<ul><li>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œuds)</li></ul></div><div class="step" step="19" data-x="30400" data-y="0"><h1 id="id21">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id22"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/snakegpu1.png" alt="" width="" height="400px"></img>Image de 4000x4000 : contour final de 447 nœuds en 700ms.</div><div class="step" step="20" data-x="32000" data-y="0"><h1 id="id23">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="parallelisation-du-snake-polygonal-sur-gpu">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Identification des fonctions coûteuses</p><img src="img/algosnake1.png" alt="" width="" height="500px"></img></div><div class="step" step="21" data-x="33600" data-y="0"><h1 id="id24">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id25">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Détail de la fonction de calcul du critère GL</p><img src="img/algosnake2b.png" alt="" width="" height="500px"></img></div><div class="step" step="22" data-x="35200" data-y="0"><h1 id="id26">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id27">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><img src="img/snake-pairimpair.png" alt="" width="800px" height=""></img><div class="notes"><ul><li>Pour un nœud et un pas de déplacement donnés, on évalue <strong>en parallèle</strong> 8 positions voisines, soit 16 segments distincts.</li><li>Pour éviter les oscillations et <em>coller</em> à l'algorithme séquentiel, on distingue les nœuds d'indices pairs et impairs.</li><li>On évalue <strong>en parallèle</strong> l'ensemble des déplacements éventuels de tous les nœuds de même parité.</li></ul></div></div><div class="step" step="23" data-x="36800" data-y="0"><h1 id="id28">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id29">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Structure des données</strong> (nœuds pairs)</p><img src="img/16segments.png" alt="" width="800px" height=""></img><div class="notes"><ul><li>règle 1 thread par pixel</li></ul></div></div><div class="step" step="24" data-x="38400" data-y="0"><h1 id="id30">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id31">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Obtention du critère</strong></p><ul><li>Parallélisation : 1 thread par pixel.</li><li>Une seule taille de segment : la taille du plus long.</li><li>Bourrage avec des threads inactifs pour les segments plus courts.</li><li>Calcul réalisé en 3 étapes par 3 fonctions parallèles GPU (<em>kernels</em>)</li></ul><blockquote><ol><li>Calculs réalisables <strong>au niveau bloc</strong> : coordonnées des pixels, lecture des paramètres dans les images cumulées, sommes partielles des contributions des segments.</li><li><strong>Réductions</strong> : calcul final des contributions des segments.</li><li>Calcul des valeurs du critère pour chaque contour évalué. Sélection du meilleur contour.</li></ol></blockquote><div class="notes"><ul><li>les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1</li></ul></div></div><div class="step" step="25" data-x="40000" data-y="0"><h1 id="id32">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id33">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Propriétés de l'implémentation</strong></p><blockquote><ul><li>Conservation des données en mémoire GPU.</li><li>Les images cumulées sont calculées en parallèle.</li><li>Abandon de l'algorithme de Bresenham pour la discretisation des segments.</li><li>Trop peu de calculs à effectuer. Peu de threads dans la grille.</li><li>Pas de coalescence possible dans les accès à la mémoire globale.</li><li>Emploi de la mémoire partagée.</li></ul></blockquote><div class="notes"><ul><li>Un seul entier est échangé entre le CPU et le GPU à chaque itération.</li><li>image cumulées par une adaptation de la méthode des sommes de préfixes.</li><li>Abandon Bresenham Possible car parcours unidirectionnel du contour.</li><li>Trop peu de calculs ne permet pas de masquer les latences.</li><li>Pas de coalescence possible dans les accès à la mémoire globale car la géométrie des segments varie.</li><li>mémoire partagée à cause des réductions.</li></ul></div></div><div class="step" step="26" data-x="41600" data-y="0"><h1 id="id34">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id35">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Performances de l'implémentation</strong></p><img src="img/perfs-snake.png" alt="" width="600px" height=""></img><img src="img/perfs-snake-img.png" alt="" width="600px" height=""></img></div><div class="step" step="27" data-x="43200" data-y="0"><h1 id="id36">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id37">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Conclusion</strong></p><ul><li>Première et seule implémentation à ce jour.</li><li>Performances intéressantes pour les grandes images. 1OO MP en moins de 0,6 seconde.</li><li>Temps de calcul très dépendant du contenu de l'image.</li><li>Le GPU n'est pas employé de manière optimale : réductions, threads inactifs, non coalescence.</li><li>Le GPU apporte un gain important sur les premières itérations, quand les segments sont grands.</li><li>Initialisation optionnelle par maximum de vraisemblance. Accélération jusqu'à x15 avec de petites cibles.</li></ul></div><div class="step" step="28" data-x="44800" data-y="0"><h1 id="le-filtrage-des-images">LE FILTRAGE DES IMAGES</h1><p>Filtre médian - Filtres de convolution - Filtre par lignes de niveaux</p></div><div class="step" step="29" data-x="46400" data-y="0"><h1 id="id38">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median">Filtre médian</h2></div><div class="step" step="30" data-x="48000" data-y="0"><h1 id="id39">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-principe">Filtre médian : principe</h2><img src="img/median-principe.png" alt="" width="600px" height=""></img><p>La valeur de sortie d'un pixel est la <strong>médiane</strong> des valeurs de son voisinage.</p><ul><li>Bonne réduction de bruits gaussien et <em>poivre & sel</em></li><li>Valeurs de sortie appartenant au voisinage.</li><li>Opération de sélection coûteuse (tri).</li><li>Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).</li><li>Quelques applications avec de grandes fenêtres (au delà de 21x21).</li></ul></div><div class="step" step="31" data-x="49600" data-y="0"><h1 id="id40">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-usage">Filtre médian : usage</h2><table cellpadding="0" cellspacing="0"><thead><tr><th><img src="img/airplane_sap25.png" alt="" width="" height=""></img></th><th><img src="img/airplane_sap25_med5.png" alt="" width="" height=""></img></th><th><img src="img/airplane_sap25_med3_it2.png" alt="" width="" height=""></img></th></tr></thead><tbody><tr><td><p>Bruit <em>poivre & sel</em> 25%</p></td><td><p>Médian 5x5</p></td><td><p>Médian 3x3 - 2 passes</p></td></tr></tbody></table></div><div class="step" step="32" data-x="51200" data-y="0"><h1 id="id41">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-gpu-travaux-de-reference">Filtre médian GPU : Travaux de référence</h2><ul><li>Sanchez <em>et al.</em> ont proposé le <strong>PCMF</strong> 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. <strong>80 MP/s</strong>) :</li></ul><blockquote><ul><li><strong>ArrayFire</strong>, bibliothèque commerciale, débit max. <strong>185 MP/s</strong></li><li><strong>BVM</strong> parallélisé par Kachelrieß, débit max. <strong>110 MP/s</strong></li></ul></blockquote><img src="img/compar-median2.png" alt="" width="500px" height=""></img><div class="notes"><ul><li>PCMF : Parallel (Complementary Cumulative Derivative Function) Median Filter (histogrammes cumulatifs)</li><li>CTMF : CPU à temps constant</li></ul></div></div><div class="step" step="33" data-x="52800" data-y="0"><h1 id="id42">LE FILTRAGE DES IMAGES</h1><h2 id="id43">Filtre médian GPU : Travaux de référence</h2><p>Emploi de la <strong>mémoire partagée</strong> pour pré-charger les valeurs utiles à chaque bloc de threads.</p><img src="img/shmemhalo.png" alt="" width="800px" height=""></img></div><div class="step" step="34" data-x="54400" data-y="0"><h1 id="id44">LE FILTRAGE DES IMAGES</h1><h2 id="optimisation-du-filtre-median-gpu">Optimisation du filtre médian GPU</h2><p>Transferts des données optimisés</p><img src="img/CPU-GPU-memcpy.png" alt="" width="750px" height=""></img><img src="img/transferts-mem.png" alt="" width="650px" height=""></img><div class="notes"><p>On gagne de 13 à 43 % sur les temps de transfert.</p></div></div><div class="step" step="35" data-x="56000" data-y="0"><h1 id="id45">LE FILTRAGE DES IMAGES</h1><h2 id="id46">Optimisation du filtre médian GPU</h2><img src="img/CPU-GPU-memcpy-dummykernel.png" alt="" width="750px" height=""></img><p>Débits maximums effectifs, en MP/s, pour des images en 8 et 16 bits, incluant les transferts optimisés (C2070).</p><blockquote><img src="img/debit-max-2070.png" alt="" width="300px" height=""></img></blockquote><p><strong>Rappel :</strong> PCMF : 80 MP/s - BVM : 110 MP/s - ArrayFire : 185 MP/s</p><div class="notes"><p>ça laisse environ 80ms pour faire un tri de 9 valeurs sur une image de 4096x4096</p></div></div><div class="step" step="36" data-x="57600" data-y="0"><h1 id="id47">LE FILTRAGE DES IMAGES</h1><h2 id="id48">Optimisation du filtre médian GPU</h2><p><strong>Sélection de la médiane</strong></p><blockquote><ul><li>Emploi exclusif des <strong>registres</strong> pour charger les valeurs utiles.</li><li>Limitations à 63 registres par thread et 32 K par bloc de threads.</li><li>Envisageable pour les médians de petite taille (jusqu'à 7x7 avec 1 thread/pixel).</li><li>Exploitation des recouvrements entre fenêtres de pixels voisins.</li></ul></blockquote></div><div class="step" step="37" data-x="59200" data-y="0"><h1 id="id49">LE FILTRAGE DES IMAGES</h1><h2 id="id50">Optimisation du filtre médian GPU</h2><p><strong>Sélection de la médiane</strong> (par oubli)</p><table cellpadding="0" cellspacing="0" class="columns"><tbody><tr><td><p>Bonnes performances envisagées :</p><blockquote><ul><li>Économie de registres.</li><li>Évite le tri complet.</li></ul></blockquote></td><td><img src="img/forgetful_selection.png" alt="" width="" height="500px"></img></td></tr></tbody></table></div><div class="step" step="38" data-x="60800" data-y="0"><h1 id="id51">LE FILTRAGE DES IMAGES</h1><h2 id="id52">Optimisation du filtre médian GPU</h2><p><strong>Exploitation des recouvrements</strong></p><img src="img/recouvrement5.png" alt="" width="800px" height=""></img><p><strong>Intérêt :</strong> Économie de registres - chaque thread traite 2 pixels.</p><div class="notes"><ul><li>chaque thread utilise plus de registres</li><li>mais sur un bloc, en adaptant la taille du bloc, on économise k+1 registres par paire de pixels.</li></ul></div></div><div class="step" step="39" data-x="62400" data-y="0"><h1 id="id53">LE FILTRAGE DES IMAGES</h1><h2 id="id54">Optimisation du filtre médian GPU</h2><p><strong>Masquage des latences</strong></p><ul><li>Accès à la mémoire globale : 2 pixels par thread.</li><li>Instruction Level Parallelism (ILP) : Ordre des instructions minimisant l'interdépendance.<img src="img/bitonic.png" alt="" width="" height="300px"></img>Identification des extrema dans le vecteur initial d'un médian 5x5</li></ul><div class="notes"><ul><li>au delà de 2 pixels par thread, le gain sur les latences est compensé par la perte sur le calcul / niveau de parallèlisme.</li><li>ILP maximisée en appliquant une méthode simple; utilisée par ex. dans la technique des réseaux de tri bitoniques.</li></ul></div></div><div class="step" step="40" data-x="64000" data-y="0"><h1 id="id55">LE FILTRAGE DES IMAGES</h1><h2 id="performances-du-filtre-median-gpu-propose-prmf">Performances du filtre médian GPU proposé (PRMF)</h2><img src="img/perf-median.png" alt="" width="650px" height=""></img></div><div class="step" step="41" data-x="65600" data-y="0"><h1 id="id56">LE FILTRAGE DES IMAGES</h1><h2 id="id57">Performances du filtre médian GPU proposé (PRMF)</h2><p>Image 512x512</p><blockquote><img src="img/comp512.png" alt="" width="" height="200px"></img></blockquote><p>Image 4096x4096</p><blockquote><img src="img/comp4k.png" alt="" width="" height="200px"></img></blockquote></div><div class="step" step="42" data-x="67200" data-y="0"><h1 id="id58">LE FILTRAGE DES IMAGES</h1><h2 id="le-filtre-median-gpu">Le filtre médian GPU</h2><p><strong>Conclusion</strong></p><blockquote><ul><li>Pas d'utilisation de la mémoire partagée.</li><li>Débit global amélioré de x7 à x10, proche du maximum.</li><li>Débit de calcul atteignant <strong>5,3 GP/s</strong>.</li><li>Médian jusqu'au 9x9 sur C2070, 21x21 sur K40.</li><li>Création d'une application web générant les codes sources.</li><li>Utilisé pour le pré-traitement d'images de cristallographie au synchrotron <strong>SPring-8</strong> (Japon).</li></ul></blockquote><img src="img/SPring8.png" alt="" width="" height="200px"></img></div><div class="step" step="43" data-x="68800" data-y="0"><h1 id="id59">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution">Les filtres de convolution</h2></div><div class="step" step="44" data-x="70400" data-y="0"><h1 id="id60">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution-generalites">Les filtres de convolution : généralités</h2><p><strong>Principe</strong></p><blockquote>$$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$</blockquote><p><strong>Usage, selon les valeurs du masque h</strong></p><blockquote><ul><li>réduction de bruit,</li><li>détection de bords,...</li></ul></blockquote><div class="notes"><ul><li>selon h --> convo séparable ou non séparable</li></ul></div></div><div class="step" step="45" data-x="72000" data-y="0"><h1 id="id61">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution-gpu">Les filtres de convolution GPU</h2><p>Le fabricant Nvidia propose la plus rapide des implémentations connue :</p><p>Convolution <strong>non séparable</strong> sur image de 2048x2048, masque h de 5x5, sur <strong>GTX280</strong>.</p><ul><li>Débit global : <strong>945 MP/s</strong>.</li><li>Débit de calcul : <strong>3,00 GP/s</strong></li></ul></div><div class="step" step="46" data-x="73600" data-y="0"><h1 id="id62">LE FILTRAGE DES IMAGES</h1><h2 id="id63">Les filtres de convolution GPU</h2><p>Exploitation des recouvrements</p><blockquote><ul><li>un seul accès mémoire par pixel, mémorisation en registre.</li><li>mise à jour de tous les calculs concernés</li></ul></blockquote><img src="img/convoOverlap2.png" alt="" width="400px" height=""></img><p>Application des techniques présentées pour le filtre médian :</p><ul><li>Optimum à 8 pixels par thread.</li><li>Débit global : <strong>966 MP/s</strong>.</li><li>Débit de calcul : <strong>3,47 GP/s</strong></li></ul><p>Sur <strong>C2070</strong>, nos débits sont de <strong>1666 MP/S</strong> et <strong>5280 MP/s</strong>. Les débits maximum atteignent <strong>2140 MP/s</strong> et <strong>8540 MP/s</strong> (4090x4096, masque 3x3)</p></div><div class="step" step="47" data-x="75200" data-y="0"><h1 id="id64">LE FILTRAGE DES IMAGES</h1><h2 id="id65">Les filtres de convolution GPU</h2><p>Convolution <strong>séparable</strong> sur C2070.</p><p>Implémentation Nvidia (mémoire partagée)</p><blockquote><ul><li>Débit global max : <strong>1933 MP/s</strong>.</li><li>Débit de calcul max : <strong>6000 MP/s</strong></li></ul></blockquote><p>Notre implémentation</p><blockquote><ul><li>Optimum à 8 pixels par thread.</li><li>Une convolution 1D en mémoire partagée, l'autre en registres. Copie intermédiaire en mémoire globale (cache 1D rapide).</li><li>Débit global : <strong>2028 MP/s</strong>.</li><li>Débit de calcul : <strong>7626 MP/s</strong></li><li>Le gain est obtenu sur la convolution 1D en registres.</li></ul></blockquote></div><div class="step" step="48" data-x="76800" data-y="0"><h1 id="id66">LE FILTRAGE DES IMAGES</h1><h2 id="id67">Les filtres de convolution GPU</h2><p><strong>Conclusion</strong></p><blockquote><ul><li>Amélioration limitée des débits globaux en raison de la prépondérance des temps de transfert.</li><li>Amélioration sensible sur les débits de calcul (de 17 à 33 %).</li><li>Le traitement 1D est jusqu'à 66% plus rapide. Applicable à d'autres signaux 1D.</li></ul></blockquote></div><div class="step" step="49" data-x="78400" data-y="0"><h1 id="id68">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-par-recherche-des-lignes-de-niveaux">Filtre par recherche des lignes de niveaux</h2></div><div class="step" step="50" data-x="80000" data-y="0"><h1 id="id69">LE FILTRAGE DES IMAGES</h1><h2 id="id70">Filtre par recherche des lignes de niveaux</h2><p><strong>Motivations :</strong></p><blockquote><ul><li>Les algorithmes qui débruitent le mieux sont lents (BM3D).</li><li>Les images naturelles sont décomposables en un ensemble de lignes de niveaux ( iso-niveau de gris ).</li><li>Concevoir un algorithme GPU original et son implémentation.</li></ul></blockquote></div><div class="step" step="51" data-x="81600" data-y="0"><h1 id="id71">LE FILTRAGE DES IMAGES</h1><h2 id="id72">Filtre par recherche des lignes de niveaux</h2><p><strong>Principe - modèle</strong></p><blockquote><ul><li>Estimation locale, par maximum de vraisemblance, des lignes de niveaux.</li><li>Réduction de bruit par moyennage le long de la ligne estimée.</li><li>Les lignes de niveaux estimées sont modélisées par des lignes brisées nommées <strong>isolines</strong>.</li><li>Les segments des lignes brisées sont choisis parmi des motifs pré-établis (32 motifs).<img src="img/P5Q1.png" alt="" width="500px" height=""></img></li></ul></blockquote></div><div class="step" step="52" data-x="83200" data-y="0"><h1 id="id73">LE FILTRAGE DES IMAGES</h1><h2 id="id74">Filtre par recherche des lignes de niveaux</h2><p><strong>Principe (étape 1)</strong></p><blockquote><ul><li>En chaque pixel, recherche du motif maximisant la log-vraisemblance ( \(n=6, \sigma^2 =\) variance )</li></ul>$$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$<ul><li>Mémorisation des paramètres des motifs sélectionnés dans deux matrices \(I_{\Theta}\) et \(I_{\Sigma}\).</li></ul><img src="img/lniv-mv.png" alt="" width="500px" height=""></img></blockquote></div><div class="step" step="53" data-x="84800" data-y="0"><h1 id="id75">LE FILTRAGE DES IMAGES</h1><h2 id="id76">Filtre par recherche des lignes de niveaux</h2><p><strong>Principe (étape 2)</strong></p><blockquote><ul><li>Allongement itératif des segments sous condition GLRT.</li></ul>$$(n_{s_1s_2}+n_{s_3})\left[log\left(\widehat{\sigma_{s_1s_2}}^2\right) - log\left(\widehat{\sigma_{s_3}}^2\right) \right]$$<img src="img/pipd-detail.png" alt="" width="900px" height=""></img></blockquote></div><div class="step" step="54" data-x="86400" data-y="0"><h1 id="id77">LE FILTRAGE DES IMAGES</h1><h2 id="id78">Filtre par recherche des lignes de niveaux</h2><p><strong>Principe (étape 3)</strong></p><blockquote><p>Compensation de la non robustesse de sélection des motifs dans les zones homogènes.</p><blockquote><ul><li>identification des zones homogènes avec un détecteur de bords.</li><li>Application d'un filtre moyenneur dans ces zones.</li></ul></blockquote><img src="img/detecteur.png" alt="" width="400px" height=""></img></blockquote><div class="notes"><ul><li>Sous-ensembles de pixels n'ayant pas d'intersection --> MV</li><li>Utilisation des motifs des segments pour gain de temps.</li></ul></div></div><div class="step" step="55" data-x="88000" data-y="0"><h1 id="id79">LE FILTRAGE DES IMAGES</h1><h2 id="id80">Filtre par recherche des lignes de niveaux</h2><p><strong>Résultats</strong></p><blockquote><p>Sur l'ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD)</p><ul><li>Amélioration moyenne du rapport Signal sur bruit: <strong>+7,1 dB</strong></li><li>Indice de similarité structurelle : <strong>+30%</strong></li><li>Temps de calcul : <strong>7 ms</strong></li></ul><p>Comparaison avec BM3D</p><ul><li>Amélioration moyenne du rapport Signal sur bruit: <strong>+9,5 dB</strong></li><li>Indice de similarité structurelle : <strong>+36%</strong></li><li>Temps de calcul : <strong>4300 ms</strong></li></ul></blockquote></div><div class="step" step="56" data-x="89600" data-y="0"><h1 id="id81">LE FILTRAGE DES IMAGES</h1><h2 id="id82">Filtre par recherche des lignes de niveaux</h2><table cellpadding="0" cellspacing="0"><tbody><tr><td><img src="img/zoom_noisy.png" alt="" width="" height=""></img></td><td></td><td><img src="img/zoom_mean5.png" alt="" width="" height=""></img></td></tr><tr><td><p>Bruit gaussien \(\sigma=25\)</p></td><td></td><td><p>Moyennage 5x5</p></td></tr><tr><td><img src="img/zoom_pipdh.png" alt="" width="" height=""></img></td><td></td><td><img src="img/zoom_bm3d.png" alt="" width="" height=""></img></td></tr><tr><td><p>PI-PD</p></td><td></td><td><p>BM3D</p></td></tr></tbody></table></div><div class="step" step="57" data-x="91200" data-y="0"><h1 id="id83">LE FILTRAGE DES IMAGES</h1><h2 id="id84">Filtre par recherche des lignes de niveaux</h2><p><strong>Synthèse - conclusion</strong></p><blockquote><ul><li>Rapport qualité/temps élevé.</li><li>Traitement d'images HD à 20 fps.</li><li>Artefacts en marche d'escalier. Réduits par la méthode de Buades <em>et al.</em> (+1 dB, +0,2 ms pour 512x512).</li><li>Extension aux images couleurs et autres types de bruits (multiplicatif).</li><li>Algorithme original sans implémentation séquentielle de référence.</li></ul></blockquote></div><div class="step" step="58" data-x="92800" data-y="0"><h1 id="conclusion-generale-perspectives">CONCLUSION GÉNÉRALE - PERSPECTIVES</h1><ul><li>Trois types de conception mis en œuvre.</li><li>Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt.</li><li>L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.</li><li>Filtres utilisables par tout programmeur grâce à un générateur de code.</li><li>Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées.</li><li>Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités.</li></ul><div class="notes"><ul><li>certaines ardeurs ont été refroidies</li></ul></div></div></div><div id="hovercraft-help"><table><tr><th>Space</th><td>Forward</td></tr><tr><th>Left, Down, Page Down</th><td>Next slide</td></tr><tr><th>Right, Up, Page Up</th><td>Previous slide</td></tr><tr><th>P</th><td>Open presenter console</td></tr><tr><th>H</th><td>Toggle this help</td></tr></table></div><script type="text/javascript" src="js/impress.js"></script><script type="text/javascript" src="js/impressConsole.js"></script><script type="text/javascript" src="js/hovercraft.js"></script></body></html>
