|
Информатика, вычислительная техника и управление
Алгоритм полиномиальной сложности для поиска соответствующих точек на основе эпиполярной геометрии
С. А. Тушев, Б. М. Суховилов Южно-Уральский государственный университет (454080 Челябинск, пр. им. В.И. Ленина, д. 76)
Аннотация:
Задача установления соответствий между изображениями точек на различных снимках является основой многих базовых алгоритмов компьютерного зрения. Существуют несколько подходов к решению данной задачи: на основе дескрипторов, на основе эпиполярной геометрии и комбинированные методы. В настоящей статье рассматриваются методы поиска соответствующих точек, основанные на эпиполярной геометрии, применительно к разрабатываемой авторами фотограмметрической измерительной системе (ФИС), использующей искусственные световозвращающие однотипные круговые маркеры (мишени) в роли контрольных точек. В качестве математической модели для задачи нахождения соответствий авторами предлагается использовать взвешенный многодольный неориентированный граф, множество вершин в котором соответствует множеству изображений искусственных маркеров (мишеней) на снимках, а множество ребер определяет множество изображений, взаимно удовлетворяющих эпиполярным ограничениям. Представлено теоретически точное решение задачи на основе суперклики. Выполнена оценка временной сложности решения задачи через суперклику; показано, что данный подход является экспоненциально сложным. Рассмотрены варианты применения различных эвристических алгоритмов установления соответствий между точками. Подобные алгоритмы не всегда приводят к точному результату, однако способны сформировать приближенное решение за практически приемлемое время. Благодаря особой архитектуре, разработанной авторами ФИС, становится возможным использование быстрых приближенных алгоритмов; возможные неточности будут автоматически нейтрализованы на дальнейших этапах работы ФИС. Подобный подход позволяет восстанавливать точную трехмерную структуру измеряемой сцены за приемлемое время. Авторами предложен новый полиномиальный параллельный алгоритм поиска соответствующих точек. Оценена временная сложность разработанного алгоритма (полином 4-й степени). Выполнена сравнительная оценка производительности и эффективности нового алгоритма, в качестве алгоритмов сравнения выступают более ранние алгоритмы авторов, а также алгоритм H.-G. Maas. Новый алгоритм превосходит по производительности все конкурирующие алгоритмы.
Ключевые слова:
фотограмметрия, компьютерное зрение, поиск соответствующих точек, поиск наибольшей клики, эпиполярная геометрия, полиномиальные алгоритмы, стереозрение.
Поступила в редакцию: 03.12.2018
Образец цитирования:
С. А. Тушев, Б. М. Суховилов, “Алгоритм полиномиальной сложности для поиска соответствующих точек на основе эпиполярной геометрии”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 7:4 (2018), 83–104
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyurv201 https://www.mathnet.ru/rus/vyurv/v7/i4/p83
|
Статистика просмотров: |
Страница аннотации: | 122 | PDF полного текста: | 47 | Список литературы: | 22 |
|