X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/10d54068846e7aee58e98dc76fa92f6f3a5c957a..0b60f2b9f649af92fb00ae9fb88d77fe1cbb5c85:/PRESENTATION/diapos.rst 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: