Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d

Abstract: Dans cette thèse, nous définissons et étudions un modèle topologique de représentation d'images segmentées en 2 et 3 dimensions : la carte topologique. La définition d'un tel modèle est primordiale afin de définir des algorithmes de segmentation efficaces. Ce problème a été beaucoup étudié en dimension 2, mais les solutions proposées sont difficilement extensibles en dimension 3. Pour répondre à ce problème, nous définissons d'abord la carte topologique en dimension 2 en ayant comme préoccupation principale son extension en dimension supérieure. Nous introduisons une notion de niveau de simplification qui permet une définition progressive, chaque niveau s'obtenant simplement à partir du niveau précédent par application d'un type particulier de fusion. Cette notion permet de simplifier la définition de la carte topologique qui correspond au dernier niveau. Ces niveaux de simplification s'étendent sans difficulté majeure en dimension 3, et en dimension n. Ils facilitent également l'étude de la carte topologique et la preuve de ses propriétés. Ce modèle est en effet minimal, complet, invariant par rotation, translation et homothétie, et unique. Nous présentons des algorithmes d'extraction permettant de construire ce modèle à partir d'images segmentées. Un premier algorithme << naïf >> effectue plusieurs passes sur l'image et n'est pas linéaire en dimension 3. Nous étudions ensuite un algorithme optimal d'extraction, basé sur la notion de précode, effectuant un seul balayage de l'image et un nombre minimal d'opérations. Les niveaux de simplification permettent de regrouper les nombreux cas à traiter, en étudiant pour chaque niveau les cas supplémentaires par rapport au niveau précédent.

Keywords: Frontières interpixel, représentation d'images, segmentation en régions, carte combinatoire, codage topologique minimal, fusion, frontières interpixel.

In this thesis, we define and study a topological model of 2 and 3 dimensional segmented image representation: the topological map. The definition of such a model is essential to define efficient segmentation algorithms. This problem was studied in many different works in dimension 2, but the proposed solutions are hardly extendible in upper dimensions. To solve this problem, we first define the topological map in dimension 2, while keeping in mind our main concern, its extension in upper dimension. We introduce a notion of simplification level that allows a progressive definition, each level is obtained easily from the previous one by application of a particular type of merging. This notion allows to simplify the definition of the topological map that corresponds to the last level. Moreover, these simplification levels can be easily extended to dimension 3, even to dimension n. They also make the study of the topological map and the proof of its properties easier. Indeed, this model is minimal, complete, stable for rotation, translation and homothety, and unique. We present some extraction algorithms that allow to build this model from segmented images. A first "naive" algorithm performs several scans of the image and is not linear in dimension 3. We give then an optimal extraction algorithm based on the precod notion, that performs a single scan of the image. The simplification levels allow to group the several cases to treat, by studying for each level the new cases in relation to the previous one.