Оптимизация, Домино и Франкенштейн

1 min


Роберт Бош имеет новая книга выходит на следующей неделе под названием OPT ART: от математической оптимизации до визуального дизайна. В этом посте будет рассмотрен только один пример из книги: создание изображений монстра Франкенштейна (1) с использованием домино.

Франкенштейн сделан из 3 комплектов двойных девяти домино

Книга включает в себя два изображения, изображение с низким разрешением, сделанное из 3 комплектов домино, и изображение с высоким разрешением, сделанное из 48 комплектов. Это двойные девять домино, а не более распространенные двойные шесть домино, потому что первые допускают более симметричное расположение точек. В двойной девятке 55 домино. (Объяснение и обобщение Вот.)

Изображение монстра Франкенштейна из 48 комплектов двойных девяти домино

Изображения создаются путем решения ограниченной задачи оптимизации. Вы в основном хотите использовать домино, яркость которых пропорциональна яркости соответствующего раздела фотографии. Но вы можете использовать только домино, которое у вас есть, и вы должны использовать их все.

Вы, естественно, захотите использовать двойные девятки для самых ярких областей, так как они имеют самые белые пятна и двойные пробелы для самых темных областей. Но у вас есть только три каждого на первом изображении, сорок восемь каждого на втором, и вы должны обойтись с остальными доступными частями. Таким образом, вы решаете задачу оптимизации, чтобы сделать все возможное.

Каждое домино может располагаться горизонтально или вертикально, если они соответствуют общей форме изображения. На первом изображении вы можете видеть ориентацию кусочков, если присмотреться. Вот маленький кусочек из верхнего угла.

Ориентация домино

Одна двойная шестерка расположена вертикально вверху слева. Рядом с ним расположены еще одна двойная шестерка и двойная пятерка, расположенные горизонтально и т. Д.

Существуют дополнительные ограничения на проблему оптимизации, связанные с контрастом. Вы не просто хотите подобрать яркость фотографии настолько хорошо, насколько это возможно, вы также хотите сохранить контраст. Например, возможно, пять-два домино соответствовали бы яркости пары соседних квадратов на фотографии, но семь-один лучше бы отличил контрастные области изображения.

Босх объясняет, что для постановки задачи для изображения с использованием трех наборов домино требовалось 34 265 переменных и 385 ограничений домино. Это было решено с использованием 29 242 итераций симплексного алгоритма и заняло чуть менее 2 секунд.

Задача оптимизации изображения, созданного из 48 наборов домино, требовала 572 660 переменных и 5 335 ограничений. Решение потребовало 30 861 итераций симплексного алгоритма и чуть менее одной минуты вычислений.

Похожие сообщения

(1) В романе Шелли «Франкенштейн» доктор, который создает монстра, – Виктор Франкенштейн. Существо обычно называют Франкенштейном, но, строго говоря, это не его имя. Есть цитата – я не смог отследить ее источник – она ​​гласит: «Знание – это знание, что Франкенштейн не был монстром. Мудрость знает, что Франкенштейн был монстром ». То есть, имя монстра не было Франкенштейном, но то, что сделал Виктор Франкенштейн, было чудовищно.


0 Comments

Ваш e-mail не будет опубликован. Обязательные поля помечены *