Доцент Института естественных и точных наук ЮУрГУ, преподаватель центра ОП топ-уровня в сфере ИИ «ВиртУм», кандидат физико-математических наук Евгений Мартюшев вместе с коллегами из Финляндии и Чехии разработал метод автоматического построения решателей систем уравнений, состоящих из полиномов Лорана. В отличие от привычных школьных уравнений, где переменные могут быть только в положительных степенях, лорановские системы допускают и отрицательные степени. Такие системы возникают в инженерных приложениях: при создании и оптимизации алгоритмов технического зрения, навигации беспилотных аппаратов, а также в робототехнике и акустике.
Для эффективного решения лорановских систем уравнений строят «шаблон исключения» – специальную матрицу коэффициентов, оперируя с которой методами линейной алгебры, можно добраться до решений системы. Первые генераторы шаблонов исключения опирались на стандартные средства алгебраической геометрии, такие как базисы Грёбнера и результанты. Однако практика показала, что эмпирические подходы зачастую являются более эффективными. Предложенный учёными метод как раз основан на итерационной эмпирической схеме. Его главное преимущество — универсальность: он позволяет находить решатели даже для систем, имеющих положительно мерные компоненты решений, а также автоматически находить и учитывать некоторые симметрии лорановской системы. При этом от пользователя не требуется глубоких математических знаний — достаточно лишь указать функции для вычисления коэффициентов системы. Генератор сам подберёт несколько вариантов шаблонов, из которых можно выбрать самый быстрый и точный.
«Мы тестировали наш генератор на различных задачах, в основном в геометрическом компьютерном зрении, – пишут в статье Евгений Мартюшев и его коллеги. – Например, это задачи оптимальной трехракурсной триангуляции, гибридной навигации и самокалибровки по времени прихода сигнала. Эксперименты показывают, что наши решатели численно точнее и быстрее существующих аналогов».
Поясним, о каких прикладных задачах идёт речь.
Первая – оптимальная трехракурсная триангуляция. Представим себе, что три камеры с разных ракурсов снимают один и тот же объект (например, архитектурный памятник или сцену для фильма). Чтобы построить его точную 3D-модель, компьютер должен найти точку в пространстве, проекция которой оптимальным образом совмещается со всеми тремя изображениями. Решатель, предложенный учёными, позволяет это сделать быстрее и точнее. Область применения: от спецэффектов в кино до создания цифровых двойников городов.
Вторая задача – гибридная навигация (semi-generalized hybrid pose estimation). Допустим, у нас есть обычная камера на смартфоне и сложная «обобщенная» камера (например, система из нескольких объективов на беспилотном автомобиле). Задача – совместить их данные, чтобы понять, где находится автомобиль относительно смартфона.
Решатель, предложенный Евгением Мартюшевым и его коллегами, справляется с задачей в 20-30 раз быстрее существующих алгоритмов, что может оказаться критически важным при создании инфраструктуры «умных городов», отслеживающих дорожный траффик в реальном времени.
Третья задача – самокалибровка по времени прихода сигнала (time-of-arrival self-calibration). Есть несколько динамиков и микрофонов, расположенных в комнате. Зная только время, за которое звук дошел от динамика к микрофону (time-of-arrival), система должна сама вычислить местоположения всех устройств.
Это необходимо для создания «умных» конференц-залов и систем шумоподавления. Здесь новый метод для конфигураций с четырьмя динамиками и шестью микрофонами (а также с пятью динамиками и пятью микрофонами) оказался в 1,5-1,8 раза быстрее лучших мировых аналогов.
Стоит также отметить, что ранее новый метод был успешно применён в робототехнике для создания эффективного решателя прямой задачи кинематики параллельных манипуляторов.
Работа опубликована в «Международном журнале компьютерного зрения» (International Journal of Computer Vision), входящем в ТОР-1% рейтингов Scopus и Web of Science.
Работа выполнена в рамках реализации программы топ-уровня в сфере искусственного интеллекта при поддержке АНО «Аналитический центр при Правительстве Российской Федерации».
Остап Давыдов