Graph cuts et applications

Cédric ALLENESeptembre 2004

Graph cutsGraph cutsetet

applicationsapplications

Graphcut textures:Graphcut textures:Image and video synthesisImage and video synthesis

using Graph Cutsusing Graph Cuts

Article de Article de Vivek KwatraVivek Kwatra, Arno Schödl, , Arno Schödl, Irfan Essa, Greg Turk et Aaron BobickIrfan Essa, Greg Turk et Aaron Bobick

pour le SIGGRAPH 2003pour le SIGGRAPH 2003

Travail basé sur l’article

Coupe Coupe CC ( (cutcut) sur le graphe ) sur le graphe GG entre entre xx et et yy::Ensemble d’arcs tels que tout chemin de Ensemble d’arcs tels que tout chemin de xx vers vers yy passe par au moins un de ces arcs passe par au moins un de ces arcs

Capacité de la coupe Capacité de la coupe CC = = ΣΣ capacité des arcs de capacité des arcs de CC

Recherche de la coupe minimum entre Recherche de la coupe minimum entre xx et et yy::Equivaut à chercher le flot maximum de Equivaut à chercher le flot maximum de GG entre entre xx et et y y (algorithme de Ford et Fulkerson par (algorithme de Ford et Fulkerson par exemple)exemple)

Intérêt:Intérêt:Permet de minimiser une énergie Permet de minimiser une énergie

représentée par la capacité des arcsreprésentée par la capacité des arcs

et de segmenter en 2 zones:et de segmenter en 2 zones:

aval et amont de la coupeaval et amont de la coupe

Théorie des Graph CutsThéorie des Graph Cuts

PlanPlan1)1) Recherche de jonctions entre images via Recherche de jonctions entre images via

les Graph Cutsles Graph Cuts

2)2) Génération de texturesGénération de textures

3)3) Inpainting: reconstruction de parties Inpainting: reconstruction de parties manquantesmanquantes

4)4) Multiway Cuts et texture "optimale"Multiway Cuts et texture "optimale"

5)5) Développements futurs et perspectivesDéveloppements futurs et perspectives

- 1 -- 1 - Recherche de jonctionsRecherche de jonctions

entre images entre imagesvia les Graph Cutsvia les Graph Cuts

Principe de jonctionPrincipe de jonction

État initial:État initial:- Deux images en partie superposéesDeux images en partie superposées

Objectif:Objectif:- Trouver la jointure sur la zone de superposition qui donnera visuellement la Trouver la jointure sur la zone de superposition qui donnera visuellement la

meilleure délimitation de la région à plaquer sans dénaturer l’imagemeilleure délimitation de la région à plaquer sans dénaturer l’image

Exemple de jonction

Utilité de la jonctionUtilité de la jonction

Permet de "coller" deux images ensemble:Permet de "coller" deux images ensemble:

Construction basique du grapheConstruction basique du graphe Nb nœuds = 1 par pixel de la zone de jonctionNb nœuds = 1 par pixel de la zone de jonction

+ 1 représentant le reste de la région A (+ 1 représentant le reste de la région A (sourcesource))

+ 1 représentant le reste de la région B (+ 1 représentant le reste de la région B (seekseek)) Arcs non orientés reliant les nœuds:Arcs non orientés reliant les nœuds:

- des pixels de la zone de jonction entre eux selon le 4-voisinnage des pixels des pixels de la zone de jonction entre eux selon le 4-voisinnage des pixels correspondantscorrespondants

- des pixels du bord de la zone de jonction au nœud symbolisant le reste de la des pixels du bord de la zone de jonction au nœud symbolisant le reste de la pièce (pièce (patchpatch) correspondante) correspondante

Exemple de graphe pour une zone de jonction de 3x3 pixels

Coût des arcsCoût des arcs

tBtAsBsABAtsM ,,,

Arcs touchant au Arcs touchant au source/seeksource/seek = = ∞∞ Arcs Arcs reliant 2 noeuds "pixels" voisins = M(s,t,A,B),reliant 2 noeuds "pixels" voisins = M(s,t,A,B),

qualité de correspondance entre les pixels des images à lier qualité de correspondance entre les pixels des images à lier ((matching quality cost)matching quality cost) M(s,t,A,B), avec: M(s,t,A,B), avec:

s et t deux positions de pixels adjacentss et t deux positions de pixels adjacents A et B les deux images à lierA et B les deux images à lier

Graph Cuts:Graph Cuts:

