-<!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="http
s://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="avril-2014">17 avril 2014</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="filtrage">FILTRAGE</h1><p>Réduire le bruit.</p><img src="img/ex-filtrage.png" alt="" width="800px" height=""></img><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>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></ul></div></div><div class="step" step="2" data-x="3200" data-y="0"><h1 id="segmentation">SEGMENTATION</h1><p>Distinguer les zones homogènes d'une image.</p><img src="img/seg1.png" alt="" width="700px" height=""></img><div class="notes"><ul><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="3" data-x="4800" data-y="0"><h1 id="id1">SEGMENTATION</h1><p>Deux approches</p><img src="img/approches.png" alt="" width="800px" height=""></img><div class="notes"><ul><li><strong>Pré-traiter</strong> et effectuer les traitements de haut niveau sur des images <em>améliorées</em>.</li></ul><blockquote><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></blockquote><ul><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></ul></li></ul></div></div><div class="step" step="4" data-x="6400" data-y="0"><h1 id="plan-de-la-presentation">PLAN DE LA PRÉSENTATION</h1><ol><li>Introduction<ul><li>Les GPUs ou <em>Graphical Processing Units</em>.</li><li>Le filtrage et la segmentation d'images.</li></ul></li><li>La segmentation des images<ul><li>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>Travaux de référence.</li><li>Optimisation GPU des filtres médian et de convolution.</li><li>Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.</li></ul></li><li>Conclusion et perspectives</li></ol></div><div class="step" step="5" data-x="8000" data-y="0"><h1 id="introduction">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 milliers, d'unités de calcul, regroupées en 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><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></div><div class="step" step="6" data-x="9600" data-y="0"><h1 id="id2">INTRODUCTION</h1><h2 id="le-traitement-des-images">Le traitement des images</h2><p><strong>Le filtrage (du bruit)</strong></p><blockquote><ul><li>Les capteurs et les conditions d'acquisition induisent du bruit.</li><li><em>Résolution élevée</em> n'implique pas <em>bruit réduit</em>.</li></ul></blockquote><p><strong>La segmentation</strong></p><blockquote><ul><li>Enjeu important.</li><li>Aucun algorithme universel.</li></ul></blockquote><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="7" data-x="11200" data-y="0"><h1 id="id3">INTRODUCTION</h1><h2 id="ojectif-accelerer">Ojectif : accélérer</h2><p><strong>Segmentation</strong></p><blockquote><ul><li>Algorithme par contours actifs, classe des <em>snakes</em>.</li><li>Implémentation CPU optimisée existante.</li><li>Conception de l'implémentation GPU.</li><li>Adaptations mineures de l'algorithme.</li></ul></blockquote><p><strong>Filtrage</strong></p><blockquote><ul><li>Filtre par lignes de niveaux<blockquote><ul><li>Algorithme original,</li><li>Conceptions conjointes algorithme et implémentation.</li></ul></blockquote></li><li>Filtres médians, filtres de convolution<blockquote><ul><li>Opérateurs mathématiques,</li><li>Conception d'une implémentation optimisée.</li></ul></blockquote></li></ul></blockquote></div><div class="step" step="8" data-x="12800" data-y="0"><h1 id="segmentation-par-contour-actif">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="travaux-de-reference">Travaux de référence</h2><p><strong>Level-set</strong> ( Roberts <em>et al.</em>, 2010)</p><blockquote><ul><li>Images d'IRM de 256x256x256 pixels (16 millions),</li><li>Temps sur GTX280 : <strong>11 s</strong>.</li></ul></blockquote><p><strong>Snake GVF</strong> (Smistad <em>et al.</em>, 2012)</p><blockquote><ul><li>Images d'IRM de 256x256x256 pixels (16 millions),</li><li>Temps sur C2070 : <strong>7 s</strong>.</li></ul></blockquote><img src="img/brain3D-gvf.png" alt="" width="600px" height=""></img><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><li>Les algorithmes <strong>level-set</strong> sont les plus implémentés sur GPU :</li><li>Les algorithmes <strong>snakes</strong> sont très peu implémentée sur GPU :</li></ul></div></div><div class="step" step="9" data-x="14400" data-y="0"><h1 id="id4">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>Objectif : déterminer le contour le plus <em>vraisemblable</em>.</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>Calcul des variances \(\sigma^2\) pour chaque contour :</li></ul><blockquote><ul><li>Méthode de Chesnaud <em>et el.</em> (1999) en \(\mathcal{O}(n^2)\).</li><li>Implique le <strong>pré-calcul</strong> de 3 images cumulées.</li></ul></blockquote><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="10" data-x="16000" data-y="0"><h1 id="id5">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="11" data-x="17600" data-y="0"><h1 id="id6">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id7"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/cochons-it21-it22.png" alt="" width="" height="300px"></img><img src="img/cochons-it4-it5.png" alt="" width="" height="300px"></img><div class="notes"><ul><li>CONVERGENCE RAPIDE</li></ul></div></div><div class="step" step="12" data-x="19200" data-y="0"><h1 id="id8">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id9"><em>Snake</em> polygonal orienté région (algo CPU)</h2><p>Exemples de résultats</p><img src="img/snake-exs.png" alt="" width="700px" height=""></img><div class="notes"><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><div class="step" step="13" data-x="20800" data-y="0"><h1 id="id10">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="14" data-x="22400" data-y="0"><h1 id="id11">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id12">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Calcul du critère GL</p><img src="img/algosnake-3etages.png" alt="" width="800px" height=""></img></div><div class="step" step="15" data-x="24000" data-y="0"><h1 id="id13">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id14">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="16" data-x="25600" data-y="0"><h1 id="id15">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id16">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><ul><li>1 thread par pixel.</li><li>Concaténation de tous les pixels composant l'ensemble des contours évalués.</li><li>Réductions en mémoire partagée.</li><li>Une seule taille de segment : la taille du plus long.</li></ul><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="17" data-x="27200" data-y="0"><h1 id="id17">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id18">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Points positifs :</p><blockquote><ul><li>Conservation des données en mémoire GPU.</li><li>Images cumulées calculées en parallèle.</li><li>Discretisation des segments en parallèle (1 thread/pixel).</li><li>Respect de l'algorithme original.</li></ul></blockquote><p>Points négatifs :</p><blockquote><ul><li>Trop peu de calculs à effectuer.</li><li>Motifs d'accès à la mémoire globale trop irréguliers.</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="18" data-x="28800" data-y="0"><h1 id="id19">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id20">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="400px" height=""></img></div><div class="step" step="19" data-x="30400" data-y="0"><h1 id="id21">SEGMENTATION PAR CONTOUR ACTIF</h1><h2 id="id22">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.</li><li>Image 10000x10000 en moins de 0,6 seconde.</li><li>Emploi non optimal du GPU : réductions, irrégularités.</li><li>Premières itérations GPU rapides : grands segments.</li><li>Temps de calcul très dépendant du contenu de l'image :<ul><li>Proposition d'une méthode d'initialisation alternative.</li><li>Recherche du contour rectangle le plus vraisemblable.</li><li>Accélération jusqu'à x15 avec de petites cibles.</li></ul></li></ul></div><div class="step" step="20" data-x="32000" data-y="0"><h1 id="le-filtrage-des-images">LE FILTRAGE DES IMAGES</h1><blockquote><ul><li>Filtre médian,</li><li>Filtres de convolution,</li><li>Filtre par recherche des lignes de niveaux (PIPD).</li></ul></blockquote></div><div class="step" step="21" data-x="33600" data-y="0"><h1 id="id23">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.</li></ul></div><div class="step" step="22" data-x="35200" data-y="0"><h1 id="id24">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="23" data-x="36800" data-y="0"><h1 id="id25">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-gpu-travaux-de-reference">Filtre médian GPU : Travaux de référence</h2><p>Comparaison des implémentations GPU de référence :</p><blockquote><ul><li><strong>PCMF</strong>, Sanchez <em>et al.</em> (2013), débit max. <strong>80 MP/s</strong>,</li><li><strong>ArrayFire</strong>, bibliothèque commerciale, débit max. <strong>185 MP/s</strong>,</li><li><strong>BVM</strong> parallélisé par Chen <em>et al.</em> (2009), 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="24" data-x="38400" data-y="0"><h1 id="id26">LE FILTRAGE DES IMAGES</h1><h2 id="id27">Filtre médian GPU : Travaux de référence</h2><p>Emploi de la <strong>mémoire partagée</strong> (exemple médian 5x5)</p><img src="img/shmemhalo.png" alt="" width="800px" height=""></img><div class="notes"><ul><li>recouvrement pose problème à cause accès concurrents à la mémoire partagée.</li></ul></div></div><div class="step" step="25" data-x="40000" data-y="0"><h1 id="id28">LE FILTRAGE DES IMAGES</h1><h2 id="optimisation-du-filtre-median-gpu">Optimisation du filtre médian GPU</h2><img src="img/CPU-GPU-memcpy.png" alt="" width="650px" height=""></img><img src="img/transferts-mem.png" alt="" width="" height="300px"></img><div class="notes"><p>On gagne de 13 à 43 % sur les temps de transfert.</p></div></div><div class="step" step="26" data-x="41600" data-y="0"><h1 id="id29">LE FILTRAGE DES IMAGES</h1><h2 id="id30">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, sur 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="27" data-x="43200" data-y="0"><h1 id="id31">LE FILTRAGE DES IMAGES</h1><h2 id="id32">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<blockquote><ul><li>mémoires individuelles au cœur du GPU,</li><li>non indexables dans un tableau.</li><li>maximum de 63 registres par thread et 32 K par bloc de threads.</li></ul></blockquote></li><li>Pour les petites tailles : max. 7x7 avec 1 pixel/thread.</li><li>Exploitation des recouvrements entre fenêtres voisines.</li></ul></blockquote></div><div class="step" step="28" data-x="44800" data-y="0"><h1 id="id33">LE FILTRAGE DES IMAGES</h1><h2 id="id34">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>Avantages :</p><ul><li>Évite le tri complet : performances en hausse,</li><li>Économie de registres : \(\lceil \frac{n}{2}\rceil +1\) au lieu de \(n\),</li><li>Permet de plus grandes tailles : max 11x11.</li></ul></td><td><img src="img/forgetful_selection.png" alt="" width="" height="500px"></img></td></tr></tbody></table></div><div class="step" step="29" data-x="46400" data-y="0"><h1 id="id35">LE FILTRAGE DES IMAGES</h1><h2 id="id36">Optimisation du filtre médian GPU</h2><p><strong>Exploitation des recouvrements</strong> : 2 pixels par thread (médian 5x5).</p><img src="img/recouvrement5.png" alt="" width="800px" height=""></img><p>À 4 pixels/thread, zone commune = 10 pixels < 14 : <strong>pas performant</strong>.</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="30" data-x="48000" data-y="0"><h1 id="id37">LE FILTRAGE DES IMAGES</h1><h2 id="performances-du-median-gpu-propose-prmf">Performances du médian GPU proposé (PRMF)</h2><img src="img/perf-median.png" alt="" width="650px" height=""></img></div><div class="step" step="31" data-x="49600" data-y="0"><h1 id="id38">LE FILTRAGE DES IMAGES</h1><h2 id="performances-du-filtre-median-gpu-propose-prmf">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 class="notes"><ul><li>débit décroit linéairement en fonction de <strong>n</strong></li></ul></div></div><div class="step" step="32" data-x="51200" data-y="0"><h1 id="id39">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>Accès optimaux : 1 lecture par pixel.</li><li>Débit global amélioré de <strong>x7</strong> à <strong>x10</strong>, proche du maximum.</li><li>Débit de calcul max. <strong>5,3 GP/s</strong>.</li><li>Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.</li><li>Création d'une application web générant les codes sources.</li><li>Utilisé sur images de cristallographie au synchrotron <strong>SPring-8</strong>.</li></ul></blockquote><img src="img/spring82.png" alt="" width="" height="200px"></img></div><div class="step" step="33" data-x="52800" data-y="0"><h1 id="id40">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>Selon les valeurs du masque h</strong></p><blockquote><ul><li>Réduction de bruit, détection de bords,...</li><li>Opération <strong>séparable</strong> en deux convolutions 1D.</li></ul></blockquote></div><div class="step" step="34" data-x="54400" data-y="0"><h1 id="id41">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution-gpu">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>Optimum à 8 pixels/thread :</li><li>Exemple médian 5x5, pour un thread :<blockquote><ul><li>60 pixels dans le halo : 60 lectures.</li><li>200 lectures + préchargement si utilisation mémoire partagée.</li></ul></blockquote></li></ul></blockquote><p>Nvidia propose les implémentations les plus rapides (séparable ou non) :</p><blockquote><ul><li>Traitement de référence : 2048x2048 pixels, 5x5, 8bits.</li></ul></blockquote><img src="img/debit-calcul-convoNS.png" alt="" width="600px" height=""></img></div><div class="step" step="35" data-x="56000" data-y="0"><h1 id="id42">LE FILTRAGE DES IMAGES</h1><h2 id="id43">Les filtres de convolution GPU</h2><p><strong>Résultats (suite)</strong></p><img src="img/debit-calcul-convoS.png" alt="" width="600px" height=""></img><p>Convolution séparable :</p><ul><li>Une convolution verticale en mémoire partagée, suivie d'une convolution horizontale en registres.</li><li>Copie intermédiaire en mémoire globale (cache 1D rapide).</li><li>L'accélération est due à la seule convolution en registres (54%).</li></ul></div><div class="step" step="36" data-x="57600" data-y="0"><h1 id="id44">LE FILTRAGE DES IMAGES</h1><h2 id="id45">Les filtres de convolution GPU</h2><p><strong>Conclusion</strong></p><blockquote><ul><li>Amélioration sensible sur les débits de calcul (de 17 à 33 %).</li><li>Le traitement 1D est jusqu'à 54% plus rapide.</li><li>Application à d'autres familles de signaux 1D (audio,...).</li></ul></blockquote></div><div class="step" step="37" data-x="59200" data-y="0"><h1 id="id46">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-par-recherche-des-lignes-de-niveaux">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="38" data-x="60800" data-y="0"><h1 id="id47">LE FILTRAGE DES IMAGES</h1><h2 id="id48">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="39" data-x="62400" data-y="0"><h1 id="id49">LE FILTRAGE DES IMAGES</h1><h2 id="id50">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="40" data-x="64000" data-y="0"><h1 id="id51">LE FILTRAGE DES IMAGES</h1><h2 id="id52">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="41" data-x="65600" data-y="0"><h1 id="id53">LE FILTRAGE DES IMAGES</h1><h2 id="id54">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="42" data-x="67200" data-y="0"><h1 id="id55">LE FILTRAGE DES IMAGES</h1><h2 id="id56">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="43" data-x="68800" data-y="0"><h1 id="id57">LE FILTRAGE DES IMAGES</h1><h2 id="id58">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="44" data-x="70400" data-y="0"><h1 id="id59">LE FILTRAGE DES IMAGES</h1><h2 id="id60">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="45" data-x="72000" 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 class="step" step="46" data-x="73600" data-y="0"><h1 id="annexe">ANNEXE</h1><h2 id="id61">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><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>
\ No newline at end of file
+<!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="http
://localhost/MATHJAX/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="avril-2014">17 avril 2014</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="filtrage">FILTRAGE</h1><p>Réduire le bruit.</p><img src="img/ex-filtrage.png" alt="" width="800px" height=""></img><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>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></ul></div></div><div class="step" step="2" data-x="3200" data-y="0"><h1 id="segmentation">SEGMENTATION</h1><p>Distinguer les zones statistiquement homogènes d'une image bruitée.</p><img src="img/seg2.png" alt="" width="800px" height=""></img><div class="notes"><ul><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="3" data-x="4800" data-y="0"><h1 id="id1">SEGMENTATION</h1><h2 id="deux-approches">Deux approches</h2><img src="img/approches.png" alt="" width="800px" height=""></img></div><div class="step" step="4" data-x="6400" data-y="0"><h1 id="plan-de-la-presentation">PLAN DE LA PRÉSENTATION</h1><ol><li>Introduction<ul><li>Les GPUs ou <em>Graphical Processing Units</em>.</li><li>Objectifs.</li></ul></li><li>La segmentation des images<ul><li>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>Travaux de référence.</li><li>Optimisation GPU des filtres médian et de convolution.</li><li>Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.</li></ul></li><li>Conclusion et perspectives</li></ol></div><div class="step" step="5" data-x="8000" data-y="0"><h1 id="introduction">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 milliers, d'unités de calcul, regroupées en 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><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></div><div class="step" step="6" data-x="9600" data-y="0"><h1 id="id2">INTRODUCTION</h1><h2 id="ojectif-accelerer">Ojectif : accélérer</h2><p><strong>Segmentation</strong></p><blockquote><ul><li>Algorithme par contours actifs, classe des <em>snakes</em>.</li><li>Implémentation CPU optimisée existante.</li><li>Conception de l'implémentation GPU.</li></ul></blockquote><p><strong>Filtrage</strong></p><blockquote><ul><li>Filtres médians, filtres de convolution<blockquote><ul><li>Opérateurs mathématiques,</li><li>Conception d'une implémentation optimisée.</li></ul></blockquote></li><li>Filtre par lignes de niveaux<blockquote><ul><li>Conception d'un algorithme dédié GPU.</li></ul></blockquote></li></ul></blockquote></div><div class="step" step="7" data-x="11200" data-y="0"><h1 id="id3">SEGMENTATION</h1><h2 id="travaux-de-reference">Travaux de référence</h2><p><strong>Level-set</strong> ( Roberts <em>et al.</em>, 2010)</p><blockquote><ul><li>Images d'IRM de 256x256x256 pixels (16 millions),</li><li>Temps sur GTX280 : <strong>11 s</strong>.</li></ul></blockquote><p><strong>Snake GVF</strong> (Smistad <em>et al.</em>, 2012)</p><blockquote><ul><li>Images d'IRM de 256x256x256 pixels (16 millions),</li><li>Temps sur C2070 : <strong>7 s</strong>.</li></ul></blockquote><img src="img/brain3D-gvf.png" alt="" width="600px" height=""></img><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><li>Les algorithmes <strong>level-set</strong> sont les plus implémentés sur GPU :</li><li>Les algorithmes <strong>snakes</strong> sont très peu implémentée sur GPU :</li></ul></div></div><div class="step" step="8" data-x="12800" data-y="0"><h1 id="id4">SEGMENTATION</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>Objectif : déterminer le contour le plus <em>vraisemblable</em>.</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>Calcul des variances \(\sigma^2\) pour chaque contour :</li></ul><blockquote><ul><li>Méthode de Chesnaud <em>et al.</em> (1999) : sommes sur le <strong>contour</strong>.</li><li>Implique le <strong>pré-calcul</strong> de 3 images cumulées.</li></ul></blockquote><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="9" data-x="14400" data-y="0"><h1 id="id5">SEGMENTATION</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><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></div><div class="step" step="10" data-x="16000" data-y="0"><h1 id="id6">SEGMENTATION</h1><h2 id="id7"><em>Snake</em> polygonal orienté région (algo CPU)</h2><img src="img/cochons-it21-it22.png" alt="" width="" height="300px"></img><img src="img/barre-blanche.png" alt="" width="" height="10px"></img><img src="img/cochons-it4-it5.png" alt="" width="" height="300px"></img><div class="notes"><ul><li>CONVERGENCE RAPIDE</li></ul></div></div><div class="step" step="11" data-x="17600" data-y="0"><h1 id="id8">SEGMENTATION</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="12" data-x="19200" data-y="0"><h1 id="id9">SEGMENTATION</h1><h2 id="id10">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Calcul du critère GL (1 pixel/thread)</p><img src="img/algosnake-3etages.png" alt="" width="800px" height=""></img></div><div class="step" step="13" data-x="20800" data-y="0"><h1 id="id11">SEGMENTATION</h1><h2 id="id12">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="14" data-x="22400" data-y="0"><h1 id="id13">SEGMENTATION</h1><h2 id="id14">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><ul><li>1 thread par pixel.</li><li>Concaténation dans un vecteur de tous les pixels composant l'ensemble des contours évalués.<ul><li>ex : 2x 256000 éléments à l'étape 1 de l'image 100 MP.</li></ul></li><li>Sommes des contributions des pixels : opérations de <strong>réduction</strong>.<ul><li>opérations mal adaptées à l'architecture GPU,</li><li>en mémoire partagée : accélération par rapport au CPU.</li></ul></li></ul><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="15" data-x="24000" data-y="0"><h1 id="id15">SEGMENTATION</h1><h2 id="id16">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p>Points positifs :</p><blockquote><ul><li>Conservation des données en mémoire GPU.</li><li>Images cumulées (pré-calculs) effectuées en parallèle.</li><li>Discrétisation des segments en parallèle (1 thread/pixel).</li><li>Respect de l'algorithme original.</li></ul></blockquote><p>Points négatifs :</p><blockquote><ul><li>Trop peu de calculs à effectuer.</li><li>Segments de tailles et orientations variables :<ul><li>motifs d'accès à la mémoire globale irréguliers,</li><li>nombreux threads inactifs.</li></ul></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="16" data-x="25600" data-y="0"><h1 id="id17">SEGMENTATION</h1><h2 id="id18">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="400px" height=""></img></div><div class="step" step="17" data-x="27200" data-y="0"><h1 id="id19">SEGMENTATION</h1><h2 id="id20">Parallélisation du <em>Snake</em> polygonal sur GPU</h2><p><strong>Conclusion</strong></p><ul><li>Première et seule implémentation connue à ce jour.</li><li>Performances intéressantes pour les grandes images.</li><li>Image 10000x10000 en moins de 0,6 seconde.</li><li>Emploi non optimal du GPU : réductions, irrégularités.</li><li>Temps de calcul très dépendant du contenu de l'image.</li><li>Proposition d'une méthode d'initialisation alternative :<blockquote><ul><li>Recherche du contour rectangle le plus vraisemblable.</li><li>Accélération jusqu'à x15 avec de petites cibles.</li></ul></blockquote></li></ul><p><strong>Publication</strong></p><blockquote><ul><li><em>G. Perrot, S. Domas, R. Couturier, and N. Bertaux</em>. <strong>Gpu implementation of a region based algorithm for large images segmentation.</strong> <em>In Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on, pages 291–298.</em></li></ul></blockquote></div><div class="step" step="18" data-x="28800" data-y="0"><h1 id="le-filtrage-des-images">LE FILTRAGE DES IMAGES</h1><blockquote><ul><li>Filtre médian,</li><li>Filtres de convolution,</li><li>Filtre par recherche des lignes de niveaux.</li></ul></blockquote></div><div class="step" step="19" data-x="30400" data-y="0"><h1 id="id21">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 du bruit <em>poivre & sel</em>.</li><li>Assez bonne préservation des contours.</li><li>Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).</li><li>Quelques applications avec de grandes fenêtres.</li><li>Opération de sélection coûteuse (tri).</li></ul></div><div class="step" step="20" data-x="32000" data-y="0"><h1 id="id22">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-exemple">Filtre médian : exemple</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></tr></thead><tbody><tr><td><p>Bruit <em>poivre & sel</em> 25%</p></td><td><p>Médian 5x5</p></td></tr></tbody></table></div><div class="step" step="21" data-x="33600" data-y="0"><h1 id="id23">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-median-gpu-travaux-de-reference">Filtre médian GPU : travaux de référence</h2><p>Comparaison des implémentations GPU de référence :</p><blockquote><ul><li><strong>PCMF</strong>, Sanchez <em>et al.</em> (2013), débit max. <strong>80 MP/s</strong>,</li><li><strong>ArrayFire</strong>, commerciale (2013), débit max. <strong>185 MP/s</strong>,</li><li><strong>BVM</strong> parallélisé par Chen <em>et al.</em> (2009), 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="22" data-x="35200" data-y="0"><h1 id="id24">LE FILTRAGE DES IMAGES</h1><h2 id="id25">Filtre médian GPU : Travaux de référence</h2><p>Emploi de la <strong>mémoire partagée</strong> (exemple médian 5x5)</p><table cellpadding="0" cellspacing="0"><tbody><tr><td><img src="img/shmem.png" alt="" width="" height=""></img></td><td><img src="img/carreB.png" alt="" width="" height=""></img></td><td><img src="img/halo.png" alt="" width="" height=""></img></td></tr></tbody></table><div class="notes"><ul><li>recouvrement pose problème à cause accès concurrents à la mémoire partagée.</li></ul></div></div><div class="step" step="23" data-x="36800" data-y="0"><h1 id="id26">LE FILTRAGE DES IMAGES</h1><h2 id="optimisation-du-filtre-median-gpu">Optimisation du filtre médian GPU</h2><img src="img/CPU-GPU-memcpy.png" alt="" width="650px" height=""></img><img src="img/transferts-mem.png" alt="" width="" height="300px"></img><div class="notes"><p>On gagne de 13 à 43 % sur les temps de transfert.</p></div></div><div class="step" step="24" data-x="38400" data-y="0"><h1 id="id27">LE FILTRAGE DES IMAGES</h1><h2 id="id28">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, sur 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="25" data-x="40000" data-y="0"><h1 id="id29">LE FILTRAGE DES IMAGES</h1><h2 id="id30">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<blockquote><ul><li>mémoires individuelles au cœur du GPU,</li><li>non indexables dans un tableau.</li><li>maximum de 63 registres par thread et 32 K par bloc de threads.</li></ul></blockquote></li><li>Pour les petites tailles : max. 7x7 avec 1 pixel/thread.</li><li>Exploitation des recouvrements entre fenêtres voisines.</li></ul></blockquote></div><div class="step" step="26" data-x="41600" data-y="0"><h1 id="id31">LE FILTRAGE DES IMAGES</h1><h2 id="id32">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>Avantages :</p><ul><li>Évite le tri complet : performances en hausse,</li><li>Économie de registres : \(\lceil \frac{n}{2}\rceil +1\) au lieu de \(n\),</li><li>Permet de plus grandes tailles : max 11x11.</li></ul></td><td><img src="img/forgetful_selection.png" alt="" width="" height="500px"></img></td></tr></tbody></table></div><div class="step" step="27" data-x="43200" data-y="0"><h1 id="id33">LE FILTRAGE DES IMAGES</h1><h2 id="id34">Optimisation du filtre médian GPU</h2><p><strong>Exploitation des recouvrements</strong> : 2 pixels par thread (médian 5x5).</p><img src="img/recouvrement5.png" alt="" width="800px" height=""></img><ul><li><strong>7+2x5 = 17</strong> étapes de sélection au lieu de <strong>2x12 = 24</strong>.</li><li>Les plus coûteuses sont communes.</li><li>À 4 pixels/thread, zone commune = 10 pixels < 14.</li></ul><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="28" data-x="44800" data-y="0"><h1 id="id35">LE FILTRAGE DES IMAGES</h1><h2 id="performances-du-median-gpu-propose-prmf">Performances du médian GPU proposé (PRMF)</h2><img src="img/perf-median.png" alt="" width="650px" height=""></img><p><strong>Rappels :</strong></p><blockquote><ul><li>débit crête de la plateforme = 2444 MP/s.</li><li>débit maximum des implémentations de référence = 185 MP/s.</li></ul></blockquote></div><div class="step" step="29" data-x="46400" data-y="0"><h1 id="id36">LE FILTRAGE DES IMAGES</h1><h2 id="performances-du-filtre-median-gpu-propose-prmf">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 class="notes"><ul><li>débit décroit linéairement en fonction de <strong>n</strong></li></ul></div></div><div class="step" step="30" data-x="48000" data-y="0"><h1 id="id37">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>Accès optimaux : 1 lecture par pixel.</li><li>Débit global amélioré de <strong>x7</strong> à <strong>x10</strong>, proche du maximum.</li><li>Débit de calcul max. <strong>5,3 GP/s</strong>.</li><li>Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.</li><li>Création d'une application web générant les codes sources.</li><li>Utilisé sur images de cristallographie au synchrotron SPring-8.</li></ul></blockquote><p><strong>Publications</strong></p><blockquote><ul><li><em>Gilles Perrot. Image processing. In</em> <strong>Designing Scientific Applications on GPUs</strong>, <em>pages 28-70. CRC Press, 2013.</em></li><li><em>Gilles Perrot, Stéphane Domas, and Raphaël Couturier.</em> <strong>Fine-tuned high-speed implementation of a gpu-based median filter.</strong> <em>Journal of Signal Processing Systems, pages 1–6, 2013.</em></li></ul></blockquote></div><div class="step" step="31" data-x="49600" data-y="0"><h1 id="id38">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution">Les filtres de convolution</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>Selon les valeurs du masque h</strong></p><blockquote><ul><li>Réduction de bruit, détection de bords,...</li><li>Potentiellement <strong>séparable</strong> en deux convolutions 1D.</li></ul></blockquote></div><div class="step" step="32" data-x="51200" data-y="0"><h1 id="id39">LE FILTRAGE DES IMAGES</h1><h2 id="les-filtres-de-convolution-gpu">Les filtres de convolution GPU</h2><p>Extension des méthodes appliquées au filtre médian :</p><blockquote><ul><li>Un seul accès mémoire par pixel.</li><li>Mémorisation et calculs en registre.</li><li>Optimum à 8 pixels/thread.</li></ul></blockquote><p>Implémentations de référence (C2070) :</p><blockquote><ul><li>Nvidia atteint un débit de calcul maximum de <strong>6,00 GP/s</strong>.</li></ul></blockquote></div><div class="step" step="33" data-x="52800" data-y="0"><h1 id="id40">LE FILTRAGE DES IMAGES</h1><h2 id="id41">Les filtres de convolution GPU</h2><p><strong>Résultats</strong></p><blockquote><ul><li>Amélioration sensible des débits de calcul en 2D : 16 à 35 %.</li><li>Débit de la convolution 1D horizontale jusqu'à 54% plus élevé.</li><li>Débit maximum de <strong>8,54 GP/s</strong>.</li><li>Application à d'autres familles de signaux 1D (audio,...).</li></ul></blockquote></div><div class="step" step="34" data-x="54400" data-y="0"><h1 id="id42">LE FILTRAGE DES IMAGES</h1><h2 id="filtre-par-recherche-des-lignes-de-niveaux">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="35" data-x="56000" data-y="0"><h1 id="id43">LE FILTRAGE DES IMAGES</h1><h2 id="id44">Filtre par recherche des lignes de niveaux</h2><p><strong>Principe - modèle</strong></p><blockquote><ul><li>Estimation locale, par maximum de vraisemblance.</li><li>Réduction de bruit par moyennage le long de la ligne estimée.</li><li>Modèle de ligne de niveaux retenu : <strong>isoline</strong><blockquote><p>= ligne brisée composée de <strong>segments</strong>.</p></blockquote></li><li>Segments choisis parmi 32 motifs pré-calculés.</li><li>Les 8 premiers motifs pour des segments de 6 pixels :<img src="img/P5Q1.png" alt="" width="450px" height=""></img></li></ul></blockquote></div><div class="step" step="36" data-x="57600" data-y="0"><h1 id="id45">LE FILTRAGE DES IMAGES</h1><h2 id="id46">Filtre par recherche des lignes de niveaux</h2><p><strong>Étape 1</strong> (1 pixel/thread)</p><blockquote><ul><li>En chaque pixel, recherche du motif maximisant la log-vraisemblance ( exemple \(n=6\))</li></ul>$$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$<img src="img/lniv-mv.png" alt="" width="400px" height=""></img><ul><li>Mémorisation des paramètres du motif sélectionné dans deux matrices \(I_{\Theta}\) (indice) et \(I_{\Sigma}\) (moyenne, variance).</li></ul></blockquote></div><div class="step" step="37" data-x="59200" data-y="0"><h1 id="id47">LE FILTRAGE DES IMAGES</h1><h2 id="id48">Filtre par recherche des lignes de niveaux</h2><p><strong>Étape 2</strong> (1 pixel/thread)</p><blockquote><ul><li>Isoline validée de \(n_{prec}\) pixels.</li><li>Segment candidat de \(n_s\) pixels.</li><li>Allongement de l'isoline sous condition GLRT ?</li></ul>$$GLRT=T-\scriptstyle (n_{prec}+n_s)\left[log\left(\widehat{\sigma_{prec+s}}^2\right) - log\left(\widehat{\sigma_{prec}}^2\right) - log\left(\widehat{\sigma_{s}}^2\right) \right]$$<img src="img/pipd-extension.png" alt="" width="500px" height=""></img></blockquote></div><div class="step" step="38" data-x="60800" data-y="0"><h1 id="id49">LE FILTRAGE DES IMAGES</h1><h2 id="id50">Filtre par recherche des lignes de niveaux</h2><p><strong>Étape 3</strong> (optionnelle)</p><blockquote><p>Compensation de la non robustesse de sélection des motifs dans les zones homogènes.</p><blockquote><ul><li>Conception d'un détecteur de zones homogènes.</li><li>Identification des zones homogènes avec ce détecteur.</li><li>Application d'un filtre moyenneur dans les zones identifiées comme homogènes (convolution).</li></ul></blockquote></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="39" data-x="62400" data-y="0"><h1 id="id51">LE FILTRAGE DES IMAGES</h1><h2 id="id52">Filtre par recherche des lignes de niveaux</h2><p><strong>Résultats</strong></p><blockquote><p>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 (C2070, <strong>avec</strong> détecteur) : <strong>7 ms</strong>.</li></ul><p>Algorithme de référence 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 class="notes"><ul><li>2,4 dB d'écart, soit réduction de 43% de la puissance de bruit</li></ul></div></div><div class="step" step="40" data-x="64000" data-y="0"><h1 id="id53">LE FILTRAGE DES IMAGES</h1><h2 id="id54">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="41" data-x="65600" data-y="0"><h1 id="id55">LE FILTRAGE DES IMAGES</h1><h2 id="id56">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.</li><li>Parallélisation de la méthode de Buades <em>et al.</em> (2006) :<blockquote><ul><li>gain +1 dB en +0,2 ms pour 512x512.</li></ul></blockquote></li><li>Algorithme dédié GPU, sans implémentation séquentielle de référence.</li></ul></blockquote><p><strong>Publication</strong></p><blockquote><ul><li><em>Gilles Perrot, Stéphane Domas, Raphaël Couturier, and Nicolas Bertaux.</em> <strong>Fast gpu-based denoising filter using isoline levels.</strong> <em>Journal of Real-Time Image Processing, pages 1–12, 2013.</em></li></ul></blockquote></div><div class="step" step="42" data-x="67200" data-y="0"><h1 id="conclusion-generale">CONCLUSION GÉNÉRALE</h1><ul><li>Trois types de conception mis en œuvre :<blockquote><ul><li>Parallélisation GPU d'une implémentation CPU (<em>snake</em>).</li><li>Implémentations optimisées pour GPU d'opérateurs mathématiques (médian, convolution).</li><li>Algorithme dédié GPU et son implémentation (isolines).</li></ul></blockquote></li><li>Le portage <strong>efficace</strong> d'algorithme sur GPU s'avère très complexe.</li><li>Certains algorithmes ne se prêtent pas à la parallélisation GPU.</li><li>L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.</li><li>Filtrage à des débits inégalés, proches des performances crête.</li><li>Filtres utilisables par tout programmeur grâce au générateur de code.</li></ul></div><div class="step" step="43" data-x="68800" data-y="0"><h1 id="perspectives">PERSPECTIVES</h1><blockquote><ul><li>Extension des filtres aux images couleurs et autres types de bruits (multiplicatif).</li><li>Extension aux pseudo-médians de grandes tailles (microscopie).</li><li>Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées (audio, imagerie 3D, BM3D).</li><li>Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités (parallélisme dynamique, kernels concurrents).</li></ul></blockquote><div class="notes"><ul><li>certaines ardeurs ont été refroidies</li></ul></div></div><div class="step" step="44" data-x="70400" data-y="0"><h1 id="annexe-1">ANNEXE 1</h1><h2 id="id57">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="45" data-x="72000" data-y="0"><h1 id="annexe-2-median">ANNEXE 2 (médian)</h1><h2 id="image-cristallographie-spring-8">Image cristallographie SPring-8</h2><img src="img/spring82.png" alt="" width="400px" height=""></img></div><div class="step" step="46" data-x="73600" data-y="0"><h1 id="annexe-3-lniv">ANNEXE 3 (lniv)</h1><h2 id="detecteur-de-bords">Détecteur de bords</h2><blockquote><img src="img/detecteur.png" alt="" width="400px" height=""></img></blockquote></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>
\ No newline at end of file
