Воспроизведение изображений с примитивными формами. (Задача оптимизации графики)

Question

Исходя из этой оригинальной идеи, которую многие из вас, вероятно, видели раньше: http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Я хотел попробовать другой подход:

У вас есть целевое изображение. Допустим, вы можете добавить один треугольник за раз. Существует некоторый треугольник (или треугольники в случае галстука), который максимизирует сходство изображения (фитнес-функция). Если бы вы могли грубой силой пройти через все возможные формы и цвета, вы бы ее нашли. Но это слишком дорого. Поиск всех треугольников - это 10-мерное пространство: x1, y1, x2, y2, x3, y3, r, g, b, a.

Я использовал имитацию отжига с довольно хорошими результатами. Но мне интересно, смогу ли я еще улучшить это. Одна из идей заключалась в том, чтобы на самом деле проанализировать разницу между целевым изображением и текущим изображением и найти «горячие точки», которые могли бы быть хорошими местами для размещения нового треугольника.

Какой алгоритм вы бы использовали, чтобы найти оптимальный треугольник (или другую форму), который максимизирует сходство изображения?

Должен ли алгоритм изменяться, чтобы по-разному обрабатывать грубые и мелкие детали? Я не позволил ему работать достаточно долго, чтобы начать улучшать детали изображения. Кажется, что он стесняется добавлять новые фигуры, чем дольше он работает ... он использует низкие значения альфа (очень прозрачные фигуры).

Целевое изображение и воспроизводимое изображение (28 треугольников):

Редактировать! У меня появилась новая идея. Если заданы координаты фигуры и альфа-значение, оптимальный цвет RGB для фигуры может быть рассчитан путем анализа пикселей в текущем изображении и целевом изображении. Это исключает 3 измерения из пространства поиска, и вы знаете, что используемый вами цвет всегда оптимален! Я реализовал это и попробовал другой прогон, используя круги вместо треугольников.

300 кругов и 300 треугольников:

Answer 1

Я бы начал экспериментировать с цветами вершин (иметь разные значения RGBA для каждой вершины), это немного увеличит сложность, но значительно увеличит способность быстро соответствовать целевому изображению (предполагая, что фотографические изображения, как правило, имеют естественные градиенты вих).

Ваш вопрос, кажется, предлагает отойти от генетического подхода (то есть попытаться найти хороший треугольник, который бы подходил, а не развивал его).Однако это можно интерпретировать в обоих направлениях, поэтому я отвечу на генетический подход.

Чтобы сфокусировать ваши мутации, можно применить сетку к изображению, вычислить, какой квадрат сетки является наименьшим.наилучшее совпадение соответствующего квадрата сетки на целевом изображении и определите, какие треугольники пересекаются с этим квадратом сетки, а затем пометьте их для большей вероятности мутации.

Вы также можете (в то же время) улучшитьдетализируйте, выполнив меньшую проверку на основе сетки для best соответствующего квадрата сетки.

Например, если вы используете сетку 8x8 над изображением:

• Определите, какой из 64 квадратов сетки является наихудшим совпадением, и отметьте пересекающиеся (или рядом / окружающие) треугольники для большей вероятности мутации.
• Определите, какой из 64 квадратов сетки best совпадают и повторяются с другой меньшей сеткой 8x8 только в пределах этого квадрата (то есть сетки 8x8 в пределах этого лучшего квадрата сетки).Они могут быть отмечены для вероятных мест для добавления новых треугольников или просто для точной настройки деталей.

Answer 2

Идея с использованием нескольких прогонов:

• Используйте исходный алгоритм в качестве первого запуска и остановите его после заданного количества шагов.
  • Анализ результатов первого запуска. Если результат получился довольно хорошим на большей части изображения, но плохо работал на небольшой части изображения, увеличьте выделение этой части.
• При выполнении второго прогона удвоите вклад ошибок из выделенной части (см. Примечание). Это приведет к тому, что второй забег станет лучше в этой области. С другой стороны, в остальной части изображения это будет хуже, чем при первом запуске.
• Повторно выполнить много прогонов.

Наконец, используйте генетический алгоритм для объединения результатов - ему разрешено выбирать из треугольников, сгенерированных из всех предыдущих прогонов, но не разрешается генерировать новые треугольники.

Примечание. На самом деле существовало несколько алгоритмов для расчета того, насколько велика доля ошибок. Она называется http://en.wikipedia.org/wiki/Boosting. Однако, я думаю, что идея все равно будет работать без использования математически точного метода.

Answer 3

Я думаю, что алгоритм на самом деле очень прост.

P = 200 # size of population 
max_steps = 100

def iteration
  create P totally random triangles (random points and colors)
  select one triangle that has best fittness
  #fitness computing is described here: http://rogeralsing.com/2008/12/09/genetic-programming-mona-lisa-faq/
  put selected triangle on the picture (or add it to array of triangles to manipulate them in future)
end

for i in 1..max_steps {iteration}

Answer 4

Действительно очень интересная проблема!Моим способом анализа такой проблемы было использование алгоритма оптимизации эволюционной стратегии .Это не быстро и подходит, если количество треугольников мало.Я не достиг хорошей аппроксимации исходного изображения - но это отчасти потому, что мое исходное изображение было слишком сложным - поэтому я не пробовал много перезапусков алгоритма, чтобы посмотреть, какие другие неоптимальные результаты может дать EVO ...дело - это неплохо, как метод генерации абстрактного искусства: -)