Comment trouver Waldo avec Mathematica?

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):

J'ai trouvé Waldo!

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]]

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.

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 !

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.

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.

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):

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: