Phuntsok Drak-pa ea4072482e probably the last commit, university project is done

2019-04-29 23:56:47 +02:00

21 KiB

Raw Permalink Blame History

Création d’images par algorithme génétique avec référence

{{{newpage}}}

Avant-propos

Ce document est un rapport de projet dont le sujet est décrit ci-dessous. Si vous souhaitez obtenir le code source sans avoir à recopier celui contenu dans ce fichier PDF, vous pouvez vous rendre sur son dépôt Git situé à l’adresse suivante : https://labs.phundrak.fr/phundrak/genetic-images

Notes sur le code

Le code source de ce projet repose sur trois dépendances :

boost_options
spdlog
opencv

Cependant, seul opencv est une dépendance que l’on peut appeler « cœure » au projet ; en effet, c’est grâce à cette bibliothèque que sont exécutées toutes les opérations de manipulation d’images, allant de la simple ouverture de fichier image à la génération des images telle que décrite ci-dessous. boost_options est utilisé afin de parser les options du programme passées dans le terminal, et spdlog permet de générer une sortie utile pour la version debug du programme, affichant des données utiles pour un développeur travaillant sur le code source (en l’occurrence moi-même). Ces deux dernières dépendances n’ont pas d’impact sur la rapidité du programme. {{{newpage}}}

Sujet

Le sujet de ce projet est la création d’un logiciel pouvant recréer une image fournie grâce à des générations aléatoires et successives de formes aux positions, couleurs et taille aléatoires. À chaque étape, une évaluation de la ressemblance entre l’image générée et l’image de référence est effectuée. Si l’algorithme constate que l’application d’une de ces formes aléatoire à l’image générée améliore cette ressemblance entre cette dernière et l’image de ressemblance, la modification est conservée. Sinon elle est ignorée, et une nouvelle image candidate au remplacement de l’image générée est créée. En d’autres mots, il s’agit d’un équivalent de sélection naturelle au sein des images générées aléatoirement ; seules les meilleures sont retenues et seront la base des images générées aléatoirement ultérieures. Ce processus se répètera autant de fois que l’utilisateur le souhaite.

{{{newpage}}}

Les méthodes utilisées

Plusieurs approches au problème sont possibles, allant de la simple implémentation naïve du problème à des moyen pouvant fortement accélérer la vitesse de génération de l’image ainsi que sa qualité. Deux types de formes aléatoires ont été implémentés : des triangles et des carrés. Les triangles sont pour l’instant restreint dans leur dimensions –en effet, ils tiennent tous dans un carré, leur hauteur et largeur sur les axes x et y étant égales. Il serait toutefois possible d’implémenter une version de ce programme générant une hauteur et une largeur toutes deux indépendantes l’une de l’autre pour une version future du programme. Le choix de la forme se fait via l’utilisation d’une option du programme, -f [--form] prenant pour valeur soit 1, le choix par défaut, activant alors d’utilisation des carrés, ou bien la valeur 2 activant l’utilisation des triangles.

Pour évaluer la ressemblance entre deux image, j’évalue une distance euclidienne entre le vecteur de leurs pixels qui peut se résumer à ceci :

V étant le vecteur de pixels de l’image de référence, W étant le vecteur de pixels de l’image générée, et n la taille de ces deux vecteurs.

Les tests de temps sont réalisés sur un Lenovo Ideapad Y700, disposant d’un processeur Intel® Core™ i7-6700HQ à 2.6GHz et un turbo à 3.5GHz, composé de quatre cœurs supportant chacun deux threads, et l’ordinateur dispose d’un total de de 16Go de RAM. Le programme est compilé avec clang 8.0 et avec les options -Wall -Wextra -Wshadow -Wpedantic -pedantic -O3 -flto.

Voici également ci-dessous la liste des options et arguments possibles concernant l’exécution du logiciel.

  $ ./bin/genetic-image -h
  Allowed options:
    -h [ --help ]           Display this help message
    -i [ --input ] arg      Input image
    -o [ --output ] arg     Image output path (default: "output_" + input path)
    -n [ --iterations ] arg Number of iterations (default: 2000)
    -m [ --method ] arg     Method number to be used (default: 1)
    -f [ --form ] arg       Select shape (1:square, 2:triangle)
    -c [ --cols ] arg       For method 5 only, number of columns the reference
                            image should be divided into. If the value is equal
                            to 0, then it will be assumed there will be as many
                            rows as there are collumns. (default: 0)
    -r [ --rows ] arg       For method 5 only, number of rows the reference image
                            should be divided into. (default: 1)
    -S [ --submethod ] arg  Sub-method that will be used to generate the
                            individual tiles from method 5. (default: 1)
    -s [ --size ]           Enables controlled size of the random shapes
    -v [ --verbose ]        Enables verbosity

Méthode naïve (méthode 1)

J’ai tout d’abord implémenté la méthode naïve afin d’avoir une référence en matière de temps. Cette dernière est implémentée dans src/methods.cc avec la fonction method1(). Comme ce à quoi je m’attendais, cette méthode de génération d’images est très lente, principalement dû au fait que l’algorithme en l’état essaiera d’appliquer des couleurs n’existant pas dans l’image de référence, voire complètement à l’opposées de la palette de couleurs de l’image de référence.

Voici les options de la commande utilisée ici :

  -i img/mahakala-monochrome.jpg -n2000 -m1 -f1 # carrés
  -i img/mahakala-monochrome.jpg -n2000 -m1 -f2 # triangles

Voici les moyennes de temps d’exécution de cette méthode pour 2.000 améliorations :

carrés	triangles
10m 40s 615ms	4m 57s 987ms

On constate une plus grande rapidité d’exécution lors de l’utilisation de carrés. Je suppose que cela est dû à une facilité avec les triangles à créer des traits et bordures inclinées pour lesquelles plusieurs carrés seraient nécessaires, ainsi qu’une meilleure flexibilité quant aux formes pouvant être créées.

Vous trouverez en Annexes un exemple d’image générée à partir de img/mahakala-monochrome.png avec 2000 améliorations via cette méthode.

Réduction du panel des couleurs (méthode 2)

Constatant que la majorité des échecs d’ajout de formes de couleur par la première méthode échouent dû à une couleur incorrecte, voire n’appartenant pas à l’image de référence, j’ai décidé de restreindre les possibilités de couleurs parmis lesquelles le hasard peut choisir à la liste des couleurs présentes dans l’image de référence uniquement. Ce choix se fait donc via l’implémentation d’un set de valeurs uniques représentant les couleurs trouvées dans l’image de référence, leur détection étant réalisée avec des threads parallèles pour plus de rapidité à l’exécution. Cette méthode est celle implémentée dans la fonction method2() dans src/methods.cc.

Voici les options de la commande utilisée ici :

  -i img/mahakala-monochrome.jpg -n2000 -m2 -f1 # carrés
  -i img/mahakala-monochrome.jpg -n2000 -m2 -f2 # triangles

Voici le temps moyen d’exécution pour cette méthode avec 2.000 améliorations :

carrés	triangles
7m 23s 774ms	2m 57s 152ms

On peut remarquer une amélioration quant à la rapidité d’exécution du logiciel. Cependant, le résultat n’est pas aussi important qu’escompté. Je suppose que cela est dû au fait que l’algorithme précédent peut considérer un rapprochement d’une zone déjà colorée vers la couleur d’origine comme une amélioration, avec une possibilité plus large sur ce plan-là que pour le second algorithme qui se doit d’être plus précis concernant les couleurs. Une nette amélioration du résultat est toutefois visibles (voir Annexes pour une image générée à partir de img/mahakala-monochrome.png via la méthode 2 et avec 2000 améliorations).

À nouveau, on constate également un meilleur temps avec les triangles qu’avec les carrés.

Étant donné que cette modification ne sera à priori pas en conflit avec d’autres méthodes, cette amélioration sera conservée pour toutes les autres avancées suivantes.

Une taille des formes aléatoire mais contrôlée (méthode 3)

Une autre méthode peut être de contrôler la taille des éléments en spécifiant une taille minimale et maximale selon le nombre d’éléments posés et le nombre total d’éléments à poser. Ainsi, on pourrait privilégier tout d’abord de grandes formes en début de génération pour encourager petit à petit les formes à réduire en taille. Cela permettrait d’obtenir rapidement une représentation grossière de l’image pour ensuite pouvoir progressivement afiner les détails. La taille de la forme à appliquer est définie comme suit :

Cette version du logiciel est nettement plus lente que ses versions précédentes du fait de la contrainte de taille pour les formes pouvant potentiellement améliorer l’image, et cela à un tel point que pour 2.000 améliorations, le programme tourne durant plus d’une heure. De plus, la qualité de l’image ainsi générée n’est pas nécessairement meilleure, ainsi cette méthode n’est pas nécessairement bonne. Toujours est-il que j’ai laissé pour les méthodes suivantes une option pour l’utilisateur lui permettant d’activer le contrôle de la taille des éléments s’il le souhaite via l’option -s [--size]. Toutefois, les temps d’exécution des méthodes suivantes n’en tiendront pas compte.

Concurrence entre threads (méthode 4)

Une utilisation de calculs parallèles pourrait être intéressante afin d’accélerer la génération des images : l’utilisation de threads mis en concurrence. À chaque tentative d’amélioration de l’image, plusieurs threads sont lancés, et chacun créera sa propre amélioration possible de l’image. Ces résultats sont récupérés et évalués, et parmi les résultats améliorant l’image générée, celle avec le meilleur score est conservée. Cela permet ainsi de multiplier les chances d’avoir une amélioration de l’image par tentative.

Voici les options de la commande utilisée ici :

  -i img/mahakala-monochrome.jpg -n2000 -m4 -f1 # carrés
  -i img/mahakala-monochrome.jpg -n2000 -m4 -f2 # triangles

Voici les moyennes de temps d’exécution de cette méthode pour 2.000 améliorations sans contrôle de la taille des éléments générés :

carrés	triangles
2m 30s 636ms	58s 885ms

Nous avons cette fois-ci une très nette amélioration de la vitesse d’exécution de l’algorithme, ce dernier étant jusqu’à environ trois fois plus rapide que la seconde méthode. Il s’agit d’une claire amélioration de la seconde méthode, qui elle-même présentait une amélioration de rapidité et de qualité d’image par rapport à la première méthode. En revanche, il n’y a pas de différence de qualité d’image visible au bout de ces 2.000 améliorations de visible à l’œil nu entre les deuxième et quatrième méthodes.

Collaboration entre threads (méthode 5)

Une différente approche au parallélisme peut être réalisée : plutôt que d’essayer de mettre en concurrence plusieurs threads, il serait possible d’essayer de plutôt les mettre en collaboration. Cela implique par exemple de diviser l’image d’entrée en plusieurs zones sur laquelle chacun des threads lancés travailleraient, appliquant chacun le nombre d’améliorations demandé sur sa zone dédiée. Puis, une fois que chacun des threads a terminé son travail, les différentes zones sont unifiées en une seule image. Plusieurs choix s’offrent alors à nous une fois les différents threads lancés concernant leur méthode de génération d’image, il est possible d’utiliser chacune des méthodes précédentes. Ce choix se fera via une option supplémentaire --sub-method ou -S.

J’ai choisi d’utiliser les deux méthodes les plus efficaces comme sous-méthodes, la deuxième et la quatrième. J’ai choisi la deuxième car il s’agit actuellement de la méthode la plus efficace qui ne soit pas parallélisée, et je pense que cela pourrait peut-être présenter un avantage par rapport à la quatrième méthode qui risque de se retrouvée ralentie par un trop grand nombre de threads lancés en même temps ; une image découpée en deux lignes et cinq colonnes, comme cela va être le cas ci-dessous, lancera sur le processeur de tests au maximum 2×4×8 threads en même temps, soit 16 threads simultanés potentiels, deux fois plus donc qu’avec la méthode 2 en sous-méthode, qui ne tournera que sur huit threads.

Voici les options de la commande utilisée ici :

  -i img/mahakala-monochrome.jpg -n2000 -m5 -c2 -r4 -S4 -f1 # carrés
  -i img/mahakala-monochrome.jpg -n2000 -m5 -c2 -r4 -S4 -f2 # triangles

Voici les temps moyens d’exécution pour la cinquième méthode, utilisant en sous-méthode la seconde présentée :

carrés	triangles
6m 26s 520ms	2m 6s 865ms

Et voici les temps moyens d’exécution pour la même méthode utilisant la quatrième méthode comme sous-méthode :

carrés	triangles
4m 26s 78ms	1m 6s 984ms

Bien que les deux méthodes n’aient pas nécessairement bénéficiées d’amélioration quant à leur temps d’exécution, les images générées via cette cinquième méthode sont d’une qualité nettement supérieure aux images générées jusqu’à présent, avec un niveau de détail largement meilleur. La quatrième méthode utilisée en sous-méthode présente un avantage sur la seconde en considérant le temps d’exécution, et il semblerait que l’on puisse remarquer une légère amélioration de l’image également. Cependant, et bien que cela soit plus lent, la génération à base de carrés présente cette fois-ci un avantage par rapport à la génération à base de triangles : ces derniers cachent beaucoup plus aisément la séparation entre les différentes zones de génération de l’image que les triangles, sans doutes dû à la difficulté d’obtenir des zones de remplissages dont un des côtés soit parfaitement vertical ou horizontal avec ces derniers.

J’ai également remarqué que si l’on utilise un grand nombre de colonnes et de lignes, le programme peut mettre énormément de temps pour effectuer sa tâche. Avec l’image de test, j’ai exécuté le logiciel en divisant l’image de test en cinq colonnes et lignes, donnant un total de vingt-cinq threads exécutant chacun une méthode sur une zone de l’image ; j’ai dû manuellement arrêter le programme au bout de plus d’une heure de travail afin de ne pas perdre de temps. Je pense que cela est dû à certaines zones étant très homogènes, rendant le travail d’amélioration de cette zone très difficile quand la majorité de la zone est à peu près identique à sa version originale, chaque amélioration ne pouvant s’effectuer que sur quelques pixels tout au plus.

{{{newpage}}}

Conclusion

Plusieurs approches ont été abordées lors de ce projet quand à la meilleure méthode de génération d’images basée sur des formes aléatoires, aux couleurs aléatoires. Quelques unes d’entre elles portent sur un certain contrôle du facteur aléatoire, tandis que d’autres tentent de tirer profit du matériel utilisé afin de disposer d’une plus grande puissance de calcul. Alors que l’on a constaté qu’une limitation de l’arbitraire quant au panel de couleurs possibles est intéressante, celle de leur taille l’est moins, tout du moins avec la formule utilisée. Il serait néamoins intéressant de réitérer cette tentative avec une autre approche, comme par exemple réduire la taille maximale des éléments suite à un certain nombre d’échecs de génération de successeurs successifs.

En revanche, les méthodes consistant à répartir la charge de travail sur plusieurs threads ont été chacune couronnées de succès, et ultimement la combination d’une méthode se basant sur la concurrence entre threads elle-même lancée en collaboration avec d’autres de cette même méthode s’est prouvée être l’une des méthodes les plus efficaces afin de re-créer avec fidélité une image de référence.

Note intéressante : la génération d’image avec des triangles est plus rapide qu’une génération d’image basée sur des carrés, mais ces derniers seront la forme la plus efficace visuellement lors de cette cinquième et meilleure méthode présentée dans ce rapport.

{{{newpage}}}