Lucas–Kanade method

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

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

Концепция

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

$${\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}}$$

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

Эти уравнения можно записать в матричной форме $Av=b$, где $$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}}$$

В этой системе больше уравнений, чем неизвестных, и поэтому она обычно переопределена. Метод Лукаса-Канаде позволяет получить компромиссное решение по принципу наименьших квадратов . А именно, решает $2\times 2$ система $$A^{T}Av=A^{T}b$$ или $$\mathrm {v} =(A^{T}A)^{-1}A^{T}b$$ где $A^{T}$ это транспонирование матрицы $A$. То есть он вычисляет $${\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}}$$ где центральная матрица в уравнении является обратной матрицей . Суммы исчисляются $i=1$ к $n$.

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

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

Приведенное выше простое решение методом наименьших квадратов придает одинаковую важность всем $n$ пиксели $q_{i}$ в окне. На практике обычно лучше придавать больший вес пикселям, расположенным ближе к центральному пикселю. $p$. Для этого используется взвешенная версия уравнения наименьших квадратов: $$A^{T}WAv=A^{T}Wb$$ или $$\mathrm {v} =(A^{T}WA)^{-1}A^{T}Wb$$ где $W$ это $n\times n$ диагональная матрица, содержащая веса $W_{ii}=w_{i}$ быть присвоено уравнению пикселя $q_{i}$. То есть он вычисляет $${\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}}$$

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

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

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

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

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

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

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

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

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

См. также

• Оптический поток
• Метод Хорна – Шунка
• Алгоритм обнаружения углов Ши – Томаси
• Kanade–Lucas–Tomasi feature tracker

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

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