Wie finde ich Waldo mit Mathematica?

1542

Das nervte mich über das Wochenende: Was ist ein guter Weg, um diese zu lösen ? Wo ist Waldo? [ 'Wally' außerhalb Nordamerikas] Rätsel mit Mathematica (Bildverarbeitung und andere Funktionen)?

Folgendes habe ich bisher: Eine Funktion, die die visuelle Komplexität ein wenig reduziert, indem einige der nicht roten Farben gedimmt werden:

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

Und ein Beispiel für eine URL, bei der dies funktioniert:

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

(Waldo ist an der Kasse):

Original Bild

Mathematica Grafik

Arnoud Buzing
quelle
31
@yoda - oben links, Tisch mit vielen Schuhen, eine Registrierkasse und Waldo in der Nähe der Tischecke.
Arnoud Buzing
8
Als Doktorand in Computer Vision bin ich sooo versucht, dies zu versuchen ... aber ich muss widerstehen. Für das, was es wert ist, würde ich mich für das Histogramm orientierter Verläufe + Schiebefenster-SVM entscheiden, wie in dieser sehr einflussreichen Arbeit (Warnung: pdf).
Dimatura
54
"Wo ist Wally? " >. <
Leichtigkeitsrennen im Orbit
2
Können wir die Frage ändern, um auch andere Sprachen zu unterstützen? Ich dachte darüber nach, es mit Matlab
Andrey Rubshtein
2
@ArnoudBuzing: In Ihrer Frage könnten Sie Waldo finden, indem Sie sich die Auswahl ansehen, die am meisten Weiß enthält. : /
Tamara Wijsman

Antworten:

1640

Ich habe Waldo gefunden!

Waldo war gefunden worden

Wie ich es gemacht habe

Zuerst filtere ich alle Farben heraus, die nicht rot sind

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

Als nächstes berechne ich die Korrelation dieses Bildes mit einem einfachen Schwarz-Weiß-Muster, um die Rot-Weiß-Übergänge im Hemd zu finden.

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

Ich benutze es Binarize, um die Pixel im Bild mit einer ausreichend hohen Korrelation auszuwählen und einen weißen Kreis um sie zu zeichnen, um sie mit hervorzuhebenDilation

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

Ich musste ein wenig mit dem Level herumspielen. Wenn der Pegel zu hoch ist, werden zu viele Fehlalarme ausgewählt.

Schließlich kombiniere ich dieses Ergebnis mit dem Originalbild, um das obige Ergebnis zu erhalten

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]
Heike
quelle
52
@MikeBantegui Obwohl Heikes Lösung großartig ist, würde ich sie nicht so schnell in eine WhereIsWaldoFunktion packen , da es sich nicht um eine allgemeine Lösung handelt. Heike selbst hat darauf hingewiesen, dass die Levels herumgespielt werden müssen, bevor Sie ein positives Ergebnis erzielen können. Um zu sehen, was ich meine, probieren Sie Ihre verpackte Funktion so aus, wie sie ist. "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"Mit dieser Funktion ist es schwieriger.
abcd
17
Dieses Bild ist schwieriger: Waldo . Ich denke jedoch, dass es immer noch nützlich ist, etwas zu haben, das potenzielle Waldos hervorheben kann (für eine Definition von "nützlich"). (Dies erinnert mich an einige Dinge, die iPhoto manchmal als Gesicht in unserer Fotosammlung identifiziert ...)
Brett Champion
33
Bitte lesen
Bill the Lizard
155
Sie scheinen die Regeln von Where's Waldo missverstanden zu haben. Das ist eindeutig Betrug.
Stefan Kendall
91
Dies ist zwar ein netter Hack, funktioniert aber einfach nicht. Es erfordert eine manuelle Abstimmung und funktioniert nur mit einem Bild. Ich verstehe nicht, warum dies positiv bewertet und sogar als Antwort gewählt wird. Es hält andere davon ab, überhaupt mit besseren Arbeitsmethoden zu antworten.
Sam Hocevar
144

