Architecture dédiée au traitement d'image base sur les équations aux dérivées partielles - Archive ouverte HAL Access content directly
Theses Year : 2004

Architecture dédiée au traitement d'image base sur les équations aux dérivées partielles

Eva Dejnozkova

Abstract

The image processing methods based on Partial Differetial Equations (PDEs) draw a groving attention of the scientific community. The number of applications has considerably increased with the introduction of the Level Set methods. The EDPs apply in many domains such the image improvement (non linear diffusion), the segmentation by active contours used both for static pictures (graphe of Voronoï, watershed, shortest paths, object detection) and image sequences (object tracking) or more recent methods such as shape-from-shading. The industrial applications of these methods remain very limited due to a considerable computation complexity (high iteration number) on one hand, and the difficulties of embedded system implementation (energy consumption, memory requirements) on the other hand. To our knowledge, few real time experiments on supercomputers and graphics hardware were published, and embedded applications are almost inexistent. Our goal is to propose a dedicated architecture facilitating the implementation of a real time embedded system. Regarding this objective, we propose a new algorithm (called Massive Marching) solving the Eikonal equation for computation of the distance function. It proceeds in parallel and eliminates the usage of the ordered data structures. It allows to obtain the solution either on the entire image or only on its part: the Narrow Band around the propagation front. The complexity of Massive Marching is linear. We consider that its introduction is important also for the community of Mathematical Morphology, because Massive Marching represents the algorithm allowing to obtain the watershed in parallel. Next, we propose two architecture types (i) SIMD and (ii) MIMD, based on several embedded processor cores, implementing Massive Marching in parallel or semi-parallèle. The same architecture types can be used to implement filtering algorithms as well as methods of interface evolution. The same architecture can therefore be used to implement all the steps of a complete application consisting of different types of algorithms, e.g. filtering followed by segmentation.
Les méthodes de traitement d'images fondées sur les équations aux dérivées partielles (EDP) bénéficient d'une attention particulière de la part de la communauté scientifique. Le nombre d'applications a considérablement augmenté après la formulation du problème sous forme d'ensembles de niveaux. Les EDPs s'appliquent dans de nombreux domaines tels le filtrage des images (diffusion non-linéaire), les contours actifs utilisés pour la segmentation des images statiques (graphe de Voronoï, Ligne de Partage des Eaux, plus court chemin, détection d'objets), aussi bien que des séquences d'images (suivi d'objets) ou encore des méthodes plus récentes tel le shape-from-shading. Les applications industrielles de ces méthodes sont néanmoins très limitées, d'une part par une complexité considérable de calculs (nombre d'itérations très élevé, par ex.), d'autre part par des difficultés rencontrées lors d'implantation embarquées (consommation d'énergie, exigences mémoire). Quelques expériences temps-réel ont été publiées avec des super-calculateurs ou des accélérateurs graphiques. Quant aux applications embarquées, elles sont à notre connaissance quasi-inexistantes. Notre but est de proposer une architecture dédiée, facilitant tant l'implantation temps-réel qu'embarquée. En vue de cet objectif nous proposons un nouvel algorithme de solution de l'équation Eikonale/calcul de fonction distance qui procède en parallèle, élimine l'usage des files d'attente hiérarchiques et permet d'obtenir la solution sur la totalité ou seulement sur une partie de l'image (le narrow band). La complexité de cet algorithme, nommé Massive Marching, est linéaire. Nous estimons que l'impact de Massive Marching est d'autant plus important pour la communauté de Morphologie Mathématique, qu'il s'agit du premier algorithme permettant d'obtenir en parallèle la ligne de partage des eaux non-biaisée. Ensuite, nous proposons deux types d'architecture (i) SIMD et (ii) plusieurs coeurs de processeurs embarqués implantant Massive Marching en parallèle ou semi-parallèle. Ces mêmes types d'architecture peuvent être utilisés pour implanter un filtrage aussi bien que des méthodes à évolution d'interface. La même architecture peut donc être utilisée pour implanter une application complète, composée de différents types d'algorithmes comme par exemple filtrage suivi par segmentation.
Fichier principal
Vignette du fichier
these_print_dejnozkova_v2.pdf (6.13 Mo) Télécharger le fichier

Dates and versions

pastel-00001180 , version 1 (05-04-2005)

Identifiers

  • HAL Id : pastel-00001180 , version 1

Cite

Eva Dejnozkova. Architecture dédiée au traitement d'image base sur les équations aux dérivées partielles. domain_other. École Nationale Supérieure des Mines de Paris, 2004. English. ⟨NNT : ⟩. ⟨pastel-00001180⟩
440 View
691 Download

Share

Gmail Facebook Twitter LinkedIn More