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 homogènes d'une image.
72 .. image:: img/seg1.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 * **Pré-traiter** et effectuer les traitements de haut niveau sur des images *améliorées*.
95 * réduction, *a priori*, du coût des traitements de haut niveau.
96 * les prétraitements ont eux aussi un coût, en temps de calcul et potentiellement en information.
98 * **Ne pas pré-traiter** et effectuer les traitements de haut niveau sur les images bruitées.
100 * pas de perte d'information due au pré-traitement.
104 PLAN DE LA PRÉSENTATION
105 =======================
109 - Les GPUs ou *Graphical Processing Units*.
110 - Le filtrage et la segmentation d'images.
112 #. La segmentation des images
114 - Travaux de référence.
115 - Parallélisation GPU d'un algorithme de segmentation de type *snake*.
117 #. Le filtrage des images
119 - Travaux de référence.
120 - Optimisation GPU des filtres médian et de convolution.
121 - Conception d'un algorithme GPU de débruitage par recherche des lignes de niveaux.
123 #. Conclusion et perspectives
129 Les GPUs ou *Processeurs graphiques*.
130 -------------------------------------
132 .. image:: img/gpucpu1.png
136 * Processeurs *classiques* **CPU** : exécution **séquentielle**
138 - Quelques unités de calcul ( les c |oe| urs).
140 * Processeurs *graphiques* **GPU** : exécution **massivement parallèle**
142 - Des centaines, voire milliers, d'unités de calcul, regroupées en SMs (*Streaming Multiprocessors*).
146 * La multiplication des c |oe| urs dans les GPUs se fait au détriment des fonctions de contrôle et de cache.
147 * Seule la mémoire *globale* est accessible par l'ensemble des fils d'exécution (les *threads*) et ses performances sont faibles.
148 * AU sein de la RAM il y a différents canaux vers différents types de mémoires.
149 * L'accès efficace aux mémoires est contraignant.
150 * Les échanges de données entre le GPU et son hôte CPU sont pénalisants.
151 * 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.
152 * La mise au point n'est pas aisée lorsque des centaines de milliers de threads concourent à l'exécution d'une tâche.
154 * L'accroissement des capacités de calcul a suivi l'augmentation des résolutions d'images.
155 * 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.
156 * 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.
164 Le traitement des images
165 ------------------------
167 **Le filtrage (du bruit)**
169 * Les capteurs et les conditions d'acquisition induisent du bruit.
170 * *Résolution élevée* n'implique pas *bruit réduit*.
175 * Aucun algorithme universel.
179 * les bruits dégradent l'image de la scène idéale et peuvent en fausser ou compliquer l'interprétation.
180 * on recense plus de 4000 algorithmes de segmentation
181 * La segmentation intervient dans beaucoup d'applications : du tracking à la détection ou à l'extraction de caractéristiques diverses.
182 * 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.
195 * Algorithme par contours actifs, classe des *snakes*.
196 * Implémentation CPU optimisée existante.
197 * Conception de l'implémentation GPU.
198 * Adaptations mineures de l'algorithme.
202 * Filtre par lignes de niveaux
204 - Algorithme original,
205 - Conceptions conjointes algorithme et implémentation.
207 * Filtres médians, filtres de convolution
209 - Opérateurs mathématiques,
210 - Conception d'une implémentation optimisée.
215 SEGMENTATION PAR CONTOUR ACTIF
216 ==============================
220 **Level-set** ( Roberts *et al.*, 2010)
222 * Images d'IRM de 256x256x256 pixels (16 millions),
223 * Temps sur GTX280 : **11 s**.
225 **Snake GVF** (Smistad *et al.*, 2012)
227 * Images d'IRM de 256x256x256 pixels (16 millions),
228 * Temps sur C2070 : **7 s**.
230 .. figure:: img/brain3D-gvf.png
237 * Le domaine médical recèle la quasi totalité des implémentations GPU d'algorithmes de segmentation.
238 * Nombre d'entre elles concernent des traitements effectués en 3D par nécessité, où l'emploi du GPU s'impose assez naturellement.
239 * Les algorithmes **level-set** sont les plus implémentés sur GPU :
240 * Les algorithmes **snakes** sont très peu implémentée sur GPU :
244 SEGMENTATION PAR CONTOUR ACTIF
245 ===============================
246 *Snake* polygonal orienté région (principe)
247 -------------------------------------------
255 * - .. image:: img/snake-modele.png
257 - * Objectif : déterminer le contour le plus *vraisemblable*.
258 * Le critère de vraisemblance généralisée est, dans le cas gaussien :
262 $$GL = \frac{1}{2}\left[ n_B.log\left(\sigma_B^2\right) + n_T.log\left(\sigma_T^2\right)\right]$$
264 * Calcul des variances :math:`\(\sigma^2\)` pour chaque contour :
266 * Méthode de Chesnaud *et el.* (1999) en :math:`\(\mathcal{O}(n^2)\)`.
267 * Implique le **pré-calcul** de 3 images cumulées.
271 * Cela permet d'extraire des formes aux contours mal définis, en raison d'un fort niveau de bruit par exemple.
275 SEGMENTATION PAR CONTOUR ACTIF
276 ===============================
277 *Snake* polygonal orienté région (algo CPU)
278 --------------------------------------------
280 .. image:: img/cochons-it0-it1.png
285 #. Le contour initial est rectangulaire ( 4 n |oe| uds )
286 #. 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.
291 SEGMENTATION PAR CONTOUR ACTIF
292 ===============================
293 *Snake* polygonal orienté région (algo CPU)
294 --------------------------------------------
296 .. image:: img/cochons-it21-it22.png
299 .. image:: img/cochons-it4-it5.png
308 SEGMENTATION PAR CONTOUR ACTIF
309 ===============================
310 *Snake* polygonal orienté région (algo CPU)
311 --------------------------------------------
313 Exemples de résultats
315 .. figure:: img/snake-exs.png
320 * 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)
324 SEGMENTATION PAR CONTOUR ACTIF
325 ===============================
326 Parallélisation du *Snake* polygonal sur GPU
327 --------------------------------------------
328 Identification des fonctions coûteuses
330 .. image:: img/algosnake1.png
335 SEGMENTATION PAR CONTOUR ACTIF
336 ===============================
337 Parallélisation du *Snake* polygonal sur GPU
338 --------------------------------------------
341 .. image:: img/algosnake-3etages.png
347 SEGMENTATION PAR CONTOUR ACTIF
348 ===============================
349 Parallélisation du *Snake* polygonal sur GPU
350 --------------------------------------------
352 .. image:: img/snake-pairimpair.png
357 * 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.
358 * Pour éviter les oscillations et *coller* à l'algorithme séquentiel, on distingue les n |oe| uds d'indices pairs et impairs.
359 * On évalue **en parallèle** l'ensemble des déplacements éventuels de tous les n |oe| uds de même parité.
365 SEGMENTATION PAR CONTOUR ACTIF
366 ===============================
367 Parallélisation du *Snake* polygonal sur GPU
368 --------------------------------------------
370 * 1 thread par pixel.
371 * Concaténation de tous les pixels composant l'ensemble des contours évalués.
372 * Réductions en mémoire partagée.
373 * Une seule taille de segment : la taille du plus long.
377 * les réduction consistent à sommer, pour chaque segment les contributions partielles par bloc calculées au 1
381 SEGMENTATION PAR CONTOUR ACTIF
382 ===============================
383 Parallélisation du *Snake* polygonal sur GPU
384 --------------------------------------------
388 * Conservation des données en mémoire GPU.
389 * Images cumulées calculées en parallèle.
390 * Discretisation des segments en parallèle (1 thread/pixel).
391 * Respect de l'algorithme original.
395 * Trop peu de calculs à effectuer.
396 * Motifs d'accès à la mémoire globale trop irréguliers.
397 * Emploi de la mémoire partagée.
401 * Un seul entier est échangé entre le CPU et le GPU à chaque itération.
402 * image cumulées par une adaptation de la méthode des sommes de préfixes.
403 * Abandon Bresenham Possible car parcours unidirectionnel du contour.
404 * Trop peu de calculs ne permet pas de masquer les latences.
405 * Pas de coalescence possible dans les accès à la mémoire globale car la géométrie des segments varie.
406 * mémoire partagée à cause des réductions.
410 SEGMENTATION PAR CONTOUR ACTIF
411 ===============================
412 Parallélisation du *Snake* polygonal sur GPU
413 --------------------------------------------
415 **Performances de l'implémentation**
417 .. image:: img/perfs-snake.png
422 .. image:: img/perfs-snake-img.png
427 SEGMENTATION PAR CONTOUR ACTIF
428 ===============================
429 Parallélisation du *Snake* polygonal sur GPU
430 --------------------------------------------
434 * Première et seule implémentation à ce jour.
435 * Performances intéressantes pour les grandes images.
436 * Image 10000x10000 en moins de 0,6 seconde.
437 * Emploi non optimal du GPU : réductions, irrégularités.
438 * Premières itérations GPU rapides : grands segments.
439 * Temps de calcul très dépendant du contenu de l'image :
441 - Proposition d'une méthode d'initialisation alternative.
442 - Recherche du contour rectangle le plus vraisemblable.
443 - Accélération jusqu'à x15 avec de petites cibles.
447 LE FILTRAGE DES IMAGES
448 ======================
451 * Filtres de convolution,
452 * Filtre par recherche des lignes de niveaux (PIPD).
456 LE FILTRAGE DES IMAGES
457 ======================
458 Filtre médian : principe
459 ------------------------
461 .. image:: img/median-principe.png
464 La valeur de sortie d'un pixel est la **médiane** des valeurs de son voisinage.
466 * Bonne réduction de bruits gaussien et *poivre & sel*
467 * Valeurs de sortie appartenant au voisinage.
468 * Opération de sélection coûteuse (tri).
469 * Usages fréquents avec des petites fenêtres (de 3x3 à 7x7).
470 * Quelques applications avec de grandes fenêtres.
474 LE FILTRAGE DES IMAGES
475 ======================
476 Filtre médian : usage
477 ---------------------
481 =================================== ======================================== ============================================
482 .. image:: img/airplane_sap25.png .. image:: img/airplane_sap25_med5.png .. image:: img/airplane_sap25_med3_it2.png
483 =================================== ======================================== ============================================
484 Bruit *poivre & sel* 25% Médian 5x5 Médian 3x3 - 2 passes
485 =================================== ======================================== ============================================
489 LE FILTRAGE DES IMAGES
490 ======================
491 Filtre médian GPU : Travaux de référence
492 ----------------------------------------
494 Comparaison des implémentations GPU de référence :
496 - **PCMF**, Sanchez *et al.* (2013), débit max. **80 MP/s**,
497 - **ArrayFire**, bibliothèque commerciale, débit max. **185 MP/s**,
498 - **BVM** parallélisé par Chen *et al.* (2009), débit max. **110 MP/s**.
500 .. image:: img/compar-median2.png
505 * PCMF : Parallel (Complementary Cumulative Derivative Function) Median Filter (histogrammes cumulatifs)
506 * CTMF : CPU à temps constant
510 LE FILTRAGE DES IMAGES
511 ======================
512 Filtre médian GPU : Travaux de référence
513 ----------------------------------------
515 Emploi de la **mémoire partagée** (exemple médian 5x5)
517 .. image:: img/shmemhalo.png
522 - recouvrement pose problème à cause accès concurrents à la mémoire partagée.
526 LE FILTRAGE DES IMAGES
527 ======================
528 Optimisation du filtre médian GPU
529 ---------------------------------
531 .. image:: img/CPU-GPU-memcpy.png
534 .. image:: img/transferts-mem.png
539 On gagne de 13 à 43 % sur les temps de transfert.
543 LE FILTRAGE DES IMAGES
544 ======================
545 Optimisation du filtre médian GPU
546 ---------------------------------
549 .. image:: img/CPU-GPU-memcpy-dummykernel.png
553 Débits maximums effectifs, en MP/s, sur C2070.
555 .. image:: img/debit-max-2070.png
558 **Rappel :** PCMF : 80 MP/s - BVM : 110 MP/s - ArrayFire : 185 MP/s
562 ça laisse environ 80ms pour faire un tri de 9 valeurs sur une image de 4096x4096
566 LE FILTRAGE DES IMAGES
567 ======================
568 Optimisation du filtre médian GPU
569 ---------------------------------
571 **Sélection de la médiane**
573 * Emploi exclusif des **registres** pour charger les valeurs utiles
575 - mémoires individuelles au c |oe| ur du GPU,
576 - non indexables dans un tableau.
577 - maximum de 63 registres par thread et 32 K par bloc de threads.
579 * Pour les petites tailles : max. 7x7 avec 1 pixel/thread.
580 * Exploitation des recouvrements entre fenêtres voisines.
585 LE FILTRAGE DES IMAGES
586 ======================
587 Optimisation du filtre médian GPU
588 ---------------------------------
590 **Sélection de la médiane** (par oubli)
600 * Évite le tri complet : performances en hausse,
601 * Économie de registres : :math:`\(\lceil \frac{n}{2}\rceil +1\)` au lieu de :math:`\(n\)`,
602 * Permet de plus grandes tailles : max 11x11.
604 - .. image:: img/forgetful_selection.png
609 LE FILTRAGE DES IMAGES
610 ======================
611 Optimisation du filtre médian GPU
612 ---------------------------------
614 **Exploitation des recouvrements** : 2 pixels par thread (médian 5x5).
616 .. image:: img/recouvrement5.png
619 À 4 pixels/thread, zone commune = 10 pixels < 14 : **pas performant**.
623 * chaque thread utilise plus de registres
624 * mais sur un bloc, en adaptant la taille du bloc, on économise k+1 registres par paire de pixels.
628 LE FILTRAGE DES IMAGES
629 ======================
630 Performances du médian GPU proposé (PRMF)
631 ------------------------------------------------
633 .. image:: img/perf-median.png
638 LE FILTRAGE DES IMAGES
639 ======================
640 Performances du filtre médian GPU proposé (PRMF)
641 ------------------------------------------------
645 .. image:: img/comp512.png
650 .. image:: img/comp4k.png
655 * débit décroit linéairement en fonction de **n**
659 LE FILTRAGE DES IMAGES
660 ======================
666 * Pas d'utilisation de la mémoire partagée.
667 * Accès optimaux : 1 lecture par pixel.
668 * Débit global amélioré de **x7** à **x10**, proche du maximum.
669 * Débit de calcul max. **5,3 GP/s**.
670 * Médian jusqu'au 11x11 sur C2070, 21x21 sur K40.
671 * Création d'une application web générant les codes sources.
672 * Utilisé sur images de cristallographie au synchrotron **SPring-8**.
674 .. image:: img/spring82.png
679 LE FILTRAGE DES IMAGES
680 ======================
681 Les filtres de convolution : généralités
682 -----------------------------------------
688 $$I_{out}(x, y) = \left(I_{in} * h\right) = \sum_{(i < H)} \sum_{(j < L)}I_{in}(x-j, y-i)h(j,i)$$
690 **Selon les valeurs du masque h**
692 * Réduction de bruit, détection de bords,...
693 * Opération **séparable** en deux convolutions 1D.
699 LE FILTRAGE DES IMAGES
700 ======================
701 Les filtres de convolution GPU
702 ------------------------------
704 Exploitation des recouvrements :
706 * un seul accès mémoire par pixel, mémorisation en registre.
707 * Optimum à 8 pixels/thread :
708 * Exemple médian 5x5, pour un thread :
710 - 60 pixels dans le halo : 60 lectures.
711 - 200 lectures + préchargement si utilisation mémoire partagée.
713 Nvidia propose les implémentations les plus rapides (séparable ou non) :
715 * Traitement de référence : 2048x2048 pixels, 5x5, 8bits.
717 .. image:: img/debit-calcul-convoNS.png
722 LE FILTRAGE DES IMAGES
723 ======================
724 Les filtres de convolution GPU
725 ------------------------------
727 **Résultats (suite)**
729 .. image:: img/debit-calcul-convoS.png
732 Convolution séparable :
734 * Une convolution verticale en mémoire partagée, suivie d'une convolution horizontale en registres.
735 * Copie intermédiaire en mémoire globale (cache 1D rapide).
736 * L'accélération est due à la seule convolution en registres (54%).
740 LE FILTRAGE DES IMAGES
741 ======================
742 Les filtres de convolution GPU
743 ------------------------------
747 * Amélioration sensible sur les débits de calcul (de 17 à 33 %).
748 * Le traitement 1D est jusqu'à 54% plus rapide.
749 * Application à d'autres familles de signaux 1D (audio,...).
753 LE FILTRAGE DES IMAGES
754 ======================
755 Filtre par recherche des lignes de niveaux
756 ------------------------------------------
760 * Les algorithmes qui débruitent le mieux sont lents (BM3D).
761 * Les images naturelles sont décomposables en un ensemble de lignes de niveaux ( iso-niveau de gris ).
762 * Concevoir un algorithme GPU original et son implémentation.
766 LE FILTRAGE DES IMAGES
767 ======================
768 Filtre par recherche des lignes de niveaux
769 ------------------------------------------
771 **Principe - modèle**
773 * Estimation locale, par maximum de vraisemblance, des lignes de niveaux.
774 * Réduction de bruit par moyennage le long de la ligne estimée.
775 * Les lignes de niveaux estimées sont modélisées par des lignes brisées nommées **isolines**.
776 * Les segments des lignes brisées sont choisis parmi des motifs pré-établis (32 motifs).
779 .. image:: img/P5Q1.png
785 LE FILTRAGE DES IMAGES
786 ======================
787 Filtre par recherche des lignes de niveaux
788 ------------------------------------------
790 **Principe (étape 1)**
792 * En chaque pixel, recherche du motif maximisant la log-vraisemblance ( :math:`\(n=6, \sigma^2 =\)` variance )
796 $$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$
798 * Mémorisation des paramètres des motifs sélectionnés dans deux matrices :math:`\(I_{\Theta}\)` et :math:`\(I_{\Sigma}\)`.
800 .. image:: img/lniv-mv.png
805 LE FILTRAGE DES IMAGES
806 ======================
807 Filtre par recherche des lignes de niveaux
808 ------------------------------------------
810 **Principe (étape 2)**
812 * Allongement itératif des segments sous condition GLRT.
816 $$(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]$$
818 .. image:: img/pipd-detail.png
823 LE FILTRAGE DES IMAGES
824 ======================
825 Filtre par recherche des lignes de niveaux
826 ------------------------------------------
828 **Principe (étape 3)**
830 Compensation de la non robustesse de sélection des motifs dans les zones homogènes.
832 * identification des zones homogènes avec un détecteur de bords.
833 * Application d'un filtre moyenneur dans ces zones.
835 .. image:: img/detecteur.png
840 * Sous-ensembles de pixels n'ayant pas d'intersection --> MV
841 * Utilisation des motifs des segments pour gain de temps.
845 LE FILTRAGE DES IMAGES
846 ======================
847 Filtre par recherche des lignes de niveaux
848 ------------------------------------------
852 Sur l'ensemble d'images de S. Lansel (DenoiseLab, Université Stanford), filtre proposé (PI-PD)
854 * Amélioration moyenne du rapport Signal sur bruit: **+7,1 dB**
855 * Indice de similarité structurelle : **+30%**
856 * Temps de calcul : **7 ms**
858 Comparaison avec BM3D
860 * Amélioration moyenne du rapport Signal sur bruit: **+9,5 dB**
861 * Indice de similarité structurelle : **+36%**
862 * Temps de calcul : **4300 ms**
866 LE FILTRAGE DES IMAGES
867 ======================
868 Filtre par recherche des lignes de niveaux
869 ------------------------------------------
873 ============================================ === ========================================
874 .. image:: img/zoom_noisy.png .. image:: img/zoom_mean5.png
876 Bruit gaussien :math:`\(\sigma=25\)` Moyennage 5x5
878 .. image:: img/zoom_pipdh.png .. image:: img/zoom_bm3d.png
881 ============================================ === ========================================
885 LE FILTRAGE DES IMAGES
886 ======================
887 Filtre par recherche des lignes de niveaux
888 ------------------------------------------
890 **Synthèse - conclusion**
892 * Rapport qualité/temps élevé.
893 * Traitement d'images HD à 20 fps.
894 * Artefacts en marche d'escalier. Réduits par la méthode de Buades *et al.* (+1 dB, +0,2 ms pour 512x512).
895 * Extension aux images couleurs et autres types de bruits (multiplicatif).
896 * Algorithme original sans implémentation séquentielle de référence.
900 CONCLUSION GÉNÉRALE - PERSPECTIVES
901 ==================================
903 * Trois types de conception mis en |~oe| uvre.
904 * Le portage efficace d'algorithme peut s'avérer très complexe, voire sans intérêt.
905 * L'emploi de la mémoire partagée n'apporte pas les meilleures performances en cas de recouvrements.
906 * Filtres utilisables par tout programmeur grâce à un générateur de code.
907 * Beaucoup de traitements et domaines peuvent bénéficier des techniques proposées.
908 * Les évolutions de l'architecture laissent entrevoir de nouvelles possibilités.
913 * certaines ardeurs ont été refroidies
919 Parallélisation du *Snake* polygonal sur GPU
920 --------------------------------------------
922 **Structure des données** (n |oe| uds pairs)
924 .. image:: img/16segments.png
929 * règle 1 thread par pixel
932 .. |oe| unicode:: U+0153
935 .. |~oe| unicode:: U+0153
939 .. |B| unicode:: U+00DF