Meine Vermutung über einen "kugelsicheren Weg, dies zu tun" (denken Sie, die CIA findet Waldo jederzeit in jedem Satellitenbild, nicht nur in einem einzigen Bild ohne konkurrierende Elemente wie gestreifte Hemden) ... Ich würde eine Boltzmann-Maschine auf vielen Bildern von Waldo trainieren - alle Variationen von ihm sitzen, stehen, verschlossen usw.; Hemd, Hut, Kamera und alle Arbeiten. Sie brauchen kein großes Korpus Waldos (vielleicht reichen 3-5), aber je mehr desto besser.

Dadurch werden Wahrscheinlichkeiten verschiedenen Elementen zugeordnet, die in der richtigen Anordnung auftreten, und dann (über Segmentierung) die durchschnittliche Objektgröße ermittelt. Das Quellbild wird in Zellen von Objekten fragmentiert, die einzelnen Personen am ähnlichsten sind (unter Berücksichtigung möglicher Okklusionen und Posenänderungen) ), aber da Waldo-Bilder normalerweise eine Menge Leute in ungefähr demselben Maßstab enthalten, sollte dies eine sehr einfache Aufgabe sein und dann diese Segmente der vorgeübten Boltzmann-Maschine füttern. Es gibt Ihnen die Wahrscheinlichkeit, dass jeder Waldo ist. Nehmen Sie eine mit der höchsten Wahrscheinlichkeit.

So funktionieren OCR, Postleitzahlleser und streichellose Handschrifterkennung heute. Grundsätzlich wissen Sie, dass die Antwort da ist, Sie wissen mehr oder weniger, wie sie aussehen sollte, und alles andere mag gemeinsame Elemente haben, ist aber definitiv "nicht es", also kümmern Sie sich nicht um das "nicht es", Sie Schauen Sie sich nur die Wahrscheinlichkeit von "es" unter allen möglichen "es" an, die Sie zuvor gesehen haben "an (in Postleitzahlen würden Sie beispielsweise BM nur für 1s, nur 2s, nur 3s usw. trainieren und dann jeweils füttern Dies funktioniert viel besser als die Lernfunktionen eines einzelnen neuronalen Netzwerks aller Zahlen.

Gregory Klopper
quelle
13
Reichen dafür nicht einfach nur neuronale Netze aus? Außerdem behauptet der Wikipedia-Artikel, dass Boltzmann-Maschinen nicht praktisch sind.
GClaramunt
2
Ohne es zu versuchen, bin ich mir nicht sicher, aber wenn es groß genug und komplex genug ist, sollte ein neuronales Netzwerk für ALLES ausreichen. Besonders bei Wiederholungen. Boltzmann-Maschinen sind SEHR SEHR SEHR gut geeignet, um einen ziemlich vereinfachten Datensatz mit hohem Rauschen in einem Datenmeer zu erkennen, das sich von ihm selbst unterscheidet.
Gregory Klopper
14
Postleitzahlen werden mit Boltzmann-Maschinen ständig gelesen, und die Genauigkeit der Postzustellung ist durch das Dach gegangen.
Gregory Klopper
47

Ich stimme @GregoryKlopper zu, dass der richtige Weg, um das allgemeine Problem zu lösen, Waldo (oder ein Objekt von Interesse) in einem beliebigen Bild zu finden, darin besteht, einen überwachten Klassifikator für maschinelles Lernen zu trainieren. Anhand vieler positiv und negativ gekennzeichneter Beispiele könnte ein Algorithmus wie Support Vector Machine , Boosted Decision Stump oder Boltzmann Machine wahrscheinlich trainiert werden, um bei diesem Problem eine hohe Genauigkeit zu erzielen. Mathematica nimmt diese Algorithmen sogar in sein Machine Learning Framework auf .

