Алгоритм Лукаса — Канаде
Алгоритм Лукаса — Канаде — широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока.
Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса — Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.
Алгоритм Лукаса — Канаде менее чувствителен к шуму на изображениях, чем поточечные методы, однако является сугубо локальным и не может определить направление движения пикселей внутри однородных областей.
Описание алгоритма
Предположим, что смещение пикселей между двумя кадрами невелико. Рассмотрим пиксель p, тогда, по алгоритму Лукаса — Канаде, оптический поток должен быть одинаков для всех пикселей, находящихся в окне с центром в p. А именно, вектор оптического потока ( V x , V y ) {displaystyle (V_{x},V_{y})} в точке p должен быть решением системы уравнений
{ I x ( q 1 ) V x + I y ( q 1 ) V y = − I t ( q 1 ) I x ( q 2 ) V x + I y ( q 2 ) V y = − I t ( q 2 ) . . . I x ( q n ) V x + I y ( q n ) V y = − I t ( q n ) {displaystyle {egin{cases}I_{x}(q_{1})V_{x}+I_{y}(q_{1})V_{y}=-I_{t}(q_{1})I_{x}(q_{2})V_{x}+I_{y}(q_{2})V_{y}=-I_{t}(q_{2})...I_{x}(q_{n})V_{x}+I_{y}(q_{n})V_{y}=-I_{t}(q_{n})end{cases}}}где
q 1 , q 2 , … , q n {displaystyle q_{1},q_{2},dots ,q_{n}} — пиксели внутри окна, I x ( q i ) , I y ( q i ) , I t ( q i ) {displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})} — частные производные изображения I {displaystyle I} по координатам x, y и времени t, вычисленные в точке q i {displaystyle q_{i}} .Это уравнение может быть записано в матричной форме:
A v = b {displaystyle Av=b} ,где
A = [ I x ( q 1 ) I y ( q 1 ) I x ( q 2 ) I y ( q 2 ) ⋮ ⋮ I x ( q n ) I y ( q n ) ] , v = [ V x V y ] , b = [ − I t ( q 1 ) − I t ( q 2 ) ⋮ − I t ( q n ) ] {displaystyle A={egin{bmatrix}I_{x}(q_{1})&I_{y}(q_{1})[10pt]I_{x}(q_{2})&I_{y}(q_{2})[10pt]vdots &vdots [10pt]I_{x}(q_{n})&I_{y}(q_{n})end{bmatrix}},quad quad v={egin{bmatrix}V_{x}[10pt]V_{y}end{bmatrix}},quad quad b={egin{bmatrix}-I_{t}(q_{1})[10pt]-I_{t}(q_{2})[10pt]vdots [10pt]-I_{t}(q_{n})end{bmatrix}}}Полученную переопределенную систему решаем с помощью метода наименьших квадратов. Таким образом, получается система уравнений 2×2:
A T A v = A T b {displaystyle A^{T}Av=A^{T}b} ,откуда
v = ( A T A ) − 1 A T b {displaystyle mathrm {v} =(A^{T}A)^{-1}A^{T}b} ,где A T {displaystyle A^{T}} — транспонированная матрица A {displaystyle A} . Получаем:
[ V x V y ] = [ ∑ i I x ( q i ) 2 ∑ i I x ( q i ) I y ( q i ) ∑ i I x ( q i ) I y ( q i ) ∑ i I y ( q i ) 2 ] − 1 [ − ∑ i I x ( q i ) I t ( q i ) − ∑ i I y ( q i ) I t ( q i ) ] {displaystyle {egin{bmatrix}V_{x}[10pt]V_{y}end{bmatrix}}={egin{bmatrix}sum _{i}I_{x}(q_{i})^{2}&sum _{i}I_{x}(q_{i})I_{y}(q_{i})[10pt]sum _{i}I_{x}(q_{i})I_{y}(q_{i})&sum _{i}I_{y}(q_{i})^{2}end{bmatrix}}^{-1}{egin{bmatrix}-sum _{i}I_{x}(q_{i})I_{t}(q_{i})[10pt]-sum _{i}I_{y}(q_{i})I_{t}(q_{i})end{bmatrix}}}Взвешенное окно
В методе наименьших квадратов все n пикселей q i {displaystyle q_{i}} в окне оказывают одинаковое влияние. Однако логичнее учитывать более близкие к p пиксели с большим весом. Для этого используется взвешенный метод наименьших квадратов,
A T W A v = A T W b {displaystyle A^{T}WAv=A^{T}Wb}или
v = ( A T W A ) − 1 A T W b {displaystyle mathrm {v} =(A^{T}WA)^{-1}A^{T}Wb}где W {displaystyle W} — диагональная матрица n×n, содержащая веса W i i = w i {displaystyle W_{ii}=w_{i}} , которые будут присвоены пикселям q i {displaystyle q_{i}} . Получаем следующую систему уравнений:
[ V x V y ] = [ ∑ i w i I x ( q i ) 2 ∑ i w i I x ( q i ) I y ( q i ) ∑ i w i I x ( q i ) I y ( q i ) ∑ i w i I y ( q i ) 2 ] − 1 [ − ∑ i w i I x ( q i ) I t ( q i ) − ∑ i w i I y ( q i ) I t ( q i ) ] {displaystyle {egin{bmatrix}V_{x}[10pt]V_{y}end{bmatrix}}={egin{bmatrix}sum _{i}w_{i}I_{x}(q_{i})^{2}&sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})[10pt]sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})&sum _{i}w_{i}I_{y}(q_{i})^{2}end{bmatrix}}^{-1}{egin{bmatrix}-sum _{i}w_{i}I_{x}(q_{i})I_{t}(q_{i})[10pt]-sum _{i}w_{i}I_{y}(q_{i})I_{t}(q_{i})end{bmatrix}}}В качестве весов w i {displaystyle w_{i}} обычно используется нормальное распределение расстояния между q i {displaystyle q_{i}} и p.