Samstag, 10. Mai 2014

Android: Musterkennung

Nachdem ich im vorigen Post erklärt habe, wie man in das App Fenster malen bzw. schreiben kann, möchte ich nun darauf aufbauen und zeigen, wie man leichte gemalte Muster erkennen kann.
Zuerst kurz was zur Theorie: Zur Mustererkennung gibt es etliche Verfahren, ich habe mich hier für ein auf Graph - Matching basierendes Verfahren entschieden. Dieses ist nicht so schwer umzusetzen, liefert aber auch für nicht runde Muster schon ganz annehmbare Ergebnisse. Wir werden uns jeweils Eckpunkte des Musters heraussuchen und diese dann in einen Graph aufnehmen. Die Knoten dieses sind die Eckpunkte, wir attributieren sie jeweils mit Länge und Winkel der anliegenden Strecke. Dann versuchen wir den entstandenen Graph mit dem Graph des zu testenden Musters zu matchen und berechnen einen Wert für die Übereinstimmung.

Fangen wir langsam mit dem Code an. Die Klasse Graph verwaltet Graphen, ihre Liste Nodes die Knoten im Graphen. Bei Programmstart legen wir die zu erkennenden Muster an, in dem wir die Koordinaten der Eckpunkte als Knoten hinzufügen und anschließend die Funktionen Finish() und NormLength() aufrufen. Finish() durchläuft alle Knoten und berechnet die dazugehörigen Winkel und Längen. Jeder Knoten speichert die Entfernung zum Vorgängerknoten, was wir einfach mit Pythagoras ausrechnen. Außerdem speichert jeder Knoten den Winkel zwischen Vorgängerknoten, aktuellem Knoten und Nachfolgerknoten. Hierfür stellen wir die relative Position von Vorgängerknoten - aktueller Knoten (Left) und aktueller Knoten - Nachfolgerknoten (Right) als Vekor da, und berechnen den Winkel mit der aus der Vektorrechnung bekannten Formel Winkel = Arccos(Left * Right / (|Left| * |Right|).
Die Funktion NormLength() normiert die in den Knoten gespeicherten Längen, da wir Muster erkennen möchten und als Idee zugrunde legen, dass z.B. ein Quadrat durch 4 gleiche lange Seiten mit 90° Winkeln gekennzeichnet ist, die Größe des Quadrates aber irrelevant ist.

Beim Zeichnen dann wird ein neuer Graph angelegt, welcher das gezeichnete Muster beschreibt. In der Funktion OnTouchEvent() für jeden Punkt im Zeichenpfad ein neuer Knoten im aktuellen Graph angelegt. Der Graph besteht also aus (viel zu) vielen Knoten. Ist das Zeichnen beendet, rufen wir daher die Funktion Process() auf. Diese versucht die tatsächlichen Ecken des Musters zu finden und alle anderen Knoten zu löschen.
Hierzu werden alle Knoten durchlaufen und zuerst all diejenigen gelöscht, deren Winkel unter bzw. über einem bestimmten Wert liegen (ich habe 155° und 205°) genommen. Dadurch werden Punkte die in etwa auf einer Geraden liegen entfernt.
Daraufhin werden Knoten gelöscht, die zu nah an ihrem Vorgänger liegen. Auf diese Weise werden Knoten gelöscht, die in dichter Umgebung voneinander liegen. Wenn der Benutzer z.B. lange auf einem Punkt beim Zeichnen verweilt, entstehen dort viele Knoten, die sehr nah beinander liegen und dadurch eventuell sehr große Winkel haben.

Nach der Bereinigung des Graphen kann dieser mit den vordefinierten Vergleichsmustern verglichen werden. Dazu werden die Knoten des gezeichneten Graphens sowie des Vergleichsgraphen der Reihe nach durchlaufen und miteinander verglichen. Jeder Knoten des Vergleichsgraphen ist einmal Startpunkt des Durchlaufs, um unabhängig vom Startpunkt des Zeichnens das Muster zu erkennen. Dann wird der Durchlauf mit der größten Übereinstimmung genommen. Bei dem Vergleich zweier Knoten wird eine Zahl zwischen 0 und 1 zurückgegeben, mit der die aktuelle Matchgenauigkeit (anfänglich beträgt sie 100) multipliziert wird. Beim Vergleich zweier Knoten wird das Verhältnis der beiden Längen mit dem Verhältnis der beiden Winkel multipliziert, wobei ich das Verhältnis der Winkel doppelt bewerte. Stimmt die Anzahl der Knoten nicht überein, wird die Matchgenauigkeit für jeden überschüssigen Knoten halbiert.

Dem Beispielprogramm habe ich 4 Muster vordefiniert: Quadrat, Dreieck, Blitz und M. Bei jedem Zeichnen wird das gezeichnete Muster mit diesen verglichen und die Übereinstimmung mit einem von diesem oben links angezeigt sowie der Name des am ehesten passendsten Musters.

Am Schluss noch ein paar Anmerkungen zu diesem Verfahren: Es eignet sich relativ gut zur Erkennung von einfachen, eckigen Mustern. Für runde Strukturen ist das Verfahren nicht gut geeignet. Ein Manko ist auch die festgelegte Reihenfolge der Knoten. Natürlich lässt sich noch sehr viel damit machen, den Code habe ich so einfach wie möglich versucht zu halten um die Grundlagen der Mustererkennung zu zeigen. Aber ich freue mich natürlich auch, wie immer, über Anregungen und Kritik, insbesondere über Optimierungstipps!
Nachtrag: Natürlich gehört hier noch der Code hin, den ich beim ersten Posten vergessen hatte.

MainActivity.cs:
using System;
using Android.App;
using Android.Content;
using Android.Runtime;
using Android.Views;
using Android.Widget;
using Android.OS;

namespace PatternRecognizer
{
     [Activity (Label = "PatternRecognizer", MainLauncher = true)]
     public class MainActivity : Activity
     {
          protected override void OnCreate (Bundle bundle)
          {
               base.OnCreate (bundle);
               DrawView test = new DrawView(this);
               test.start ();
               SetContentView (test);
          }
     }
}

DrawView.cs:
using System;
using Android.Views;
using Android.Graphics;
using System.Collections.Generic;
using Android.Content;
using Java.Lang;

namespace PatternRecognizer
{
     public class DrawView : View
     {
          public DrawView (Context context) : base (context)
          {

          }

          private Path drawPath;
          private Paint drawPaint, canvasPaint;
          private uint paintColor = 0xFF660000;
          private Canvas drawCanvas;
          private Bitmap canvasBitmap;

          class Vector
          {
               public float x;
               public float y;

               public Vector (float _x, float _y)
               {
                    x = _x;
                    y = _y;
               }

               public float Abs ()
               {
                    return (float)System.Math.Sqrt (System.Math.Pow (x, 2) + System.Math.Pow (y, 2));
               }

               public float ScalProd (Vector v1, Vector v2)
               { // später static
                    return (v1.x * v2.x + v1.y * v2.y);
               }
          }

          public class Node
          {
               public float Angle;
               public float Length;
               public float x;
               public float y;

               public Node (float _x, float _y)
               {
                    x = _x;
                    y = _y;
               }

               public Node (float _x, float _y, float length, float angle)
               {
                    x = _x;
                    y = _y;
                    Length = length;
                    Angle = angle;
               }

               public float DistanceFrom (Node other)
               {
                    return (float)System.Math.Sqrt (System.Math.Pow (x - other.x, 2)
                    + System.Math.Pow (y - other.y, 2));
               }

               public void SetAngle (Node prev, Node next)
               {

                    Vector Left = new Vector (x - prev.x, y - prev.y);
                    Vector Right = new Vector (x - next.x, y - next.y);
                    Angle = (float)Java.Lang.Math.ToDegrees (System.Math.Acos (Left.ScalProd (Left, Right)
                    / (Left.Abs () * Right.Abs ())));
               }

               public float Resemblance (Node test)
               {
                    float LengthR = System.Math.Abs (test.Length / Length);
                    float AngleR = System.Math.Abs ((test.Angle + 0.5f) / (Angle + 0.5f));
                    if (LengthR > 1)
                         LengthR = 1 / LengthR;
                    if (AngleR > 1)
                         AngleR = 1 / AngleR;
                    AngleR *= 2;
                    if (AngleR > 1)
                         AngleR = 1;
                    return System.Math.Abs (LengthR * AngleR);
               }
          }

          public class Graph
          {
               public Graph DeepCopy ()
               {
                    Graph Result = new Graph ();
                    Result.Nodes = new List<Node> ();
                    for (int i = 0; i < Nodes.Count; i++) {
                         Result.Nodes.Add (new Node (Nodes [i].x, Nodes [i].y, Nodes [i].Length, Nodes [i].Angle));
                    }
                    return Result;
               }

               public Graph ()
               {
                    Nodes = new List<Node> ();
               }

               public void Reset ()
               {
                    Nodes = new List<Node> ();
               }

               public Graph CreateSquare ()
               {
                    Graph Square = new Graph ();
                    Square.Nodes.Add (new Node (0, 0));
                    Square.Nodes.Add (new Node (1, 0));
                    Square.Nodes.Add (new Node (1, 1));
                    Square.Nodes.Add (new Node (0, 1));
                    Square.Finish();
                    Square.NormLength ();
                    return Square;
               }

               public Graph CreateTri ()
               {
                    Graph Tri = new Graph ();
                    Tri.Nodes.Add (new Node (0.5f, 0));
                    Tri.Nodes.Add (new Node (0, 1));
                    Tri.Nodes.Add (new Node (1, 1));
                    Tri.Finish();
                    Tri.NormLength ();

                    return Tri;
               }

               public Graph CreateM ()
               {
                    Graph Octa = new Graph ();

                    Octa.Nodes.Add (new Node (0, 1));
                    Octa.Nodes.Add (new Node (1, 0));
                    Octa.Nodes.Add (new Node (2, 1));
                    Octa.Nodes.Add (new Node (3, 0));
                    Octa.Nodes.Add (new Node (4, 1));

                    Octa.Finish();
                    Octa.NormLength ();

                    return Octa;
               }

               public Graph CreateBlitz ()
               {
                    Graph Pattern = new Graph ();

                    Pattern.Nodes.Add (new Node (1, 0));
                    Pattern.Nodes.Add (new Node (0, 2));
                    Pattern.Nodes.Add (new Node (1, 2));
                    Pattern.Nodes.Add (new Node (0, 4));

                    Pattern.Finish();
                    Pattern.NormLength ();

                    return Pattern;
               }

               Graph Square;
               Graph Tri;
               Graph M;
               Graph Blitz;

               public void Init ()
               {
                    Square = CreateSquare ();
                    Tri = CreateTri ();
                    M = CreateM ();
                    Blitz = CreateBlitz ();
               }

               float LowerBound = 155;
               float UpperBound = 205;
               public List<Node> Nodes = new List<Node> ();

               public double Check (Graph origpattern, Graph origtest)
               {
                    double MaxMatch = 0;

                    if (origtest.Nodes.Count >= origpattern.Nodes.Count) {
                         for (int i = 0; i < origtest.Nodes.Count; i++) {
                              double Match = 100;
                              Graph test = origtest.DeepCopy ();
                              for (int j = 0; j < test.Nodes.Count; j++) {
                                   if (j >= origpattern.Nodes.Count) {
                                        Match *= 0.5;
                                        continue;
                                   }
                                   double TempMatch1 = test.Nodes [((j + i) % test.Nodes.Count)].Resemblance (
                                                            origpattern.Nodes [((j) % origpattern.Nodes.Count)
                                                            ]);
                                            
                                   Match *= TempMatch1;
                              }
                              if (Match > MaxMatch)
                                   MaxMatch = Match;
                         }
                    } else {
                         for (int i = 0; i < origpattern.Nodes.Count; i++) {
                              double Match = 100;

                              Graph pattern = origpattern.DeepCopy ();
                              for (int j = 0; j < origpattern.Nodes.Count; j++) {
                                   if (j >= origtest.Nodes.Count) {
                                        Match *= 0.5;
                                        continue;
                                   }
                                   double TempMatch1 = pattern.Nodes [((j + i) % pattern.Nodes.Count)].Resemblance (
                                                            origtest.Nodes [((j) % origtest.Nodes.Count)]);


                                   Match *= TempMatch1;

                              }
                              if (Match > MaxMatch)
                                   MaxMatch = Match;
                         }
                    }
                    return MaxMatch;
               }

               public double[] Matchings;

               public void Finish ()
               {
                         for (int i = 0; i < Nodes.Count; i++) {
                              Node NextNode;
                              Node PrevNode;
                              if (i == Nodes.Count - 1)
                                   NextNode = Nodes [(0)];
                              else
                                   NextNode = Nodes [(i + 1)];
                              if (i == 0)
                                   PrevNode = Nodes [(Nodes.Count - 1)];
                              else
                                   PrevNode = Nodes [(i - 1)];

                              Vector Left = new Vector (Nodes [(i)].x - PrevNode.x,
                                                 Nodes [i].y - PrevNode.y);
                              Vector Right = new Vector (Nodes [i].x - NextNode.x,
                                                  Nodes [i].y - NextNode.y);

                              Nodes [i].Length = (float)System.Math.Sqrt (System.Math.Pow (NextNode.x
                              - Nodes [i].x, 2)
                              + System.Math.Pow (NextNode.y - Nodes [i].y, 2));
                              Nodes [i].Angle = (float)Java.Lang.Math.ToDegrees (System.Math.Acos (Left
                              .ScalProd (Left, Right) / (Left.Abs () * Right.Abs ())));
                         }
               }

               public void NormLength ()
               {
                    float Length = 0;
                    for (int i = 0; i < Nodes.Count; i++) {
                         Length += Nodes [i].Length;
                    }

                    for (int i = 0; i < Nodes.Count; i++) {
                         Nodes [i].Length = Nodes [i].Length / Length;
                    }
               }

               public void Process ()
               {
                    Finish();

                    bool NodesDeleted = true;

                    while (NodesDeleted) {
                         NodesDeleted = false;
                         for (int i = 0; i < Nodes.Count; i++) {
                              if (Nodes.Count <= 2)
                                   break;
                              Node PrevNode;

                              if (i == 0)
                                   PrevNode = Nodes [Nodes.Count - 1];
                              else
                                   PrevNode = Nodes [i - 1];

                              if (Nodes [i].Angle > LowerBound
                                 && Nodes [i].Angle < UpperBound) {

                                   Nodes [((i - 1 + Nodes.Count) % Nodes.Count)].SetAngle (Nodes [((i - 2 + Nodes.Count) % Nodes.Count)], Nodes [((i + 1) % Nodes.Count)]);
                                   PrevNode.Length += Nodes [i].Length;

                                   Nodes.RemoveAt (i);
                                   i--;
                                   NodesDeleted = true;
                              }
                         }
                          
                         bool CloseCorner = false;

                         for (int i = 0; i < Nodes.Count; i++) {
                              if (Nodes.Count <= 2)
                                   break;

                              if (Nodes.Count == 1)
                                   break;
                              Node PrevNode;
                              Node NextNode;

                              if (i == 0)
                                   PrevNode = Nodes [(Nodes.Count - 1)];
                              else
                                   PrevNode = Nodes [(i - 1)];
                              if (Nodes [(i)].DistanceFrom (PrevNode) < 30) {
                                   if (Nodes [(i)].Angle > LowerBound
                                      && Nodes [(i)].Angle < UpperBound && !CloseCorner) {
                                        CloseCorner = true;
                                   } else {

                                        Node PrevPrevNode;

                                        if (i <= 1)
                                             PrevPrevNode = Nodes [(Nodes.Count - (2 - i))];
                                        else
                                             PrevPrevNode = Nodes [(i - 2)];
                                        if (i >= Nodes.Count - 2)
                                             NextNode = Nodes [(0 + (Nodes.Count - 1 - i))];
                                        else
                                             NextNode = Nodes [(i + 2)];

                                        PrevNode.Length += Nodes [(i)].DistanceFrom (PrevNode)
                                        + Nodes [(i)].Length;
                                        PrevNode.SetAngle (PrevPrevNode, NextNode);

                                        Nodes [((i - 1 + Nodes.Count) % Nodes.Count)].SetAngle (Nodes [((i - 2 + Nodes.Count) % Nodes.Count)], Nodes [((i + 1) % Nodes.Count)]);

                                        Nodes.RemoveAt (i);
                                        i = -1;

                                        NodesDeleted = true;
                                   }
                              } else
                                   CloseCorner = false;
                         }
                    }
                    NormLength ();

                    Matchings = new double[4];
                    Matchings [0] = Check (Square, this);
                    Matchings [1] = Check (Tri, this);
                    Matchings [2] = Check (Blitz, this);
                    Matchings [3] = Check (M, this);
               }
          }

          public void start ()
          {
               drawPath = new Path ();
               drawPaint = new Paint ();
               drawPaint.Color = new Color ((int)paintColor);
               drawPaint.AntiAlias = true;
               drawPaint.StrokeWidth = 20;
               drawPaint.SetStyle (Paint.Style.Stroke);
               drawPaint.StrokeJoin = Paint.Join.Round;
               drawPaint.StrokeCap = Paint.Cap.Round;
               canvasPaint = new Paint ();
               canvasPaint.Dither = true;
               Pattern = new Graph ();
               Pattern.Init ();
          }

          protected override void OnSizeChanged (int w, int h, int oldw, int oldh)
          {
               base.OnSizeChanged (w, h, oldw, oldh);
               canvasBitmap = Bitmap.CreateBitmap (w, h, Bitmap.Config.Argb8888);
               drawCanvas = new Canvas (canvasBitmap);
          }

          protected override void OnDraw (Canvas canvas)
          {
               canvas.DrawBitmap (canvasBitmap, 0, 0, canvasPaint);
               canvas.DrawPath (drawPath, drawPaint);
      

               if (Pattern != null) {
                    for (int i = 0; i < Pattern.Nodes.Count; i++) {

                         Paint myPaint = new Paint ();

                         myPaint.Color = Color.Rgb (0, 40 * (i + 1), 0);
                         canvas.DrawRect (Pattern.Nodes [i].x, Pattern.Nodes [i].y,
                              Pattern.Nodes [i].x + 10,
                              Pattern.Nodes [i].y + 10, myPaint);
                         Paint myPaint2 = new Paint ();
                         myPaint2.TextSize = 30;
                         myPaint2.Color = Color.Rgb (100, 255, 255);
                         canvas.DrawText (i.ToString (), Pattern.Nodes [i].x, Pattern.Nodes [i].y + 20, myPaint2);
                    }
               }

               if (Pattern != null) {
                    Paint myPaint = new Paint ();
                    myPaint.TextSize = 30;
                    myPaint.Color = Color.Rgb (100, 255, 255);

                    int MaxIndex = 0;
                    double MaxMatch = 0;

                    if (Pattern.Matchings != null) {
                         for (int i = 0; i < Pattern.Matchings.Length; i++) {
                              canvas.DrawText (Pattern.Matchings [i].ToString (), 100, 100 * (i + 1), myPaint);
                              if (Pattern.Matchings [i] > MaxMatch) {
                                   MaxMatch = Pattern.Matchings [i];
                                   MaxIndex = i;
                              }
                         }

                         string Shape = "";

                         switch (MaxIndex) {
                         case 0:
                              Shape = "Square";
                              break;
                         case 1:
                              Shape = "Triangle";
                              break;
                         case 2:
                              Shape = "Blitz";
                              break;
                         case 3:
                              Shape = "M";
                              break;
                         default:
                              break;
                         }

                         canvas.DrawText (Shape, 100, 900, myPaint);
                    }
               }
          }

          Graph Pattern = null;

          public override  bool OnTouchEvent (MotionEvent e)
          {
               float touchX = e.GetX ();
               float touchY = e.GetY ();
               switch (e.Action) {
               case MotionEventActions.Down:
                    drawPath.MoveTo (touchX, touchY);
                    Pattern.Reset ();
                    Pattern.Nodes.Add (new Node (touchX, touchY));
                    break;
               case MotionEventActions.Move:
                    drawPath.LineTo (touchX, touchY);
                    if (Pattern == null)
                         Pattern = new Graph ();
                    Pattern.Nodes.Add (new Node (touchX, touchY));
                    break;
               case MotionEventActions.Up:
                    drawCanvas.DrawPath (drawPath, drawPaint);
                    Pattern.Process ();
                    drawPath.Reset ();

                    break;
               default:
                    return false;
               }
    

               Invalidate ();
               return true;
          }
     }
}

Hier ein paar Screenshots:




Wer Interesse hat, die Erkennung in Action zu sehen, zum Ausprobieren habe ich ein Android Spiel online gestellt, welches genau diese Methode verwendet.

Keine Kommentare:

Kommentar veröffentlichen