Skip to Main content Skip to Navigation

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

Raffi Enficiaud 
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.
Document type :
Complete list of metadata

Cited literature [56 references]  Display  Hide  Download
Contributor : Ecole Mines ParisTech Connect in order to contact the contributor
Submitted on : Monday, February 4, 2008 - 8:00:00 AM
Last modification on : Wednesday, November 29, 2017 - 3:02:33 PM
Long-term archiving on: : Monday, July 26, 2010 - 8:13:47 PM


  • HAL Id : pastel-00003122, version 1



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. ⟨pastel-00003122⟩



Record views


Files downloads