From: zulu Date: Tue, 15 Apr 2014 17:54:15 +0000 (+0200) Subject: final X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/commitdiff_plain/e42b2289f57cc234c130e3cfdec43a7328d24958 final --- diff --git a/PRESENTATION (copie).tar.gz b/PRESENTATION (copie).tar.gz new file mode 100644 index 0000000..0a1810b Binary files /dev/null and b/PRESENTATION (copie).tar.gz differ diff --git a/PRESENTATION/css/zulug5.css b/PRESENTATION/css/zulug5.css index 5338d40..0e94d42 100644 --- a/PRESENTATION/css/zulug5.css +++ b/PRESENTATION/css/zulug5.css @@ -40,6 +40,7 @@ header { font-size: 50px; text-shadow: rgba(0, 0, 0, 0.2) 0 2px 5px; } + h1 { color: #0054AB ; font-size: 200%; @@ -160,6 +161,13 @@ img:hover { margin-left: 780px; } +body{counter-reset: h1;} +h1:after { + content: " (" counter(h1) ") "; + counter-increment: h1; + text-align: right ; + font-size: 40% ; +} body { diff --git a/PRESENTATION/diapos.rst b/PRESENTATION/diapos.rst index 8a0274d..f4a6af8 100644 --- a/PRESENTATION/diapos.rst +++ b/PRESENTATION/diapos.rst @@ -67,10 +67,10 @@ Réduire le bruit. SEGMENTATION ============ -Distinguer les zones homogènes d'une image. +Distinguer les zones statistiquement homogènes d'une image bruitée. -.. image:: img/seg1.png - :width: 700px +.. image:: img/seg2.png + :width: 800px .. note:: @@ -78,27 +78,16 @@ Distinguer les zones homogènes d'une image. * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses. * Mais aujourd'hui encore, une bonne segmentation est celle qui permet d'extraire ce que l'on attend => l'algorithme dépend du problème. - ---- SEGMENTATION ============ Deux approches +-------------- .. image:: img/approches.png :width: 800px -.. note:: - - * **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*. - - * réduction, *a priori*, du coût des traitements de haut niveau. - * les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information. - - * **Ne pas pré-traiter** et effectuer les traitements de haut niveau sur les images bruitées. - - * pas de perte d'information due au pré-traitement. - ---- PLAN DE LA PRÉSENTATION @@ -107,7 +96,7 @@ PLAN DE LA PRÉSENTATION #. Introduction - Les GPUs ou *Graphical Processing Units*. - - Le filtrage et la segmentation d'images. + - Objectifs. #. La segmentation des images @@ -156,31 +145,6 @@ Les GPUs ou *Processeurs graphiques*. * 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. - ----- - -INTRODUCTION -============ -Le traitement des images ------------------------- - -**Le filtrage (du bruit)** - - * Les capteurs et les conditions d'acquisition induisent du bruit. - * *Résolution élevée* n'implique pas *bruit réduit*. - -**La segmentation** - - * Enjeu important. - * Aucun algorithme universel. - -.. note:: - - * les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation. - * on recense plus de 4000 algorithmes de segmentation - * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses. - * Mais aujourd'hui encore, une bonne segmentation est celle qui permet d'extraire ce que l'on attend => l'algorithme dépend du problème. - ---- INTRODUCTION @@ -189,31 +153,28 @@ INTRODUCTION Ojectif : accélérer ------------------- - **Segmentation** * Algorithme par contours actifs, classe des *snakes*. * Implémentation CPU optimisée existante. * Conception de l'implémentation GPU. - * Adaptations mineures de l'algorithme. **Filtrage** - * Filtre par lignes de niveaux - - - Algorithme original, - - Conceptions conjointes algorithme et implémentation. - * Filtres médians, filtres de convolution - Opérateurs mathématiques, - Conception d'une implémentation optimisée. - + * Filtre par lignes de niveaux + + - Conception d'un algorithme dédié GPU. + + ---- -SEGMENTATION PAR CONTOUR ACTIF -============================== +SEGMENTATION +============ Travaux de référence -------------------- @@ -241,7 +202,7 @@ Travaux de référence ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== *Snake* polygonal orienté région (principe) ------------------------------------------- @@ -263,7 +224,7 @@ SEGMENTATION PAR CONTOUR ACTIF * Calcul des variances :math:`\(\sigma^2\)` pour chaque contour : - * Méthode de Chesnaud *et el.* (1999) en :math:`\(\mathcal{O}(n^2)\)`. + * Méthode de Chesnaud *et al.* (1999) : sommes sur le **contour**. * Implique le **pré-calcul** de 3 images cumulées. .. note:: @@ -272,7 +233,7 @@ SEGMENTATION PAR CONTOUR ACTIF ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== *Snake* polygonal orienté région (algo CPU) -------------------------------------------- @@ -280,15 +241,14 @@ SEGMENTATION PAR CONTOUR ACTIF .. image:: img/cochons-it0-it1.png :height: 300px -**Itération 1** - #. Le contour initial est rectangulaire ( 4 n |oe| uds ) - #. On déplace successivement les 4 n |oe| uds jusqu'à ce que plus aucun nouveau déplacement ne provoque l'amélioration du critère. +#. Le contour initial est rectangulaire ( 4 n |oe| uds ) +#. On déplace successivement les 4 n |oe| uds jusqu'à ce que plus aucun nouveau déplacement ne provoque l'amélioration du critère. ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== *Snake* polygonal orienté région (algo CPU) -------------------------------------------- @@ -296,6 +256,9 @@ SEGMENTATION PAR CONTOUR ACTIF .. image:: img/cochons-it21-it22.png :height: 300px +.. image:: img/barre-blanche.png + :height: 10px + .. image:: img/cochons-it4-it5.png :height: 300px @@ -303,25 +266,10 @@ SEGMENTATION PAR CONTOUR ACTIF * CONVERGENCE RAPIDE ----- - -SEGMENTATION PAR CONTOUR ACTIF -=============================== -*Snake* polygonal orienté région (algo CPU) --------------------------------------------- - -Exemples de résultats - -.. figure:: img/snake-exs.png - :width: 700px - -.. note :: - - * Les résultats de segmentation dépendent des paramètres de la séquence d'optimisation (pas des déplacements, contour initial, seuil d'ajout des n |oe| uds) ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- @@ -332,11 +280,11 @@ Identification des fonctions coûteuses ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- -Calcul du critère GL +Calcul du critère GL (1 pixel/thread) .. image:: img/algosnake-3etages.png :width: 800px @@ -344,7 +292,7 @@ Calcul du critère GL ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- @@ -362,15 +310,20 @@ Parallélisation du *Snake* polygonal sur GPU ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- * 1 thread par pixel. -* Concaténation de tous les pixels composant l'ensemble des contours évalués. -* Réductions en mémoire partagée. -* Une seule taille de segment : la taille du plus long. +* Concaténation dans un vecteur de tous les pixels composant l'ensemble des contours évalués. + + - ex : 2x 256000 éléments à l'étape 1 de l'image 100 MP. + +* Sommes des contributions des pixels : opérations de **réduction**. + + - opérations mal adaptées à l'architecture GPU, + - en mémoire partagée : accélération par rapport au CPU. .. note:: @@ -378,7 +331,7 @@ Parallélisation du *Snake* polygonal sur GPU ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- @@ -386,15 +339,17 @@ Parallélisation du *Snake* polygonal sur GPU Points positifs : * Conservation des données en mémoire GPU. - * Images cumulées calculées en parallèle. - * Discretisation des segments en parallèle (1 thread/pixel). + * Images cumulées (pré-calculs) effectuées en parallèle. + * Discrétisation des segments en parallèle (1 thread/pixel). * Respect de l'algorithme original. Points négatifs : * Trop peu de calculs à effectuer. - * Motifs d'accès à la mémoire globale trop irréguliers. - * Emploi de la mémoire partagée. + * Segments de tailles et orientations variables : + + - motifs d'accès à la mémoire globale irréguliers, + - nombreux threads inactifs. .. note:: @@ -407,7 +362,7 @@ Points négatifs : ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- @@ -424,24 +379,27 @@ Parallélisation du *Snake* polygonal sur GPU ---- -SEGMENTATION PAR CONTOUR ACTIF +SEGMENTATION =============================== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- **Conclusion** -* Première et seule implémentation à ce jour. +* Première et seule implémentation connue à ce jour. * Performances intéressantes pour les grandes images. * Image 10000x10000 en moins de 0,6 seconde. * Emploi non optimal du GPU : réductions, irrégularités. -* Premières itérations GPU rapides : grands segments. -* Temps de calcul très dépendant du contenu de l'image : - - - Proposition d'une méthode d'initialisation alternative. - - Recherche du contour rectangle le plus vraisemblable. - - Accélération jusqu'à x15 avec de petites cibles. +* Temps de calcul très dépendant du contenu de l'image. +* Proposition d'une méthode d'initialisation alternative : + - Recherche du contour rectangle le plus vraisemblable. + - Accélération jusqu'à x15 avec de petites cibles. + +**Publication** + + * *G. Perrot, S. Domas, R. Couturier, and N. Bertaux*. **Gpu implementation of a region based algorithm for large images segmentation.** *In Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on, pages 291–298.* + ---- LE FILTRAGE DES IMAGES @@ -449,7 +407,7 @@ LE FILTRAGE DES IMAGES * Filtre médian, * Filtres de convolution, - * Filtre par recherche des lignes de niveaux (PIPD). + * Filtre par recherche des lignes de niveaux. ---- @@ -463,38 +421,38 @@ Filtre médian : principe La valeur de sortie d'un pixel est la **médiane** des valeurs de son voisinage. -* Bonne réduction de bruits gaussien et *poivre & sel* -* Valeurs de sortie appartenant au voisinage. -* Opération de sélection coûteuse (tri). +* Bonne réduction du bruit *poivre & sel*. +* Assez bonne préservation des contours. * Usages fréquents avec des petites fenêtres (de 3x3 à 7x7). * Quelques applications avec de grandes fenêtres. +* Opération de sélection coûteuse (tri). ---- LE FILTRAGE DES IMAGES ====================== -Filtre médian : usage ---------------------- +Filtre médian : exemple +----------------------- .. table:: - =================================== ======================================== ============================================ - .. image:: img/airplane_sap25.png .. image:: img/airplane_sap25_med5.png .. image:: img/airplane_sap25_med3_it2.png - =================================== ======================================== ============================================ - Bruit *poivre & sel* 25% Médian 5x5 Médian 3x3 - 2 passes - =================================== ======================================== ============================================ + =================================== ======================================== + .. image:: img/airplane_sap25.png .. image:: img/airplane_sap25_med5.png + =================================== ======================================== + Bruit *poivre & sel* 25% Médian 5x5 + =================================== ======================================== ---- LE FILTRAGE DES IMAGES ====================== -Filtre médian GPU : Travaux de référence +Filtre médian GPU : travaux de référence ---------------------------------------- Comparaison des implémentations GPU de référence : - **PCMF**, Sanchez *et al.* (2013), débit max. **80 MP/s**, - - **ArrayFire**, bibliothèque commerciale, débit max. **185 MP/s**, + - **ArrayFire**, commerciale (2013), débit max. **185 MP/s**, - **BVM** parallélisé par Chen *et al.* (2009), débit max. **110 MP/s**. .. image:: img/compar-median2.png @@ -514,9 +472,13 @@ Filtre médian GPU : Travaux de référence Emploi de la **mémoire partagée** (exemple médian 5x5) -.. image:: img/shmemhalo.png - :width: 800px - +.. table:: + + =================================== ========================== ======================================== + .. image:: img/shmem.png .. image:: img/carreB.png .. image:: img/halo.png + =================================== ========================== ======================================== + + .. note:: - recouvrement pose problème à cause accès concurrents à la mémoire partagée. @@ -616,7 +578,9 @@ Optimisation du filtre médian GPU .. image:: img/recouvrement5.png :width: 800px -À 4 pixels/thread, zone commune = 10 pixels < 14 : **pas performant**. +* **7+2x5 = 17** étapes de sélection au lieu de **2x12 = 24**. +* Les plus coûteuses sont communes. +* À 4 pixels/thread, zone commune = 10 pixels < 14. .. note:: @@ -633,6 +597,11 @@ Performances du médian GPU proposé (PRMF) .. image:: img/perf-median.png :width: 650px +**Rappels :** + + - débit crête de la plateforme = 2444 MP/s. + - débit maximum des implémentations de référence = 185 MP/s. + ---- LE FILTRAGE DES IMAGES @@ -669,17 +638,20 @@ Le filtre médian GPU * Débit de calcul max. **5,3 GP/s**. * Médian jusqu'au 11x11 sur C2070, 21x21 sur K40. * Création d'une application web générant les codes sources. - * Utilisé sur images de cristallographie au synchrotron **SPring-8**. - -.. image:: img/spring82.png - :height: 200px + * Utilisé sur images de cristallographie au synchrotron SPring-8. + +**Publications** + + * *Gilles Perrot. Image processing. In* **Designing Scientific Applications on GPUs**, *pages 28-70. CRC Press, 2013.* + * *Gilles Perrot, Stéphane Domas, and Raphaël Couturier.* **Fine-tuned high-speed implementation of a gpu-based median filter.** *Journal of Signal Processing Systems, pages 1–6, 2013.* + ---- LE FILTRAGE DES IMAGES ====================== -Les filtres de convolution : généralités ------------------------------------------ +Les filtres de convolution +-------------------------- **Principe** @@ -690,7 +662,7 @@ Les filtres de convolution : généralités **Selon les valeurs du masque h** * Réduction de bruit, détection de bords,... - * Opération **séparable** en deux convolutions 1D. + * Potentiellement **séparable** en deux convolutions 1D. ---- @@ -701,39 +673,16 @@ LE FILTRAGE DES IMAGES Les filtres de convolution GPU ------------------------------ -Exploitation des recouvrements : - - * un seul accès mémoire par pixel, mémorisation en registre. - * Optimum à 8 pixels/thread : - * Exemple médian 5x5, pour un thread : - - - 60 pixels dans le halo : 60 lectures. - - 200 lectures + préchargement si utilisation mémoire partagée. - -Nvidia propose les implémentations les plus rapides (séparable ou non) : - - * Traitement de référence : 2048x2048 pixels, 5x5, 8bits. - -.. image:: img/debit-calcul-convoNS.png - :width: 600px - ----- - -LE FILTRAGE DES IMAGES -====================== -Les filtres de convolution GPU ------------------------------- +Extension des méthodes appliquées au filtre médian : -**Résultats (suite)** + * Un seul accès mémoire par pixel. + * Mémorisation et calculs en registre. + * Optimum à 8 pixels/thread. -.. image:: img/debit-calcul-convoS.png - :width: 600px +Implémentations de référence (C2070) : -Convolution séparable : + * Nvidia atteint un débit de calcul maximum de **6,00 GP/s**. -* Une convolution verticale en mémoire partagée, suivie d'une convolution horizontale en registres. -* Copie intermédiaire en mémoire globale (cache 1D rapide). -* L'accélération est due à la seule convolution en registres (54%). ---- @@ -742,12 +691,14 @@ LE FILTRAGE DES IMAGES Les filtres de convolution GPU ------------------------------ -**Conclusion** +**Résultats** - * Amélioration sensible sur les débits de calcul (de 17 à 33 %). - * Le traitement 1D est jusqu'à 54% plus rapide. + * Amélioration sensible des débits de calcul en 2D : 16 à 35 %. + * Débit de la convolution 1D horizontale jusqu'à 54% plus élevé. + * Débit maximum de **8,54 GP/s**. * Application à d'autres familles de signaux 1D (audio,...). + ---- LE FILTRAGE DES IMAGES @@ -770,14 +721,17 @@ Filtre par recherche des lignes de niveaux **Principe - modèle** - * Estimation locale, par maximum de vraisemblance, des lignes de niveaux. + * Estimation locale, par maximum de vraisemblance. * Réduction de bruit par moyennage le long de la ligne estimée. - * Les lignes de niveaux estimées sont modélisées par des lignes brisées nommées **isolines**. - * Les segments des lignes brisées sont choisis parmi des motifs pré-établis (32 motifs). - + * Modèle de ligne de niveaux retenu : **isoline** + + = ligne brisée composée de **segments**. + * Segments choisis parmi 32 motifs pré-calculés. + * Les 8 premiers motifs pour des segments de 6 pixels : + .. image:: img/P5Q1.png - :width: 500px + :width: 450px ---- @@ -787,18 +741,20 @@ LE FILTRAGE DES IMAGES Filtre par recherche des lignes de niveaux ------------------------------------------ -**Principe (étape 1)** +**Étape 1** (1 pixel/thread) - * En chaque pixel, recherche du motif maximisant la log-vraisemblance ( :math:`\(n=6, \sigma^2 =\)` variance ) + * En chaque pixel, recherche du motif maximisant la log-vraisemblance ( exemple :math:`\(n=6\)`) .. math:: $$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$ - * Mémorisation des paramètres des motifs sélectionnés dans deux matrices :math:`\(I_{\Theta}\)` et :math:`\(I_{\Sigma}\)`. - + .. image:: img/lniv-mv.png - :width: 500px + :width: 400px + + + * Mémorisation des paramètres du motif sélectionné dans deux matrices :math:`\(I_{\Theta}\)` (indice) et :math:`\(I_{\Sigma}\)` (moyenne, variance). ---- @@ -807,16 +763,19 @@ LE FILTRAGE DES IMAGES Filtre par recherche des lignes de niveaux ------------------------------------------ -**Principe (étape 2)** - - * Allongement itératif des segments sous condition GLRT. +**Étape 2** (1 pixel/thread) + * Isoline validée de :math:`\(n_{prec}\)` pixels. + * Segment candidat de :math:`\(n_s\)` pixels. + * Allongement de l'isoline sous condition GLRT ? + + .. math:: - $$(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]$$ + $$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]$$ - .. image:: img/pipd-detail.png - :width: 900px + .. image:: img/pipd-extension.png + :width: 500px ---- @@ -825,16 +784,14 @@ LE FILTRAGE DES IMAGES Filtre par recherche des lignes de niveaux ------------------------------------------ -**Principe (étape 3)** +**Étape 3** (optionnelle) Compensation de la non robustesse de sélection des motifs dans les zones homogènes. - * identification des zones homogènes avec un détecteur de bords. - * Application d'un filtre moyenneur dans ces zones. + * Conception d'un détecteur de zones homogènes. + * Identification des zones homogènes avec ce détecteur. + * Application d'un filtre moyenneur dans les zones identifiées comme homogènes (convolution). - .. image:: img/detecteur.png - :width: 400px - .. note:: * Sous-ensembles de pixels n'ayant pas d'intersection --> MV @@ -849,18 +806,22 @@ Filtre par recherche des lignes de niveaux **Résultats** - Sur l'ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD) + Ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD) - * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB** - * Indice de similarité structurelle : **+30%** - * Temps de calcul : **7 ms** + * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB**, + * Indice de similarité structurelle : **+30%**, + * Temps de calcul (C2070, **avec** détecteur) : **7 ms**. - Comparaison avec BM3D + Algorithme de référence BM3D - * Amélioration moyenne du rapport Signal sur bruit: **+9,5 dB** - * Indice de similarité structurelle : **+36%** - * Temps de calcul : **4300 ms** + * Amélioration moyenne du rapport Signal sur bruit: **+9,5 dB**, + * Indice de similarité structurelle : **+36%**, + * Temps de calcul : **4300 ms**. +.. note:: + + * 2,4 dB d'écart, soit réduction de 43% de la puissance de bruit + -------- LE FILTRAGE DES IMAGES @@ -891,31 +852,56 @@ Filtre par recherche des lignes de niveaux * Rapport qualité/temps élevé. * Traitement d'images HD à 20 fps. - * Artefacts en marche d'escalier. Réduits par la méthode de Buades *et al.* (+1 dB, +0,2 ms pour 512x512). - * Extension aux images couleurs et autres types de bruits (multiplicatif). - * Algorithme original sans implémentation séquentielle de référence. + * Artefacts en marche d'escalier. + * Parallélisation de la méthode de Buades *et al.* (2006) : + + - gain +1 dB en +0,2 ms pour 512x512. + + * Algorithme dédié GPU, sans implémentation séquentielle de référence. + +**Publication** + + * *Gilles Perrot, Stéphane Domas, Raphaël Couturier, and Nicolas Bertaux.* **Fast gpu-based denoising filter using isoline levels.** *Journal of Real-Time Image Processing, pages 1–12, 2013.* + ---- -CONCLUSION GÉNÉRALE - PERSPECTIVES -================================== +CONCLUSION GÉNÉRALE +=================== + +* Trois types de conception mis en |~oe| uvre : -* Trois types de conception mis en |~oe| uvre. -* Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt. + - Parallélisation GPU d'une implémentation CPU (*snake*). + - Implémentations optimisées pour GPU d'opérateurs mathématiques (médian, convolution). + - Algorithme dédié GPU et son implémentation (isolines). + +* Le portage **efficace** d'algorithme sur GPU s'avère très complexe. +* Certains algorithmes ne se prêtent pas à la parallélisation GPU. * L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements. -* Filtres utilisables par tout programmeur grâce à un générateur de code. -* Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées. -* Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités. +* Filtrage à des débits inégalés, proches des performances crête. +* Filtres utilisables par tout programmeur grâce au générateur de code. + + +---- + +PERSPECTIVES +============ + + * Extension des filtres aux images couleurs et autres types de bruits (multiplicatif). + * Extension aux pseudo-médians de grandes tailles (microscopie). + * Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées (audio, imagerie 3D, BM3D). + * Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités (parallélisme dynamique, kernels concurrents). .. note:: * certaines ardeurs ont été refroidies + ---- -ANNEXE -====== +ANNEXE 1 +======== Parallélisation du *Snake* polygonal sur GPU -------------------------------------------- @@ -928,6 +914,27 @@ Parallélisation du *Snake* polygonal sur GPU * règle 1 thread par pixel +---- + +ANNEXE 2 (médian) +================= +Image cristallographie SPring-8 +------------------------------- + +.. image:: img/spring82.png + :width: 400px + +---- + +ANNEXE 3 (lniv) +=============== +Détecteur de bords +------------------ + + .. image:: img/detecteur.png + :width: 400px + + .. |oe| unicode:: U+0153 :trim: diff --git a/PRESENTATION/img/CPU-GPU-memcpy.png b/PRESENTATION/img/CPU-GPU-memcpy.png index 0bc6402..56fbd0f 100644 Binary files a/PRESENTATION/img/CPU-GPU-memcpy.png and b/PRESENTATION/img/CPU-GPU-memcpy.png differ diff --git a/PRESENTATION/img/airplane_sap25.png b/PRESENTATION/img/airplane_sap25.png index 3fa4004..22856c2 100755 Binary files a/PRESENTATION/img/airplane_sap25.png and b/PRESENTATION/img/airplane_sap25.png differ diff --git a/PRESENTATION/img/airplane_sap25_med5.png b/PRESENTATION/img/airplane_sap25_med5.png index 03c9a04..5316fea 100755 Binary files a/PRESENTATION/img/airplane_sap25_med5.png and b/PRESENTATION/img/airplane_sap25_med5.png differ diff --git a/PRESENTATION/img/algosnake-3etages.png b/PRESENTATION/img/algosnake-3etages.png index af82ac7..1d5329c 100644 Binary files a/PRESENTATION/img/algosnake-3etages.png and b/PRESENTATION/img/algosnake-3etages.png differ diff --git a/PRESENTATION/img/algosnake1.png b/PRESENTATION/img/algosnake1.png index 944d1e3..ef86662 100644 Binary files a/PRESENTATION/img/algosnake1.png and b/PRESENTATION/img/algosnake1.png differ diff --git a/PRESENTATION/img/approches.png b/PRESENTATION/img/approches.png index 6485f85..e4ec70d 100644 Binary files a/PRESENTATION/img/approches.png and b/PRESENTATION/img/approches.png differ diff --git a/PRESENTATION/img/barre-blanche.png b/PRESENTATION/img/barre-blanche.png new file mode 100644 index 0000000..33d9792 Binary files /dev/null and b/PRESENTATION/img/barre-blanche.png differ diff --git a/PRESENTATION/img/carreB.png b/PRESENTATION/img/carreB.png new file mode 100644 index 0000000..1d6a010 Binary files /dev/null and b/PRESENTATION/img/carreB.png differ diff --git a/PRESENTATION/img/halo.png b/PRESENTATION/img/halo.png new file mode 100644 index 0000000..b8b79a7 Binary files /dev/null and b/PRESENTATION/img/halo.png differ diff --git a/PRESENTATION/img/median5-overlap.png b/PRESENTATION/img/median5-overlap.png index 59d495a..d10dd8e 100644 Binary files a/PRESENTATION/img/median5-overlap.png and b/PRESENTATION/img/median5-overlap.png differ diff --git a/PRESENTATION/img/median_1.svg b/PRESENTATION/img/median_1.svg index 154efd5..8df5305 100644 --- a/PRESENTATION/img/median_1.svg +++ b/PRESENTATION/img/median_1.svg @@ -500,11 +500,48 @@ + id="filter8375-5-9-5"> + id="feGaussianBlur8377-0-4-7" /> + + + + + + + + + @@ -18713,5 +18750,1255 @@ id="tspan10727-6" x="320.10553" y="237.87029">Fenêtre d'évaluation + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + i + j + + + + pixel central - thread du bloc + pixel du halo diff --git a/PRESENTATION/img/perfs-snake-img.svg b/PRESENTATION/img/perfs-snake-img.svg index 35d441d..ba2f51c 100644 --- a/PRESENTATION/img/perfs-snake-img.svg +++ b/PRESENTATION/img/perfs-snake-img.svg @@ -45,34 +45,24 @@ showgrid="false" inkscape:zoom="0.22" inkscape:cx="2415.9462" - inkscape:cy="2888.9367" - inkscape:window-x="65" - inkscape:window-y="24" + inkscape:cy="1979.8458" + inkscape:window-x="139" + inkscape:window-y="156" inkscape:window-maximized="0" inkscape:current-layer="svg4803" /> - @@ -97,39 +87,24 @@ 100 Mpixels - Segments > 128 - 100 Mpixels - Segments >32 + x="1268.1036" + y="1208.5109" + style="font-size:32.46996307px" + id="tspan4880">100 Mpixels 100 Mpixels - Segments >32 + x="1783.6959" + y="1207.9243" + style="font-size:32.46996307px">100 Mpixels diff --git a/PRESENTATION/img/pipd-detail.svg b/PRESENTATION/img/pipd-detail.svg new file mode 100644 index 0000000..a56f46c --- /dev/null +++ b/PRESENTATION/img/pipd-detail.svg @@ -0,0 +1,930 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +(i,j) +(i1,j1) +IΘ(i1,j1) +IΣ(i1,j1) +validationGLRT + + \ No newline at end of file diff --git a/PRESENTATION/img/pipd-extension.png b/PRESENTATION/img/pipd-extension.png new file mode 100644 index 0000000..9c8ad5d Binary files /dev/null and b/PRESENTATION/img/pipd-extension.png differ diff --git a/PRESENTATION/img/seg2.png b/PRESENTATION/img/seg2.png new file mode 100644 index 0000000..51a8948 Binary files /dev/null and b/PRESENTATION/img/seg2.png differ diff --git a/PRESENTATION/img/shmem.png b/PRESENTATION/img/shmem.png index c7e3788..ce873db 100644 Binary files a/PRESENTATION/img/shmem.png and b/PRESENTATION/img/shmem.png differ diff --git a/PRESENTATION/img/snake_cpu_algo1.svg b/PRESENTATION/img/snake_cpu_algo1.svg index 5bae827..85a7805 100644 --- a/PRESENTATION/img/snake_cpu_algo1.svg +++ b/PRESENTATION/img/snake_cpu_algo1.svg @@ -98,15 +98,15 @@ objecttolerance="10" inkscape:pageopacity="0.0" inkscape:pageshadow="2" - inkscape:zoom="0.48083261" + inkscape:zoom="1.03" inkscape:cx="704.47765" inkscape:cy="552.11681" inkscape:document-units="px" inkscape:current-layer="layer1" inkscape:window-width="1299" inkscape:window-height="715" - inkscape:window-x="99" - inkscape:window-y="38" + inkscape:window-x="65" + inkscape:window-y="24" showgrid="false" inkscape:window-maximized="0" showguides="true" @@ -119,7 +119,7 @@ image/svg+xml - + @@ -435,7 +435,7 @@ pixels + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160" /> + inkscape:export-xdpi="160" + inkscape:export-ydpi="160"> Oui + diff --git a/PRESENTATION/img/transferts-mem.png b/PRESENTATION/img/transferts-mem.png index 5784b3a..3705635 100644 Binary files a/PRESENTATION/img/transferts-mem.png and b/PRESENTATION/img/transferts-mem.png differ diff --git a/PRESENTATION/index.html b/PRESENTATION/index.html index 91b91df..59e6efa 100644 --- a/PRESENTATION/index.html +++ b/PRESENTATION/index.html @@ -1 +1 @@ -Algorithmes rapides sur GPU

TRAITEMENT D'IMAGES SUR GPU

Algorithmes rapides pour le filtrage et la segmentation des images bruitées sur GPU.

Gilles Perrot

17 avril 2014

Université de Franche-Comté, Institut FEMTO-ST

Département DISC - équipe AND

Direction : R. Couturier & S. Domas

FILTRAGE

Réduire le bruit.

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

SEGMENTATION

Distinguer les zones homogènes d'une image.

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

SEGMENTATION

Deux approches

  • Pré-traiter et effectuer les traitements de haut niveau sur des images améliorées.
  • réduction, a priori, du coût des traitements de haut niveau.
  • les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.
  • Ne pas pré-traiter et effectuer les traitements de haut niveau sur les images bruitées.
    • pas de perte d'information due au pré-traitement.

PLAN DE LA PRÉSENTATION

  1. Introduction
    • Les GPUs ou Graphical Processing Units.
    • Le filtrage et la segmentation d'images.
  2. La segmentation des images
    • Travaux de référence.
    • Parallélisation GPU d'un algorithme de segmentation de type snake.
  3. Le filtrage des images
    • Travaux de référence.
    • Optimisation GPU des filtres médian et de convolution.
    • Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.
  4. Conclusion et perspectives

INTRODUCTION

Les GPUs ou Processeurs graphiques.

  • Processeurs classiques CPU : exécution séquentielle
    • Quelques unités de calcul ( les cœurs).
  • Processeurs graphiques GPU : exécution massivement parallèle
    • Des centaines, voire milliers, d'unités de calcul, regroupées en SMs (Streaming Multiprocessors).
  • La multiplication des cœurs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
  • Seule la mémoire globale est accessible par l'ensemble des fils d'exécution (les threads) et ses performances sont faibles.
  • AU sein de la RAM il y a différents canaux vers différents types de mémoires.
  • L'accès efficace aux mémoires est contraignant.
  • Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
  • Il est important de concevoir un partage équilibré des ressources au sein de chaque SM, pour permettre un niveau de parallélisme élevé, et donc d'envisager de bonnes performances.
  • La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.
  • L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
  • Les traitements envisagés sur les images sont de plus en plus évolués ( traitements de haut niveau ) et requièrent souvent un temps de calcul accru.
  • L'architecture parallèle particulière des GPUs a permis d'améliorer considérablement les performances de certaines classes d'algorithme et fait espérer par ailleurs des accélérations importantes.

INTRODUCTION

Le traitement des images

Le filtrage (du bruit)

  • Les capteurs et les conditions d'acquisition induisent du bruit.
  • Résolution élevée n'implique pas bruit réduit.

La segmentation

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

INTRODUCTION

Ojectif : accélérer

Segmentation

  • Algorithme par contours actifs, classe des snakes.
  • Implémentation CPU optimisée existante.
  • Conception de l'implémentation GPU.
  • Adaptations mineures de l'algorithme.

Filtrage

  • Filtre par lignes de niveaux
    • Algorithme original,
    • Conceptions conjointes algorithme et implémentation.
  • Filtres médians, filtres de convolution
    • Opérateurs mathématiques,
    • Conception d'une implémentation optimisée.

SEGMENTATION PAR CONTOUR ACTIF

Travaux de référence

Level-set ( Roberts et al., 2010)

  • Images d'IRM de 256x256x256 pixels (16 millions),
  • Temps sur GTX280 : 11 s.

Snake GVF (Smistad et al., 2012)

  • Images d'IRM de 256x256x256 pixels (16 millions),
  • Temps sur C2070 : 7 s.
  • Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
  • Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
  • Les algorithmes level-set sont les plus implémentés sur GPU :
  • Les algorithmes snakes sont très peu implémentée sur GPU :

SEGMENTATION PAR CONTOUR ACTIF

Snake polygonal orienté région (principe)

  • Objectif : déterminer le contour le plus vraisemblable.
  • 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]$$
  • Calcul des variances \(\sigma^2\) pour chaque contour :
  • Méthode de Chesnaud et el. (1999) en \(\mathcal{O}(n^2)\).
  • Implique le pré-calcul de 3 images cumulées.
  • Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple.

