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

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche

Le but de ce projet est une amélioration de la version proposée par [Lucas Chardonnet] en ajoutant des fonctionnalités. La plus importante étant la bibliothèque [Numpy] afin d'accélérer la vitesse d'exécution du programme.
Afin de comprendre correctement cette page, je vous invite tout d'abord à vous rendre sur la page de la première version de ce sujet ([ici]) pour bien comprendre le fonctionnement du programme et son but.

Quelles étaient les limites de l'ancien programme

Le programme précédant fonctionnait très bien et donnait de bons rendus. Néanmoins il mettait un temps relativement long pour effectuer les calculs, ce qui devenait problématique si on voulait faire un transfert de couleurs entre 2 images avec un grand nombre de pixels.

Quelques statistiques sur les temps de calcul

Taille de l'image
(en pixel)
720x576 1280x720 1920x1080 3840x2160
Temps d’exécution du programme ~48sec ~2min25 ~5min30 ~20min25

A noter que ces tests ont été réalisés avec un nombre de répétition de 20 dans le programme.
Ce nombre est une valeur de référence suffisante pour avoir assez de tests pour trouver un bon vecteur pour le transfert de couleur.

On remarque par ces chiffres que lorsque l'on transfert des images de petite résolution, le temps de transfert reste tout à fait correct.
Néanmoins dès que l'on va vouloir prendre des images de résolution plus importante (HD ou même 4K), le temps d'exécution devient bien plus important.

En effet l'ancien programme comporte bon nombre de boucle for , la machine doit donc faire quelques centaines de milliers de boucle. Cela semble très simple pour nos processeurs qui sont capables de faire un milliard de calculs par seconde mais Python est un langage interprété, ce qui rajoute un temps de calcul non négligeable (comme on peut le voir par les valeurs dans le tableau).

Nouvelle version avec numpy

Pourquoi numpy

Dans ce programme, nous utilisons de nombreux tableaux afin de stocker toutes les variables dont nous avons besoin, et la bibliothèque Numpy possède des tableaux bien plus compacts. De plus, l'avantage majeur est que l'on peut appliquer des calculs directement sur l'ensemble du tableau au lieu de faire une boucle pour appliquer ces calculs sur chaque variable.
De ce fait, on gagne énormément de temps de calcul en évitant de nombreuses boucles.
Cette bibliothèque est très complète et si vous voulez plus d'informations je vous conseille de vous rendre sur la page officielle [Numpy]

Comparaison première version avec la version numpy

Taille de l'image
(en pixel)
720x576 1280x720 1920x1080 3840x2160
Temps d’exécution du programme ~48sec ~2min25 ~5min30 ~20min25
Temps d’exécution avec numpy ~6sec ~13sec ~30sec ~2min

Ces tests ont eux aussi été réalisés avec un nombre de répétition de 20 dans le programme
On voit ainsi que l'utilisation de Numpy permet de rendre le programme environ 10 fois plus rapide. Ainsi on peut donc penser maintenant à augmenter le nombre de répétition pour avoir un meilleur résultat en gardant un temps d’exécution correct.

Temps d’exécution du programme
Taille de l'image / Nombres de tours dans le programme -> 20 40 50 75 100
720x576 6sec 10sec 13sec 18sec 24sec
1280x720 13sec 25sec 30sec 48sec 1min
1920x1080 30sec 54sec 1min10 1min40 2min
3840x2160 2min 3min50 5min 7min15 9min30

Plus on augmente la taille de l'image et le nombre de tour, plus le temps d'exécution devient important. En effet, les tailles deviennent exponentielles avec l'augmentation de la qualité ce qui demande énormément de pixels à traiter.
On pourrait ainsi imaginer, pour les images de haute qualité, de regrouper plusieurs pixels en 'paquets' et les traiter ainsi.
Cela permettrait d'avoir moins de pixels à traiter sans pour autant avoir un énorme impact sur la qualité de l'image, on ne devrait pas voir une grande différence à l’œil nu.

Changement d'espace chromatique

Maintenant que l’algorithme fonctionne plus vite, on peut penser à modifier l'espace de couleurs afin d'obtenir un meilleur rendu.

L'espace chromatique L*a*b CIE 1976

En effet, l'espace RVB est très bien mais il correspond aux écrans et non à l’œil humain, tandis que l'espace [L*a*b CIE 1976] a pour but de mieux approximer la réalité. Cet espace, autrement appelé : CIELAB est un espace reposant sur 3 composantes : la clarté L* et l'écart de la couleur par rapport à celle d'une surface grise de même clarté pour a* et b*.

