Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Thèse en cours de

Thèse en cours
Equipe : Systèmes Parallèles

Étiquetage en composantes connexes efficace pour les architectures hautes performances

Début le 01/11/2012
Direction : LACASSAGNE, Lionel

Financement : salarie
Etablissement d'inscription : Université Paris-Sud
Lieu de déroulement : LRI-ARCHI

Soutenue le 28/09/2016 devant le jury composé de :
Directeur de thèse
M. Lionel LACASSAGNE, UPMC

Examinateurs :
-M. Sylvain CONCHON, Université Paris-Sud 11,
-M. Daniel ETIEMBLE, Université Paris-Sud,
-M. Olivier SENTIEYS, INRIA,
-M. Sven SIMON, Universität Stuttgart,

Rapporteurs :
-Mme Annick MONTANVERT, Université Pierre-Mendès France,
-M. Hugues TALBOT, Université Paris-Est-Marne-la-Vallée / ESIEE,

Activités de recherche :

Résumé :
Ces travaux de thèse, dans le domaine de l'adéquation algorithme
architecture pour la vision par ordinateur, ont pour cadre l'étiquetage
en composantes connexes (ECC) dans le contexte parallèle des
architectures hautes performances. Alors que les architectures
généralistes modernes sont multi-coeur, les algorithmes d'ECC sont
majoritairement séquentiels, irréguliers et utilisent une structure de
graphe pour représenter les relations d'équivalence entre étiquettes, ce
qui rend complexe leur parallélisation.

L'ECC permet à partir d'une image binaire de regrouper sous une même
étiquette tous les pixels connexes. Il fait ainsi le pont entre les
traitements de bas niveau tels que le filtrage et ceux de haut niveau
tels que la reconnaissance de forme ou la prise de décision. Il est donc
impliqué dans un grand nombre de chaînes de traitements qui nécessitent
l'analyse d'images segmentées. L'accélération de cette étape représente
donc un enjeu pour tout un ensemble d'algorithmes.
Les travaux de thèse se sont tout d'abord concentrés sur les
performances comparées des algorithmes de l'état de l'art tant pour
l'ECC que pour l'analyse des caractéristiques des composantes connexes
(ACC) afin d'en dégager une hiérarchie et d’identifier les composantes
déterminantes des algorithmes. Pour cela, une méthode d'évaluation des
performances, reproductible et indépendante du domaine applicatif, a été
proposée et appliquée à un ensemble représentatif des algorithmes de
l'état de l'art. Les résultats montrent que l'algorithme séquentiel le
plus rapide est l'algorithme LSL qui manipule des segments contrairement
aux autres algorithmes qui manipulent des pixels.

Dans un deuxième temps, une méthode de parallélisation des algorithmes
directs utilisant OpenMP a été proposée avec pour objectif principal de
réaliser l’ACC à la volée et de diminuer le coût de la communication
entre les threads. Pour cela, l'image binaire est découpée en bandes
traitées en parallèle sur chaque coeur de l'architecture. Ensuite une
étape de fusion pyramidale d'ensembles d'étiquettes deux à deux
disjoints permet d'obtenir l'image complètement étiquetée sans avoir de
concurrence d'accès aux données entre les différents threads. La
procédure d'évaluation des performances appliquée à des machines de
degré de parallélisme variés a démontré que la méthode de
parallélisation proposée était efficace et qu'elle s'appliquait à tous
les algorithmes directs. L'algorithme LSL s'est encore avéré être le
plus rapide et le seul adapté à l'augmentation du nombre de coeurs du
fait de son approche «segments». Pour une architecture à 60 coeurs,
l'algorithme LSL permet de traiter de 42,4 milliards de pixels par
seconde pour des images de taille 8192x8192, tandis que le plus rapide
des algorithmes pixels est limité par la bande passante et sature à 5,8
milliards de pixels par seconde.

Après ces travaux, notre attention s'est portée sur les algorithmes
d'ECC itératifs dans le but de développer des algorithmes pour les
architectures manycore et GPU. Les algorithmes itératifs se basant sur
un mécanisme de propagation des étiquettes de proche en proche, aucune
autre structure que l'image n'est nécessaire, ce qui permet d'en
réaliser une implémentation massivement parallèle (MPAR). Ces travaux
ont mené à la création de deux nouveaux algorithmes :

- une amélioration incrémentale de MPAR utilisant un ensemble de
mécanismes tels qu'un balayage alternatif, l'utilisation d'instructions
SIMD ainsi qu'un mécanisme de tuiles actives permettant de répartir la
charge entre les différents coeurs tout en limitant le traitement des
pixels aux zones actives de l'image et à leurs voisines,
- un algorithme mettant en œuvre la relation d’équivalence directement
dans l’image pour réduire le nombre d'itérations nécessaires à
l'étiquetage. Une implémentation pour GPU basée sur les instructions «
atomic » avec un pré-étiquetage en mémoire locale a été réalisée et
s'est révélée efficace dès les images de petite taille.