Comment trouver Waldo avec Mathematica?

1542

Cela m'a dérangé pendant le week-end: Quelle est une bonne façon de résoudre ces cas où est Waldo? Casse -tête [ «Wally» en dehors de l'Amérique du Nord], en utilisant Mathematica (traitement d'image et autres fonctionnalités)?

Voici ce que j'ai jusqu'à présent, une fonction qui réduit un peu la complexité visuelle en atténuant certaines des couleurs non rouges:

whereIsWaldo[url_] := Module[{waldo, waldo2, waldoMask},
    waldo = Import[url];
    waldo2 = Image[ImageData[
        waldo] /. {{r_, g_, b_} /;
          Not[r > .7 && g < .3 && b < .3] :> {0, 0,
          0}, {r_, g_, b_} /; (r > .7 && g < .3 && b < .3) :> {1, 1,
          1}}];
    waldoMask = Closing[waldo2, 4];
    ImageCompose[waldo, {waldoMask, .5}]
]

Et un exemple d'URL où cela "fonctionne":

whereIsWaldo["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"]

(Waldo est à la caisse):

Image originale

Graphique Mathematica

Arnoud Buzing
la source
31
@yoda - en haut à gauche, une table avec beaucoup de chaussures, une caisse enregistreuse et Waldo près du coin de la table.
Arnoud Buzing
8
En tant que doctorant en vision par ordinateur, je suis tellement tenté de tenter le coup ... mais je dois résister. Pour ce que ça vaut, j'irais pour Histogramme de dégradés orientés + fenêtre coulissante SVM, comme dans ce travail très influent (avertissement: pdf).
dimatura
54
"Où est Wally ." >. <
Courses de légèreté en orbite
2
Pouvons-nous changer la question pour prendre en charge d'autres langues également? J'ai pensé à le faire avec Matlab
Andrey Rubshtein
2
@ArnoudBuzing: Dans votre question, vous pouvez trouver Waldo en regardant la sélection qui contient le plus de blanc. : /
Tamara Wijsman

Réponses:

1640

J'ai trouvé Waldo!

waldo avait été trouvé

Comment je l'ai fait

Tout d'abord, je filtre toutes les couleurs qui ne sont pas rouges

waldo = Import["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"];
red = Fold[ImageSubtract, #[[1]], Rest[#]] &@ColorSeparate[waldo];

Ensuite, je calcule la corrélation de cette image avec un simple motif noir et blanc pour trouver les transitions rouge et blanc dans la chemise.

corr = ImageCorrelate[red, 
   Image@Join[ConstantArray[1, {2, 4}], ConstantArray[0, {2, 4}]], 
   NormalizedSquaredEuclideanDistance];

J'utilise Binarizepour sélectionner les pixels de l'image avec une corrélation suffisamment élevée et dessiner un cercle blanc autour d'eux pour les souligner en utilisantDilation

pos = Dilation[ColorNegate[Binarize[corr, .12]], DiskMatrix[30]];

J'ai dû jouer un peu avec le niveau. Si le niveau est trop élevé, trop de faux positifs sont détectés.

Enfin, je combine ce résultat avec l'image d'origine pour obtenir le résultat ci-dessus

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]
Heike
la source
52
@MikeBantegui Bien que la solution de Heike soit excellente, je ne serais pas si rapide à l'intégrer dans une WhereIsWaldofonction, car ce n'est pas une solution générale. Heike elle-même a souligné que les niveaux doivent être modifiés avant de pouvoir obtenir un résultat positif. Pour voir ce que je veux dire, essayez votre fonction empaquetée telle quelle sur "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"C'est plus difficile avec celle-ci.
abcd
17
Cette image est plus délicate: Waldo . Je pense cependant que le fait d'avoir quelque chose qui peut mettre en évidence le potentiel de Waldos est toujours utile (pour une définition de `` utile ''). (Cela me rappelle certaines des choses qu'iPhoto identifiera parfois comme un visage dans notre collection de photos ...)
Brett Champion
33
Veuillez consulter ce message Meta: meta.stackexchange.com/questions/116401/…
Bill the Lizard
155
Vous semblez avoir mal compris les règles de Where's Waldo. C'est clairement de la triche.
Stefan Kendall
91
Bien que ce soit un bon hack, cela ne fonctionne tout simplement pas. Il nécessite un réglage manuel et ne fonctionne que sur une seule image. Je ne comprends pas pourquoi cela est voté positivement et même choisi comme réponse. Cela décourage quiconque d'essayer même de répondre avec de meilleures méthodes de travail.
sam hocevar
144

