Wednesday, May 14, 2014

Pattern Recognition in C#

In the previous post I explained the basics of automatic pattern recognition using a graph matching procedure.
This we then applied in an Android app, in which the user can draw on the screen, this drawing is then send to the algorithm for pattern recognition.
Of course it is now an easy task to port this principle to Visual Studio, for the sake of completeness I still want to post about this though.
The code of the classes responsible for pattern recognition stays nearly identical, only the code for the interface changes. For this we use a PictureBox, in which is drawn in mouse events.
I think the previous post should also make this application clear, therefor here simply directly the 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);
        }
    }
}

No comments:

Post a Comment