Введение 4
Глава 1 Обзор существующих методов вычисления
оптического потока 6
§1 Алгоритм Лукаса-Канаде 6
§2 Алгоритм Horn-Schunck 14
§3 Обобщения для предположений постоянства производных . 19
§4 Детали дискретизации 22
Глава 2 Алгоритм построения поля скоростей 24
§1 Смешаный алгоритм Лукаса-Канаде и Horn Schunck 24
§2 Модификация для выделения границ 28
§3 Система линейных уравнений 30
§4 Численные методы решения систем линейных уравнений . . 32
§5 Сходимость блочных методов 33
Глава 3 Программная реализация вычисления оптического
потока 35
§1 Общая схема реализации вычислительной системы 35
§2 Средства реализации 37
§3 Описание жизненного цикла задачи 39
Глава 4 Примеры и анализ работы алгоритмов 42
§1 Пример: движение прямоугольника 42
§2 Пример: сдвиг изображения 47
§3 Пример: сдвиг карты 50
§4 Анализ работы алгоритмов 53
Заключение 58
Список литературы
В настоящее время широкий интерес вызывают задачи распознавания [1-9]. В данной работе рассматривается задача распознавания движения на изображении или на видео. Современные информационные технологии позволяют ускорить методы, которые применяются для решения данной задачи, например, за счет параллельной обработки различных частей видео или изображений из одной временной последовательности.
Целью данной работы является построение прототипа распределенной системы для распознавания движения на видео или последовательности изображений.
В качестве основы можно рассмотреть, семейство методов, основанных на представлении движения на изображении в форме поля скоростей или оптического потока [4-5, 10]. Поле скоростей (оптический поток) - одна из форм представления движения объектов на изображении, при котором каждой точке изображения ставится в соответствие вектор скорости, отвечающий соответствующей точке на объекте. При постановке задачи распознавания движения в форме поиска оптического потока существует несколько методов для ее решения.
1. Фазовая корреляция — основан на инверсия нормализованного перекрестного спектра.
2. Блочные методы — минимизация суммы квадратов или суммы модулей разностей.
3. Группа дифференциальных методов оценки оптического потока, основанных на частных производных:
3.1. Алгоритм Лукаса-Канаде — рассматриваются части изображения и аффинная модель движения.
3.2. Horn-Schunck — минимизация функционала, выражающего пред-положения постоянства цвета объектов на изображении и гладкости полу-
чаемого векторного поля.
3.3. Buxton-Buxton — основан на модели движения границ объектов в последовательности изображений.
4. Общие вариационные методы — модификации метода Horn-Schunck, использующие другие ограничения на данные и другие ограничения на гладкость.
5. Дискретные методы оптимизации — поисковое пространство квантуется, затем каждому пикселю изображения ставится в соответствие метка таким образом, чтобы расстояние между последовательными кадрами было минимальным. Оптимальное решение часто ищется с помощью алгоритмов нахождения минимального разреза и максимального потока в графе, линейного программирования или belief propagation.
В этой работе будут рассматриваться дифференциальные методы оценки поля скоростей, в его основе лежит вычисление частных производных по горизонтальному и вертикальному направлениям изображения. Как будет показано далее, одних только производных недостаточно чтобы определить смещения точек объектов на изображении. Поэтому существует множество модификаций названых алгоритмов, заточенных под определенные частные задачи.
Для построения прототипа распределенной системы для распознавания движения на видео или последовательности изображений в работе решаются следующие задачи:
1. Анализ существующих методов оценки поля скоростей, выбор основного алгоритма
2. Создание распределенной компьютерной реализации алгоритма вычисления поля скоростей на основе облачных технологий.
3. Анализ результатов.
В работе было сделано следующее:
1. Был построен прототип системы распределенного вычисления поля скоростей по видео и последовательности изображений.
2. Было предложено две модификации метода вычисления поля скоростей Horn-Schunck: смешанный алгоритм Horn-Schunck и Лукаса-Канаде и модификация подчеркивания границ.
3. Для смешанного алгоритма Horn-Schunck и Лукаса-Канаде была показана сходимость итерационных методов Якоби, Гаусса-Зейделя и метода последовательной верхней релаксации.
4. На примерах было продемонстрировано, что смешанный алгоритм дает более эффективный результат, чем стандартный метода Horn-Schunck.
Таким образом, цель работы, заключавшаяся в построении системы распределенного вычисления поля скоростей, достигнута.
Построенный прототип системы можно улучшить несколькими способами: ускорить вычислительный процесс, добавив распределение одной задачи на несколько узлов, усовершенствовать применяемый алгоритм, усовершенствовать отказоустойчивость системы при выходе из строя вычислительных узлов.
