Imagerie temps réel : parallélisation d’algorithmes sur plate-forme multi-processeurs

Topological features of an object are fundamental in image processing. In many applications,including medical imaging, it is important to maintain or control the topology of the image. Howeverthe design of such transformations that preserve topology and geometric characteristics of the inputimage is a complex task, especially in the case of parallel processing.Parallel processing is applied to accelerate computation by sharing the workload among multipleprocessors. In terms of algorithm design, parallel computing strategies profits from the naturalparallelism (called also partial order of algorithms) present in the algorithm which provides two main resources of parallelism: data and functional parallelism. Concerning architectural design, it is essential to link the spectacular evolution of parallel architectures and the parallel processing. In effect, if parallelization strategies become necessary, it is thanks to the considerable improvements in multiprocessing systems and the rise of multi-core processors. All these reasons make multiprocessing very practical. In the case of SMP machines, immediate sharing of data provides more flexibility in designing such strategies and exploiting data and functional parallelism, notably with the evolution of interconnection system between processors.In this perspective, we propose a new parallelization strategy, called SD&M (Split Distribute andMerge) strategy that cover a large class of topological operators. SD&M has been developed in orderto provide a parallel processing for many topological transformations.Based on this strategy, we proposed a series of parallel topological algorithm (new or adaptedversion). In the following we present our main contributions:(1)A new approach to compute watershed transform based on MSF transform, that is parallel,preserves the topology, does not need prior minima extraction and suited for SMP machines.Proposed algorithm makes use of Jean Cousty streaming approach and it does not require any sortingstep, or the use of any hierarchical queue. This contribution came after an intensive study of allexisting watershed transform in the discrete case.(2)A similar study on thinning transform was conducted. It concerns sixteen parallel thinningalgorithms that preserve topology. In addition to performance criteria, we introduce two qualitativecriteria, to compare and classify them. New classification criteria are based on the relationshipbetween the medial axis and the obtained homotopic skeleton. After this classification, we tried toget better results through the proposal of a new adapted version of Couprie's filtered thinningalgorithm by applying our strategy.(3)An enhanced computation method for topological smoothing through combining parallelcomputation of Euclidean Distance Transform using Meijster algorithm and parallel Thinning–Thickening processes using the adapted version of Couprie's algorithm already mentioned.Les caractéristiques topologiques d'un objet sont fondamentales dans le traitement d'image. Dansplusieurs applications, notamment l'imagerie médicale, il est important de préserver ou de contrôlerla topologie de l'image. Cependant la conception de telles transformations qui préservent à la foi la topologie et les caractéristiques géométriques de l'image est une tache complexe, en particulier dans le cas du traitement parallèle.Le principal objectif du traitement parallèle est d'accélérer le calcul en partagent la charge de travail à réaliser entre plusieurs processeurs. Si on approche cet objectif sous l'angle de la conception algorithmique, les stratégies du calcul parallèle exploite l'ordre partiel des algorithmes, désigné également par le parallélisme naturel qui présent dans l'algorithme et qui fournit deux principales sources de parallélisme : le parallélisme de données et le parallélisme fonctionnelle.De point de vue conception architectural, il est essentiel de lier l'évolution spectaculaire desarchitectures parallèles et le traitement parallèle. En effet, si les stratégies de parallèlisation sont devenues nécessaire, c'est grâce à des améliorations considérables dans les systèmes de multitraitement ainsi que la montée des architectures multi-core. Toutes ces raisons font du calculeparallèle une approche très efficace. Dans le cas des machines à mémoire partagé, il existe un autreavantage à savoir le partage immédiat des données qui offre plus de souplesse, notamment avec l'évolution du système d'interconnexion entre processeurs, dans la conception de ces stratégies etl'exploitation du parallélisme de données et le parallélisme fonctionnel.Dans cette perspective, nous proposons une nouvelle stratégie de parallèlisation, baptisé SD&M(Split, Distribute and Merge) stratégie qui couvrent une large classe d'opérateurs topologiques.SD&M a été développée afin de fournir un traitement parallèle de tout opérateur basée sur latransformation topologique. Basé sur cette stratégie, nous avons proposé une série d'algorithmestopologiques parallèle (nouvelle version ou version adapté). Nos principales contributions sont :(1)Une nouvelle approche pour calculer la ligne de partage des eaux basée sur ‘MSF transform'.L'algorithme proposé est parallèle, préserve la topologie, n'a pas besoin d'extraction préalable deminima et adaptée pour les machines parallèle à mémoire partagée. Il utilise la même approchede calcule de flux proposé par Jean Cousty et il ne nécessite aucune étape de tri, ni l'utilisationd'une file d'attente hiérarchique. Cette contribution a été précédé par une étude intensive desalgorithmes de calcule de la ligne de partage des eaux dans le cas discret.(2)Une étude similaire sur les algorithmes d'amincissement a été menée. Elle concerne seizealgorithmes d'amincissement qui préservent la topologie. En sus des critères de performance,nous somme basé sur deux critères qualitative pour les comparer et les classés. Après cetteclassification, nous avons essayé d'obtenir de meilleurs résultats grâce avec une version adaptéede l'algorithme d'amincissement proposé par Michel Couprie.(3)Une méthode de calcul amélioré pour le lissage topologique grâce à la combinaison du calculparallèle de la distance euclidienne (en utilisant l'algorithme Meijster) et l'amincissement/épaississement parallèle (en utilisant la version adaptée de l'algorithme de Couprie déjàmentionné)