Erkennen ähnlicher Formen in zufälliger Skalierung und Translation
Ich bin gerade ratlos, wenn ich Sachen auf einem graphischen Bildschirm finde, aber ich weiß nicht, wie ich eine bestimmte Form innerhalb eines Bildes finden kann. Die Form im Bild könnte einen anderen Maßstab haben und natürlich bei einem unbekannten x, y-Versatz liegen.
Abgesehen von Pixelartefakten, die von verschiedenen Skalen herrühren, gibt es auch ein wenig Rauschen in beiden Bildern, daher brauche ich eine etwas tolerante Suche.
Hier ist das Bild, das ich suche.
Es sollte irgendwo in einem Bildschirmabzug meines (doppelten) Bildschirmpuffers erscheinen, etwa 3300 x 1200 Pixel groß. Ich würde natürlich erwarten, es in einem Browserfenster zu finden, aber diese Information sollte nicht notwendig sein.
Das Ziel dieser Übung (bis jetzt) ist es, ein Ergebnis zu finden, das besagt:
- Ja, der Holzrahmen (von dieser ungefähren Farbe und dieser möglicherweise leicht abgeschnittenen Form) wurde auf meinem Bildschirm gefunden (oder nicht); und
- Der Client-Bereich des Spiels (der schwarze Bereich innerhalb des Rahmens) belegt das Rechteck von
(x1,y1)bis(x2,y2).
Ich wäre gerne robust gegen Skalierung und das Rauschen, das wahrscheinlich durch Dithering entsteht. Auf der anderen Seite kann ich einige der üblichen CV-Herausforderungen wie Rotation oder Nicht-Steifigkeit ausschließen. Diese Rahmenform ist für das menschliche Gehirn leicht zu erkennen, wie schwer kann es für eine bestimmte Software sein? Dies ist eine Adobe Flash-Anwendung, und bis vor kurzem dachte ich, dass die Wahrnehmung der Bilder von einer Spiel-GUI einfach sein sollte.
Ich suche nach einem Algorithmus, der in der Lage ist, die x, y-Translation zu finden, bei der die größtmögliche Überlappung zwischen der Nadel und dem Heuhaufen auftritt, und wenn möglich ohne eine Reihe von möglichen Skalierungsfaktoren durchlaufen zu müssen. Im Idealfall könnte der Algorithmus die "Form-Ness" der Bilder in einer Skala abbilden, die von der Skalierung unabhängig ist.
Ich habe ein paar interessante Dinge über Fourier-Transformationen gelesen, um etwas Ähnliches zu erreichen: Bei einem Zielbild im gleichen Maßstab ergaben FFT und einige Matrix-Mathe die Punkte im größeren Bild, die dem Suchmuster entsprachen. Aber ich habe weder den theoretischen Hintergrund, um dies in die Praxis umzusetzen, noch weiß ich, ob dieser Ansatz das Skalierungsproblem elegant bewältigen wird. Hilfe wäre willkommen!
Technologie: Ich programmiere in Clojure / Java, könnte aber Algorithmen in anderen Sprachen anpassen. Ich denke, ich sollte in der Lage sein, mit Bibliotheken zu interagieren, die C-Aufrufkonventionen folgen, aber ich würde eine reine Java-Lösung bevorzugen.
Vielleicht können Sie verstehen, warum ich mich davor gescheut habe, das tatsächliche Bild zu präsentieren. Es ist nur ein blödes Spiel, aber die Aufgabe, es zu lesen, erweist sich als viel herausfordernder, als ich gedacht habe.
Ich bin offensichtlich in der Lage, meinen Bildschirmpuffer genau nach den Pixeln (außer Schwarz) zu durchsuchen, die mein Bild ausmachen, und das sogar in weniger als einer Minute abläuft. Aber mein Ehrgeiz war es, diesen Holzrahmen mit einer Technik zu finden, die zu der Form passt, ungeachtet der Unterschiede, die durch das Skalieren und Dithering entstehen könnten.
Dithering ist in der Tat eine von vielen Frustrationen, die ich mit diesem Projekt habe. Ich habe daran gearbeitet, einige nützliche Vektoren durch Kantenextraktion zu extrahieren, aber Kanten sind schwer fassbar, weil die Pixel eines gegebenen Bereichs weitgehend inkonsistente Farben haben - daher ist es schwierig, echte Kanten von lokalen Dithering-Artefakten zu unterscheiden. Ich hatte keine Ahnung, dass ein so einfach aussehendes Spiel Grafiken erzeugen würde, die für Software so schwer zu erkennen sind.
Soll ich zunächst Pixel lokal modellieren, bevor ich nach Features suche? Sollte ich die Farbtiefe reduzieren, indem ich die niedrigstwertigen Bits der Pixelfarbwerte wegwerfe?
Ich versuche für eine reine Java-Lösung (eigentlich Programmierung in Clojure / Java Mix), also bin ich nicht verrückt nach opencv (das .DLL oder .so ist mit C-Code installiert). Bitte mach dir keine Sorgen über meine Sprachwahl, die Lernerfahrung ist für mich viel interessanter als die Leistung.
3 Antworten
Da ich ein Computer-Vison-Typ bin, würde ich normalerweise auf Feature-Extrahierung und -Matching (SIFT, SURF, LBP usw.) verweisen, aber das ist mit ziemlicher Sicherheit ein Overkill, da die meisten dieser Methoden mehr Invarianzen (= Toleranzen) bieten gegen Transformationen) als Sie eigentlich benötigen (zB gegen Rotation, Luminanzänderung, ...). Auch die Verwendung von Features würde entweder OpenCV oder viele Programmierung beinhalten.
Also hier ist mein Vorschlag für eine einfache Lösung - Sie beurteilen, ob es die Intelligenzschwelle erfüllt:
Es sieht so aus, als hätte das Bild, nach dem Sie suchen, sehr unterschiedliche Strukturen (Buchstaben, Logos usw.). Ich würde vorschlagen, dass Sie eine Pixel-zu-Pixel-Übereinstimmung für jede mögliche Übersetzung und für eine Reihe von verschiedenen Skalen (ich nehme an, der Bereich der Skalen ist begrenzt) - aber nur für einen kleinen unverwechselbaren Patch des gesuchten Bildes (etwa ein quadratischer Teil des gelben Textes). Das ist viel schneller als das Ganze zu vergleichen. Wenn Sie einen ausgefallenen Namen dafür haben wollen: In der Bildbearbeitung wird das Template-Matching nach Korrelation aufgerufen. Die "Vorlage" ist das, was Sie suchen.
Sobald Sie ein paar Kandidaten für Ihren kleinen unverwechselbaren Patch gefunden haben, können Sie überprüfen , ob Sie einen Treffer erzielt haben, indem Sie entweder das gesamte Bild oder, effizienter, ein paar andere
In Bezug auf die Dithering-Toleranz würde ich für eine einfache Vorfilterung beider Bilder (die Vorlage, die Sie suchen, und das Bild, das Ihr Suchraum ist) gehen. Abhängig von den Eigenschaften des Ditherings können Sie mit einer einfachen Box-Unschärfe experimentieren und wahrscheinlich mit einem Median-Filter mit einem kleinen Kernel (3 x 3) fortfahren, wenn das nicht funktioniert. Dadurch erhalten Sie nicht 100% Identität zwischen Vorlage und gesuchtem Bild, sondern robuste numerische Ergebnisse, die Sie vergleichen können.
Im Lichte der Kommentare bearbeiten
Ich verstehe, dass (1) Sie etwas robuster, mehr "CV-like" und ein bisschen mehr Phantasie als eine Lösung wünschen, und dass Sie Skaleninvasivität durch einfaches Scannen durch einen großen Stapel von skeptisch sind verschiedene Maßstäbe.
In Bezug auf (1) ist der kanonische Ansatz, wie bereits erwähnt, die Verwendung von Merkmalsdeskriptoren. Feature-Deskriptoren beschreiben nicht ein vollständiges Bild (oder eine vollständige Form), sondern einen kleinen Teil eines Bildes, der gegen verschiedene Transformationen invariant ist. Schauen Sie sich SIFT und SURF und bei VLFeat , das eine gute SIFT-Implementierung hat und auch MSER und HOG (und ist viel kleiner als OpenCV). SURF ist einfacher zu implementieren als SIFT, beide sind stark patentiert. Beide haben eine "aufrechte" Version, die keine Rotationsinvarianz hat. Dies sollte die Robustheit in Ihrem Fall erhöhen.
Die Strategie, die Sie in Ihrem Kommentar beschreiben, geht mehr in Richtung der Formdeskriptoren als der Bildmerkmaldeskriptoren. Stellen Sie sicher, dass Sie den Unterschied zwischen diesen verstehen! 2D-Formdeskriptoren zielen auf Formen ab, die typischerweise durch einen Umriss oder eine binäre Maske beschrieben werden. Bildmerkmaldeskriptoren (im obigen Sinn Verwendung) zielen auf Bilder mit Intensitätswerten ab, typischerweise Fotografien. Ein interessanter Shapedeskriptor ist Shape-Kontext , viele andere werden zusammengefasst hier . Ich denke nicht, dass dein Problem am besten durch Formdeskriptoren gelöst wird, aber vielleicht habe ich etwas falsch verstanden. Ich würde sehr vorsichtig mit Formdeskriptoren auf Bildkanten umgehen, da Kanten, die erste Ableitungen sind, durch Dithering-Rauschen stark verändert werden können.
Betreffend (2) : Ich würde Sie gerne davon überzeugen, dass das Scannen durch eine Reihe verschiedener Maßstäbe nicht nur ein dummer Hack für diejenigen ist, die Computer Vision nicht kennen! Eigentlich hat es viel in der Vision gemacht, wir haben nur einen schlauen Namen dafür, um die nicht initiierte - Skalierungsraum Suche in die Irre zu führen. Das ist ein bisschen eine Vereinfachung, aber wirklich nur ein bisschen. Die meisten Bildmerkmaldeskriptoren, die in der Praxis verwendet werden, erzielen Skaleninvarianz unter Verwendung eines Skalierungsraums, der ein Stapel von zunehmend herunterskalierten (und tiefpassgefilterten) Bildern ist. Der einzige Trick, den sie hinzufügen, ist Extrema im Maßstabsraum zu suchen und Deskriptoren nur bei diesen Extrema zu berechnen. Dennoch wird der gesamte Skalenraum berechnet und durchlaufen, um diese Extrema zu finden.Im ursprünglichen SIFT-Papier finden Sie dazu eine gute Erklärung.
Nett. Ich habe einmal einen Schummler auf einem Flash-Spiel implementiert, indem ich den Bildschirm auch aufgenommen habe :). Wenn Sie den genauen Rahmen suchen müssen, den Sie im Bild angegeben haben, können Sie einen Farbfilter erstellen, wodurch alle anderen entfernt werden und Sie ein Binärbild erhalten, das Sie für die weitere Verarbeitung verwenden könnten (die Aufgabe wäre, zu finden ein passendes Rechteck mit einem bestimmten Rahmenverhältnis und vier Kerne, die die Ecken in verschiedenen Maßstäben finden würden.
Wenn Sie einen Bildstrom haben und wissen, dass eine Bewegung vorhanden ist, können Sie den Unterschied zwischen den Einzelbildern überwachen, um die Aktionsteile auf Ihrem Bildschirm zu erfassen, indem Sie eine Hintergrundmodellierungslösung verwenden. Kombiniere diese und du wirst ziemlich weit kommen, denke ich, ohne auf exotischere Methoden zurückgreifen zu müssen, wie Multi-Scale-Analyse und so.
Es ein Problem ausgeführt? Mein Cheat nutzte etwa 20 fps, da er schnell genug auf einen Ball klicken musste.
Ich melde mich mit einer Antwort auf meine eigene Frage zurück, um die Leute wissen zu lassen, wo ich damit gelandet bin.
Nachdem ich keine Hinweise auf meinen gesuchten skaleninvarianten Formdeskriptor gefunden oder erhalten habe, entschied ich mich, mit dem Ratschlag von DCS fortzufahren und ziemlich geradlinige Pixelsuche über den gesamten Bildschirm durchzuführen.
Zuerst suchte ich nach einem 512 x 60 großen Teil des Logos. Aber es stellt sich heraus, dass, was schließlich eine Quad-Nested-Schleife (Zeilen / Spalten von Vollbild x Zeilen / Spalten von Suchbild) endet würde für mehr als eine Stunde ausgeführt werden, worst case. Inakzeptabel.
Ich konnte das Problem linear verkleinern, indem ich ein kleineres Suchbild wählte, ein Patch von etwa 48 x 32 Pixel. Dies brachte mich auf ungefähr 30 Sekunden und war immer noch langsamer, als ich es mir gewünscht hätte. Außerdem würde die Zeit steigen, wenn ich später nach anderen Features suchen würde.
Meine Lösung bestand darin, nur nach einer einzigen Scanzeile meines Suchbilds zu suchen, und sogar nach dem Proxy und nicht vollständig. Aufgrund der Comic-Farbnatur des Bildes, das ich suchte, entschied ich, dass durchschnittliche Farbtöne annehmbare Proxies für die Pixel bilden würden, nach denen ich suchte. Ich wählte die "mittlere" Zeile des Suchbildes aus, extrahierte den Farbton (als ganze Zahl zwischen 0 und 7200) für jedes Pixel und berechnete die Summe dieser Farbtonwerte. Im Bildschirmbild berechnete ich eine sich bewegende Summe über die Anzahl von Pixeln entsprechend der Breite des Suchbildes, so dass ich für jede Pixelposition nur das älteste Pixel abziehen und ein einzelnes neues hinzufügen müsste. Die Verwendung von Java Color.rgbToHSB ließ einige Optimierungspotentiale übrig, insbesondere angesichts der Umwandlung in float und zurück, aber der gesamte Bildschirm konnte in ein paar hundert ms vorgesampelt werden.
Also habe ich eine Liste von Unterschieden zwischen den Bildschirmfarbsummen und der für meine Suchbild-Mittellinie erstellt, die beste (dh kleinste) Differenz gefunden und dann einen vollständigen Pixel-für-Pixel-Vergleich für die Positionen gemacht, die den ersten Platz geteilt haben der beste Unterschied. Es gab normalerweise weniger als 10 dieser optimalen Farbgesamtübereinstimmungen, so dass 10 Pixel-zu-Pixel-Vergleiche vernachlässigbare Zeit benötigten.
So, jetzt finde ich mein Suchbild in ungefähr einer halben Sekunde, mit einigem Optimierungspotential, das noch nicht genutzt wurde. Wenn ich mehr verschiedene Skalen "machen" muss, wird mir hoffentlich die unterschiedliche Auflösung erlauben, ein anderes Suchbild ohne Versuch und Irrtum auszuwählen, aber im schlimmsten Fall muss nur ein kleiner Teil der Vergleichsarbeit mehrfach ausgeführt werden, und ich erwarte noch immer unter einer Sekunde.
Ich habe mein ursprüngliches Ziel nicht erreicht, sehr resistent gegen verschiedene Dither (d. h. Detail-Pixel-Wiedergabe) meiner gesuchten Bilder zu sein; Mein Algorithmus erfordert eine gute Übereinstimmung der Farben. Aber angesichts dessen, wie schwierig ein Problem ist, habe ich beschlossen, dass ich diese Brücke überqueren werde, wenn es nötig sein sollte.
Tags und Links opencv image-processing computer-vision fft image-recognition