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

Основываясь на этой оригинальной идее, которую многие из вас, вероятно, видели раньше: 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 треугольников:

Ответ 1

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

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

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

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

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

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

Ответ 2

Идея, использующая несколько прогонов:

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

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

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

Ответ 3

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

Ответ 4

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

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}