SEGMENTATION PAR CONTOUR ACTIF

Snake polygonal orienté région (algo CPU)

Itération 1

  1. Le contour initial est rectangulaire ( 4 nœuds )
  2. On déplace successivement les 4 nœuds jusqu'à ce que plus aucun nouveau déplacement ne provoque l'amélioration du critère.

SEGMENTATION PAR CONTOUR ACTIF

Snake polygonal orienté région (algo CPU)

  • CONVERGENCE RAPIDE

SEGMENTATION PAR CONTOUR ACTIF

Snake polygonal orienté région (algo CPU)

Exemples de résultats

  • Les résultats de segmentation dépendent des paramètres de la séquence d'optimisation (pas des déplacements, contour initial, seuil d'ajout des nœuds)

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

Identification des fonctions coûteuses

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

Calcul du critère GL

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

  • Pour un nœud et un pas de déplacement donnés, on évalue en parallèle 8 positions voisines, soit 16 segments distincts.
  • Pour éviter les oscillations et coller à l'algorithme séquentiel, on distingue les nœuds d'indices pairs et impairs.
  • On évalue en parallèle l'ensemble des déplacements éventuels de tous les nœuds de même parité.

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

  • 1 thread par pixel.
  • Concaténation de tous les pixels composant l'ensemble des contours évalués.
  • Réductions en mémoire partagée.
  • Une seule taille de segment : la taille du plus long.
  • les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

Points positifs :

  • Conservation des données en mémoire GPU.
  • Images cumulées calculées en parallèle.
  • Discretisation des segments en parallèle (1 thread/pixel).
  • Respect de l'algorithme original.

Points négatifs :

  • Trop peu de calculs à effectuer.
  • Motifs d'accès à la mémoire globale trop irréguliers.
  • Emploi de la mémoire partagée.
  • Un seul entier est échangé entre le CPU et le GPU à chaque itération.
  • image cumulées par une adaptation de la méthode des sommes de préfixes.
  • Abandon Bresenham Possible car parcours unidirectionnel du contour.
  • Trop peu de calculs ne permet pas de masquer les latences.
  • Pas de coalescence possible dans les accès à la mémoire globale car la géométrie des segments varie.
  • mémoire partagée à cause des réductions.

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

Performances de l'implémentation

SEGMENTATION PAR CONTOUR ACTIF

Parallélisation du Snake polygonal sur GPU

Conclusion

  • Première et seule implémentation à ce jour.
  • Performances intéressantes pour les grandes images.
  • Image 10000x10000 en moins de 0,6 seconde.
  • Emploi non optimal du GPU : réductions, irrégularités.
  • Premières itérations GPU rapides : grands segments.
  • Temps de calcul très dépendant du contenu de l'image :
    • Proposition d'une méthode d'initialisation alternative.
    • Recherche du contour rectangle le plus vraisemblable.
    • Accélération jusqu'à x15 avec de petites cibles.