Recherche de la coupe minimum du grapheRecherche de la coupe minimum du graphe

Application:Application:

Trouver la jointure (Trouver la jointure (cutcut; ensemble d’arcs) qui minimise les différences entre les ; ensemble d’arcs) qui minimise les différences entre les images de part et d’autre de celle-ci (critère de coût des arcs)images de part et d’autre de celle-ci (critère de coût des arcs)

Recherche de jointure

Recherche de la jointure,Recherche de la jointure,Graph CutsGraph Cuts

Comment tenir compte des disparités dues à la présence Comment tenir compte des disparités dues à la présence d’anciennes jointures dans la sortie déjà calculée ?d’anciennes jointures dans la sortie déjà calculée ?

Cas particulier:Cas particulier:présence d’anciennes jointuresprésence d’anciennes jointures

Soient:Soient:- B: la région que l’on souhaite B: la région que l’on souhaite

plaquerplaquer

- A: la sortie déjà calculée, avec A: la sortie déjà calculée, avec As et At les régions dont les As et At les régions dont les pixels s et t en sortie sont pixels s et t en sortie sont originaires,originaires,

- s et t: des nœuds de pixels s et t: des nœuds de pixels reliés par un arc de l’ancienne reliés par un arc de l’ancienne jointure,jointure,

Rajout d’un nœud supplémentaire à la place des Rajout d’un nœud supplémentaire à la place des arcs de l’ancienne jointure:arcs de l’ancienne jointure:

- relié au nœud de la région à plaquer,relié au nœud de la région à plaquer,

coûtcoût:: M(s,t,AM(s,t,Ass,A,Att)), , la valeur de la valeur de

l’ancienne jointure,l’ancienne jointure,

- relié à chacun des deux nœuds de part et relié à chacun des deux nœuds de part et d’autre de l’ancienne jointure,d’autre de l’ancienne jointure,

coûtcoût:: M(s,t,AM(s,t,Ass,B),B) pour l’arc pour l’arc

relié au nœud du pixel srelié au nœud du pixel s

M(s,t,B, AM(s,t,B, Att)) pour l’arc pour l’arc

relié au nœud du pixel trelié au nœud du pixel t

Cas particulier:Cas particulier:présence d’anciennes jointuresprésence d’anciennes jointures

Construction de graphe en tenant compte d’une ancienne jointure

(en jaune: désignation des patchs servant à calculer le"matching quality cost" entre les deux pixels pour un arc)

Présentation dans le cas 1D:Présentation dans le cas 1D:

Cas particulier:Cas particulier:présence d’anciennes jointuresprésence d’anciennes jointures

Graphe avec une ancienne jointure en 1D

Intérêt des 3 arcs des nœuds de jointures:Intérêt des 3 arcs des nœuds de jointures:

Cas particulier:Cas particulier:présence d’anciennes jointuresprésence d’anciennes jointures

Exemple de coupe dans un graphe avec anciennes jointures

Nouveau calcul de qualité de correspondance:Nouveau calcul de qualité de correspondance:

Atténuation des jointures par lissageAtténuation des jointures par lissage

Améliorations techniquesAméliorations techniques

tGsGtGsG

BAtsMBAtsM

dB

dB

dA

dA

,,,

,,,'

Avec:Avec: - - ; ; - - dd, la direction de l’arc entre , la direction de l’arc entre ss et et tt;; - - GGdd

XX, le gradient selon la direction , le gradient selon la direction dd de l’image de l’image XX

tBtAsBsABAtsM ,,,

- 2 -- 2 -Génération de texturesGénération de textures

IntroductionIntroductionObjectifObjectif::

Générer une texture visuellement similaire à une Générer une texture visuellement similaire à une image plus petiteimage plus petite

PrincipePrincipeItérations de deux étapesItérations de deux étapes::

PositionnementPositionnement de la portion d’image dans la sortie de la portion d’image dans la sortie ((offsetoffset))

Choix de la partie à conserver, Choix de la partie à conserver, jonctionjonction avec les avec les portions d’images déjà placées (portions d’images déjà placées (seamseam))

Plusieurs méthodes pour le choix de l’Plusieurs méthodes pour le choix de l’offset offset et de la région à plaquer:et de la région à plaquer:

• Placement aléatoirePlacement aléatoire,,• Placement par correspondancePlacement par correspondance

Méthodes de placementMéthodes de placement

Résultats obtenusRésultats obtenus

