Продолжаю эксперименты над графическим генетическим алгоритмом.
Предыдущие части: Новая надежда, Заключение, Генетическая Мона Лиза
Для тех, кто здесь впервые, поясню: генетические алгоритмы это семейство методов, которые должны найти решение задачи с помощью селекционного отбора случайных вариантов.
В нашем случае задача это построение картинки, максимально близкой к заданной. Картинка может быть любая, но как тестовый пример используем Мону Лизу:
Хромосома – набор цветных треугольников (генов). Они мутируют, и мы отбираем те варианты, которые ближе к оригиналу. Близость определяется путём подсчёта рейтинга – это сумма всех разниц между пикселами оригинала и хромосомы. Чем меньше рейтинг, тем лучше.
В программе были неочевидные ошибки и проблемы со сходимостью алгоритма. На каком-то шаге изображение переставало улучшаться, а точнее этот процесс занимал очень долгое время.
Я также потратил много времени на оптимизацию программы, и она практически не удалась, кроме одного пункта.
Интерлейсинг
Пробовал рисовать через строчку и считать рейтинг также через пиксел в обоих направлениях. Идея состояла в том, что это был как бы "черновой" режим для быстрой проверки работы алгоритма на конкретной картинке, после чего можно было включить "чистовой" режим.
Но по скорости никакого заметного прироста не получилось. Зато из-за пропусков в рейтинге в хромосоме стали вылезать артефакты, которые попадали ровно в промежутки между рейтинговыми пикселами и потому оставались невидимыми для учёта.
Пришлось отказаться.
Грязный прямоугольник
Затем возникла идея считать рейтинг не по всей площади, а только в "грязном прямоугольнике". Когда один или несколько полигонов мутируют, они изменяют рейтинг в тех местах, где находились/находятся. В других местах картинки рейтинг остаётся таким же. Поэтому для всех мутировавших полигонов вычисляется прямоугольник, описанный вокруг них – это грязный прямоугольник. И перерасчёт рейтинга делается только внутри него.
Прямоугольник может быть площадью как целая картинка, но чаще он оказывается гораздо меньше. Что ведёт к значительному сокращению вычислений.
Блоки рейтинга
Чтобы пересчитать рейтинг с использованием грязного прямоугольника, нужно вычесть из рейтинга ту часть, которая попадает в прямоугольник. Затем подсчитать новое значение внутри прямоугольника и прибавить его назад к рейтингу.
Беда в том, что рейтинг это всего одно число – общая сумма разниц. И мы не знаем, какая часть этого числа приходится на какой пиксел. И значит, не можем вычесть из рейтинга содержимое прямоугольника. Чтобы его вычесть, его надо повторно подсчитать, но тогда мы не выиграем практически ничего.
Поэтому картинка была разбита на блоки размером 32*32 пиксела. В каждом блоке рейтинг считается и хранится отдельно. А общий рейтинг – это сумма блоков.
Теперь, чтобы вычесть из рейтинга нужную область, я вычитаю из него все блоки, которые попадают (хотя бы частично) в грязный прямоугольник. И подсчет нового рейтинга делаю затем в этих же блоках.
Овердрайв
Долгое время была проблема: когда картинка уже почти готова, самые мелкие детали на ней никак не появлялись. Обычно от этого страдали лица, а так как на картинке мы первым делом смотрим на лицо, такая ситуация удручала.
С помощью тестов и наблюдений я выяснил, что мелкие детали не появляются просто потому, что у них очень низкая вероятность удачного появления. Деталь маленькая, а картинка относительно неё большая, и у детали очень много шансов попасть совершенно не туда, где она нужна. Случайное расположение когда-нибудь к этому приведёт, но ждать приходится бесконечно долго.
И тут мне на помощь пришли те же блоки, созданные в общем-то для другой задачи.
Я сделал специальный режим, который назвал в честь Моны Лизы "овердрайв". Работает он так: после какого-то числа добавленных полигонов он активизируется и ищет блок с самым плохим рейтингом – то есть где разница с картинкой максимальна.
Как правило, такой блок будет именно там, где должны быть мелкие детали. В режиме овердрайва любой новый полигон сможет добавиться только в этот блок и иметь размер не больше, чем размер блока (32*32 пиксела). То есть случайное распределение полигонов сужается до пределов одного блока.
Само собой, после этого вероятность появления правильного полигона резко увеличивается. Результат тоже нагляден: на иллюстрации ниже вы видите слева режим овердрайва, а справа нет.
Картинка справа более равномерно проработана по всей площади, но лицо нарисовано пока ещё слишком грубо. Картинка слева лучше изображает лицо, но хуже фон – потому что в первую очередь ресурсы шли на проработку лица.
Я почти счастлив, но и у этого метода есть недостатки. Например, если на фото вместе с человеком есть какой-нибудь детализированный фон, то алгоритм не сможет понять, какие детали нужнее, и будет старательно выписывать фон. При этом на человека полигонов уже может и не хватить.
В ходе поиска подходящей картинки в интернете нашел такую:
Она должна стать настоящей пыткой для алгоритма из-за детализированного фона. Вот уже много часов он трудится, пытаясь воссоздать белые полоски:
Что ж, на эту проблему также есть решение, которое сейчас проходит тестирование.
И исходный код программы, и сама программа в виде исполняемого файла будут доступны позже, когда я закончу все тестирования и приведу всё в порядок. Сейчас в программе не хватает самого главного – сохранения текущего состояния и картинки.