-Поиск по дневнику

Поиск сообщений в CraigFatman

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 03.05.2007
Записей:
Комментариев:
Написано: 70

Эволюция в действии

Дневник

Четверг, 01 Октября 2009 г. 14:29 + в цитатник
Говорил не буду выкладывать умные мысли, но разнообразие не помешает.

Похоже, это мой первый опыт написания настоящих генетических алгоритмов. Пусть пока что гипотезы (они же особи) содержат только по девять чисел-генов, но их обработка имеет некоторый толк в решении прикладных задач. А задача стояла - подобрать линейную комбинацию каналов RGB, оптимальную для данного преобразования. По сути, гены формируют искомую матрицу 3x3. Я тут занимаюсь 8-битной графикой, и решил привести простую, линейную цветовую модель к логарифмической. Нужно мне это для того, чтобы одной look-up таблицей наложения (прозрачности) v=sqrt(v0*v0+v1*v1) описать как сложение, так и умножение цветов в палитре. Использования только одной такой таблицы требует движок, под который я всё это делаю.

0 < x < 1
x' = log(x)/-3
x = exp(x'*-3)

Вот эти формулы лучше всего позволяют привести умножение ко сложению. Однако прямая подстановка цветовых коэффициентов приводит к низкому качеству восстановленного по двум таблицам поиска (CLUT) изображения. Следует помнить, что преобразованная палитра должна быть представлена по возможности теми же цветами, что и исходная. К счастью, преобразуемые каналы вполне могут быть линейной комбинацией исходных красного, зелёного и синего. Правильно подобрать коэффициенты для произвольной палитры - задача под стать численному моделированию. Поскольку применять аналитические методы в данных условиях не удаётся, я решил опробовать эволюционный метод, по-быстрому написав алгоритм в Evaldraw. После некоторых доработок и тестов популяция стала развиваться более-менее устойчиво. Оказалось достаточно выгодно использовать популяцию численностью 2-3 тысячи особей.

На скриншоте исходная палитра и результаты её преобразования показаны на верхних таблицах. Внизу по центру - приведённая к ближайшим цветам таблица логарифмирования, правее созданная на её основе таблица экспонирования. Можно увидеть, что ряд ячеек этой таблицы не используется - они остались белыми. Чем меньше таких белых участков, тем больше уникальных цветов можно увидеть на левой таблице - восстановленной палитре, и тем выше окажется её качество. Лучшая из гипотез позволила восстановить 168 цветов; она напоминает модель CMY, что вполне понятно: именно так вызванная преобразованием инверсия приводится к исходным оттенкам. Существуют и варианты, восстанавливающие 173 цвета, но они не передают самые яркие градации. Мне пришлось модифицировать функцию Fitness, чтобы ценность цвета стала пропорциональной его яркости.

Оставшаяся после финального отбора популяция в списке справа содержит ещё пару неплохих разновидностей, одна из которых аналогична CMY, а другая в середине - более экзотическое сочетание зелёного, оранжевого и пурпурного. В ходе эволюции можно было наблюдать и другие комбинации вроде BGR, которые, однако, оказались не столь успешны. Это указывает на сложную структуру пространства поиска в данной задаче.
 (700x525, 509Kb)

Метки:  

 Страницы: [1]