LE FILTRAGE DES IMAGES

  • Filtre médian,
  • Filtres de convolution,
  • Filtre par recherche des lignes de niveaux (PIPD).

LE FILTRAGE DES IMAGES

Filtre médian : principe

La valeur de sortie d'un pixel est la médiane des valeurs de son voisinage.

  • Bonne réduction de bruits gaussien et poivre & sel
  • Valeurs de sortie appartenant au voisinage.
  • Opération de sélection coûteuse (tri).
  • Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).
  • Quelques applications avec de grandes fenêtres.

LE FILTRAGE DES IMAGES

Filtre médian : usage

Bruit poivre & sel 25%

Médian 5x5

Médian 3x3 - 2 passes

LE FILTRAGE DES IMAGES

Filtre médian GPU : Travaux de référence

Comparaison des implémentations GPU de référence :

  • PCMF, Sanchez et al. (2013), débit max. 80 MP/s,
  • ArrayFire, bibliothèque commerciale, débit max. 185 MP/s,
  • BVM parallélisé par Chen et al. (2009), débit max. 110 MP/s.
  • PCMF : Parallel (Complementary Cumulative Derivative Function) Median Filter (histogrammes cumulatifs)
  • CTMF : CPU à temps constant

LE FILTRAGE DES IMAGES

