Wiki du LAMA (UMR 5127) - Contributions [fr]

Transport optimal par coupe 1D et transfert de couleurs entre images

2022-05-11T15:13:11Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

La complexité de ce programme est de l'ordre de ln(N), car le trie des liste domine.
Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.bmp")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. Pour l'image C, son format par défaut est en bmp.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 
 
[[Fichier:experimentation1a.jpg|600px]] 
 
[[Fichier:experimentation1b.jpg|600px]] 
</li>
 
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 
 
[[Fichier:experimentation2a.jpg|600px]] 
 
[[Fichier:experimentation2b.jpg|600px]] 
</li>
 
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 
 
[[Fichier:experimentation3a.jpg|600px]] 
 
[[Fichier:experimentation3b.jpg|600px]] 
 
On peut aussi inverser le rôle des images. 
 
[[Fichier:experimentation3c.jpg|600px]] 
</li>
 
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 
 
[[Fichier:experimentation4a.jpg|600px]] 
 
[[Fichier:experimentation4b.jpg|600px]] 
 
Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]
*Source de l'image A bis : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B bis : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

== Liens ==
Une version mise à jour du code présenté est disponible sur github à l'adresse [https://github.com/clau555/color-transfer https://github.com/clau555/color-transfer].

Transport optimal par coupe 1D et transfert de couleurs entre images

2021-03-29T21:29:55Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

La complexité de ce programme est de l'ordre de ln(N), car le trie des liste domine.
Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.bmp")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. Pour l'image C, son format par défaut est en bmp.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 
 
[[Fichier:experimentation1a.jpg|600px]] 
 
[[Fichier:experimentation1b.jpg|600px]] 
</li>
 
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 
 
[[Fichier:experimentation2a.jpg|600px]] 
 
[[Fichier:experimentation2b.jpg|600px]] 
</li>
 
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 
 
[[Fichier:experimentation3a.jpg|600px]] 
 
[[Fichier:experimentation3b.jpg|600px]] 
 
On peut aussi inverser le rôle des images. 
 
[[Fichier:experimentation3c.jpg|600px]] 
</li>
 
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 
 
[[Fichier:experimentation4a.jpg|600px]] 
 
[[Fichier:experimentation4b.jpg|600px]] 
 
Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]
*Source de l'image A bis : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B bis : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

== Liens ==
Une version mise à jour du code présenté est disponible sur github à l'adresse [https://github.com/LucCha42/color-transfer https://github.com/LucCha42/color-transfer].

Transport optimal par coupe 1D et transfert de couleurs entre images

2021-03-29T21:29:23Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

La complexité de ce programme est de l'ordre de ln(N), car le trie des liste domine.
Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.bmp")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. Pour l'image C, son format par défaut est en bmp.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 
 
[[Fichier:experimentation1a.jpg|600px]] 
 
[[Fichier:experimentation1b.jpg|600px]] 
</li>
 
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 
 
[[Fichier:experimentation2a.jpg|600px]] 
 
[[Fichier:experimentation2b.jpg|600px]] 
</li>
 
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 
 
[[Fichier:experimentation3a.jpg|600px]] 
 
[[Fichier:experimentation3b.jpg|600px]] 
 
On peut aussi inverser le rôle des images. 
 
[[Fichier:experimentation3c.jpg|600px]] 
</li>
 
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 
 
[[Fichier:experimentation4a.jpg|600px]] 
 
[[Fichier:experimentation4b.jpg|600px]] 
 
Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]
*Source de l'image A bis : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B bis : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

== Liens ==
Une version mise à jour du code présenté est disponible sur github à l'adresse [[https://github.com/LucCha42/color-transfer https://github.com/LucCha42/color-transfer]].

VISI201 CMI : visite de laboratoire

2019-05-23T08:45:16Z

Chardonnet : Mise à jour du lien du Transport optimal

* Cours du semestre 2 du parcours CMI Informatique (licence INFO).

* Responsable pour 2018--2019: Jacques-Olivier Lachaud
* Responsable pour 2017--2018: Jacques-Olivier Lachaud
* Responsable pour 2016--2017: Jacques-Olivier Lachaud

= Descriptif =

L'objectif du module est de faire découvrir les laboratoires, le monde de la recherche et les enseignants-chercheurs et chercheurs, ainsi que la réflexion scientifique. Cela se fait de deux manières.

D'abord, une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [[http://www.lama.univ-savoie.fr/index.php?use=seminaires&&lang=fr&equipe=cmi&annee=1&lang=fr Planning des séminaires CMI]]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet proposé par les enseignants, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail se fait en interaction avec un tuteur académique (5-6 contacts au moins). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.

= Sujets réalisés (2018-2019) =

* [[Transport optimal par coupe 1D et transfert de couleurs entre images]] (Lucas CHARDONNET)
* [[Génération et résolution de labyrinthes II]] (Romain THEODET)
* [[Rest & Pub-Sub : protocole hybride pour l'IoT]] (Ewan RAKOTOANOSY)
* [[La suite de Conway et la classification périodique des "éléments"]] (Yohann THEPAUT)
* Initiation à la démonstration sur ordinateur et certification de logiciel
* [[Dilemme du prisonnier]] (Christophe CARMAGNAC)

= Sujets proposés (2018-2019) =

* Transport optimal par coupe 1D et transfert de couleurs entre images
* Génération et résolution de labyrinthes II
* REST + Pub/Sub : protocole hybride pour l’IoT
* La suite de Conway et la classification périodique des "éléments"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Dilemme du prisonnier

== Transport optimal par coupe 1D et transfert de couleurs entre images ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous verrons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.

[[Fichier:Ex-transfert-couleur-OT.png]]

* Objectifs:
*# comprendre ce qu'est une image niveaux couleur, et ce qu'on appelle le transfert de couleurs.
*# comprendre le principe du transport optimal (discret).
*# comprendre et décrire le principe du transport optimal par coupe 1D, et comment se fait le calcul du meilleur transport dans ce cas.
*# Coder un programme de transfert de couleur, qui prend deux images couleurs et réalise le transfert de couleurs.
*# On pourra ensuite réfléchir à quelques améliorations simples (espace couleur YUV, grouper les pixels).
* Liens pour démarrer
** Le vrai "Transport Optimal" est vite très mathématique (ce sont des mesures qui sont transportées), mais on peut l'aborder beaucoup plus simplement dans le cas discret (un nombre fini de valeurs) comme une simple assignation entre deux ensembles.
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

== Génération et résolution de labyrinthes II ==

* Tuteur: François Boussion
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter un labyrinthe avec une structure de données simple
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
*# introduire des poids pour varier le labyrinthe
*# comment faire un labyrinthe sur grille hexagonale avec des tableaux.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== REST + Pub/Sub : protocole hybride pour l’IoT ==

* Tuteur: David Télisson
* Résumé: L’avènement de l’Internet des Objets (IoT) depuis une dizaine d’années a fait apparaitre des problématiques propres aux protocoles de communications liées à ces objets. En effet, l’échange de données dans ce contexte nécessite de tenir compte (au moins) des paramètres suivant :
*# Autonomie énergétique souvent limitée
*# Faible puissance des processeurs et taille réduite de la mémoire
*# Disponibilité « aléatoire » de l’accès aux réseaux de communication

De nombreux protocoles cohabitent et la littérature du domaine foisonne d’exemples autour des réseaux dédiées (LORA, Sigfox, etc.) et des protocoles applicatifs (OPC-UA, MQTT, CoaP, XMPP) mais force est de constater que dans la réalité, ces solutions ne répondent pas toujours aux besoins des concepteurs qui leurs préfèrent encore le protocole HTTP. Celui-ci offre l’avantage d’implémenter un protocole applicatif (REST) en même temps qu’un protocole de transport de haut niveau (TCP/IP) permettant de passer les pare-feu. Cependant, la version actuel d’HTTP ne répond pas vraiment aux critères énoncés précédemment.
Depuis quelques années émerge donc l’idée d’enrichir HTTP pour créer un protocole hybride qui mêlerait les avantages de REST avec ceux proposés par les mécanismes de type Publish/Subscribe (MQTT, AMQP, JMS, etc.). En attendant cette éventuelle évolution, peut-on envisager de mettre en place un mécanisme de type Pub/Sub avec le protocole Websocket au-dessus d’HTTP ?

* Objectifs:
*# Etudier et faire une synthèse des deux approches : REST et Pub/Sub
*# Implémentez un PoC (proof of concept) d’une solution hybride qui met en œuvre un mécanisme de Pub/Sub sur Websocket. .
*# Présenter un protocole de test pour valider ou invalider cette solution

* Liens pour démarrer :
** https://nsrc.org/workshops/2018/apricot/iot/presentations/mqttvsrest_v4.pdf
** http://www.tigli.fr/lib/exe/fetch.php?media=cours:tutorial_mqtt_mit_2015_2016.pdf
** https://openclassrooms.com/fr/courses/3449001-utilisez-des-api-rest-dans-vos-projets-web
** http://www.lirmm.fr/~tibermacin/ens/ws/expose.pdf

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ==

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

== Dilemme du prisonnier ==

* Tuteur: Gerald Cavallini
* Résumé: Le dilemme du prisonnier caractérise en théorie des jeux une situation où deux joueurs auraient
intérêt à coopérer, mais où, en l’absence de communication entre les deux joueurs, chacun choisira
de trahir l'autre si le jeu n'est joué qu'une fois.

On peut informatiquement modéliser ce dilemme à l’aide de matrices de gains et conserver la
mémoire des choix de l’adversaire. Ce modèle appliqué à un grand nombre d’individus peut être
utilisé pour comprendre l’émergence de stratégies stables dans l’économie, l’écologie, l’évolution
des espèces ...

On peut visualiser spatialement les interactions entre individus en les représentants par des pixels et
en leurs associant une couleur en fonction de leurs stratégies.

[[Fichier:Dilemme.png]]

* Objectifs
*# Comprendre le dilemme du prisonnier
*# Comprendre la notion de stratégie
*# Penser un modèle spatiale pour « opposer » des individus qui appliquent des stratégies différentes
*# Développer une interface pour visualiser dans le temps l’évolution d’une population d’individus adoptants des stratégies différentes.

* Lien :
*# [https://fr.wikipedia.org/wiki/Dilemme_du_prisonnier Dilemme du prisonnier Wikipedia]
*# [http://cormas.cirad.fr/fr/applica/dps.htm Site spécifique]

= Sujets réalisés (2017-2018) =

* [[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]
* [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] (Nils Ruet, 2018)
* [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] (Rémi Bouvier, 2018)
* [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] (Robin Wagner, 2018)
* [[Pavages de Penrose]] (Brunelle Cordier-Pierre-Bès, 2018)

= Sujets proposés (2017-2018) =

* Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
* Transformées en distance, diagramme de Voronoi et applications en geometry processing
* Pavages de Penrose

== [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
* Objectifs:
*# comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
*# décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
*# décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
*# Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Watershed_(image_processing) Watershed Wikipedia]]
** Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf PDF]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] ==

* Tuteur: Laurent Vuillon
* Résumé: L'idée de ce projet est de se familiariser avec les techniques de fouille de données textuelles à partir des "Exercices de style" de R. Queneau (https://fr.wikipedia.org/wiki/Exercices_de_style). On cherchera à comprendre la structure du vocabulaire du corpus de textes, à utiliser les techniques de TF/IDF pour extraire les mots significatifs du corpus puis à tester les techniques de LDA (Allocation de Dirichlet latente) pour extraire automatiquement les thématiques du corpus afin de construire des regroupements par thème. On pourra également proposer des visualisations des résultats afin de rendre accessible visuellement l'analyse de données produite sur le corpus de documents.
* Objectifs: Introduction à la fouille de données au travers d'un cas pratique
* Pour aller plus loin
** http://blogperso.univ-rennes1.fr/stephane.tuffery/
** http://www.editionstechnip.com/en/catalogue-detail/1005/data-mining-et-statistique-decisionnelle.html
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es
** https://fr.wikipedia.org/wiki/TF-IDF
** "Recherche d'information : applications, modèles et algorithmes; Data mining, décisionnel et big data" de Amini et Gaussier aux éditions Eyrolles.

== [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
*# Identifier le lien avec l'axe médian et les squelettes
*# Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
*# Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
*# Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
** [[https://en.wikipedia.org/wiki/Distance_transform Transformée en distance Wikipedia]]
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
** [[http://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]

== [[Pavages de Penrose]] ==

* Tuteur : Pierre Hyvernat
* Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

[[Fichier:P2.png]]

* Objectifs
*# comprendre les notion de pavage périodique, non périodique et apériodique,
*# comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
*# comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
*# écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
*# utiliser ces méthodes pour générer d'autres types de pavages apériodique.

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Pavage_de_Penrose pavage de Penrose (wikipedia]]
** [[https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf Penrose Tiling (Marting Gardner, en anglais)]]

== [[Algorithmes d'analyse syntaxique]] ==

* Tuteur : Pierre Hyvernat

* Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données ''textuelles'' et ''structurées''. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle ''d'analyseur syntaxique'' ou de ''parseur''. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.

* Objectifs :
*# étudier la formalisation du problème à travers la notion de ''langage'' et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
*# comprendre le lien entre les langages et les automates (automates finis / automates à pile)
*# implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
*# comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (''LL*(k)'', ''LR'', etc.)
*# à partir de là, de nombreuses pistes sont ouvertes :
*#* essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
*#* comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
*#* améliorer l'efficacité des parseurs produits
*#* ajouter des fonctionnalités,
*#* ...

* Liens pour démarrer :
** [[https://en.wikipedia.org/wiki/Parsing page wikipedia "parsing"]]
** [[https://en.wikipedia.org/wiki/Recursive_descent_parser page wikipedia "recursive descent parser"]]
** Le livre référence sur le parsing est probablement "Compilers: Principles, Techniques, and Tools" de Aho, Sethi et Ullman (le "dragon book")
** [[https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ exemples de notes cours de compilation]]

= Sujets réalisés (2016-2017) =

* [[Algorithme de rendu de scène 3D par Z-buffer]]
* [[Traitement d'image]]
* [[Nim et la théorie des jeux impartiaux]]
* [[Calculabilité et modèles de calcul]]
* [[Génération et résolution de labyrinthes]]

= Sujets proposés (2016-2017) =

== [[Algorithme de rendu de scène 3D par Z-buffer]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
* Objectifs:
*# décrire le principe de la projection 3D vers 2D
*# décrire la rastérisation des triangles sur une image en pixel
*# expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
*# expliquer comment les couleurs sont calculées par pixel
*# indiquer les qualités et limitations de l'algorithme
* Pour aller plus loin
*# mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
*# expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Z-buffer Wikipedia]]
** [[https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/overview-rasterization-algorithm Scratch a pixel]]

== [[Traitement d'image]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
* Objectifs:
*# identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
*# identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
*# comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
*# choisir un ou deux algorithmes de traitement et les expliquer en détails
* Pour aller plus loin
*# Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Traitement_d%27images Wikipedia]]
** [[http://www.ipol.im/ Image Processing on line]] (permet de tester en ligne des algorithmes sur vos images)

== [[Nim et la théorie des jeux impartiaux]] ==

* Tuteur: Pierre Hyvernat

* Étudiant : Luca Chapelle

* Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
* Objectifs:
*# comprendre la théorie du jeu de Nim (et la programmer)
*# comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
*# regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
*# programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

* Liens pour commencer
** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]
** [https://fr.wikipedia.org/wiki/Jeu_de_Grundy jeu de Grundy]

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== Initiation à la démonstration sur ordinateur et certification de logiciel ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Calculabilité et modèles de calcul]] ==

* Tuteur: Rodolphe Lepigre
* Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
* Objectifs:
*# comprendre la notion de fonction calculable,
*# comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
*# regarder et comparer quelque modèles de calcul,
*# programmer un modèle de calcul et comprendre les limitations pratiques.

* Liens pour commencer:
** https://fr.wikipedia.org/wiki/Calculabilité
** https://fr.wikipedia.org/wiki/Machine_de_Turing
** https://fr.wikipedia.org/wiki/Lambda-calcul
** https://fr.wikipedia.org/wiki/Jeu_de_la_vie

== [[Génération et résolution de labyrinthes]] ==

* Tuteur: <strike>Jacques-Olivier Lachaud</strike> Xavier Provençal
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter avec une structure de données un labyrinthe
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== Pavages par polyomino ==

* Tuteur: Xavier Provençal
* Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?
On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?
* Objectifs :
*# Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
*# Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
*# Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
* Pour aller plus loin :
*# Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
*# Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Polyomino Polyomino]]
** [[https://en.wikipedia.org/wiki/Polyomino Polyomino (en)]]
** [[https://fr.wikipedia.org/wiki/Pavage_par_des_polygones_r%C3%A9guliers Pavages]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-22T16:44:31Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-22T11:35:31Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.jpg")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. De même pour l'image C.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 
 
[[Fichier:experimentation1a.jpg|600px]] 
 
[[Fichier:experimentation1b.jpg|600px]] 
</li>
 
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 
 
[[Fichier:experimentation2a.jpg|600px]] 
 
[[Fichier:experimentation2b.jpg|600px]] 
</li>
 
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 
 
[[Fichier:experimentation3a.jpg|600px]] 
 
[[Fichier:experimentation3b.jpg|600px]] 
 
On peut aussi inverser le rôle des images. 
 
[[Fichier:experimentation3c.jpg|600px]] 
</li>
 
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 
 
[[Fichier:experimentation4a.jpg|600px]] 
 
[[Fichier:experimentation4b.jpg|600px]] 
 
Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]
*Source de l'image A bis : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B bis : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

Fichier:Experimentation4b.jpg

2019-05-22T11:32:43Z

Chardonnet :

Fichier:Experimentation4a.jpg

2019-05-22T11:31:50Z

Chardonnet :

Fichier:Experimentation3c.jpg

2019-05-22T11:31:20Z

Chardonnet :

Fichier:Experimentation3b.jpg

2019-05-22T11:30:49Z

Chardonnet :

Fichier:Experimentation3a.jpg

2019-05-22T11:30:20Z

Chardonnet : *Source de l'image A : https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 *Source de l'image B : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All...

*Source de l'image A : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-22T11:29:14Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.jpg")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. De même pour l'image C.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 

[[Fichier:experimentation1a.jpg|600px]] 
 
[[Fichier:experimentation1b.jpg|600px]] 
</li>
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 

[[Fichier:experimentation2a.jpg|600px]] 
 
[[Fichier:experimentation2b.jpg|600px]] 
</li>
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 

[[Fichier:experimentation3a.jpg|600px]] 
 
[[Fichier:experimentation3b.jpg|600px]] 

On peut aussi inverser le rôle des images. 

[[Fichier:experimentation3c.jpg|600px]] 
</li>
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour les ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 

[[Fichier:experimentation4a.jpg|600px]] 
 
[[Fichier:experimentation4b.jpg|600px]] 

Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]
*Source de l'image A bis : [[https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340 https://www.deviantart.com/rockspire/art/Canyon-concept-art-187906340]]
*Source de l'image B bis : [[https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750 https://vignette.wikia.nocookie.net/starwars/images/b/bd/All_Terrain_Exploration_Droid.png/revision/latest?cb=20140511072750]]

Fichier:Experimentation2b.jpg

2019-05-22T11:24:37Z

Chardonnet :

Fichier:Experimentation2a.jpg

2019-05-22T11:23:16Z

Chardonnet : *Source de l'image A : https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/

*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]

Fichier:Experimentation1b.jpg

2019-05-22T11:21:00Z

Chardonnet :

Fichier:Experimentation1a.jpg

2019-05-22T11:18:08Z

Chardonnet :

*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Fichier:Experimentation1a.jpg

2019-05-22T11:16:52Z

Chardonnet : Source de l'image A : [https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/] Source de l'image B : [https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]

Source de l'image A : [https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]
Source de l'image B : [https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-22T11:14:02Z

Chardonnet : /* Expérimentations */

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.jpg")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. De même pour l'image C.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 

[[Fichier:experimentation1a.jpg|600px]] 

[[Fichier:experimentation1b.jpg|600px]] 
</li>
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité. 

[[Fichier:experimentation2a.jpg|600px]] 

[[Fichier:experimentation2b.jpg|600px]] 
</li>
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 

[[Fichier:experimentation3a.jpg|600px]] 

[[Fichier:experimentation3b.jpg|600px]] 

On peut aussi inverser le rôle des images. 

[[Fichier:experimentation3c.jpg|600px]] 
</li>
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour les ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale. 

[[Fichier:experimentation4a.jpg|600px]] 

[[Fichier:experimentation4b.jpg|600px]] 

Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-22T11:13:18Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

best_cost(im1_rgb, im2_rgb)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.jpg")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. De même pour l'image C.

== Expérimentations ==

<ul>
<li>
Si l'on fait l'inverse de ce qui a été fait précédemment, en prenant l'image du graffiti en palette, on obtient une image de sortie chargée en "bruit", du fait du fort contraste de couleurs que présente le graffiti. 

[[Fichier:experimentation1a.jpg|600px]] 

[[Fichier:experimentation1b.jpg|600px]] 
</li>
<li>
En prenant une image palette présentant toute les nuances entre le noir et le blanc, l'image de sortie est parfaitement net, du fait de sa linéarité.

[[Fichier:experimentation2a.jpg|600px]] 

[[Fichier:experimentation2b.jpg|600px]] 
</li>
<li>
En prenant deux images aux couleurs assez homogènes mais très contrastées entre elles, l'image de sortie est plutôt correcte malgré quelques imperfections sur certaines couleurs (notamment les zones sombres). 

[[Fichier:experimentation3a.jpg|600px]] 

[[Fichier:experimentation3b.jpg|600px]] 

On peut aussi inverser le rôle des images. 

[[Fichier:experimentation3c.jpg|600px]] 
</li>
<li>
On peut essayer de prendre les deux images recolorisées entre elles pour les ré-effectuer un transfert, et observer si l'image de sortie est proche de l'originale.

[[Fichier:experimentation4a.jpg|600px]] 

[[Fichier:experimentation4b.jpg|600px]] 

Les couleurs sont reconnues dans leur globalité, mais l'information dite "géographique" est perdue, vu que chaque pixel est traité indépendamment des autres.
</li>

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Fichier:Transport-simp2.jpg

2019-05-21T20:46:14Z

Chardonnet : Chardonnet a téléversé une nouvelle version de Fichier:Transport-simp2.jpg

Dilemme du prisonnier

2019-05-19T13:42:18Z

Chardonnet : Correction d'absence de ponctuation à un certain endroit

== Introduction ==

Le dilemme du prisonnier à été inventer en 1950 par Albert William Tucker et fait parti de la théorie des jeux qui est un domaine des mathématiques étudiant les interactions entre différents individus qui sont conscients ou non de ces interactions. Ils devront donc faire des choix dont ils sont conscients ou non lors de ces interactions.

== Le dilemme du prisonnier ==

Les individus sont soumis dans le dilemme du prisonnier à une interaction où ils ont deux choix : soit ils coopèrent avec l’autre individu, soit ils le trahissent. Les individus sont récompensés selon la matrice des Paiements suivante :

[[Fichier:Tableau matrice paiements.PNG]]

L’intérêt de la configuration actuelle de la matrice des Paiements actuelle est que les individus ont un intérêt certain à trahir l’autre mais que la coopération est la meilleur option pour les deux individus. On représente l’intérêt à trahir par rapport à la coopération par la variable B qui dans notre exemple est égale à 1,85.

Afin de simplifier notre modèle nous ne considérerons que deux comportements possibles qui sont :

-Le Croyant qui coopérera systématiquement

-Le Traître qui trahira systématiquement

== Spatialisation du Dilemme du prisonnier ==

Nous spatialisons le dilemme du prisonnier afin d’expliquer en partie des observations dans le vivant où les êtres vivants coopèrent entre eux alors qu’ils ont tout à y gagner en ne le faisant pas. Pour étayer nos propos on propose la citation suivante :« The prisoners’ Dilemma is an interesting metaphor for the fundamental biological problem of how cooperative behaviour may evolve and be maintained »([https://www.researchgate.net/publication/216634494_Evolutionary_Games_and_Spatial_Chaos Nowak, M.A. et May, R.M. 1992. Evolutionary games and spatial chaos]). En spatialisant le dilemme du prisonnier nous pouvons observer l’évolution des pratiques dans des situations variées. Il est à noter que nous pouvons aussi établir des liens entre les domaines de l’économie et de la sociologie notamment.

Les prisonniers sont au voisinage de Moore (8 voisins) de tel sorte à ce que dans l’espace les voisins d’un prisonnier lambda soient disposés de la manière suivante :

1 2 3

4 P 5

6 7 8

L’espace dans lequel ils évoluent est un espace toroïdale (bordures ouvertes) en forme de carré de dimension n*n. On peut aussi le représenter comme une matrice carré avec les bordures qui communiquent entre elles.

À Chaque tour les prisonniers vont jouer au dilemme du prisonnier avec chacun de leurs voisins. Ils obtiendront un score conformément à leurs choix et à la matrice des Paiements. Puis chacun leur tour mettre à jour leur stratégie en fonction du score des voisins.

Afin de pouvoir visualiser l'évolution de notre espace nous avons créer un programme en Java afin de profiter des aspects suivant de Java:

Le premier est la programmation objet, cela nous permet de diviser la complexité de notre programme dans plusieurs objets interagissants entre eux. Nous pouvons aussi créer des abstractions d'objets qui nous permettent d'avoir des objets qui ont des comportements différents les uns des autres mais ayants tous des points communs ce qui permet de les manipulés plus facilement.

Le second est la bibliothèque Abstract Windows Toolkit (ou AWT pour faire plus court). Qui nous permet de faire sans trop de problèmes une fenêtre personnalisable qui affiche des composants grapihques. Ces composants étant eux mêmes variées, on utilisera surtout les propriétés du composant Canvas dans ce programme. Grâce à l’héritage permis par la programmation objet nous pouvons créer nos propres composants graphiques pour afficher nos résultats.

Notre programme crée donc une fenêtre qui affiche les prisonniers en fonction de leur stratégie actuelle et de leur dernière stratégie.Le code couleur est le suivant :

-en rouge les Traîtres qui l’ont été pendant 2 tours consécutifs

-en jaune les Croyants qui sont devenus Traîtres

-en vert les Traîtres devenus Croyants

-en bleu les Croyants qui l’ont été pendant 2 tours consécutifs

== Une expérience intéressante ==

On propose dans cette partie de commencer à étudier un cas en particulier. Dans cette première expérience nous fixons B à 1,85 et plaçons un traître au milieu de croyants dans une grille de 301 par 301. Nous pensons que cette configuration donnera des résultats intéressants car B n'est pas assez grand pour permettre une domination complète des Traîtres ou pas assez petit pour permettre une domination complète des Croyants.

Après quelques tours de la simulation nous observons l'image suivante:

[[Fichier:Screen_première_exp.PNG]]

Nous pouvons voir grâce à la bordure verte que le carré de traîtres au centre de l'image est en train de rétrécir alors que dans les coins des îlots de traîtres apparaissent comme nous le montre la grand quantité de jaune.

Nous passons sous silence quelques tours pour arriver à la situation suivante:

[[Fichier:Screen première exp 2.PNG]]

Nous pouvons voir à présent que les comportements dans la simulation varient beaucoup comme témoignent l'abondance de prisonniers affichés en jaune et en vert.

Lors du déroulé de cette simulation nous avons pus récolter C qui est le rapport entre le nombre de croyants dans la matrice sur le nombre de prisonniers au total. Cette variable nous permettra de visualiser l'évolution du nombre de croyants dans la simulation rapidement. Nous allons maintenant montrer son évolution au court du temps dans la simulation.

[[Fichier:Screen Graph_première exp.PNG]]

Nous pouvons ainsi observer sur le graphique que C semble tendre vers environ 0.3 montrant de ce fait que la simulation est dominé par les traîtres mais que les croyants résistent tout de même. Les variations de C ne sont pas de ce que l'on observe sur le graphique et la simulation cycliques ce qui veut dire que même si le nombre de croyants semble à peut près stable il n'en reste pas moins fluctuant.

== Automatisation des expériences ==

Nous avons pus observer une simulation particulière mais nous devons maintenant pouvoir faire des observations autres que visuelles car nous n’avons pas le temps de le faire pour toutes les expériences permisses par notre modèle. On n’as alors décidé donc de créer un objet dans le programme pour extraire les données des expériences et nous les résumées. Nous ne montrerons toutefois que les expériences que l’on juge intéressantes.

Nous voulons tout d'abord mesurer l'influence de B sur l'évolution d'une répartition aléatoire. Pour cela nous fixerons les paramètres suivants pour chaque simulation. Dans chaque simulation on aura systématiquement 10% de traîtres répartis aléatoirement parmi 90% de croyants. La dimension des matrices sera de 200*200. Nous ferons variez B entre 1.75 et 2.

Pour un B appartenant à [1.75;1.8[ On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen_B_1,75_10%.PNG]]

On observe des réseaux de traîtres interconnectés entre eux mais pouvant être indépendants avec une taille minimale d'un carré de 4 traîtres. On observe aussi des zones ou les prisonniers alternent entre traître et croyant, on les repères en cherchant les zones en jaune ou en vert.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 1,75 10%.PNG]]

Ce graphique nous permet d'affirmer que la simulation est à peut près stable car on observe toujours des petits chutes du nombre de croyants. C semble tendre par ailleurs vers 0.7.

Pour un B appartenant à [1.8;2[ On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen B 1,9 10%.PNG]]

On observe une situation chaotique avec une majorité de Traîtres et des îlots de Croyants apparaissant et disparaissant au fur et à mesure de la simulation. On remarque aussi beaucoup de jaune et de verts sur les images cela nous montre que les comportements des prisonniers changent beaucoup.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 1,9 10%.PNG]]

Ce graphique nous montre que la simulation n'est pas stable mais que C se stabilise vers 0.3.

Il est aussi à noter que sur les images B est à 1.9 et que plus B tend vers 1.8, C se stabilise vers 0.4.

Pour un B supérieur à 2 On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen B 2 10%.PNG]]

On observe que les traîtres occupent quasiment tout l'espace et que les croyants sont regroupés en îlots qui s'étendent et se rétrécissent périodiquement.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 2 10%.PNG]]

Ce graphique nous montre que la simulation est très stable et que C tend vers 0.02.

== Améliorations à apporter ==

Nous n’avons pas exploré toutes les possibilités de notre modèle nous discuterons ici des améliorations à apportées à notre modèle.

La première des améliorations que nous pourrions apporter pourrait être l’introduction de comportements avec un historique des actions passées de leurs voisins. Cela nous permettrait d’avoir des stratégies plus complexes à étudiées.

La deuxième amélioration que nous pourrions apporter serait une amélioration au niveau du code. On proposerais de faire en sorte d’avoir un objet Stratégie qui se passerait de prisonnier en prisonnier et grâce à la programmation objet on pourrait créer des Stratégies variées avec peu de changements dans la structure du programme.

== Sources ==

[http://cormas.cirad.fr/fr/applica/dps.htm Lien vers le site du cormas]

[https://www.researchgate.net/publication/216634494_Evolutionary_Games_and_Spatial_Chaos Lien vers l'article original]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-18T10:08:17Z

Chardonnet :

Le but du projet est de trouver une technique permettant la meilleure recolorisation d'une image A avec les pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B aux pixels de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise pour cela la technique du transport optimal qui va permettre d'associer une valeur au transport entre pixels. Cette valeur s'appelle le coût.

== Principe du transport optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques unes :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transport de couleurs par coupe 1D ==

Le coût choisi pour le transport de couleurs est <math>c(x,y)=|x-y|^2</math>, car il offre une grande sensibilité quant à la distance entre deux pixels.

=== Simplification du transport optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixel comme un point, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rang entre les deux images, pour déterminer que tel pixel de l'image B prendra la place de tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]] (A)

[[Fichier:transport-imB.jpg|600px]] (B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert, que l'on abrège en rgb (pour red, green, blue). Chacune de ces composantes prend des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
Un pixel se note donc, par exemple : 
<math>x = (x_{rouge},x_{vert},x_{bleu})</math>

On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math> quelconque. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnées. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal Simplification du transport optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme les pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le tranport doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert des couleurs ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certain vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associés pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]] (C)

== Algorithme en python ==

<pre>
#!/usr/bin/env python

from PIL import Image
from random import randint
from operator import itemgetter
import time

best_u = (0,0,0)
quality = 0

""" Légende :
im : image
_RGB : objet image en rgb
_rgb : liste de tuples rgb
_ord : _rgb ordonné selon u
u : vecteur tiré aléatoirement
cost : coût
_cur : courant """

def intro(fichier1, fichier2):
""" Entrées : deux fichiers image
Sortie : booléen
Vérifie la compatibilité de taille et mode des deux images """

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

print()
print("=== Image A ===\nFormat : {}\nTaille : {}\nMode : {}".format(im1.format, im1.size, im1.mode))
print()
print("=== Image B ===\nFormat : {}\nTaille : {}\nMode : {}".format(im2.format, im2.size, im2.mode))
print()
if im1.size==im2.size and im1.mode==im2.mode :
print("Fichiers OK")
print()
res = True
else :
print("ATTENTION, incompatibilité des fichiers")
res = False

im1.close()
im2.close()
return res

def to_rgb(im):
""" Entrée : image
Sortie : liste de tuples
Convertie un objet image en liste rgb """

im_RGB = im.convert('RGB')
size = [ im_RGB.size[0], im_RGB.size[1] ]
im_rgb = []

for j in range (0, size[1]):
for i in range (0, size[0]):
pix = im_RGB.getpixel((i, j))
im_rgb.append(pix)

return(im_rgb)

def to_ord(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple (vecteur)
Sortie : un tuple de deux listes de tuples
Ordonne deux listes rgb selon un vecteur u """

im1_ord = []
im2_ord = []

for i in range(0,len(im1_rgb)):
px1_ord = ( im1_rgb[i][0]*u[0] + im1_rgb[i][1]*u[1] + im1_rgb[i][2]*u[2], im1_rgb[i][0], im1_rgb[i][1], im1_rgb[i][2], i )
im1_ord += [px1_ord]

px2_ord = ( im2_rgb[i][0]*u[0] + im2_rgb[i][1]*u[1] + im2_rgb[i][2]*u[2], im2_rgb[i][0], im2_rgb[i][1], im2_rgb[i][2], i )
im2_ord += [px2_ord]

im1_ord.sort()
im2_ord.sort()

for i in range(0,len(im1_ord)):
#im2_ord[i][4] = im1_ord[i][4]
#im2_ord[i] = tuple(im2_ord[i])
im2_ord[i] = (im2_ord[i][0],im2_ord[i][1],im2_ord[i][2],im2_ord[i][3],im1_ord[i][4])

return(im1_ord, im2_ord)

def cost(im1_rgb, im2_rgb, u):
""" Entrée : deux listes de tuples et un tuple
Sortie : un entier
Calcul le coût entre deux listes rgb selon un vecteur u """

im12_ord = to_ord(im1_rgb, im2_rgb, u)
im1_ord = im12_ord[0]
im2_ord = im12_ord[1]
dist = 0.0
for i in range (0, len(im1_rgb)):
dist += 1.0*(im1_ord[i][1]-im2_ord[i][1])**2 + 1.0*(im1_ord[i][2]-im2_ord[i][2])**2 + 1.0*(im1_ord[i][3]-im2_ord[i][3])**2

return dist

def best_cost(im1_rgb, im2_rgb):
""" Entrée : deux listes de tuples
Sortie : un entier
Calcul le meilleur coût entre deux listes rgb """

global best_u

u = (randint(-500,500), randint(-500,500), randint(-500,500)) # rand en flottant !
best_cost = cost(im1_rgb, im2_rgb, u)

nb_u = 20 # nombre de tirages de u
cost_list = [] # liste de tout les coûts que l'on va calculer
for i in range(0, nb_u):
# print("Calcul du meilleur coût en cours {}/{}".format(i+1, nb_u))
u = (randint(-500,500), randint(-500,500), randint(-500,500))
cost_cur = cost(im1_rgb, im2_rgb, u)
cost_list += [ cost_cur ]

# echo
print( i+1, best_cost, cost_cur )

if cost_cur < best_cost :
best_cost = cost_cur
best_u = u

quality = min(cost_list) / max(cost_list)

print()
print("Meilleur vecteur u :", best_u)
print("Qualité :", quality)
print()
return best_cost

def new_image(fichier1, fichier2, fichier3):
""" Entrées : deux fichiers image, puis le nom du fichier créé
Sortie : rien
Créer un fichier en transférant la palette du fichier 2 vers le fichier 1 """

global best_u

# echo
inittime = time.time()
print ('init',inittime)

im1 = Image.open(fichier1)
im2 = Image.open(fichier2)

im1_rgb = to_rgb(im1)
im2_rgb = to_rgb(im2)

# echo
intime = time.time() - inittime
print ('toRgb ',intime)
print()

best_cost(im1_rgb, im2_rgb)

# echo
intime = time.time() - inittime
print ('best_cost ',intime)

# on récuperre les deux listes ordonnées par le meilleur vercteur
var = to_ord(im1_rgb, im2_rgb, best_u)
im1_ord = var[0]
im2_ord = var[1]
im3_rgb = [0]*len(im1_ord)

# echo
intime = time.time() - inittime
print ('to_ord ',intime)

im2_ord.sort(key=itemgetter(4))

im3_rgb = im2_ord
for i in range(0,len(im2_ord)):
im3_rgb[i] = im2_ord[i][1:4]
im3_rgb[i] = tuple(im3_rgb[i])

# echo
intime = time.time() - inittime
print ('im3_rgb ',intime)

im3 = Image.new(im1.mode, im1.size)
im3.putdata(im3_rgb)

# echo
intime = time.time() - inittime
print ('im3 ',intime)

print()
print("sauvegarde du nouveau fichier")
im3.save(fichier3, "BMP")
print("Fin")

im1.close()
im2.close()

def main(fichier1, fichier2, fichier3):
if intro(fichier1, fichier2):
new_image(fichier1, fichier2, fichier3)

</pre>

Pour exécuter le programme avec, par exemple, deux fichiers "imageA.jpg" et "imageB.jpg", on entre dans l'interpréteur la fonction

<pre>main("imageA.jpg", "imageB.jpg", "imageC.jpg")</pre>

L'image C sera alors générée.

Remarque : les deux fichiers d'entrée ne sont pas obligatoirement au même format, mais doivent tout deux rester des images. De même pour l'image C.

== Expérimentation ==

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-17T10:41:47Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-17T09:55:55Z

Chardonnet :

Le but du projet est de trouver la meilleure recolorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B au pixel de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise la technique du transport optimal, qui va permettre d'associer une valeur au transport entre pixels, que l'on appelle le coût.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images, pour déterminer que tel pixel de l'image B prendra la place tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]](A)

[[Fichier:transport-imB.jpg|600px]](B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme nos pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T21:23:07Z

Chardonnet :

Le but du projet est de trouver, au mieux, la recolorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B au pixel de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise la technique du transport optimal, qui va permettre d'associer une valeur au transport entre pixels, que l'on appelle le coût.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
À chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images, pour déterminer que tel pixel de l'image B prendra la place tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]](A)

[[Fichier:transport-imB.jpg|600px]](B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme nos pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T21:08:49Z

Chardonnet :

Le but du projet est de trouver, au mieux, la recolorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B au pixel de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise la technique du transport optimal, qui va permettre d'associer une valeur au transport entre pixels, que l'on appelle le coût.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images, pour déterminer que tel pixel de l'image B prendra la place tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]](A)

[[Fichier:transport-imB.jpg|600px]](B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme nos pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

== Sources ==
*Source de l'image A : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]
*Source de l'image B : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Fichier:Transport-imC.jpg

2019-05-16T21:08:39Z

Chardonnet :

Fichier:Transport-imB.jpg

2019-05-16T21:08:09Z

Chardonnet : Source : https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/

Source : [[https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/ https://www.flickr.com/photos/wolfgangstaudt/2252688630/in/photostream/]]

Fichier:Transport-imA.jpg

2019-05-16T21:07:25Z

Chardonnet :

Source : [[https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/ https://pixabay.com/photos/tag-street-art-mural-graffiti-1036811/]]

Fichier:Transport-imA.jpg

2019-05-16T21:06:13Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T20:49:17Z

Chardonnet :

Le but du projet est de trouver, au mieux, la recolorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A. Pour cela il va falloir associer chacun des pixels de l'image B au pixel de l'image A dont il est le plus proche en terme de distance (dans l'espace des couleurs).

On utilise la technique du transport optimal, qui va permettre d'associer une valeur au transport entre pixels, que l'on appelle le coût.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différemment selon les domaines d'application. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même aire et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est-à-dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manières de calculer un coût, qui sont chacune appropriées au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires (c'est à dire composé du même nombre de pixels) où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]](1)

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
On a alors <math>C=\sum_{i=1}^n c(x_i,y_i)</math> 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images, pour déterminer que tel pixel de l'image B prendra la place tel pixel de l'image A. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit sur l'image (1)).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg|600px]](A)

[[Fichier:transport-imB.jpg|600px]](B)

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes les deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs, par convention, de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]L'image A est en cyan et l'image B en magenta.

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal [https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images#Simplification_du_transfert_optimal]. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme nos pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math>, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal, soit le meilleur coût possible. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T17:52:45Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]]

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On appelle x les pixels de l'image A et y les pixels de l'image B. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>. 
Ici, comme nos pixels x et y sont chacun représentés selon leurs trois composantes rgb, la distance au carré entre deux pixels est la somme des différences entre composantes correspondantes, le tout au carré, soit 
<math>c(x_i,y_i)=|x_i-y_i|^2=(x_{i_{rouge}}-y_{i_{rouge}})^2+(x_{i_{vert}}-y_{i_{vert}})^2+(x_{i_{bleu}}-y_{i_{bleu}})^2</math>. 

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T16:40:30Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]]

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 

[[Fichier:transport-im3D-2.jpg|600px]]

On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

Fichier:Transport-im-cout.jpg

2019-05-16T16:38:27Z

Chardonnet :

Fichier:Transport-im-ord2.jpg

2019-05-16T16:23:18Z

Chardonnet :

Fichier:Transport-im-ord1.jpg

2019-05-16T16:22:57Z

Chardonnet :

Fichier:Transport-im3D-2.jpg

2019-05-16T16:20:32Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T16:20:03Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 

[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]]

==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg|600px]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 

[[Fichier:transport-im-ord1.jpg|600px]]

On se retrouve alors dans un cas similaire à la section Simplification du transport optimal. On peut ainsi faire correspondre les pixels entre eux. 

[[Fichier:transport-im-ord2.jpg|600px]]

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.

[[Fichier:transport-im-cout.jpg|600px]]

Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 

[[Fichier:transport-imC.jpg|600px]]

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T15:46:38Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points, on définit un vecteur unitaire <math>\vec{u}</math>. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T15:19:43Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Puis on répète l'opération, jusqu'à que toutes les quantités de <math>f</math> soient transférées dans <math>g</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T15:16:43Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (comme on le voit deux images plus haut).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T15:12:34Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 

[[Fichier:transport-simp1.jpg|600px]]

Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 

[[Fichier:transport-simp2.jpg|600px]]

Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (ici, le vecteur <math>\vec{u}</math>).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 

[[Fichier:transport-im3D-1.jpg|600px]]

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Fichier:Transport-im3D-1.jpg

2019-05-16T15:11:30Z

Chardonnet :

Fichier:Transport-simp2.jpg

2019-05-16T15:11:12Z

Chardonnet :

Fichier:Transport-simp1.jpg

2019-05-16T15:09:56Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T14:32:38Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images.

Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 

[[Fichier:transport-opti.jpg|600px]]

On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 
 
[[Fichier:transport-simp1.jpg]] 
 
Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 
 
[[Fichier:transport-simp2.jpg]] 
 
Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (ici, le vecteur <math>\vec{u}</math>).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 
 
[[Fichier:transport-im3D-1.jpg]] 
 

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Fichier:Transport-opti.jpg

2019-05-16T14:10:57Z

Chardonnet :

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T14:08:33Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images. 
Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 
 
[[Fichier:transport-opti.jpg]] 
 
On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 
 
[[Fichier:transport-simp1.jpg]] 
 
Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 
 
[[Fichier:transport-simp2.jpg]] 
 
Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (ici, le vecteur <math>\vec{u}</math>).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport-imA.jpg]][[Fichier:transport-imB.jpg]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 
 
[[Fichier:transport-im3D-1.jpg]] 
 

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport-im3D-2.jpg]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport-im-ord.jpg]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport-im-cout.jpg]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport-imC.jpg]] 
 

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-16T14:06:08Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images. 
Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 
 
[[Fichier:transport_opti]] 
 
On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout doit se faire de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 
 
[[Fichier:transport_simp1]] 
 
Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 
 
[[Fichier:transport_simp2]] 
 
Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (ici, le vecteur <math>\vec{u}</math>).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[[Fichier:transport_imA]][[Fichier:transport_imB]] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 
 
[[Fichier:transport_im3D_1]] 
 

==== Mise en ordre des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[[Fichier:transport_im3D_1]] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[[Fichier:transport_im_ord]] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[[Fichier:transport_im_cout]] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[[Fichier:transport_imB]] 
 

== Algorithme en python ==

Transport optimal par coupe 1D et transfert de couleurs entre images

2019-05-15T14:06:46Z

Chardonnet :

Le transport optimal par coupe en une dimension peut être désigné, dans notre cas, par le fait de faire correspondre des listes de valeurs ordonnées selon une droite, pour ensuite les transférer l'une vers l'autre. Ici, les valeurs sont des pixels de couleur, et les listes de valeurs sont des images. 
Ce principe permet de trouver, au mieux, la colorisation d'une image A avec chaque pixels d'une image B. Le résultat peut alors être assimilé à une réorganisation des pixels de l'image B pour qu'il ressemble le plus à l'image A.

== Principe du transfert optimal ==

En théorie, le transport optimal peut se traduire par un déplacement de quantité d'une position à une autre. 
A chaque déplacement est associé un coût, que l'on calcule différement selon les domaines. 
On peut visualiser deux fonctions pour illustrer le propos. 
 
[image légendée] 
 
On part du principe que nous sommes dans un cas discret, que <math>f</math> et <math>g</math> sont de la même air et que leurs abscisses respectives sont nommées <math>x</math> et <math>y</math>. 
Le but du transport optimal est de répartir les quantités des <math>f(x)</math> dans les quantités <math>g(y)</math>. On note alors <math>q(x,y)</math> la quantité <math>q</math> déplacée de <math>x</math> à <math>y</math>. 
On note le coût d'un déplacement <math>c(x,y)</math>. Le coup d'un déplacement suivant une quantité est alors le produit entre la quantité déplacée et le coût du déplacement, soit <math>q(x,y)c(x,y)</math>. 
Le tout se fait de manière optimale, c'est à dire en ayant le coût global le plus bas possible. Coût global que l'on note : 
<math>C=\sum_{i=1}^n q(x_i,y_i)c(x_i,y_i)</math>, avec n le nombre d'effectifs de <math>x</math> ou de <math>y</math>.

=== Calcul du coût ===

Il existe plusieurs manière de calculer un coût, qui sont chacune adéquat au domaine où elles s'appliquent. 
En voici quelques une :
<ul>
<li><math>c(x,y)=|x-y|</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, le coût global est toujours optimal.</li>
<li><math>c(x,y)=|x-y|^2</math> 
Soit la distance au carré entre les deux points <math>x</math> et <math>y</math>. 
Dans ce cas, la sensibilité à la distance parcourue est exponentielle (du fait de la fonction carré).</li>
<li><math>c(x,y)=|x-y|^{1/2}</math> 
Soit la distance entre les deux points <math>x</math> et <math>y</math>.</li>
</ul>

== Transfert de couleurs pas coupe 1D ==

Le coût choisi pour le transfert de couleurs est <math>c(x,y)=|x-y|^2</math>.

=== Simplification du transfert optimal ===

Dans le cadre de deux images de mêmes aires où l'on veut transférer les pixels de l'une à l'autre, la notion de quantité disparaît. 
En effet, on considère chaque pixels comme des points, et non des valeurs. 
 
[image légendée] 
 
Comme il n'y a plus de quantité, seul le coût d'un déplacement importe pour obtenir un coût global optimal. 
Alors, le moyen d'obtenir un coût global optimal est de faire correspondre chaque pixels de même rangs entre les deux images. 
 
[image légendée] 
 
Mais ceci ne fonctionne que si les deux listes de pixels ont été préalablement ordonnées selon un vecteur (ici, le vecteur <math>\vec{u}</math>).

=== Application pour deux images ===

On prend donc deux images A et B de mêmes aires. 
 
[image A] [image B] 
 
==== Représentation des deux images ====

Les deux images peuvent être traduites par deux listes de pixels de même taille (car elles ont toutes deux la même aire). 
Chaque pixel est lui même représenté par trois composantes : bleu, rouge et vert. Chacune de ces composantes prennent des valeurs allant de 0 à 255. 
On peut ainsi représenter graphiquement les images dans un repère en trois dimensions par deux nuages de points. 
 
[image 1] [image 2] 
 

==== Ordonnance des pixels ====

Pour ordonner ces deux nuages de points selon une droite <math>d</math>, on définit son vecteur directeur <math>\vec{u}</math> qui est aussi un vecteur unitaire. 
Le produit scalaire de chaque pixels d'une image avec <math>\vec{u}</math> donne le rang auquel le pixel correspond sur sa liste ordonnée. 
 
[image légendée] 
 
On ordonne donc les deux nuages de points pour obtenir deux listes ordonnée. 
 
[image légendée] 
 

==== Calcul du meilleur coût ====

On peut ensuite calculer le coût global <math>C</math> entre les deux listes ordonnées. 
Pour rappel, <math>C=\sum_{i=1}^n c(x_i,y_i)</math>, avec <math>c(x_i,y_i)=|x_i-y_i|^2</math>.
 
[image légendée] 
 
Sachant que ce coût dépend du vecteur <math>\vec{u}</math> tiré, on a <math>C(\vec{u})</math>. 
Comme le transfert doit être optimal, il faut trouver le vecteur <math>\vec{u}</math> pour lequel <math>C(\vec{u})</math> est minimal. 
La méthode utilisée est donc de tirer au hasard <math>\vec{u}</math> un nombre suffisant de fois pour s'approcher du <math>C(\vec{u})</math> minimal.

==== Transfert final ====

Une fois que l'on a trouvé le coût <math>C</math> le plus bas pour un certains vecteur <math>\vec{u}</math>, il ne reste plus qu'à faire correspondre les pixels de l'image B avec l'emplacement initial des pixels de l'image A auxquels ils sont associé pour former l'image sortante C. 
 
[image C] 
 

== Algorithme en python ==