Некоторое время назад я задумывался о том, возможно ли мышление без языка, только на уровне визуальных образов. В отличие от естественного языка, пиктографическая или геометрическая знаковая система в гораздо меньшей степени подвержена полисемии и ошибкам, связанным с неверной интерпретацией последовательности или контекста. Может ли быть, что визуальный язык окажется для некоторых машин/роботов более понятным, чем лингвистический? Размышляя об этом, я нашёл на Хабре статью уважаемого @FirstJohn в блоге компании FirstVDS «Семь дощечек мастерства на службе ML» от февраля 2023 года, рассказывающую об алгоритмическом применении танграма. Ниже я подробнее расскажу об этой игре, а также о том, как её сегодня пытаются применять в распознавании образов и при решении других задач, связанных с комбинаторикой..
Структура танграма и другие подобные головоломки
Танграм – это китайская головоломка, в которой содержится семь базовых фигур, образующих квадрат. Это пять прямоугольных треугольников (два больших, один средний, один маленький), квадрат и параллелограмм. Два больших треугольника равны по площади, и некоторые стороны многоугольников также равны. При этом, если принять длину стороны полного квадрата за 1, то параметры остальных фигур будут равны строго:
У маленьких треугольников — гипотенуза = ½ и катеты = √2/4
У среднего треугольника — гипотенуза 1/√2 и катеты ½
У больших треугольников — гипотенуза 1 и катеты 1/√2
Сторона малого квадрата — √2/4
Стороны параллелограмма ½ и √2/4, углы 45° и 135°.
Цель игры – выкладывать из этих многоугольников различные фигуры, так, чтобы отдельные элементы соприкасались друг с другом сторонами или углами, но не лежали изолированно, а также не накладывались друг на друга. Вот как можно собрать из танграма все арабские цифры:
Также существует версия танграма со скруглёнными фигурами; этот набор в совокупности образует не квадрат, а сердечко. При этом многоугольник, напоминающий сердечко, можно собрать и из традиционной версии танграма:
Танграм определённо изобретён в Китае, но о том, когда это произошло, достоверных сведений нет. Самое ранее описание правил игры встречается в книге «Картинки из семи хитрых фрагментов», опубликованной в 1813 году. Там упоминается, что эта игра была обычна в китайских аристократических кругах ещё на 20-25 лет ранее. В Китае сохранились орнаменты (например, на столешницах), напоминающие расширенную версию танграма и относящиеся к эпохе династии Сун (X-XIII век).
По-видимому, само слово «Tangram» впервые употребил в 1848 году художник Томас Хилл в брошюре «Головоломки для обучения геометрии». В Европе с танграмом связано множество «коммерческих» легенд, мистификаций и попыток искусственно состарить эту игру, придумав ей античное, легендарное или даже боговдохновлённое происхождение. Особенно усердствовал в такой популяризации Сэмюэл Лойд, выпустивший в 1908 году издание «Восьмая книга Тан», в котором содержалось «историческое» описание танграма и 700 задач. Некоторые из них до сих пор считаются нерешаемыми. Лойд придумал такую историю:
Давным-давно жил в Китае человек по имени Тан. Он владел красивейшей фарфоровой плиткой. Как-то раз он захотел показать своё сокровище императору, отправился в путь, но споткнулся и разбил эту плитку.
Она раскололась ровно на семь частей, уже рассмотренных нами выше: два больших треугольника, два малых, один средний, квадрат и параллелограмм. Тан сразу же попытался вновь составить плитку в исходный вид. Но, чем дольше он этим занимался, тем яснее понимал, что из получившихся осколков можно составить и множество других фигур, в частности, стилизованных изображений животных. Затем к этой игре подключились его друзья, и так постепенно она обрела всекитайскую популярность.
Легенда о древности танграма прижилась отчасти потому, что подобные головоломки известны в течение столетий как в китайской, так и в европейской цивилизации. Такие игры называются в англоязычных источниках «rearrangement puzzles» («перестановочными пазлами»). Древнейшая достоверно известная из таких игр — стомахион, описанный в одноимённом трактате Архимеда. Стомахион — это упражнение в комбинаторике, демонстрирующее, как разделить квадрат на 14 неравных частей при помощи прямых линий:
Стомахион состоит из 14 фрагментов, и сейчас известно 536 различных способов сложить из них квадрат. По-видимому, в античные времена это была не столько игра, сколько визуальное изучение комбинаторики.
Ранее я также публиковал на Хабре статью «Змей и дротик. От михраба до квазикристаллов». В ней затронуты средневековые мусульманские (прежде всего, персидские) опыты по замощению плоскости наименьшим возможным количеством фигур. Постепенно такие периодические мозаики привели к созданию апериодических, среди которых наиболее известна мозаика Пенроуза.
В Китае первые опыты, напоминающие танграм, восходят к опытам математика Лю Хуэя (220-280). Среди прочих работ Лю Хуэя известны его попытки объяснить соотношение сторон треугольника и их квадратов по «методу гоу-гу», являющемуся китайским аналогом теоремы Пифагора.
В настоящее время такие перестановочные игры становятся только разнообразнее. Например, работающая в Новосибирске компания «Мехвуд» предлагает деревянные наборы, среди которых наряду с танграмом предлагаются игры «пентамино», «циркум», «яйцо Колумба» и даже «пятнашки».
Обратите внимание: в циркуме и яйце Колумба присутствует симметрия, отсутствующая в танграме. Таким образом, танграм является одной из самых простых головоломок своего рода, но всё равно допускает сотни информативных конфигураций. При этом танграм существенно отличается от трёхмерных конструкторов, в частности, LEGO и Meccano, так как количество комбинаций в танграме пусть и велико, но строго ограничено, а значит – поддаётся алгоритмизации. Ниже я кратко рассмотрю некоторые успешные попытки такого алгоритмического применения танграма.
Танграм как алгоритмический метод
Задача автоматического составления фигур танграма относится к более широкому классу NP-сложных задач, именуемых в англоязычных источниках «Cutting and Packing» (C&P), а в русскоязычных — «задачами геометрического покрытия» или «задачами одномерного раскроя материалов». При этом задачи на составление танграм-фигур можно подразделить на простые и сложные. Первые сводятся к операциям переноса и поворотов, причём, повороты должны быть кратны 45° — и в результате имеем фигуру, покрывающую сплошной участок поверхности. При решении сложных танграм-задач получаем фигуры, обладающие не менее чем одной из следующих характеристик: 1) наличие нескольких связных участков, 2) наличие пустот (дырок) в мозаике, 3) необходимость произвольно свободно поворачивать фигуры, 4) необходимость зеркального преобразования параллелограмма..
Для решения танграм-задач машина должна руководствоваться правилами, характеризующими как свойства отдельных многоугольников (в данном случае — треугольников, квадрата и параллелограмма), так и сочетание многоугольников при изменении их ориентации. Например, на уровне аксиом должно учитываться, что два маленьких прямоугольных треугольника образуют квадрат, а два больших прямоугольных треугольника могут образовать прямоугольник как частный случай параллелограмма, но при этом обычный параллелограмм в наборе танграма всегда остаётся один, так как для получения второго такого параллелограмма требуются тупоугольные треугольники, а у нас их нет. Танграм-задачи также применимы для анализа симметрии, поиска отрицательного пространства, а также выявления неплотного прилегания фигур. Выявление неплотного прилегания фигур также связано с задачей оптимизации, которая называется «поиск неустранимых пробелов» (frozen holes). Неустранимый пробел — это фигура, явно не соответствующая ни одной из оставшихся деталей или их комбинации, и такой пробел должен игнорироваться для повышения производительности алгоритма. Вышеперечисленные принципы легли в основу алгоритма «Tangram and Glue» от Google, применяемого при решении следующих задач:
-
Оптимизация: итерационные и геометрические операции, при помощи которых подбирается наиболее выгодное расположение и полное прилегание фигур.
-
Вычислительная геометрия: алгоритм используется для автоматических манипуляций с фигурами, связанных с перестановкой фигур для получения из одного цельного контура другого цельного контура.
Оказывается, что этот алгоритм и другие подобные ему находят применение в графическом дизайне, архитектуре, а также в задачах искусственного интеллекта, например, при подборе поисковой выдачи.
Танграм в конвейерной сборке
В 2022 году Шуо Цинь из Технологического института в Ухане предложил использование танграма в качестве абстрактной знаковой системы, упрощающей роботизированную конвейерную сборку. Когда манипулятор работает, опираясь на данные сенсора (камеры), наиболее сложная часть задачи – это установка деталей в нужном порядке и с правильной стыковкой. Эту задачу можно переформулировать в терминах танграма, если алгоритм будет учитывать нижние грани (основания) детали как фигуры на плоскости. В таком случае манипулятор сначала получает информацию о форме детали, чтобы обеспечить правильный захват, затем информацию о том, как выглядит частично собранный механизм, находящийся на данном этапе сборки, а затем, руководствуясь танграм-подобными принципами (вероятно, также похожими на принципы «Тетриса») устанавливает деталь ровно в ту точку и в том положении, как требуется. Компьютерная модель, предложенная Цинем, демонстрирует конвейерную сборку полного танграм-квадрата, а также стилизованных фигур животных, например, коровы. Порядок работы таков:
-
На ленте конвейера случайным образом генерируется фигура танграма. Как только фигура доезжает до конца конвейера, конвейер останавливается и отправляет манипулятору сигнал к началу работы. Тогда включается манипулятор, задача которого – снять фигуру с конвейера и правильно её установить.
-
Визуальный сенсор считывает цвет и контуры поступившей детали и определяет, с каким из семи элементов танграма имеет дело.
-
Работает манипулятор. В соответствии с определёнными на предыдущем шаге цветом и формой детали, эта деталь устанавливается в позицию, которая соответствует, во-первых, форме фигуры, а во-вторых — общим очертаниям чертежа, по которому мы собираем фигуру (будь то исходный полный квадрат танграма или более сложная фигура).
-
По прошествии семи таких операций проверяется, соответствует ли собранная фигура заданному чертежу. После этого может поступить сигнал либо на коррекцию фигуры, либо на её разбор, либо на сбор следующей фигуры.
При применении такого метода можно соотнести с фигурой танграма в памяти компьютера произвольную деталь и указать, с какими другими деталями она должна сочетаться, маркер какого цвета ей соответствует, сколько таких деталей есть в наборе, и какие положения эта деталь ни в коем случае не может занимать. В таком случае манипулятор может обходиться при работе сравнительно простой камерой и меньше зависеть от проблем, связанных с возможной неверной интерпретацией фигур.
Танграм при решении визуальных микрозадач
Также в 2022 году группа под руководством Ючжоу Чжао из Калифорнийского университета в Лос-Анджелесе предложила использовать алгоритмы на основе танграма для решения задач, связанных с расчётом свёртывания гибких фигур и расположения элементов внутри контура. Алгоритм компьютерного зрения сначала обучается на фигурах танграма и их сочетаниях, а потом получает на вход более сложный датасет, в котором представлены различные категории объектов:
В результате алгоритм усваивает правила симметрии и может обучаться на малых выборках (few-shot learning), так как расчерчивает фигуру по правилам симметрии и, в конечном счёте, редуцирует её до танграм-подобных фигур. Например, можно сообщить алгоритму, что все следующие предметы относятся к одежде, но два левых силуэта являются платьями (по признаку симметрии), а два правых – не являются:
Вот обратное разложение силуэтов одежды на составляющие фигуры:
Наконец, танграм-подобные методы оказываются действенными при генерации планировок, подборе вариантов для расстановки предметов (в том числе, мебели), а также при генерации сцен в компьютерных играх и симуляторах. Эти исследования также проводятся учёными китайского происхождения в Калифорнийском университете Лос-Анджелеса. Танграм-подобный подход позволяет алгоритмизировать показатели компактности и реконфигурируемости. Более того, сцена может включать несколько уровней детализации (например, на уровне предметов и на уровне текстур), где каждый слой может анализироваться в отдельности, но всё равно сводится к набору простейших фигур, между которыми действуют чёткие правила сочетаемости.
Для полноты картины упомяну ещё пару разработок:
Инструмент Mapzen позволяет генерировать по принципу Tangram различные ландшафты, в которых учитывается как высота, так и освещённость каждой точки на местности.
Вот подборка примеров.
Исследователь танграма Бретт Кэмпер из Нью-Йорка предлагает использовать танграм-подобные алгоритмы для процедурной генерации карт, на которых автоматически очерчиваются застроенные и незастроенные участки.
Заключение
Можно предположить, что классический танграм и расширенные наборы подобных фигур значительно упрощают решение нетривиальных геометрических задач, при работе как с компьютерными симуляциями, так и с физическими объектами. Танграм упрощает не только сборку, но и разбор объектов, позволяет достоверно моделировать сложные объекты на основе простых фигур и правил. Я также предположу, что развитие танграм-подобных алгоритмов может привести к развитию алгоритмов и устройств для имитации фасеточного зрения, которое, в отличие от естественного фасеточного зрения у насекомых, может опираться на мощные нейронные сети и на быструю классификацию образов и объектов в зависимости от их геометрического подобия.