Filtre médian GPU : Travaux de référence

Emploi de la mémoire partagée (exemple médian 5x5)

  • recouvrement pose problème à cause accès concurrents à la mémoire partagée.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

On gagne de 13 à 43 % sur les temps de transfert.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Débits maximums effectifs, en MP/s, sur C2070.

Rappel : PCMF : 80 MP/s - BVM : 110 MP/s - ArrayFire : 185 MP/s

ça laisse environ 80ms pour faire un tri de 9 valeurs sur une image de 4096x4096

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Sélection de la médiane

  • Emploi exclusif des registres pour charger les valeurs utiles
    • mémoires individuelles au cœur du GPU,
    • non indexables dans un tableau.
    • maximum de 63 registres par thread et 32 K par bloc de threads.
  • Pour les petites tailles : max. 7x7 avec 1 pixel/thread.
  • Exploitation des recouvrements entre fenêtres voisines.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Sélection de la médiane (par oubli)

Avantages :

  • Évite le tri complet : performances en hausse,
  • Économie de registres : \(\lceil \frac{n}{2}\rceil +1\) au lieu de \(n\),
  • Permet de plus grandes tailles : max 11x11.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

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

À 4 pixels/thread, zone commune = 10 pixels < 14 : pas performant.

  • chaque thread utilise plus de registres
  • mais sur un bloc, en adaptant la taille du bloc, on économise k+1 registres par paire de pixels.

LE FILTRAGE DES IMAGES

Performances du médian GPU proposé (PRMF)

LE FILTRAGE DES IMAGES

Performances du filtre médian GPU proposé (PRMF)

Image 512x512

Image 4096x4096

  • débit décroit linéairement en fonction de n

LE FILTRAGE DES IMAGES

Le filtre médian GPU

Conclusion

  • Pas d'utilisation de la mémoire partagée.
  • Accès optimaux : 1 lecture par pixel.
  • Débit global amélioré de x7 à x10, proche du maximum.
  • Débit de calcul max. 5,3 GP/s.
  • Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.
  • Création d'une application web générant les codes sources.
  • Utilisé sur images de cristallographie au synchrotron SPring-8.

LE FILTRAGE DES IMAGES

Les filtres de convolution : généralités

Principe

$$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$

Selon les valeurs du masque h

  • Réduction de bruit, détection de bords,...
  • Opération séparable en deux convolutions 1D.

LE FILTRAGE DES IMAGES

Les filtres de convolution GPU

Exploitation des recouvrements :

  • un seul accès mémoire par pixel, mémorisation en registre.
  • Optimum à 8 pixels/thread :
  • Exemple médian 5x5, pour un thread :
    • 60 pixels dans le halo : 60 lectures.
    • 200 lectures + préchargement si utilisation mémoire partagée.

Nvidia propose les implémentations les plus rapides (séparable ou non) :

  • Traitement de référence : 2048x2048 pixels, 5x5, 8bits.

LE FILTRAGE DES IMAGES

Les filtres de convolution GPU

Résultats (suite)

Convolution séparable :

  • Une convolution verticale en mémoire partagée, suivie d'une convolution horizontale en registres.
  • Copie intermédiaire en mémoire globale (cache 1D rapide).
  • L'accélération est due à la seule convolution en registres (54%).

LE FILTRAGE DES IMAGES

Les filtres de convolution GPU

