Gestenerkennung

Problem

Der Nutzer soll Magie per Mauszeiger à la Black & White nutzen können. Dafür müssen wir erkennen ob ein Nutzer eine Geste nachgemalt hat. Es muss also ein Pfad geben der zu einen Zauber gehört.

Idee 1:

Wir erstellen ein Polygon um den Pfad. Dann können wir testen, ob der Nutzer in dieser Fläche gemalt hat.

Wie erstellen wir diese Fläche?

Gehe alle Punkte des Pfades durch

Beim ersten Punkt, finde den Richtungsvektor (R_V) zum nächsten Punkt und normalisiere diesen.

Flippe den Vector R_V um 180°, multipliziere mit dem Threshold (Mindestabstand von Pfad zum Rand, für leichtere Erkennung) und addiere diese neue Richtung auf den ersten Punkt der Ausgangslinie. Man erhält den ersten Punkt des Polygons.

• Drehe den Richtungsvektor R_V um -90° nach Links und addiere den Vektor auf den ersten Punkt der Ausgangslinie.
• Drehe den Richtungsvektor R_V um 90° nach Rechts und addiere den Vektor auf den ersten Punkt der Ausgangslinie.

Wir erhalten zwei weitere Punkte der Hülle.

Nebenbei: Für das rotieren eines Vectors nutzen wir folgenden Algorithmus: https://stackoverflow.com/a/28112459

Für alle weitern Punkte der Ausgangslinie, aber nicht für den letzten Punkt, führe folgende Schritte aus:

• Finde den Richtungsvektor R_V zum nächsten Punkt und normalisiere diesen.

• Erstelle aus den vorherigen Punkt und dem aktuellen Punkt eine Linie L1
• Erstelle aus dem nächsten Punkt und dem aktuellen Punkt eine Linie L2
• Finde den inneren Winkel ⍺ der beiden Linien

• Halbiere den Winkel ⍺ und drehe den Richtungsvektor R_V um (⍺/2 - 90°) links. Multipliziere mal Threshold. Addiere den neuen Vector auf den aktuellen Punkt.
• Halbiere den Winkel ⍺ und drehe den Richtungsvektor R_V um (⍺/2 + 90°) rechts. Multipliziere mal Threshold. Addiere den neuen Vector auf den aktuellen Punkt.

Wir erhalten zwei weitere Punkte der Hülle.

Nebenbei: Für das Finden des Winkels zwischen zwei Linien nutzen wir folgenden Algorithums: https://stackoverflow.com/a/42159152

Für den letzten Punkt müssen folgende Schritte gemacht werden:

• Wir berechnen den Richtungsvektor R_V zum vorherigen Punkt und normalisiere diesen.

• Wir drehen den Vektor R_V um 180°, multiplizieren mit dem Threshold und addieren dies auf den letzten Punkt.

• Drehe den Richtungsvektor R_V um -90° nach Links und addiere den Vektor auf den letzten Punkt der Ausgangslinie.
• Drehe den Richtungsvektor R_V um 90° nach Rechts und addiere den Vektor auf den letzten Punkt der Ausgangslinie.

Wir erhalten die letzten zwei Punkte der Hülle.

Zum Schluss verbinden wir die äußeren Punkte in der korrktet Anordnung zu einem Polygon.

Prüfung mit der Fläche

Nun können wir eine gemalte Linie kontrollieren.

Wir nutzten dafür folgenden Algorithms: https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html

Dieser wurde hier in JS konvertiert: https://stackoverflow.com/a/29915728

Problem 1

Nutzer brauchen nur eine kleine Linie in der Fläche zeichnen damit die Geste erkannt wird.

Lösung Problem 1

Wir legen auf jeden Punkt der Ausgangslinie einen Kreis. Die gemalte Linie muss in jedem Kreis ein Punkt haben damit die Geste erkannt wird.

Problem 2

Wenn der Winkel zwischen zwei Linien zu klein ist, wird das Malen in der Fläche schwierig.

Problem 3

Die Geste kann Linien haben, die sich überschneiden. Der "Ist in Polygon" Algorithmus unterstütz dies nicht.

Problem 4

Komplexe Linien und damit komplexe Polygone als Hülle werden vom "Ist in Polygon" Algorithmus nicht unterstützt.

Idee 2:

Ist eine Abwandlung von Idee 1. Anstelle eines Polygons als Hülle, erstellen wir für jede Linie des Ausgangspfad ein Rechteck.

Nun müssen alle Punkte der gemalten Geste sich mindestens in einem Rechteck befinden. Des Weiteren integrieren wir die Kreis-Routine für alle Ausgangspunkte, damit wir den vollständigen Pfad abdecken. Dank der Rechtecke kommt es an den Punkte zu Überlappungen und wir haben genug Platz bei steilen Winkel. Somit ist Problem 2 gelöst. Problem 3 und 4 treten auch nicht mehr auf, da wir nur simple Rechtecke testen und wir jeweils nur ein Rechteck benötigen damit ein Punkt als "Zum Pfad gehörend" klassifiziert können.

Wie erstellen wir diese Rechtecke?

Für jeden Punkt des Ausgangspfad außer den Letzen:

• Berechne Richtungsvektor zum nächsten Punkt
• Drehe Vektor 135° und 225° nach Links und addiere die zwei Vektoren auf den aktuellen Punkt
• Drehe den Vektor 45° und 315° nach Links und addiere die zwei Vektoren auf den nächsten Punkt

Wir erhalten vier Punkte des Rechtecks das wir abspeichern und zum nächsten Punkt übergehen können.

Optimierung 1

Die Polygone der Gesten können schon vorberechnet und abgespeichert werden oder sollten beim Start der Anwendung einmalig berechnet werden.

Optimierung 2

Die gezeichnete Linie des Nutzers kann On-The-Fly simplifiziert werden:

Gehe jeden Punkt außer den ersten und letzten Punkt durch.

• Erstelle eine Linie L1 zum vorherigen Punkt und L2 zum nächsten Punkt. Berechne den Innenwinkel von L1 und L2
• Berechne den Abstand zum vorherigen Punkt
• Wenn der Abstand unter ein Threshold und Winkel über ein Threshold liegt, dann entferne den aktuellen Punkt

Normalisierung

Wir möchten die Geste irgendwo auf dem Bildschirm, in verschiedensten Größen malen können.

Dafür müssen wir die Gesten normalisieren und vergleich. Was müssen wir dabei machen?

• Platziere Pfad zu (0,0) Koordinate
  • Berechne die kleinste X und Y Koordinate, in dem de ganze Pfad durchgegangen wird
  • Die beiden Werte ergeben einen Vector zu oberen linken Ecke des Pfads
  • Ziehe von allen Punkte diesen Vektor ab und verschiebe den Pfad somit zum Ursprung
• Skaliere den Pfad zu einer festen Breite
  • Der kleinste X Wert sollte dank des vorherigen Schrittes 0 sein
  • Berechne den maximalen X Wert
  • Dividiere den maximalen Wert, welche gleichzeitig die Breite des Pfades ist durch 1 (die später gewünschte Länge) und du erhälst den Skalierungswert
  • Multipliziere jede X/Y-Koordinate des Pfades, um den normalisierten Pfad zu erhalten

Den normalisierten Pfad können wir nun mit normalisierte Ausgangspfade vergleichen

Problem 5

Geschlossene Pfade können unvollständig erkannt werden. Wenn wir folgenden geschlossenen Pfad haben:

Dann ergeben sich folgende Rechtecke:

Gucken wir uns nun folgenden Beispielpfad an und kontrollieren die Erfolgsbedingungen.

1. Aus Idea 2: Ist jeder Punkt des Pfades in mindestens ein Rechteck? ja

2. Aus Problemlösung 1: Hat jeder Punkt des Ausgangspfades ein Punkt des gemalten Pfades in der nähe? ja

Betrachten wir nur diese zwei Annahmen kommen wir zum Schluss das die gemalte Linie valide ist. Der Nutzer hat aber die abschließende Linie nicht gemalt und die Erkennung sollte hierbei fehlschlagen.

Lösung Problem 5

Wenn wir mit einen geschlossenen Pfad vergleichen, müssen wir den Anfangs- und Endpunkt der gemalten Linie wie folgt vergleichen:

1. Habe beide Punkte ein Mindestabstand?
2. Liegen die selben Rechtecke über ihnen?

Dann sollten sie in der nähe sein und die gemalte Linie passt zur Geste.

Problem 6

Die Erstellung des gemalten Pfades hängt von der Erkennung der Maus ab. Um so schneller die Maus gezogen wird, so weniger Punkte werden pro Strecke erkannt. Ein Nutzer kann somit über ein Lücke in Springen und die Geste kann erkannt werden.

Lösung Problem 6

Die Reihenfolge der Pfadpunkte muss vom gemalten Pfad die selbe sein, wie die des Ausgangspfades. Mit der Problemlösung 1 erkennen wir ob die Pfadpunkte des gemalten Pfades nahe an die Ausgangspfadpunkte liegen. Es fehlt hierbei die Beachtung der Reihenfolge.

Die Lösung könnte erweitert werden mit einer Kontrolle die checkt ob eine Linie des gemalten Pfades sich mit der Außenhülle schneidet.

Problem 7

Es können falsche Geste erkannt werden, wenn diese Innerhalb liegen.

Lösung Problem 7

In der Problemlösung 6 wird die Reihenfolge der Punkte beachtet. Diese Lösung würde das Problem 7 mitlösen.

Problem 8

Es können nur Gesten erkannt werden die Proportional korrekt sind. Nur eine Stauchung ist nicht erlaubt.

Lösung Problem 8

Dieses Problem zeigt die Grenze der Idea 2 und kann nicht durch Erweiterung gelöst werden. Es wird ein neuer Ansatz benötigt und dieser wird in der Idea 3 beschrieben.

Idee 3

Die Ideen 1/2 checken ob der gemalte Pfad in einem Bereich liegt. In Problem 8 sieht man das Limit dieses Verfahren. Eine eventuelle Stauchung, Dehnung oder leichte Rotierung ist nicht erlaubt. Es wird eine universellere Lösung benötigt. Eine Geste ist eine folge von Strecken, die eine bestimmte länge und Richtung haben.

Wir können nun eine gemalte Strecke ablaufen und die Länge und Winkel einer Linie mit dem Ursprungspfad vergleichen. Wenn diese Werte nicht zu weit abweichen, gehört die Linie zum Ausgangspfad. Wenn alle Linien zum Ausgangspfad passen und alle Punkte des Ausgangspfad durchgangen sind, dann gehört der gemalte Pfad zum Ausgangspfad.

Calculate accuracy