Метод Лукаса – Канаде - Lucas–Kanade method

В компьютерное зрение, то Метод Лукаса – Канаде широко используемый дифференциальный метод для оптический поток оценка разработана Брюс Д. Лукас и Такео Канаде. Предполагается, что поток практически постоянен в локальной окрестности пиксель рассматриваемого, и решает основные уравнения оптического потока для всех пикселей в этой окрестности с помощью критерий наименьших квадратов.^[1]^[2]

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

Концепция

Метод Лукаса-Канаде предполагает, что смещение содержимого изображения между двумя соседними моментами (кадрами) мало и примерно постоянно в пределах окрестности точки. п на рассмотрении. Таким образом уравнение оптического потока можно предположить, что он сохраняется для всех пикселей в окне с центром в п. А именно, вектор потока (скорости) локального изображения ${displaystyle (V_ {x}, V_ {y})}$ должен удовлетворить

{displaystyle I_ {x} (q_ {1}) V_ {x} + I_ {y} (q_ {1}) V_ {y} = - I_ {t} (q_ {1})}

{displaystyle I_ {x} (q_ {2}) V_ {x} + I_ {y} (q_ {2}) V_ {y} = - I_ {t} (q_ {2})}

{displaystyle vdots}

{displaystyle I_ {x} (q_ {n}) V_ {x} + I_ {y} (q_ {n}) V_ {y} = - I_ {t} (q_ {n})}

куда ${displaystyle q_ {1}, q_ {2}, точки, q_ {n}}$ - пиксели внутри окна, и ${displaystyle I_ {x} (q_ {i}), I_ {y} (q_ {i}), I_ {t} (q_ {i})}$ частные производные изображения ${displaystyle I}$ по положению Икс, у и время т, оценивается в точке ${displaystyle q_ {i}}$ и в настоящее время.

Эти уравнения можно записать в виде матрица форма ${displaystyle Av = b}$ , куда

{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 quad v = {egin {bmatrix} V_ { x} [10pt] V_ {y} end {bmatrix}} quad quad 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

{displaystyle A ^ {T} Av = A ^ {T} b}

или же

{displaystyle mathrm {v} = (A ^ {T} A) ^ {- 1} A ^ {T} b}

куда ${displaystyle A ^ {T}}$ это транспонировать матрицы ${displaystyle A}$ . То есть вычисляет

{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_ {y} (q_ {i}) I_ {x} (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}}}

где центральная матрица в уравнении является Обратная матрица. Суммы бегут от я= От 1 до п.

Матрица ${displaystyle A ^ {T} A}$ часто называют структурный тензор изображения в точке п.

Взвешенное окно

Приведенное выше простое решение методом наименьших квадратов придает одинаковую важность всем п пиксели ${displaystyle q_ {i}}$ в окне. На практике обычно лучше придавать больший вес пикселям, расположенным ближе к центральному пикселю. п. Для этого используется взвешенная версия уравнения наименьших квадратов,

{displaystyle A ^ {T} WAv = A ^ {T} Wb}

или же

{displaystyle mathrm {v} = (A ^ {T} WA) ^ {- 1} A ^ {T} Wb}

куда ${displaystyle W}$ является п×п диагональная матрица содержащий веса ${displaystyle W_ {ii} = w_ {i}}$ присваивается уравнению пикселя ${displaystyle 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} {начало {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}) конец {bmatrix}}}

Вес ${displaystyle w_ {i}}$ обычно устанавливается на Функция Гаусса расстояния между ${displaystyle q_ {i}}$ и п.

Условия и методы использования

Чтобы уравнение ${displaystyle A ^ {T} Av = A ^ {T} b}$ быть разрешимым, ${displaystyle A ^ {T} A}$ должен быть обратимым, или ${displaystyle A ^ {T} A}$ собственные значения удовлетворяют ${displaystyle lambda _ {1} geq lambda _ {2}> 0}$ . Чтобы избежать шума, обычно ${displaystyle lambda _ {2}}$ требуется, чтобы он не был слишком маленьким. Кроме того, если ${displaystyle lambda _ {1} / lambda _ {2}}$ слишком большой, это означает, что точка п находится на грани, и этот метод страдает проблема диафрагмы. Итак, чтобы этот метод работал правильно, необходимо, чтобы ${displaystyle lambda _ {1}}$ и ${displaystyle lambda _ {2}}$ достаточно велики и имеют одинаковую величину. Это условие также подходит для Обнаружение углов. Это наблюдение показывает, что можно легко определить, какой пиксель подходит для работы с методом Лукаса – Канаде, изучив одно изображение.

Одно из основных предположений для этого метода заключается в том, что движение небольшое (например, менее 1 пикселя между двумя изображениями). Если движение велико и нарушает это предположение, один из способов - сначала уменьшить разрешение изображений, а затем применить метод Лукаса-Канаде.^[3]

Чтобы достичь отслеживание движения с помощью этого метода вектор потока можно итеративно применять и пересчитывать до тех пор, пока не будет достигнут некоторый порог, близкий к нулю, после чего можно предположить, что окна изображений очень похожи.^[1] Делая это для каждого последующего окна отслеживания, точку можно отслеживать на нескольких изображениях в последовательности, пока она не станет затемненной или выйдет за пределы кадра.

Улучшения и расширения

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

Сам по себе метод Лукаса – Канаде можно использовать только тогда, когда вектор потока изображения ${displaystyle V_ {x}, V_ {y}}$ между двумя кадрами достаточно мало для выполнения дифференциального уравнения оптического потока, которое часто меньше расстояния между пикселями. Когда вектор потока может превышать этот предел, например, при стереосопоставлении или регистрации искаженного документа, метод Лукаса – Канаде все же может использоваться для уточнения некоторой приблизительной оценки того же самого, полученной другими способами; например, по экстраполяция векторы потока, вычисленные для предыдущих кадров, или путем выполнения алгоритма Лукаса-Канаде на уменьшенных версиях изображений. Действительно, последний метод лежит в основе популярных Канаде-Лукас-Томази (KLT) алгоритм сопоставления признаков.

Аналогичный метод можно использовать для вычисления дифференциального аффинный деформации содержимого изображения.

Смотрите также

внешняя ссылка

Плагин стабилизатора изображения для ImageJ на основе метода Лукаса – Канаде
Mathworks Лукас-Канаде Реализация в Matlab обратного и нормального аффинный Лукас-Канаде
ФолькиГПУ: Реализация на графическом процессоре итеративного оптического потока на основе Лукаса-Канаде
KLT: Реализация трекера функций Канаде – Лукаса – Томаси
Такео Канаде
Пример C ++ с использованием алгоритма оптического потока Лукаса-Канаде
Пример Python с использованием алгоритма оптического потока Лукаса-Канаде
Пример Python использование трекера Lucas-Kanade для сопоставления гомографии
Быстрый пример MATLAB метода Лукаса-Канаде для отображения поля оптического потока
Быстрый пример MATLAB метода Лукаса-Канаде для отображения вектора скорости объектов

[LKproc-1] а ^б Б. Д. Лукас и Т. Канаде (1981), Методика итеративной регистрации изображений с приложением к стереозрению. Труды семинара по пониманию изображений, страницы 121--130

[Lthesis-2] Брюс Д. Лукас (1984) Обобщенное сопоставление изображений методом различий (докторская диссертация)

[iteraLK-3] Ж. И. Буге, (2001) . Пирамидальная реализация аффинного описания алгоритма в трекере функций Лукаса Канаде. Корпорация Intel, 5.

[1]

[2]

[3]