Algorithmes multidimensionnels et multispectraux en Morphologie Mathématique : approche par méta-programmation. - Archive ouverte HAL Access content directly
Theses Year : 2007

Algorithmes multidimensionnels et multispectraux en Morphologie Mathématique : approche par méta-programmation.

Raffi Enficiaud
  • Function : Author

Abstract

This PhD focuses on algorithms in the field of Mathematical Morphology and Image Processing, from the point of view of modern programming techniques. Computer science is often considered as a simple witness of hardware improvements dictated by Moore's law. However, software techniques evolve as well, and new programming tools such as metaprogramming are now available for the scientific community. Programming is of paramount interest for image processing; for this task, meta-programming brings significant improvements both in scientific terms by providing a powerful mean of abstraction, and in terms of practicability by providing portability, development centralizing, error reduction, etc. The work presented in this thesis is structured around the elaboration of a general algorithmic framework for - morphological - image processing. Furthermore, examples drawn from concrete industrial applications (in the fields of visual surveillance and car security) are described in order to illustrate the use of some of these developments. Prior to any algorithmic development, the thesis first proposes a model identifying underlying mathematical notions and their connections: data structures - images, graphs, topology, orders, and priority queues - are revisited with the meta-programming paradigm. This model clearly distinguishes the different actors and reaches the targeted abstraction level. Using specific mechanisms, the automation of numerous tasks is enabled with the compiler. Algorithms are then closer in description to the original mathematical formulations. These developments open for a wide area of research, including N dimensional and hyperspectral images which we further investigate in the following. The support of both N dimensional imaging and generic programming philosophy led us to define an exact distance transform algorithm. The hypotheses assumed regarding the underlying distance are few (homogeneity in space and convexity of the unit ball), which allows the use of a wide class of functions. Following a theoretical study, an algorithm is proposed based on ordered propagation. The error-proneness on many examples in 4D space (Euclidian, L5, oriented, non-isometric) is also illustrated. A different approach uses morphological distance transforms, popular in the field of mathematical morphology. This approach has recently seen a significant extension from binary to grey-scale images: Beucher's « quasi-distance ». In this thesis, an algorithm is proposed which features lower complexity than the one proposed originally for this purpose. The handling of colour, or more generally of hyperspectral images (i.e. vectorial data), is rather delicate in the field of Mathematical Morphology. This thesis tackles this issue, and proposes three different approaches: the use of colour metrics, then of local statistics and finally of algebraic lattices by means of lexicographical orders. The programming framework introduced in the document suits all the needs of such approaches. Colour metrics enable the definition of morphological gradients in colour spaces. However, this definition is computationally expensive and practically unusable for wide neighbourhoods. In this case, local statistics provide an interesting alternative solution. Focus was put on circular statistics in HLS colour space, which led to a chromatic gradient. Lexicographical orders also provide an algebraic framework suitable for mathematical morphology in colour spaces. Using the framework proposed in this thesis, such orders do not require a fundamental revisiting of the existing algorithms. Operators based on orders and geodesy (extrema, reconstructions, granulometries ...) are extended with a very low cost in development. These abstract considerations are illustrated within two concrete applications: skin colour characterization robust to illumination changes (automotive security context), and motion detection (visual surveillance). Finally, this thesis deals with the issue of segmentation - more precisely, the watershed algorithm. An efficient implementation of the watershed uses hierarchically ordered queues. However the original algorithm using this method leads to some bias. The algorithm proposed in this thesis corrects these biases. Again, a great benefit comes from the proposed framework and, as a result, the algorithm is bound neither to space nor to relief data: watersheds in 4D, on real or colour images are now possible. Region construction is then modified in order to have a finer control on segmentations from a few numbers of markers. The first modification brings external information (e.g. colour or statistical consistency) using a cost function, computed either on the contour or the interior of the region. The second modification is based on contours' local geometrical configuration and simulates a viscous flooding.
Au cours de ces travaux de thèse, nous nous sommes intéressés d'un point de vue global aux algorithmes en Traitement d'Image et plus particulièrement en Morphologie Mathématique, selon certaines techniques nouvelles de programmation. L'évolution matérielle des moyens informatiques suit les prédictions de la loi de Moore. Cependant, une évolution parallèle, d'ordre logicielle, met à la disposition de la recherche scientifique des moyens de programmation nouveaux, dont la méta-programmation. Les avantages sont considérables, tant en terme scientifique par les possibilités offertes, qu'en termes simplement pratiques (portabilité, capitalisation des développements, réduction des erreurs, etc.). La présentation des travaux est structurée autour de la conception d'une bibliothèque de traitement - morphologique - d'image. Les différents aspects sont illustrés en partie par des exemples pris dans les domaines de la vidéosurveillance et de la sécurité automobile, et issus de projets industriels. Nous présentons dans un premier temps le cadre informatique utilisé pour l'écriture algorithmique. Afin de rendre efficace l'utilisation des nouvelles techniques de programmation, une étude préalable des notions mathématiques en Morphologie Mathématique - images, graphes, relations d'ordre, voisinages, éléments structurant, ... -, ainsi que des outils informatiques associés, est réalisée. La séparation correcte des rôles permet en outre l'écriture des structures indépendamment de la nature des données qu'ils contiennent, l'automatisation de nombreuses opérations par le compilateur, et une écriture algorithmique fidèle à une formulation mathématique. La conjonction de ces développements ouvre un grand champ d'exploration comme celui émanant des images nD et hyperspectrales, dont nous nous proposons d'explorer certains aspects. Le support des images nD associé à la programmation générique a sollicité le développement d'un algorithme de transformée exacte en distance. Les hypothèses sur la fonction distance sont faibles (homogénéité dans l'espace et convexité de la boule unité associée) afin d'utiliser les mêmes développements pour une large classe de fonction. Suite à une étude théorique, nous proposons un algorithme de calcul basé sur des propagations. Le même algorithme est utilisé pour l'ensemble des illustrations (fonctions de distance - L2, L5, orienté, non isométrique, ... - sur des images 4D). Les transformées morphologiques en distance sont d'approche totalement différente et d'usage courant en morphologie mathématique. Elles connaissent actuellement de nouveaux développements grâce à l'extension numérique proposée par Beucher: les « quasi-distances ». Nous proposons un algorithme de calcul rapide de ces distances. La couleur et plus généralement les images multispectrales (données vectorielles) sont d'une manipulation délicate en morphologie mathématique. Nous présentons trois approches complémentaires: l'utilisation de métriques couleurs, des statistiques locales et enfin les relations d'ordre lexicographique. Notre cadre informatique et algorithmique est parfaitement adapté à ces trois types de traitement. Le cadre métrique permet d'étendre la définition du gradient morphologique aux espaces couleurs, et plusieurs métriques dans Lab et HLS sont envisagées. Cette formulation est cependant coûteuse en termes de calcul et devient impraticable lorsque le voisinage utilisé pour le gradient s'agrandit. L'usage de statistiques locales permet de contourner ce problème. Nous nous sommes particulièrement intéressés à des statistiques circulaires dans HLS, ce qui nous a amené à la définition d'un gradient chromatique dans cet espace. Enfin, l'utilisation de relation d'ordre lexicographique étend le cadre algébrique classique à la couleur, sans modification fondamentale des algorithmes. Dans cette optique, nous verrons quels sont les moyens à notre disposition pour étendre la plupart des opérateurs (extrema, reconstruction, granulométries, ...) en maintenant un coût de développement bas. Deux études illustrent ces développements : la caractérisation chromatique de la peau, robuste aux changements d'illumination (contexte automobile), et la détection des zones de mouvement (vidéosurveillance). Le dernier sujet d'intérêt concerne la segmentation, et plus particulièrement l'algorithme de ligne de partage des eaux. L'implémentation de référence à l'aide de files d'attente hiérarchiques conduit à certains biais que nous corrigeons. L'algorithme proposé étant générique, nous l'appliquons sur des images de dimension 4, sur des reliefs en précision flottante ou couleur. Nous modifions ensuite la construction des bassins versants de manière à contourner certaines difficultés rencontrées lors de la segmentation avec un nombre faible de marqueurs. La première modification injecte dans le processus de propagation une information extérieure exprimée sous forme de fonction de coût. Cette fonction concerne aussi bien le contour que l'intérieur de la région en cours de construction. La seconde modification utilise une contrainte locale et rend le fluide visqueux. Des analogies sont établies entre ces nouvelles propagations et les équations d'évolution de courbe à l'aide de dérivées partielles.
Fichier principal
Vignette du fichier
PhD_Raffi_Enficiaud.pdf (51.21 Mo) Télécharger le fichier
Loading...

Dates and versions

pastel-00003122 , version 1 (04-02-2008)

Identifiers

  • HAL Id : pastel-00003122 , version 1

Cite

Raffi Enficiaud. Algorithmes multidimensionnels et multispectraux en Morphologie Mathématique : approche par méta-programmation.. Mathematics [math]. École Nationale Supérieure des Mines de Paris, 2007. English. ⟨NNT : ⟩. ⟨pastel-00003122⟩
559 View
192 Download

Share

Gmail Facebook Twitter LinkedIn More