Algorithmes de la morphologie mathématique pour les architectures orientées flux.

Accueil || Parcours || Recherche || S'enregistrer || Mon Compte || Contacts || Aide || Langues

Brambor, Jaromír (2006) Algorithmes de la morphologie mathématique pour les architectures orientées flux. Doctorat Morphologie Mathématique, ENSMP - CMM Centre de Morphologie Mathématique, ENSMP.

Plein texte disponible en tant que : - Brambor-Doctoral-Thesis--hypertext-in-bw.pdf ( 4083 Kb ) - Brambor-Doctoral-Thesis.pdf ( 5974 Kb )

Licence: Copyright

Autres Localisations: http://cmm.ensmp.fr/~brambor/public/docs/Brambor-Doctoral-Thesis/Brambor-Doctoral-Thesis.pdf, http://cmm.ensmp.fr/~brambor/public/docs/Brambor-Doctoral-Thesis/Brambor-Doctoral-Thesis--hypertext-in-bw.pdf

Résumé

Cette thèse est consacrée aux algorithmes de morphologie mathématique qui peuvent considérer les pixels d'une image comme un flux de données. Nous allons démontrer qu'un grand nombre d'algorithmes de morphologie mathématique peuvent être décrits comme un flux de données traversant des unités d'exécution. Nous verrons que cette approche peut aussi fonctionner sur des processeurs génériques possédant un jeu d'instructions multimédia ou sur des cartes graphiques.
Pour décrire les algorithmes en flux de données, nous proposons d'utiliser le langage fonctionnel Haskell, ce qui nous permettra de décrire les briques de base de la construction des algorithmes de morphologie mathématique. On applique ces briques dans la description des algorithmes les plus couramment utilisés (dilatation/érosion, opérations géodésiques, fonction distance et nivellements) ce qui facilitera le portage de ces algorithmes sur plusieurs plate-formes.
Nous proposons pour la construction des algorithmes morphologiques un mode d'exécution original par macro blocs et nous étudions en profondeur la transposition de cette idée aux architectures SIMD. Nous montrons que l'utilisation des macro blocs est intéressante pour les architectures multimédia et nous montrons également que les algorithmes morphologiques proposés dans cette thèse atteignent de meilleures performances que les implémentations standard. Un nouveau champ s'ouvre ainsi aux algorithmes développés dans les applications de traitement d'images en temps réel.
Cette thèse explore également les processeurs graphiques et démontre sur des résultats expérimentaux qu'ils sont, dès à présent, assez performants pour concurrencer les processeurs généraux.

Table des Matières

