Sonntag, 18. Mai 2014

Alle Permutationen erzeugen

Oft musste ich beim Programmieren alle Permutationen einer bestimmten Menge finden und ausgeben. Deshalb möchte ich heute eine, wie ich finde, schnelle und elegante Methode dafür vorstellen.
Diese erwartet als Parameter eine Liste von int Werten, und gibt dann alle möglichen Permutationen dieser aus. Der Parameter int der Liste lässt sich aber durch einen beliebigen anderen Datentyp ersetzen.
Das Erzeugen der Permutationen funktioniert rekursiv. Der aktuell erzeugte Teil der Permutation wird als Liste gespeichert, in jedem Schritt wird dieser ein Element hinzugefügt und dieses aus der Liste der verbleibenden Elemente entfernt. Sind keine Elemente mehr vorhanden, wird die aktuelle Liste in die Liste der fertigen Permutationen aufgenommen.
Der Code für diese Funktion sieht so aus:

public void RecCreatePermutation(List<int> current, List<int> elements)
{
    for (int i = 0; i < elements.Count; i++)
    {
        List<int> NewCurrent = Copy(current);
        List<int> NewElements = Copy(elements);
        NewCurrent.Add(elements[i]);
        NewElements.RemoveAt(i);
        if (NewElements.Count == 0)
        {
            Permutations.Add(NewCurrent);
        }
        else
            RecCreatePermutation(NewCurrent, NewElements);
    }
}
Wie man sieht, wird jeweils eine Funktion Copy() aufgerufen. Das ist deshalb nötig, weil Listen in C# Verweistypen sind (für eine genaue Erklärung siehe hier) - so würde das Ändern der Liste in einem Aufruf auch die Liste in allen anderen Aufrufen mit dieser Liste ändern.
Der komplette Code sollte selbsterklärend sein und sieht so aus:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CreatePermutations
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            List<int> Elements = new List<int>();
            for (int i = 0; i < 5; i++)
            {
                Elements.Add(i);

            }
           List<List<int>> Perms = CreatePermutation(Elements);
        }

        List<List<int>> Permutations;
        public List<List<int>> CreatePermutation(List<int> elements)
        {
            Permutations = new List<List<int>>();
            RecCreatePermutation(new List<int>(), elements);
            return Permutations;
        }

        private List<int> Copy(List<int> dummy)
        {
            List<int> Result = new List<int>();
            foreach (int i in dummy)
                Result.Add(i);
            return Result;
        }

        public void RecCreatePermutation(List<int> current, List<int> elements)
        {
            for (int i = 0; i < elements.Count; i++)
            {
                List<int> NewCurrent = Copy(current);
                List<int> NewElements = Copy(elements);
                NewCurrent.Add(elements[i]);
                NewElements.RemoveAt(i);
                if (NewElements.Count == 0)
                {
                    Permutations.Add(NewCurrent);
                }
                else
                    RecCreatePermutation(NewCurrent, NewElements);
            }
        }
    }
}

Mittwoch, 14. Mai 2014

Musterkennung mit C#

Im vorigen Post habe ich die Grundlagen von maschineller Musterkennung unter Verwendung eines Graph Matching Verfahrens erläutert.
Dieses haben wir dann in einer Android App angewandt, in welcher der Benutzer mit dem Finger auf den Bildschirm malen kann, diese Zeichnung wird dann an den Mustererkennung Algorithmus geschickt.
Nun ist es natürlich ein leichtes, dieses Prinzip in Visual Studio zu übertragen, der Vollständigkeit möchte ich aber trotzdem darüber posten.
Der Code der für die Musterkennung zuständigen Klassen bleibt nahezu gleich, lediglich der Code für das Interface muss geändert werden. Hierfür verwenden wir eine PictureBox, in welcher bei Maus Events das Zeichnen realisiert wird.
Ich denke, der vorige Post sollte auch diese Anwendung verständlich machen, deswegen hier einfach direkt der Code:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace PatternRecognizer
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            Pattern.Init();
        }

        Graph Pattern = new Graph();

        private void pictureBox1_MouseMove(object sender, MouseEventArgs e)
        {
            if (e.Button == System.Windows.Forms.MouseButtons.Left)
            {
                Pattern.Nodes.Add(new Node(e.X, e.Y));
                pictureBox1.Refresh();
            }
        }

        private void pictureBox1_Paint(object sender, PaintEventArgs e)
        {
            if (Pattern != null)
            {
                for (int i = 0; i < Pattern.Nodes.Count; i++)
                {
                    e.Graphics.DrawString(i.ToString(), new Font("Arial", 6), new SolidBrush(Color.Red), Pattern.Nodes[i].x, Pattern.Nodes[i].y);
                    if (i >= 1)
                    {
                        e.Graphics.DrawLine(new Pen(new SolidBrush(Color.Red)), Pattern.Nodes[i - 1].x, Pattern.Nodes[i - 1].y, Pattern.Nodes[i].x, Pattern.Nodes[i].y);
                    }
                }
            }

            if (Pattern != null)
            {
                int MaxIndex = 0;
                double MaxMatch = 0;

                if (Pattern.Matchings != null)
                {
                    for (int i = 0; i < Pattern.Matchings.Length; i++)
                    {
                        e.Graphics.DrawString(Pattern.Matchings[i].ToString(), new Font("Arial", 8), new SolidBrush(Color.Red), 10, 20 * (i + 1));
                        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;
                    }

                    e.Graphics.DrawString(Shape, new Font("Arial", 12),  new SolidBrush(Color.Red), 10, 120);
                }
            }
        }

        private void pictureBox1_MouseUp(object sender, MouseEventArgs e)
        {
            Pattern.Process();
            pictureBox1.Refresh();
        }

        private void pictureBox1_MouseDown(object sender, MouseEventArgs e)
        {
            Pattern.Reset();
        }
    }

    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)
        {
            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));
        }

        private double ToDegrees(double rad)
        {
            return (rad / (2 * Math.PI) * 360);
        }

        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)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)ToDegrees(System.Math.Acos(Left
                .ScalProd(Left, Right) / (Left.Abs() * Right.Abs())));
            }
        }

        private double ToDegrees(double rad)
        {
            return (rad / (2 * Math.PI) * 360);
        }

        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);
        }
    }
}

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.