Template Matching (subimage recognition via Formel) vs KNN

[Xyz1]

Hallo, ich wollte mal fragen wer Erfahrungen damit hat... Welche Vor und Nachteile hätte A (TM) und welche B (NN)?
Konkret geht es darum, ein meist ähnliches Muster in einem Bild zu finden.
Das kann größer/kleiner, etwas verändert oder irgendwo in dem Bild sein.
Das geht mit A: https://docs.opencv.org/2.4/doc/tut...rams/template_matching/template_matching.html
Oder B: einem künstlichen neuronalen Netz.
Welches wäre denn wofür besser?
Welches könnte sich denn besser anpassen oder wäre besser, schneller usw. und warum?
Das sind bestimmt jetzt zu viele Fragen.

 

[mihe7]

Ich denke, das wirst Du testen müssen. Außerdem vermute ich mal, dass Du die Suche nicht über Pixel sondern über Features (HOG, SURF/SIFT) durchführen werden musst.

 

[Xyz1]

das wirst Du testen müssen

Ok

dass Du die Suche nicht über Pixel

Wieso nicht? Ich hab jetzt schon verkleinert und in Graustufen umgewandelt um nur noch einen int Wert pro Pixel zu haben...... Wird das NN dann zu groß?

Interessiert dich, was ich konkret suche?

Danke für Deine Antwort!

 

[mihe7]

Wieso nicht?

Hm... Wie soll das funktionieren wenn Du z. B. ein Auge mit 10x10 Pixel suchst, im Bild das Auge aber 50 x 50 groß ist?

 

[Xyz1]

Also ich habe mal ein Beispiel.
Ich suche die Ausgangsstellungen beim Schach:













Das NN soll dann folgendes liefern:
0 42 5 325
1 6 44 309
2 46 167 276
3 226 225 245
...
12 22 30 349
13 118 3 285

Also den x und y Wert der linken oberen Ecke und die Länge.

wenn Du z. B. ein Auge mit 10x10 Pixel suchst, im Bild das Auge aber 50 x 50 groß ist

Das NN kriegt alle alle Grauwerte des Bilds als Eingabe und gibt 3 Werte aus.

Aber ich denk das Problem könnte sein, die Koordinaten auch bei xbeliebigen Figurenstellungen zu erkennen?

 

[mihe7]

Das scheint mir mit TM lösbar. Mit Hough-Transformation das Spielfeld suchen, dann über die Größe des Spielfelds den Skalierungsfaktor ermitteln.

 

[Xyz1]

Ich bin jetzt aber heiß darauf, NN zu verwenden...
Im Vergleich dazu sind TM Librarys auch gigantisch groß.
Ich hatt auch mal selber einen Algorithmus mit wenigen Zeilen dafür der ist aber Opfer des Papierkorbs geworden.

 

[mihe7]

Sollte doch genauso funktionieren.

 

[Xyz1]

Also die Grafiken sind ja 480x540... Brauche ich dann wirklich 259.200 Input Neuronen? Das scheint mir nicht praktikabel.

 

[mihe7]

Nein. Du trainierst z. B. einen Classifier, der die Figuren erkennt. Fürs Training nutzt Du z. B. 20x20 Bilder (ggf. reichen auch 10x10 Pixel aus), die jeweils ein ggf. skaliertes Feld des Schachbretts inkl. Label enthalten. Für das Training bietet es sich an, die Bilder etwas zu verändern (quasi ein Rauschen hinzufügen, verschieben usw.) damit der Classifier robuster wird.

 

[mihe7]

Wo hast Du denn die Bilder her?

 

[Xyz1]

Und dieser Classifier... kann 0 liefern, in dem Fall wenn er nix erkannt hat?

 

[Xyz1]

Wo hast Du denn die Bilder her?

Die hatte ich vorhin selber erstellt (8-bit grayscale, cropped und scaled)

Bearbeitung, hier wären 1000 als Trainingsdaten: https://ufile.io/9fxi2oal

 

[mihe7]

Die hatte ich vorhin selber erstellt

Ich meinte die Figuren bzw. das Schachbrett

Und dieser Classifier... kann 0 liefern, in dem Fall wenn er nix erkannt hat?

Die Output-Neuronen geben ja an, mit welcher Wahrscheinlichkeit etwas erkannt wurde. Dem entsprechend kannst Du sagen: wenn die Wahrscheinlichkeit unter x % liegt, wurde nichts erkannt.

 

[Xyz1]

Ich meinte die Figuren bzw. das Schachbrett

Hm, das ist ein Screenshot aus einem Schach Programm...

mit welcher Wahrscheinlichkeit etwas erkannt wurde

Aber ich möchte ja zunächst nur mal die Position des Schachfeldes im Screenshot...

 

[mihe7]

Aber ich möchte ja zunächst nur mal die Position des Schachfeldes im Screenshot...

Das Problem ist:

Also die Grafiken sind ja 480x540... Brauche ich dann wirklich 259.200 Input Neuronen? Das scheint mir nicht praktikabel.

Darum habe ich oben geschrieben, dass die Suche über Pixel ungeeignet ist, sondern andere Features verwendet werden müssen. Du könntest z. B. je Bild eine fixe Anzahl an Eckpunkten (edge bzw. corner detection) extrahieren und dann mit der tatsächlichen Lage des Spielfelds als Label trainieren. Ob das allerdings robust funktioniert...

Alternativ wäre eben umgekehrt: erst die Spielfelder erkennen und anhand dieser das Schachbrett und damit die Lage.

 

[Xyz1]

sondern andere Features verwendet werden müssen

Kannst Du mir dabei helfen? ... ich bin da mit meinem Latein am Ende.
Ich möchte es aber gerne schaffen.

 

[mihe7]

Ich weiß nicht, wie ich da groß helfen könnte. Wenn Du die Ecken finden willst: https://docs.opencv.org/3.0-beta/do...2d/py_features_harris/py_features_harris.html

 

[Xyz1]

erst die Spielfelder erkennen

Du meinst die Figuren oder? Das wäre der zweite Schritt. (Dritter Schritt ist fen String erstellen, aber das würd jetzt zu weit gehen).

Aber wie soll ich Figuren erkennen, bevor ich weiß, wo sie sind?

 

[mihe7]

Aber wie soll ich Figuren erkennen, bevor ich weiß, wo sie sind?

Über ein Sliding Window (wie beim Template Matching).

 

[Xyz1]

Über ein Sliding Window (wie beim Template Matching).

Mir fehlen die Grundlagen...
(ich werd mir eine Vorlesung dazu anhören, aber welche?)
Danke dennoch.

 

[mihe7]

Mir fehlen die Grundlagen...

Mir auch

 

[Xyz1]

Hm, und noch etwas... es gibt eine harte Zeitschranke, idealerweise soll das in 100ms passieren, wobei ein Screenshot erstellen bei mir schon 30ms dauert...
Danke für das geframedte Video.. Ich schaue mal rein.

 

[Xyz1]

YOLO Rofl

 

[Xyz1]

@mihe7 Das Schachfeld wäre hierbei aber viel größer als die Fahrzeuge... deshalb, corners finden?

 

[mihe7]

Danke für das geframedte Video..

Das ist ein kompletter Kurs über Convulotional Deep Networks...

Das Schachfeld wäre hierbei aber viel größer als die Fahrzeuge... deshalb, corners finden?

Jein. Es geht einfach um die Frage, wie man die Verarbeitungszeit reduzieren kann. Du sagst ja z. B.: ich brauche keine drei Kanäle (RGB), einer reicht (Graustufen). Warum? Weil Du dadurch die Zahl der Features auf ein Drittel reduzierst. Jetzt würde ich mal vermuten, dass ein Bild mit einem 0,5 Megapixel (= Features) immer noch viel zu groß, um hier effizient ein NN anzulernen.

Daher ist die Frage, ob man statt Pixel nicht andere Features des Bilds verwenden kann. Eine Idee wäre eben, statt Pixel nur die Eckpunkte zu verwenden.

 

[Xyz1]