Calcul nécessaire

Passage RVB -> Lab

Afin de passer dans l'espace CIELAB nous devons d'abord passer dans l'espace [CIE XYZ] car il est défini par ce dernier.

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \begin{pmatrix} X \\ Y \\ Z \\ \end{pmatrix} = \begin{pmatrix} 0.618 & 0.177 & 0.205 \\ 0.299 & 0.587 & 0.205 \\ 0 & 0.056 & 0.944 \\ \end{pmatrix} \begin{pmatrix} R \\ V \\ B \\ \end{pmatrix} }

On passe ensuite de l'espace XYZ à l'espace CIELAB grâce aux formules suivantes :

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \begin{align} L^* &= 116 f(Y/Y_n) - 16\\ a^* &= 500 \left[f(X/X_n) - f(Y/Y_n)\right]\\ b^* &= 200 \left[f(Y/Y_n) - f(Z/Z_n)\right] \end{align}} Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \qquad \mathrm o \mathrm \grave{u}~f(t) = \begin{cases} t^{1/3} & \mbox{si } t > (\frac{6}{29})^3 \\ \frac13 \left( \frac{29}{6} \right)^2 t + \frac{4}{29} & \mbox{sinon} \end{cases}}

Ici Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle X_n} , Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y_n} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Z_n} sont les composantes du blanc de référence, ce sont des constantes valant 255, on les obtient avec RVB =(255,255,255).

On récupère ainsi les valeurs de chaque composante de l'espace CIELAB et on peut ensuite calculer l'écart de couleur de la même manière que dans l'espace RVB.

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \Delta E = \sqrt{(\Delta L^*)^2 + (\Delta a^*)^2 + (\Delta b^*)^2 }}

Passage Lab -> RVB

De la même manière on doit d'abord repasser dans l'espace XYZ avant de revenir dans l'espace RGB

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Y = Y_n \cdot f^{-1}\left(\frac{L^*+16}{116}\right)} Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \qquad \mathrm o \mathrm \grave{u}~f^{-1}(t) = \begin{cases} t^3 & \mbox{si } t > \tfrac{6}{29} \\ 3\left(\tfrac{6}{29}\right)^2\left(t - \tfrac{4}{29}\right) & \mbox{sinon} \end{cases}}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle X = X_n \cdot f^{-1}\left(\frac{L^*+16}{116} + \frac{a^*}{500}\right)}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle Z = Z_n \cdot f^{-1}\left(\frac{L^*+16}{116} - \frac{b^*}{200}\right)}


On repasse ensuite dans l'espace RVB avec de nouveau une matrice de passage

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \begin{pmatrix} R \\ V \\ B \\ \end{pmatrix} = \begin{pmatrix} 1.876 & -0.533 & -0.343 \\ -0.967 & 1.998 & -0.031 \\ 0.057 & -0.118 & 1.061 \\ \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ \end{pmatrix} }

Rendu des images

Les images dans l'espace CIELAB nous permettent d'avoir dans certains cas un meilleur rendu.
Prenons l'exemple de ces 2 images
Grand canyon.jpg Degrade vert.jpg

Regardons maintenant le résultat avec les 2 programmes :

Rendu avec le programme classique Rendu avec l'espace CIELAB
Canyon vert numpy.jpg Canyon vert Lab.jpg

On peut voir que dans la version avec l'espace CIELAB, les couleurs sont plus harmonieuses, et restent dans la même intensité de couleurs.
Néanmoins, on peut voir qu'on à plus de mal a distinguer le relief sur la seconde image.

Temps d’exécution

On peut comparer la vitesse du nouveau programme avec celui réalisé avec numpy

Taille de l'image
(en pixel)
720x576 1280x720 1920x1080 3840x2160
Temps d’exécution du programme dans l'espace RGB ~6sec ~13sec ~30sec ~2min
Temps d’exécution du programme dans l'espace CIELAB ~37sec ~1min20 ~3min ~12min30

On remarque que le temps d’exécution du programme dans l'espace CIELAB est plus long.
La différence se fait durant les calculs pour les changements d'espace; le programme doit en effet faire des étapes supplémentaires sur tous les pixels au début et à la fin.

Code

J'ai mis mes 2 programmes sur GitHub ici
Pour utiliser le programme il faut lancer la fonction suivante : main_numpy("image1.jpg","image2.jpg","image3.jpg")
A noter que les 2 premiers paramètres ne sont pas obligatoirement au même format mais doivent tout deux être des images.
Penser à bien indiquer le format de l'image 3 dans la fonction.

Sources

Numpy
Fonction numpy
Espace CIELAB