Conclusion

  • Amélioration sensible sur les débits de calcul (de 17 à 33 %).
  • Le traitement 1D est jusqu'à 54% plus rapide.
  • Application à d'autres familles de signaux 1D (audio,...).

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Motivations :

  • Les algorithmes qui débruitent le mieux sont lents (BM3D).
  • Les images naturelles sont décomposables en un ensemble de lignes de niveaux ( iso-niveau de gris ).
  • Concevoir un algorithme GPU original et son implémentation.

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Principe - modèle

  • Estimation locale, par maximum de vraisemblance, des lignes de niveaux.
  • Réduction de bruit par moyennage le long de la ligne estimée.
  • Les lignes de niveaux estimées sont modélisées par des lignes brisées nommées isolines.
  • Les segments des lignes brisées sont choisis parmi des motifs pré-établis (32 motifs).

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Principe (étape 1)

  • En chaque pixel, recherche du motif maximisant la log-vraisemblance ( \(n=6, \sigma^2 =\) variance )
$$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$
  • Mémorisation des paramètres des motifs sélectionnés dans deux matrices \(I_{\Theta}\) et \(I_{\Sigma}\).

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Principe (étape 2)

  • Allongement itératif des segments sous condition GLRT.
$$(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]$$

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Principe (étape 3)

Compensation de la non robustesse de sélection des motifs dans les zones homogènes.

  • identification des zones homogènes avec un détecteur de bords.
  • Application d'un filtre moyenneur dans ces zones.
  • Sous-ensembles de pixels n'ayant pas d'intersection --> MV
  • Utilisation des motifs des segments pour gain de temps.

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Résultats

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

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

Comparaison avec BM3D

  • Amélioration moyenne du rapport Signal sur bruit: +9,5 dB
  • Indice de similarité structurelle : +36%
  • Temps de calcul : 4300 ms

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Bruit gaussien \(\sigma=25\)

Moyennage 5x5

PI-PD

BM3D

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Synthèse - conclusion

  • Rapport qualité/temps élevé.
  • Traitement d'images HD à 20 fps.
  • Artefacts en marche d'escalier. Réduits par la méthode de Buades et al. (+1 dB, +0,2 ms pour 512x512).
  • Extension aux images couleurs et autres types de bruits (multiplicatif).
  • Algorithme original sans implémentation séquentielle de référence.

CONCLUSION GÉNÉRALE - PERSPECTIVES

  • Trois types de conception mis en œuvre.
  • Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt.
  • L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.
  • Filtres utilisables par tout programmeur grâce à un générateur de code.
  • Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées.
  • Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités.
  • certaines ardeurs ont été refroidies

ANNEXE

Parallélisation du Snake polygonal sur GPU

Structure des données (nœuds pairs)

  • règle 1 thread par pixel
SpaceForward
Left, Down, Page DownNext slide
Right, Up, Page UpPrevious slide
POpen presenter console
HToggle this help
\ No newline at end of file +Algorithmes rapides sur GPU

TRAITEMENT D'IMAGES SUR GPU

Algorithmes rapides pour le filtrage et la segmentation des images bruitées sur GPU.

Gilles Perrot

17 avril 2014

Université de Franche-Comté, Institut FEMTO-ST

Département DISC - équipe AND

Direction : R. Couturier & S. Domas

FILTRAGE

Réduire le bruit.

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

SEGMENTATION

Distinguer les zones statistiquement homogènes d'une image bruitée.

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

SEGMENTATION

Deux approches

PLAN DE LA PRÉSENTATION

  1. Introduction
    • Les GPUs ou Graphical Processing Units.
    • Objectifs.
  2. La segmentation des images
    • Travaux de référence.
    • Parallélisation GPU d'un algorithme de segmentation de type snake.
  3. Le filtrage des images
    • Travaux de référence.
    • Optimisation GPU des filtres médian et de convolution.
    • Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.
  4. Conclusion et perspectives

INTRODUCTION

Les GPUs ou Processeurs graphiques.

  • Processeurs classiques CPU : exécution séquentielle
    • Quelques unités de calcul ( les cœurs).
  • Processeurs graphiques GPU : exécution massivement parallèle
    • Des centaines, voire milliers, d'unités de calcul, regroupées en SMs (Streaming Multiprocessors).
  • La multiplication des cœurs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
  • Seule la mémoire globale est accessible par l'ensemble des fils d'exécution (les threads) et ses performances sont faibles.
  • AU sein de la RAM il y a différents canaux vers différents types de mémoires.
  • L'accès efficace aux mémoires est contraignant.
  • Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
  • Il est important de concevoir un partage équilibré des ressources au sein de chaque SM, pour permettre un niveau de parallélisme élevé, et donc d'envisager de bonnes performances.
  • La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.
  • L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
  • Les traitements envisagés sur les images sont de plus en plus évolués ( traitements de haut niveau ) et requièrent souvent un temps de calcul accru.
  • L'architecture parallèle particulière des GPUs a permis d'améliorer considérablement les performances de certaines classes d'algorithme et fait espérer par ailleurs des accélérations importantes.

INTRODUCTION

Ojectif : accélérer

Segmentation

  • Algorithme par contours actifs, classe des snakes.
  • Implémentation CPU optimisée existante.
  • Conception de l'implémentation GPU.

Filtrage

  • Filtres médians, filtres de convolution
    • Opérateurs mathématiques,
    • Conception d'une implémentation optimisée.
  • Filtre par lignes de niveaux
    • Conception d'un algorithme dédié GPU.

SEGMENTATION

Travaux de référence

Level-set ( Roberts et al., 2010)

  • Images d'IRM de 256x256x256 pixels (16 millions),
  • Temps sur GTX280 : 11 s.

Snake GVF (Smistad et al., 2012)

  • Images d'IRM de 256x256x256 pixels (16 millions),
  • Temps sur C2070 : 7 s.
  • Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
  • Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
  • Les algorithmes level-set sont les plus implémentés sur GPU :
  • Les algorithmes snakes sont très peu implémentée sur GPU :

SEGMENTATION

Snake polygonal orienté région (principe)

  • Objectif : déterminer le contour le plus vraisemblable.
  • 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]$$
  • Calcul des variances \(\sigma^2\) pour chaque contour :
  • Méthode de Chesnaud et al. (1999) : sommes sur le contour.
  • Implique le pré-calcul de 3 images cumulées.
  • Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple.

SEGMENTATION

Snake polygonal orienté région (algo CPU)

  1. Le contour initial est rectangulaire ( 4 nœuds )
  2. On déplace successivement les 4 nœuds jusqu'à ce que plus aucun nouveau déplacement ne provoque l'amélioration du critère.

SEGMENTATION

Snake polygonal orienté région (algo CPU)

  • CONVERGENCE RAPIDE

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

Identification des fonctions coûteuses

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

Calcul du critère GL (1 pixel/thread)

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

  • Pour un nœud et un pas de déplacement donnés, on évalue en parallèle 8 positions voisines, soit 16 segments distincts.
  • Pour éviter les oscillations et coller à l'algorithme séquentiel, on distingue les nœuds d'indices pairs et impairs.
  • On évalue en parallèle l'ensemble des déplacements éventuels de tous les nœuds de même parité.

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

  • 1 thread par pixel.
  • Concaténation dans un vecteur de tous les pixels composant l'ensemble des contours évalués.
    • ex : 2x 256000 éléments à l'étape 1 de l'image 100 MP.
  • Sommes des contributions des pixels : opérations de réduction.
    • opérations mal adaptées à l'architecture GPU,
    • en mémoire partagée : accélération par rapport au CPU.
  • les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

Points positifs :

  • Conservation des données en mémoire GPU.
  • Images cumulées (pré-calculs) effectuées en parallèle.
  • Discrétisation des segments en parallèle (1 thread/pixel).
  • Respect de l'algorithme original.

Points négatifs :

  • Trop peu de calculs à effectuer.
  • Segments de tailles et orientations variables :
    • motifs d'accès à la mémoire globale irréguliers,
    • nombreux threads inactifs.
  • Un seul entier est échangé entre le CPU et le GPU à chaque itération.
  • image cumulées par une adaptation de la méthode des sommes de préfixes.
  • Abandon Bresenham Possible car parcours unidirectionnel du contour.
  • Trop peu de calculs ne permet pas de masquer les latences.
  • Pas de coalescence possible dans les accès à la mémoire globale car la géométrie des segments varie.
  • mémoire partagée à cause des réductions.

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

Performances de l'implémentation

SEGMENTATION

Parallélisation du Snake polygonal sur GPU