Table des matières
Guide de thèse - 15
I Introduction, bases théoriques et appareil mathématique - 17
1 Motivation - 19
1.1 Évolution en chiffres - 19
1.2 Processeurs à usage général - les GPP et les GPPMM - 20
1.3 Processeurs graphiques - les GPU - 21
1.4 Au-delà de l'horizon - 23
2 État de l'art - 25
3 Architectures - 31
3.1 Taxonomie des architectures - 31
3.1.1 Taxonomie de Flynn - 31
3.1.2 Taxonomie de Duncan - 33
3.2 Facteurs influant la performance - 36
3.2.1 Structure de l'architecture - 37
3.2.2 Fréquence de(s) l'unité(s) de calcul - 37
3.2.3 Structure, capacité et fréquence des mémoires - 38
3.2.4 Parallélisation des données - 39
3.2.5 Parallélisation d'exécution - 39
3.2.6 Écartement et latence des instructions - 39
3.2.7 Instructions spécialisées - 40
3.2.8 Nombre de registres et leur - 40
3.2.9 Approche à l'implémentation des algorithmes - 41
3.3 Consommation d'énergie - 42
3.4 Modèle stream du calcul et les architectures associées - 44
3.4.1 Calcul sur les streams - 44
3.4.2 Architectures stream - 45
3.4.3 Architecture de von Neumann et ses successeurs utilisés pour le calcul stream - 46
3.4.4 Calcul stream sur les architectures SWAR à plusieurs fils - 49
3.4.5 Pipeline graphique et les GPUs - 51
3.4.6 Calcul sur les flux de données avec les GPU - 55
4 Formalisme fonctionnel adopté pour la morphologie mathématique - 59
4.1 Approche fonctionnelle et impérative - 59
4.2 Haskell et les bases des langages fonctionnels - 60
4.2.1 Syntaxe du Haskell - 60
4.2.2 Fonctions de base du Haskell - 62
4.3 Primitives de stockage et de représentation des données - 63
4.3.1 Types de base - 64
4.4 Primitives du calcul comme skeletons algorithmiques - 66
4.4.1 Primitives du calcul séquentiel - 66
4.4.2 Primitives du calcul parallèle - 67
4.4.3 Paquetage et dépaquetage des arrays pour le traitement SIMD - 68
4.4.4 Sens du parcours, passage d'un array à un flux de données et vice vers - 70
4.4.5 Concept des "superpixels" - 73
4.5 Modèle formel du traitement en pipeline graphique - 76
4.5.1 Types de données utilisés dans le modèle - 76
4.5.2 Primitive de calcul avec le pipeline graphique - 81
4.5.3 Modèle du pipeline graphique des GPU - 83
4.6 Primitives de la morphologique mathématique - 84
4.6.1 Images dans la morphologie mathématique - 84
4.6.2 Grilles et voisinages - 84
4.6.3 Éléments structurants - 86
4.6.4 Extraction du voisinage - 88
4.6.5 Kernels de la morphologie mathématique travaillant sur le voisinage local - 92
4.6.6 Opérations du voisinage local avec un masque - 94
4.6.7 Travail sur le voisinage avec les superpixels - 94
II Algorithmes et les skeletons algorithmiques - 97
5 Algorithmes de voisinage non dépendants du sens du parcours - 99
5.1 Algorithmes élémentaires pour les GPP - 99
5.1.1 Approche naïve à l'implémentation des opérations sur le voisinage - 99
5.1.2 Division du problème en traitement de l'intérieur et en traitement du bord - 102
5.1.3 Généralisation du travail sur le voisinage - 105
5.1.4 Approche des superpixels, algorithmes aux kernels complexes qui exploitent la localité des données - 108
5.2 Algorithmes élémentaires pour les GPPMM - 112
5.2.1 Skeletons algorithmiques GPPMM de base - 112
5.2.2 Algorithmes concrets GPPMM de base de la morphologie mathématique - 113
5.2.3 Algorithmes SIMD basés sur l'approche des superpixels - 114
5.3 Algorithmes géodésiques pour les GPP/GPPMM - 115
5.3.1 Idée de base - 115
5.3.2 Itérations, fin de propagation - 116
5.3.3 Note sur le travail géodésique avec les superpixels - 117
5.3.4 Travail SIMD avec les vecteurs paquetés - 117
5.4 Algorithmes pour les GPU - 118
5.4.1 Traitement des bords de la texture sur les GPU - 118
5.4.2 Approche utilisant les opérations de Minkowski - 118
5.4.3 Approche utilisant l'échantillonnage complexe des textures dans l'unité de traitement des fragments - 120
5.4.4 Approche utilisant les point sprites - 120
5.4.5 Description des algorithmes pour les processeurs graphiques par le formalisme fonctionnel - 121
5.5 Résultats expérimentaux - 123
5.6 Récapitulation - 123
6 Permutation SIMD des arrays appliquée au changement de stockage des données vectorielles - 127
6.1 Transpositions et rotations des arrays - 128
6.1.1 Définitions des transpositions et des rotations - 128
6.2 Approche macro blocs aux transpositions et rotations - 129
6.2.1 Découpage des arrays en macro blocs et leur recollage - 131
6.2.2 L'algorithme générique travaillant sur les macro blocs - 131
6.3 Algorithmes rapides SIMD de transposition et de rotation - 133
6.3.1 Fonctions shuffle - 133
6.3.2 Découpage sur les macro blocs et leur recollage sur les architectures SWAR - 134
6.3.3 Shuffles utilisés pour les transpositions et rotations d'un macro bloc - 135
6.3.4 Algorithme complet pour les transpositions et les rotations par SIMD - 140
6.4 Notes sur l'implémentation, résultats expérimentaux - 141
6.5 Récapitulation, perspectives - 144
7 Algorithmes de voisinage dépendant du sens prédéfini de parcours de l'image - 147
7.1 Particularité du sens du parcours pour le traitement SIMD du voisinage - 147
7.2 Skeletons applico-réductifs pour la propagation - 150
7.3 Skeleton algorithmique de la propagation SIMD en 4-voisinage - 151
7.3.1 Propagation à l'intérieur d'un macro bloc - 151
7.3.2 Phase généralisée de la propagation - 152
7.3.3 Propagations SIMD sur l'image entière pour le 4-voisinage et la grille carrée - 153
7.3.4 Calcul de la fonction distance - 153
7.3.5 Calcul des nivellements - 154
7.4 Approche utilisant les macro blocs avec la transposition directe - 158
7.5 Notes sur l'implémentation, résultats expérimentaux - 159
7.6 Récapitulation - 162
8 Algorithmes de la dilatation/érosion pour les éléments structurants de la forme d'un segment - 165
8.1 Approche itérative - 166
8.2 Approche employant les algorithmes à réutilisation des valeurs - 167
8.2.1 Principe de l'algorithme de van Herk-Gil-Werman - 168
8.2.2 Parallélisation pour les architectures SIMD - 172
8.3 Résultats expérimentaux - 173
8.4 Récapitulation - 176
9 Algorithmes et complexité - 177
9.1 Définition d'un algorithme - 177
9.2 Complexité d'un algorithme - 177
9.2.1 Définition de la complexité - 177
9.2.2 Les mesures de la croissance - 177
9.3 Modélisation des performances - 178
9.4 Estimation de la complexité et des performances pour les GPP/GPPMM - 179
9.4.1 Idée générale - 179
9.4.2 Estimation pratique pour les GPPMM - 180
9.5 Exemple d'estimation pratique de la complexité des algorithmes de voisinage - 181
9.6 Estimation de la complexité et des performances pour les GPU - 183
9.6.1 Transfert de données - 183
9.6.2 Influence du système d'exploitation et de l'API - 186
9.7 Récapitulation - 187
Conclusion et perspectives - 189
Annexe - 197
Listes - 205
Liste des termes et des abréviations - 205
Liste des figures - 207
Liste des tableaux - 211
Bibliographie - 213
Index - 225

Statistiques de consultation

Administrateurs de l'archive uniquement : éditer cet enregistrement