Ma conjecture sur une "manière à toute épreuve de le faire" (pensez que la CIA trouve Waldo dans n'importe quelle image satellite à tout moment, pas seulement une seule image sans éléments concurrents, comme des chemises rayées) ... Je formerais une machine Boltzmann sur de nombreuses images de Waldo - toutes les variantes de lui assis, debout, occlus, etc .; chemise, chapeau, appareil photo et toutes les œuvres. Vous n'avez pas besoin d'un grand corpus de Waldos (peut-être 3 à 5 suffira), mais plus c'est mieux.

Cela attribuera des nuages ​​de probabilités à divers éléments se produisant dans la disposition correcte, puis établira (via la segmentation) ce qu'est une taille d'objet moyenne, fragmentera l'image source en cellules d'objets qui ressemblent le plus à des personnes individuelles (en tenant compte des occlusions possibles et des changements de pose ), mais comme les images Waldo incluent généralement BEAUCOUP de personnes à peu près à la même échelle, cela devrait être une tâche très facile, puis alimenter ces segments de la machine Boltzmann pré-entraînée. Cela vous donnera la probabilité que chacun soit Waldo. Prenez-en un avec la probabilité la plus élevée.

C'est ainsi que fonctionnent aujourd'hui l'OCR, les lecteurs de code postal et la reconnaissance d'écriture sans traits. Fondamentalement, vous savez que la réponse est là, vous savez plus ou moins à quoi elle devrait ressembler, et tout le reste peut avoir des éléments communs, mais c'est définitivement "pas ça", donc vous ne vous embêtez pas avec le "pas ça", vous il suffit de regarder la probabilité de "ça" parmi tous les "c'est" que vous avez déjà vu "(dans les codes postaux par exemple, vous entraîneriez BM pour seulement 1s, juste 2s, juste 3s, etc., puis nourrissez chacun chiffre à chaque machine, et choisissez celui qui a le plus de confiance.) Cela fonctionne beaucoup mieux qu'un seul réseau neuronal d'apprentissage des fonctionnalités de tous les nombres.

Gregory Klopper
la source
13
Les réseaux de neurones ne sont-ils pas suffisants pour cela? En outre, l'article de wikipedia affirme que les machines Boltzmann ne sont pas pratiques.
GClaramunt
2
Sans essayer, je ne suis pas sûr, mais s'il est suffisamment grand et suffisamment complexe, un réseau de neurones devrait être suffisant pour TOUT. Surtout avec les devises. Les machines Boltzmann font TRÈS TRÈS TRÈS bien pour reconnaître un ensemble de données assez simpliste avec une grande quantité de bruit dans une mer de données contrairement à elle-même.
Gregory Klopper
14
Les codes postaux sont lus en permanence avec les machines Boltzmann, et la précision de la livraison du courrier est passée sous silence.
Gregory Klopper
47

Je suis d'accord avec @GregoryKlopper que la bonne façon de résoudre le problème général de trouver Waldo (ou tout autre objet d'intérêt) dans une image arbitraire serait de former un classificateur d'apprentissage automatique supervisé. En utilisant de nombreux exemples étiquetés positifs et négatifs, un algorithme tel que Support Vector Machine , Boosted Decision Stump ou Boltzmann Machine pourrait probablement être formé pour atteindre une grande précision sur ce problème. Mathematica inclut même ces algorithmes dans son Machine Learning Framework .

Les deux défis avec la formation d'un classificateur Waldo seraient:

  1. Déterminer la bonne transformation de la fonction d'image. C'est là que la réponse de @ Heike serait utile: un filtre rouge et un détecteur de motif dépouillé (par exemple, la décomposition en ondelettes ou DCT) seraient un bon moyen de transformer les pixels bruts en un format dont l'algorithme de classification pourrait apprendre. Une décomposition par blocs qui évalue toutes les sous-sections de l'image serait également nécessaire ... mais cela est rendu plus facile par le fait que Waldo est a) toujours à peu près de la même taille et b) toujours présent exactement une fois dans chaque image.
  2. Obtenir suffisamment d'exemples de formation. Les SVM fonctionnent mieux avec au moins 100 exemples de chaque classe. Les applications commerciales du boosting (par exemple, la mise au point du visage dans les appareils photo numériques) sont formées sur des millions d'exemples positifs et négatifs.

Une recherche rapide d' images Google révèle de bonnes données - je vais essayer de collecter des exemples de formation et de les coder maintenant!

