Comment trouver Waldo avec Mathematica?

Cela m’a déconcerté ce week-end: quelle est la bonne façon de résoudre ces problèmes ? Où est Waldo? [ ‘Wally’ hors Amérique du Nord] puzzles, en utilisant Mathematica (traitement d’images 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  {0, 0, 0}, {r_, g_, b_} /; (r > .7 && g < .3 && b  {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):

Graphique Mathematica

J’ai trouvé Waldo!

Waldo avait été trouvé

Comment je l’ai fait

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 rouges et blanches dans la chemise.

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

J’utilise Binarize pour sélectionner les pixels de l’image avec une corrélation suffisamment élevée et dessiner un cercle blanc autour d’eux pour les accentuer en utilisant la Dilation

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

Je devais 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 originale pour obtenir le résultat ci-dessus

 found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]] 

J’imagine une “façon à toute épreuve de le faire” (pensez à la CIA qui trouve Waldo dans n’importe quelle image satellite à tout moment, pas seulement une 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 que 3-5 suffiront), mais le plus sera le mieux.

Cela assignera des nuages ​​de probabilités à divers éléments présents dans la bonne disposition, puis établira (via la segmentation) la taille moyenne d’un object, fragmentera l’image source en cellules d’objects qui ressemblent le plus à des individus individuels ), mais comme les images de Waldo comprennent généralement BEAUCOUP de personnes à peu près à la même échelle, cela devrait être une tâche très simple, puis nourrir ces segments de la machine Boltzmann pré-formée. Cela vous donnera la probabilité que chacun soit Waldo. Prenez un avec la plus grande probabilité.

C’est ainsi que fonctionnent aujourd’hui les lecteurs OCR, les codes postaux et la reconnaissance de l’écriture manuscrite. Fondamentalement, vous savez que la réponse est là, vous savez plus ou moins à quoi cela devrait ressembler, et tout le rest peut avoir des éléments communs, mais ce n’est certainement pas ça, donc vous ne vous souciez pas du “not it”, vous il suffit de regarder la probabilité “il” parmi tous les “il” que vous avez vu auparavant “(dans les codes postaux par exemple, vous formiez BM pour seulement 1s, juste 2s, juste 3s, etc., puis nourrir chaque numériser sur chaque machine, et en choisir un qui a le plus 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 sur le fait que la bonne manière de résoudre le problème général de trouver Waldo (ou n’importe quel object intéressant) dans une image arbitraire serait de former un classificateur d’apprentissage automatique supervisé. En utilisant de nombreux exemples d’étiquettes positives et négatives, un algorithme tel que Support Vector Machine , Boosted Decision Stump ou Boltzmann Machine pourrait probablement être formé pour obtenir une haute précision sur ce problème. Mathematica inclut même ces algorithmes dans son cadre d’apprentissage automatique .

Les deux défis de l’entraînement d’un classificateur Waldo seraient:

  1. Détermination de la transformation de la caractéristique d’image correcte. C’est là que la réponse de @ Heike serait utile: un filtre rouge et un détecteur de motif dépouillé (par exemple, décomposition en ondelettes ou DCT) seraient un bon moyen de transformer les pixels bruts en un format dont l’algorithme de classification pourrait tirer des enseignements. Une décomposition basée sur des blocs qui évalue toutes les sous-sections de l’image serait également requirejse … mais cela est facilité par le fait que Waldo a) a toujours la même taille et b) toujours présente une seule 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 de boosting (par exemple, la focalisation sur les appareils photo numériques) sont entraînées sur des millions d’exemples positifs et négatifs.

Une recherche rapide d’ images sur Google fournit de bonnes données. Je vais essayer de rassembler des exemples de formation et de les coder dès 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 telle que la Terre de Waldos !

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

Il y a quand même une faille majeure dans le fait de compter sur les rayures seules pour trouver la réponse (je n’ai personnellement aucun problème avec un ajustement manuel). Il y a un exemple (listé par Brett Champion, ici ) présenté qui montre qu’ils parfois, brisent le modèle de chemise. Donc, cela devient un modèle plus complexe.

Je voudrais essayer une approche de l’identifiant de la forme et des couleurs, ainsi que des relations spatiales. Tout comme la reconnaissance faciale, vous pouvez rechercher des motifs géomésortingques à certains ratios. La mise en garde est que généralement une ou plusieurs de ces formes est occultée.

Obtenez une balance des blancs sur l’image et une balance rouge sur l’image. Je crois que Waldo a toujours la même valeur / teinte, mais l’image peut provenir d’un scan ou d’une mauvaise copie. Ensuite, référez-vous toujours à un tableau des couleurs que Waldo est en réalité: 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. Aussi, par rapport aux autres personnes dans l’image, Waldo est du côté maigre.

Donc, trouver des personnes au hasard pour obtenir la taille des personnes dans cette image. Mesurez la hauteur moyenne d’un tas de choses à des points aléatoires de l’image (un contour simple produira plusieurs personnes). Si chaque chose ne se trouve pas dans un écart type, elles sont ignorées pour le moment. 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 (?) Des fois pour vous assurer que les échantillons sont assez proches les uns des autres, en excluant toute moyenne en dehors d’un écart type. Possible dans Mathematica?

Ceci est votre taille Waldo. Walso est maigre, donc vous cherchez quelque chose de 5: 1 ou 6: 1 (ou autre) ht: wd. Cependant, 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 de 0,5: 1 au-dessus du rouge-blanc.
  2. Pantalon bleu. Toute quantité de bleu à la même largeur à 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 toute 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 du rouge-blanc principal.
  5. Cheveux foncés.
  6. Couleur de la chaussure Je ne connais pas la couleur.

Tout cela pourrait s’appliquer. Ce sont aussi des contrôles négatifs contre des personnes similaires sur la photo – par exemple, le n ° 2 annule le port d’un tablier rouge-blanc (trop près des chaussures), le n ° 5 élimine les cheveux clairs. De plus, la forme n’est qu’un indicateur pour chacun de ces tests. . . la couleur seule à la distance spécifiée peut donner de bons résultats.

Cela réduira les zones à traiter.

Stocker ces résultats produira un ensemble de zones dans lesquelles Waldo devrait figurer. Exclure toutes les autres zones (par exemple, pour chaque zone, sélectionnez un cercle deux fois plus grand que la taille moyenne de la personne), puis exécutez le processus que @Heike a défini en supprimant tout sauf le rouge, etc.

Des idées sur la façon de coder cela?


Modifier:

Réflexions sur la façon de coder ceci. . . exclure toutes les zones sauf le rouge Waldo, squelettiser les zones rouges et les réduire en un seul point. Faites de même pour les cheveux brun Waldo, le pantalon Waldo bleu, la couleur des chaussures Waldo. Pour la couleur de peau Waldo, exclure, puis trouver le contour.

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

À partir de là, en utilisant les zones rouges squelettées (et non les zones dilatées), comptez les lignes dans chaque zone. S’il y a le nombre correct (quatre, non?), C’est certainement un domaine possible. Si ce n’est pas le cas, je suppose que je ne fais qu’exclure (comme étant un centre Waldo… Ça peut toujours être son chapeau).

Ensuite, vérifiez s’il y a une forme de visage au-dessus, un sharepoint cheveux au-dessus, le sharepoint pantalon ci-dessous, les points de chaussure ci-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èle disponible dans OpenCV pour trouver Waldo.

Pour ce faire, un modèle est nécessaire. J’ai donc recadré Waldo de l’image originale et l’ai utilisé comme modèle.

entrer la description de l'image ici

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

entrer la description de l'image ici

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

entrer la description de l'image ici