Статья закрученные потоки оптические методы. То, что вы хотели знать про оптический поток, но стеснялись спросить

Это представление видимого следа движения объектов, поверхностей и граней визуальной сцены, наблюдается при относительного движения между наблюдателем (например, глаз человека или камера) и сцены.

Понятие оптического потока была предложенное американским психологом Джеймсом Дж. Гибсоном в 1940-х годах для описания визуального стимула (сигнала), что возникает у животных, которые движутся в пространстве относительно окружающей среды.

Джеймс Гибсон подчеркивал важность оптического потока для возможности восприятия, способность различать ограничения и возможности для действий в окружающей обстановке. Последователи робот Гибсона и его экологического подхода к психологии впоследствии смогли показать роль стимула оптического потока для восприятия движения наблюдателя относительно окружающего мира; восприятие формы, дистанции и движения окружающих объектов; и контроль передвижения.

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

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

Расчет

Последовательность из упорядоченных изображений позволяет оценить движение, или в виде мгновенных скоростей изображение, или в виде дискретных величин смещения изображения. Есть материалы в виде урока по методу оптического потока на основе градиентов. Также исследователи проводили анализ сравнения различных техник оптического потока, анализируют точность и частоту измерений.

Методы расчета оптического движения пытаются оценить движение между двумя кадрами изображения, видносятся к моментам времени t и в каждой позиции вокселя. Такие методы называются дифференциальными, так как они основаны на локальных оценках ряда Тейлора для сигнала изображения то есть они используют частные производные по пространственным и временным координатам.

Для случая размерности 2D + t (так же и для 3D или n -D случаев) расположение вокселя с интенсивностью, который будет двигаться на, и между двумя кадрами изображения, и с последующим ограничением постоянства яркости (brightness constancy constraint) можно записать:

Считая, что движение было незначительное, рассчитывая приближения изображения в с помощью рядов Тейлора можно получить:

… (Члены высшего порядка)

Из этих уравнений следует, что:

в результате чего

где это компоненты и скорости или оптического потока и, и являются производными для изображения в в соответствующих направлениях. И далее могут быть записаны для производных.

Таким образом:

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

Датчик оптического потока

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

Одной из сфер современных исследований является использование техники нейроморфнои инженерии для реализации схем, которые воспринимают оптический поток, и таким образом могут быть использованы в качестве оптического датчика. Такие схемы черпают идеи из биологических нейронных сетей, и по схожему принципу воспринимают оптический поток.

Изображения по теме

В системах компьютерного зрения и обработки изображений часто возникает задача определения перемещений объектов в трехмерном пространстве с помощью оптического сенсора, то есть видеокамеры. Имея на входе последовательность кадров, необходимо воссоздать запечатленное на них трехмерное пространство и те изменения, которые происходят с ним с течением времени. Звучит сложно, но на практике зачастую достаточно найти смещения двухмерных проекций объектов в плоскости кадра.

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

Существует несколько подходов к определению смещений между двумя соседними кадрами. Например, можно для каждого небольшого фрагмента (скажем, 8 на 8 пикселей) одного кадра найти наиболее похожий фрагмент на следующем кадре. В этом случае разность координат исходного и найденного фрагментов даст нам смещение. Основная сложность тут состоит в том, как быстро отыскать нужный фрагмент, не перебирая весь кадр пиксель за пикселем. Различные реализации этого подхода так или иначе решают проблему вычислительной сложности. Некоторые настолько успешно, что применяются, например, в распространенных стандартах сжатия видео. Платой за скорость естественно является качество. Мы же рассмотрим другой подход, который позволяет получить смещения не для фрагментов, а для каждого отдельного пикселя, и применяется тогда, когда скорость не столь критична. Именно с ним в литературе часто связывают термин “оптический поток”.

Данный подход часто называют дифференциальным, поскольку в его основе лежит вычисление частных производных по горизонтальному и вертикальному направлениям изображения. Как мы увидим далее, одних только производных недостаточно чтобы определить смещения. Именно поэтому на базе одной простой идеи появилось великое множество методов, каждый из которых использует какую-нибудь свою математическую пляску с бубном, чтобы достичь цели. Сконцентрируемся на методе Лукаса-Канаде (Lucas-Kanade), предложенном в 81 году Брюсом Лукасом и Такео Канаде.

Метод Лукаса-Канаде

В основе всех дальнейших рассуждений лежит одно очень важное и не очень справедливое предположение: Предположим, что значения пикселей переходят из одного кадра в следующий без изменений . Таким образом, мы делаем допущение, что пиксели, относящиеся к одному и тому же объекту, могут сместиться в какую либо сторону, но их значение останется неизменным. Конечно же это предположение имеет мало общего с реальностью, потому что от кадра к кадру могут меняться глобальные условия освещения и освещенность самого движущегося объекта. Масса проблем связана с этим допущением, но, как ни странно, вопреки всему оно достаточно хорошо работает на практике.

На математическом языке это допущение можно записать так: . Где I - это функция яркости пикселей от положения на кадре и времени. Другими словами x и y - это координаты пикселя в плоскости кадра, и - это смещение, а t - это номер кадра в последовательности. Условимся, что между двумя соседними кадрами проходит единичный отрезок времени.

Одномерный случай

Для начала рассмотрим одномерный случай. Представим себе два одномерных кадра 1 пиксель в высоту и 20 пикселей в ширину (рисунок справа). На втором кадре изображение немного смещено вправо. Именно это смещение мы и хотим найти. Для этого представим эти же кадры в виде функций (рисунок слева). На входе позиция пикселя, на выходе - его интенсивность. В таком представление искомое смещение (d) видно еще более наглядно. В соответствии с нашим предположением, это просто смещенная , то есть можем сказать, что .

Обратите внимание, что и при желании можно записать и в общем виде: ; где y и t зафиксированы и равны нулю.

Для каждой координаты нам известны значения и в этой точке, кроме того мы можем вычислить их производные. Свяжем известные значения со смещением d. Для этого запишем разложение в ряд Тейлора для :

Сделаем второе важное предположение: Предположим, что достаточно хорошо аппроксимируется первой производной . Сделав это предположение, отбросим всё что после первой производной:

Насколько это корректно? В общем-то не очень, тут мы теряем в точности, если только наша функция/изображение не строго линейна, как в нашем искусственном примере. Зато это существенно упрощает метод, а для достижения требуемой точности можно сделать последовательное приближение, которе мы рассмотрим позже.

Мы почти у цели. Смещение d - это наша искомая величина, поэтому надо что-то сделать с . Как мы условились ранее, , поэтому просто перепишем:

Двумерный случай

Теперь перейдем от одномерного случая к двумерному. Запишем разложение в ряд Тейлора для и сразу отбросим все старшие производные. Вместо первой производной появляется градиент:

Где - вектор смещения.
В соответствии со сделанным допущением . Обратите внимание, что это выражение эквивалентно . Это то, что нам нужно. Перепишем:

Поскольку между двумя кадрами проходит единичный интервал времени, то можно сказать, что есть не что иное, как производная по времени.
Перепишем:

Перепишем ещё раз, раскрыв градиент:

Мы получили уравнение, которое говорит нам о том, что сумма частных производных должны быть равна нулю. Проблема только в том, что уравнение у нас одно, а неизвестных в нем два: и . На этом моменте начинается полет фантазии и разнообразие подходов.

Сделаем третье предположение: Предположим, что соседние пиксели смещаются на одинаковое расстояние . Возьмем фрагмент изображения, скажем 5 на 5 пикселей, и условимся, что для каждого из 25 пикселей и равны. Тогда вместо одного уравнения мы получим сразу 25 уравнений! Очевидно, что в общем случае система не имеет решения, поэтому будем искать такие и , которые минимизируют ошибку:

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

Чтобы найти минимум воспользуемся методом наименьших квадратов, найдем её частные производные по и :

Перепишем в более компактной форме и приравняем к нулю:

Перепишем эти два уравнения в матричной форме:

Если матрица М обратима (имеет ранг 2), можем вычислить и , которые минимизируют ошибку E:

Вот собственно и все. Мы знаем приблизительное смещение пикселей между двумя соседними кадрами.

Поскольку в нахождении смещения каждого пикселя участвуют также соседние с ним пиксели, при реализации данного метода целесообразно предварительно посчитать производные кадра по горизонтали и вертикали.

Недостатки метода