Cependant, même une approche d'apprentissage automatique (ou l'approche basée sur des règles suggérée par @iND) aura du mal à obtenir une image comme le Pays de Waldos !

lubar
la source
Un système de vision par ordinateur basé sur l'apprentissage automatique qui tente de résoudre le problème "Où est Waldo" dans le monde réel (c'est-à-dire trouver une personne en particulier sur les photos de foule sur Flickr) a été présenté à la conférence Computer Vision and Pattern Recognition l'an dernier. Ils trichent un peu cependant en ajoutant des informations de localisation 3D en utilisant plusieurs photos de la même scène.
lubar
41

Je ne connais pas Mathematica. . . dommage. Mais j'aime la réponse ci-dessus, pour la plupart.

Il y a toujours un gros défaut à se fier uniquement aux rayures pour glaner la réponse (personnellement, je n'ai pas de problème avec un réglage manuel). Il y a un exemple (répertorié par Brett Champion, ici ) présenté qui montre qu'ils cassent parfois le motif de la chemise. Alors cela devient un modèle plus complexe.

J'essaierais une approche de la forme et des couleurs, ainsi que des relations spatiales. Tout comme la reconnaissance faciale, vous pouvez rechercher des motifs géométriques à certains rapports les uns des autres. La mise en garde est que généralement une ou plusieurs de ces formes sont occluses.

Obtenez une balance des blancs sur l'image et une balance des rouges sur le rouge de l'image. Je crois que Waldo a toujours la même valeur / teinte, mais l'image peut provenir d'une numérisation ou d'une mauvaise copie. Référez-vous ensuite toujours à un tableau des couleurs que Waldo est réellement: rouge, blanc, brun foncé, bleu, pêche, {couleur de la chaussure}.

Il y a un motif de chemise, ainsi que le pantalon, les lunettes, les cheveux, le visage, les chaussures et le chapeau qui définissent Waldo. De plus, par rapport aux autres personnes sur l'image, Waldo est plutôt maigre.

Alors, trouvez des personnes aléatoires pour obtenir la taille des personnes sur cette photo. Mesurez la hauteur moyenne d'un tas de choses à des points aléatoires de l'image (un simple contour produira pas mal de personnes individuelles). Si chaque chose ne se trouve pas dans un écart type les unes par rapport aux autres, elles sont ignorées pour l'instant. Comparez la moyenne des hauteurs à la hauteur de l'image. Si le rapport est trop élevé (par exemple, 1: 2, 1: 4 ou similaire), essayez à nouveau. Exécutez-le 10 (?) Fois pour vous assurer que les échantillons sont tous assez rapprochés, à l'exclusion de toute moyenne qui est en dehors de tout écart-type. Possible en Mathematica?

C'est votre taille Waldo. Walso est maigre, donc vous cherchez quelque chose de 5: 1 ou 6: 1 (ou autre) ht: wd. Mais cela ne suffit pas. Si Waldo est partiellement caché, la hauteur pourrait changer. Donc, vous cherchez un bloc de rouge-blanc ~ 2: 1. Mais il doit y avoir plus d'indicateurs.

  1. Waldo a des lunettes. Recherchez deux cercles 0,5: 1 au-dessus du rouge-blanc.
  2. Pantalon bleu. Toute quantité de bleu à la même largeur sur une distance quelconque entre la fin du rouge-blanc et la distance à ses pieds. Notez qu'il porte sa chemise courte, donc les pieds ne sont pas trop proches.
  3. Le chapeau. Rouge-blanc n'importe quelle distance jusqu'à deux fois le haut de sa tête. Notez qu'il doit avoir les cheveux foncés en dessous, et probablement des lunettes.
  4. Manches longues. rouge-blanc à un certain angle par rapport au rouge-blanc principal.
  5. Cheveux foncés.
  6. Couleur de la chaussure. Je ne connais pas la couleur.

N'importe lequel d'entre eux pourrait s'appliquer. Ce sont également des contrôles négatifs contre des personnes similaires sur la photo - par exemple, le n ° 2 nie le port d'un tablier rouge-blanc (trop près des chaussures), le n ° 5 élimine les cheveux de couleur claire. De plus, la forme n'est qu'un indicateur pour chacun de ces tests. . . la couleur seule dans la distance spécifiée peut donner de bons résultats.

Cela réduira les domaines à traiter.

Le stockage de ces résultats produira un ensemble de zones qui devraient contenir Waldo. Excluez toutes les autres zones (par exemple, pour chaque zone, sélectionnez un cercle deux fois plus grand que la taille moyenne d'une personne), puis exécutez le processus défini par @Heike en supprimant tout sauf le rouge, etc.

Des réflexions sur la façon de coder cela?


Éditer:

Réflexions sur la façon de coder cela. . . exclure toutes les zones, sauf Waldo rouge, squelette les zones rouges et élague-les en un seul point. Faites de même pour les cheveux Waldo marron, le pantalon Waldo bleu, la couleur de chaussure Waldo. Pour la couleur de peau Waldo, excluez, puis trouvez le contour.

Ensuite, excluez les zones non rouges, dilatez (beaucoup) toutes les zones rouges, puis squelettez et élaguez. Cette partie donnera une liste des points centraux Waldo possibles. Ce sera le marqueur pour comparer toutes les autres sections de couleurs Waldo.

À partir d'ici, en utilisant les zones rouges squelettées (pas les zones dilatées), comptez les lignes dans chaque zone. S'il y a le bon nombre (quatre, non?), C'est certainement un domaine possible. Sinon, je suppose que l'exclure (comme étant un centre Waldo ... cela peut toujours être son chapeau).

Vérifiez ensuite s'il y a une forme de visage au-dessus, une pointe de cheveux au-dessus, une pointe de pantalon en dessous, des pointes de chaussures en dessous, etc.

Pas encore de code - toujours en train de lire les documents.

Indiana
la source
8
Vous pouvez peut-être montrer une preuve de concept dans le système / la langue que vous connaissez. Cela vous donnera également une idée de l'endroit où les difficultés pourraient survenir.
Szabolcs
1
Oh, j'apprécie simplement le défi tel qu'il se présente. Cela me donne quelque chose à faire entre les promenades sur la plage et l'habillage pour le dîner.
2012 à
1
Donc. . . pourquoi les downvotes? En quoi est-ce différent de l'autre réponse spéculative ici? Est-ce une suggestion que cette question devrait être prise plus au sérieux? Ou simplement que je devrais paraître plus sérieux dans mon enquête? Mon approche est-elle vraiment fausse?
2012
3
Je ne vous ai pas downvote et je ne pense pas que les downvotes soient appropriés pour des tentatives honnêtes de réponse (à moins qu'elles ne donnent de fausses informations). La raison la plus probable des votes négatifs est que vous ne semblez pas avoir essayé l'approche (à consonance assez compliquée), et trouver une bonne solution nécessiterait probablement une bonne quantité d'expérimentation pratique et d'exclure de nombreuses idées. L'autre réponse spéculative suggère une méthode générale (comme point de départ) qui a été utilisée dans le passé pour des problèmes similaires, et il y a une bonne quantité de littérature à ce sujet. J'essaye juste d'expliquer ce qui s'est passé.
Szabolcs
Merci pour l'explication. Je suppose que je ne me concentre pas sur l'histoire des idées.
2012
2

J'ai une solution rapide pour trouver Waldo en utilisant OpenCV.

J'ai utilisé la fonction de correspondance de modèles disponible dans OpenCV pour trouver Waldo.

Pour ce faire, un modèle est nécessaire. J'ai donc recadré Waldo à partir de l'image d'origine et l'ai utilisé comme modèle.

entrez la description de l'image ici

Ensuite, j'ai appelé la cv2.matchTemplate()fonction avec le coefficient de corrélation normalisé comme méthode utilisée. Il a renvoyé une forte probabilité dans une seule région, comme indiqué en blanc ci-dessous (quelque part dans la région supérieure gauche):

entrez la description de l'image ici

La position de la région probable la plus élevée a été trouvée en utilisant la cv2.minMaxLoc()fonction, que j'ai ensuite utilisée pour dessiner le rectangle pour mettre en évidence Waldo:

entrez la description de l'image ici

Jeru Luke
la source
7
Vous essayez de répondre aux questions de traitement d'image les plus connues de SO? ;) Votre solution est agréable et facile mais a / ne fonctionne que pour cette image spécifique et b / a besoin de l'image exacte de Waldo que vous voulez trouver à l'avance, alors que je pense que la question était de trouver n'importe quel Waldo dans n'importe quelle "Où est l'image Waldo" comme vous joueriez le jeu normal: sans savoir à quoi il ressemble à l'avance. Cette question est très amusante de toute façon
Soltius
@Solitus ha exactement !!! Je l'ai travaillé uniquement pour cette image en particulier. Le travailler pour différentes images serait un défi cependant !!
Jeru Luke