Saturday, May 10, 2014

Android: Pattern Recognition

After I explained in the previous post, how one can draw or write by hand in the app window, I now want to build up on this and explain how simple drawn patterns can be regonized.
First a bit about the theory: For pattern recognition numerous algorithms exist, I will here write about a procedure based on graph matching. It is relatively easy to implement, but also provides acceptable results for certain patterns. Therefor we will search the corner nodes of the pattern and then insert them into a graph. We will attribute them with length and angle of the incident lines. Then we try to match the resulting graph with the graph of the pattern to be checked and calculate a value for the similarity.

Let us start slowly with the code. The class Graph handles graphs, its list Nodes the nodes in the graph. On startup we create the patterns we want to recognize by adding the coordinates of the corner points as nodes and calling Finish() and NormLength(). Finish() iterates over all nodes and calculates the corresponding angles and lengths. Every node saves the distance to the predecessor node, which we simply calculate with Pythagoras. Furthermode every node saves the angle between precedessor, current node and successor. For this we represent the relative position of precedessor - current node (Left) and current node - successor (Right) as a vector, and then calculate the angle by the formula known from vector arithmetics: Angle = Arccos(Left * Right / |Left| * |Right|).
The function NormLength() norms the lengths saved in the nodes, since we want to recognize patterns and follow the idea, that for example a square is characterized by 4 equally long sides connected with 90° angles, but the actual size is irrelevant.

When drawing then a new graph is created, which describes the drawn pattern. In the function OnTouchEvent() for every point in the drawing path a new node in the current graph is created. The graph thus consists of (much too) many nodes. If the drawing is finished we call the function Process(). This tries to find the actual corners of the pattern and to delete all other nodes.
For this we iterate over all nodes and first delete all those, whose angle is under or over a specific value (I chose 155°, respectively 205°). By this nodes which roughly form a straight line are deleted.
After this nodes are deleted, which lie too close to their precedessor. If the user for example hovers over one point for too long, many nodes are created there which are very close together and because of this probably form very big angles.

After this cleanup the graph can be compared to the reference patterns. For this the nodes of the graph as well as those of the reference graph are iterated over and compared to each other. Each node of the reference graph forms the starting point of this iteration once, to recognize the pattern no matter from where the user started drawing. Then the iteration with the highest match is chosen. When comparing two nodes the ratio of the lenghts and angles is multiplied with eath other, for which I weigh the ratio of the angles as twice as important. If the number of nodes is not the same, the matching quality is reduced by half for every additional node.

In the example program I defined 4 patterns: Square, triangle, blitz and M. At every drawing the drawn pattern is compared to these patterns and the matching quality of all these is display at the top left as well as the name of the pattern which matches most.

Finally some annotations to this procedure: It is relatively good in recognizing simple, angular patterns. For circular structures it is not very fitting. One downside is also the predefined order of the nodes. Of course there can a lot be done with this, I tried to keep the code as simple as possible to explain the basics of pattern recognition. But of course I am, as always, happy about encouragement and criticism, especially about tips for optimization!

Edit: Of course to this also the corresponding code belongs, which I forgot when posting this the first time.

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

Here some screenshots:




For those who are interested to see this in action, I uploaded an experimental Android game using exactly this method.

No comments:

Post a Comment