Продолжаем серию про генетические алгоритмы. В предыдущих частях мы реализовали строковый генетический алгоритм, который приводит строку, состоящую из случайных символов, к нужной нам строке.
Практическая бесполезность этого алгоритма была очевидна: нам известна целевая строка, и следовательно, нам вообще не нужно делать итераций, чтобы к ней прийти. Весь алгоритм являлся лишь упражнением.
На этот раз мы попробуем реализовать другой алгоритм:
- Берём любую картинку
- Пытаемся создать такой набор цветных треугольников, который наиболее похож на эту картинку
Здесь нам тоже известна целевая картинка. Если бы хромосомы нашего алгоритма представляли собой набор пикселов, мы получили бы ту же ситуацию, что и в случае со строками: байты картинки были бы просто символами большой строки. Соответственно, нам не нужно делать итераций, нужно просто сразу взять конечный набор пикселов, соответствующий этой картинке.
Но мы оперируем не пикселами, а геометрическими примитивами – треугольниками. И значит, появляется такое обстоятельство, которое мы уже не можем предсказать.
Хромосома состоит из N генов-треугольников. Каждый треугольник имеет специфическую форму, размер и цвет, включая прозрачность. Нам известна целевая картинка (набор пикселов), но нам неизвестна целевая конфигурация треугольников (набор координат вершин и цветов), которая наиболее близко соответствует этой картинке. Поэтому в данном случае генетический алгоритм вступает в своё полное право и приобретает практическую ценность.
Что мы можем получить с помощью треугольников?
Во-первых, это своего рода упаковка картинки. Если, например, картинка имеет размер 500*500 пикселов, то один пиксел это 3 байта (RGB) и всего у нас 750 000 байт.
Если мы представляем картинку в виде, скажем, 100 треугольников, то на 1 треугольник нужно 16 байт. Это 3 вершины по 4 байта плюс 4 байта на цвет и прозрачность. То есть 100 треугольников это всего 1600 байт. Разница в 468 раз!
Конечно, это получается "сжатие с потерями". С помощью 100 или даже 1000 треугольников вряд ли получится точно воспроизвести картинку. Но с другой стороны, это порождает некий самоценный художественный эффект.
Посмотрите:
Во-вторых, кодирование картинки треугольниками по факту переводит её в векторный формат. То есть мы можем безболезненно увеличивать и уменьшать масштаб картинки, и треугольники всякий раз будут перерисовываться без артефактов, сопутствующих пиксельному масштабированию.
Почему именно треугольники?
На самом деле подобный алгоритм можно реализовать и с помощью прямоугольников, и с помощью, скажем, эллипсов и других фигур. Почему бы нет? Просто сейчас треугольники – уже проверенный вариант, и будем ему следовать, чтобы не свалиться в проблемы. А дальше уже можно будет попробовать что-то другое.
Порядок реализации
Вышеприведённый пример с Моной Лизой я позаимствовал на канале Youtube "2 Minute Papers":
Я скачал исходники программы Genetic Mona, чтобы разобраться в них. Программа действительно работает, и как ни странно, она реально простая и содержит те же самые шаги, которые мы уже проходили в строковом генетическом алгоритме:
- фитнес-функция
- отбор элит
- одноточечный кроссоверинг
- мутации
Фактически всё отличие – это представление хромосом. Здесь хромосомы это не строки, а наборы треугольников. В качестве мутирующих генов выступают координаты вершин треугольников и их цвета.
Однако у программы есть недостаток. Через некоторое время работы в ней что-то ломается, и вместо нормальной, похожей на правду картинки она начинает генерировать что-то бессмысленное. Подозреваю, что там глючит многопоточность (фитнес-функция считается в нескольких потоках для ускорения).
Кроме того, эта программа имеет жёстко заданный размер картинки и имя файла.
Поэтому в своей реализации я хочу, во-первых, устранить глюки, и во-вторых, добавить такой функционал:
- возможность загружать любую картинку
- возможность сохранять текущую популяцию хромосом
- возможность продолжать программу с сохранённого места, чтобы не начинать каждый раз заново
Попутно нужно будет посмотреть, что и где можно оптимизировать по скорости. Это будет довольно непростая задача.
Фитнес-функция
Особую проблему представляет вычисление фитнес-функции. В строковом алгоритме это было расстояние между строками. Расстояние считается как количество несовпадающих символов.
В варианте с картинкой мы также считаем расстояние, но не между строками, а между картинками: целевой и сгенерированной из треугольников. Здесь мы должны сравнить каждый пиксел из одной картинки с пикселом в этой же позиции в другой картинке.
Но нам недостаточно знать, совпадают они или нет – нам нужно буквально расстояние между этими двумя пикселами в трёхмерном цветовом пространстве RGB. Чем больше это расстояние, тем очевидно сильнее пикселы различаются по цвету.
Итак, мы считаем расстояние между первым пикселом в целевой картинке и первым пикселом в сгенерированной треугольниками картинке. Затем считаем расстояния между вторыми пикселами, между третьими пикселами и т.д., то есть в результате мы получаем столько расстояний, сколько пикселов есть в картинке. Все эти расстояния мы складываем друг с другом и получаем общее расстояние, на котором друг от друга находятся две картинки. Это и будет фитнес-функция, но проблема тут в том, что вычисления будут занимать много времени.
Поэтому фитнес-функцию желательно бы как-то упростить. В конечном итоге нас интересуют не точные расстояния между пикселами, а только оценка "хуже-лучше". Над этим нужно подумать.
Продолжение: Практическая реализация
Читайте также: Олдскульная растеризация треугольников