Institut de Recherche sur l'Enseignement des Mathématiques de Paris

Les graphes de flot sont une façon de modéliser, dans un ordinateur, un réseau de routes et de gérer le trafic routier. Trouver un objet donné dans une image est difficile pour l’ordinateur qui ne perçoit qu’une série de nombres rangés dans un tableau. Ces deux problèmes semblent très différents, et pourtant les graphes de flots permettent à l’ordinateur de localiser, dans une image, des objets précis. En transformant l’image en un réseau de routes et en codant, sous forme d’équations, les propriétés de la forme que l’on souhaite extraire (couleur, forme, etc.), on peut faire calculer à l’ordinateur où se situe cet objet qui nous intéresse : cette méthode s’appelle les graph cuts. Après avoir présenté les graphes de flot et l’algorithme de Ford et Fulkerson qui permet de calculer le nombre de voitures maximal pouvant circuler dans le graphe, John Chaussard expliquera comment ce problème et sa solution s’appliquent à la localisation d’objets dans une image et le public pourra observer quelques résultats.