Алгоритм Лукаса — Канаде

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Лукаса — Канаде — широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока.

Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса — Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.[1][2]

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


Описание алгоритма[править | править вики-текст]

Предположим, что смещение пикселей между двумя кадрами невелико. Рассмотрим пиксель p, тогда, по алгоритму Лукаса — Канаде, оптический поток должен быть одинаков для всех пикселей, находящихся в окне с центром в p. А именно, вектор оптического потока в точке p должен быть решением системы уравнений

где

— пиксели внутри окна,
— частные производные изображения по координатам x, y и времени t, вычисленные в точке .

Это уравнение может быть записано в матричной форме:

,

где

Полученную переопределенную систему решаем с помощью метода наименьших квадратов. Таким образом, получается система уравнений 2×2:

,

откуда

,

где транспонированная матрица . Получаем:

Взвешенное окно[править | править вики-текст]

В методе наименьших квадратов все n пикселей в окне оказывают одинаковое влияние. Однако логичнее учитывать более близкие к p пиксели с большим весом. Для этого используется взвешенный метод наименьших квадратов,

или

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130
  2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation)

Ссылки[править | править вики-текст]