Page principale

Flot maximal, coupe minimale, application en vision par ordinateur

Flot dans un graphe

Le problème est alors le suivant. On cherche à faire passer un flot maximal d'un liquide (non compressible), de la source vers le puit - le débit dans chaque arc n'excédant pas sa capacité. Autrement dit, on cherche une fonction f de l'ensemble des arcs dans R telle que:

• pour tout arc a, 0≤f(a)≤c(a), où c(a) est la capacité de l'arc.
• pour tout sommet autre que la source ou le puit, la somme des débits des arcs entrants est égal à la somme des débits des arcs sortants.

On parle de flot pour une telle application. On cherche à déterminer un flot maximal, dans le sens où

• La somme des débits des arcs sortants de la source est maximale.

Voici à droite un exemple de flot.
Il n'est cependant pas maximal: on peut par exemple l'améliorer en rajoutant un débit de 1 sur le chemin S-a-b-d-e-P - passer la souris sur le graphe pour voir apparaitre les modifications correspondantes.
À noter que l'arc b-a est parcouru «à l'envers», ce qui revient à diminuer son débit.

Afin de détecter ce type de chemin améliorant, on peut utiliser le graphe graphe résiduel d'un graphe muni d'un flot, qui est un graphe orienté indiquant les augmentations (ou diminutions) de débit possibles sur chaque arc. Passer la souris sur la figure ci-contre pour visualiser le graphe des flots de départ.
On a alors le résultat suivant:

En effet, on peut alors améliorer le flot en ajoutant aux arcs du chemin le minimum des valeurs le long de ce chemin dans le graphe résiduel. Par contraposée:

Algorithme d'Edmonds-Karps

Cet algorithme permet de calculer un flot maximal. L'analyse sa correction, de sa terminaison et de sa complexité n'est pas évidente. On peut montrer qu'il termine, renvoie effectivement un flot maximal, et que sa complexité est O(|S||A|²)cf Algorithmique, de Cormen et al..

Coupe dans un graphe

La figure ci-contre montre un exemple de telle coupe, de valeur 10.
On peut alors montrer le résultat suivant:
Le fait que la valeur de tout flot soit inférieure à la valeur de toute coupe est facile, et fournit une inégalité. L'égalité est un peu plus délicate, une preuve peut-être par exemple trouvée dans Algorithmique (Cormen et al.) Une coupe minimale peut donc être vue comme un goulot d'étranglement pour le flot.

Application au débruitage d'images

Voici une application de ce que nous venons de voir en traitement d'image. Considérons une image (en noir et blanc), et la même image, qui a été bruitée.

On souhaite «débruiter» la seconde image pour retrouver la première.
On doit donc reconstituer une image de même taille que l'image bruitée B, en décidant pour chaque pixel i s'il doit être blanc ou noir. On notera I l'image reconstituée, et I_i la valeur du pixel i, avec la convention 0=noir, 1=blanc.
On reformule le problème du débruitage de la façon suivante: Intuitivement:

• La première somme traduit le fait qu'un pixel de I a tendance à avoir la même couleur que le pixel correspondant dans B (terme d'attache aux données). Cette somme est minimale (nulle) si et seulement si I et B sont identiques.
• La seconde somme traduit le fait que la couleur d'un pixel est «attirée» par la couleur de ses voisins dans l'image débruitée (terme de régularité). Cette somme est minimale si et seulement si l'image débruitée est unie !
• Le paramètre α règle l'importance relative des 2 sommes.

Il s'agit d'un problème d'optimisation pour l'énergie E. Ce type de problème est très étudié, et difficile à résoudre en général. Mais ici, les coupes minimales vont permettre d'arriver rapidement à une solution optimale. Pour simplifier, considérons le cas d'une image à 1 dimension, constituée de 4 pixels, i, j, k et l. On suppose que leurs couleurs sont respectivement noir, noir, blanc, noir dans l'image bruitée. On va lui faire correspondre le graphe ci-contre.

On va alors interpréter une coupe dans ce graphe de la façon suivante:

• tout pixel relié à la source sera colorié en blanc dans l'image débruitée
• tout pixel relié au puit sera colorié en noir dans l'image débruitée

Regardons ci-dessous quelques coupes possibles. Dans tous les cas la valeur de la coupe est égale à la valeur de l'énergie de l'image débruitée correspondante. Et donc Ce que l'on peut faire de rapidement (et de façon optimale) en calculant un flot maximal. Dans l'exemple jouet précédent, l'image débruitée sera entièrement noire si α>1/2 (forte régularité imposée - cas de la coupe 1), et identique à l'image bruitée si α<1/2 (faible régularité imposée - cas de la coupe 3).
Ce formalisme se généralise aisément à des images à 2 dimensions. Le simulateur ci-dessous montre le graphe ainsi que les résultats obtenus par cette méthode pour débruiter de petites images 10×10. Les arcs saturés à la fin du calcul sont tracés en jaune dans le graphe. Les patchs de pixels gris dans l'image restaurée sont tels que le choix de les colorier en blanc ou en noir ne modifie pas l'énergie (dans le graphe, ils peuvent indifféremment passer d'un côté ou de l'autre d'une coupe minimale).

Pour aller plus loin

Le principe ci-dessus peut être développé pour débruiter des images (de taille réelle) en niveau de gris ou en couleur. Pour obtenir de bonnes performances en pratique, il faut alors développer des algorithmes de calculs de flots maximaux plus efficacescf Algorithmique, de Cormen et al., ou An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision de Boykov et Kolmogorov (2004).

Il peut également s'appliquer à de nombreux autres problèmes de vision par ordinateur : segmentation d'image, défloutage, reconstruction stereo... Un tour d'horizon (un peu daté) ainsi que de nombreuses références sur le sujet peuvent être trouvés dans le document suivant.