Approche parallèle pour le calcul de l'arbre des formes en n-dimensions

Auteurs

Sébastien Crozet

Type

techreport

Année

2012

Numéro

1207

Résumé

L'arbre des formes est une transformée d'image utile pour effectuer des traitements sur des images discrètes de façon auto-duale. Un algorithme (non publié)travaillant sur des images n-dimensionnelles dans l'espace des complexes cellulaires, nous permet déjà de construire un arbre des formes en temps quasi-linéaire. Cependant, cet algorithme reste souvent largement plus lent que d'autres approches en temps theta(nlog(n)) sur des images naturelles en 2D ou 3D, le nombre de cellules à traiter dans l'espace des complexes étant très élevé. En vue d'améliorer ces temps de calculs, nous présentons une approche pour paralléliser l'algorithme de calcul d'arbre quasi-linéaire en exhibant des propriétés topologiques et algorithmiques qui ne peuvent être facilement obtenues par les autres approches existantes.