Оптимизация энергии в задачах компьютерного зрения и алгоритмы на графах

Задачи компьютерного зрения, как и многие другие обратные задачи, часто решаются с помощью энергетической оптимизации. Для этого каждому возможному ответу в задаче приписывается функция энергии, которая измеряет насколько хорошо данный ответ соответствует имеющимся нечетким данным (например, значению пикселей изображения), а также нашим априорным представлениям. Сама задача тогда сводится к оптимизации, т.е. нахождению минимума энергии и соответствующего ему ответа.

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