Conclusion

  • Première et seule implémentation connue à ce jour.
  • Performances intéressantes pour les grandes images.
  • Image 10000x10000 en moins de 0,6 seconde.
  • Emploi non optimal du GPU : réductions, irrégularités.
  • Temps de calcul très dépendant du contenu de l'image.
  • Proposition d'une méthode d'initialisation alternative :
    • Recherche du contour rectangle le plus vraisemblable.
    • Accélération jusqu'à x15 avec de petites cibles.

Publication

  • G. Perrot, S. Domas, R. Couturier, and N. Bertaux. Gpu implementation of a region based algorithm for large images segmentation. In Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on, pages 291–298.

LE FILTRAGE DES IMAGES

  • Filtre médian,
  • Filtres de convolution,
  • Filtre par recherche des lignes de niveaux.

LE FILTRAGE DES IMAGES

Filtre médian : principe

La valeur de sortie d'un pixel est la médiane des valeurs de son voisinage.

  • Bonne réduction du bruit poivre & sel.
  • Assez bonne préservation des contours.
  • Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).
  • Quelques applications avec de grandes fenêtres.
  • Opération de sélection coûteuse (tri).

LE FILTRAGE DES IMAGES

Filtre médian : exemple

Bruit poivre & sel 25%

Médian 5x5

LE FILTRAGE DES IMAGES

Filtre médian GPU : travaux de référence

Comparaison des implémentations GPU de référence :

  • PCMF, Sanchez et al. (2013), débit max. 80 MP/s,
  • ArrayFire, commerciale (2013), débit max. 185 MP/s,
  • BVM parallélisé par Chen et al. (2009), débit max. 110 MP/s.
  • PCMF : Parallel (Complementary Cumulative Derivative Function) Median Filter (histogrammes cumulatifs)
  • CTMF : CPU à temps constant

LE FILTRAGE DES IMAGES

Filtre médian GPU : Travaux de référence

Emploi de la mémoire partagée (exemple médian 5x5)

  • recouvrement pose problème à cause accès concurrents à la mémoire partagée.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

On gagne de 13 à 43 % sur les temps de transfert.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Débits maximums effectifs, en MP/s, sur C2070.

Rappel : PCMF : 80 MP/s - BVM : 110 MP/s - ArrayFire : 185 MP/s

ça laisse environ 80ms pour faire un tri de 9 valeurs sur une image de 4096x4096

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Sélection de la médiane

  • Emploi exclusif des registres pour charger les valeurs utiles
    • mémoires individuelles au cœur du GPU,
    • non indexables dans un tableau.
    • maximum de 63 registres par thread et 32 K par bloc de threads.
  • Pour les petites tailles : max. 7x7 avec 1 pixel/thread.
  • Exploitation des recouvrements entre fenêtres voisines.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

Sélection de la médiane (par oubli)

Avantages :

  • Évite le tri complet : performances en hausse,
  • Économie de registres : \(\lceil \frac{n}{2}\rceil +1\) au lieu de \(n\),
  • Permet de plus grandes tailles : max 11x11.

LE FILTRAGE DES IMAGES

Optimisation du filtre médian GPU

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

  • 7+2x5 = 17 étapes de sélection au lieu de 2x12 = 24.
  • Les plus coûteuses sont communes.
  • À 4 pixels/thread, zone commune = 10 pixels < 14.
  • chaque thread utilise plus de registres
  • mais sur un bloc, en adaptant la taille du bloc, on économise k+1 registres par paire de pixels.

LE FILTRAGE DES IMAGES

Performances du médian GPU proposé (PRMF)

Rappels :

  • débit crête de la plateforme = 2444 MP/s.
  • débit maximum des implémentations de référence = 185 MP/s.

LE FILTRAGE DES IMAGES

Performances du filtre médian GPU proposé (PRMF)

Image 512x512

Image 4096x4096

  • débit décroit linéairement en fonction de n

LE FILTRAGE DES IMAGES

Le filtre médian GPU

Conclusion

  • Pas d'utilisation de la mémoire partagée.
  • Accès optimaux : 1 lecture par pixel.
  • Débit global amélioré de x7 à x10, proche du maximum.
  • Débit de calcul max. 5,3 GP/s.
  • Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.
  • Création d'une application web générant les codes sources.
  • Utilisé sur images de cristallographie au synchrotron SPring-8.

Publications

  • Gilles Perrot. Image processing. In Designing Scientific Applications on GPUs, pages 28-70. CRC Press, 2013.
  • Gilles Perrot, Stéphane Domas, and Raphaël Couturier. Fine-tuned high-speed implementation of a gpu-based median filter. Journal of Signal Processing Systems, pages 1–6, 2013.

LE FILTRAGE DES IMAGES

Les filtres de convolution

Principe

$$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$

Selon les valeurs du masque h

  • Réduction de bruit, détection de bords,...
  • Potentiellement séparable en deux convolutions 1D.

LE FILTRAGE DES IMAGES

Les filtres de convolution GPU

Extension des méthodes appliquées au filtre médian :

  • Un seul accès mémoire par pixel.
  • Mémorisation et calculs en registre.
  • Optimum à 8 pixels/thread.

Implémentations de référence (C2070) :

  • Nvidia atteint un débit de calcul maximum de 6,00 GP/s.

LE FILTRAGE DES IMAGES

Les filtres de convolution GPU

Résultats

  • Amélioration sensible des débits de calcul en 2D : 16 à 35 %.
  • Débit de la convolution 1D horizontale jusqu'à 54% plus élevé.
  • Débit maximum de 8,54 GP/s.
  • Application à d'autres familles de signaux 1D (audio,...).

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Motivations :

  • Les algorithmes qui débruitent le mieux sont lents (BM3D).
  • Les images naturelles sont décomposables en un ensemble de lignes de niveaux ( iso-niveau de gris ).
  • Concevoir un algorithme GPU original et son implémentation.

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Principe - modèle

  • Estimation locale, par maximum de vraisemblance.
  • Réduction de bruit par moyennage le long de la ligne estimée.
  • Modèle de ligne de niveaux retenu : isoline

    = ligne brisée composée de segments.

  • Segments choisis parmi 32 motifs pré-calculés.
  • Les 8 premiers motifs pour des segments de 6 pixels :

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Étape 1 (1 pixel/thread)

  • En chaque pixel, recherche du motif maximisant la log-vraisemblance ( exemple \(n=6\))
$$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$
  • Mémorisation des paramètres du motif sélectionné dans deux matrices \(I_{\Theta}\) (indice) et \(I_{\Sigma}\) (moyenne, variance).

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Étape 2 (1 pixel/thread)

  • Isoline validée de \(n_{prec}\) pixels.
  • Segment candidat de \(n_s\) pixels.
  • Allongement de l'isoline sous condition GLRT ?
$$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]$$

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Étape 3 (optionnelle)

Compensation de la non robustesse de sélection des motifs dans les zones homogènes.

  • Conception d'un détecteur de zones homogènes.
  • Identification des zones homogènes avec ce détecteur.
  • Application d'un filtre moyenneur dans les zones identifiées comme homogènes (convolution).
  • Sous-ensembles de pixels n'ayant pas d'intersection --> MV
  • Utilisation des motifs des segments pour gain de temps.

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Résultats

Ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD)

  • Amélioration moyenne du rapport Signal sur bruit: +7,1 dB,
  • Indice de similarité structurelle : +30%,
  • Temps de calcul (C2070, avec détecteur) : 7 ms.

Algorithme de référence BM3D

  • Amélioration moyenne du rapport Signal sur bruit: +9,5 dB,
  • Indice de similarité structurelle : +36%,
  • Temps de calcul : 4300 ms.
  • 2,4 dB d'écart, soit réduction de 43% de la puissance de bruit

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Bruit gaussien \(\sigma=25\)

Moyennage 5x5

PI-PD

BM3D

LE FILTRAGE DES IMAGES

Filtre par recherche des lignes de niveaux

Synthèse - conclusion

  • Rapport qualité/temps élevé.
  • Traitement d'images HD à 20 fps.
  • Artefacts en marche d'escalier.
  • Parallélisation de la méthode de Buades et al. (2006) :
    • gain +1 dB en +0,2 ms pour 512x512.
  • Algorithme dédié GPU, sans implémentation séquentielle de référence.

