Vectorize the image with a genetic algorithm

    So, on the weekend we should have fun, and therefore try to vectorize the image with a genetic algorithm.
    Vectorized Dr. House

    Task


    Make the image as translucent as possible from the translucent polygons.

    First of all, I want to say that the use of a genetic algorithm in solving this problem does not have practical benefits because of the very long lead time, and everything is done just for fun.

    Demonstration


    In connection with finally approaching September, a picture of Dr. House was chosen as an example of the program .

    So the creation of Dr. House of one hundred decagons in 20 hours:


    Initial data


    What will be genes for this task? It turns out that these will be the coordinates of the points of the polygon (hereinafter we will call it the polygon) and its color. We will not use crossbreeding, only a mutation (this is completely acceptable). Strange as it may seem, the population will consist of one individual, and this will be a picture with polygons drawn on it.

    The function of the device will be the sum of the color errors of all pixels. The error for the pixel is defined as
    R * R + G * G + B * B, where R is the difference between the red component of the pixel of the original image and the resulting, G and B - green and blue. The smaller the value of the function, the smaller the error and the better picture we get.

    The code


    Define the polygon point class:
        [Serializable]
        public class Point: ICloneable
        {
            public int X { get; set; }
            public int Y { get; set; }

            public void SetRandom()
            {
                X = Helper.Rand.Next(0, Helper.Width);
                Y = Helper.Rand.Next(0, Helper.Height);
            }

            public void Mutate(Workarea workarea)
            {
                if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveMaxChance)
                {
                    SetRandom();
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveMiddleChance)
                {
                    X = Math.Min(Math.Max(0, X + Helper.Rand.Next(-Helper.MiddleRange, Helper.MiddleRange + 1)), Helper.Width);
                    Y = Math.Min(Math.Max(0, Y + Helper.Rand.Next(-Helper.MiddleRange, Helper.MiddleRange + 1)), Helper.Height);
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationPointMoveNearChance)
                {
                    X = Math.Min(Math.Max(0, X + Helper.Rand.Next(-Helper.NearRange, Helper.NearRange + 1)), Helper.Width);
                    Y = Math.Min(Math.Max(0, Y + Helper.Rand.Next(-Helper.NearRange, Helper.NearRange + 1)), Helper.Height);
                    workarea.IsChange = true;
                }
            }

            public object Clone()
            {
                return new Point { X = X, Y = Y };
            }
        }

    * This source code was highlighted with Source Code Highlighter.

    The point has X and Y coordinates . The SetRandom procedure sets the point random coordinates according to the size of our picture. The Mutate procedure is divided into three parts, each of which is performed according to its predetermined probability of loss. The first gives the chance to the point to move anywhere in the picture. The second part moves the point to the average distance, then you will see that I have it up to twenty pixels. The third part gives a chance to move a small distance, I have it up to three pixels.

    Next is the brush class that is responsible for the color of the polygon:
        [Serializable]
        public class Brush: ICloneable
        {
            public int A { get; set; }
            public int R { get; set; }
            public int G { get; set; }
            public int B { get; set; }

            public void SetRandom()
            {
                A = Helper.Rand.Next(30, 60);
                R = Helper.Rand.Next(0, 256);
                G = Helper.Rand.Next(0, 256);
                B = Helper.Rand.Next(0, 256);
            }

            public void Mutate(Workarea workarea)
            {
                if (Helper.Rand.NextDouble() <= Helper.MutationBrushAChance)
                {
                    A = Helper.Rand.Next(30, 60);
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationBrushRChance)
                {
                    R = Helper.Rand.Next(0, 256);
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationBrushGChance)
                {
                    G = Helper.Rand.Next(0, 256);
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationBrushBChance)
                {
                    B = Helper.Rand.Next(0, 256);
                    workarea.IsChange = true;
                }
            }

            public object Clone()
            {
                return new Brush
                {
                    A = A,
                    R = R,
                    G = G,
                    B = B
                };
            }
        }

    * This source code was highlighted with Source Code Highlighter.

    The brush has A , R , G , B component colors. SetRandom initializes them with random values. In the Mutate procedure, each of the components can randomly change according to its probability of a mutation.

    So we come to the class of the polygon:
        [Serializable]
        public class Polygon: ICloneable
        {
            public List Points { get; set; }
            public Brush Brush { get; set; }

            public void SetRandom()
            {
                Points = new List();

                Point center = new Point();
                center.SetRandom();

                for (int i = 0; i < Helper.MinPointsPerPolygon; i++)
                {
                    Point point = new Point();
                    point.X = Math.Min(Math.Max(0, center.X + Helper.Rand.Next(-3, 4)), Helper.Width);
                    point.Y = Math.Min(Math.Max(0, center.X + Helper.Rand.Next(-3, 4)), Helper.Height);
                    Points.Add(point);
                }

                Brush = new Brush();
                Brush.SetRandom();
            }

            public void Mutate(Workarea workarea)
            {
                if (Helper.Rand.NextDouble() <= Helper.MutationPolygonAddPointChance)
                {
                    AddPoint();
                    workarea.IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationPolygonDelPointChance)
                {
                    DelPoint();
                    workarea.IsChange = true;
                }

                Brush.Mutate(workarea);
                Points.ForEach(p => p.Mutate(workarea));
            }

            private void AddPoint()
            {
                if (Points.Count < Helper.MaxPointsPerPolygon)
                {
                    Point point = new Point();
                    int index = Helper.Rand.Next(1, Points.Count - 1);
                    Point p1 = Points[index - 1];
                    Point p2 = Points[index];
                    point.X = (p1.X + p2.X) / 2;
                    point.Y = (p1.Y + p2.Y) / 2;
                    Points.Insert(index, point);
                }
            }

            private void DelPoint()
            {
                if (Points.Count > Helper.MinPointsPerPolygon)
                {
                    int index = Helper.Rand.Next(0, Points.Count);
                    Points.RemoveAt(index);
                }
            }

            public void Draw(Graphics g)
            {
                using (SolidBrush brush = new SolidBrush(Color.FromArgb(Brush.A, Brush.R, Brush.G, Brush.B)))
                {
                    System.Drawing.Point[] points = Points.Select(p => new System.Drawing.Point(p.X,p.Y)).ToArray();
                    g.FillPolygon(brush, points);
                }
            }

            public object Clone()
            {
                Polygon newpolygon = new Polygon();
                newpolygon.Brush = Brush.Clone() as Brush;
                newpolygon.Points = new List();
                Points.ForEach(p => newpolygon.Points.Add(p.Clone() as Point));
                return newpolygon;
            }
        }

    * This source code was highlighted with Source Code Highlighter.

    The polygon includes an array of points and a brush (color). The SetRandom procedure initializes the brush and also draws a minimum number of points around a randomly selected one. A polygon mutation is a mutation of a brush and each point of a polygon, and also with some probability, some point can be added or deleted. The Draw procedure draws our polygon.

    And finally, the final main class is a workspace containing our polygons:
        [Serializable]
        public class Workarea: ICloneable
        {
            public List Polygons { get; set; }

            [XmlIgnore]
            public bool IsChange { get; set; }

            public void SetRandom()
            {
                Polygons = new List();

                for (int i = 0; i < Helper.MinPolygons; i++)
                {
                    AddPolygon();
                }

                IsChange = true;
            }

            public void Mutate()
            {
                if (Helper.Rand.NextDouble() <= Helper.MutationWorkareaAddPolygonChance)
                {
                    AddPolygon();
                    IsChange = true;
                }

                if (Helper.Rand.NextDouble() <= Helper.MutationWorkareaDelPolygonChance)
                {
                    DelPolygon();
                    IsChange = true;
                }

                Polygons.ForEach(p => p.Mutate(this));
            }

            private void AddPolygon()
            {
                if (Polygons.Count < Helper.MaxPolygons)
                {
                    Polygon polygon = new Polygon();
                    polygon.SetRandom();
                    Polygons.Add(polygon);
                }
            }

            private void DelPolygon()
            {
                if (Polygons.Count > Helper.MinPolygons)
                {
                    int index = Helper.Rand.Next(0, Polygons.Count);
                    Polygons.RemoveAt(index);
                }
            }

            public double Fitness(Color[,] colors)
            {
                double fitness = 0;
                Bitmap img = Draw();
                FastBitmap fastimg = new FastBitmap(img);
                for (int i = 0; i < Helper.Width; i++)
                {
                    for (int j = 0; j < Helper.Height; j++)
                    {
                        Color c1 = fastimg.GetPixel(i, j);
                        Color c2 = colors[i, j];
                        int r = c1.R - c2.R;
                        int g = c1.G - c2.G;
                        int b = c1.B - c2.B;
                        fitness += r * r + g * g + b * b;
                    }
                }
                fastimg.Release();
                img.Dispose();
                return fitness;
            }

            public Bitmap Draw()
            {
                Bitmap img = new Bitmap(Helper.Width, Helper.Height);
                using (Graphics g = Graphics.FromImage(img))
                {
                    g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;
                    g.Clear(Color.Black);

                    Polygons.ForEach(p => p.Draw(g));
                }
                return img;
            }

            public object Clone()
            {
                Workarea newarea = new Workarea();
                newarea.Polygons = new List();
                Polygons.ForEach(p => newarea.Polygons.Add(p.Clone() as Polygon));
                return newarea;
            }
        }

    * This source code was highlighted with Source Code Highlighter.

    The truth of the IsChange property indicates that a mutation has occurred somewhere. SetRandom initializes the minimum initial number of polygons. Mutate triggers a mutation for each polygon, and the polygon can be added or removed with a given probability. Function Fitness calculates the function of the device, it is passed an array of colors of the original image. Well, the Draw function returns our rendered image.

    The algorithm itself looks like this:
            private void Start()
            {
                if (workarea == null)
                {
                    workarea = new Workarea();
                    workarea.SetRandom();
                }

                while (isRunning)
                {
                    Workarea newarea;
                    lock (workarea)
                    {
                        newarea = workarea.Clone() as Workarea;
                    }
                    newarea.Mutate();

                    if (newarea.IsChange)
                    {
                        double newfitness = newarea.Fitness(sourceColors);

                        if (newfitness <= fitness)
                        {
                            lock (workarea)
                            {
                                workarea = newarea;
                            }
                            fitness = newfitness;
                        }
                    }
                }
            }

    * This source code was highlighted with Source Code Highlighter.

    We initialize the initial population, then make a copy and mutate it, calculate the adaptation function for the new population and, if it is less than the current one (I remind you, the lower the value of the function, the better), then we overwrite the current population with a new, better one.

    We still have a helper class where the settings are stored:
        public static class Helper
        {
            public static readonly Random Rand = new Random();

            public static int Width = 0;
            public static int Height = 0;

            public static int MinPointsPerPolygon = 3;
            public static int MaxPointsPerPolygon = 10;

            public static int MinPolygons = 0;
            public static int MaxPolygons = 100;

            public static int NearRange = 3;
            public static int MiddleRange = 20;
            
            public static double MutationPointMoveMaxChance = 0.0007;
            public static double MutationPointMoveMiddleChance = 0.0007;
            public static double MutationPointMoveNearChance = 0.0007;
            
            public static double MutationBrushAChance = 0.0007;
            public static double MutationBrushRChance = 0.0007;
            public static double MutationBrushGChance = 0.0007;
            public static double MutationBrushBChance = 0.0007;
            
            public static double MutationPolygonAddPointChance = 0.0007;
            public static double MutationPolygonDelPointChance = 0.0007;
            
            public static double MutationWorkareaAddPolygonChance = 0.0014;
            public static double MutationWorkareaDelPolygonChance = 0.0007;
        }

    * This source code was highlighted with Source Code Highlighter.

    Here we store the width and height of the original image (initialized when loading), the minimum and maximum number of points in the polygon, the minimum and maximum number of polygons, the mutation probabilities for each component (unit - 100% mutation) and the distance that a point can move.
    The entire project can be merged here .

    UPD: thanks for the karma, transferred to the blog Algorithms.

    Also popular now: