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::
* 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
#. Introduction
- Les GPUs ou *Graphical Processing Units*.
- - Le filtrage et la segmentation d'images.
+ - Objectifs.
#. La segmentation des images
* 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
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
--------------------
----
-SEGMENTATION PAR CONTOUR ACTIF
+SEGMENTATION
===============================
*Snake* polygonal orienté région (principe)
-------------------------------------------
* 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::
----
-SEGMENTATION PAR CONTOUR ACTIF
+SEGMENTATION
===============================
*Snake* polygonal orienté région (algo CPU)
--------------------------------------------
.. 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)
--------------------------------------------
.. image:: img/cochons-it21-it22.png
:height: 300px
+.. image:: img/barre-blanche.png
+ :height: 10px
+
.. image:: img/cochons-it4-it5.png
:height: 300px
* 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
--------------------------------------------
----
-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
----
-SEGMENTATION PAR CONTOUR ACTIF
+SEGMENTATION
===============================
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::
----
-SEGMENTATION PAR CONTOUR ACTIF
+SEGMENTATION
===============================
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::
----
-SEGMENTATION PAR CONTOUR ACTIF
+SEGMENTATION
===============================
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
* Filtre médian,
* Filtres de convolution,
- * Filtre par recherche des lignes de niveaux (PIPD).
+ * Filtre par recherche des lignes de niveaux.
----
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
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.
.. 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::
.. 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
* 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**
**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.
----
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%).
----
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
**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
----
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).
----
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
----
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
**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
* 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
--------------------------------------------
* 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:
