L'optimisation par coupe de graphe est une technique mathématique utilisée pour trouver le minimum d'une fonction d'énergie définie sur un graphe. C'est un outil fondamental en vision par ordinateur et en apprentissage automatique, où de nombreux problèmes peuvent être formulés comme l'attribution d'étiquettes à des pixels ou à des points de données, tout en équilibrant les coûts unaires (le coût d'attribution d'une étiquette particulière à un nœud) et les coûts par paires (le coût d'attribution de certaines combinaisons d'étiquettes à des nœuds adjacents). La technique exploite des algorithmes efficaces issus de l'optimisation combinatoire, notamment la coupe minimale/flot maximal, pour trouver des solutions globalement optimales ou quasi optimales pour certaines classes de fonctions d'énergie.
L'idée centrale est de représenter le problème de minimisation d'énergie comme un graphe, où les nœuds représentent les variables (par exemple, les pixels) et les arêtes représentent les interactions entre elles. Un nœud source et un nœud puits sont ajoutés, et les capacités des arêtes sont définies en fonction des coûts unaires et par paires. Une coupe minimale - l'ensemble des arêtes de plus petite capacité totale qui sépare la source du puits - correspond alors à l'étiquetage optimal. Cette approche est particulièrement puissante car les problèmes de coupe minimale peuvent être résolus en temps polynomial à l'aide d'algorithmes comme la méthode push-relabel ou l'algorithme de Boykov-Kolmogorov, qui est très efficace pour les graphes structurés en grille courants dans le traitement d'images.
Développement historique
Les fondements de l'optimisation par coupe de graphe reposent sur le théorème classique du flot maximal et de la coupe minimale, prouvé par Lester Ford et Delbert Fulkerson en 1956, et sur le développement ultérieur d'algorithmes efficaces pour calculer les flots maximaux. L'application de ces idées à la vision par ordinateur a commencé à la fin des années 1980 et au début des années 1990, avec des chercheurs comme Yuri Boykov et Olga Veksler qui ont été les pionniers de l'utilisation des coupes de graphe pour des problèmes tels que la segmentation d'images et la correspondance stéréo. Un article fondateur de Boykov, Veksler et Ramin Zabih en 2001 a introduit les algorithmes d'alpha-expansion et d'échange alpha-bêta, qui ont étendu les coupes de graphe aux problèmes multi-étiquettes avec des coûts par paires non sous-modulaires, rendant la technique largement applicable.
Formulation mathématique
L'optimisation par coupe de graphe traite généralement des fonctions d'énergie de la forme : E(L) = somme sur les pixels p de D_p(L_p) + somme sur les paires (p,q) de V_pq(L_p, L_q), où L est un étiquetage, D_p est le terme de données unaire, et V_pq est le terme de lissage par paires. Pour les problèmes d'étiquetage binaire (deux étiquettes), l'énergie est représentable par un graphe si les termes par paires sont sous-modulaires, ce qui signifie V(0,0) + V(1,1) <= V(0,1) + V(1,0). Dans ce cas, le minimum global exact peut être trouvé via un seul calcul de coupe minimale. Pour les problèmes multi-étiquettes, l'algorithme d'alpha-expansion déplace itérativement les étiquettes, chaque étape résolvant un sous-problème binaire, et garantit une solution dans un facteur connu de l'optimum global.
Applications en vision par ordinateur
L'optimisation par coupe de graphe est un outil essentiel en vision par ordinateur depuis plus de deux décennies. Ses principales applications incluent :
- Segmentation d'images : Séparer le premier plan de l'arrière-plan en attribuant une étiquette à chaque pixel, avec des termes unaires basés sur des modèles de couleur et des termes par paires encourageant des contours lisses.
- Correspondance stéréo : Calculer des cartes de disparité à partir de paires d'images, où l'énergie pénalise les différences d'intensité des pixels entre les points correspondants.
- Restauration et débruitage d'images : Reconstruire des images propres à partir d'observations bruitées en minimisant une énergie qui équilibre la fidélité aux données avec le lissage.
- Analyse d'images médicales : Segmenter des structures anatomiques dans des scanners CT ou IRM, où les coupes de graphe fournissent des solutions robustes et efficaces.
Relation avec l'apprentissage automatique
En apprentissage automatique, l'optimisation par coupe de graphe apparaît dans plusieurs contextes. Elle est utilisée dans la prédiction structurée, où la sortie est un ensemble d'étiquettes interdépendantes, comme dans la segmentation sémantique avec des champs aléatoires conditionnels (CRF). Les modèles d'apprentissage profond, en particulier les réseaux de neurones convolutifs, intègrent souvent les coupes de graphe comme étape de post-traitement pour affiner les prédictions au niveau des pixels. De plus, les coupes de graphe ont été appliquées à des problèmes en apprentissage automatique tels que le regroupement et la sélection de caractéristiques, où le cadre d'optimisation fournit une manière fondée d'incorporer les relations par paires.
Algorithmes et implémentations
Plusieurs algorithmes ont été développés pour résoudre efficacement le problème de coupe minimale. L'algorithme de Boykov-Kolmogorov, introduit en 2004, est spécifiquement conçu pour les graphes en grille et est largement utilisé en vision par ordinateur en raison de sa rapidité et de sa faible empreinte mémoire. D'autres approches incluent l'algorithme push-relabel, qui est plus général et souvent utilisé dans les problèmes à grande échelle. Des implémentations sont disponibles dans des bibliothèques telles qu'OpenCV et des packages spécialisés comme la bibliothèque Maxflow de Boykov et Kolmogorov. Des recherches récentes ont également exploré des versions accélérées par GPU pour traiter des images haute résolution dans des applications en temps réel.
Limitations et extensions
La principale limitation de l'optimisation par coupe de graphe est qu'elle ne garantit l'optimalité globale que pour les énergies binaires sous-modulaires ; pour des problèmes plus complexes, elle fournit des solutions approximatives. De plus, les exigences en mémoire et en calcul peuvent devenir prohibitives pour de très grands graphes. Pour remédier à ces problèmes, les chercheurs ont développé des extensions telles que les coupes de graphe hiérarchiques, qui opèrent sur des grilles allant du grossier au fin, et les coupes de graphe continues, qui gèrent des espaces d'étiquettes non discrets. Des travaux récents ont également exploré la combinaison des coupes de graphe avec le apprentissage profond pour apprendre les paramètres d'énergie directement à partir des données, ce qui améliore les performances sur des tâches comme la segmentation d'images.
Voir aussi
- Vision par ordinateur
- Minimisation d'énergie
- Champ aléatoire conditionnel
- Théorème du flot maximal et de la coupe minimale
Références
- Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence.
- Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence.
- Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics.