Algorithmes pour créer des mosaïques d'images - existe-t-il un moyen plus rapide que cela?

9

J'ai joué avec des mosaïques d'images. Mon script prend un grand nombre d'images, les réduit à la taille des vignettes, puis les utilise comme tuiles pour approximer une image cible.

L'approche est en fait assez agréable:

Je calcule l'erreur quadratique moyenne pour chaque pouce dans chaque position de tuile.

Au début, je viens d'utiliser un placement gourmand: mettre le pouce avec le moins d'erreur sur la tuile qui lui convient le mieux, puis la suivante et ainsi de suite.

Le problème avec les gourmands est qu'il vous laisse finalement placer les pouces les plus différents sur les tuiles les moins populaires, qu'elles correspondent étroitement ou non. Je montre des exemples ici: http://williamedwardscoder.tumblr.com/post/84505278488/making-image-mosaics

Je fais donc des échanges aléatoires jusqu'à ce que le script soit interrompu. Les résultats sont tout à fait corrects.

Un échange aléatoire de deux tuiles n'est pas toujours une amélioration, mais parfois une rotation de trois tuiles ou plus entraîne une amélioration globale, c'est A <-> B-à- dire peut ne pas s'améliorer, mais A -> B -> C -> A1peut ..

Pour cette raison, après avoir choisi deux tuiles aléatoires et découvert qu'elles ne s'améliorent pas, je choisis un tas de tuiles pour évaluer si elles peuvent être la troisième tuile dans une telle rotation. Je n'explore pas si n'importe quel ensemble de quatre tuiles peut être tourné de manière rentable, et ainsi de suite; ce serait très cher très bientôt.

Mais cela prend du temps .. Beaucoup de temps!

Existe-t-il une approche meilleure et plus rapide?


Mise à jour Bounty

J'ai testé différentes implémentations et liaisons Python de la méthode hongroise .

De loin le plus rapide était le https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py pur-Python

Mon intuition est que cela se rapproche de la réponse optimale; lorsqu'il est exécuté sur une image de test, toutes les autres bibliothèques sont d'accord sur le résultat, mais ce kuhnMunkres.py, tout en étant plus rapide de plusieurs ordres de grandeur, n'est devenu très très très proche du score que les autres implémentations convenues.

La vitesse est très dépendante des données; Mona Lisa s'est précipitée à travers kuhnMunkres.py en 13 minutes, mais la Perruche à poitrine écarlate a pris 16 minutes.

Les résultats étaient sensiblement les mêmes que les échanges et rotations aléatoires pour la perruche:

entrez la description de l'image icientrez la description de l'image ici

(kuhnMunkres.py à gauche, swaps aléatoires à droite; image originale pour comparaison )

Cependant, pour l'image de la Joconde avec laquelle j'ai testé, les résultats ont été sensiblement améliorés et elle avait en fait son «sourire» défini qui brillait:

entrez la description de l'image icientrez la description de l'image ici

(kuhnMunkres.py à gauche, swaps aléatoires à droite)

Volonté
la source
1
Lié ... ish. Sur Codegolf, la transformation du palais a eu des problèmes similaires.
1
Et un autre ensemble d'images connexes est allRGB où chaque image (bien que cela ne vous donne pas trop de conseils sur la façon de le faire ... juste qu'il y a un autre domaine où ce problème a été abordé).
1
J'ai rencontré ce problème avec un fabricant de mosaïque il y a quelques années. Mon raisonnement d'alors et maintenant est que le problème n'est pas tellement avec votre algorithme (la partie MSE) mais plutôt avec la taille limitée de votre palette d'images d'entrée. N'ayant pas un milliard d'images avec lesquelles travailler, je l'ai truqué en permettant à une image d'être réutilisée après un certain temps. Cependant, si vous voulez continuer avec votre approche, il peut être bon de faire une première passe pour les «bons» ajustements, puis de traiter le reste des images comme aléatoires (ou aléatoires) - avec un jeu d'entrée limité, vous n'avez que tant de choix.
J Trana
@MichaelT merci pour cet excellent lien :) Le codegolf est particulièrement fascinant. Je trouve que les meilleures solutions votées utilisent des swaps aléatoires (pas des rotations aléatoires) et fonctionnent probablement pendant un bon moment ...
Will
1
J'y arrive après avoir sélectionné une réponse et attribué une prime. Une approche différente serait de traiter cela comme un problème de recuit simulé . Vous pouvez utiliser SA comme l'une des étapes de votre pipeline de solutions.
andy256

Réponses:

3

Oui, il existe deux approches meilleures et plus rapides.

  • Problème plus simple: pour chaque tuile, choisissez le meilleur pouce (avec duplication possible). D'accord, c'est de la triche, mais cela ne peut que conduire à un meilleur résultat visuel.
  • Votre point de vue est algorithmiquement plus intéressant et se résume à un «problème d'affectation linéaire», en supposant que vous prenez MSE comme coûts de correspondance dont la somme doit être minimale. Un tel problème peut être résolu en temps polynomial, par exemple par la "méthode hongroise"

Ensuite, vous pouvez ajuster vos coûts en remplaçant MSE par une distance plus précise visuellement, sans changer l'algorithme sous-jacent.

YvesgereY
la source
THX! Le LAP et la méthode hongroise étaient les pistes dont j'avais besoin! Mettre à jour avec les résultats en question.
Will
3

Je suis raisonnablement sûr que c'est un problème NP-difficile. Pour trouver une solution «parfaite», vous devez essayer toutes les possibilités de manière exhaustive, et c'est exponentiel.

Une approche consisterait à utiliser l'ajustement gourmand, puis à essayer de l'améliorer. Cela pourrait être en prenant une image mal placée (l'une des dernières) et en trouvant un autre endroit pour la mettre, puis en prenant cette image et en la déplaçant et ainsi de suite. Vous avez terminé lorsque vous (a) manquez de temps (b) l'ajustement est «assez bon».

Si vous introduisez un élément probabiliste, il pourrait céder le pas à une approche de recuit simulé ou à un algorithme génétique. Peut-être que tout ce que vous essayez de réaliser est de répartir uniformément les erreurs. Je soupçonne que cela se rapproche de ce que vous faites déjà, alors la réponse est: avec le bon algorithme, vous pouvez obtenir un meilleur résultat plus rapidement, mais il n'y a pas de raccourci magique vers Nirvana.


Oui, c'est similaire à ce que vous faites déjà. Il s'agit d'oublier une réponse magique et de penser en termes de 2 algorithmes: d'abord remplir, puis optimiser.

Le remplissage peut être: aléatoire, meilleur disponible, premier meilleur, assez bon, une sorte de point chaud.

L'optimisation peut être aléatoire, corriger le pire ou (comme je l'ai suggéré) recuit simulé ou algorithme génétique.

Vous avez besoin d'une métrique de «bonté» et d'un temps que vous êtes prêt à y consacrer et à simplement expérimenter. Ou trouvez quelqu'un qui l'a fait.

david.pfx
la source
Vous décrivez exactement l'approche décrite dans la question ...?
Will
1

Si les dernières tuiles sont votre problème, vous devriez essayer de les placer tôt, d'une manière ou d'une autre;)

Une approche consisterait à regarder la tuile la plus éloignée du x% supérieur de ses correspondances (intuitivement, j'irais avec 33%) et de la placer sur sa meilleure correspondance. C'est le meilleur match qu'il puisse obtenir de toute façon.

De plus, vous pouvez choisir de ne pas utiliser la meilleure correspondance pour la pire tuile, mais celle où elle introduit le moins d'erreur par rapport à la meilleure correspondance pour cet emplacement, afin de ne pas jeter complètement vos meilleures correspondances pour le plaisir de " limiter les dégâts".

Une autre chose à garder à l'esprit est qu'en fin de compte, vous produisez une image à traiter par un œil. Donc, ce que vous voulez vraiment, c'est utiliser une détection de bord pour déterminer quelles positions sur votre image sont les plus importantes. De même, ce qui se passe à la périphérie même de l'image a peu de valeur pour la qualité de l'effet. Superposez ces deux poids et incluez-les dans votre calcul de distance. Toute gigue que vous obtenez devrait donc graviter vers la frontière et loin des bords, dérangeant ainsi beaucoup moins.

De plus, avec la détection des bords en place, vous voudrez peut-être placer le premier y% avec avidité (peut-être jusqu'à ce que vous tombiez en dessous d'un certain seuil de "nervosité" dans les carreaux à gauche), afin que les "points chauds" soient traités très bien, puis passez au "contrôle des dommages" pour le reste.

back2dos
la source