WikiDer > Функция отслеживания Канаде – Лукаса – Томаси

Kanade–Lucas–Tomasi feature tracker

В компьютерное зрение, то Канаде – Лукас – Томаси (KLT) функция отслеживания это подход к извлечение признаков. Предлагается в основном с целью решения проблемы, которую традиционные регистрация изображения методы обычно дорогостоящие. KLT использует информацию о пространственной интенсивности для поиска позиции, которая дает наилучшее соответствие. Это быстрее, чем традиционные методы для изучения гораздо меньшего количества потенциальных совпадений между изображениями.

Проблема регистрации

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

Некоторые меры различия между и :

  • L1 норма =
  • L2 норма =
  • Отрицательная нормализованная корреляция
    =

Базовое описание алгоритма регистрации

Функциональный трекер KLT основан на двух статьях:

В первой статье Лукас и Канаде[1] разработал идею локального поиска с использованием градиентов, взвешенных путем приближения ко второй производной изображения.

Одномерный случай

Если это смещение между двумя изображениями и тогда делается приближение, что

так что

Это приближение к градиенту изображения является точным только в том случае, если смещение локальной области между двумя регистрируемыми изображениями не слишком велико. Приближение к зависит от . Для объединения различных оценок при различных значениях , их естественно усреднить:

Среднее значение может быть дополнительно улучшено путем взвешивания вклада каждого члена в него, который обратно пропорционален оценке , куда

Для облегчения выражения весовая функция определено:

Таким образом, среднее значение с взвешиванием составляет:

После получения сметы может быть перемещен оценкой . Процедура применяется многократно, в результате чего возникает вид Ньютон-Рафсон итерация. Последовательность оценок будет идеально сходиться к наилучшей . Итерация может быть выражена как

Альтернативный вывод

Приведенный выше вывод нельзя хорошо обобщить на два измерения для 2-D линейное приближение происходит иначе. Это можно исправить, применив линейное приближение в виде:

найти что минимизирует L2 стандартная мера разницы (или погрешности) между кривыми, где погрешность может быть выражена как:

Чтобы свести к минимуму ошибку относительно , частично дифференцировать и установите его на ноль:

,

Это в основном то же самое, что и в одномерном случае, за исключением того факта, что весовая функция А форму итерации с взвешиванием можно выразить как:

Спектакль

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

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

Поскольку изображения с фильтром нижних частот могут быть отобраны при более низких разрешающая способность без потери информации применяется стратегия от грубого к точному. Для получения приблизительного соответствия можно использовать сглаженную версию изображения с низким разрешением. Применение алгоритма к изображениям с более высоким разрешением позволит уточнить соответствие, полученное при более низком разрешении.

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

Выполнение

Реализация требует расчета взвешенных сумм величин и по интересующей области Несмотря на то что не может быть рассчитан точно, его можно оценить по:

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

Обобщение на несколько измерений

Алгоритм регистрации для 1-D и 2-D может быть обобщен на большее количество измерений. Для этого мы стараемся минимизировать L2 норма мера погрешности:

куда и являются n-мерными векторами-строками.
Аналогичное линейное приближение:

И частично дифференцировать относительно :

,

который имеет почти ту же форму, что и 1-D версия.

Дальнейшие обобщения

Этот метод также можно расширить, чтобы учесть регистрацию на основе более сложных преобразований, таких как вращение, масштабирование и сдвиг, с учетом

куда является линейным пространственным преобразованием. Тогда минимизируемая ошибка будет

Чтобы определить сумму приспособить и приспособить , опять же, используем линейное приближение:

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

Дальнейшее обобщение предназначено для учета того факта, что яркость может быть разной в двух видах из-за разницы точек обзора камер или из-за различий в обработке двух изображений. Предположим разницу как линейное преобразование:

куда представляет собой настройку контрастности и представляет собой регулировку яркости.
Объединяя это выражение с общей задачей регистрации линейного преобразования:

как количество, которое нужно минимизировать по отношению к и

Обнаружение и отслеживание точечных объектов

Во второй статье Томази и Канаде[2]использовал тот же базовый метод для поиска регистрации из-за перевода, но улучшил метод, добавив функции отслеживания, которые подходят для алгоритма отслеживания. Предлагаемые функции будут выбраны, если оба собственных значения матрицы градиента будут больше некоторого порога.

По очень похожему выводу проблема формулируется как

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

Метод отслеживания, основанный на этих двух документах, обычно считается трекером KLT.

Улучшения и вариации

В третьей статье Ши и Томази[3] предложил дополнительный этап проверки правильности отслеживания объектов.

Аффинное преобразование соответствует между изображением отслеживаемого в данный момент объекта и его изображением из непоследовательного предыдущего кадра. Если аффинно-скомпенсированное изображение слишком непохоже, функция отбрасывается.

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

Используя аналогичный вывод, что и для KLT, Ши и Томаси показали, что поиск может выполняться по формуле

куда матрица градиентов, - вектор аффинных коэффициентов и - вектор ошибок. Сравните это с .

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

  1. ^ Брюс Д. Лукас и Такео Канаде. Метод итерационной регистрации изображений в приложении к стереозрению. Международная совместная конференция по искусственному интеллекту, страницы 674–679, 1981.
  2. ^ Карло Томази и Такео Канаде. Обнаружение и отслеживание точечных объектов. Технический отчет Университета Карнеги-Меллона CMU-CS-91-132, Апрель 1991 г.
  3. ^ Джианбо Ши и Карло Томази. Хорошие возможности для отслеживания. Конференция IEEE по компьютерному зрению и распознаванию образов, страницы 593–600, 1994.

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