Цикл статей про генетическую Мону Лизу был написан давно и посвящён генетическим алгоритмам. Вот последняя публикация, в которой есть ссылки на предыдущие:
Так как дело было давно, вкратце поясню, о чём вообще речь.
1. Генетический алгоритм
Это такой алгоритм, который мутирует набор данных и производит отбор до тех пор, пока этот набор не совпадёт с эталонным.
В отношении картинок набор данных это набор разноцветных треугольников, у которых мутируют координаты вершин, прозрачность и цвет. Множество таких треугольников должно в совокупности дать картинку, близкую к эталонной. В качестве эталона берётся изображение Моны Лизы.
А это её начальная аппроксимация 19-ю треугольниками:
2. Проблема сходимости
Чем ближе множество треугольников к эталонной картинке, тем медленнее идёт отбор. Это связано с тем, что когда алгоритм только начинает работу, почти любой случайный треугольник улучшает картинку, а в конце работы наоборот, почти любой ухудшает.
3. Овердрайв
Для борьбы с предыдущей проблемой я придумал режим овердрайва. Если текущий набор треугольников не может развиваться дальше, значит он уже достиг некоего стабильно-оптимального состояния, когда мутации его только ухудшают. В этом случае нужно добавлять новые треугольники, которые сформируют новые детали. Но при обычном случайном добавлении у этих треугольников слишком мало шансов попасть в отбор, потому что появившись, они с большой вероятностью ухудшат картинку и будут отброшены.
Поэтому я вычисляю в картинке области, которые сформированы хуже всего, и создаю новые треугольники именно в этих областях. Там у них больше шансов.
4. Текущая ситуация
Режим овердрайва помог, но не совсем. Да, рисуются новые детали, но развитие на каком-то этапе всё равно останавливается. Первоначально я думал, что изображению просто не хватает треугольников, и сделал динамический расчёт количества треугольников в зависимости от размеров изображения. Однако эксперименты показали, что эти треугольники полностью не используются. Например, для изображения размером 768*512 рассчитано 629 треугольников, но прогресс останавливается на 300. Очевидно есть места, куда можно добавить треугольники и улучшить картинку, но они почему-то не добавляются.
Это меня просто выводило из себя, пока я не озарился гениальной мыслью.
5. Гениальная мысль!
Корень проблемы в том, что когда картинка близка к эталонной, и появляется новый треугольник, он почти всегда будет плохим, и будет отброшен. То есть алгоритм просто не даёт появляться новым треугольникам, постоянно отбрасывая их, а случайные удачи слишком редки.
В то же время даже плохой треугольник, если дать ему появиться, начнёт мутировать и в конце концов станет хорошим. Вывод – надо просто добавлять треугольники, неважно какие.
Я пока сделал это только в режиме овердрайва. Так как я знаю область, в которую добавляется треугольник, я знаю рейтинг этой области до добавления. Рейтинг это просто разница с эталонной картинкой, чем он ниже, тем лучше.
Добавляемый треугольник ухудшает рейтинг области, но я позволяю его добавить и затем не добавляю следующий до тех пор, пока рейтинг этой области не станет как минимум таким же, каким был до добавления.
Таким образом, я жду, пока треугольник мутирует настолько, чтобы стать хорошим. И только после этого можно добавлять следующий.
6. Результат
Алгоритм сразу же стал активно использовать оставшиеся треугольники. Иногда сразу по 10 штук подряд. Это немножко напугало, но по факту оказалось не страшным. Алгоритм действительно использовал их по мере надобности и по назначению. Качество картинки моментально улучшилось, а прогресс стал идти в несколько раз быстрее.
Вот Мона Лиза с новым алгоритмом:
И можно посмотреть, куда алгоритм тратил треугольники:
Мона Лиза обманчива в том плане, что хорошо подходит под мой алгоритм, но когда я пробовал другие картинки, там получалось не так хорошо. Сейчас, с новыми изменениями, эти картинки тоже стали получаться.
Например, вот такая:
Получается вот так:
И она ограничена только максимальным количеством треугольников, которое можно увеличить и получить больше детализации. Однако, тут добиваться 100%-го совпадения с оригиналом не нужно, потому что это было бы крайне скучно. В слегка недоделанном виде картинки из треугольников выглядят гораздо интереснее.
Код на github буду обновлять позже, сейчас там слишком много мусора из-за постоянных экспериментов.