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
- Introduction
- Les GPUs ou Graphical Processing Units.
- Le filtrage et la segmentation d'images.
- La segmentation des images
- Travaux de référence.
- Parallélisation GPU d'un algorithme de segmentation de type snake.
- 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.
- 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)
 |
|
- 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
- Le contour initial est rectangulaire ( 4 nœuds )
- 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 :
|  |
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)
$$-\frac{n}{2}log\left(2\pi\right) - \frac{n}{2}log\left(\sigma^2\right) - \frac{n}{2}$$
- En chaque pixel, recherche du motif maximisant la log-vraisemblance ( \(n=6, \sigma^2 =\) variance )
- 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)
$$(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]$$
- Allongement itératif des segments sous condition GLRT.
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