Описанный выше метод основан на трех значительных допущениях, которые с одной стороны дают нам принципиальную возможность определить оптический поток, но с другой стороны вносят погрешность. Хорошая новость для перфекционистов состоит в том, что одно допущение нужно нам только для упрощения метода, и с его последствиями мы можем бороться. Мы предполагали, что для аппроксимации смещения нам будет достаточно первой производной. В общем случае это конечно же не так (рисунок слева). Для достижение требуемой точности смещение для каждой пары кадров (назовём их и ) можно вычислять итеративно. В литературе это называется искажением (warping). На практике это означает, что, вычислив смещения на первой итерации, мы перемещаем каждый пиксель кадра в противоположную сторону так, чтобы это смещение компенсировать. На следующей итерации вместо исходного кадра мы будем использовать его искаженный вариант . И так далее, пока на очередной итерации все полученные смещения не окажутся меньше заданного порогового значения. Итоговое смещение для каждого конкретного пикселя мы получаем как сумму его смещений на всех итерациях.

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

Ещё одна проблема связана с тем, что некоторые текстуры в изображении дают вырожденную матрицу М, для которой не может быть найдена обратная матрица. Соответственно, для таких текстур мы не сможем определить смещение. То есть движение вроде есть, но непонятно в какую сторону. В общем-то от этой проблемы страдает не только рассмотренный метод. Даже глаз человека воспринимает такое движение не однозначно (Barber pole).

Заключение

Мы разобрали теоретические основы одного из дифференциальных методов нахождения оптического потока. Существует множество других любопытных методов, некоторые из которых по состоянию на сегодняшний день дают более надежные результаты. Однако, метод Лукаса-Канаде при своей неплохой эффективности остается достаточно простым для понимания, а потому хорошо подходит для ознакомления с математическими основами.

Хотя проблема нахождения оптического потока изучается уже несколько десятилетий, методы всё ещё продолжают совершенствоваться. Работа продолжается в виду того, что при близком рассмотрении проблема оказывается очень непростой, а от качества определения смещений в обработке видео и изображений зависит устойчивость и эффективность многих других алгоритмов.

На этой пафосной ноте позвольте закруглиться и перейти к источникам и полезным ссылкам.
метод Лукаса-Канаде

Lucas-Kanade

Добавить метки

Агафонов В.Ю. 1

1 Агафонов Владислав Юрьевич - аспирант кафедры «системы автоматизированного проектирования и поискового конструирования», Волгоградский государственный технический университет,

г. Волгоград

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

Ключевые слова: обработка изображений, поиск смещения изображений

APPLICATION OF OPTICAL FLOW METHODS TO IMAGE SHIFT ESTIMATION

Agafonov V.U. 1

1 Agafonov Vladislav Urevich - post-graduate student of «systems of computer-aided design and search design» department,

Volgograd State Technical University, Volgograd

Abstract: in this article, methods for image shift estimation are described. The first approach is based on minimizing mean squared error when searching for the displacement of image key points. The second approach is based on approximate each neighborhood of both frames by quadratic polynomials, which can be done efficiently using the polynomial expansion transform. The main stages of the implementation of these methods are described. Test sets of images are prepared taking into account the specific nature of the problem. Results of the work are presented.

Keywords: image processing, image shift estimation

УДК 004.932.2

Введение

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

Существует несколько подходов к оценке смещения изображения. Основные их них это: выделение ключевых особенностей на изображении, с последующим сопоставлением ключевых точек, определение фазовой корреляции частотного представления сигнала изображения и оптический поток. Последний в основном его виде не используется для поиска смещений изображений, он используется для определения наличия движения на изображении. Так оптический поток применяют в системах детектирования и трэкинга объектов.

Оптический поток — это структура видимого движения объектов, поверхностей или краев сцены, вызванная относительным движением наблюдателя (глаз или камеры) относительно сцены. Алгоритмы, основанные на оптическом потоке, — такие как регистрация движения, сегментация объектов, кодирование движений, — используют это движение объектов, поверхностей и краев.

В данной работе рассмотрены два подхода, один из которых позволяет получить смещения для отельных ключевых точек, а второй - для каждого отдельного пикселя.

Оптический поток методом Лукаса-Канаде

Основная концепция метода заключается в допущении, что значения пикселей переходят из одного кадра в следующий без изменений:

где. Игнорируя остаточный член, получаем формулу для аппроксимации????:

где и определяет смещение. В соответствии со сделанным допущением получаем, что. Тогда запишем уравнение (4) как

Получается, что сумма частных производных равна нулю. Однако так как мы имеем всего одно уравнение, а неизвестных два, приходится накладывать дополнительные условия. Один из распространенных способов это введение ограничения на близлежащие пиксели. Предположим, что соседние пиксели смещаются одинаково. Очевидно, что не может быть смещения которое удовлетворяет всем пикселям, поэтому минимизируем ошибку методом наименьших квадратов.

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

Приравнивая соответствующие коэффициенты квадратичных полиномов имеем:

Это справедливо для любого сигнала.

Очевидно, что предположение о том, что сигнал можно представить одним полиномом довольно нереалистично. Тем не менее, отношение (10) может быть использовано для реальных сигналов, даже при возникновении ошибок. Основной вопрос в том, являются ли ошибки достаточно маленькими, чтобы алгоритм был полезным.

Заменим глобальное полиномиальное представление локальным. Вычислим коэффициенты полиномов для первого изображения и для второго изображения. В соответствии с (9) должно быть, но на практике используется приближение:

где отражает замещение глобального смещения, пространственно изменяющимся смещением.

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

Основная проблема метода состоит в предположении что полиномы одинаковы, за исключением смещения. Так как локальное полиномиальное разложение многочлена будет изменяться в зависимости от окружения, то это будет вносить ошибку в (11). Для малых смещений это не принципиально, однако с увеличением смещения ошибка возрастает. Если мы имеем априорное знание о смещении, мы можем сравнить два полинома: первый в, второй в, где это априорное смещение, округленное до целого значения. Таким образом мы можем выполнять метод итеративно. Лучшее априорное смещение означает меньшее относительно смещение, которое в свою очередь повышает шансы на хорошую оценку реального смещения .

Применение методов оптического потока к задаче поиска смещений изображений

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

Для метода Лукаса-Канаде необходимо выделить множество ключевых точек, смещение которых необходимо найти. Для этого используется классический метод поиска границ и углов. После получения смещения каждой из этих точек необходимо усреднить полученный результат.

Для метода Фарнебака достаточно усреднить значения смещений в каждом пикселе.

Эксперимент был проведен на выборке из 20 тестовых пар и посчитано среднеквадратическое отклонение для каждого метода.

ОП Лукаса-Канаде
ОП Фарнебака

Таблица 1 - Среднеквадратическое отклонение смещений

Из результатов эксперимента видно, что оба метода оценивают смещение изображений с высокой точностью. Результат метода Фарнебака показывает более плохой результат из-за того, что метод оценивает смещение для всех пикселей и может допускать ошибки на однотонных частях изображения.

Каждый метод имеет свои преимущества и недостатки, а также область применения и ограничения. Метод Лукаса-Канаде реализует разряженный оптический поток и

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

Преимущество оптического потока методом Фарнебака заключается в том, что смещение ищется для каждого пикселя. Однако данный метод также ошибается на периодических и слаботекстурированных объектах, но позволяет оценивать не плоскопараллельное движение.

Заключение

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

Список литературы/ References

1. Fleet D., Weiss Y. Optical flow estimation //Handbook of mathematical models in computer vision. - Springer US, 2006. - С. 237-257.
2. Farnebäck G. Two-frame motion estimation based on polynomial expansion //Image analysis. - 2003. - С. 363-370.

Построение оптического потока традиционно рассматривается как процедура оценки яркостно-геометрических изменений между настоящим (текущим) и предыдущим кадрами. Движение объектов перед неподвижной камерой, также как и движение камеры в окружающей обстановке приводят к соответствующим изменениям на изображении. Кажущееся движение видимого поля (двумерного распределения яркости), наблюдаемое при движении камеры относительно изображаемых объектов или объектов относительно камеры, называется оптическим потоком. Определим поле движения, приписав каждой точке изображения вектор скорости. В некоторый выбранный момент времени точка на изображении соответствует некоторой точке на поверхности объекта. Эти две точки связаны уравнениями проектирования. Точка объекта перемещается относительно камеры со скоростью. Это порождает движение соответствующей точки изображения. За время точка перемещается на расстояние, а ее изображение - на расстояние (см. рис. 1).

Рис. 1.

Яркостные распределения движутся вместе с наблюдаемыми объектами. Оптическим потоком, как уже упоминалось ранее, называется кажущееся движение яркостной картины. В идеале оптический поток соответствует определенному ранее полю движения, однако, на практике это не всегда так.

Пусть теперь - яркость пикселя в точке изображения в момент времени. Тогда, если и - и компоненты вектора оптического потока в этой точке, то можно ожидать, что

Сократим на в левой и правой частях, разделим на и перейдем к пределу при. Получим

Производные легко получить из изображения с помощью численных аппроксимаций производных конечными разностями

Перепишем (4) в виде

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

Задача минимизации функционала (6) решается при помощи итеративной процедуры (7)-(8). Минимизирующая функционал (6) последовательность скоростей имеет вид:

