Come trovo Waldo con Mathematica?

Questo mi ha infastidito durante il fine settimana: qual è un buon modo per risolvere chi è Waldo? [ ‘Wally’ al di fuori del Nord America] puzzle, usando Mathematica (elaborazione delle immagini e altre funzionalità)?

Ecco cosa ho finora, una funzione che riduce un po ‘la complessità visiva attenuando alcuni dei colors non rossi:

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

E un esempio di URL dove questo “funziona”:

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

(Waldo è presso il registratore di cassa):

Mathematica grafica

Ho trovato Waldo!

il waldo era stato trovato

Come l’ho fatto

Innanzitutto, sto filtrando tutti i colors che non sono rossi

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

Successivamente, sto calcolando la correlazione di questa immagine con un semplice schema in bianco e nero per trovare le transizioni rosse e bianche nella maglietta.

 corr = ImageCorrelate[red, [email protected][ConstantArray[1, {2, 4}], ConstantArray[0, {2, 4}]], NormalizedSquaredEuclideanDistance]; 

Uso Binarize per selezionare i pixel nell’immagine con una correlazione sufficientemente alta e disegnare un cerchio bianco attorno a loro per enfatizzarli usando la Dilation

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

Ho dovuto giocare un po ‘con il livello. Se il livello è troppo alto, vengono troppi i falsi positivi.

Finalmente sto combinando questo risultato con l’immagine originale per ottenere il risultato sopra

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

La mia ipotesi su un “modo a prova di proiettile per farlo” (pensa che la CIA trovi Waldo in qualsiasi immagine satellitare in qualsiasi momento, non solo una singola immagine senza elementi in competizione, come le magliette a righe) … Vorrei addestrare una macchina Boltzmann su molte immagini di Waldo – tutte le variazioni di lui seduto, in piedi, occluso, ecc .; camicia, cappello, macchina fotografica e tutte le opere. Non hai bisogno di un grande corpus di Waldos (forse 3-5 sarà sufficiente), ma più sono e meglio è.

Questo assegnerà nubi di probabilità a vari elementi che si verificano in qualunque sia la disposizione corretta, e quindi stabilirà (tramite segmentazione) qual è la dimensione media di un object, frammenta l’immagine sorgente in celle di oggetti che assomigliano di più a singole persone (considerando possibili occlusioni e cambiamenti di posa ), ma poiché le immagini di Waldo di solito includono un sacco di persone alla stessa scala, questo dovrebbe essere un compito molto semplice, quindi alimentare questi segmenti della macchina Boltzmann pre-addestrata. Ti darà la probabilità che ognuno sia Waldo. Prendi uno con la più alta probabilità.

Questo è il modo in cui oggi OCR, lettori di codici ZIP e riconoscimento della grafia senza tracce funzionano. Fondamentalmente sai che la risposta è lì, sai più o meno come dovrebbe essere, e tutto il resto può avere elementi comuni, ma è sicuramente “non è così”, quindi non ti preoccupare del “non è così”, tu guarda la probabilità di “esso” tra tutti i possibili “è quello che hai visto prima” (nei codici postali, ad esempio, devi allenare BM per solo 1, solo 2, solo 3, ecc. digitare su ciascuna macchina e sceglierne una che abbia maggior confidenza). Funziona molto meglio di una singola funzionalità di apprendimento della rete neurale di tutti i numeri.

Sono d’accordo con @GregoryKlopper che il modo giusto per risolvere il problema generale di trovare Waldo (o qualsiasi object di interesse) in un’immagine arbitraria sarebbe quello di addestrare un classificatore supervisionato di apprendimento automatico. Usando molti esempi con etichette positive e negative, un algoritmo come Support Vector Machine , Boosted Decision Stump o Boltzmann Machine potrebbe probabilmente essere addestrato per ottenere un’elevata precisione su questo problema. Mathematica include anche questi algoritmi nel suo Machine Learning Framework .

Le due sfide con la formazione di un classificatore Waldo sarebbero:

  1. Determinazione della trasformazione della caratteristica dell’immagine giusta. È qui che la risposta di @ Heike sarebbe utile: un filtro rosso e un rilevatore di pattern spogliato (ad esempio, la decomposizione wavelet o DCT) sarebbe un buon modo per trasformare i pixel grezzi in un formato da cui l’algoritmo di classificazione potrebbe imparare. Sarebbe anche necessaria una scomposizione basata su blocchi che valuti tutte le sottosezioni dell’immagine … ma ciò è reso più facile dal fatto che Waldo è a) sempre più o meno della stessa dimensione eb) sempre presente esattamente una volta in ogni immagine.
  2. Ottenere sufficienti esempi di formazione. Gli SVM funzionano meglio con almeno 100 esempi di ogni class. Le applicazioni commerciali di potenziamento (ad esempio, l’attenzione al volto nelle fotocamere digitali) sono addestrate su milioni di esempi positivi e negativi.

Una rapida ricerca di immagini di Google rivela alcuni dati validi: ho intenzione di raccogliere alcuni esempi di addestramento e di codificarlo subito!

Tuttavia, anche un approccio di machine learning (o l’approccio basato su regole suggerito da @iND) avrà problemi per un’immagine come Land of Waldos !

Non conosco Mathematica. . . peccato. Ma mi piace la risposta sopra, per la maggior parte.

C’è ancora un grande difetto nel basarsi solo sulle strisce per raccogliere la risposta (personalmente non ho problemi con una regolazione manuale). C’è un esempio (elencato da Brett Champion, qui ) presentato che mostra che, a volte, rompono il modello di camicia. Quindi diventa uno schema più complesso.

