HomeResearchEnseignementMiscellaneousCurriculum vitaePublications
Digital geometryImage AnalysisOther TopicsPhdCollaborationsProjects and Grants

Image analysis outline

My original subject of research was to propose a combinatorial algorithmic approach to image analysis. The idea has been to propose a graph representation well suited for image analysis and to use graph algorithms to perform efficient regions segmentation. This works led me to investigate combinatorial maps and to propose the topological graph of frontiers to model segmented images. In the main time, I was looking for algorithms that could perform efficient region segmentation and link pixel to region in order to facilitate the build of the topological graph of frontiers. I proposed to use Union-Find algorithms and show that linear time segmentation can be achieved. Since I am working on non-parametric auto-adaptative statistical merging criteria well suited for my segmentation algorithms.These results are use on some applications, in particular for image analysis of plants.
Image Analysis
Application to analysis of plants images Imprimer Envoyer
Since 2001, results obtained in image analysis (Union-Find segmentation, Statistical merging criteria, combinatorial map modelling) have been used, in collaboration with Dr Gilles Rabatel of UMR ITAP of CEMAGREF Montpellier, to propose solutions for image analysis of plants. First works have been done by Benoît de Mezzo, a former phd sudent. We use Union-Find algorithms [FioGus:TCS96] and Topological Graph of Frontiers (Combinatorial map representation) [Fiorio:DGCI96DamBerFio:CVIU04] in order to define an edge-region segmentation algorithm to recognize adventices in natural images of plants [MezFioRab:ECPA03]. Since 2003, with Dr Gilles Rabatel and Nathalie Gorretta we work on image analysis by a mixted hyperspectral and spatial approach [GorFioRab:FRUCTISO5,GorRabRogFio:JNIS08,GorRabFioRog:RTS09].
Mise à jour le Vendredi, 17 Avril 2009 10:59
 
Statistical merging criteria Imprimer Envoyer

I am looking for homogeneous statistical criteria suitable to Union-Find Algorithms, that is criteria that don't change algorithmic complexity. The originality of our approach is to establish a brigde between approaches that introduce constraint on distributions, and are time computing, and approaches that focus on complexity, and forget the statistical relevance of the result. Our solution is based on the definition of a new theoretical model of image and on the use of concentration inequalities (see image below illustrates model of image).

Statistical theoretical model of images

It allows us to propose auto-adaptative criteria and to bound the maximal error. Moreover these criteria do not change the complexity of our Union-Find segmentation algorithm and so process is efficient in running time [FioNoc:ICTAI98,FioNoc:ICIP00,FioNoc:BMVC00]. Below, you can see some examples of segmentation of Lena.

Lena Lena segmented
Lena Top of Lena segmented
Mise à jour le Samedi, 18 Avril 2009 16:57
 
Union-Find segmentation Imprimer Envoyer

Region segmentation is a partition of the image into regions according to a test of homogeneity, where regions are connected, homogeneous and such that the merging of two adjacent regions shall not be an homogeneous region. There are two main way to achieve this result: split or merge segmentation. The first takes the image in a whole and split it into several regions until having a segmentation. It consists of starting with the smallest regions (i.e. Pixels or Points of the image) and merging them until they are considered to be optimal. We focus on the merging approach and we proposed to use Union-Find algorithms.

The general Union-Find Problem, or more precisely the disjoint set Union Problem, can be formulated as follows. Given is a set S, the groundset, of elements, pixels in the case of image segmentation that form one-element subsets at the beginning. The goal is to perform arbitrary sequences of Union and Find operations in the best time complexity possible. Here a Union works on two disjoint subsets fusing them into one; a Find identifies the subset a certain element belongs to. Classical implementations use tree data structure and implement Union and Find operations as shown on images below:

Ranked union operation Find compress operation

In [FioGus:TCS96], J. Gusted and I have proposed two linear time segmentation algorithms based on Union-Find solution, e.g. Scanline Algorithm:

Scanline algorithm Mergesquare algorithm

 

Then we studied how to optimize the memory complexity in order to garantee an optimal use of the memory and so improve pratical running time of Union-Find algorithms (see [FioGus:STACS97]). This result allow us to propose a 3d version of our segmentation algorithm (see [FioGusLan:IWCIA00]).

ctSliceAxialtr512 regGi_blanktr amiratr512 reg3D
Mise à jour le Samedi, 18 Avril 2009 09:54
 
Combinatorial map representation Imprimer Envoyer

My goal is to propose a combinatorial data structure to represent regions segmented image that is consistent with the topology of the underlying digital space. Three important points have then to be respected:

  1. frontiers must be coded, not only adjacency;
  2. inclusion of region have to managed;
  3. to be a graph structure.

Naturally I have had then interest in planar graphs and next to combinatorial maps that are sort of multi planar graph that code subdivisions space (see image below).

3mapdecomp 3mapex

My first result was the topological graph of frontier [Fiorio:th95,AhrFioGla:DGCI99] and the extraction algorithm associated. It allows to code efficiently regions segmented 2d images (see example below).

topological graph of frontiers

Nevertheless, the topological graph of frontiers doesn't easily extend itself to 3 dimensional images and above. That's why, with Prof Yves Bertrand and Dr Guillaume Damiand, we look for alternative combinatorial map representations. The result was frontiers map, topological maps and associated extraction algorithm [BerDamFio:DGCI00,BerDamFio:GBR01,DamBerFio:CVIU04].
Mise à jour le Samedi, 18 Avril 2009 10:00