Spécification de l’intervalle de disparité par pixel dans la méthode des graph cuts

Introduction

En , Vladimir Kolmogorov et Ramin Zabih proposent une méthode globale basée sur l’utilisation de graphes pour minimiser de mani`ere approchée une fonctionnelle d’énergie. L’intérˆet de cette méthode réside en deux principales caractéristiques. En premier lieu, elle ne découle pas d’une formulation variationnelle. Autrement dit, la disparité discr`ete n’est pas la discrétisation d’une fonction continue, elle peut donc en particulier prendre des valeurs non réelles (sans ˆetre infinie). Cette propriété permet de définir une étiquette qui marque les pixels comme occultés, sans devoir les mettre artificiellement en correspondance avec d’autres pixels (section 4.1). En second lieu, la stratégie de minimisation, qui repose sur l’algorithme des expansion moves, peut ˆetre gérée de mani`ere efficace en la reformulant comme des recherches de coupures minimales dans un graphe (section 4.2). Ce dernier probl`eme est bien connu depuis Ford et Fulkerson et de nombreux algorithmes existent qui le résolvent efficacement. Cependant, on verra que les performances de la méthode reposent grandement sur la valeur de certains param`etres, dont le choix peut s’avérer délicat (section 4.6). En outre, l’utilisation des expansion moves ne permet pas de minimiser exactement la fonctionnelle, mais seulement de proposer un schéma de décroissance de l’énergie (section 4.3). Si la fonctionnelle ne poss`ede pas de minima locaux, on peut raisonnablement espérer en trouver le minimum global de cette mani`ere. Malheureusement, cette propriété n’est pas assurée car la fonctionnelle n’est pas convexe. Par ailleurs, la représentabilité de l’énergie (section 4.2) introduit des contraintes quant au choix de la fonctionnelle d’énergie. Néanmoins, l’algorithme donne des résultats tr`es satisfaisants, notamment en terme de détection des occultations (voir le chapitre précédent), et dans un temps raisonnable. L’objet principal de ce chapitre est de proposer une modification de la méthode de Kolmogorov et Zabih qui permette de définir pour chaque pixel un intervalle de disparité adapté (section 4.5). Une telle possibilité permet d’utiliser l’efficacité des coupures de graphes pour densifier des cartes éparses ou de raffiner des cartes à des précisions subpixelliques. On se propose donc dans un premier temps de décrire la méthode originale, dont les différents éléments ont été détaillées dans plusieurs articles [8, 9, 3], ainsi que dans la th`ese de Kolmogorov [6]. Cette étude reprend en partie la publication IPOL [7] consacrée à cette méthode. L’objectif est d’offrir la compréhension nécessaire pour envisager les modifications souhaitées, dont les différents résultats expérimentaux sont proposés à la section 4.6.

Fonctionnelle d’énergie

Dans tout ce qui suit, on reprend l’approche de la méthode KZ2 de [8], déjà détaillée dans l’article IPOL [7]. Toutefois, nous reformulons de mani`ere différente la fonctionnelle, pour faciliter la comparaison avec celle de la méthode proposée au chapitre précédent (dont la version discr`ete est donnée dans la section 3.3.1). Pla¸cons-nous directement dans la formulation discr`ete. Les pas de discrétisation des images et de l’intervalle de disparité valent 1, ce qui conduit, en conservant les notations du chapitre précédent (paragraphe 3.3.1) à considérer le vecteur h = (1,1,1). Contrairement à la méthode étudiée dans le chapitre précédent, la disparité u h est à valeurs dans I h disp ∪ occ, o`u occ est une étiquette particuli`ere destinée à déclarer un 116 pixel occulté

Représentation d’une énergie par un graphe

On va montrer dans cette section qu’il est possible d’utiliser les graphes pour résoudre de mani`ere efficace certains probl`emes d’optimisation d’énergies. Pour cela, on introduit le concept de représentation d’une énergie par un graphe. 4.2.1 Coupure minimale et flot maximal Graphe orienté et pondéré Commen¸cons par introduire quelques définitions utiles pour la suite. On appelle graphe G le couple (V,E) o`u V est un ensemble dont les éléments sont appelés sommets (vertices en anglais) et E ⊂ V2 est l’ensemble des arcs orientés et pondérés du graphe (edges en anglais). L’orientation des arcs implique de distinguer les deux arcs (a1,a2) et (a2,a1) si a1 6= a2 ∈ V et la pondération consiste à leur attribuer une valeur cG(a1,a2) ∈ ] 0 ; +∞], appelé capacité de l’arc. On ignore les arcs de capacité nulle, ce qui revient à les supprimer de l’ensemble E. Notons qu’on accepte les arcs de capacité infinie. Pour plus d’informations sur la théorie des graphes, on pourra se reporter à [2]. Coupure d’un graphe Désormais, on suppose que le graphe G poss`ede deux sommets distincts s et t, appelés respectivement source et puits du graphe. Une coupure 1 du graphe désigne alors toute partition (V s ,V t ) des sommets telle que la source s (resp. le puits t) appartienne au sous-ensemble V s (resp. V t ). Le coˆut d’une coupure (V s ,V t ) est donnée par la somme des capacités des arcs (a1,a2) ∈ V partant de a1 ∈ Vs et aboutissant à a2 ∈ Vt .