Vorrei provare un approccio di forma id e colors, insieme a relazioni spaziali. Molto simile al riconoscimento facciale, puoi cercare motivi geometrici a determinati rapporti l’uno dall’altro. L’avvertenza è che di solito una o più di queste forms è occlusa.

Ottenere un bilanciamento del bianco sull’immagine e redare un bilanciamento del rosso dall’immagine. Credo che Waldo abbia sempre lo stesso valore / tonalità, ma l’immagine potrebbe provenire da una scansione o da una ctriggers copia. Quindi fai sempre riferimento ad una matrice di colors che Waldo è in realtà: rosso, bianco, marrone scuro, blu, pesca, {colore scarpa}.

C’è un modello di camicia, e anche i pantaloni, gli occhiali, i capelli, il viso, le scarpe e il cappello che definiscono Waldo. Inoltre, rispetto ad altre persone nell’immagine, Waldo è sul lato scarno.

Quindi, trovare persone a caso per ottenere l’altezza delle persone in questa foto. Misura l’altezza media di un gruppo di cose in punti casuali dell’immagine (un semplice schema produrrà un bel po ‘di persone). Se ogni cosa non si trova all’interno di una deviazione standard l’una dall’altra, per il momento vengono ignorate. Confronta la media delle altezze con l’altezza dell’immagine. Se il rapporto è troppo grande (ad es. 1: 2, 1: 4 o similmente chiuso), quindi riprovare. Eseguilo 10 (?) Volte per assicurarsi che i campioni siano tutti abbastanza vicini, escludendo qualsiasi media al di fuori di una deviazione standard. Possibile in Mathematica?

Questa è la tua taglia Waldo. Walso è magro, quindi stai cercando qualcosa 5: 1 o 6: 1 (o qualsiasi altra cosa) ht: wd. Tuttavia, questo non è sufficiente. Se Waldo è parzialmente nascosto, l’altezza potrebbe cambiare. Quindi, stai cercando un blocco di rosso-bianco che ~ 2: 1. Ma ci devono essere più indicatori.

  1. Waldo ha gli occhiali. Cerca due cerchi 0.5: 1 sopra il rosso-bianco.
  2. Pantaloni blu. Qualsiasi quantità di blu alla stessa larghezza entro qualsiasi distanza tra la fine del rosso-bianco e la distanza dai suoi piedi. Nota che indossa una maglietta corta, quindi i piedi non sono troppo vicini.
  3. Il cappello. Rosso-bianco qualsiasi distanza fino a due volte la parte superiore della sua testa. Si noti che deve avere i capelli scuri sotto, e probabilmente occhiali.
  4. Maniche lunghe. rosso-bianco in qualche angolo rispetto al rosso-bianco principale.
  5. Capelli scuri.
  6. Colore della scarpa Non conosco il colore

Qualcuno di quelli potrebbe applicare. Questi sono anche controlli negativi contro persone simili nella foto – ad esempio, # 2 nega con un grembiule rosso-bianco (troppo vicino alle scarpe), # 5 elimina i capelli chiari. Inoltre, la forma è solo un indicatore per ciascuno di questi test. . . il colore solo all’interno della distanza specificata può dare buoni risultati.

Questo restringerà le aree da elaborare.

Memorizzare questi risultati produrrà un insieme di aree che dovrebbero avere Waldo in esso. Escludere tutte le altre aree (ad esempio, per ogni area, selezionare un cerchio due volte più grande della dimensione media della persona), quindi eseguire il processo che @Heike ha disposto con la rimozione di tutto tranne il rosso, e così via.

Qualche idea su come codificarla?


Modificare:

Pensieri su come codificare questo. . . escludere tutte le aree tranne il rosso Waldo, schelizzare le aree rosse e sfoltirle in un unico punto. Fai lo stesso con i capelli marrone Waldo, i pantaloni Waldo blu, i colors delle scarpe Waldo. Per il colore della pelle Waldo, escludere, quindi trovare il contorno.

Quindi, escludere i non-rossi, dilatare (molto) tutte le aree rosse, quindi schelizzare e sfoltire. Questa parte fornirà un elenco di possibili punti centrali Waldo. Questo sarà il marcatore per confrontare tutte le altre sezioni di colore di Waldo in.

Da qui, usando le aree rosse scheletrate (non quelle dilatate), conta le linee in ogni area. Se c’è il numero corretto (quattro, giusto?), Questa è certamente una zona ansible. Se no, immagino che lo escluda (essendo un centro Waldo … potrebbe essere ancora il suo cappello).

Quindi controlla se c’è una forma del viso sopra, un punto di capelli sopra, punto di pantaloni sotto, punti di scarpa in basso, e così via.

Nessun codice ancora – ancora leggendo i documenti.

Ho una soluzione rapida per trovare Waldo usando OpenCV.

Ho usato la funzione di corrispondenza dei modelli disponibile in OpenCV per trovare Waldo.

Per fare questo è necessario un modello. Così ho ritagliato Waldo dall’immagine originale e l’ho usato come modello.

inserisci la descrizione dell'immagine qui

Successivamente ho chiamato la funzione cv2.matchTemplate() insieme al coefficiente di correlazione normalizzato come metodo utilizzato. Ha restituito un’alta probabilità in una singola regione come mostrato in bianco sotto (da qualche parte nella regione in alto a sinistra):

inserisci la descrizione dell'immagine qui

La posizione della regione più probabile è stata trovata utilizzando la funzione cv2.minMaxLoc() , che ho poi utilizzato per disegnare il rettangolo per evidenziare Waldo:

inserisci la descrizione dell'immagine qui