Здесь индекс показывает номер текущей итерации, - индексы текущего узла сетки.

Итерационный процесс заканчивается, когда невязка (9) между двумя последовательными итерациями будет меньше заранее заданного числа:

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

Оптический поток также может оказаться равным нулю там, где поле скоростей не равно нулю. Такой случай, например, встречается при перемещении объекта, характеризующегося постоянной яркостью по всей площади занимаемой области изображения. В данном случае оптический поток, вычисленный на границе объекта, будет ненулевым, а вычисленный в центре объекта будет близок к нулю, в то время истинное как поле скоростей должно быть одинаково на всей поверхности объекта. Данная проблема называется «проблемой апертуры».

Производные яркости изображения предлагается считать следующим образом:

Здесь используется сеточная аппроксимация производных. Индекс показывает номер текущего кадра, - индексы текущего узла сетки. Вариации и при подсчете частных производных (10) можно выбирать любыми. Обычно используется сетка с

Теперь, подставив частные производные (10) и средние скорости (8) в итерационный процесс (7) с начальными условиями, для всех из области, легко найти скорости всех точек сетки на наблюдаемых кадрах видеопоследовательности.

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

Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

Что же такое оптический поток

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

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

Есть два варианта расчета оптического потока: плотный (dense) и выборочный (sparse). Sparse поток рассчитывает сдвиг отдельных заданных точек (например, точек, выделенных некоторым feature detector"ом), dense поток считает сдвиг всех точек изображения. Естественно, выборочный поток вычисляется быстрее, однако для некоторых алгоритмов разница не такая уж и большая, а для некоторых задач требуется нахождение потока во всех точках изображения.

Для вырожденных случаев можно применять более простые методы определения сдвига. В частности, если все точки изображения имеют один и тот же сдвиг (изображение сдвинуто целиком), то можно применить метод фазовой корреляции: вычислить преобразование Фурье для обоих изображений, найти свертку их фаз и по ней определить сдвиг (см. en.wikipedia.org/wiki/Phase_correlation). Также можно применять поблочное сравнение (block matching): находить сдвиг, минимизирующий норму разности изображений в окне. В чистом виде такой алгоритм будет работать долго и неустойчиво к поворотам и прочим искажениям. Английская википедия причисляет перечисленные алгоритмы к различным вариантам вычисления оптического потока, но мне это кажется не слишком корректным, так как эти алгоритмы могут быть применены и в других целях и не полностью решают данную задачу. Мы будем называть оптическим потоком методы, основанные на локальных характеристиках изображений (то, что в английской википедии называется differential methods).

Стандартный подход (метод Лукаса-Канаде)

Математическое описание алгоритма достаточно подробно приведено в этой статье , но в ней затрагиваются лишь теоретические аспекты.

Рассмотрим математическую модель оптического потока, считая, что у точки в результате смещения не изменилась интенсивность.

Пусть – интенсивность в некоторой точке (x, y) на первом изображении (т. е. в момент времени t). На втором изображении эта точка сдвинулась на (dx, dy), при этом прошло время dt, тогда – это мы разложили по Тейлору функцию интенсивности до первого члена (позже будет упомянуто, почему только до первого), здесь – частные производные по координатам и времени, то есть по сути – изменение яркости в точке (x, y) между двумя кадрами.

Мы считаем, что у точки сохранилась интенсивность, значит
Получаем одно уравнение с двумя неизвестными (dx и dy), значит его недостаточно для решения, то есть только на этом уравнении далеко не уедешь.

Самое простое решение проблемы – алгоритм Лукаса-Канаде. У нас же на изображении объекты размером больше 1 пикселя, значит, скорее всего, в окрестности текущей точки у других точек будут примерно такие же сдвиги. Поэтому мы возьмем окно вокруг этой точки и минимизируем (по МНК) в нем суммарную погрешность с весовыми коэффициентами, распределенными по Гауссу, то есть так, чтобы наибольший вес имели пиксели, ближе всего находящиеся к исследуемому. После простейших преобразований, получаем уже систему из 2 уравнений с 2 неизвестными:

Как известно, эта система имеет единственное решение не всегда (хотя и очень часто): если детерминант системы равен нулю, то решений либо нет, либо бесконечное число. Эта проблема известна как Aperture problem – неоднозначность сдвига при ограниченном поле зрения для периодических картинок. Она соответствует случаю, когда в поле зрения попадает фрагмент изображения, в котором присутствует некоторая цикличность; тут уж и человек не сможет однозначно определить, куда картинка сместилась. Проблема в том, что из-за шумов в таких неоднозначных ситуациях мы получим не нулевой детерминант, а очень маленький, который, скорее всего, приведет к очень большим значениям сдвига, особо не коррелирующим с действительностью. Так что на определенном этапе нужно просто проверять, не является ли детерминант системы достаточно маленьким, и, если что, не рассматривать такие точки или отмечать их как ошибочные.

Почему не работает?

Если мы остановимся на этом этапе и реализуем этот алгоритм, то он будет успешно работать. Но только если сдвиг между соседними изображениями будет очень маленький, порядка 1 пикселя, и то не всегда. (Для анализа качества генерировались синтетические последовательности с различным относительным сдвигом, причем этот сдвиг может выражаться нецелым числом пикселей, тогда результирующее изображение соответствующим образом интерполируется) Уже на сдвиге в 2 пикселя погрешность будет большая, а если 3 и более, то результат будет вообще неадекватным. В чем же дело?

Тут нам устроила подставу математика. Она привила нам ощущение, что все функции вокруг непрерывные и много раз дифференцируемые. И вообще нас в институте приучили приближение функции в окрестности точки записывать с помощью формулы Тейлора, и мы везде бездумно радостно пользуемся этим. А теперь задумаемся, какой физический смысл производных в данном месте? Мы хотим с их помощью определить изменение значения функции в конечной окрестности точки, а производная дает представление о бесконечно малой окрестности. Для расширения этой окрестности можно было бы добавить более высокий порядок производных в разложение Тейлора, но это приведет к нелинейностям в системе, от чего ее станет существенно сложнее решать, а преимущества будут сомнительны, тем более что на практике мы имеем дело не с непрерывными многократно дифференцируемыми функциями, а с вообще непонятно какими дискретными функциями. Поэтому логичнее будет искать функцию g(x), для которой в нашем дискретном случае как можно точнее выполняется f(x) + g(x) = f(x+1), f(x) + 2g(x) = f(x+2), f(x) - g(x) = f(x-1), и т. д. Таким образом, нам в этом случае нужна не производная, а некоторая линейная функция, наиболее близко лежащая к точкам исходной функции. Простые математические выкладки приводят к решению , где . Если мы строили производную по одной соседней точке с каждой стороны, то нам повезло: в этом случае формула совпадает с формулой приближенного вычисления производных: g(x) = (f(x+1) – f(x-1)) / 2. Что характерно, в OpenCV при вычислении оптического потока Лукаса-Канаде используется именно такая формула, к этому мы еще вернемся потом. А вот если взять больше точек, то формула уже становится совсем не похожа на классические разностные схемы для первой производной.

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

Другим слабым местом алгоритма является то, что мы опять же имеем дело не с гладкими непрерывными функциями, а с произвольными, да еще и дискретными. Поэтому на некоторых фрагментах изображения интенсивность может «скакать» вообще без явных закономерностей, например на границах объектов, или из-за шумов. В этом случае никакая функция g(x) не сможет достаточно точно описать изменения изображения в окрестности точки. Чтобы с этим побороться (хотя бы частично), предлагается исходное изображение размазать, причем полезно будет его размазать достаточно сильно, то есть лучше применять даже не всеми любимый gaussian blur (усреднение с весовыми коэффициентами), а прямо таки box filter (равномерное усреднение по окну), да еще и несколько раз подряд. Гладкость изображения для нас сейчас важнее, чем детализация.

Тем не менее, эти меры так же не спасут нас от ограничения детектируемого сдвига в 2-3 пикселя. И кстати, в OpenCV 1.0 присутствовала такая реализация оптического потока, и работала она только в идеальных условиях на очень маленьких сдвигах.

Что же делать?

Итого, обычный Лукас-Канаде хорошо определяет маленькие сдвиги, такие, в рамках которых картинка похожа на свое линейное приближение. Чтобы с этим побороться, воспользуемся стандартным приемом CV – multi-scaling"ом: построим «пирамиду» изображений разного масштаба (почти всегда берется масштабирование в 2 раза по каждой оси, так проще считать) и пройдем по ним оптическим потоком от меньшего изображения к большему, тогда детектированный маленький сдвиг на маленьком изображении будет соответствовать большому сдвигу на большом изображении. На самом маленьком изображении мы обнаруживаем сдвиг не более 1-2 пикселей, а переходя от меньшего масштаба к большему, мы пользуемся результатом с предыдущего шага и уточняем значения сдвига. Собственно, в OpenCV его и реализует функция calcOptFlowPyrLK. Использование этого пирамидального алгоритма позволяет нам не заморачиваться вычислением линейной аппроксимации по многим точкам: проще взять больше уровней пирамиды, а на каждом уровне брать довольно грубое приближение этой функции. Поэтому в OpenCV и идет расчет всего по двум соседним точкам. И поэтому применительно к этой реализации алгоритма наши умозаключения про преимущество аппроксимирующей функции перед производной оказались бесполезными: для такого количества опорных точек производная и есть лучшая аппроксимирующая функция.

А какие еще бывают?

Этот алгоритм не является единственным вариантом вычисления оптического потока. В OpenCV кроме потока Лукаса-Канаде есть еще поток Farneback и SimpleFlow, также часто ссылаются на алгоритм Horn–Schunck.

Метод Horn–Schunck носит несколько более глобальный характер, чем метод Лукаса-Канаде. Он опирается на предположение о том, что на всем изображении оптический поток будет достаточно гладким. От того же самого уравнения предлагается перейти к функционалу , то есть добавить требование на отсутствие резкого изменения сдвигов с весовым коэффициентом α. Минимизация этого функционала приводит нас к системе из двух уравнений:

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

В данном алгоритме тоже предлагают использовать multi-scaling, причем рекомендуют масштабировать изображения не в 2 раза, а с коэффициентом 0.65

Этот алгоритм был реализован в первых версиях OpenCV, но в последствии от него отказались.

Farneback предложил аппроксимировать изменение интенсивности в окрестности с помощью квадратичной формы: I = xAx + bx + c с симметричной матрицей A (по сути, рассматривая разложение по Тейлору до первого члена, мы брали линейную аппроксимацию I = bx + c, то есть сейчас мы как раз решили повысить точность приближения) Если изображение сдвинулось в пределах этой окрестности, то , подставляем в квадратичное разложение, раскрываем скобки, получаем


.

Теперь мы можем вычислить значения A, b, c на обеих картинках, и тогда эта система станет избыточной относительно d (особенно смущает первое уравнение), и вообще d можно получить из второго уравнения: . Приходится прибегать к следующей аппроксимации: . Обозначим еще для простоты , Тогда получим просто .

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

Как обычно, у этого алгоритма есть некоторое количество модификаций и усовершенствований, в первую очередь позволяющих использовать известную априорную информацию – заданную начальную аппроксимацию потока – и, опять же, multi-scaling.

В основе метода SimpleFlow лежит следующая идея: если мы все равно не умеем определять сдвиг больше чем размер окна, по которому мы искали производные, то зачем вообще заморачиваться с вычислением производных? Давайте просто в окне найдем наиболее похожую точку! А для разрешения неоднозначностей и для компенсации шумов учтем, что поток непрерывный и в окрестности данной точки все точки имеют почти одинаковый сдвиг. А проблему с размером окна опять же решим за счет multi-scaling"а.

Более строго, алгоритм звучит так: для всех точек в окне находится функция «энергии», отвечающая (с обратной логарифмической зависимостью) за вероятность перехода исходной точки в эту точку: . Далее, считается свертка этой энергии с гауссовым окном и находятся значения (dx,dy), минимизирующие эту функцию. Чтобы получить субпиксельную точность, рассматривается малая окрестность найденной оптимальной точки (dx,dy) и в ней ищется пик функции энергии как пик параболоида. И, как было упомянуто выше, эта процедура выполняется для пирамиды масштабированных изображений. Еще у них в алгоритме предложены хитрые методы ускорения расчетов, но это уже кому интересно разберутся сами. Для нас же важно, что за счет этого данный алгоритм является (теоретически) достаточно быстрым при неплохой точности. И у него нет такой проблемы, как у предыдущих, что чем больше сдвиг, тем хуже он детектируется.

А если брать не интенсивность?

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

Практика

Давайте опробуем на практике алгоритмы, которые нам предлагает OpenCV.

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

Подробно синтаксис процедур описан на странице с мануалом , здесь я приведу выжимку-перевод с моими комментариями.

Классический Лукас-Канаде реализован с пирамидой в процедуре calcOpticalFlowPyrLK. Алгоритм рассчитывает sparse-поток, то есть для заданного набора точек на первом изображении оценивает их положение на втором. Входные параметры достаточно очевидны: два входных изображения, входной и выходной наборы точек, status – выходной вектор, показывающий, найдена ли успешно соответствующая точка, err – выходной вектор оцененных погрешностей соответствующих точек, WinSize – размер окна, по которому происходит гауссово усреднение, я брал 21х21 и работало хорошо, maxLevel – количество слоев в пирамиде минус один, т. е. номер последнего слоя, я брал 5, criteria – условие выхода из итеративного процесса определения сдвига (минимизация погрешности производится итеративно) – этот параметр я оставлял по умолчанию, flags – дополнительные флаги, например можно использовать начальное приближение потока или выбрать метод оценки погрешности, minEigThreshold – пороговое значение градиента, ниже которого матрица считается вырожденной, я оставлял по умолчанию. Начиная с OpenCV 2.4.1, при вычислении потока можно использовать заранее вычисленную пирамиду отмасштабированных изображений.

Результат работы – успешно и стабильно обнаруживаются как малые, так и большие сдвиги, устойчив к довольно большим шумам, время работы – порядка 10 мс для 400 точек c 5-слойной пирамидой (на core i7 950).

Кстати, этот алгоритм реализован так же на Gpu (CUDA), причем как dense, так и sparse версии.

Поток Farneback реализуется процедурой calcOpticalFlowFarneback, рассчитывается dense-поток, то есть сдвиг каждой точки. Параметры: входные изображения, выходной поток в формате двухканальной матрицы float"ов, pyr_scale определяет отношение масштабов между слоями пирамиды, levels – количество уровней в пирамиде, winsize – размер окна, по которому производится усреднение, iterations – количество итераций на каждом уровне, poly_n – размер полинома, по которому оцениваются значения A и b, poly_sigma – сигма гауссовского размытия при сглаживании производных, рекомендованные значения параметров указаны в мануале, flags – дополнительные флаги, например можно использовать начальное приближение потока или по-другому усреднять по окну.

Этот алгоритм куда менее стабилен (по моим наблюдениям), легче промахивается на довольно равномерных картинках (видимо, проблема в отсутствии фильтрации неудачных точек), плохо определяет большие сдвиги. У меня отрабатывал за 600 мс на изображении 512х512.

Поток SimpleFlow реализует процедура calcOpticalFlowSF (рассчитывается опять же dense поток), и у нее есть множество загадочных параметров без дефолтных значений, и вообще на данный момент на странице информация предоставлена весьма лаконично. Попробуем разобраться. Первые 3 – входные изображения и выходное двухканальное; layers – количество слоев в пирамиде, то есть сколько раз масштабируем исходное изображение; averaging_block_size – размер окна, в котором мы считали функцию энергии пикселей; max_flow – максимальный сдвиг, который мы хотим уметь определять на каждом шаге, по сути он определяется размером окна (хотя не совсем понятно, почему он int). На этом можно остановиться, а можно задать еще несколько параметров, смысл некоторых из них от меня ускользает.

На сайте предлагают посмотреть пример его использования, в котором он запускается с такими параметрами: calcOpticalFlowSF(frame1, frame2, flow, 3, 2, 4, 4.1, 25.5, 18, 55.0, 25.5, 0.35, 18, 55.0, 25.5, 10);

У меня алгоритм работает значительно медленнее других, порядка 9-12 секунд на картинку 512х512. Результат работы кажется более правдоподобным, чем Farneback, по крайней мере лучше определяется сдвиг на равномерных картинках, заметно лучше срабатывает с большими сдвигами.

Выводы

Если вы хотите использовать где-то оптический поток, сначала подумайте, нужен ли он вам: часто можно обойтись более простыми методами. Браться реализовывать поток самостоятельно стоит только несколько раз подумав: каждый алгоритм имеет множество хитростей, тонкостей и оптимизаций; что бы вы ни сделали, скорее всего, в OpenCV оно же работает лучше (естественно, при условии, что оно там есть). Тем более что они там вовсю используют логические и хардварные оптимизации типа использования SSE инструкций, многопоточность, возможности вычисления с CUDA или OpenCL и т. д. Если вам достаточно посчитать сдвиг некоторого набора точек (т. е. sparse поток), то можете смело использовать функцию calcOpticalFlowPyrLK, оно работает хорошо, надежно и достаточно быстро. Для вычисления dense-потока хорошо использовать функцию calcOpticalFlowSF, но она работает очень медленно. Если быстродействие критично, то calcOpticalFlowFarneback, но надо еще удостовериться, что результаты его работы вас устроят. Добавить метки