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

Метод компьютерного зрения для оценки оптического потока

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

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

Концепция

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

$${\displaystyle {\begin{aligned}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})\\&\;\ \vdots \\I_{x}(q_{n})V_{x}+I_{y}(q_{n})V_{y}&=-I_{t}(q_{n})\end{aligned}}}$$

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

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

$${\displaystyle A={\begin{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={\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}\quad \quad \quad b={\begin{bmatrix}-I_{t}(q_{1})\\[10pt]-I_{t}(q_{2})\\[10pt]\vdots \\[10pt]-I_{t}(q_{n})\end{bmatrix}}}$$

В этой системе больше уравнений, чем неизвестных, и поэтому она обычно переопределена. Метод Лукаса-Канаде позволяет получить компромиссное решение по принципу наименьших квадратов . А именно, он решает систему ${\displaystyle 2\times 2}$

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

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

​ ${\displaystyle A^{T}}$ ${\displaystyle A}$

$${\displaystyle {\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{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}{\begin{bmatrix}-\sum _{i}I_{x}(q_{i})I_{t}(q_{i})\\[10pt]-\sum _{i}I_{y}(q_{i})I_{t}(q_{i})\end{bmatrix}}}$$

обратная матрица ${\displaystyle i=1}$ ${\displaystyle n}$

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

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

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

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

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

диагональная матрица, ${\displaystyle W}$ ${\displaystyle n\times n}$ ${\displaystyle W_{ii}=w_{i}}$ ${\displaystyle q_{i}}$

$${\displaystyle {\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{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}{\begin{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}}}$$

Вес обычно устанавливается в виде гауссовой функции расстояния между и . ${\displaystyle w_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle p}$

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

Для того чтобы уравнение было разрешимо, оно должно быть обратимым или его собственные значения удовлетворяют . Чтобы избежать проблем с шумом, обычно не требуется, чтобы размер был слишком маленьким. Кроме того, если значение слишком велико, это означает, что точка находится на краю, и этот метод страдает от проблемы апертуры . Итак, чтобы этот метод работал правильно, необходимо, чтобы они были достаточно большими и имели одинаковую величину. Это условие также является условием обнаружения угла . Это наблюдение показывает, что можно легко определить, какой пиксель подходит для работы метода Лукаса-Канаде, проверив одно изображение. ${\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 p}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle \lambda _{2}}$

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

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

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

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

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

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

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

• Оптический поток
• Метод Хорна – Шунка
• Алгоритм обнаружения углов Ши – Томаси
• Трекер функций Канаде – Лукаса – Томаси

Рекомендации

1. BD Лукас и Т. Канаде (1981), Итеративный метод регистрации изображений с применением к стереозрению. Материалы семинара по пониманию изображений, страницы 121–130.
2. Брюс Д. Лукас (1984) Обобщенное сопоставление изображений методом различий (докторская диссертация)
3. JY Буге, (2001) . Пирамидальная реализация аффинного описания алгоритма отслеживания функций Lucas kanade. Корпорация Интел, 5.

Внешние ссылки

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