Решение археологических головоломок


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

Решение головоломки – это NP-полная задача, которая возникает во многих областях. Израильские исследователи Нив Дерех и Айеллет Тал из Техниона и Илан Шимшони из Хайфского университета решили сосредоточиться на археологии:

потому что археологическая область обнажает пределы современных методов компьютерного зрения. Археологические артефакты не «чистые» и «ухоженные»; скорее они сломаны, размыты, зашумлены и, в конечном итоге, чрезвычайно сложны для алгоритмов, которые их анализируют или собирают заново. Таким образом, с точки зрения видения археология представляет собой чрезвычайно сложную прикладную область.

Предложенный ими алгоритм основан на четырех ключевых идеях:

Во-первых, чтобы решить проблему истирания фрагментов, мы предлагаем экстраполировать каждый фрагмент перед повторной сборкой. Это уменьшает проблему непрерывности (предсказание того, как «продолжить» фрагмент), с которой мы сталкиваемся, до проблемы сопоставления. Во-вторых, мы предлагаем метод выборки преобразования, который основан на понятии конфигурационного пространства и специально адаптирован к нашей проблеме. . В-третьих, в основе любого алгоритма решения головоломок лежит вопрос о том, что является хорошим совпадением. Мы предлагаем новую меру, которая учитывает особые характеристики области: промежутки между частями, выцветание цвета, ложные края, тот факт, что длина совпадающей границы варьируется, и неточные преобразования. Наконец, при размещении учитываются не только указанные выше оценки, но и наша уверенность в матче, на которую влияют уникальность матча и размер фрагмента.

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

Более подробная информация представлена в их статье «Решение археологических головоломок», доступной на arXiv.


Добавить комментарий