Die zwei Herausforderungen beim Training eines Waldo-Klassifikators wären:

  1. Bestimmen der richtigen Bildfeature-Transformation. Hier wäre die Antwort von @ Heike nützlich: Ein Rotfilter und ein Streifenmusterdetektor (z. B. Wavelet- oder DCT-Zerlegung) wären eine gute Möglichkeit, Rohpixel in ein Format umzuwandeln, aus dem der Klassifizierungsalgorithmus lernen könnte. Eine blockbasierte Zerlegung, die alle Unterabschnitte des Bildes bewertet, wäre ebenfalls erforderlich ... dies wird jedoch dadurch erleichtert, dass Waldo a) immer ungefähr gleich groß ist und b) in jedem Bild immer genau einmal vorhanden ist.
  2. Erhalten Sie genügend Trainingsbeispiele. SVMs funktionieren am besten mit mindestens 100 Beispielen jeder Klasse. Kommerzielle Anwendungen des Boostings (z. B. die Gesichtsfokussierung in Digitalkameras) werden an Millionen von positiven und negativen Beispielen trainiert.

Eine schnelle Google-Bildsuche liefert einige gute Daten - ich werde versuchen, einige Trainingsbeispiele zu sammeln und diese jetzt zu codieren!

Aber selbst ein Ansatz des maschinellen Lernens (oder der von @iND vorgeschlagene regelbasierte Ansatz) wird um ein Bild wie das Land Waldos kämpfen !

lubar
quelle
Ein auf maschinellem Lernen basierendes Computer-Vision-System, das versucht, das Problem "Wo ist Waldo" in der realen Welt zu lösen (dh eine bestimmte Person auf Crowd-Fotos auf Flickr zu finden), wurde letztes Jahr auf der Konferenz für Computer Vision und Mustererkennung vorgestellt. Sie betrügen jedoch ein wenig, indem sie einige 3D-Standortinformationen hinzufügen, indem sie mehrere Fotos derselben Szene verwenden.
Lubar
41

Ich kenne Mathematica nicht. . . schade. Aber die obige Antwort gefällt mir größtenteils.

Dennoch gibt in Berufung auf den Streifen ein großer Fehler ist allein aufzulesen die Antwort (Ich persönlich habe kein Problem mit einer manuellen Einstellung). Es ist ein Beispiel (aufgeführt von Brett - Meister, hier ) vorgestellt , die zeigen , dass sie in Zeiten, das Hemd Muster aufzubrechen. Dann wird es ein komplexeres Muster.

Ich würde einen Ansatz von Form-ID und Farben zusammen mit räumlichen Beziehungen versuchen. Ähnlich wie bei der Gesichtserkennung können Sie nach geometrischen Mustern in bestimmten Verhältnissen suchen. Die Einschränkung ist, dass normalerweise eine oder mehrere dieser Formen verdeckt sind.

Holen Sie sich einen Weißabgleich auf dem Bild und einen Rotabgleich auf dem Bild. Ich glaube, Waldo hat immer den gleichen Wert / Farbton, aber das Bild stammt möglicherweise von einem Scan oder einer schlechten Kopie. Beziehen Sie sich dann immer auf eine Reihe der Farben, die Waldo tatsächlich hat: Rot, Weiß, Dunkelbraun, Blau, Pfirsich, {Schuhfarbe}.

Es gibt ein Hemdmuster und auch die Hosen, Brillen, Haare, das Gesicht, die Schuhe und den Hut, die Waldo definieren. Außerdem ist Waldo im Vergleich zu anderen Personen auf dem Bild eher dünn.

