Méthodes et Algorithmes Graphiques

  • Published on
    30-Dec-2015

  • View
    26

  • Download
    2

Embed Size (px)

DESCRIPTION

Mthodes et Algorithmes Graphiques. Ian Jermyn. Quelques points avant de commencer. Pour me contacter : Ian Jermyn. Ian.Jermyn@sophia.inria.fr . www-sop.inria.fr/ariana/personnel/Ian.Jermyn . Nationalit : Britannique. Excusez mon franais sil vous plait. - PowerPoint PPT Presentation

Transcript

<ul><li><p>Mthodes et Algorithmes GraphiquesIan Jermyn</p></li><li><p>Quelques points avant de commencer.Pour me contacter: Ian Jermyn.Ian.Jermyn@sophia.inria.fr.www-sop.inria.fr/ariana/personnel/Ian.Jermyn. Nationalit: Britannique. Excusez mon franais sil vous plait.Chercheur en traitement dimage et vision par ordinateur lINRIA dans projet Ariana.Formation: en physique thorique, puis vision par ordinateur.</p></li><li><p>Quelques points avant de commencer.Nhsitez pas :Me questionner: cest la faon meilleure dapprendre.Demander que: Je parle plus fort.Je rpte ou explique quelque chose.Vous pouvez trouver ce fichier lURL precedent, sous Teaching/Advising puis Courses, partir de lundi. </p></li><li><p>ButDonner une structure mathmatique afin que vous puissiez: Comprendre la littrature.Utiliser ces mthodes pour: Systmatiser vos ides.Bien poser les problmes.Donner des algorithmes flexibles:Pour que vous compreniez les possibilits de ces techniques.Que vous pouvez adapter vos problmes.Que vous pouvez incorporer dans des solutions plus compltes.</p></li><li><p>MotivationBeaucoup des problmes en traitement dimage peuvent tre exprims ainsi:Trouver une structure linique avec telles ou telles proprits.Trouver une rgion ou son contour (i.e. bord) avec telles ou telles proprits.Exemples:Extraction de rseaux routiers. Extraction de zones urbaines.</p></li><li><p>Exemples</p></li><li><p>MotivationLes graphes image sont une reprsentation discrte de la gomtrie de limage. Les problmes prcdents se traduisent par des problmes sur des graphes dfinis partir de limage:Trouver un chemin (de poids minimum) dans un graphe.Trouver un cycle (de poids (ratio) minimum) dans un graphe.</p></li><li><p>Plan du coursGraphes et graphes imageFonctions sur les graphesProblmes graphiques et algorithmesChemins de poids minimumCycles diversCycle de poids rationnel minimumFonctions sur les graphes imageProblmes imageExemples</p></li><li><p>Graphes et graphes image</p></li><li><p>Graphes orients: intuitionOn peut imaginer un graphe orient en termes de sommets (cercles verts) et darcs (flches noires):On peut avoir des sommets isols (7). On peut avoir des boucles (g). On peut avoir plus dun arc entre deux sommets (h,i).1567243abcdfgehi</p></li><li><p>Graphes orientsUn graphe consiste de deux ensembles E (arcs) et V (sommets) et deux applications s (source) et b (but) de E V:</p><p>On peut penser une seule application de E V V: </p><p>s(e)eb(e)1a42b14c23d23e43f16g6h5</p></li><li><p>Types de graphesSi il y a plus dun arc entre deux sommets, on a un multigraphe (s b pas injective).Sinon (s b est injective), on peut identifier E avec un sous-ensemble de V V.Si il ny a pas de boucle, on a un graphe simple. Si on a tous les arcs possibles (E = V V), le graphe est complet (s b surjective).Nous utiliserons le mot graphe pour les non-multigraphes simples.</p></li><li><p>Graphe symtriquePour chaque arc e, il y a un autre arc (e-1) entre les mmes sommets mais avec lorientation inverse.8 e 2 E. 9 ! e-1 2 E t.q. s b(e-1) = b s(e).</p></li><li><p>ConnectivitUn graphe nest pas connect si les sommets se divisent en deux parties, sans un arc entre les deux. On parle de graphes connects dans le cours.</p></li><li><p>Sous-graphesUn sous-graphe H = (U, D) dun graphe G = (V, E) est un sous-ensemble des sommets U V, et un sous-ensemble des arcs entre eux: D E (U U). </p></li><li><p>Graphes spciaux: chemins et cyclesUn chemin est une squence darcs:{ei}i 2 [1..n], t.q.b(ei) = s(ei + 1) pour i 2 [1..(n 1)].Un cycle est un chemin avec b(en) = s(e1).On dit quun graphe contient un chemin ou un cycle si il a un sous-graphe qui est un chemin ou un cycle. </p></li><li><p>SimplicitGraphe acyclique (GA): Une graphe qui ne contient pas un sous-graphe qui est un cycle. Chemin simple: Une chemin qui ne contient pas un sous-graphe qui est un cycle.Cycle simple: Un cycle qui ne contient pas un sous-graphe propre qui est un cycle. </p></li><li><p>Graphes imageV est lensemble des pixels.Deux graphes symtriques:Vert: G = (E, V).Rouge: G = (E, V).Il existe une bijection : E $ E.Rotation positive de p/2.e = e-1.</p></li><li><p>Exemples Image</p></li><li><p>Et maintenant?On cherche un chemin ou un cycle dans un des deux graphes image.Mais comment on va le slectionner?On dfinit une fonction (poids) qui donne une valeur pour chaque chemin ou chaque cycle dans le graphe.On cherche le chemin ou le cycle avec le poids minimum. Comment construire une telle fonction? </p></li><li><p>Fonctions sur les graphes</p></li><li><p>Fonctions sommet et arcSommets:Pour chaque sommet v, on a une valeur (un poids) f(v).Arcs: Pour chaque arc e, on a une valeur (un poids) f(e).On peut dfinir la drive dune fonction sommet, qui est un fonction arc:(df)(e) = f(b(e)) f(s(e)). </p></li><li><p>Fonctions spcialesOn peut dfinir des fonctionsPositives: f(u) &gt; 0.Entires: f(u) 2 Z.Binaires: f(u) 2 {0,1}. (Sous-ensemble de U.)Soit g et h deux fonctions, h positive.On dfinit une fonction rationelle g/h(u) = g(u)/h(u).</p></li><li><p>Fonctions symtriquesRappel quun graphe symtrique a pour chaque arc e, un arc e-1.Pour les fonctions arc, on dfinit: l-1(e) = l(e-1). On dfinit les fonctions symtriques:l= l-1On dfinit les fonctions antisymtriques:l= -l-1</p></li><li><p>Fonctions sur ensemblesEtant donn une fonction sommet ou arc, on peut dfinir une fonction sur sous-ensembles de V ou E par sommation. E.g.:U V; f(U) = v 2 U f(v).Noter que df(c) = 0 si c est un cycle. </p></li><li><p>Cycles ngatifsUne fonction arc l a un cycle ngatif si le graphe contient un cycle c t.q. l(c) &lt; 0.Les cycles ngatifs jouent une rle important dans la suite du cours.</p></li><li><p>ExempleUne fonction f sur V.Une fonction g sur E.Dans ce cas, g = df.4.02.5-9.2-2.1-13.21.511.74.66.1-7.1</p></li><li><p>Et maintenant?On a vu comment dfinir des fonctions sur les chemins et les cycles.Comment trouver le chemin ou cycle avec le poids minimum? </p></li><li><p>Problmes graphiques et algorithmes</p></li><li><p>ProblmesChemins de poids minimum.Cycle de poids minimum.Dtection de cycles ngatifs.Cycle de poids rationel minimum.</p></li><li><p>GnralitsOn suppose:Un graphe G = (E, V). C est le sous-ensemble de cycles dans G. Deux fonctions arc, l et t. t est positive. t nest pas toujours utilis. On peut supposer que l et t sont entiers.</p></li><li><p>Problmes graphiques et algorithmes IChemins de poids minimum</p></li><li><p>Chemins de poids minimumProblme:Trouver le chemin qui a le poids minimum de l parmi les chemins qui passent entre un sommet s et un sommet t.Diffrents Cas:G contient un cycle ngatif.G ne contient aucun cycle ngatif. </p></li><li><p>Diffrents cas</p><p>Cycle ngatifPas de cycle ngatifCheminl 0 : impossible.GA.Par dfaut, on trouve un chemin simple.l 0. l gnral. Mal dfinil gnral.Chemin simplel gnral. NP-completGA.l 0.l 0 : impossible.l gnral.</p></li><li><p>Notations, Init et RelaxA la fin de chaque algorithme:d: V ! R sera le poids du chemin de poids minimum (valeur minimal de l) entre s et v.r: V ! V est le prdcesseur de chaque sommet dans le chemin de poids minimum de s.Init(d, s)d(s) = 0; 8 v 2 Vn{s}: d(v) = 1;Relax(e, d, r, l)Si d(b(e)) &gt; d(s(e)) + l(e) d(b(e)) = d(s(e)) + l(e) r(b(e)) = s(e)</p></li><li><p>l 0: algorithme de DijkstraDijkstra(G, s, l)Init(d, s)Q = VTant que Q ;u = arg minv 2 Q {d(v)}Q = Qn{u}Pour e 2 s-1(u)Relax(e, d, r, l)Complexit: O(E log(V)).</p></li><li><p>l gnral: algorithme de Bellman/FordBellmanFord(G, s, l)Init(d, s)Pour n 2 {1,,(jVj 1)}Q = VTant que Q ;u = arb(Q); Q = Qn{u}Pour e 2 s-1(u)Relax(e, d, r, l)Complexit: O(VE).</p></li><li><p>CommentaireNoter que si lon veut calculer la distance entre un sommet et un sous-ensemble des autres sommets lalgorithme de Dijkstra peut tre arrt au point o les sommets sont selectionns. </p></li><li><p>Problmes graphiques et algorithmes IICycles divers</p></li><li><p>Cycle de poids minimum</p><p>Cycle ngatifPas de cycle ngatifCyclel 0 : impossible.l 0. Trivial. Par dfaut, on trouve un cycle simple, mais trivial.l gnral. Mal dfinil gnral.ld = l - ddCycle simplel gnral. NP-completl 0.Trivial.l 0 : impossible.l gnral.ld = l - dd</p></li><li><p>Dtection de cycles: algorithmeCycle(G)Pour v 2 VSi M(v) = 0DFS (v)DFS(v) depth-first search recherche par profondeur dabordM(v) = 1;Pour u 2 b(s-1(v))Si M(u) = 0r(u) = vDFS(u)Si M(u) = 1r(u) = vRend u (cycle dtect)M(v) = 2</p></li><li><p>Dtection de cycles ngatifs: algorithmeCycNeg(G, l)s = arb(V)d = BellmanFord(G, s) Pour e 2 Eu = s(e)v = b(e)Si d(v) &gt; d(u) + l(e) (ou dd(e) &gt; l(e))Il y a une cycle ngatif.</p></li><li><p>Dtection de cycles zro.d(v) d(u) + l(hu, vi).Donc ld(hu, vi) = l(hu, vi) - dd(hu, vi) est positive.Pour un cycle c: ld(c) = l(c) parce que df(c) = 0 pour toutes fonctions sommet f et tous cycles.Donc, l(c) = 0 ) ld(e) = 0 8 e 2 c.</p></li><li><p>Cycles zro: algorithmeZeroCyc(G, l)s = arb(V)d = BellmanFord(G, s, l)E0 = {e 2 E : ld(e) = 0}G0 = (E0, b(E0) [ s(E0))c = Cycle(G0)</p></li><li><p>Problmes graphiques et algorithmes IIICycle de poids rationnel minimum</p></li><li><p>Cycle de poids rationnel minimumProblme: Trouver arg minc 2 C l/t(c).Ce problme ne presente pas les difficults rencontres avec le cycle de poids minimum.Dans les applications, il y a aussi des proprits thoriques intressantes.</p></li><li><p>Cycle de poids rationnel minimum </p><p>Cycle ngatifPas de cycle ngatifCyclel 0 : impossible.l 0. G, l sym: trivial. Par dfaut, on trouve un cycle simple.</p><p>l gnral Par dfaut, on trouve un cycle simple.l gnral.ld = l - ddCycle simplel gnrall 0.G, l sym: trivial.l 0 : impossible.l gnral.ld = l - dd</p></li><li><p>CommentairesPas de restriction sur l: l peut avoir des cycles ngatifs.On trouve toujours un cycle simple.Pour les graphes symtriques, l antisymtrique, t symtrique: arg minc 2 C l/t(c) = arg maxc 2 C jl/t(c)j.Donc lalgorithme maximise jl/tj. </p></li><li><p>LemmesOn dfinit une fonction arc paramtrise lb = l - bt.Lemme: Soit b t.q. minc 2 C lb(c) = 0 et soit c un cycle minimisant lb(c) = 0, alors b = minc 2 C l/t(c) et l/t(c) = b. lb(c) = 0 ) l/t(c) = b.Supposons b minc 2 C l/t(c), alors 9 c t.q. l/t(c) &lt; b ) lb(c) &lt; 0. Contradiction parce que minc 2 C lb(c) = 0.Lemme: Soit b = minc 2 C l/t(c) et soit c un cycle minimisant, alors minc 2 C lb(c) = 0 et lb(c) = 0.lb(c) = 0 ( l/t(c) = b.Supposons minc 2 C lb(c) 0, alors 9 c t.q. lb(c) &lt; 0 ) l/t(c) &lt; b. Contradiction parce que b = minc 2 C l/t(c).</p></li><li><p>Nouveau problmeDonc le problme devient: comment trouver b t.q. minc 2 C lb(c) = 0, puis comment trouver un cycle de poids zro.Noter: lmin = mine 2 E l(e) b maxe 2 E l(e) = lmax9 c 2 C. lb(c) &lt; 0 ) minc 2 C lb(c) &lt; 0 ) b &gt; blb(c) &lt; 0 ) b l/t(c) &lt; bl/t(c) l/t(c0) ) j l/t(c) - l/t(c0) j (Etmax)-2 </p></li><li><p>Cycle de poids rationnel minimum: algorithmeCyclePRM(G, l, t)b = maxe 2 E l(e)Tant que c = CycNeg(G, lb) b = l/t(c)b = bc = ZeroCyc(G, lb)</p></li><li><p>Et maintenant? Etant donn les fonctions arc et , on peut trouver le chemin de poids minimum ou le cycle de poids rationnel minimum. Mais tant donn une image, comment construire ces fonctions? Une image est une fonction sur les sommets rouges, lintensit.Le rsultat de lapplication dun filtre (e.g. qui mesure une texture) est une fonction sommet rouge.</p></li><li><p>Fonctions sur les graphes image</p></li><li><p>Graphes imageDeux graphes symtriques:Vert: G = (E, V).Rouge: G = (E, V).V est lensemble des pixels.Il existe une bijection : E $ E.Rotation positive de p/2.e = e-1.</p></li><li><p>Fonctions simplesEtant donn une fonction f sur les sommets rouges, on peut dfinir une fonction g sur les arcs rouges:g(e) = h(f(s(e)), f(b(e))).Deux exemples:Somme: h(x, y) = x + y. Fonction symtrique.Lintgrale de f le long dun chemin.Diffrence: h(x, y) = x y.h = df.Fonction antisymtrique.Pas trs utile: si c est un cycle, alors df(c) = 0.</p></li><li><p>Fonctions duellesEtant donn une fonction f sur les arcs rouges, on peut definir une fonction f sur les arcs verts (et vice-versa): f(e) = f(e).Donc, tant donn une fonction f sur les sommets rouges, on peut dfinir une fonction df sur les arcs verts. Pour un cycle c:df(c) = e 2 c [f(b(e)) f(s(e))].Donc le flux du gradient de f travers c.Drive: elle dcrit les changements de f.Proprit de bord.</p></li><li><p>Fonction arc ) fonction sommetEtant donn une fonction arc vert (rouge) f antisymtrique, dfinir la drive df comme la fonction sommet rouge (vert):df(v) = e 2 c(v) f(e)O c(v) est le cycle autour de v (choix dorientation).Thorme de Stokes/Green: Pour un cycle c: f(c) = v 2 Int(c) df(v).</p></li><li><p>Fonction sommet ) fonction arcPour chaque fonction sommet rouge (vert), on peut trouver une fonction arc vert (rouge) antisymtrique Af t.q.dAf = fAlors, on a v 2 Int(c) f(v) = Af(c).Donc on peut calculer lintgrale de f sur une rgion, mais en utilisant les arcs.Intgrale: elle dcrit le masse de f. Proprit de rgion.</p></li><li><p>Fonctions arc antisymtriquesTrois faons pour crer une fonction arc antisymtrique partir dune fonction sommet rouge:f a df.Pas trs utile: si c est un cycle, alors df(c) = 0.f a df a df.Drive: elle dcrit les changements de f.Proprit de bord.f a Af.Intgrale sur une rgion: elle dcrit le masse de f. Proprit de rgion.</p></li><li><p>Fonctions arc symtriquesTrois faons pour crer une fonction arc symtrique:Directement: 8 e 2 E. t(e) = 1. 8 e 2 E. t(e) = la longueur gomtrique de e = l(e). partir dune fonction sommet rouge, en utilisant une fonction h symtrique.Lintgrale de f le long dun chemin. partir de l, fonction arc antisymtrique:On dfinit t = jlj par jlj(e) = j(l(e))j.Exemple jdfj: gradient sans orientation.</p></li><li><p>Problmes image</p></li><li><p>ModlisationOn veut trouver une structure linique ou une rgion dans une image qui correspond un objet. Il faut construire des fonctions arc (rouge ou vert) qui incorpore:Notre connaissance a priori des proprits de lobjet.La relation entre lobjet et limage.</p></li><li><p>CommentairesCes exemples sont illustratifs. Ils ne sont pas les solutions compltes aux problmes mentionns. Pourquoi?Les solutions compltes nexistent pas. E.g. lextraction des rseaux routiers est encore un sujet actuel de recherche (problme ouvert).Il vaut mieux dexpliquer comment on peut appliquer ces techniques que de donner des mthodes toutes faites.Chaque problme est diffrent et il faut penser au problme spcifique.</p></li><li><p>Rseaux routiersUn rseau routier est compos de routes, donc: Utiliser les chemins de poids minimum et lalgorithme de Dijkstra.On voudrait une chane de pixels:On va utiliser le graphe rouge.On doit dfinir:Un fonction arc symtrique et positive l.Deux types de modlisation:Gomtrie a priori.Attache aux donnes.On va construire l = klG + lA, (k2 R+). </p></li><li><p>Gomtrie a prioriLa possibilit la plus simple est: lG = l, la longueur gomtrique.Donc, sans lA:Le chemin de poids minimum entre deux sommets est donc le chemin le plus court.</p></li><li><p>Attache aux donnesSoit f une fonction sommet rouge, lintensit des pixels.Les chemins sont souvent clairs et ont une radiomtrie homogne. Donc, on peut essayer: lA(e) = exp[-a(f(b(e)) + f(s(e))], a 2 R+.</p></li><li><p>InitialisationPour utiliser lalgorithme de Dijkstra, il faut s. On ne veut pas les chemins de s tous les autres sommets:Juste aux sommets qui font partie dun chemin.Choisir les intersections des routes avec le bord de limage.</p></li><li><p>Rsultat rel</p></li><li><p>Bord dune rgionLe bord dune rgion est un cycle: Utiliser le cycle de poids rationel minimum.On voudrait le bord dune rgion:On va utiliser le graphe vert.On doit dfinir:Un fonction arc antisymtrique l.Un fonction arc symtrique et positive t.Rappel: lalgorithme essaye de maximiser jl/tj. </p></li><li><p>Modle simple 1.Soit f une fonction sommet rouge, lintensit des pixels.Donc l = df mesure la somme des valeurs du gradient orient sur le bord.Soit t = l, la longueur gomtrique.l/t mesure la densit du gradient sur le bord.Lalgorithme va la maximiser.Point positif: invariant lchelle.Par contre, l dpend de la longueur du bord.Point ngatif: les bords qui ont...</p></li></ul>