1 :title: Algorithmes rapides sur GPU
5 # boite arrondie fond gris
22 * - * kjh kj hkjh kqj hdkq jdhq lkj lj lkj lkj lj lqks,jxdxqdiqoioqiij
23 * jkkjskdjf lskfj lskfjlksdjfls
24 - .. image:: css/logo-femto.png
32 TRAITEMENT D'IMAGES SUR GPU
33 ===========================
35 Algorithmes rapides pour le filtrage et la segmentation des images bruitées sur GPU.
36 ------------------------------------------------------------------------------------------------
42 Université de Franche-Comté, Institut FEMTO-ST
43 +++++++++++++++++++++++++++++++++++++++++++++++
44 Département DISC - équipe AND
45 +++++++++++++++++++++++++++++
46 Direction : R. Couturier & S. Domas
47 ++++++++++++++++++++++++++++++++++++
56 .. image:: img/ex-filtrage.png
61 * les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.
62 * Les capteurs numériques et les conditions d'acquisition sont à l'origine de perturbations (bruits).
63 * Les hautes résolutions sont souvent obtenues à faible flux de photons, dont les variations engendrent du bruit.
70 Distinguer les zones statistiquement homogènes d'une image bruitée.
72 .. image:: img/seg2.png
77 * on recense plus de 4000 algorithmes de segmentation
78 * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
79 * 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.
88 .. image:: img/approches.png
93 PLAN DE LA PRÉSENTATION
94 =======================
98 - Les GPUs ou *Graphical Processing Units*.
101 #. La segmentation des images
103 - Travaux de référence.
104 - Parallélisation GPU d'un algorithme de segmentation de type *snake*.
106 #. Le filtrage des images
108 - Travaux de référence.
109 - Optimisation GPU des filtres médian et de convolution.
110 - Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.
112 #. Conclusion et perspectives
118 Les GPUs ou *Processeurs graphiques*.
119 -------------------------------------
121 .. image:: img/gpucpu1.png
125 * Processeurs *classiques* **CPU** : exécution **séquentielle**
127 - Quelques unités de calcul ( les c |oe| urs).
129 * Processeurs *graphiques* **GPU** : exécution **massivement parallèle**
131 - Des centaines, voire milliers, d'unités de calcul, regroupées en SMs (*Streaming Multiprocessors*).
135 * La multiplication des c |oe| urs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
136 * Seule la mémoire *globale* est accessible par l'ensemble des fils d'exécution (les *threads*) et ses performances sont faibles.
137 * AU sein de la RAM il y a différents canaux vers différents types de mémoires.
138 * L'accès efficace aux mémoires est contraignant.
139 * Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
140 * 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.
141 * La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.
143 * L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
144 * 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.
145 * 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.
158 * Algorithme par contours actifs, classe des *snakes*.
159 * Implémentation CPU optimisée existante.
160 * Conception de l'implémentation GPU.
164 * Filtres médians, filtres de convolution
166 - Opérateurs mathématiques,
167 - Conception d'une implémentation optimisée.
169 * Filtre par lignes de niveaux
171 - Conception d'un algorithme dédié GPU.
181 **Level-set** ( Roberts *et al.*, 2010)
183 * Images d'IRM de 256x256x256 pixels (16 millions),
184 * Temps sur GTX280 : **11 s**.
186 **Snake GVF** (Smistad *et al.*, 2012)
188 * Images d'IRM de 256x256x256 pixels (16 millions),
189 * Temps sur C2070 : **7 s**.
191 .. figure:: img/brain3D-gvf.png
198 * Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
199 * Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
200 * Les algorithmes **level-set** sont les plus implémentés sur GPU :
201 * Les algorithmes **snakes** sont très peu implémentée sur GPU :
206 ===============================
207 *Snake* polygonal orienté région (principe)
208 -------------------------------------------
216 * - .. image:: img/snake-modele.png
218 - * Objectif : déterminer le contour le plus *vraisemblable*.
219 * Le critère de vraisemblance généralisée est, dans le cas gaussien :
223 $$GL = \frac{1}{2}\left[ n_B.log\left(\sigma_B^2\right) + n_T.log\left(\sigma_T^2\right)\right]$$
225 * Calcul des variances :math:`\(\sigma^2\)` pour chaque contour :
227 * Méthode de Chesnaud *et al.* (1999) : sommes sur le **contour**.
228 * Implique le **pré-calcul** de 3 images cumulées.
232 * Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple.
237 ===============================
238 *Snake* polygonal orienté région (algo CPU)
239 --------------------------------------------
241 .. image:: img/cochons-it0-it1.png
245 #. Le contour initial est rectangulaire ( 4 n |oe| uds )
246 #. 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.
252 ===============================
253 *Snake* polygonal orienté région (algo CPU)
254 --------------------------------------------
256 .. image:: img/cochons-it21-it22.png
259 .. image:: img/barre-blanche.png
262 .. image:: img/cochons-it4-it5.png
273 ===============================
274 Parallélisation du *Snake* polygonal sur GPU
275 --------------------------------------------
276 Identification des fonctions coûteuses
278 .. image:: img/algosnake1.png
284 ===============================
285 Parallélisation du *Snake* polygonal sur GPU
286 --------------------------------------------
287 Calcul du critère GL (1 pixel/thread)
289 .. image:: img/algosnake-3etages.png
296 ===============================
297 Parallélisation du *Snake* polygonal sur GPU
298 --------------------------------------------
300 .. image:: img/snake-pairimpair.png
305 * Pour un n |oe| ud et un pas de déplacement donnés, on évalue **en parallèle** 8 positions voisines, soit 16 segments distincts.
306 * Pour éviter les oscillations et *coller* à l'algorithme séquentiel, on distingue les n |oe| uds d'indices pairs et impairs.
307 * On évalue **en parallèle** l'ensemble des déplacements éventuels de tous les n |oe| uds de même parité.
314 ===============================
315 Parallélisation du *Snake* polygonal sur GPU
316 --------------------------------------------
318 * 1 thread par pixel.
319 * Concaténation dans un vecteur de tous les pixels composant l'ensemble des contours évalués.
321 - ex : 2x 256000 éléments à l'étape 1 de l'image 100 MP.
323 * Sommes des contributions des pixels : opérations de **réduction**.
325 - opérations mal adaptées à l'architecture GPU,
326 - en mémoire partagée : accélération par rapport au CPU.
330 * les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1
335 ===============================
336 Parallélisation du *Snake* polygonal sur GPU
337 --------------------------------------------
341 * Conservation des données en mémoire GPU.
342 * Images cumulées (pré-calculs) effectuées en parallèle.
343 * Discrétisation des segments en parallèle (1 thread/pixel).
344 * Respect de l'algorithme original.
348 * Trop peu de calculs à effectuer.
349 * Segments de tailles et orientations variables :
351 - motifs d'accès à la mémoire globale irréguliers,
352 - nombreux threads inactifs.
356 * Un seul entier est échangé entre le CPU et le GPU à chaque itération.
357 * image cumulées par une adaptation de la méthode des sommes de préfixes.
358 * Abandon Bresenham Possible car parcours unidirectionnel du contour.
359 * Trop peu de calculs ne permet pas de masquer les latences.
360 * Pas de coalescence possible dans les accès à la mémoire globale car la géométrie des segments varie.
361 * mémoire partagée à cause des réductions.
366 ===============================
367 Parallélisation du *Snake* polygonal sur GPU
368 --------------------------------------------
370 **Performances de l'implémentation**
372 .. image:: img/perfs-snake.png
377 .. image:: img/perfs-snake-img.png
383 ===============================
384 Parallélisation du *Snake* polygonal sur GPU
385 --------------------------------------------
389 * Première et seule implémentation connue à ce jour.
390 * Performances intéressantes pour les grandes images.
391 * Image 10000x10000 en moins de 0,6 seconde.
392 * Emploi non optimal du GPU : réductions, irrégularités.
393 * Temps de calcul très dépendant du contenu de l'image.
394 * Proposition d'une méthode d'initialisation alternative :
396 - Recherche du contour rectangle le plus vraisemblable.
397 - Accélération jusqu'à x15 avec de petites cibles.
401 * *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.*
405 LE FILTRAGE DES IMAGES
406 ======================
409 * Filtres de convolution,
410 * Filtre par recherche des lignes de niveaux.
414 LE FILTRAGE DES IMAGES
415 ======================
416 Filtre médian : principe
417 ------------------------
419 .. image:: img/median-principe.png
422 La valeur de sortie d'un pixel est la **médiane** des valeurs de son voisinage.
424 * Bonne réduction du bruit *poivre & sel*.
425 * Assez bonne préservation des contours.
426 * Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).
427 * Quelques applications avec de grandes fenêtres.
428 * Opération de sélection coûteuse (tri).
432 LE FILTRAGE DES IMAGES
433 ======================
434 Filtre médian : exemple
435 -----------------------
439 =================================== ========================================
440 .. image:: img/airplane_sap25.png .. image:: img/airplane_sap25_med5.png
441 =================================== ========================================
442 Bruit *poivre & sel* 25% Médian 5x5
443 =================================== ========================================
447 LE FILTRAGE DES IMAGES
448 ======================
449 Filtre médian GPU : travaux de référence
450 ----------------------------------------
452 Comparaison des implémentations GPU de référence :
454 - **PCMF**, Sanchez *et al.* (2013), débit max. **80 MP/s**,
455 - **ArrayFire**, commerciale (2013), débit max. **185 MP/s**,
456 - **BVM** parallélisé par Chen *et al.* (2009), débit max. **110 MP/s**.
458 .. image:: img/compar-median2.png
463 * PCMF : Parallel (Complementary Cumulative Derivative Function) Median Filter (histogrammes cumulatifs)
464 * CTMF : CPU à temps constant
468 LE FILTRAGE DES IMAGES
469 ======================
470 Filtre médian GPU : Travaux de référence
471 ----------------------------------------
473 Emploi de la **mémoire partagée** (exemple médian 5x5)
477 =================================== ========================== ========================================
478 .. image:: img/shmem.png .. image:: img/carreB.png .. image:: img/halo.png
479 =================================== ========================== ========================================
484 - recouvrement pose problème à cause accès concurrents à la mémoire partagée.
488 LE FILTRAGE DES IMAGES
489 ======================
490 Optimisation du filtre médian GPU
491 ---------------------------------
493 .. image:: img/CPU-GPU-memcpy.png
496 .. image:: img/transferts-mem.png
501 On gagne de 13 à 43 % sur les temps de transfert.
505 LE FILTRAGE DES IMAGES
506 ======================
507 Optimisation du filtre médian GPU
508 ---------------------------------
511 .. image:: img/CPU-GPU-memcpy-dummykernel.png
515 Débits maximums effectifs, en MP/s, sur C2070.
517 .. image:: img/debit-max-2070.png
520 **Rappel :** PCMF : 80 MP/s - BVM : 110 MP/s - ArrayFire : 185 MP/s
524 ça laisse environ 80ms pour faire un tri de 9 valeurs sur une image de 4096x4096
528 LE FILTRAGE DES IMAGES
529 ======================
530 Optimisation du filtre médian GPU
531 ---------------------------------
533 **Sélection de la médiane**
535 * Emploi exclusif des **registres** pour charger les valeurs utiles
537 - mémoires individuelles au c |oe| ur du GPU,
538 - non indexables dans un tableau.
539 - maximum de 63 registres par thread et 32 K par bloc de threads.
541 * Pour les petites tailles : max. 7x7 avec 1 pixel/thread.
542 * Exploitation des recouvrements entre fenêtres voisines.
547 LE FILTRAGE DES IMAGES
548 ======================
549 Optimisation du filtre médian GPU
550 ---------------------------------
552 **Sélection de la médiane** (par oubli)
562 * Évite le tri complet : performances en hausse,
563 * Économie de registres : :math:`\(\lceil \frac{n}{2}\rceil +1\)` au lieu de :math:`\(n\)`,
564 * Permet de plus grandes tailles : max 11x11.
566 - .. image:: img/forgetful_selection.png
571 LE FILTRAGE DES IMAGES
572 ======================
573 Optimisation du filtre médian GPU
574 ---------------------------------
576 **Exploitation des recouvrements** : 2 pixels par thread (médian 5x5).
578 .. image:: img/recouvrement5.png
581 * **7+2x5 = 17** étapes de sélection au lieu de **2x12 = 24**.
582 * Les plus coûteuses sont communes.
583 * À 4 pixels/thread, zone commune = 10 pixels < 14.
587 * chaque thread utilise plus de registres
588 * mais sur un bloc, en adaptant la taille du bloc, on économise k+1 registres par paire de pixels.
592 LE FILTRAGE DES IMAGES
593 ======================
594 Performances du médian GPU proposé (PRMF)
595 ------------------------------------------------
597 .. image:: img/perf-median.png
602 - débit crête de la plateforme = 2444 MP/s.
603 - débit maximum des implémentations de référence = 185 MP/s.
607 LE FILTRAGE DES IMAGES
608 ======================
609 Performances du filtre médian GPU proposé (PRMF)
610 ------------------------------------------------
614 .. image:: img/comp512.png
619 .. image:: img/comp4k.png
624 * débit décroit linéairement en fonction de **n**
628 LE FILTRAGE DES IMAGES
629 ======================
635 * Pas d'utilisation de la mémoire partagée.
636 * Accès optimaux : 1 lecture par pixel.
637 * Débit global amélioré de **x7** à **x10**, proche du maximum.
638 * Débit de calcul max. **5,3 GP/s**.
639 * Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.
640 * Création d'une application web générant les codes sources.
641 * Utilisé sur images de cristallographie au synchrotron SPring-8.
645 * *Gilles Perrot. Image processing. In* **Designing Scientific Applications on GPUs**, *pages 28-70. CRC Press, 2013.*
646 * *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.*
651 LE FILTRAGE DES IMAGES
652 ======================
653 Les filtres de convolution
654 --------------------------
660 $$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$
662 **Selon les valeurs du masque h**
664 * Réduction de bruit, détection de bords,...
665 * Potentiellement **séparable** en deux convolutions 1D.
671 LE FILTRAGE DES IMAGES
672 ======================
673 Les filtres de convolution GPU
674 ------------------------------
676 Extension des méthodes appliquées au filtre médian :
678 * Un seul accès mémoire par pixel.
679 * Mémorisation et calculs en registre.
680 * Optimum à 8 pixels/thread.
682 Implémentations de référence (C2070) :
684 * Nvidia atteint un débit de calcul maximum de **6,00 GP/s**.
689 LE FILTRAGE DES IMAGES
690 ======================
691 Les filtres de convolution GPU
692 ------------------------------
696 * Amélioration sensible des débits de calcul en 2D : 16 à 35 %.
697 * Débit de la convolution 1D horizontale jusqu'à 54% plus élevé.
698 * Débit maximum de **8,54 GP/s**.
699 * Application à d'autres familles de signaux 1D (audio,...).
704 LE FILTRAGE DES IMAGES
705 ======================
706 Filtre par recherche des lignes de niveaux
707 ------------------------------------------
711 * Les algorithmes qui débruitent le mieux sont lents (BM3D).
712 * Les images naturelles sont décomposables en un ensemble de lignes de niveaux ( iso-niveau de gris ).
713 * Concevoir un algorithme GPU original et son implémentation.
717 LE FILTRAGE DES IMAGES
718 ======================
719 Filtre par recherche des lignes de niveaux
720 ------------------------------------------
722 **Principe - modèle**
724 * Estimation locale, par maximum de vraisemblance.
725 * Réduction de bruit par moyennage le long de la ligne estimée.
726 * Modèle de ligne de niveaux retenu : **isoline**
728 = ligne brisée composée de **segments**.
730 * Segments choisis parmi 32 motifs pré-calculés.
731 * Les 8 premiers motifs pour des segments de 6 pixels :
733 .. image:: img/P5Q1.png
739 LE FILTRAGE DES IMAGES
740 ======================
741 Filtre par recherche des lignes de niveaux
742 ------------------------------------------
744 **Étape 1** (1 pixel/thread)
746 * En chaque pixel, recherche du motif maximisant la log-vraisemblance ( exemple :math:`\(n=6\)`)
750 $$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$
753 .. image:: img/lniv-mv.png
757 * Mémorisation des paramètres du motif sélectionné dans deux matrices :math:`\(I_{\Theta}\)` (indice) et :math:`\(I_{\Sigma}\)` (moyenne, variance).
761 LE FILTRAGE DES IMAGES
762 ======================
763 Filtre par recherche des lignes de niveaux
764 ------------------------------------------
766 **Étape 2** (1 pixel/thread)
768 * Isoline validée de :math:`\(n_{prec}\)` pixels.
769 * Segment candidat de :math:`\(n_s\)` pixels.
770 * Allongement de l'isoline sous condition GLRT ?
775 $$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]$$
777 .. image:: img/pipd-extension.png
782 LE FILTRAGE DES IMAGES
783 ======================
784 Filtre par recherche des lignes de niveaux
785 ------------------------------------------
787 **Étape 3** (optionnelle)
789 Compensation de la non robustesse de sélection des motifs dans les zones homogènes.
791 * Conception d'un détecteur de zones homogènes.
792 * Identification des zones homogènes avec ce détecteur.
793 * Application d'un filtre moyenneur dans les zones identifiées comme homogènes (convolution).
797 * Sous-ensembles de pixels n'ayant pas d'intersection --> MV
798 * Utilisation des motifs des segments pour gain de temps.
802 LE FILTRAGE DES IMAGES
803 ======================
804 Filtre par recherche des lignes de niveaux
805 ------------------------------------------
809 Ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD)
811 * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB**,
812 * Indice de similarité structurelle : **+30%**,
813 * Temps de calcul (C2070, **avec** détecteur) : **7 ms**.
815 Algorithme de référence BM3D
817 * Amélioration moyenne du rapport Signal sur bruit: **+9,5 dB**,
818 * Indice de similarité structurelle : **+36%**,
819 * Temps de calcul : **4300 ms**.
823 * 2,4 dB d'écart, soit réduction de 43% de la puissance de bruit
827 LE FILTRAGE DES IMAGES
828 ======================
829 Filtre par recherche des lignes de niveaux
830 ------------------------------------------
834 ============================================ === ========================================
835 .. image:: img/zoom_noisy.png .. image:: img/zoom_mean5.png
837 Bruit gaussien :math:`\(\sigma=25\)` Moyennage 5x5
839 .. image:: img/zoom_pipdh.png .. image:: img/zoom_bm3d.png
842 ============================================ === ========================================
846 LE FILTRAGE DES IMAGES
847 ======================
848 Filtre par recherche des lignes de niveaux
849 ------------------------------------------
851 **Synthèse - conclusion**
853 * Rapport qualité/temps élevé.
854 * Traitement d'images HD à 20 fps.
855 * Artefacts en marche d'escalier.
856 * Parallélisation de la méthode de Buades *et al.* (2006) :
858 - gain +1 dB en +0,2 ms pour 512x512.
860 * Algorithme dédié GPU, sans implémentation séquentielle de référence.
864 * *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.*
872 * Trois types de conception mis en |~oe| uvre :
874 - Parallélisation GPU d'une implémentation CPU (*snake*).
875 - Implémentations optimisées pour GPU d'opérateurs mathématiques (médian, convolution).
876 - Algorithme dédié GPU et son implémentation (isolines).
878 * Le portage **efficace** d'algorithme sur GPU s'avère très complexe.
879 * Certains algorithmes ne se prêtent pas à la parallélisation GPU.
880 * L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.
881 * Filtrage à des débits inégalés, proches des performances crête.
882 * Filtres utilisables par tout programmeur grâce au générateur de code.
890 * Extension des filtres aux images couleurs et autres types de bruits (multiplicatif).
891 * Extension aux pseudo-médians de grandes tailles (microscopie).
892 * Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées (audio, imagerie 3D, BM3D).
893 * Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités (parallélisme dynamique, kernels concurrents).
898 * certaines ardeurs ont été refroidies
905 Parallélisation du *Snake* polygonal sur GPU
906 --------------------------------------------
908 **Structure des données** (n |oe| uds pairs)
910 .. image:: img/16segments.png
915 * règle 1 thread par pixel
921 Image cristallographie SPring-8
922 -------------------------------
924 .. image:: img/spring82.png
934 .. image:: img/detecteur.png
939 .. |oe| unicode:: U+0153
942 .. |~oe| unicode:: U+0153
946 .. |B| unicode:: U+00DF
