Vectorize the image with a genetic algorithm.
So, on the weekends we should have a good time to rest, and therefore we will try to vectorize the image with a genetic algorithm.
Make a translucent polygon image as close as possible to the original.
First of all, I want to say that the use of a genetic algorithm in solving this problem has no practical use because of the very long execution time, and everything is done just for fun.
In connection with the approaching September at last, the picture of Dr. House was chosen as an example of the work of the program.
')
So the creation of Dr. House from a hundred decagon for 20 hours:
What will be the genes for this task? It turns out that these will be the coordinates of the points of the polygon (hereinafter, we will call it a polygon) and its color. We will not use crossing, only mutation (it is quite acceptable). The population, oddly enough, will consist of one individual, and this will be a picture with polygons traced on it.
The function of the device will be the sum of the colors errors of all pixels. Pixel error is defined as
R * R + G * G + B * B, where R is the difference between the red pixel component of the original image and the resulting one, G and B are green and blue. The smaller the value of the function, the smaller the error and the better picture we received.
Define the polygon point class:
The point has coordinates X and Y. The SetRandom procedure sets random coordinates to a point, according to the size of our image. Mutate procedure is divided into three parts, each of which is performed according to its given probability of loss. The first gives a chance to the point to move to any place in the picture. The second part moves the point to the average distance, then you will see that I have up to twenty pixels. The third part gives a chance to move a small distance, I have it up to three pixels.
Next comes the class of the brush responsible for the color of the polygon:
The brush has A , R , G , B color components. SetRandom initializes them with random values. In the Mutate procedure, each of the components may randomly change according to its probability of mutation.
Here we come to the polygon class:
Polygon includes an array of points and a brush (color). The SetRandom procedure initializes the brush, and also builds a minimum number of points around a randomly selected one. A mutation of a polygon is a mutation of a brush and each point of a polygon, and with some probability adding or deleting a point can occur. The Draw procedure draws our polygon.
Finally, the final main class is the workspace containing our polygons:
The truth of the IsChange property indicates that a mutation has occurred somewhere. SetRandom initializes the minimum starting polygon count. Mutate triggers a mutation for each polygon, and a polygon can be added or removed with a given probability. The Fitness function calculates the adaptation function, 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:
We initialize the new population and then make a copy and mutate it, calculate the adaptation function for the new population and, if it is less current (I remind you, the smaller the function value, the better), then we overwrite the current population with a new, better one.
We still have an auxiliary class where the settings are stored:
Here we store the width and height of the original image (initialized during loading), the minimum and maximum number of points in the polygon, the minimum and maximum number of polygons, the mutation probabilities for each component (one is one hundred percent mutation) and the distances that the point can move.
The entire project can be merged here .
UPD: thanks for the karma, transferred to the blog Algorithms.
Task
Make a translucent polygon image as close as possible to the original.
First of all, I want to say that the use of a genetic algorithm in solving this problem has no practical use because of the very long execution time, and everything is done just for fun.
Demonstration
In connection with the approaching September at last, the picture of Dr. House was chosen as an example of the work of the program.
')
So the creation of Dr. House from a hundred decagon for 20 hours:
Initial data
What will be the genes for this task? It turns out that these will be the coordinates of the points of the polygon (hereinafter, we will call it a polygon) and its color. We will not use crossing, only mutation (it is quite acceptable). The population, oddly enough, will consist of one individual, and this will be a picture with polygons traced on it.
The function of the device will be the sum of the colors errors of all pixels. Pixel error is defined as
R * R + G * G + B * B, where R is the difference between the red pixel component of the original image and the resulting one, G and B are green and blue. The smaller the value of the function, the smaller the error and the better picture we received.
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 coordinates X and Y. The SetRandom procedure sets random coordinates to a point, according to the size of our image. Mutate procedure is divided into three parts, each of which is performed according to its given probability of loss. The first gives a chance to the point to move to any place in the picture. The second part moves the point to the average distance, then you will see that I have up to twenty pixels. The third part gives a chance to move a small distance, I have it up to three pixels.
Next comes the class of the brush 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 color components. SetRandom initializes them with random values. In the Mutate procedure, each of the components may randomly change according to its probability of mutation.
Here we come to the polygon class:
[ Serializable ]
public class Polygon: ICloneable
{
public List <Point> Points { get ; set ; }
public Brush Brush { get ; set ; }
public void SetRandom()
{
Points = new List <Point>();
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(pX,pY)).ToArray();
g.FillPolygon(brush, points);
}
}
public object Clone()
{
Polygon newpolygon = new Polygon();
newpolygon.Brush = Brush.Clone() as Brush;
newpolygon.Points = new List <Point>();
Points.ForEach(p => newpolygon.Points.Add(p.Clone() as Point));
return newpolygon;
}
}
* This source code was highlighted with Source Code Highlighter .Polygon includes an array of points and a brush (color). The SetRandom procedure initializes the brush, and also builds a minimum number of points around a randomly selected one. A mutation of a polygon is a mutation of a brush and each point of a polygon, and with some probability adding or deleting a point can occur. The Draw procedure draws our polygon.
Finally, the final main class is the workspace containing our polygons:
[ Serializable ]
public class Workarea: ICloneable
{
public List <Polygon> Polygons { get ; set ; }
[XmlIgnore]
public bool IsChange { get ; set ; }
public void SetRandom()
{
Polygons = new List <Polygon>();
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 <Polygon>();
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 starting polygon count. Mutate triggers a mutation for each polygon, and a polygon can be added or removed with a given probability. The Fitness function calculates the adaptation function, 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 new population and then make a copy and mutate it, calculate the adaptation function for the new population and, if it is less current (I remind you, the smaller the function value, the better), then we overwrite the current population with a new, better one.
We still have an auxiliary 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 during loading), the minimum and maximum number of points in the polygon, the minimum and maximum number of polygons, the mutation probabilities for each component (one is one hundred percent mutation) and the distances that the point can move.
The entire project can be merged here .
UPD: thanks for the karma, transferred to the blog Algorithms.
Source: https://habr.com/ru/post/68323/
All Articles