2D and 3D Voronoi Diagrams, applications in image analysis

The aim of this Ph.D. thesis is to show how computational geometry in the general case and the Voronoi diagram in the particular case contribute to image analysis. The purpose of image analysis is the description of the image content in order to interpret it and make a decision. Computational geometry is used to find optimal algorithms to solve geometric problems. We are interested here in the representation image problem. We will propose a solution based on the partitionning of the image content. Among the various solutions to partitionning, we will specifically develop the Voronoi model. The 3D shape codage by skeletons will then be developed as it relates to the generalized 3D Voronoi diagram. Image segmentation is an important problem in image analysis. We will present a new approach in a pyramidal environment, initialized by the Voronoi diagram and controled by Hopfiel neural networks. Finally, Markov random field will be used to determine an optimal partitionning in such a way which is still to be defined.Cette these est axee sur la cooperation entre l'analyse d'images et la geometrie algorithmique sur la base des diagrammes de Voronoi et de Delaunay. Le propos de l'analyse d'images est la description du contenu d'une image,en vue de son interpretation et d'une prise de decision. La geometrie algorithmique quant a elle consiste a trouver des algorithmes efficaces en vue de resoudre des problemes a caractere geometrique. Nous nous interesserons ici au probleme de representation des images par des partitionnements plus ou moins complexes, adaptes ou non au contenu informatif des images. Parmi ces partitionnements, nous developperons plus particulierement celui en regions de Voronoi. Nous aborderons ensuite le probleme du codage de formes tridimensionnelles par leur squelette qui est lie aux diagramme de Voronoi Generalise 3D. Nous montrerons enfin comment utiliser les partitionnements en region de Voronoi dans un contexte pyramidal controle par un reseau de Hopfield en vue de la segmentation, et dans un contexte markovien en vue de trouver un partitionnement repondant a une certaine optimalite