Prof. Dominique de Werra

Operations Research Group ROSE, EPFL

April 25, 2008, 14:15, Room ME B3 31 (click here for the map)

Discrete tomography problems

En tomographie discrète l’un des problèmes de base est la reconstruction d’une image à partir de ses projections (horzontales et verticales). En d’autres termes on a un tableau m x n où chaque case correspond à un pixel qui peut avoir l’une des couleurs 1,2,…, k. On donne pour chaque rangée (ligne ou colonne) le nombre de pixels de chaque couleur qui s’y trouvent . Il s’agit alors de voir si l’on peut construire une affectation de couleurs aux pixels qui satisfasse ces conditions de projection. Des modèles de graphes ont été proposés pour aborder ces problèmes et on en a étudié diverses variations et généralisations. Ceci a permis de formuler divers problèmes d’ordonnancement en particulier qui n’ont rien de tomographique. Nous discuterons certaines de ces variations. Nous montrerons quels sont les problèmes qui sont facilement solubles et nous étudierons la complexité d’autres problèmes. Nous montrerons comment divers modèles classiques de recherche opérationnelle permettent d’appréhender des cas particuliers du problème de la reconstruction d’image et nous mentionnerons quelques problèmes ouverts.

Bio