Flot maximal, coupe minimale, application en vision par ordinateur
Flot dans un graphe
On considère un graphe orienté (S,A), c'est-à-dire:
Un ensemble fini de sommets S
Un ensemble d'arcs qui relient certains
de ces sommets (on peut voir A comme un ensemble de
couples de S).
Parmi les sommets sont distingués: la source S, et le puit P.
À chaque arc est associée un nombre réel strictement
positif, appelé capacité.
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:
S'il existe un chemin dans le graphe résiduel de la
source vers le puit, alors le flot n'est pas
maximal.
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:
Si le flot est maximal, il n'existe pas de chemin dans le graphe
résiduel de la source vers le puit.
Algorithme d'Edmonds-Karps
Cet algorithme permet de calculer un flot maximal.
Initialisation: mettre le débit à 0.
Tant qu'il y a un chemin dans le graphe résiduel. Choisir le plus courtOn pourrait choisir un chemin quelconque - c'est l'algorithme de Ford-Fulkerson. Mais dans ce cas, la terminaison n'est pas assurée !.
Augmenter au maximum le débit le long de ce chemin.
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|2)cf Algorithmique, de Cormen et al..
Graphe de flot
Graphe résiduel
Coupe dans un graphe
On appelle coupe dans un graphe une partitionLes deux ensembles sont disjoints, et leur réunion forme l'ensemble des sommets. (VS, VP) de l'ensemble des sommets, telle que S∈VS et P∈VP.
On appelle valeur d'une coupe (VS, VP) la somme des capacités des arcs ayant leur sommet de départ dans VS, et leur sommet d'arrivée dans VP.
La figure ci-contre montre un exemple de telle coupe, de valeur 10.
On peut alors montrer le résultat suivant:
Théorème Flot Maximal/Coupe Minimale
La valeur d'un flot maximal est égal à la valeur d'une
coupe minimale.
De plus, si (A,B) est une coupe minimale, et que a est un arc ayant son départ dans A et son extrémité dans B, est saturéi.e. le débit y est égal à la capacité. par tout flot maximal.
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.
Flot maximal, coupe minimale.
La coupe est ({S, a, c}, {P, b, d, e})
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
Ii 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:
Trouver une image I minimisant E(I) = Σid(Bi,Ii)+αΣi,j pixels voisinsd(Ii,Ij) où d(a,b)=0 si a=b, et 1 sinon.
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.
Coupe 1 Valeur de la coupe : 1
Coupe 2 Valeur de la coupe : 1+α
Coupe 3 Valeur de la coupe: 2α
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
Minimiser l'énergie revient à calculer une coupe
minimale dans le graphe.
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).
Image originale
Image bruitée
Image restaurée
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.