Parallelization of Morphological Operators Based on Graphs

YOUKANA, Imane (2017) Parallelization of Morphological Operators Based on Graphs. Doctoral thesis, UNIVERSITE DE MOHAMED KHIDER BISKRA.

Preview

Text ThèseDoctorat-YOUKANA-Imane.pdf Download (5MB) | Preview

Abstract

La morphologie mathématique est un cadre puissant qui fournit un ensemble d’outils de filtrage et de segmentation très utiles dans les applications d’analyse d’image. Initialement le premier champ d’applications de la morphologie mathématique était sur les images binaires et proposé par Matheron et Serra en 1964 [54]. En outre la théorie de la morphologie mathématique repose sur le fait que l’espace de l’image est un treillis complet [28] ce qui permet d’envisager le traitement d’une très large classe de données avec les opérateurs de la morphologie mathématique. En prenant en considération les objets numériques portant des informations structurelles, la morphologie mathématique a ´été développée sur des graphes, des complexes simpliciaux, et sur les hypergraphes. Ainsi le travail proposé dans cette thèse se focalise sur le cadre de la morphologie mathématique basée sur les graphes présenté dans [14]. Dans ce cadre les ensembles d’entrées et sorties des opérateurs considères sont des graphes (ensembles de sommets ainsi que des ensembles d’arêtes) et les opérateurs de base peuvent aller d’un type d’ensembles vers l’autre. Ils peuvent être combinés afin d’obtenir des opérateurs agissant sur le sous ensemble d’arêtes, sur le sous-ensemble des sommets, et sur les sous-graphes d’un graphe donné. L’objectif principal dans cette thèse est de fournir un calcul et une implémentation efficaces pour ces opérateurs morphologiques en se basant sur les graphes non pondérés. En effet, ces opérateurs dépendent d’un paramètre de taille qui spécifie le nombre d’itérations de dilatations et d’érosions élémentaires. Ainsi, le temps d’exécution associé à ces opérateurs itératifs augmente avec le paramètre de taille et la complexité est de l’ordre de O(λ.n), où n est la taille du graphe et λ le paramètre de taille. Dans notre travail, nous sommes particulièrement intéressés par les cartes de distances qui nous ont permis (par seuillage) de caractériser et d’effectuer toutes les dilatations/ érosions considérées et par conséquent tous les opérateurs propos ´es dans [14]. En premier lieu nous avons proposés trois nouvelles cartes de distance basées sur les graphes. Il s’agit des cartes de distance arête-sommet, sommet-arête et arête - arête. En plus, basé sur une nouvelle notion de chemin qui considère à la fois le nombre d’arêtes et de sommets sur le chemin, nous présentons une carte de distance sommet-sommet. Nous montrons que ces nouvelles cartes de distance mènent à des caractérisations originales de toutes les dilatations et érosions présentées dans [14]. Ensuite, des algorithmes séquentiels en temps linéaire ont été proposés afin de calculer ces nouvelles cartes de distance dans les graphes et par conséquent les opérateurs de dilatations/érosions basés sur les graphes. Toute dilatation, érosion, ouverture et fermeture sur les graphes peuvent être obtenues avec une seule itération par le seuillage de ces cartes de distance. Ainsi, ces opérateurs peuvent être calculés en temps linéaire par rapport à la taille du graphe avec une seule itération et sans aucune dépendance avec le paramètre de taille. Afin de calculer efficacement les cartes de distance proposées et les opérateurs morphologiques basés sur les graphes, nous avons développé une stratégie parallèle sur une architecture multi-cœurs à mémoire partagée qui consiste à construire d’une manière itérative les niveaux successifs des cartes de distance avec un parcours en parallèle de chaque niveau. Afin d’estimer la complexité de notre stratégie parallèle, nous proposons et démontrons des hypothèses sur le graphe et les ensembles considérés. Selon ces hypothèses, la complexité de nos algorithmes parallèles est O(n/p + K log2p) où n, p, et K sont respectivement la taille du graphe, le nombre de processeurs disponibles et le nombre de niveaux distincts de la carte de distance, respectivement. Dans l’évaluation expérimentale, nous avons fourni une description des bases de données utilisées ; Il s’agit de deux bases d’images 2D et une base des 3D maillages triangulaires texturées. Nous avons évalué la régularité des hypothèses proposées sur les bases de données considérées pour effectuer ensuite une analyse des résultats obtenus par les implémentations séquentiels et parallèle des algorithmes proposés sur les architectures cibles. Cette évaluation montre une amélioration significative en termes de temps d’exécution par rapport aux implémentations disponibles auparavant.

Actions (login required)

View Item