DéroulementDéroulement

Résultats avec Résultats avec offsetoffset aléatoire aléatoire

Résultats avec Résultats avec offsetoffset aléatoire aléatoire

Résultats avec Résultats avec offsetoffset aléatoire aléatoire

- 3 -- 3 -Inpainting:Inpainting:

reconstruction de parties reconstruction de parties manquantesmanquantes

Sélection de Sélection de patchespatches placés au bord de la région manquante par placés au bord de la région manquante par correspondancecorrespondance

Reconstruction par simple Reconstruction par simple correspondancecorrespondance

Sélection de Sélection de patchespatches placés au bord de la région manquante par placés au bord de la région manquante par correspondance avec recherche de la meilleure jonctioncorrespondance avec recherche de la meilleure jonction

Reconstruction par recherche de Reconstruction par recherche de jointuresjointures

- 4 -- 4 -Multiway CutsMultiway Cuts

et texture "optimale"et texture "optimale"

Graphe G avec N nœuds terminauxGraphe G avec N nœuds terminaux

Coupe Coupe CC ( (cutcut) sur le graphe ) sur le graphe GG entre les terminaux: entre les terminaux:Ensemble d’arcs tels que tout chemin d’un terminal à un autre passe par au Ensemble d’arcs tels que tout chemin d’un terminal à un autre passe par au moins un de ces arcsmoins un de ces arcs

Capacité de la coupe Capacité de la coupe CC = = ΣΣ capacité des arcs de capacité des arcs de CC

Problème APX-hardProblème APX-hard

Principe des Multiway CutsPrincipe des Multiway Cuts

Principe des Multiway CutsPrincipe des Multiway Cuts

Recherche de jointures pouvant traiter plusieurs Recherche de jointures pouvant traiter plusieurs images superposées:images superposées:

- Suppression de la phase de placementSuppression de la phase de placement

- Permet de choisir directement entre les offsets possiblesPermet de choisir directement entre les offsets possibles

ApplicationApplication à la génération de textures à la génération de textures

Construction basique du grapheConstruction basique du graphe

Nb nœuds = 1 par pixel de l’image de sortieNb nœuds = 1 par pixel de l’image de sortie

+ 1 par offset entre chaque couple de pixels de l'image + 1 par offset entre chaque couple de pixels de l'image

de sortie (nœuds de liaison)de sortie (nœuds de liaison)

Arcs non orientés reliant les nœuds:Arcs non orientés reliant les nœuds:- des nœuds de liaison aux terminauxdes nœuds de liaison aux terminaux

correspondants:correspondants:

- des nœuds de liaison aux nœudsdes nœuds de liaison aux nœuds"pixels" de l’image de sortie:"pixels" de l’image de sortie:

jij

i PPtsMC ,,,min

'',/',

,,,' min jjijijjj

i PPtsMC

Construction basique du grapheConstruction basique du graphe

Soit Soit X=M(s, t, P X=M(s, t, Puu, P, Pvv) la correspondance "privilégiée" entre s ) la correspondance "privilégiée" entre s

et t (valeur minimale)et t (valeur minimale)

- CCii = X uniquement pour i=u et i=v, = X uniquement pour i=u et i=v,

supérieur pour tous les autressupérieur pour tous les autres

- CCii‘ = X uniquement pour i‘ = X uniquement pour i≠≠u et iu et i≠≠v, v,

supérieur pour les autressupérieur pour les autres

- 5 -- 5 -Développements futurs,Développements futurs,

perspectivesperspectives

Utilisation de la technique des Utilisation de la technique des Multiway CutsMultiway Cuts pour l’pour l’inpaintinginpainting

Développement d’une méthode alternative avec Développement d’une méthode alternative avec l’algorithme de ligne de partage des eaux adapté l’algorithme de ligne de partage des eaux adapté aux graphes à arcs valuésaux graphes à arcs valués

A – Texture "optimale"A – Texture "optimale"

Mise en place de la méthode pour la 3D dans un Mise en place de la méthode pour la 3D dans un espace discretespace discret

Application pour reconstruire des formes 3D Application pour reconstruire des formes 3D incomplètesincomplètes

Adaptation pour un traitement directement sur Adaptation pour un traitement directement sur des surfaces (discrétisation)des surfaces (discrétisation)

B – Traitement 3DB – Traitement 3D

Merci de votre attention!Merci de votre attention!

N’hésitez pas à poser vos N’hésitez pas à poser vos questions…questions…