Finden Sie also zufällige Personen, um die Größe der Personen in diesem Bild zu ermitteln. Messen Sie die durchschnittliche Höhe einer Reihe von Dingen an zufälligen Punkten im Bild (ein einfacher Umriss erzeugt einige einzelne Personen). Wenn jedes Ding nicht innerhalb einer Standardabweichung voneinander liegt, werden sie vorerst ignoriert. Vergleichen Sie den Durchschnitt der Höhen mit der Höhe des Bildes. Wenn das Verhältnis zu groß ist (z. B. 1: 2, 1: 4 oder ähnlich nahe), versuchen Sie es erneut. Führen Sie es 10 (?) Mal durch, um sicherzustellen, dass alle Stichproben ziemlich nahe beieinander liegen, mit Ausnahme von Durchschnittswerten, die außerhalb einer Standardabweichung liegen. In Mathematica möglich?

Dies ist Ihre Waldo-Größe. Walso ist dünn, also suchen Sie etwas 5: 1 oder 6: 1 (oder was auch immer) ht: wd. Dies reicht jedoch nicht aus. Wenn Waldo teilweise versteckt ist, kann sich die Höhe ändern. Sie suchen also nach einem rot-weißen Block, der ~ 2: 1 ist. Aber es muss mehr Indikatoren geben.

  1. Waldo hat eine Brille. Suchen Sie nach zwei Kreisen 0,5: 1 über dem Rot-Weiß.
  2. Blaue Hosen. Jede Menge Blau bei gleicher Breite in einem beliebigen Abstand zwischen dem Ende des Rot-Weiß und dem Abstand zu seinen Füßen. Beachten Sie, dass er sein Hemd kurz trägt, damit die Füße nicht zu eng sind.
  3. Der Hut. Rot-weiß in jeder Entfernung bis zur doppelten Spitze seines Kopfes. Beachten Sie, dass es unten dunkles Haar und wahrscheinlich eine Brille haben muss.
  4. Lange Ärmel. rot-weiß in einem Winkel vom Hauptrot-weiß.
  5. Dunkles Haar.
  6. Schuhfarbe. Ich kenne die Farbe nicht.

Jeder von diesen könnte zutreffen. Dies sind auch negative Überprüfungen gegen ähnliche Personen auf dem Bild - z. B. negiert # 2 das Tragen einer rot-weißen Schürze (zu nahe an Schuhen), # 5 eliminiert helles Haar. Außerdem ist die Form nur ein Indikator für jeden dieser Tests. . . Farbe allein innerhalb des angegebenen Abstands kann zu guten Ergebnissen führen.

Dadurch werden die zu verarbeitenden Bereiche eingegrenzt.

Durch das Speichern dieser Ergebnisse wird eine Reihe von Bereichen erstellt, in denen Waldo enthalten sein sollte . Schließen Sie alle anderen Bereiche aus (z. B. wählen Sie für jeden Bereich einen Kreis aus, der doppelt so groß ist wie die durchschnittliche Personengröße), und führen Sie dann den von @Heike festgelegten Prozess aus, indem Sie alle außer Rot entfernen und so weiter.

Irgendwelche Gedanken darüber, wie man das codiert?


Bearbeiten:

Gedanken darüber, wie man das codiert. . . Schließen Sie alle Bereiche außer Waldo-Rot aus, skelettieren Sie die roten Bereiche und beschneiden Sie sie auf einen einzigen Punkt. Machen Sie dasselbe für Waldo Haare braun, Waldo Hosen blau, Waldo Schuhfarbe. Für die Waldo-Hautfarbe ausschließen und dann den Umriss finden.

Als nächstes nicht rot ausschließen, alle roten Bereiche erweitern (viel), dann skelettieren und beschneiden. Dieser Teil enthält eine Liste möglicher Waldo-Mittelpunkte. Dies ist der Marker, mit dem alle anderen Waldo-Farbabschnitte verglichen werden können.

Von hier aus zählen Sie anhand der skelettierten roten Bereiche (nicht der erweiterten) die Linien in jedem Bereich. Wenn es die richtige Zahl gibt (vier, richtig?), Ist dies sicherlich ein möglicher Bereich. Wenn nicht, schließe ich es einfach aus (als Waldo-Zentrum ... es kann immer noch sein Hut sein).

