# Template Matching (subimage recognition via Formel) vs KNN



## Xyz1 (3. Jul 2019)

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 (3. Jul 2019)

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 (3. Jul 2019)

mihe7 hat gesagt.:


> das wirst Du testen müssen


Ok



mihe7 hat gesagt.:


> 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 (3. Jul 2019)

Tobias-nrw hat gesagt.:


> 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 (3. Jul 2019)

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.



mihe7 hat gesagt.:


> 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 (3. Jul 2019)

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


----------



## Xyz1 (3. Jul 2019)

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 (3. Jul 2019)

Sollte doch genauso funktionieren.


----------



## Xyz1 (3. Jul 2019)

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


----------



## mihe7 (3. Jul 2019)

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 (3. Jul 2019)

Wo hast Du denn die Bilder her?


----------



## Xyz1 (3. Jul 2019)

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


----------



## Xyz1 (3. Jul 2019)

mihe7 hat gesagt.:


> 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 (3. Jul 2019)

Tobias-nrw hat gesagt.:


> Die hatte ich vorhin selber erstellt


Ich meinte die Figuren bzw. das Schachbrett  



Tobias-nrw hat gesagt.:


> 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 (3. Jul 2019)

mihe7 hat gesagt.:


> Ich meinte die Figuren bzw. das Schachbrett


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



mihe7 hat gesagt.:


> mit welcher Wahrscheinlichkeit etwas erkannt wurde


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


----------



## mihe7 (3. Jul 2019)

Tobias-nrw hat gesagt.:


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



Das Problem ist: 


Tobias-nrw hat gesagt.:


> 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 (3. Jul 2019)

mihe7 hat gesagt.:


> 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 (3. Jul 2019)

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 (3. Jul 2019)

mihe7 hat gesagt.:


> 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 (3. Jul 2019)

Tobias-nrw hat gesagt.:


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


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


----------



## Xyz1 (3. Jul 2019)

mihe7 hat gesagt.:


> Ü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 (3. Jul 2019)

Tobias-nrw hat gesagt.:


> Mir fehlen die Grundlagen...


Mir auch


----------



## Xyz1 (3. Jul 2019)

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 (3. Jul 2019)

YOLO Rofl


----------



## Xyz1 (3. Jul 2019)

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


----------



## mihe7 (3. Jul 2019)

Tobias-nrw hat gesagt.:


> Danke für das geframedte Video..


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



Tobias-nrw hat gesagt.:


> 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 (4. Jul 2019)

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 (4. Jul 2019)

Tobias-nrw hat gesagt.:


> 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 (4. Jul 2019)

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 (4. Jul 2019)

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


----------



## Xyz1 (4. Jul 2019)

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 (4. Jul 2019)

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 (4. Jul 2019)

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 (4. Jul 2019)

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 (4. Jul 2019)

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 (4. Jul 2019)

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


----------



## Xyz1 (4. Jul 2019)

mihe7 hat gesagt.:


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


Das stimmt  . Hast Post.


----------