Publication

  • Gilles Perrot, Stéphane Domas, Raphaël Couturier, and Nicolas Bertaux. Fast gpu-based denoising filter using isoline levels. Journal of Real-Time Image Processing, pages 1–12, 2013.

CONCLUSION GÉNÉRALE

  • Trois types de conception mis en œuvre :
    • Parallélisation GPU d'une implémentation CPU (snake).
    • Implémentations optimisées pour GPU d'opérateurs mathématiques (médian, convolution).
    • Algorithme dédié GPU et son implémentation (isolines).
  • Le portage efficace d'algorithme sur GPU s'avère très complexe.
  • Certains algorithmes ne se prêtent pas à la parallélisation GPU.
  • L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.
  • Filtrage à des débits inégalés, proches des performances crête.
  • Filtres utilisables par tout programmeur grâce au générateur de code.

PERSPECTIVES

  • Extension des filtres aux images couleurs et autres types de bruits (multiplicatif).
  • Extension aux pseudo-médians de grandes tailles (microscopie).
  • Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées (audio, imagerie 3D, BM3D).
  • Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités (parallélisme dynamique, kernels concurrents).
  • certaines ardeurs ont été refroidies

ANNEXE 1

Parallélisation du Snake polygonal sur GPU

Structure des données (nœuds pairs)

  • règle 1 thread par pixel

ANNEXE 2 (médian)

Image cristallographie SPring-8

ANNEXE 3 (lniv)

Détecteur de bords

SpaceForward
Left, Down, Page DownNext slide
Right, Up, Page UpPrevious slide
POpen presenter console
HToggle this help
\ No newline at end of file diff --git a/p1.pdf b/p1.pdf new file mode 100644 index 0000000..45d27ac Binary files /dev/null and b/p1.pdf differ diff --git a/p10.pdf b/p10.pdf new file mode 100644 index 0000000..4a055d9 Binary files /dev/null and b/p10.pdf differ diff --git a/p11.pdf b/p11.pdf new file mode 100644 index 0000000..0c695ae Binary files /dev/null and b/p11.pdf differ diff --git a/p12.pdf b/p12.pdf new file mode 100644 index 0000000..4459eba Binary files /dev/null and b/p12.pdf differ diff --git a/p13.pdf b/p13.pdf new file mode 100644 index 0000000..9edc8e6 Binary files /dev/null and b/p13.pdf differ diff --git a/p14.pdf b/p14.pdf new file mode 100644 index 0000000..75995d5 Binary files /dev/null and b/p14.pdf differ diff --git a/p15.pdf b/p15.pdf new file mode 100644 index 0000000..746509f Binary files /dev/null and b/p15.pdf differ diff --git a/p16.pdf b/p16.pdf new file mode 100644 index 0000000..3230c87 Binary files /dev/null and b/p16.pdf differ diff --git a/p17.pdf b/p17.pdf new file mode 100644 index 0000000..e651d01 Binary files /dev/null and b/p17.pdf differ diff --git a/p18.pdf b/p18.pdf new file mode 100644 index 0000000..4442fe2 Binary files /dev/null and b/p18.pdf differ diff --git a/p19.pdf b/p19.pdf new file mode 100644 index 0000000..2bedc93 Binary files /dev/null and b/p19.pdf differ diff --git a/p2.pdf b/p2.pdf new file mode 100644 index 0000000..69e2869 Binary files /dev/null and b/p2.pdf differ diff --git a/p20.pdf b/p20.pdf new file mode 100644 index 0000000..aa512c1 Binary files /dev/null and b/p20.pdf differ diff --git a/p21.pdf b/p21.pdf new file mode 100644 index 0000000..412c972 Binary files /dev/null and b/p21.pdf differ diff --git a/p22.pdf b/p22.pdf new file mode 100644 index 0000000..efbed9d Binary files /dev/null and b/p22.pdf differ diff --git a/p23.pdf b/p23.pdf new file mode 100644 index 0000000..82eac68 Binary files /dev/null and b/p23.pdf differ diff --git a/p24.pdf b/p24.pdf new file mode 100644 index 0000000..6a7df6a Binary files /dev/null and b/p24.pdf differ diff --git a/p25.pdf b/p25.pdf new file mode 100644 index 0000000..58b0afc Binary files /dev/null and b/p25.pdf differ diff --git a/p26.pdf b/p26.pdf new file mode 100644 index 0000000..aa67870 Binary files /dev/null and b/p26.pdf differ diff --git a/p27.pdf b/p27.pdf new file mode 100644 index 0000000..b1f8e32 Binary files /dev/null and b/p27.pdf differ diff --git a/p28.pdf b/p28.pdf new file mode 100644 index 0000000..1f0b36c Binary files /dev/null and b/p28.pdf differ diff --git a/p29.pdf b/p29.pdf new file mode 100644 index 0000000..d417f8c Binary files /dev/null and b/p29.pdf differ diff --git a/p3.pdf b/p3.pdf new file mode 100644 index 0000000..5a08088 Binary files /dev/null and b/p3.pdf differ diff --git a/p30.pdf b/p30.pdf new file mode 100644 index 0000000..9732260 Binary files /dev/null and b/p30.pdf differ diff --git a/p31.pdf b/p31.pdf new file mode 100644 index 0000000..a2da435 Binary files /dev/null and b/p31.pdf differ diff --git a/p32.pdf b/p32.pdf new file mode 100644 index 0000000..1f0f52d Binary files /dev/null and b/p32.pdf differ diff --git a/p33.pdf b/p33.pdf new file mode 100644 index 0000000..62a1f14 Binary files /dev/null and b/p33.pdf differ diff --git a/p34.pdf b/p34.pdf new file mode 100644 index 0000000..41e706e Binary files /dev/null and b/p34.pdf differ diff --git a/p35.pdf b/p35.pdf new file mode 100644 index 0000000..ca80fa2 Binary files /dev/null and b/p35.pdf differ diff --git a/p36.pdf b/p36.pdf new file mode 100644 index 0000000..267ac0d Binary files /dev/null and b/p36.pdf differ diff --git a/p37.pdf b/p37.pdf new file mode 100644 index 0000000..efc56dd Binary files /dev/null and b/p37.pdf differ diff --git a/p38.pdf b/p38.pdf new file mode 100644 index 0000000..5099171 Binary files /dev/null and b/p38.pdf differ diff --git a/p39.pdf b/p39.pdf new file mode 100644 index 0000000..a77caac Binary files /dev/null and b/p39.pdf differ diff --git a/p4.pdf b/p4.pdf new file mode 100644 index 0000000..8d053e8 Binary files /dev/null and b/p4.pdf differ diff --git a/p40.pdf b/p40.pdf new file mode 100644 index 0000000..b99f8b6 Binary files /dev/null and b/p40.pdf differ diff --git a/p41.pdf b/p41.pdf new file mode 100644 index 0000000..902bcd4 Binary files /dev/null and b/p41.pdf differ diff --git a/p42.pdf b/p42.pdf new file mode 100644 index 0000000..d8871be Binary files /dev/null and b/p42.pdf differ diff --git a/p43.pdf b/p43.pdf new file mode 100644 index 0000000..8ce2344 Binary files /dev/null and b/p43.pdf differ diff --git a/p44.pdf b/p44.pdf new file mode 100644 index 0000000..8fd825c Binary files /dev/null and b/p44.pdf differ diff --git a/p45.pdf b/p45.pdf new file mode 100644 index 0000000..e3f21fc Binary files /dev/null and b/p45.pdf differ diff --git a/p5.pdf b/p5.pdf new file mode 100644 index 0000000..6956217 Binary files /dev/null and b/p5.pdf differ diff --git a/p6.pdf b/p6.pdf new file mode 100644 index 0000000..2da9268 Binary files /dev/null and b/p6.pdf differ diff --git a/p7.pdf b/p7.pdf new file mode 100644 index 0000000..10309f9 Binary files /dev/null and b/p7.pdf differ diff --git a/p8.pdf b/p8.pdf new file mode 100644 index 0000000..38e5be0 Binary files /dev/null and b/p8.pdf differ diff --git a/p9.pdf b/p9.pdf new file mode 100644 index 0000000..7ca179c Binary files /dev/null and b/p9.pdf differ diff --git a/presentation-pdf.pdf b/presentation-pdf.pdf new file mode 100644 index 0000000..07ee5f1 Binary files /dev/null and b/presentation-pdf.pdf differ