Давеча мне посчастливилось заручится поддержкой моего собственного интереса и на его базе написать в маткаде программу рисующую закат на основе генетического алгоритма. И здесь я хочу поведать как это было.
Я собирался написать программу рисующую некоторое изображение, например как то что выше. Рисовать она будет прямоугольниками закрашенными в один цвет. А генетический алгоритм будет составной частью этой программы, он будет подыскивать наиболее оптимальные прямоугольники, оптимальные в смысле положение+цвет некоторой области. В итоге я ожидаю получить что-то похожее на оригинал, но нарисованное только прямоугольниками)))
В конце я приложу анимацию процесса рисования, которая получилась по истечении 1200+ итераций.
А теперь к самому процессу.
Сперва-наперво были написаны функции преобразования между представлениями изображения.
Функция M2T(M) преобразует изображение из "матричного" вида в "тензорный", а функция T2M(T) делает противоположное: преобразует изображение из "тензорного" вида в "матричный".
Что ещё за "тензорный" и "матричный" виды? поясню.
Когда маткад импортирует изображение он позволяет работать с цветным изображением как с матрицей, но не обычной а своего рода блочной, в которой каждый канал (красный, зелёный и синий) является отдельной картинкой и он эти три канала объединяет последовательно рядом друг с другом, просто "стык-в-стык", вот пример ниже, слева цветное изображение, а справа его представление в "матричном" виде, как принято по умолчанию в маткаде.
Так вот что бы не прыгать по каналам, я преобразую изображение в форму в которой все три цвета как и полагается лежат в одном пикселе, я называю этот вид "тензорным", но не потому что это настоящий тензор, а потому что в каждой ячейке матрицы лежит уже не число, а массив из трёх элементов-цветов: красный, зелёный и синий.
В функции T2M(T) они так и обозначены: R, G, B.
Не буду долго на этом останавливаться, скажу лишь то, что выводить, и на экран, и для сохранения, можно только изображения в "матричном" виде, тогда как работать с преобразованиями лучше в "тензорном", это удобнее, поэтому исходное изображение вначале преобразуется в "тензорный" вид, я с ним буду работать и после всего что только можно сделать, это изображение преобразую обратно в матричный вид что бы сохранить или отобразить его на экране. Вот такая особенность.
Для того что бы начать рисовать в маткад, я написал функцию создания некоего полотна - canvas`a - она так и называется createCanvas(H, W, Color)
Она принимает в качестве аргументов высоту, ширину и цвет полотна
Далее по порядку, но не по порядку создания, идёт три функции генерирующих случайные объекты
Эти функции генерируют случайные координаты (или размеры), случайный цвет и случайный прямоугольник, который я по привычке называл "квадратом".
Однако в процессе разработки этой программы была иная очерёдность действий, вначале я продумал вид отдельной особи в форме этого самого "квадрата", который должен содержать в себе положение центра, ширину, высоту и цвет. Я решил что не буду делать свои прямоугольники полупрозрачными и потому не стал добавлять к цвету ещё и "альфу".
Таким образом каждый прямоугольник (и по совместительству особь в ГА) должен иметь такую структуру:
После этого было написано многое по отрисовке и частично ГА и только потом я вычленил ряд функций отдельно из других что бы позже их переиспользовать в других алгоритмах. Одна из таких вычлененных функций это функция getVertexQuadro(center, hw, canvas), а те функции генерации случайных я писал уже непосредственно подступив к ГА
Эта функция вычисляет координаты диагональных углов прямоугольника на основе положения его центра, его ширины и высоты, а также параметров холста.
Кстати, забыл упомянуть, зачем здесь нужны параметры холста? дело в том что я решил что координаты и размеры прямоугольников я буду записывать в долях от единицы, поэтому что бы от долей перейти к пикселям нужно знать размер холста в пикселях.
Следом идёт функция для рисования прямоугольника.
И написанная на основе неё функция для рисования нескольких прямоугольников
Она последовательно берёт каждый прямоугольник из списка и рисует их на холсте.
Теперь сам ГА, его я решил использовать несколько не обычно: не искать все прямоугольники сразу, а делать это по очереди. То есть, первым делом ищется один прямоугольник, минимизируя квадрат суммы отклонений всех цветов попиксельно, затем на основе уже найденного решения ищется ещё один прямоугольник таким же образом, и тд..
Таким образом можно найти сколь угодно много прямоугольников и замостить холст подходящими решениями, нарисовав нужную картинку.
Начинать ГА следует с начальной популяции, но я конечно начинал его писать иначе, в другой последовательности, но так как сейчас я лишь описываю то, что получилось, я рассказываю именно про начальную популяцию.
Она выглядит нехитро, это просто набор прямоугольников со случайными положениями, размерами и цветом.
Далее идёт функция скрещивания, но прежде чем скрестить всю популяцию нужно уметь скрещивать пару особей (это одна из ключевых функций алгоритма поэтому она раскрашена у меня в красный цвет)
Здесь с вероятностью 50% в особь-потомка попадут гены одного из двух особей-родителей, то есть: положение, размеры и цвет. Можно было бы скрещивать конкретные координаты и так далее, но в таком виде скрещивание будет скрещивать целые признаки, а не просто части этих признаков.
Общая функция скрещивания, для всей популяции, выглядит следующим образом
Далее на очереди мутации, но они имеют ту же особенность, что бы мутировать всю популяцию, нужно уметь мутировать произвольную особь. Но не всё так просто, в рамках данной задачи координаты и размеры могут мутировать как угодно, они могут стать больше единицы, это просто будет означать большое смещение центра прямоугольника или его большой размер, и они так же могут стать отрицательными, тогда размер будет отсчитываться как-бы в противоположную сторону, что существенно не скажется на результате.
Но что касается цвета, с ним другое дело, он ограничен значениями 0 (для абсолютно черного) и 255 (для абсолютно белого), причем для каждого из каналов, поэтому прежде чем писать функцию для мутации двух особей нужно написать функцию для мутации цвета, с учетом этих ограничений.
Тогда функция мутации особи будет выглядеть примерно таким образом (это тоже ключевая функция и она тоже раскрашена)
Теперь мутации всей популяции, они почти что стандартные
После скрещивания и мутаций следует определение приспособленности и здесь, как я уже писал, она заключается в суммировании разницы квадратов отклонений всех цветов попиксельно. Для этого нужно написать функцию вычисляющую эту самую разницу
Эта функция имеет в названии цифру "2" и не просто так, дело в том что это оптимизация более ранней функции которая позволила ускорить вычисление разницы в примерно 100 раз. Мысль примитивная, но я дошёл до неё только спустя пару дней, нужно при рисовании очередного прямоугольника считать не всю разницу между изображениями, а только в области рисования, так как остальная разница не меняется.
Поэтому сначала, на старте ГА считается базовая разница между текущих холстом и оригинальным изображением, эта разница как параметр передаётся в функцию вычисления приспособленности где вместо того что бы проходить все пиксели считается разница только в области рисования квадрата, эта разница вычитается из текущей разницы между всем холстом и оригиналом, а после, к этой разнице прибавляется разница между цветом квадрата и оригиналом, так как квадрат (прямоугольник) всегда одноцветный.
Отсюда огромный прирост в скорости расчёта разницы, причем эта скорость нарастает с уменьшением размера квадрата, что и случается в результате работы ГА: с течением времени ГА ищет всё меньшие и меньшие квадраты для их рисования, потому что большие квадраты не только не делают лучше, а стирают часть предыдущей работы и ухудшают показатель приспособленности. То есть со временем ГА начинает работать более детально (впрочем скоро вы увидите это на анимации поиска оптимальных прямоугольников для рисования).
Что ж вот и сама функция вычисления приспособленности (то же вторая, так как в ней применяется оптимизированная предыдущая функция которая работает чуть иначе чем ранее)
Далее идёт стандартная функция обора на основе отклонения. Она сращивает два массива (особи с их ошибкой рисования), сортирует по возрастанию (то есть особи с меньшей ошибкой будут выше) и вычленяет первые несколько несколько особей в новую популяцию, а остальных просто забывает
Сам Генетический Алгоритм выглядит таким образом
Он довольно громоздок, в силу того, что в нем я дополнительно делаю подсчёт попадания в локальный оптимум и досрочный выход из него при нескольких неудачных попыток, а так же вывожу информацию в реальном времени в "консоль", хотя это не столько консоль сколько просто информационное окно)))).
Этот алгоритм выполняется на каждой итерации расчёта нового прямоугольника в базовом алгоритме, который выглядит ещё более громоздко, но это тоже потому что там есть некоторые дополнения в виде повтора поиска в ГА при условии что предыдущий ГА завершился с тем же результатом (с той же ошибкой) что и текущий, то есть текущий ГА не улучшил результат, а значит его бесполезно и нужно начинать снова искать этот же прямоугольник, так как найденный плох.
В результате работы этого алгоритма выводится информация о истории поиска в виде списка HH с набором отклонений лучшей особи на каждой итерации и новый список прямоугольников.
Причем алгоритм построен так что на вход он тоже получает список прямоугольников, то есть он может дополнять свои же решения, что я и реализовал в виде загрузки и сохранения его результатов по нажатию чекбокса:
Загрузка информации из файла.
И сохранение в фаил
Важно после сохранения сразу же снять галочку с этого чекбокса, иначе после следующего запуска поиска новой порции прямоугольников они автоматически запишутся в фаил, даже если они вам не нужны или если она вам не нравятся...
И обещанная анимация рисования (гиф-формат немного искажает цвета из-за сжатия, но в целом всё норм)
Казалось бы, что тут такого, какие-то прямоугольники, и картинка пиксельная, но в этом и был изначальный замысел - это приближение обычного изображения прямоугольниками, с получением не самого плохого результата, даже округлая луна получилась округлой, а так же прочие цвета местности и градиент неба, всё нарисовано одноцветными прямоугольниками)))
Пока я писал эту статейку, захотелось немного доработать генерацию анимации. Я добавил вниз изображения полоску заполняющуюся по мере прохождения анимации и нашёл новые картинки для демонстрации (это картинки из некоторой нейросети).
Первая картинка минималистичная, вот такой зайчик
и вот анимация приближения его вида прямоугольниками
Вот такое лицо (здесь я хотел посмотреть как будут отыскиваться крупные формы)
И его приближение
А так же вот такую "геометричную" картинку что бы посмотреть как он будет справляться с прямоугольниками на картинке
И результат поиска набора прямоугольников (кстати, по совокупности отклонений этот вариант дал наимение плохой результат за примерно одинаковое количество итераций - примерно в 3-4 раза лучший чем любой из вышеприведённых, я думаю это из-за того что на оригинале много прямоугольных одноцветных областей, это я и хотел проверить выбрав эту картинку)
вообще нужно понимать что для ускорения я произвожу поиск на малом холсте и там всё находится отменно, вот сравнение результата с оригиналом (оригинал слева, результат справа)
Но при масштабировании все квадраты становятся более отчетливо видны, тогда как на маленьком изображении они могли вписываться в "околопиксельный" формат восприятия и не сильно бросаться в глаза)))
Так же у меня сейчас появилась идея использовать только маленькие прямоугольники для поиска оптимума и это привело вот к такому интересному эффекту. Мне понравилась "стилизация" итогового изображения, выглядит по своему заманчиво, особенно когда это синий и золотой цвета... может ещё посмотрю на это позднее, чувствуется некий потенциал...
В окончании могу лишь предоставить ссылку на маткад-документ на моём гугл-диске, но будьте осторожны, если будете его запускать, из-за чекбоксов он требует разрешения на включение скриптов (точнее на их отключение)...
П.С. Так же в файле ещё есть функции для генерации анимации и сохранения секвенции с выделением каждого прямоугольника красной обводкой (для заметности),а так же функции по удалению дубликатов прямоугольников, но я оставлю это за кадром так как непосредственно к ГА это не относится.
Для тех кому интересно как всё это было написано, оно есть в видео формате на Ютубе длительностью 8 часов))) (в трёх частях):