В.Н. Карнаухов, В.И. Кобер, М.Г. Мозеров, Л.В. Зимина

Динамическое программирование на многомерной решетке и быстрый алгоритм поиска минимума энергии в задачах стерео и оптического потока

В данной работе представлен алгоритм рекурсивного минимального поиска (РМП), значительно снижающий вычислительную сложность задачи поиска минимума. Упомянутое сокращение особенно существенно, если пространство поиска определено на многомерной решетке 2D или 3D. Предложенный метод может быть применен в хорошо известном подходе динамического программирования (ДП) для стерео и оптического потока. В этом случае общая двумерная задача глобальной дискретной минимизации энергии сводится к нескольким взаимно независимым подзадачам одномерной минимизации и для каждой подзадачи получается точное решение. В этой статье также представлена новая модификация методов ДП, которую мы называем расширенным динамическим программированием (РДП) для минимизации энергии. Метод РДП используется, если рассматривается аппроксимация общей двумерной дискретной задачи минимизации энергии. В этом случае предлагаемый алгоритм рекурсивного минимального поиска (РМП) является существенной частью метода РДП. Использование алгоритма РДП позволяет находить решение с более низкими значениями энергии, чем известный алгоритм максимального потока на графе.

KEYWORDS: динамическое программирование, минимизация энергии, стерео, оптический поток