Überprüfen Sie dann, ob oben eine Gesichtsform, oben ein Haarpunkt, unten ein Hosenpunkt, unten ein Schuhpunkt usw. vorhanden ist.

Noch kein Code - liest noch die Dokumente.

iND
quelle
8
Vielleicht können Sie einen Proof of Concept in dem System / der Sprache vorlegen, mit dem Sie vertraut sind. Dies gibt Ihnen auch ein Gefühl dafür, wo Schwierigkeiten auftreten könnten.
Szabolcs
1
Oh, ich genieße die Herausforderung so wie sie ist. Es gibt mir etwas zu tun zwischen Spaziergängen am Strand und Anziehen zum Abendessen.
Am
1
Damit. . . Warum die Abstimmungen? Wie unterscheidet sich das von der anderen spekulativen Antwort hier? Ist dies ein Vorschlag, diese Frage ernster zu nehmen? Oder nur, dass ich bei meinen Ermittlungen ernsthafter wirken sollte? Ist mein Ansatz tatsächlich falsch?
Am
3
Ich habe Sie nicht abgelehnt und ich denke nicht, dass Abstimmungen für ehrliche Antwortversuche geeignet sind (es sei denn, sie geben Fehlinformationen). Der wahrscheinlichste Grund für die Abstimmungen ist, dass Sie den (ziemlich kompliziert klingenden) Ansatz nicht ausprobiert zu haben schienen und eine gute Lösung zu finden, würde wahrscheinlich eine Menge praktischer Experimente erfordern und viele Ideen ausschließen. Die andere spekulative Antwort schlägt eine allgemeine Methode (als Ausgangspunkt) vor, die in der Vergangenheit für ähnliche Probleme verwendet wurde, und es gibt eine gute Menge an Literatur darüber. Ich versuche nur zu erklären, was passiert ist.
Szabolcs
Danke für die Erklärung. Ich denke, ich konzentriere mich nicht auf die Geschichte der Ideen.
Am
2

Ich habe eine schnelle Lösung, um Waldo mit OpenCV zu finden.

Ich habe die in OpenCV verfügbare Template-Matching- Funktion verwendet, um Waldo zu finden.

Dazu wird eine Vorlage benötigt. Also habe ich Waldo aus dem Originalbild herausgeschnitten und als Vorlage verwendet.

Geben Sie hier die Bildbeschreibung ein

Als nächstes nannte ich die cv2.matchTemplate()Funktion zusammen mit dem normalisierten Korrelationskoeffizienten als verwendete Methode. Es wurde eine hohe Wahrscheinlichkeit für eine einzelne Region zurückgegeben, wie unten in Weiß gezeigt (irgendwo oben links):

Geben Sie hier die Bildbeschreibung ein

Die Position des höchstwahrscheinlichen Bereichs wurde mithilfe der cv2.minMaxLoc()Funktion ermittelt, mit der ich dann das Rechteck gezeichnet habe, um Waldo hervorzuheben:

Geben Sie hier die Bildbeschreibung ein

Jeru Luke
quelle
7
Versuchen Sie, die bekanntesten Fragen der Bildverarbeitung von SO zu beantworten? ;) Ihre Lösung ist nett und einfach, aber a / funktioniert nur für dieses bestimmte Bild und b / benötigt das genaue Bild von Waldo, das Sie vorher finden möchten, während ich denke, dass die Frage darin bestand, einen Waldo in einem "Wo ist Waldo-Bild" wie zu finden Sie würden das normale Spiel spielen: ohne vorher zu wissen, wie er aussieht. Diese Frage macht sowieso viel Spaß
Soltius
@ Solitus ha genau !!! Ich habe es nur für dieses Bild gearbeitet. Es wäre allerdings eine Herausforderung, es für verschiedene Bilder zu bearbeiten !!
Jeru Luke