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

Keine Kommentare:

Kommentar veröffentlichen