Brambor, Jaromír (2006) Algorithms of mathematical morphology for stream-oriented architectures. PhD thesis Morphologie Mathématique, ENSMP - CMM Centre de Morphologie Mathématique, ENSMP.

Full text available as: - Brambor-Doctoral-Thesis--hypertext-in-bw.pdf ( 4083 Kb ) - Brambor-Doctoral-Thesis.pdf ( 5974 Kb )

Licence: Copyright

Alternative Locations: 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

Abstract

This thesis deals with the algorithms of Mathematical Morphology that can consider the pixels of an image as if they were a stream of data. We will show that a great number of algorithms of Mathematical Morphology can be described by data flows (streams) passing through the operating units. We will see that this approach can function on generic processors supporting a multi-media instruction set as well as on graphics cards.
We propose to use the functional language Haskell for the description of algorithms operating on data flows. This allows us to describe the building blocks that are used to construct morphological algorithms. We apply these building blocks in the description of the most usually used algorithms (dilation/erosion, geodesic operations, distance function and levelings). This will also facilitate the porting of these algorithms onto several platforms.
We propose an original mode of execution by macro blocks for the construction of morphological algorithms and we study in depth the transposition of this idea to SIMD architectures. We show that the use of macro blocks is interesting for multimedia architectures. We also show that the morphological algorithms proposed in this thesis reach better performances than standard implementations. Thus, a new field opens to algorithms we have developed here in real-time image processing applications.
This thesis also explores the graphics processors and shows on experimental results that they are already powerful enough to compete with general processors.

Table of content

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

Repository Staff Only: edit this item