Итак, на выходных мы должны весело отдохнуть, а потому попробуем векторизовать изображение генетическим алгоритмом.
Сделать из полупрозрачных многоугольников изображение максимально похожее на оригинал.
Прежде всего хочу сказать, что использование генетического алгоритма в решении этой задачи не имеет практической пользы из-за очень долгого времени выполнения, и сделано все just for fun.
В связи с приближающимся наконец-то сентябрем, в качестве примера работы программы была выбрана картинка доктора Хауса.
Итак создание доктора Хауса из ста десятиугольников в течение 20 часов:
Что для данной задачи будет являться генами? Оказывается, это будут координаты точек многоугольника (далее будем называть его полигоном) и его цвет. Скрещивание мы использовать не будем, только мутацию (это вполне допустимо). Популяция, как ни странно, будет состоять из одного индивида, и это будет картинка с прорисованными на ней полигонами.
Функцией приспособления будет сумма погрешностей цветов всех пикселов. Погрешность для пикселя определяем как
R*R + G*G + B*B, где R — разность между красной составляющей пикселя исходной картинки и полученной, G и B — зеленой и синей. Чем меньше значение функции, тем меньше погрешность и тем лучшую картинку мы получили.
Определим класс точки полигона:
Точка имеет координаты X и Y. Процедура SetRandom задает точке случайные координаты, согласно размерам нашей картинки. Процедура Mutate делится на три части, каждая из которых выполняется согласно своей заданной вероятности выпадения. Первая дает шанс точке переместиться в любое место картинки. Вторая часть перемещает точку на среднее расстояние, далее вы увидите, что у меня это до двадцати пикселов. Третья часть дает шанс переместиться на маленькое расстояние, у меня это до трех пикселов.
Далее идет класс кисти, отвечающей за цвет полигона:
У кисти есть A, R, G, B составляющие цвета. SetRandom инициализирует их случайными значениями. В процедуре Mutate каждая из составляющих может случайно измениться согласно своей вероятности выпадения мутации.
Вот мы и подошли к классу полигона:
Полигон включает в себя массив точек и кисть (цвет). Процедура SetRandom инициализирует кисть, а также строит минимальное количество точек вокруг случайно выбранной. Мутация полигона представляет собой мутацию кисти и каждой точки полигона, а также с некоторой вероятностью может произойти добавление или удаление какой-то точки. Процедура Draw отрисовывает наш полигон.
Ну и наконец заключительный основной класс представляет собой рабочую область, содержащую наши многоугольники:
Истинность свойства IsChange показывает, что где-то произошла мутация. SetRandom инициализирует минимальное начальное число полигонов. Mutate запускает мутацию для каждого полигона, а также с заданной вероятностью может произойти добавление или удаление полигона. Функция Fitness вычисляет функцию приспособления, ей передается массив цветов оригинальной картинки. Ну и функция Draw возвращает нашу отрисованную картинку.
Сам алгоритм выглядит так:
Инициализируем начальную популяцию, далее делаем копию и мутируем ее, вычисляем функцию приспособления для новой популяции и, если она меньше текущей (напоминаю, у нас, чем меньше значение функции, тем лучше), то перезаписываем текущую популяцию новой, более лучшей.
Еще у нас остался вспомогательный класс, где хранятся настройки:
Здесь у нас хранятся ширина и высота исходной картинки (инициализируется при загрузке), минимальное и максимальное количество точек в полигоне, минимальное и максимальное число полигонов, вероятности мутаций для каждой компоненты (единица — стопроцентная мутация) и расстояния, на которые может переместиться точка.
Проект целиком можно слить здесь.
UPD: спасибо за карму, перенес в блог Алгоритмы.
Задача
Сделать из полупрозрачных многоугольников изображение максимально похожее на оригинал.
Прежде всего хочу сказать, что использование генетического алгоритма в решении этой задачи не имеет практической пользы из-за очень долгого времени выполнения, и сделано все just for fun.
Демонстрация
В связи с приближающимся наконец-то сентябрем, в качестве примера работы программы была выбрана картинка доктора Хауса.
Итак создание доктора Хауса из ста десятиугольников в течение 20 часов:
Исходные данные
Что для данной задачи будет являться генами? Оказывается, это будут координаты точек многоугольника (далее будем называть его полигоном) и его цвет. Скрещивание мы использовать не будем, только мутацию (это вполне допустимо). Популяция, как ни странно, будет состоять из одного индивида, и это будет картинка с прорисованными на ней полигонами.
Функцией приспособления будет сумма погрешностей цветов всех пикселов. Погрешность для пикселя определяем как
R*R + G*G + B*B, где R — разность между красной составляющей пикселя исходной картинки и полученной, G и B — зеленой и синей. Чем меньше значение функции, тем меньше погрешность и тем лучшую картинку мы получили.
Код
Определим класс точки полигона:
[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.
Точка имеет координаты X и Y. Процедура SetRandom задает точке случайные координаты, согласно размерам нашей картинки. Процедура Mutate делится на три части, каждая из которых выполняется согласно своей заданной вероятности выпадения. Первая дает шанс точке переместиться в любое место картинки. Вторая часть перемещает точку на среднее расстояние, далее вы увидите, что у меня это до двадцати пикселов. Третья часть дает шанс переместиться на маленькое расстояние, у меня это до трех пикселов.
Далее идет класс кисти, отвечающей за цвет полигона:
[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.
У кисти есть A, R, G, B составляющие цвета. SetRandom инициализирует их случайными значениями. В процедуре Mutate каждая из составляющих может случайно измениться согласно своей вероятности выпадения мутации.
Вот мы и подошли к классу полигона:
[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(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<Point>();
Points.ForEach(p => newpolygon.Points.Add(p.Clone() as Point));
return newpolygon;
}
}
* This source code was highlighted with Source Code Highlighter.
Полигон включает в себя массив точек и кисть (цвет). Процедура SetRandom инициализирует кисть, а также строит минимальное количество точек вокруг случайно выбранной. Мутация полигона представляет собой мутацию кисти и каждой точки полигона, а также с некоторой вероятностью может произойти добавление или удаление какой-то точки. Процедура Draw отрисовывает наш полигон.
Ну и наконец заключительный основной класс представляет собой рабочую область, содержащую наши многоугольники:
[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.
Истинность свойства IsChange показывает, что где-то произошла мутация. SetRandom инициализирует минимальное начальное число полигонов. Mutate запускает мутацию для каждого полигона, а также с заданной вероятностью может произойти добавление или удаление полигона. Функция Fitness вычисляет функцию приспособления, ей передается массив цветов оригинальной картинки. Ну и функция Draw возвращает нашу отрисованную картинку.
Сам алгоритм выглядит так:
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.
Инициализируем начальную популяцию, далее делаем копию и мутируем ее, вычисляем функцию приспособления для новой популяции и, если она меньше текущей (напоминаю, у нас, чем меньше значение функции, тем лучше), то перезаписываем текущую популяцию новой, более лучшей.
Еще у нас остался вспомогательный класс, где хранятся настройки:
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.
Здесь у нас хранятся ширина и высота исходной картинки (инициализируется при загрузке), минимальное и максимальное количество точек в полигоне, минимальное и максимальное число полигонов, вероятности мутаций для каждой компоненты (единица — стопроцентная мутация) и расстояния, на которые может переместиться точка.
Проект целиком можно слить здесь.
UPD: спасибо за карму, перенес в блог Алгоритмы.