Le transport optimal
et ses applications
Gabriel Peyré
[Link] ÉCOLE NORMALE
S U P É R I E U R E
ansport framework Sliced Wasserstein projection Applications
lication to Color Transfer
Transport Optimal
Monge Kantorovich Dantzig Brenier Otto McCann Villani
Sliced Wasserstein projection of X to style
image color statistics Y
Source image (X )
Source image after color transfer
Style image (Y )
J. Rabin Wasserstein Regularization
Des fournisseurs aux boulangeries
in
m
22
12 m
in
19 m i n
in
35 m
cij y1 y2 y3 y4 y5 y6
x1 12 10 31 27 10 30
15
x2 22 7 25 15 11 14
m
in
x3 19 7 19 10 15 15
x4 10 6 21 19 14 24
x5 15 23 14 24 31 34
x6 35 26 16 9 34 15
Le problème d’affectation optimale
ci,j
Objets ou points (xi )ni=1 , (yj )nj=1 . 1 1
2 2
Cout de transport ci,j entre i et j.
3 3
A↵ectation: : {1, . . . , n} ! {1, . . . , n}. 4 4
pour tout j, il existe i, (i) = j 5 5
6 6
i j
Le problème d’affectation optimale
ci,j
Objets ou points (xi )ni=1 , (yj )nj=1 . 1 1
2 2
Cout de transport ci,j entre i et j.
3 3
A↵ectation: : {1, . . . , n} ! {1, . . . , n}. 4 4
pour tout j, il existe i, (i) = j 5 5
6 6
i j
cij y1 y2 y3 y4 y5 y6
x1 12 10 31 27 10 30
x2 22 7 25 15 11 14 Cout:
x3 19 7 19 10 15 15 10+7+15+10+14+9
x4 10 6 21 19 14 24
x5 15 23 14 24 31 34
= 65 min
x6 35 26 16 9 34 15
Le problème d’affectation optimale
ci,j
Objets ou points (xi )ni=1 , (yj )nj=1 . 1 1
2 2
Cout de transport ci,j entre i et j.
3 3
A↵ectation: : {1, . . . , n} ! {1, . . . , n}. 4 4
pour tout j, il existe i, (i) = j 5 5
6 6
i j
cij y1 y2 y3 y4 y5 y6
x1 12 10 31 27 10 30
x2 22 7 25 15 11 14 Cout:
x3 19 7 19 10 15 15 10+7+15+10+14+9
x4 10 6 21 19 14 24
x5 15 23 14 24 31 34
= 65 min
x6 35 26 16 9 34 15
n
X
A↵ectation optimale : min ci, (i)
i=1
Du meilleur … au moins bon
Coût=64 Coût=65
Coût=66 Coût=152
Gaspard Monge (1746-1818)
Il joue un grand rôle dans la Révolution
française, tant du point de vue politique
que du point de vue de l'instauration d'un
nouveau système éducatif : il participe à
la création de l'École normale de l'an III et
de l'École polytechnique (en 1794), deux
écoles où il enseigne la géométrie. Il
concourt également avec Berthollet,
Chaptal et Laplace à la création de l'École
d'arts et métiers. Il est également membre
de la commission des sciences et des arts
lors de la campagne d'Italie (1796–1797),
et chargé de mission dans l'expédition
d'Égypte (1798–1799).
Nombre de Possibilités
De 1 vers: 1, 2, 3, 4, 5, 6.
De 2 vers: 2, 3, 4, 5, 6.
De 3 vers: 3, 4, 5, 6.
De 4 vers: 4, 5, 6.
De 5 vers: 5, 6.
De 6 vers: 6.
6 ⇥ 5 ⇥ 4 ⇥ 3 ⇥ 2 ⇥ 1 = 720
Nombre de Possibilités
De 1 vers: 1, 2, 3, 4, 5, 6.
De 2 vers: 2, 3, 4, 5, 6.
De 3 vers: 3, 4, 5, 6.
De 4 vers: 4, 5, 6.
De 5 vers: 5, 6.
De 6 vers: 6.
6 ⇥ 5 ⇥ 4 ⇥ 3 ⇥ 2 ⇥ 1 = 720
n n! n n!
0 1 9 362880 Atomes dans l’univers: 1079
1
2
1
2
10 3628800
Neurones dans le cerveau: 1011 .
11 39916800
3 6 12 479001600
4 24 … …
5 120
25 1,551x1025
6 720
7 5 040 … …
8 40 320 70 1,198x10100
Exemples n=70
Cout=200 Cout=1493
En dimension 1
Le cas 1D: xi , yj 2 R ci,j = |xi yj |
y3 y4 x 2 x4 y5
Notes /20: Classe 1
0 x3 x1 10 x y2 y1 20 Classe 2
5
Ligne metro
x5 x1
y4 y2 y1
x 2 y3 y5 x4 x3
En dimension 1
Le cas 1D: xi , yj 2 R ci,j = |xi yj |
y3 y4 x 2 x4 y5
Notes /20: Classe 1
0 x3 x1 10 x y2 y1 20 Classe 2
5
Ligne metro
x5 x1
y4 y2 xxx
y1
x 2 y3 y5 x4 x3
! Solution: classer les (xi )i , (yj )j par ordre croissant.
En dimension 1
Le cas 1D: xi , yj 2 R ci,j = |xi yj |
y3 y4 x 2 x4 y5
Notes /20: Classe 1
0 x3 x1 10 x y2 y1 20 Classe 2
5
Ligne metro
x5 x1
y4 y2 xxx
y1
x 2 y3 y5 x4 x3
! Solution: classer les (xi )i , (yj )j par ordre croissant.
Algorithmes de tri: par selection, pire cas n(n 1)/2 opérations.
n n! n(n-1)/2 n log(n)
10 3628800 45 23
11 39916800 55 26
12 479001600 66 30
Tri rapide: n log(n).
25 1,551x1025 300 80
70 1,198x10100 21415 297
En dimension 2
x
Le cas 2D: i j q, y 2 R 2 xj
xi
ci,j = ||xi yj || = (x1i yj1 )2 + (x2i yj2 )2
n = 10 n = 70 n = 300
En dimension 2
x
Le cas 2D: i j q, y 2 R 2 xj
xi
ci,j = ||xi yj || = (x1i yj1 )2 + (x2i yj2 )2
n = 10 n = 70 n = 300
Propriété: deux segments ne se croisent pas.
xi xj xi xj
x i0 xj 0 x i0 xj 0
mauvais meilleur
Poids et histogrammes
A↵ectation entre ensembles de tailles di↵érentes: impossible.
2 2 Points (x i ) i , poids (p i ) i .
?
1 2 Points (yj )j , poids (qj )j .
1 P P
Contrainte: i pi = j qj
Poids ⇠ masse ⇠ capacité.
Poids et histogrammes
A↵ectation entre ensembles de tailles di↵érentes: impossible.
2 2 Points (x i ) i , poids (p i ) i .
?
1 2 Points (yj )j , poids (qj )j .
1 P P
Contrainte: i pi = j qj
Poids ⇠ masseP ⇠ capacité.
Normalisation i pi = 1 , histogramme.
20
10
0 p11 p22 p33 p44 p55 p66
20
10
0 q11 q22 q33 q44 q55 q66
Couplage Optimal
Transport de masse i $ j: P i,j > 0
Conservation de la masse:
P P 3 23 18 26 16 14
L j P i,j = pi C i P i,j = qj 24 1 7 0 0 16 0
9 0 0 0 0 0 9
3 0 0 0 0 0 3
16 0 16 0 0 0 0
21 2 0 18 1 0 0
27 0 0 0 25 0 2
20
qj
10
02
01
10
20
02
01
0
0
0
0
1 2 3 4 5 6
1
1
1
2
2
2
pi
3
3
P i,j
3
4
4
4
5
5
5
6
6
6
Couplage Optimal
Transport de masse i $ j: P i,j > 0
Conservation de la masse:
P P 3 23 18 26 16 14
L j P i,j = pi C i P i,j = qj 24 1 7 0 0 16 0
9 0 0 0 0 0 9
3 0 0 0 0 0 3
ProblèmeX de Kantorovich:
16 0 16 0 0 0 0
min P i,j ci,j “Programmation 21 2 0 18 1 0 0
P i,j >0 linéaire” 27 0 0 0 25 0 2
i,j
L &C 20
qj
10
02
01
10
20
02
01
0
0
0
0
1 2 3 4 5 6
1
1
1
2
2
2
pi
3
3
P i,j
3
4
4
4
5
5
5
6
6
6
Examples
Leonid Kantorovich (1912-1986)
Леонид Витальевич Канторович
Au cours du siège de Léningrad, Peu avant la Seconde Guerre
Kantorovitch est responsable de la mondiale, Leonid Kantorovitch
sécurité de la Route de la vie. Il détermine découvre la programmation linéaire,
la distance optimale à observer entre les l'optimisation linéaire et ses
voitures sur la surface gelée du lac applications à l'optimisation de la
Ladoga, en fonction de l'épaisseur de production économique planifiée. Il est
glace et de la température de l’air. En le seul chercheur soviétique à avoir
décembre 1941–janvier 1942, reçu le « prix Nobel » d'économie
Kantorovitch s'assure lui-même de la (1975). Les théories de Kantorovitch
viabilité de la banquise en marchant entre ne sont publiées qu’après l'ère
les camions. Cependant bien des stalinienne. Un des apports de
véhicules chargés d'approvisionnements Kantorovitch est d'avoir incité à une
sont détruits par les bombardements meilleure prise en compte de la
aériens nazis. En récompense de ses productivité marginale de
exploits et de son courage, les autorités l’investissement, afin de résoudre les
attribuent à Kantorovitch l’ordre de la difficultés liées à l’allocation des
Guerre patriotique, et le décorent de la ressources au sein d’une économie
Médaille pour la Défense de Léningrad. socialiste.
Applications aux formes
Sliced Wasserstein projection of
Applicationsimage
aux color
couleurs
statistics Y
Optimal transport framework Sliced Wasserstein projection Applications
Application to Color Transfer
Transport
Source image (XApplication
)
Optimal transport framework Sliced Wasserstein projection Applications
to Color Transfer
optimal
Sliced Wasserstein projection of X to style
image color statistics Y
Source image (X ) Sliced Wasserstein projectio
image color statistics Y
Référence Entrée
Source image (X ) Sortie
Source image after color transfer
Style image (Y )
Source image after color tra
J. Rabin Wasserstein Regularization
Style image (Y )
Histogrammes de textes
Histogrammes des fréquence empirique des mots:
Histogrammes de textes
Histogrammes des fréquence empirique des mots:
Visualisation d’une base de donnée:
20news
[Link]
[Link] [Link]
[Link]
[Link] [Link]
[Link]
[Link] [Link]
[Link]
[Link] [Link]
[Link].x
[Link] [Link]
[Link] [Link] [Link]
[Link] [Link]
image color statistics Y
Conclusion
Les distributions de “masses” sont partout:
Source image (X )
Source image after color transfer
Style image (Y )
J. Rabin Wasserstein Regularization
image color statistics Y
Conclusion
Les distributions de “masses” sont partout:
Source image (X )
Source image after color transfer
Style image (Y )
Les pioniers: J. Rabin Wasserstein Regularization
Monge Kantorovich Dantzig Wasserstein Brenier Otto McCann Villani
image color statistics Y
Conclusion
Les distributions de “masses” sont partout:
Source image (X )
Source image after color transfer
Style image (Y )
Les pioniers: J. Rabin Wasserstein Regularization
Monge Kantorovich Dantzig Wasserstein Brenier Otto McCann Villani
1500
Un domaine de recherche actif: 1000
500
“transport optimal” selon Google Scholar:
0
1995 2000 2005 2010 2015