Embed Size (px)
Citation preview
1
Méthodes et Algorithmes
Graphiques
Florent Lafarge
2
But
Donner une structure mathématique afin que
vous puissiez:
Comprendre la littérature.
Utiliser ces méthodes pour:
Mettre vos idées en place.
Bien poser les problèmes.
Donner des algorithmes flexibles:
Pour que vous compreniez les possibilités de ces
techniques.
Que vous puissiez les incorporer dans des
solutions plus complètes.
3
Motivation
Beaucoup de problèmes en traitement
d’image peuvent être exprimés ainsi :
Trouver une structure linéique avec telles ou
telles propriétés.
Trouver une région ou son contour (i.e. bord)
avec telles ou telles propriétés.
Exemples:
Extraction de réseaux routiers.
Extraction de zones urbaines.
4
Exemples
5
Motivation
Les graphes image sont une représentation
discrète de la géométrie de l’image.
Les problèmes précédents être formulés sur
des graphes définis à partir de l’image:
Trouver un chemin (de poids minimum) dans un
graphe.
Trouver un cycle (de poids (ratio) minimum) dans
un graphe.
6
Plan du cours
Graphes et graphes image
Fonctions sur les graphes
Problèmes graphiques et algorithmes I Chemins de poids minimum
Fonctions sur les graphes image
Problème image: détection des réseaux routiers.
-------------------
Problèmes graphiques et algorithmes II Cycles divers
Problèmes graphiques et algorithmes III Cycle de poids rationnel minimum
Problème image: détection d’objets.
2
Graphes et graphes image
8
Graphes orientés: intuition
On peut imaginer un graphe orienté en termes de sommets (cercles verts) et d’arcs (flèches noires): On peut avoir des
sommets isolés (7).
On peut avoir des boucles (g).
On peut avoir plus d’un arc entre deux sommets(h,i).
1
5
6
7
2
43
ab
cd
f
g
e
hi
9
Graphes orientés
Un graphe consiste
en deux ensembles E
(arcs) et V (sommets)
et deux applications
s (source) et b (but)
de E à V:
On peut penser à une
seule application de E à V £ V:
s(e) e b(e)
1 a 4
2 b 1
4 c 2
3 d 2
3 e 4
3 f 1
6 g 6
h 5 s bE V V
s
b
E V
10
Types de graphes
S’il y a plus d’un 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 n’y 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.
11
Graphe symétrique
Pour chaque arc e, il y a un autre arc (e-1)
entre les mêmes sommets mais avec
l’orientation inverse.
8 e 2 E. 9 ! e-1 2 E t.q. s £ b(e-1) = b £ s(e).
12
Connectivité
Un graphe n’est pas
connecté si les sommets
se divisent en deux
parties, sans un arc entre
les deux.
On parle de graphes
connectés dans le cours.
3
13
Sous-graphes
Un sous-graphe H = (U, D) d’un graphe G =
(V, E) est un sous-ensemble des sommets U ½ V, et un sous-ensemble des arcs entre
eux: D ½ E (U £ U).
H
G
14
Graphes spéciaux: chemins et
cycles
Un chemin est une séquence d’arcs:
{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 qu’un graphe contient un chemin ou
un cycle s’il a un sous-graphe qui est un
chemin ou un cycle.
15
Simplicité
Graphe acyclique (GA):
Un graphe qui ne contient pas un sous-graphe qui
soit un cycle.
Chemin simple:
Un chemin qui ne contient pas un sous-graphe qui
soit un cycle.
Cycle simple:
Un cycle qui ne contient pas un sous-graphe
propre qui soit un cycle.
16
Graphes image
V est l’ensemble des pixels.
Deux graphes symétriques:
Vert: G = (E, V).
Rouge: G = (E, V).
Il existe une bijection ¤: E
$ E.
Rotation positive de p/2.
¤¤e = e-1.
=
17
Exemples Image
=
18
Et maintenant?
On cherche un chemin ou un cycle dans un
des deux graphes image.
Mais comment le sélectionner?
On définit 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?
4
Fonctions sur les graphes
20
Fonctions sommet et arc
Sommets:
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 définir la dérivée d’une fonction
sommet, qui est un fonction arc:
(df)(e) = f(b(e)) – f(s(e)).
21
Fonctions spéciales
On peut définir des fonctions
Positives: f(u) > 0.
Entières: f(u) 2 Z.
Binaires: f(u) 2 {0,1}. (Sous-ensemble de U.)
Soit g et h deux fonctions, h positive.
On définit une fonction rationelle g/h(u) =
g(u)/h(u).
22
Fonctions symétriques
Rappel qu’un graphe symétrique a pour
chaque arc e, un arc e-1.
Pour les fonctions arc, on définit:
l-1(e) = l(e-1).
On définit les fonctions symétriques:
l= l-1
On définit les fonctions antisymétriques:
l= -l-1 l(e) = 2
l(e-1) = §2
23
Fonctions sur ensembles
Etant donné une fonction sommet ou
arc, on peut définir 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.
24
Cycles négatifs
Une fonction arc l a un cycle négatif si le
graphe contient un cycle c t.q. l(c) < 0.
Les cycles négatifs jouent un rôle
important dans la suite du cours.
5
25
Exemple
Une fonction f sur V.
Une fonction g sur E.
Dans ce cas, g = df.4.0
2.5
-9.2
-2.1
-13.21.5
11.7 4.6
6.1
-7.1
26
Et maintenant?
On a vu comment définir des fonctions sur
les chemins et les cycles.
Comment trouver le chemin ou cycle avec le
poids minimum?
Problèmes graphiques et
algorithmes
28
Problèmes
Chemins de poids minimum.
Cycle de poids minimum.
Détection de cycles négatifs.
Cycle de poids rationnel minimum.
29
Généralités
On 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 n’est pas toujours utilisé.
On peut supposer que l et t sont entiers.
Problèmes graphiques et
algorithmes I
Chemins de poids minimum
6
31
Chemins de poids minimum
Problème:
Trouver le chemin qui a le poids minimum de l
parmi les chemins qui passent entre un sommet s
et un sommet t.
Différents Cas:
G contient un cycle négatif.
G ne contient aucun cycle négatif. 1 6
4
12
1
2
t
s
32
Différents cas
Cycle négatif Pas de cycle négatif
Chemin l ¸ 0 : impossible. GA.
Par
défaut,
on trouve
un
chemin
simple.
l ¸ 0. l général.
Mal définil général.
Chemin
simple
l général.
NP-complet
GA.
l ¸ 0.l ¸ 0 : impossible.
l général.
33
Notations, Init et Relax
A 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 prédécesseur de chaque sommet
dans le chemin de poids minimum.
Init(d, s)
d(s) = 0; 8 v 2 Vn{s}: d(v) = 1;
Relax(e, d, r, l)
Si d(b(e)) > d(s(e)) + l(e)
d(b(e)) = d(s(e)) + l(e)
r(b(e)) = s(e)
34
l ¸ 0: algorithme de Dijkstra
Dijkstra(G, s, l)
Init(d, s)
Q = V
Tant 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)).
35
Iterations
s 0
a
b
c
d
e
f
g
t
Détaillez dans la table ci-dessous (ou
d’une façon claire) l’exécution de
l’algorithme de Dijkstra en partant du
sommet s. Pour chaque itération et pour
chaque sommet, notez son poids et son
prédécesseur courants. L’initialisation
vous est donnée. Quel est le poids du
chemin de poids minimum entre s et t ?
s
a
b
c
d
e
f
g t
1
5
36
5
2
3
12
4
4
11 1
Algo de Dijkstra: un exemple
36
l général: algorithme de
Bellman/Ford
BellmanFord(G, s, l)
Init(d, s)
Pour n 2 {1,…,(jVj – 1)}
Q = V
Tant que Q ;
u = arb(Q);
Q = Qn{u}
Pour e 2 s-1(u)
Relax(e, d, r, l)
Complexité: O(VE).
7
37
Commentaire
Noter que si l’on veut calculer la distance
entre un sommet et un sous-ensemble des
autres sommets l’algorithme de Dijkstra
peut être arrêté au point où les sommets
sont selectionnés.
38
Et maintenant?
Etant donné la fonction arc l, on peut
trouver le chemin de poids minimum.
Mais étant donné une image, comment
construire cette fonction?
Une image est une fonction sur les sommets
rouges, l’intensité.
Le résultat de l’application d’un filtre (e.g. qui
mesure une texture) est une fonction sommet
rouge.
Fonctions sur les graphes image
40
Graphes image
Deux graphes symétriques:
Vert: G = (E, V).
Rouge: G = (E, V).
V est l’ensemble des pixels.
Il existe une bijection ¤: E
$ E.
Rotation positive de p/2.
¤¤e = e-1.
=
41
Fonctions simples
Etant donné une fonction f sur les sommets rouges, on peut définir 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 symétrique.
« L’intégrale » de f le long d’un chemin.
Différence: h(x, y) = x – y. h = df.
Fonction antisymétrique.
Pas très utile: si c est un cycle, alors df(c) = 0.
42
Fonctions duales
Etant 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 définir 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.
Dérivée: elle décrit les changements de f.
Propriété de bord.
8
43
Fonction arc ) fonction sommet
Etant donné une fonction arc vert (rouge) f
antisymétrique, définir la dérivée 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
d’orientation).
Théorème de Stokes/Green:
Pour un cycle c: f(c) = v 2 Int(c) df(v).
44
Fonction sommet ) fonction arc
Pour chaque fonction sommet rouge (vert),
on peut trouver une fonction arc vert (rouge)
antisymétrique Af t.q.
dAf = f
Alors, on a v 2 Int(c) f(v) = Af(c).
Donc on peut calculer « l’intégrale » de f sur
une région, mais en utilisant les arcs.
Intégrale: elle décrit la masse de f.
Propriété de région.
45
Résumé: fonctions arc
antisymétriques
Trois façons pour créer une fonction arc
antisymétrique à partir d’une fonction
sommet rouge:
f a df.
Pas très utile: si c est un cycle, alors df(c) = 0.
f a df a ¤df.
Dérivée: elle décrit les changements de f.
Propriété de bord.
f a Af.
Intégrale sur une région: elle décrit la masse de f.
Propriété de région.
46
Résumé: fonctions arc
symétriques
Trois façons pour créer une fonction arc
symétrique:
Directement:
8 e 2 E. t(e) = 1.
8 e 2 E. t(e) = la longueur géométrique de e = l(e).
À partir d’une fonction sommet rouge, en
utilisant une fonction h symétrique.
« L’intégrale » de f le long d’un chemin.
À partir de l, fonction arc antisymétrique:
On définit t = jlj par jlj(e) = j(l(e))j.
Exemple j¤dfj: gradient sans orientation.
Problème image
48
Modélisation
On veut trouver une structure linéique ou
une région dans une image qui correspond à
un objet.
Il faut construire des fonctions arc (rouge ou
vert) qui incorpore:
Notre connaissance a priori des propriétés de
l’objet.
La relation entre l’objet et l’image.
9
49
Commentaires
Ces exemples sont illustratifs. Ils ne sont pas
les solutions complètes aux problèmes
mentionnés. Pourquoi?
Les solutions complètes n’existent pas.
E.g. l’extraction des réseaux routiers est encore un
sujet actuel de recherche (problème ouvert).
Il vaut mieux expliquer comment on peut
appliquer ces techniques que de donner des
méthodes toutes faites.
Chaque problème est différent et il faut penser au
problème spécifique.
50
Réseaux routiers
Un réseau routier est composé de linéiques, donc:
Utiliser les chemins de poids minimum et l’algorithme de
Dijkstra.
On voudrait une chaîne de pixels:
On va utiliser le graphe rouge.
On doit définir:
Un fonction arc symétrique et positive l.
Deux types de modélisation:
Géométrie a priori.
Attache aux données.
On va construire l = klG + lA, (k2 R+).
51
Géométrie a priori
La possibilité la plus simple est:
lG = l, la longueur géométrique.
Donc, sans lA:
Le chemin de poids minimum entre deux
sommets est donc le chemin le plus court.
52
Attache aux données
Soit f une fonction sommet rouge, l’intensité
des pixels.
Les chemins sont souvent clairs et ont une
radiométrie homogène.
Donc, on peut essayer:
lA(e) = exp[-a(f(b(e)) + f(s(e))], a 2 R+.
53
Initialisation
Pour utiliser l’algorithme
de Dijkstra, il faut s.
On ne veut pas les chemins
de s à tous les autres
sommets:
Juste aux sommets qui font
partie d’un chemin.
Choisir les intersections des
routes avec le bord de
l’image.
54
Résultat réel
10
55
0.9 0.8 0.8 1
0.1 0.3 0.2 0.8
0.9 0.9 0.4 0.2
0.8 0.8 0.8 0
Exemple: extraction de
réseaux linéiques
56
Exemple: extraction de
réseaux linéiques0.9 0.8 0.8 1
0.1 0.3 0.1 0.8
0.9 0.9 0.4 0.1
0.8 0.8 0.8 0
S
B
1/Proposer un modèle par graphe avec une fonction
de cout prenant en compte a la fois la géométrie et
la radiométrie de l’image
2/ trouver le chemin de poids minimum de ce
modèle
Problèmes graphiques et
algorithmes II
Cycles divers
58
Cycle de poids minimum
Cycle négatif Pas de cycle
négatif
Cycle l ¸ 0 : impossible. l ¸ 0.
Trivial. Par
défaut,
on trouve
un cycle
simple,
mais
trivial.
l général.
Mal défini
l général.
ld = l - dd
Cycle
simple
l général.
NP-complet
l ¸ 0.
Trivial.
l ¸ 0 : impossible. l général.
ld = l - dd
59
Détection de cycles:
algorithme
Cycle(G) Pour v 2 V
Si M(v) = 0
DFS (v)
DFS(v) – depth-first search – recherche par profondeur d’abord M(v) = 1;
Pour u 2 b(s-1(v))
Si M(u) = 0
r(u) = v
DFS(u)
Si M(u) = 1
r(u) = v
Rend u (cycle détecté)
M(v) = 2
60
Détection de cycles négatifs:
algorithme
CycNeg(G, l)
s = arb(V)
d = BellmanFord(G, s)
Pour e 2 E
u = s(e)
v = b(e)
Si d(v) > d(u) + l(e) (ou dd(e) > l(e))
Il y a un cycle négatif.
11
61
Détection de cycles zéro.
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.
62
Cycles zéro: algorithme
ZeroCyc(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)
Problèmes graphiques et
algorithmes III
Cycle de poids rationnel minimum
64
Cycle de poids rationnel
minimum
Problème:
Trouver arg minc 2 C l/t(c).
Ce problème ne presente pas les difficultés
rencontrées avec le cycle de poids minimum.
Dans les applications, il y a aussi des
propriétés théoriques intéressantes.
65
Cycle négatif Pas de cycle
négatif
Cycle l ¸ 0 : impossible. l ¸ 0.
G, l sym: trivial. Par
défaut,
on trouve
un cycle
simple.
l général Par
défaut,
on trouve
un cycle
simple.
l général.
ld = l - dd
Cycle
simple
l général l ¸ 0.
G, l sym: trivial.
l ¸ 0 : impossible. l général.
ld = l - dd
Cycle de poids rationnel
minimum
66
Commentaires
Pas de restriction sur l:
l peut avoir des cycles négatifs.
On trouve toujours un cycle simple.
Pour les graphes symétriques, l
antisymétrique, t symétrique:
arg minc 2 C l/t(c) = arg maxc 2 C jl/t(c)j.
Donc l’algorithme maximise jl/tj.
12
67
Lemmes
On définit une fonction arc paramétrisée 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) < b¤ )
lb¤(c) < 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) < 0 )
l/t(c) < b¤. Contradiction parce que b¤ = minc 2 C l/t(c).
68
Nouveau problème
Donc le problème devient: comment trouver
b¤ t.q. minc 2 C lb¤(c) = 0, puis comment
trouver un cycle de poids zéro.
Noter:
lmin = mine 2 E l(e) · b¤ · maxe 2 E l(e) = lmax
9 c 2 C. lb(c) < 0 ) minc 2 C lb(c) < 0 ) b > b¤
lb(c) < 0 ) b¤ · l/t(c) < b
l/t(c) l/t(c0) ) j l/t(c) - l/t(c0) j ¸ (Etmax)-2
69
Cycle de poids rationnel
minimum: algorithme
CyclePRM(G, l, t)
b = maxe 2 E l(e)
Tant que c = CycNeg(G, lb)
b = l/t(c)
b¤ = b
c¤ = ZeroCyc(G, lb¤)
70
Et maintenant?
Etant donné les fonctions arc l et t, on peut
trouver le cycle de poids rationnel minimum.
Mais étant donné une image, comment
construire ces fonctions?
Une image est une fonction sur les sommets
rouges, l’intensité.
Le résultat de l’application d’un filtre (e.g. qui
mesure une texture) est une fonction sommet
rouge.
Problème image
72
Bord d’une région
Le bord d’une région est un cycle: Utiliser le cycle de poids rationnel
minimum.
On voudrait le bord d’une région: On va utiliser le graphe vert.
On doit définir: Un fonction arc antisymétrique l.
Un fonction arc symétrique etpositive t.
Rappel: l’algorithme essaye de maximiser jl/tj.
13
73
Modèle simple 1.
Soit f une fonction sommet rouge, l’intensité des
pixels.
Donc l = ¤df mesure la somme des valeurs du
gradient orienté sur le bord.
Soit t = l, la longueur géométrique.
l/t mesure la densité du gradient sur le bord.
L’algorithme va la maximiser.
Point positif: invariant à l’échelle. Par contre, l dépend de la longueur du bord.
Point négatif: les bords qui ont un gradient qui
s’inverse.
74
Modèle simple 2
Soit f une fonction sommet rouge ´ 1.
l = Af mesure l’aire de la région.
Soit g une fonction sommet rouge, l’intensité
des pixels.
t = 1/j¤dgj mesure la somme des valeurs
inverses du gradient non-orienté sur le bord.
Donc, jl/tj est grand quand:
L’aire est grande.
Les gradients sont identiques et grands.
75
Resultat synthétique
1. Un bord pour lequel le gradient s’inverse.
2. Résultat avec modèle 1.
3. Résultat avec modèle 2.
(2)(1) (3)
76
Résultat réel
Cratère Lunaire: JPL
Fin
78
GA: ordre topologique
On peut définir un ordre Á des sommets t.q. si u Áv, il n’existe aucun chemin de v à u.
OT(G) Pour v 2 V
Si M(v) = 0
OTT(v, T)
OTT(v, T) M(v) = 1;
T = T + 1;
Pour u 2 b(s-1(v))
Si M(u) = 0
OTT(u, T)
T = T + 1
F(v) = T
On a:
M: V! {0,1}.
F: V! Z+
L’ordre est: u Á v ,
F(v) < F(u).
L’ordre n’est pas
unique.
Complexité: O(E).
14
79
GA: algorithme
CPMGA(G, s, l)
Init(d, s)
Q = V
Tant que Q ;
u = minÁ Q;
Q = Qn {u}
Pour e 2 s-1(u)
Relax(e, d, r, l)
Complexité: O(E).
