Команда исследователей из Техниона и Университета Хайфы разработала новый подход к решению археологических пазлов с помощью компьютерных систем. В своей статье, предварительно опубликованной на arXiv, ученые рассматривают общий алгоритм, который может автоматически собирать фрагменты археологических артефактов.
«Решение подобных головоломок являлось интригующей проблемой на протяжении многих лет. Наш алгоритм имеет множество областей применения – его можно использовать в редактировании изображений, археологии, биологии и даже сборе измельченных документов», – пишут ученые в размещенном материале.
Исследователи пытались разработать инструменты, способные автоматически собирать пазлы, на протяжении десятилетий. Первый вычислительный алгоритм, представленный еще в 1964 году, мог решать головоломки, состоящие из девяти частей. Сегодня большинство современных методов сбора пазлов предназначены для работы с естественными изображениями с возможностью сопоставления цветов и формы или их комбинаций.
Специалисты из Техниона и Университета Хайфы решили сосредоточиться на решении головоломок в области археологии. На момент обнаружения большинство археологических артефактов находятся в плохом или фрагментарном состоянии. Поэтому археологам приходится вручную собирать эти фрагменты, чтобы потом тщательно изучить цельные предметы. Компьютерные инструменты могут значительно упростить этот сложный и трудоемкий процесс за счет автоматизации решения археологических пазлов.
«Мы решили сконцентрировать внимание на археологии не только потому, что сохранение культурного наследие является важной целью во всех странах мира, но и из-за возможности ею открыть пределы современных методов машинного зрения. Археологические артефакты редко сохраняются в идеальном состоянии – чаще всего они разбиты на мелкие фрагменты, а изображения на них трудноразличимы. Поэтому далеко не каждый алгоритм может собрать их заново. Следовательно, археология является одной из наиболее сложных областей применения данной технологии», – отметили специалисты в своей статье.
Исследователи разработали подход, который направлен на нахождение трех основных различий между квадратными кусочками естественных изображений и изображений археологических артефактов, связанных с истиранием, выцветанием и непрерывностью. У древних объектов истирание нередко создает разрывы между частями, затрудняя сопоставление соседних фрагментов.
Кроме того, выцветание может привести к появлению ложных краев, которые необходимо отличать от реальных краев и градиентов. Наконец, в пазлах с естественным изображением у одной пары квадратных кусочков имеется фиксированное количество преобразований, а у археологических артефактов преобразования связаны с непрерывным пространством, что еще сильнее усложняет решение головоломки.
«Мы разработали новый алгоритм, который способен справиться со всеми этими трудностями. Он основан на четырех ключевых идеях. Во-первых, для решения проблемы истирания мы предлагаем экстраполировать каждый фрагмент перед повторной сборкой. Это уменьшает проблему непрерывности, подсказывая системе, как “продолжить” фрагмент. Во-вторых, мы используем метод выборки преобразования, который основан на конфигурационном пространстве и специально адаптирован к нашей проблеме», – отметили исследователи.
По словам специалистов, в основе любого решения пазла лежит вопрос: на чем базируется хорошее совпадение элементов? Чтобы ответить на него, они использовали новую меру, которая учитывает уникальные характеристики археологических головоломок, включая разрывы между кусочками, выцветание, ложные края, различную длину совпадающих границ и неточные преобразования. Кроме того, их алгоритм размещает фигуры, основываясь на уверенности в том, что они совпадают. Эта уверенность базируется на вероятности совпадения и размере фрагмента.
Ученые проверили свой алгоритм на десятках реальных археологических объектах из Британского музея и фресках из церквей по всему миру. Они обнаружили, что он практически идеально выполнял свою работу, правильно собирая подавляющее большинство разбитых артефактов.