mihe7, sorry wenn ich Dich nerve, kann der classifier, der die linke obere Ecke erkennt, derselbe sein, der auch die rechte untere Ecke erkennt?, sprich kann ein NN zwei unterschiedliche Dinge erkennen - oder wäre es besser, zwei NN einzusetzen, wobei das zweite nur nach dem ersten greift? Ich vermute ich kann dadurch einige Layer sparen.
Und zu den Features... das ist ja schon zweimal um 50 % verkleinert, einmal ausgeschnitten, einmal 0,5-skaliert - und es ist in Graustufen => 0,5*0,5*1/3 = ca um 91 % verkleinert.

 

[mihe7]

sprich kann ein NN zwei unterschiedliche Dinge erkennen

Selbstverständlich. Ich würde sogar sagen, es soll unterschiedliche Dinge erkennen. Jedes Output-Neuron stellt eine solche Klasse dar. Du wählst am Ende die Klasse, für die das Output-Neuron den höchsten Wert liefert.

 

[Xyz1]

Super,
A: Eckpunkt gesehen? (0 oder 1)
B: linke obere oder rechte untere Ecke? (0 oder 1)
C: x_1 Postion (+^4) (0 oder 1)
D: x_2 Postion (+^3) (0 oder 1)
E: x_3 Postion (+^1) (0 oder 1)
F: x_4 Postion (+^0) (0 oder 1)
G: y_1 Postion (+^4) (0 oder 1)
H: y_2 Postion (+^3) (0 oder 1)
I: y_3 Postion (+^1) (0 oder 1)
J: y_4 Postion (+^0) (0 oder 1)

Also 10 output layer?

Alles soweit korrekt?

(Dann stricke ich jetzt mal das Netz....)

 

[mihe7]

Hm... mir ist nicht ganz klar, wie Du das anwenden willst, aber schauen wir mal was rauskommt

 

[Xyz1]

mihe7, ich brauche dann auch noch ein zweites Netz, um diesmal nicht die Position zu erkennen, sondern eine Figur zu klassifizieren. Hast du noch einen Tipp? ziel ist der FEN String.

 

[mihe7]

S. Kommentar #10. Wenn Du Lage und Größe des Spielfelds kennst, kannst Du ja die einzelnen Felder berechnen (div 8), runterskalieren (auf 10x10 oder 20x20, je nachdem) und gegen den Classifier laufen lassen.

 

[Xyz1]

Jap, ich muss ihn nur vorher trainieren. D.h. gaaaanz viele Schachfiguren ausschneiden.
(Mitm Auto würde man an dieser Stelle eine Teststrecke abfahren....(?))
Danke für Deine Hilfe!

 

[Xyz1]

mihe, das klappt nicht, das überfüttert und liefert ungültige Werte zurück, das sind zu viele Dinge die erkannt werden müssen. Magst du mal einen Blick drauf werfen?

 

[Xyz1]

Habe den Fehler gefunden, es ist aber mega blöd.

Es geht um eine untere Ecke:

Quader 36x32:
201 206 201 197 197 197 191 61 61 61
199 195 199 197 197 202 197 61 61 61
0 0 202 205 205 195 194 61 61 61
0 0 202 205 205 195 194 61 61 61
0 0 202 199 199 198 194 61 61 61
0 0 202 191 191 187 191 61 61 61
202 202 202 197 197 187 189 61 61 61
202 202 202 197 197 187 189 61 61 61
202 203 197 199 199 191 187 61 61 61
202 202 201 199 199 190 191 61 61 61

Quader 36x33: (liegt direkt unter x32)
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61 61 61

"Es" hat gelernt, die Ecke liegt in 36x33. Darin ist aber gar nix zu erkennen, die Ecke liegt tatsächlich in 36x32.

mihe7, was macht man in solchen Fällen?

 

[mihe7]

Ich denke, wir machen mal der PN weiter, so interessant ist das für die Allgemeinheit wohl auch nicht...

 

[Xyz1]

so interessant ist das für die Allgemeinheit wohl auch nicht

Das stimmt . Hast Post.